A Análise de Conceitos Formais (FCA) é uma teoria matemática que formaliza a noção de conceitos e hierarquias conceituais. De importância central a esta teoria é uma estrutura algébrica denominada reticulado de conceitos. Esta estrutura é definida em função de um conjunto de objetos, outro de atributos e uma relação que indica os atributos apresentados por cada objeto. Uma representação gráfica de um reticulado de conceitos, por meio de uma interface computacional, é capaz de expor regularidades presentes em dados a um usuário, e este pode então realizar tarefas de análise exploratória de dados. Este tipo de aplicação de FCA vem sendo empregado em dezenas de projetos pertencentes a áreas diversas, como medicina, serviços de inteligência, engenharia de software e bioinformática. Mostramos neste trabalho um sistema de análise exploratória de dados baseado em FCA, e sua utilização sobre dados reais. Também é mostrado como reticulados de conceitos podem ser empregados em interfaces de recuperação de informação. Do ponto de vista algorítmico, analisamos métodos computacionais para a determinação do reticulado de conceitos, e também de uma subestrutura simplificada, o conjunto de conceitos. O tamanho de um reticulado de conceitos pode ser exponencial em função dos tamanhos dos conjuntos de objetos e de atributos. Assim, é de vital interesse o estabelecimento de cotas superiores para o número de conceitos de um reticulado. Neste trabalho, apresentamos as cotas já conhecidas presentes na literatura. Também estabelecemos uma nova cota superior, e mostramos famílias de casos em que nossa cota superior é mais justa que as demais. Para algumas famílias particulares, nossa cota é polinomial, enquanto que as demais são exponenciais. / 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.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-26012012-192041 |
| Date | 02 December 2011 |
| Creators | Albano, Alexandre Luiz Junqueira Hadura |
| Contributors | Lago, Alair Pereira do |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0022 seconds