The Discovery of association rules is a non-supervised task of data mining. Its mostly hard step is to look for the frequent itemsets embedded into large amounts of data. Based on the theory of Formal Concept Analysis, we suggest that the notion of Formal Concept generalizes the notion of itemset, since it takes into account the itemset (as the intent) and the support (as the cardinality of the extent). Accordingly, we propose a new approach to mine interesting item-sets as the optimal concepts covering a binary table (concept coverage). This approach uses a new quality-criteria of a rule: the gain that generalizes the support criteria.
The volume of stored data increases rapidly. In the past, it doubles each three
centuries. Nowadays, it doubles each 72 days. The analysis of huge volumes of data
by computers leads to the emerging field of Data-Mining and Knowledge-Discovery.
This includes techniques to create knowledge from data sets serving for classification,
clustering, prediction, estimation and optimization tasks [
The notion of “Concept” as a couple of intent and extent (serving to represent
nuggets of knowledge) was introduced and formalized many decades ago [
In this paper, we study the clustering problem that we resolve by the induction of
association rules. In fact, the experts (biologists) want to know which sub-sequences
of proteins that appear together in Tall Like Receptor (TLR) sequences or even in
Similar TLR sequences [
In section 2, we resume the basic concepts of association rules and we outline the well-known techniques. In section 3, we introduce the basic definitions of Formal Concept Analysis that we use later. In section 4, we give two heuristic algorithms to calculate the optimal Item-sets from rows of data. Illustrative examples are given throughout the paper. Finally, we present our concluding remarks and the future perspectives of this work.
Discovering association rules is a non-supervised data-mining task that aims to induce
symbolic conditional rules from a data file [
The association rules are used in a wide range of applications, due to their
comprehensive format. Mainly, it is used to analyze the supermarket tickets. This
helps in optimal stock management, in merchandizing and marketing [
During the few last years, a wide variety of algorithms have been proposed. The
most popular algorithm is certainly the iterative one: Apriori [
MaxEclat and MaxClique [
Generally, the number of association rules (induced by these algorithms) grows in
an exponential manner with the number of data-rows (or the attributes). This can
reach hundreds’ of thousands using only some thousands of data rows [
To remedy to this problem, many methods were proposed [
- Support (X → Y): the percentage of examples satisfying both X and Y. - Confidence (X → Y): the number of examples satisfying both X and Y, devided by the number of examples satisfying only the condition X.
The authors introduce two thresholds defined by the end-user: - MinSup: the minimal value of the rule support that can be accepted. - MinConf: the minimal value of the rule confidence that can be accepted.
The method discards all the item-sets with a support less than MinSup, and all the rules with a confidence less than MinConf.
To filter more efficiently the association rules, some authors [
In this paper, we introduce a new mesure: the gain. It combines the support of the
rule with the length of the itemset. This is done thanks to the theory of Formal
Concept Analysis [
Definition 1 [
Definition 2 [
A4={p∈P | oRp for all o∈A} (1) The set of objects which have all properties in B :
B3={o∈O | oRp for all p∈B}
The couple of operators (4,3) is a Galois Connection.
(2)
Definition 3 [
A⊆O, B⊆P, A4=B and B3=A. (3) We call A the extent and B the intent of the concept (A, B).
Definition 4 [
∅ o1,o2, o3, o4, o5 FC2
B o1, o2, o3, o4 FC4
A, B o1, o2
B, C o3, o4 A, B, C, D ∅
C o3, o4, o5 B, C, D o4
FC3 C, D o4, o5 FC7
FC6 P A 1 1 0 0 0 O o1 o2 o3 o4 o5 FC5
FC8
1.b Concept Lattice of the context (O, P, R)
Basic Theorem for Concept Lattices [
i∈I(Ai, Bi)=((∪i∈IAi)43, (∩i∈IBi))
Inf
i∈I(Ai, Bi)=( ∩i∈IAi, (∪i∈IBi)34)
(5)
(6)
Example : Figure 1 (graphic 1.a) is used to illustrate the notion of formal context (O,
P, R). This context includes five objects {o1, o2, o3, o4, o5} described by four
properties {A, B, C, D}. The concept lattice of this context is drawn in Figure 1
(graphic 1.b). It contains eight formal concepts.
Definition 5 [
Definition 6 [
Example: To illustrate the notion of pseudo-concept and coverage, we consider the same formal context (O, P, R) from figure 1. Figure 2 (graphic 2.a) represents the pseudo-concept containing the couple (o3, B). It is the union of the concepts FC2 and FC5 (see figure 1).
A coverage of the context (O, P, R) can be formed by the three concepts: {FC4,
FC5 , FC6}. FC4 is the concept containing the items ({o1, o2}, {A, B}). FC5 is the
concept containing the items ({o3, o4}, {B, C}). FC6 is the concept containing the
items ({o4, o5}, {C, D}). The lattice constitutes also a concept coverage.
4 Discovery of Optimal Item-sets
The most computationally expensive step to discover association rules is the
calculation of the frequent item-sets [
In this step, we think that many approaches use, in an implicit manner, two basic characteristics of the association rules: - General rules: we should ignore the item-sets with high support and low cardinality. General rules are week, since they are valid for numerous examples (or observations).
Specific rules: we should ignore the item-sets with high cardinality and low support. Specific rules are week, since they are valid only for few examples (or observations).
The two characteristics are defined based on the cardinality of two special sets: - Support: that is the cardinality of the set of examples verifying the rule. In
Formal Concept Analysis, this represents the extent of a formal concept. - Cardinality of the Item-set: that is the number of properties in the item-set.
In Formal Concept Analysis, this represents the intent of a formal concept.
Consequently, we think that an association rule should not be represented only by the item-set (that is the intent). An association rule is completely and explicitly represented by a formal concept (as a couple of intent and extent).
Also, we think that the selection of “good” item-sets should not be based only on the support (that is the cardinality of the extent). A powerful selection should be based on the cardinalities of both the extent and the intent of its formal concept.
To formalize the new criterions, we give the following definitions.
Definition 7: Let FCi= (Ai, Bi) be a formal concept. We define: - Length of a concept FCi: the number of properties in the intent Bi of the concept. - Width of a concept FCi: the number of examples in the extent Ai of the concept. - Gain of a concept: is a function of the width and the length, given by:
Gain(FCi)=width(FCi)*length(FCi)–[width(FCi)+length(FCi)] (7) In a manner that the gain function cannot be maximised when one of the two parameters is low and the other is high. It becomes maximal only when the two parameters are high (a lot of examples and a lot of properties). Hence, we are sure that the rule is not a general one, neither a specific one. Note also that the Width indicates the support of the itemset (or the corresponding association rule).
Definition 8 [
Definition 9 [
Example: Figure 2 (graphic 2.b) represents the optimal concept FC5 containing the couple (o3, B) and having the gain value 0. Figure 2 (graphic 2.c) represents the non optimal concept FC2 containing the couple (o3, B) and having the gain value -1.
The optimal coverage of the context (O, P, R) is formed by three optimal concepts: {FC4., FC5 , FC6}. FC4 is the concept containing the items ({o1, o2}, {A, B}). FC5 is the concept containing the items ({o3, o4}, {B, C}). FC6 is the concept containing the items ({o4, o5}, {C, D}). 4.1 Heuristic Searching for Optimal Concept The pseudo-concept containing the couple (o, p), introduced in definition 5, is the union of all the concepts containing (o, p). The importance of the notion of pseudoconcept, indicated by PCF, is that it can be calculated in a simple manner as the restriction of the relation R by the set of objects/examples described by p, so {p}4, and the set of properties describing the object o, so {o}3. Where (4,3) is the Galois connection of the context (O, P, R).
Once we obtain the pseudo-concept PCF, two cases are considered: - Case 1: PCF forms a formal concept. This means that no zero is found in the relation/matrix representing PCF. Then, PCF is the optimal concept that we are looking for. The algorithm stops. - Case 2: PCF is not a formal concept. This means, simply, that we can find some zero entries in the relation/matrix representing PCF. In this case, we will look for more restraint pseudo-concepts within the pseudo-concept PCF. So, we consider the pseudo-concepts containing the couples like (X, p) or (o, Y). These concepts contain, certainly, the couple (o, p). The heuristic that we use here is that: the optimal concept is included in the optimal pseudoconcept. So, we should calculate the Gain value of the different pseudoconcepts containing the couples like (X, p) or (o, Y). Then we choose the pseudo-concept having the greatest value of the Gain function to be the new PCF.
This heuristic procedure (of case 2) is repeated until we meat the case 1: until PCF becomes a formal concept. To calculate the gain of a pseudo-concept, we introduce the general form of the previous function: Definition 10: Let PCFi= (Ai, Bi, Ri) be a pseudo-concept, where Ri is the restriction of the binary relation R, to the subsets Ai and Bi. We define the: - Length of a pseudo-concept PCFi: the number of properties in Bi. - Width of a pseudo-concept PCFi: the number of examples in Ai. - Size of a pseudo-concept PCFi: the number of couples (of values equal to 1) in the pseudo-concept. When PCFi is a formal concept, we have:
Size(PCF)=Length(PCF)×Width(PCF) (8)
Gain of a pseudo-concept: is a function of the width, the length and the size given by (9) :
Size(PCF) ⎤×[Size(PCF)−(Length(PCF)+Width(PCF))] Gain(PCF )=⎡⎢⎣ Length(PCF)×Width(PCF) ⎦⎥
The problem of covering a binary relation by a set of optimal concepts is known as the problem of covering a binary matrix by a number of its complete sub-matrix. A complete sub matrix is a matrix where all its entries are equal to '1'. This was found as an NP-hard problem. Here, we use a polynomial heuristic solution.
Let R be the binary relation to cover. The heuristic solution consists of dividing R into p packages (subsets): P1, ..., Pp. Each package represents one or more couples. The idea is to construct step by step the optimal coverage of R. In the first step, we cover the relation R1=P1 by CV1. In the kth step, let Rk-1=P1 ∪ ... ∪ Pk-1 and let CVk-1 be its optimal coverage. The task is to construct the optimal coverage CVk of Rk=Rk-1 ∪ Pk using only the initial coverage CVk-1 and the package Pk. In the pth step, we obtain a set of concepts covering the relation R.
Algorithm for building the Coverage Begin Let R be partitioned to p packages P1, ..., Pp. Let CV0:=∅.
FOR k=1 to p DO
Sort the couples of Pk by the pertinence of their pseudo-concepts While (Pk≠∅) Do -Select a couple (a, b) in Pk by the sorted order of the gain function (9) -Search PC : the pseudo-concept containing (a, b) within Rk=CVk-1∪Pk -Search FC: the optimal concept containing (a, b) within PC CVk:=(CV k-1-{r∈CV k-1/ r⊆FC }) ∪{FC}: Delete all the redundant concepts from CVk
Pk:=Pk-{(X,Y)∈Pk/(X,Y)∈FC}
End While End FOR End.
Example: Let R be the relation of figure 1. R is partitioned into five packages: P1={o1}x{A, B}, P2={o2}x{A, B}, P3={o3}x{B, C}, P4={o4}x{B, C, D} and P5={o5}x{C, D}. Initially, R is an empty relation and in each step we add a package. Figure 3 presents the incrementation step when adding P5.
In this step R4 encloses the four rows P1, ..., P4. The initial optimal coverage CV4 encloses the formal concepts FC4=({o1, o2}, {A, B}) and FC5=({o3, o4}, {B, C}) and FC7=({o4}, {B, C, D}) (graphic 3.a). The package P5 encloses only two couples. The pseudo concept containing the couple (o5, C) represents the union of two formal concepts FC3 and FC6. So, the optimal concept containing (o5, C) and (o5, D) is the concept FC6. The concept FC7 is redundant. Thus, the final coverage of R contains the concepts FC4, FC5 and FC6.
In conclusion, from the data set of figure 1, we discover three Item-sets : {A, B}, {B, C} and {C, D}. These Item-sets will be processed later by the Apriori algorithm, to calculate the corresponding association rules.
The experiments are done with a PC PENTIUM II, 233 MHZ, 144 Mo of RAM and
running under MS-Windows 98. The analyzed data sets are organized in two groups.
The first group is made by five data sets representing biological sequences coding
macromolecules (table 1). The first two data sets are proprietary sets for the TLR
macromolecules. The three others are taken from the machine-learning repository at
UCI University. Classic tables of data make the second group of data sets (table 2).
The first two data sets are also taken from the machine-learning repository at UCI
University. The other sets are taken from a proprietary database.
To evaluate the performance of the proposed method (IAR: Incremental induction of
Association Rules), we compare it to the existing approach Aprior [
DB1 DB2 DB3 DB4 DB5
DB6 DB7 DB8 DB9 DB10
763 619 106 1150 500 Rows 958 1191 1000 5000 1000 use the two methods to analyze the ten data sets. We choose two sets of parameters. The first one with MinSup=0.6 and MinConf=0.5 is used for the biological data sets (table 1). The second one with MinSup=0.35 and MinConf=0.75 is used for the standard data sets (table 2). ) c e s ( e m it U P
C IAR Apriori ) % ( s e s a b e g d e l w o n K f o y iilitr a m
S IAR/Apriori
DB1 DB2 DB3 DB4 0,21 0,13 0,49 0,03 MinSup=0.6 and MinConf=0.5
DB5 0,16
IAR/Apriori
DB6 0,42
DB7 0,12
DB8 0,3
DB9 0,03
DB10 0,24 MinSup=0.35 and MinConf=0.75 Fig. 5: Similarity between the knowledge bases of the two methods
DB1 DB2 DB3 3930 304 9 12451 916 12
MinSup=0.6 and MinConf=0.5
Figure 4 presents the CPU time measured in seconds for the three methods. We remark that the three methods keep the same behavior overall the data sets. The Apriori method takes the greater time, since it is based on an exhaustive approach to test all the possible combinations. The proposed method IAR takes always a CPU time better than Apriori. ) c e s ( e m it U P
C IAR Apriori ) % ( s e s a b e g d e l w o n K f o y iliitr a m S
A FMoromnadlhCeronMceapdtdAounrailysis Approach to Discover Association Rules from Data
In this paper, we presented a new Formal Concept Analysis approach to search for
optimal item-sets. We gave two heuristic algorithms to build the coverage of formal
concepts and to create optimal item-sets from data records. The association rules can
be induced from the Item-sets in the same manner as Apriori [
We assume that a Formal Concept generalizes the notion of Item-set, since it is more powerful and more explicit. In fact, we note that an item-set represents only the intent of a Formal Concept. Also, the support of an item-set is the cardinality of the concept extent. Hence, the Formal Concept encloses more information than the itemset itself.
The first experimentation of the proposed method is done on a variety of data sets
having different data formats (structured and unstructured). We compared the
proposed method with a known one: Apriori [
Future work will focus on the quality of the created association rules. In fact, we
plan to study the significance of the discovered rules for human experts. For this
reason we propose to present the rules concerning the TLR macromolecules to our
biologists in order to get their points of view. Accordingly, we plan to study quality
measures other than the support and the confidence [