Formal Concept Analysis and Pattern Structures for mining Structured Data

Aleksey Buzmakov 1
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Nowadays, more and more data of different kinds is becoming available. Various datasets contain valuable information that could help to solve many practical problems or to lead to a breakthrough in fundamental science. But how can one extract these precious pieces of information? Formal concept analysis (FCA) and pattern structures are theoretical frameworks that allow dealing with an arbitrary structured data. But how can one put it into practice? Furthermore, the number of concepts, i.e., elementary pieces of information, extracted by FCA is typically huge. To deal with this problem one can either simplify the data representation, which can be done by projections of pattern structures, or by introducing constraints to select the most relevant concepts. What is the best data simplification? How to find concepts efficiently satisfying a given constraint? These are the questions that we address in this work. The manuscript starts with application of FCA to mining important pieces of information from molecular structures. These molecular structures are encoded as sets of attributes. Even for this simple encoding and without any additional constraints, FCA is able to extract important pieces of information from small datasets. With the growth of dataset size good constraints begin to be essential. For that we explore stability of a concept, a well-founded formal constraint. We show experimentally that it is a good choice and apply it to analyze a dataset of mutagenetic chemical substances. Finding stable concepts in this dataset allows us finding new possible mutagenetic candidates that can be further interpreted by chemists. However for more complex cases, the simple attribute representation of data is not enough. Correspondingly, we turn to pattern structures that can deal with many different kinds of descriptions. The important point about pattern structures is that they allow data simplification by means of projections. We extend the original formalism of projections to have more freedom in data simplification. We show that this extension is essential for analyzing patient trajectories, describing patients hospitalization histories. Indeed, patient trajectories are sequences of hospitalizations and every hospitalization is described by a heterogeneous description. This data is very rich and hence, produce a lot of concepts. The new type of projections allows efficient reduction of concept space and in combination with stability constraints can find important common trajectories. In addition, projections are useful to correct linked open data, a data that is distributed all over the world and that can be enriched by any person. The errors are inevitable but some of them can be efficiently found by an approach based on pattern structures. Yet another application of pattern structures is mining of drug-drug interactions from text corpuses. Based on a text of corpuses we are able to find and explain syntactic structures encoding this kind of relation. So far pattern structures do not allow direct finding of patterns satisfying the stability constraint. Correspondingly, the manuscript ends by an original and very efficient approach that enables to mine stable patterns directly. This approach is called Σοφια and is able to find the best stable patterns in polynomial time. The efficiency is essential for mining large datasets and this highlights the importance of Σοφια. We evaluate this new algorithm on several datasets and the experiments show the significant improvement of Σοφια w.r.t. its competitors for attribute and interval tuple data. Moreover it open a new direction of research for mining different types of patterns in polynomial time that is very important in the world of large data.
Complete list of metadatas

Cited literature [251 references]  Display  Hide  Download

https://hal.inria.fr/tel-01751818
Contributor : Aleksey Buzmakov <>
Submitted on : Monday, November 23, 2015 - 3:02:29 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:02 PM
Long-term archiving on : Friday, April 28, 2017 - 9:30:00 PM

Identifiers

  • HAL Id : tel-01751818, version 2

Citation

Aleksey Buzmakov. Formal Concept Analysis and Pattern Structures for mining Structured Data. Artificial Intelligence [cs.AI]. Universite de Lorraine, 2015. English. ⟨NNT : 2015LORR0112⟩. ⟨tel-01751818v2⟩

Share

Metrics

Record views

965

Files downloads

1794