Master's Dissertation
DOI
10.11606/D.45.2011.tde-26012012-192041
Document
Author
Full name
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2011
Supervisor
Committee
Lago, Alair Pereira do (President)
Carmo, Renato José da Silva
Ferreira, Carlos Eduardo
Title in Portuguese
Keywords in Portuguese
Análise de Conceitos Formais
Bicliques maximais
Sistemas conceituais de informação
Abstract in Portuguese
Title in English
Concept lattices
Keywords in English
Concept lattices
Conceptual information systems
Formal Concept Analysis
Maximal bicliques
Abstract in English
Formal Concept Analysis (FCA) is a mathematical theory that formalizes the notion of concepts and conceptual hierarchies. Of central importance to this theory is an algebraic structure termed concept lattice. Such structure becomes defined after being given one set of objects, one of attributes, and an incidence relation describing the attributes held by each object. A graphical representation of a concept lattice, by means of a computational interface, is capable of unfolding regularities present in data to an user, who is then able to conduct exploratory data analysis tasks. This sort of FCA application is currently deployed in tens of projects belonging to a wide range of areas, such as medicine, intelligence services, software engineering and bioinformatics. We show in this work an FCA-based system of exploratory data analysis, and its use over real data. Moreover, it is shown how concept lattices can be employed in information retrieval interfaces. From the algorithmic viewpoint, we analyse computational methods for the determination of a concept lattice, and also of a simplified substructure, the concept set. The size of a concept lattice can be exponential when compared to the size of the objects and the attributes sets. Therefore, it is of paramount interest the establishment of upper bounds for the number of concepts of a lattice. In this work, we present the upper bounds already known in the literature. We also establish a new upper bound, and show families of cases in which our bound is sharper than the others. For particular families, our bound is polynomial, whereas the other bounds are exponential.