Comparision Between Features of CbO based Algorithms for Generating Formal Concepts

Comparision Between Features of CbO based Algorithms for Generating Formal Concepts

Nuwan Kodagoda (Sri Lanka Institute of Information Technology, Malabe, Sri Lanka) and Koliya Pulasinghe (Sri Lanka Institute of Information Technology, Malabe, Sri Lanka)
DOI: 10.4018/IJCSSA.2016010101

Abstract

Formal Concept Analysis provides the mathematical notations for representing concepts and concept hierarchies making use of order and lattice theory. This has now been used in numerous applications which include software engineering, linguistics, sociology, information sciences, information technology, genetics, biology and in engineering. The algorithms derived from Kustenskov's CbO were found to provide the most efficient means of computing formal concepts in several research papers. In this paper key enhancements to the original CbO algorithms are discussed in detail. The effects of these key features are presented in both isolation and combination. Eight different variations of the CbO algorithms highlighting the key features were compared in a level playing field by presenting them using the same notation and implementing them from the notation in the same way. The three main enhancements considered are the partial closure with incremental closure of intents, inherited canonicity test failures and using a combined depth first and breadth first search. The algorithms were implemented in an un-optimized way to focus on the comparison on the algorithms themselves and not on any efficiencies provided by optimizing code. The main contribution of this paper is the complete comparison of the three main enhancements used in recent variations of the CbO based algorithms. The main findings were that there is a significant performance improvement partial closure with incremental closure of intents is used in isolation. However, there is no significant performance improvement when the depth and breadth first search or the inherited canonicity test failure feature is used in isolation. The inherited canonicity test failure needs to be combined with the combined depth and breadth first feature to obtain a performance increase. Combining all the three enhancements brought the best performance.
Article Preview

Background

Knowledge is represented in Formal Concept Analysis as a formal context. This describes a binary relationship between a set of objects and a set of attributes of a domain.

  • A precise definition of a formal context is given below.

  • A formal context is defined as

Where is a set of objects, a set of attributes and a binary incidence relationship between and with

Since formal contexts are a binary relationship they can be represented as cross tables. Here each object and attribute is represented as a row and a column respectively (Wille, 1982; see also Ganter, Stumme, & Wille, 2002)

Let’s take an example to illustrate formal concept definitions making use of the Solar system. Figure 1 shows the eight major planets in our Solar System with details of seven different properties. The table has the eight planet as rows and the eight properties as columns. A cross is used to mark the presence of a property against a planet. For example, the planets Jupiter, Saturn, Uranus and Neptune are considered to be gas giant planets. This is denoted in the table with crosses marked against each of the above planets for the property gas giant planet. The rows are known as extents and the columns are known as intents. A formal concept is defined as a pair of maximum of a set of extents and a set of intents. For the earlier example, we can also see that the four planets also have the property Has Some Moon checked. So the formal concept consisting of gas giants is defined as ({Jupiter, Saturn, Uranus, Neptune}, {Gas Giant, Has Some Moon}). Similarly, we can define a formal concept of planets that are gas giants and where the sun sets in the West. From Figure 1, we can find the following concept ({Jupiter, Saturn, Neptune}, {Gas Giant, Sun sets in the west, Has some Moon}). Here too the property Has some moon is a common property and is included as part of the formal concept. The planets Jupiter, Saturn and Neptune are the gas giant planets where the sun sets in the west. The planets mentioned above are the extent of this formal concept and the three attributes form the intent. A mathematical definition of Formal Concepts is given below.

Figure 1.

A context about planets in our solar system (Krötzsch & Bernhard, 2009)

For a set of objects the set is defined as

Similarly, for a set of attributes the set is defined as

is a formal concept if and .

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 7: 2 Issues (2019): Forthcoming, Available for Pre-Order
Volume 6: 2 Issues (2018): 1 Released, 1 Forthcoming
Volume 5: 2 Issues (2017)
Volume 4: 2 Issues (2016)
Volume 3: 2 Issues (2015)
Volume 2: 2 Issues (2014)
Volume 1: 2 Issues (2013)
View Complete Journal Contents Listing