Formal Concept Analysis Homepage

Formal Concept Analysis Homepage -- Table of Contents/Sitemap -- Uta Priss

Formal Concept Analysis Algorithms

One of the first FCA algorithms was Bernhard Ganter's Next Concept algorithm, which was published in "Two basic algorithms in concept analysis". Because the original publication is difficult to retrieve, I obtained permission from Bernhard to provide a scanned copy of the algorithm and an example on this site.

At the ICCS'09 there was a competition between FCA algorithms. The winner at that time was Fcbo (FCA algorithms) and the runner-up In-Close. However, subsequent advances in In-Close (notably the 'partial closure' canonicity test) have shown that In-Close now out-performs Fcbo.

Publications on FCA Algorithms

Ganter, Bernhard (1984). Two basic algorithms in concept analysis. (Technical Report FB4- Preprint No. 831). TH Darmstadt. (Reprinted in the ICFCA'10 proceedings).
Kuznetsov, S.; Obiedkov, S (2002). Comparing Performance of Algorithms for Generating Concept Lattices. Journal of Experimental & Theoretical Artificial Intelligence, 14. (Link)
Fu H., Mephu Nguifo E. (2004). A Parallel Algorithm to Generate Formal Concepts for Large Data. ICFCA 2004, LNCS 2961. (Google Books Link)
Van Der Merwe, Dean; Obiedkov, Sergei; Kourie, Derrick (2004). AddIntent: A new incremental algorithm for constructing concept lattices. ICFCA'04. (Link)
Baklouti, Fatma; Levy, Gerard; Emilion, Richard (2005). A fast and general algorithm for Galois lattices building. The Electronic Journal of Symbolic Data Analysis, 2, 1. (Link)
Krajca P., Outrata J., Vychodil V. (2008). Parallel Recursive Algorithm for FCA. In: Belohlavek R., Kuznetsov S. O. (Eds.): Proc. CLA 2008, CEUR WS, 433. (Link)
Andrews S. (2009). In-Close, a Fast Algorithm for Computing Formal Concepts. In: Rudolph, Dau, Kuznetsov (Eds.): Supplementary Proceedings of ICCS'09, CEUR WS 483. (Link)
Krajca P., Outrata J., Vychodil V. (2010). Advances in algorithms based on CbO. CLA'2010. (Link)
Several other papers presented at the CLA'2010 conference.
Strok, F; Neznanov, A. (2010). Comparing and analyzing the computational complexity of FCA algorithms. Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists. (Link)

Data sources

There are no standard datasets for FCA. Different researchers use different sets from different sources (mostly data mining sources), such as

FCA Data Repository
Wikipedia and Clinical Trials Data
UCI ML Repository
Kdnuggets: data sets
FIMI repository

A popular data set is the mushroom data from UCI.