Skip to Main content Skip to Navigation

Contributions to indexing and retrieval using Formal Concept Analysis

Victor Codocedo-Henriquez 1
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : One of the first models ever to be considered as an index for documents using terms as descriptors, was a lattice structure, a couple of decades before the arrival of Formal Concept Analysis (FCA) as a solid theory for data mining and knowledge discovery. While the Information Retrieval (IR) community has shifted to more advanced techniques for document retrieval, like probabilistic and statistic paradigms, the interest of the FCA community on developing techniques that would improve the state-of-the-art in IR while providing relevance feedback and semantic based features, never decayed. In this thesis we present a set of contributions on what we call FCA-based IR systems. We have divided our contributions in two sets, namely retrieval and indexing. For retrieval, we propose a novel technique that exploits semantic relations among descriptors in a document corpus and a new concept lattice navigation strategy (called cousin concepts), enabling us to support classification-based reasoning to provide better results compared with state-of-the-art retrieval techniques. The basic notion in our strategy is supporting query modification using ``term replacements'' using the lattice structure and semantic similarity. For indexing, we propose a new model that allows supporting the vector space model of retrieval using concept lattices. One of the main limitations of current FCA-based IR systems is related to the binary nature of the input data required for FCA to generate a concept lattice. We propose the use of pattern structures, an extension of FCA to deal with complex object descriptions, in order to support more advanced retrieval paradigms like the vector space model. In addition, we propose an advanced model for heterogeneous indexing through which we can combine the vector space model and the Boolean retrieval model. The main advantage of this approach is the ability of supporting indexing of convex regions in an arbitrary vectorial space built from a document collection. Finally, we move forward to a mining model associated with document indexing, namely exhaustive bicluster enumeration using FCA. Biclustering is an emerging data analysis technique in which objects are related by similarity under certain attributes of the description space, instead of the whole description space like in standard clustering. By translating this problem to the framework of FCA, we are able to exploit the robust machinery associated with the computation of concept lattices to provide an algorithm for mining biclusters based on similar values. We show how our technique performs better than current exhaustive enumeration biclustering techniques.
Complete list of metadata

Cited literature [130 references]  Display  Hide  Download
Contributor : Victor Codocedo Connect in order to contact the contributor
Submitted on : Friday, December 11, 2015 - 9:38:24 AM
Last modification on : Saturday, October 16, 2021 - 11:26:07 AM
Long-term archiving on: : Saturday, April 29, 2017 - 10:37:15 AM


  • HAL Id : tel-01751990, version 2


Victor Codocedo-Henriquez. Contributions to indexing and retrieval using Formal Concept Analysis. Artificial Intelligence [cs.AI]. Université de Lorraine, 2015. English. ⟨NNT : 2015LORR0143⟩. ⟨tel-01751990v2⟩



Record views


Files downloads