Projekt Knowledge Discovery and Data Engineering Sommersemester 2021

Knowledge Extraction from OpenStreetMap

Bei OpenStreetMap (OSM) handelt es sich um ein freies Projekt, dessen Ziel es ist, frei nutzbare Geodaten zu sammeln, zu strukturieren und für die Nutzung durch jedermann mittels einer (semantischen) Datenbank zur Verfügung zu stellen. Die Daten in OSM werden insbesondere durch eine Vielzahl von Tags [1] angereichert. Diese Tags können wiederum genutzt werden, um Orte oder Gebiete zu bechreiben. Im Projekt soll daher versucht werden, für gegebene Orte automatisch eine Beschreibung mittels Tags zu generieren. Für das Projekt soll eine Demonstrationsapplikation entwickelt werden, in Clojure oder Python3, welche es erlaubt, gegebene Orte automatisch anhand ihrer Beschreibung aus OSM zu vergleichen. Im Rahmen einer Abschlussarbeit kann darauf aufbauend ein ontologisches Rahmenwerk für diese Art von Ortsvergleichen angefangen werden.
[1] https://wiki.openstreetmap.org/wiki/Tags

Informationen: Tom Hanika

Causal AI — Implementing Causal Closure Operators

Eine große Herausforderung in der KI-Forschung ist es, kausale Zusammenhänge aus gelernten Modellen zu extrahieren. Die Formale Begriffsanalyse bietet dafür eine umfangreiche Palette an Werkzeugen, insbesondere die menschlich-nachvollziehbare Extraktion von Hüllenoperatoren und Hüllensystemen aus Daten. Ein interessanter Ansatz, dies für Kausale-KI zu nutzen, sind kausale Hüllenoperatoren, welche in diesem Projekt oder dieser Arbeit untersucht werden sollen. Dabei liegt für das Projekt der Schwerpunkt in einer effizienten Implementierung eines `Causal Closure Operators` aus der Literatur in Clojure oder Python3. Bei einer Abschlussarbeit liegt der Fokus auf einem Vergleich dieses Operators mit statistischen Ansätzen zu Kausalität in Daten.

Informationen: Tom Hanika

Analyse von WikiCite

Das WikiCite-Projekt [1] versucht, basierend auf der Infrastruktur von WikiData [2], (wissenschaftliche) Publikationen und deren jeweilige Zitationen abzubilden. Bis dato hat das Projekt 40 Mio. Publikationen und ca. 300 Mio Zitationen verlinkt. Ziel dieses Bachelor-/Master-Projektes bzw. einer möglichen Abschlussarbeit ist es, diese Daten hinsichtlich sozialer Netzwerkstrukturen zu analysieren.

[1] http://wikicite.org/

[2] https://www.wikidata.org/

Informationen: Tom Hanika

Topic Flow-Graphen für Textdaten visualisieren

Topic-Modelle ermöglichen es, große Text-Corpora thematisch zu clustern und so besser zu verstehen. Dabei ist es besonders interessant zu messen, wie stark verschiedene Themencluster andere über die Zeit beeinflusst haben. In `Research Topic Flows in Co-Authorship Networks` [1] haben die Autoren einen Vorschlag zur Messung dieses Einflusses gemacht, dessen Ergebnisse demnächst auf einer Website (basierend auf Vue.js) interaktiv explorierbar sind. Im vorliegenden Projekt soll diese Präsentation der Ergebnisse erweitert werden. Genauer sollen thematische Beiträge einzelner Autoren aus dem Gesamtmodell berechnet und grafisch visualisiert werden. Die Implementation soll ebenso mittels Vue.js stattfinden.

[1] https://arxiv.org/pdf/2206.07980.pdf

Informationen: Tom Hanika

Intrinsische Dimension und Knoteneinbettungen

In dieser Arbeit soll untersucht werden, wie hoch die intrinsische Dimension von Datensätzen ist, welche mit verschiedenen Knoteneinbettungsverfahren aus Graphen erstellt wurden.

Informationen: Maximilian Stubbemann

Community Detection in WikiData zur Datensatzgenerierung

Knowlegde Graphs wie WikiData enthalten sehr viel Wissen, das im Bereich der künstlichen Intelligenz in vielen Anwendungen eingesetzt werden kann. Der Umfang an Informationen ist aber auch ein Problem für viele Anwendungen. Ihre Aufgabe besteht darin, Methoden der Community Detection in sozialen Netzwerken auf die Struktur von WikiData zu übertragen. Des Weiteren sollen Sie untersuchen, wie diese Methoden genutzt werden können, um kleinere Teil-Datensätze aus WikiData zu extrahieren.

