Computing and Visualizing Concept Lattices

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