FCA_Retrieval: A Multi-operator Algorithm for Information Retrieval from Binary Concept Lattice

FCA Retrieval: A Multi-operator Algorithm for Information Retrieval from Binary Concept Lattice Fethi Fkih MARS Research Lab LR17ES05 University of Sousse Tunisia fethi.fkih@gmail.com Mohamed Nazih Omri MARS Research Lab LR17ES05 University of Sousse Tunisia mohamednazih.omri@fsm.rnu.tn Abstract The use of a concept lattice for the vi- sual representation of knowledge has become very common in the data mining field. In- deed, the theory of Formal Concept Anal- ysis (FCA) gives the possibility of organiz- ing and making reasoning on the knowledge stored in the lattice. In this context, we pro- pose FCA Retrieval a fast and efficient algo- rithm for information retrieval from a binary concept lattice. This algorithm can respond to queries containing several types of logical operators (conjunction, disjunction and nega- tion). The experimental study proves the good performance of our algorithm. 1 Introduction With the evolution of documents quantity in databases, it has become very difficult to extract the information corresponding to the exact needs of the user in a reasonable time without the design of an ef- fective strategy. Indeed, this strategy must be based, first, on the right representation of the information found in the documents or in the query and, sec- ondly, on the development of an efficient and fast algorithms for information retrieval (Fkih and Omri, 2012). In this context, concept lattices are considered as very powerful tools for the visual presentation of knowledge (Poelmans et al., 2013). Also, For- mal Concept Analysis (FCA) is considered a flex- ible and practical theoretical framework for binary relations management. The relation between a doc- ument and the information that presents it is a binary relation (the information presents the document or not). Therefore, a concept lattice can easily model the document/term relation and can be considered as an semantic index (Fkih and Omri, 2016). In this paper, we propose an efficient algorithm (FCA Retrieval) for the retrieval of information in a concept lattice. This algorithm uses the theory of formal concept analysis (FCA) to respond to a user query and retrieve the information in a reasonable time. The main advantage of this algorithm is that it can handle multiple logical operators queries (i.e. conjunctive, disjunctive and negation operators). The remainder of this paper is structured as fol- lows. In section 2,we provide an overview on the works that use the concept lattice for documents in- dexing. Section 3 presents the basic notions of the Formal Concept Analysis (FCA) theory. In section 4, we introduce our algorithm, FCA Retrieval, for information retrieval in a concept lattice. Section 5 is reserved for an experimental comparative study between the proposed model and other models in the literature. 2 Related Works The use of concept lattices for information retrieval began with the introduction of the Formal Con- cept Analysis (FCA) theory by (Wille, 1982) in the 1980s. Information retrieval is considered a direct application of the concept lattice due to the high correspondence between the theoretical foundations of this approach and those of information retrieval (Godin et al., 1995). Indeed, …

Content truncated to 500 words