Informationen: Johannes Hirth

Logische Repräsentationen für Skalenmaße

Eine Methode der Datenskalierung in der Formalen Begriffsanalyse sind Skalenmaße. Das Skalenmaß-Framework bietet eine kanonische Repräsentation für jede mögliche Skalierung. Diese Repräsentation ist aber nicht gut im Sinne der Interpretierbarkeit der Attribute. Um dieses Problem zu lösen, gibt es eine Interpretation der kanonischen Attribute mittels konjunktiv verknüpfter Attribute des Originaldatensatzes. In dieser Arbeit sollen Sie weitere logische Repräsentation erarbeiten und miteinander auf deren Interpretierbarkeit, Ausdrucksstärke und Berechenbarkeit vergleichen.

Informationen: Johannes Hirth

Evaluierung von Graphzeichnungen

Ziel dieser Arbeit ist es, zu evaluieren, welche “weichen” Kriterien für Graphzeichnungen in der Praxis wie stark mit als “schön” wahrgenommenen Zeichnungen korellieren. Außerdem soll untersucht werden, inwieweit die “wichtigen” Kriterien sich beim Zeichnen von Graphen und Ordnungsdiagrammen unterscheiden.

Informationen: Maximilian Stubbemann

Einbettungsverfahren für Formale Kontexte

Ziel dieses Projektes ist es, Verfahren zur Einbettung von Gegenständen und Objekten in formalen Kontexten zu recherchieren und für conexp-clj zu implementieren.

Informationen: Maximilian Stubbemann

Automatisierte Themenbenennung

Topic Models berechnen i.d.R. Themen, aus denen sich ihre “wichtigsten” Wörter ableiten lassen. In der Forschung existieren bereits einige Ansätze zur automatisierten Benennung von Themen solcher Wortmengen. In dieser Arbeit sollen verschiedene bestehende sowie mindestens ein eigener Ansatz implementiert und miteinander verglichen werden.

Informationen: Bastian Schäfermeier

Planar polyline edge-length ratio on a fixed grid

The planar edge-length ratio of a straight-line drawing is defined as the ratio between the length of longest edge and the length of the shortest edge. There has been recent attention to this topic with several publications, for example. The planar polyline edge-length ratio is a generalization of the planar edge-length ratio where edges do not have to be straight-line segments, but can be polylines with a maximum number of bends per edge defined by the input.

The goal of this project is to develop an algorithm in order to minimize the planar polyline edge-length ratio.

Informationen: Dominik Dürrschnabel

Thematische Trajektorien mit Dynamischen Topic Models

Am Fachgebiet Wissensverarbeitung wird zur Zeit an thematischen Trajektorien von wissenschaftlichen Konferenzen und Journalen geforscht. In unserer Forschung wurden (statische) Themen durch die sogenannte Nonnegative Matrix Factorization (NMF) extrahiert. In dieser Arbeit sollen dynamische Verfahren, bei denen sich Themen über die Zeit ändern (z.Bsp. D-LDA), auf ihre Tauglichkeit überprüft werden.

Informationen: Bastian Schäfermeier

Heuristiken für das Sugiyama-Framework

Das Sugiyama Framework ist ein Framework für die automatische Generierung von Zeichnungen von Graphen und Netzwerken. Dabei müssen mehrere NP-schwere Probleme mit Hilfe von Heuristiken gelöst werden.

Das Ziel dieses Projektes ist es, die wichtigsten Heuristiken aufzuarbeiten und diese miteinander, sowie (wo möglich) mit einer exakten Lösung der Probleme zu vergleichen. Dafür soll eine User-Studie durchgeführt werden.

Informationen: Dominik Dürrschnabel

K-Means und FCA

K-means, oder genauer Lloyds-Algorithmus, ist eine Technik, durch welche Datenpunkte im Euklidischen Raum in eine Anzahl von k-Clustern zerlegt werden können. Durch wiederholtes Ausführen mit unterschiedlichem k entsteht eine Menge von sich teilweise überlappenden Clustern. Durch das Hinzufügen der Schnitte der einzelnen Cluster können diese zu einer Verbandsstruktur erweitert werden. Dieser Verband wiederum hat einen zugehörigen formalen Kontext.

