Introduced by Rudolf Wille in the mid-80s, Formal Concept Analysis (FCA) is a mathematical framework that offers conceptual data analysis and knowledge discovery. FCA analyzes the data, which is represented in the form of a formal context, that describe the relationship between a particular set of objects and a particular set of attributes. From the formal context, FCA produces hierarchically ordered clusters called formal concepts and the basis of attribute dependencies, called attribute implications. All the concepts of a formal context form a hierarchical complete lattice structure called concept lattice that reflects the relationship of generalization and specialization among concepts. Several algorithms are proposed in the literature to extract the formal concepts from a given context. The objective of this chapter is to analyze, demonstrate, and compare a few standard algorithms that extract the formal concepts. For each algorithm, the analysis considers the functionality, output, complexity, delay time, exploration type, and data structures involved.
TopIntroduction
Formal Concept Analysis (FCA) is a mathematical framework based on mathematical order and lattice theory which supports knowledge discovery in databases. The unique aspect of FCA is the integration of several components of conceptual data and knowledge processing. These components include discovery and reasoning with concepts and dependencies in data, visualization of concepts and dependencies. With such integration, FCA has been successfully applied in different domains including gene expression data analysis, ontology design, software code analysis, psychology etc (Kaytoue et al. 2011, Krohn et al. 1999, Mephu & Ngiwoua 1998, Priss 2006, Priss & Old 2004, Priss et al., 2007). Knowledge representation in FCA is shown in the form of formal concepts (Boulicaut & Besson 2008, Ganter & Wille 1999, Jurekevicius & Vasilecas 2009, Stumme 2009, Stumme et al. 2002), concept lattices(Stumme et al. 1998, Valtchev et al. 2002, Wille 1982) and association rules(Agrawaal & Srikant, 1994, Aswani Kumar, 2011, Aswani Kumar & Srinivas, 2010, Stumme et al. 2001, Zhang and Wu 2011). FCA starts the analysis on a data matrix, known as formal context, specifying a set of objects, a set of attributes and the relation between them (Wille, 1982). FCA has been successfully extended into fuzzy settings(Ghosh et al, 2010, Prem Kumar and Aswani Kumar, 2012a, 2012b, Maio et al., 2012), however this study is focused on FCA in crisp setting. From the formal context, FCA finds the natural clusters of objects that share a common subset of attributes and natural clusters of attributes that are shared by natural object clusters (Shi et al., 2007). A formal concept is a pair containing object cluster and corresponding attribute cluster. Concept lattice structure visualizes all the concepts (Belohlavek and Vychodil, 2009). The notion “formal” emphasizes that concepts are mathematical objects. The sets of objects and attributes in a formal concept mutually relate each other through a Galois connection which induces closure operator. The set of all the concepts of a given context is partially ordered and form a complete lattice. Main features of FCA include mathematical background, algorithmic methods that can perform conceptual clustering through concept lattice, rule mining through attribute implications, data apposition and concatenation makes FCA a suitable paradigm for KDD (Maddouri, 2005, Stumme, 1995, Zhang & Wu, 2011). Due to the closure properties and mathematical order theory that FCA follows, only the patterns of maximal size are extracted which reduces the exploration and increases the efficiency while mining the data. Through attribute implications, FCA provides a compact representation of knowledge. These attribute implications are closely associated with functional dependencies in the database field (Poelmans et al. 2010, Stumme 2002a, Wu et al. 2009).