Formal Concept Analysis

• Best place to start for link and examples: FCA Home. Unfortunately, there seems to be little or no information provided about the algorithms, languages, and interoperability (file formats, e.g.) of the various tools listed. I'll try to remedy that here.

• On algorithms for construction line diagrams of concept lattices and the set of all concepts by Serhiy A. Yevtushenko, 2001. 55 slides. Includes presentation of the GRAIL algorithm used by ConExp.
• An Introduction to using Relation Algebra with FCA, Uta Priss, www.upriss.org.uk, Version 1.2, May 2009.
• Comparing performance of algorithms for generating concept lattices by SERGEI O. KUZNETSOV{ and SERGEI A. OBIEDKOV, 2002. Performance testing of nine algorithms, each of which is described in pseudocode: Bordat, NextClosure, Close by One, Lindig, Chein, Nourine, Norris, Godin,Dowling

• ConExp The Concept Explorer. Java language, GRAIL algorithm, ConExp provides the following tools:
  • context editing,
  • building concept lattices from a formal context,
  • finding a base for implications that are true in formal context,
  • finding a base of association rules that are true in formal context and
  • performing attribute exploration.
  • Currently the following formats are supported:
    • ConExp native format *.cex: This is an XML-based format. It stores information about the context and the lattice line diagram. In addition to the others it stores the information whether implications and/or association rules were calculated. We recommend to use this format.
    • ConImp context data *.cxt: It is possible to work with contexts, that were created using ConImp. The disadvantage is, only the context can be encoded in this format.
    • Comma Separated Values *.csv: So far ConExp supports only the import of contexts in this format. Actual separator is semicolon (;). It is assumed, that the first line of the file contains attributes names and the first cell is empty. (I.e, if one has a context with attributes attr1 and attr2, then first line will be the following: ;attr1;attr2.) Each of the succeeding lines should start with an object name followed by a sequence of 0s and 1s. A cross will appearer in all cells of the imported context, where a 1 has been set.
    • formats#oal|Object Attribute List *.oal: So far ConExp supports only the import of contexts in this format.
• fcalgs by by Petr Krajca, Jan Outrata, and Vilem Vychodil. ; parallel recursive implementation of Kuznetsov's CbO (Close by One) algorithm. The INPUT-FILE is in the usual FIMI format. The code is C and “parallel” is an option; it can be run as the sequential algorithm. In fact, the parallelism only kicks in after the sequential algorithm has built a good foundation for the threads to complete. Whereas CbO as originally described adds objects to the extent one by one, intersecting their intents with the previous intent (as long as the intersection is not empty), pcbo processes the dual problem: it adds attributes to the intent and intersects the extent of the new attribute with the extent of the previous concept. It appears to be about 100 times faster than any other algorithm for binary attributes. More recently, Simon Andrews published an algorithm called In-Close similar in concept, but with different choices of pre-calculation and memory usage, which seems to be about 40 times faster than the sequential version of pcbo!
• FcaStone
  • FcaStone (named in analogy to “Rosetta Stone”) is a command-line utility that converts between the file formats of commonly-used FCA tools (such as ToscanaJ, ConExp, Galicia and Colibri) and between FCA formats and other graphics formats. The main purpose of FcaStone is to improve the interoperability between FCA, graph editing and vector graphics software.
  • FcaStone can
    • convert between commonly used FCA file formats (cxt, cex, csc, slf, bin.xml, and csx).
    • convert between FCA file formats and comma separated value (csv) files as exported from and imported into databases and spreadsheets.
    • convert formal contexts into the xfig format or into Bernhard Ganter's latex format.
    • convert concept lattices into graph formats (dot, gxl, gml, …) for use by graph editors (yEd, jgraph, …) or into vector graphics formats (fig, svg, …) for use by vector graphics editors (Xfig, Dia, Inkscape, …).
    • convert formal contexts into lattice diagrams (using Graphviz's layout).
    • serve as a component of a server-side script for generating lattices on webpages.
  • The emphasis of FcaStone is on converting file formats, not on fast algorithms for lattice construction which are already provided by other FCA software.

Serhiy A. Yevtushenko ConExp