Graph Theoretic Lattice Mining Based on Formal Concept Analysis (FCA) Theory for Text Mining

Hasni Hassan, Noraida Ali, Aznida Hayati Zakaria, Mohd Isa Awang, Abd Rasid Mamat


The growth of the semantic web has fueled the need to search for information based on the understanding of the intent of the searcher, coupled with the contextual meaning of the keywords supplied by the searcher. The common solution to enhance the searching process includes the deployment of formal concept analysis (FCA) theory to extract concepts from a set of text with the use of corresponding domain ontology. However, creating a domain ontology or cross-platform ontology is a tedious and time consuming process that requires validation from domain experts. Therefore, this study proposed an alternative solution called Lattice Mining (LM) that utilizes FCA theory and graph theory. This is because the process of matching a query to related documents is similar to the process of graph matching if both the query and the documents are represented using graphs. This study adopted the idea of FCA in the determination of the concepts based on texts and deployed the lattice diagrams obtained from an FCA tool for further analysis using graph theory. The LM technique employed in this study utilized the adjacency matrices obtained from the lattice outputs and performed a distance measure technique to calculate the similarity between two graphs. The process was realized successively via the implementation of three algorithms called the Relatedness Algorithm (RA), the Adjacency Matrix Algorithm (AMA) and the Concept-Based Lattice Mining (CBLM) Algorithm. A similarity measure between FCA output lattices yielded promising results based on the ranking of the trace values from the matrices. Recognizing the potential of this method, future work includes refinement in the steps of the CBLM algorithm for a more efficient implementation of the process.


formal concept analysis; graph theory; text mining; adjacency matrix

Full Text:




Published by INSIGHT - Indonesian Society for Knowledge and Human Development