TU Darmstadt / ULB / tuprints

Computing and Visualizing Concept Lattices

Yevtushenko, Serhiy :
Computing and Visualizing Concept Lattices.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2004)

[img]
Preview
PDF
diss-yevtushenko.pdf
Available under Simple publication rights for ULB.

Download (1193Kb) | Preview
Item Type: Ph.D. Thesis
Title: Computing and Visualizing Concept Lattices
Language: English
Abstract:

One of the tasks of Artificial Intelligence is to model abilities that are generally considered as human by means of computers. One such ability is to analyze data and make decisions on the basis of the results. Another ability that is tightly connected with the first one is to represent knowledge and perform reasoning on the basis of this knowledge. Among the areas of the artificial intelligence in which these abilities are explored and used in applications are Machine Learning and related to it Knowledge Discovery in Databases (KDD), sometimes also referred as Data Mining. In recent years the number of applications of Data Mining has swiftly grown. One of the methods of data mining that is gaining recognition is Formal Concept Analysis (FCA). The peculiarity that distinguishes FCA from many other data analysis methods is the absence of loss of information during the analysis of data. This peculiarity is at the same time an advantage and a disadvantage of the method: it is an advantage because the user can be sure that no important details were left out, and a disadvantage because the computational expenses arising when applying this method are very high. In the thesis the two central tasks for Formal Concept Analysis are explored: the task of computing the set of all concepts and the task of visualizing concept lattices. The task of computing the set of all concepts and its line diagram has a central importance for applications using FCA. Also, it plays an important role in several fields of data analysis that are related to Formal Concept Analysis, namely, the association analysis and the JSM method for hypothesis generation. In this thesis, a new algorithm called Grail computing concept lattices is developed. An experimental comparison with existing approaches is conducted. Additionally, another approach for computing the set of all concepts based on usage of Binary Decision Diagrams is investigated and a family of algorithms using BDDs is developed. These algorithms are shown to have better performance for the cases that are hard for algorithms using explicit representation. The second part of the thesis is concerned with the question of how to visualize concept lattices. After computing a concept lattice, it can be presented to the user for examination. Good visualization of concept lattices is important because it very much determines how much information a user can extract and hence the quality of analysis. Proper visualization of concept lattices as line diagrams allows to structure the data and to exhibit dependencies that exist between different attributes in the data. Two new methods for drawing concept lattices are developed and compared with previous methods in this thesis.

Alternative Abstract:
Alternative AbstractLanguage
Ein Ziel der Künstlichen Intelligenz ist die Modellierung von Fähigkeiten, die man üblicherweise Menschen zuschreibt, mittels Computern. Eine solche Fähigkeit ist die Analyse von Daten und das Treffen von Entscheidungen aufgrund der Ergebnisse dieser Analyse. Eine weitere Fähigkeit, die eng mit der ersten verknüpft ist, ist die Repräsentation von Wissen sowie das logische Schließen auf der Basis des repräsentierten Wissens. Zwei der Bereiche der Künstlichen Intelligenz, in denen die genannten Fähigkeiten erforscht und in Systemen angewendet werden, sind die Gebiete des Maschinellen Lernens und das verwandte Gebiet der Wissensentdeckung in Datenbanken, das auch als Data Mining bezeichnet wird. In den letzten Jahren ist die Zahl der Anwendungen des Data Mining stark gestiegen. Eine Methode des Data Mining, die in letzter Zeit viel Beachtung fand, ist die formale Begriffsanalyse (FBA). Im Gegensatz zu vielen anderen Analysemethoden kommt es bei der FBA nicht zu Informationsverlusten während der Analyse der Daten. Diese Eigenheit ist gleichzeitig ein Vor- und ein Nachteil der Methode: Sie ist ein Vorteil, da der Benutzer sicher sein kann, dass keine wichtigen Details verloren gehen; sie ist ein Nachteil, weil der Rechenaufwand für diese Methode sehr hoch ist. In dieser Dissertation werden zwei zentrale Aufgaben der FBA erforscht: Die Aufgabe, die Menge aller Konzepte zu berechnen und die Aufgabe, Konzeptverbände zu visualisieren. Das Berechnen der Menge aller Konzepte sowie die Visualisierung von Konzeptverbänden hat zentrale Bedeutung bei der praktischen Anwendung von FBA-Methoden. Des weiteren spielen diese Aufgaben eine wichtige Rolle in einigen anderen Gebieten der Datenanalyse wie Assoziationsanalyse (engl. Association Analysis) und der JSM-Methode für Hypothesengenerierung. In dieser Dissertation wird ein neuer Algorithmus zur Berechnung von Konzeptverbänden namens Grail entwickelt. Dieser Algorithmus wird experimentell mit existierenden Ansätzen zur Berechnung von Konzeptverbänden verglichen. Zusätzlich wird ein weiterer Ansatz zur Berechnung von Konzeptverbänden vorgestellt und untersucht, der binäre Entscheidungsdiagramme benutzt (engl. Binary Decision Diagrams, BDD). Dieser Ansatz resultiert in einer ganzen Familie von konkreten Algorithmen, die BDD benutzen. Es wird gezeigt, dass die resultierenden Algorithmen gerade auch für solche Problemstellungen, die für Algorithmen mit expliziter Darstellung schwierig zu lösen sind, eine bessere Performanz haben. Der zweite Teil dieser Dissertation beschäftigt sich mit Visualisierung von Konzeptverbänden. Nachdem ein Konzeptverband berechnet wurde, kann er einem Benutzer zur Auswertung präsentiert werden. Dabei spielt eine gute Visualisierung eine wichtige Rolle, da sie ganz wesentlich bestimmt, wie viel Information der Benutzer extrahieren kann und demnach wie gut die Analyse durch den Benutzer sein kann. Eine angemessene Visualisierung als Liniendiagramm (engl. Line Diagram) erlaubt die Strukturierung der Daten und das Aufzeigen von Abhängigkeiten zwischen Datenmerkmalen. In dieser Dissertation werden zwei neue Methoden zur Visualisierung von Konzeptverbänden als Liniendiagramm entwickelt und mit anderen Visualisierungsmethoden verglichen.German
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:21
Last Modified: 07 Dec 2012 11:50
Official URL: http://elib.tu-darmstadt.de/diss/000488
URN: urn:nbn:de:tuda-tuprints-4884
License: Simple publication rights for ULB
Referees: Bibel, Prof. Dr. Wolfgang and Ganter, Prof. Dr. Bernhard
Advisors: Bibel, Prof. Dr. Wolfgang
Refereed: 7 October 2004
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/488
Export:

Actions (login required)

View Item View Item