Data mining aims at nding interesting patterns from datasets, where \interesting" means re ecting intrinsic dependencies in the domain of interest rather than just in the dataset. Concept stability is a popular relevancy measure in FCA but its behaviour have never been studied on various datasets. In this paper we propose an approach to study this behaviour. Our approach is based on a comparison of stability computation on datasets produced by the same general population. Experimental results of this paper show that high stability of a concept in one dataset suggests that concepts with the same intent in other dataset drawn from the population have also high stability. Moreover, experiments shows some asymptotic behaviour of stability in such kind of experiments when dataset size increases.
In data mining, many usefulness measures of patterns are introduced. For
example, more than 30 statistical methods are enumerated and discussed in [
Within FCA there are several approaches for pattern selection. Two disjoint approaches can be distinguished. The rst one is to introduce background knowledge into the procedure computing concepts [3{5]. These approaches allow one to nd patterns which are likely to be useful for the current task. Although the number of resulting patterns can be signi cantly reduced, they are still numerous. The second approach can be applied in a composition with the rst ones, ranking the resulting patterns w.r.t. a relevance measure.
The authors of [
The rest of the paper is organised as follows. Section 2 introduces de nition of stability and discusses known stability estimates. In Section 3 experiments on relevancy of stability are discussed. 2 2.1
FCA [
G M The Galois connection maps a set of objects to the maximal set of attributes shared by all objects and reciprocally. For example, fg1; g2g0 = fm6g, while fm6g0 = fg1; g2; g3; g4g.
De nition 1. A formal concept is a pair (A; B), where A is a subset of objects, B is a subset of attributes, such that A0 = B and A = B0, where A is called the extent of the concept, and B is called the intent of the concept.
For example, a pair (fg1; g2; g3; g4g ; fm6g) is a formal concept. Formal concepts can be partially ordered w.r.t. the extent inclusion (dually, intent inclusion). For example, (fg3g ; fm3; m6g) (fg1; g2; g3; g4g ; fm6g): This partial order of concepts is shown in Figure 1b. 2.2
Stability is an interestingness measure of a formal concept introduced in [
De nition 2. Given a concept c, concept stability Stab(c) is de ned as Stab(c) := jfs 2 }(Ext(c)) j s0 = Int(c)gj 2jExt(c)j (1) i.e., the relative number of subsets of the concept extent (denoted by Ext(c)), whose description (i.e., the result of ( )0) is equal to the concept intent (denoted by Int(c)) where }(P ) is the power set of P .
Example 1. Figure 1b shows the concept lattice of the context in Figure 1a, for simplicity some intents are not given. The extent of the highlighted concept c is Ext(c) = fg1; g2; g3; g4g, thus, its power set contains 24 elements. The descriptions of 5 subsets of Ext(c) (fg1g ; : : : ; fg4g and ;) are di erent from Int(c) = fm6g, while all other subsets of Ext(c) have a description equal to fm6g. So, Stab(c) = 2424 5 = 0:69.
Stability measures the dependence of a concept intent on objects of the
concept extent. In [
In some papers it is noticed that in large datasets most of the concepts tends
to have stability close to 1 [
LStab(c) = log2(1
Stab(c)) (2)
Stability computation is #P-complete [
Experiment on relevancy of stability
Experiments on behaviour of stability are carried out on public datasets available
from the UCI repository [
When computing stability, one wants to know if the intent of a stable concept is a general characteristic rather than an artefact speci c for a dataset. For that it is necessary to evaluate stability w.r.t. a test dataset di erent from the reference one. Reference and test datasets are two names of disjoint datasets on which the stability behaviour is evaluated. In order to do that the following scheme of experiment is developed: 1. Given a dataset K of size K objects, experiments are performed on dataset subsets whose size in terms of number of objects is N . This size is required to be at least half the size of K. For example, for a dataset of size K = 10 the size of it subset can be N = 4. 2. Two disjoint dataset subsets K1 and K2 of size N (in terms of objects) of dataset K are generated by sampling, e.g., K1 = fg2; g5; g6; g9g and K2 = fg3; g7; g8; g10g. Later, K1 is used as a reference dataset for computing stability, while K2 is a test dataset for evaluating stability computed in K1. 3. The corresponding sets of concepts L1 and L2 with their stability are built for both datasets K1 and K2. 4. The concepts with the same intents in L1 and L2 are declared as corresponding concepts. 5. Based on this list of corresponding concepts, a list of pairs S = fhX; Y i ; : : : g is built, where X is the stability of the concept in L1 and Y is the stability of the corresponding concept in L2. If an intent exists only in one dataset, its stability is set to zero in the other dataset (following the de nition of
stability). Finally, the list LS = fhXlog; Ylogi ; : : : g includes the stability pairs from S in logarithmic scale as stated by Eq. (2). We study here the sets S and LS.
The idea of evaluating stability computed on a reference dataset w.r.t. a test
dataset comes from the supervised classi cation methods. Moreover, this idea
is often used to evaluate statistical measures for pattern selection and can be
found as a part of pattern selection algorithms with a good performance [
Sets of pairs S and LS can be drawn by matching every point hX; Y i to a point in a 2D-plot. The best case is y = x. It means that stability computed for dataset part K1 is exactly the same as stability computed for the dataset part K2. However, this is hardly the case in real-world experiments. For example, Figure 2a shows the corresponding diagram for the dataset Mush4000.1 This gure also highlights the fact that many concepts have stability close to 1. However, when the logarithmic set LS is used, a blurred line y = x can be perceived in Figure 2b. Moreover, selecting the concepts which are stable w.r.t. a high threshold in the reference dataset K1, the corresponding concepts in K2 are stable w.r.t. a lower threshold. Thus, we can conclude that stability is more tractable in the logarithmic scale, and, thus, we only consider this logarithmic scale in the rest of the paper. 3.1
In the previous subsection it is mentioned that concepts stable in the reference dataset are stable in the test dataset with a smaller threshold. But what is \smaller"? Imagine that in the reference dataset K1 we have the threshold 1, i.e., if Stab(c) 1 then c is stable, while in the K2 we have 2. Then, we want to know the threshold 1 such that at least 99% of stable concepts in K1 1 From here, the name of a dataset followed by a number such as `N ameN ' refers to an experiment based on the dataset N ame where K1 and K2 are of the size N . d l o h s e r h T y ilit b a t S e c n e fr e e R 5 1 0 1 5 ● ● ● ●
● 50 100 200 500 5: Mush 5: Plnt 5: Sflr 5: Nurs corresponds to stable concepts in K2. Figure 3 shows the reference threshold 1 (x-axis) w.r.t. the size of the datasets (y-axis) for 2 = 1 and 2 = 5. For example, the line `5: Mush' corresponds to the line of 1, where 2 is xed to 5 w.r.t. to the size of the dataset built from dataset Mushrooms. The value 2 = 1 means that any stable concept is just found in the test dataset, while 2 = 5 requires that they are quite stable in the test dataset. We can see that for large datasets the stability threshold is independent of the dataset, while for small datasets the diversity is higher. We can see that the value of 1 should be set to 5{6 in order to ensure that 99% of stable concepts have corresponding concepts in another dataset. 3.2
Another way of using usefulness measures is pattern ranking. Thus, it is an interesting question if the order of patterns could be preserved by using stability. A way to study an order of an array ar is to compute its sorting rate r, i.e., the relative number of pairs in the array sorted in the ascending order: r = 2 f(i;j)jjia<rjj (ajnadrjar1i) arjg . A sorting rate equal to 1 means that the array is in the ascending order, while 0 means that it is in the descending order; the value 0:5 means that there is no order at all. Figure 4 shows the sorting rate (SR) for di erent datasets, i.e., the sorting rate of concept stabilities in K2, ordered w.r.t. stabilities of the corresponding stable concepts in K1. We can see that SR for all datasets is slowly increasing preserving nearly the same value along the stability threshold in K1. And, thus, concept stability can be used to rank concepts. e t a R g n it r o S
In this paper we study concept stability as an e cient measure for pattern selection. It is shown that stability computed in the logarithmic scale is more convenient since it allows one to better distinguish stable concepts. Given a threshold of stability, patterns whose stability are above a threshold in a given dataset are likely to have stability above a smaller threshold in another dataset coming from the same distribution. However, independently of a dataset, as found experimentally, a concept should have logarithmic stability more than 5 in order to re ect any property of the population. We also show that stability is able to sort concepts in two independent datasets with nearly the same order by selecting concepts with stability above a certain threshold.
There are many future research directions. The found properties of stability suggest that interesting concepts can be found by resampling, i.e., analyzing many small parts of a large dataset, thus providing a key to an e cient processing of datasets with Formal Concept Analysis. The second important direction is to develop a methodology for comparison of stability and other known approaches for pattern selection.
This research was supported by the Basic Research Program at the National Research University Higher School of Economics (Moscow, Russia) and by the BioIntelligence project (France).