Scalable computation of the extensional and intensional stability of formal concepts

ABSTRACT

The effective use of the concept lattice in large datasets has been always limited by the large volume of extracted knowledge. The stability measure has been shown to be of valuable help for knowledge selection. In this paper, we introduce the SC-MG algorithm to efficiently compute both types of stability, i.e. extensional and intensional. The guiding idea is to exploit the relationship between stability and minimal generators in order to compute both measures. The performed experiments show the efficiency of the SC-MG algorithm. In addition, it sharply outperforms the pioneering approaches of the literature.

KEYWORDS:

• Knowledge quality
• concept lattice
• formal concept
• stability measure
• minimal generator
• minimal transversal

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 Roughly speaking, the lower cover of a formal concept stands for the immediate formal concepts subsumed by it.

2 In the remainder of this paper, we use a separator-free abbreviation form for the sets; e.g. bfg stands for the itemset $\{b,f,g\}$.

3 A minimal transversal is a set of elements intersecting all the object sets of a formal context and which is minimal with respect to the set inclusion.

4 The cardinality of the formal context refers to the numbers of “1” in the associated incidence relation.

5 The prefix of an itemset $I=i_1{i}_2\cdots i_n$ is the $\parallel I\parallel -1$ first items of I; prefix(I)=$i_1{i}_2\cdots i_{n-1}$

6 http://archive.ics.uci.edu/ml/.

7 Complexity stands for the number of the formal concepts that may be extracted, given the number of object sets and attributes of the formal context.

8 Please note that the second column of Table 5 reports the number of actually handled formal concepts, since we apply some minsup restrictions for very large datasets. For example, a threshold equal to 0.9 was applied to only retain the handled 177 formal concepts from the TIC-TAC-TOE dataset