Applications of FCA in AKT fact-file

What's the problem?

Information overload is a major knowledge management problem. When analysing raw data, we need to utilise expensive resources. Most of work to date is based on statistical methods which do not accommodate mechanisms for indentifying and reasoning over first class objects for domain analysis, like concepts.

Towards a solution

In AKT, we aim to use a technology which emerged in the early 80s, and is centered upon the mathematical notion of concept, Formal Concept Analysis (FCA).

FCA is based on mathematical order theory and lattice theory (dating back to Garrett Birkhoff's 1940 work). Nowadays, FCA is revisited by Ganter and Wille who applied it to conceptual structures.

The basic notion of FCA is that of a concept. In a formal context, the set of entities forms the extension of a concept, and the set of attributes the intention of a concept. FCA characterizes a (formal) context as a fixed set of entities and attributes, presented in a cross-reference table.
The information found in such a cross-reference table is often depicted as a line diagram, or concept lattice. Here's the formal definitions of FCA.

Some interesting properties of line diagrams (concept lattices) is the hierarchical order they impose to their nodes.

Concept lattices also have a close relation with attribute logic. It has been shown that concept lattices can be inferred from the implication between the attributes, for example, "every object with attributes a,b,c,…also has the attributes x,y,z":

FCA has been used in a variety of application areas:

• In psychology where repertory grids were analyzed using FCA;
• In libraries where FCA and line diagrams were used to help readers retrieve related literature;
• In software re-engineering where line diagrams were used to locate clusters of subroutines in obsolete FORTAN code;
• In KBSs where FCA is used to re-engineer, represent and investigate KBs created by ripple down rules in an iterative manner;
• In other KA work as a data analysis tool

Take a Guided Tour

Here's a short introduction to FCA:

A 1'53" movie (no sound provided) in .avi format (1MB) (TSCC codec required) and .mov format (10MB)

Try a Demonstration

For publicly available FCA tools visit Uta Priss's FCA portal

Technical requirements

There open-source tools for most platforms and programming environments. In AKT, we are using Concept Explorer, an open-source Java program written by Sergey Yevtushenko and we are at the stage of co-developing an API.

Example Applications

In AKT, we investigate a variety of scenarios where FCA can be applied:

* Analyse research areas attributed to published papers:

We use a small number of articles from the ACM Intelligence journal (accessible from the ACM Digital Library Portal), and the ACM classification scheme (which we have already RDFy in AKT ontology).

The formal context consists of 20 objects (articles) and 58 attributes (research areas). We then analyze the context, we draw the line diagram (concept lattice) to identify (super-)/(sub-) concepts and apply FCA algorithms to reduce the context in order to identify clusters of similar concepts. We calculate the stem base (implication set) to find dependencies between concepts.

Once the analysis is done, it can be used in many ways, recall that a concept in this domain is a {article(s),research area(s)} pair. Articles have authors; authors are working in organisations; organisations are researching certain research themes; research themes are decomposed into research areas; authors often collaborate with people who share the same research area(s);, these could be found in other {article(s),research area(s)} pairs (concepts), and so on.

* Analyse alternative research areas attributed to published papers:

We used the same articles but this time with a different classification scheme, Elsevier's classification of fields relevant to Data and Knowledge Engineering.

* Analyse how AKT tools are designed, developed and deployed:

We used the components found in the AKT conceptual architecture (CASD) to analyse how AKT tools are designed, developed and deployed among AKT partners. This analysis could reveal collaboration opportunities and assist coordination among partners.

* Analyse participation of programme committee membership:

We analyzed the EKAW community (European Knowledge Acquisition Workshops community) programme committees membership over the past 8 years to reason about the evolution of PC members as a supporting argument for reflecting the evolution of interests in that community.

Further Reading

Key document:

"Formal Concept Analysis: Mathematical Foundations",
Bernhard Ganter, Rudolf Wille, Springer, ISBN: 3-540-62771-5, 1999

Other relevant documents:

A collection of FCA related resources can be found at the FCA portal maintained by Uta Priss.

Semantic representation

View in the AKT Triplestore Browser or as RDF.

Also available in DOAP RDF (Description Of A Project)