Das Ziel dieses Projektes ist es zu untersuchen, inwiefern diese Cluster mit dem Hüllensystem des formalen Kontextes zusammenhängen.

Informationen: Dominik Dürrschnabel

Invarianten für Formale Kontexte

Es ist nicht einfach zu erkennen, ob zwei (reduzierte) Formale Kontexte isomorph sind, bzw. gegeben eine Menge Formaler Kontexte zu erkennen, wie viele verschiedene Formale Kontexte dort enthalten sind. Ein Hilfsmittel sind Invarianten, also abgeleitete Größen, die nicht von der konkreten Darstellung des Formalen Kontexts abhängen, beispielsweise die Anzahl der Attribute des Kontexts oder auch die Anzahl der Begriffe des Kontexts. Haben zwei Kontexte unterschiedliche Werte für eine Invariante, so sind die Kontexte nicht isomorph. Ziel ist es, Formale Kontexte hinsichtlich möglicher Invarianten zu untersuchen. Formale Kontexte können als bipartite Graphen dargestellt werden, daher sollen insbesondere bekannte Graph-Invarianten in Betracht gezogen werden.

Informationen: Maximilian Felde

Begriffliches Skalieren von Datensätzen

Begriffliches Skalieren ist eine Methode der Formalen Begriffsanalyse, um einen mehrwertigen Kontext (d.h. einen tabellarischen Datensatz) in einen (einwertigen) formalen Kontext zu überführen. Dazu wurde am Fachgebiet eine Anwendung entwickelt, die grundlegende Funktionalität zum Begrifflichen Skalieren bereitstellt. Ziel des Projekts ist es, diese Anwendung weiterzuentwickeln. Die Programmiersprache ist Clojurescript.

Informationen: Maximilian Felde

Erklärbarkeit von Klassifikatoren durch Surrogate

Viele der gegenwärtig genutzten Lernmodelle zur Klassifikation erzeugen sogenannte Blackbox-Funktionen/Relationen, z.B. Random Forests oder Neuronale Netze. Diese entziehen sich einer direkten Erklärbarkeit und sind daher für Nutzer:innen schwer nachvollzieh- und überprüfbar. Es gibt verschiedene numerische / kategorische/ statistische Ansätze, um diesem Problem zu begegnen. Ein besonderer Ansatz ist Surrogatlernen, d.h., das Trainieren eines erklärbaren Klassifikators basierend auf einer Blackbox. Je nach Ausrichtung (Projekt/Bachelorarbeit/Masterarbeit) soll versucht werden, bestehende Surrogat-Ansätze praktisch zu evaluieren oder theoretische Ansätze fortzusetzen.

Informationen: Tom Hanika

FCA RuleMining mittels GPU

Die Berechnung von Implikationsbasen in Formalen Kontexten (binären Datentabellen) basiert auf einem co-NP schweren Problem. Um dennoch Wissen in Form von Implikationen zu extrahieren, wurden verschiedene Maße für `interessante` Regeln und deren Berechnung gefunden. Da auch deren Berechnung bei wachsenden Datensätzen einer kombinatorischen Explosion gegenübersteht, ist eine hohe Parallelisierung mittels GPU-Hardware notwendig. In `GPU-Accelerated Parameter Optimization for Classification Rule Learning` schlagen die Autoren eine Variante von “beam-search” auf GPUs vor, die in dem vorliegenden Projekt untersucht, implementiert und auf Formale Kontexte angewendet werden soll.

Informationen: Tom Hanika

Reduktionstechniken in der Formalen Begriffsanalyse

Ein Problem für Algorithmen der Formalen Begriffsanalyse ist die Größe der Daten. In dieser Arbeit sollen verschiedene Techniken zur Größenreduktion oder Kompression zusammengetragen und gegenübergestellt werden. Dabei soll insbesondere auf den Informationsverlust in einem geeigneten Formalismus eingegangen werden.

Informationen: Johannes Hirth

PCA auf formalen Kontexten

Principal Component Analysis dient dazu, Datensätze zu vereinfachen. Hierbei wird eine große Menge an (möglicherweise) korrelierten Variablen in eine möglichst aussagekräftige kleinere Menge transformiert. Dieses Vorgehen soll auf formale Kontexte übertragen werden, um ihre Merkmalsmenge einzuschränken.

Informationen: Maren Koyda