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 [1].
The notion of "Concept" as a couple of intent and extent (serving to represent nuggets of knowledge) was introduced and formalized many decades ago [2,3,4]. Recently, its use in Data-Mining and Knowledge-Discovery is in growth [5]. Our ConceptMiner project (a development environment in MS-Visual C++) aims to design new heuristic algorithms for Data-Mining based on Formal Concept Analysis.
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 [8].
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 [1]. The conditional rule has the following syntax: "IF conditions THEN results". The combination of conditions leads to a descriptive rule like: "IF A AND NOT B THEN C AND D". It can lead, also, to a predictive rule including the time dimension like: "IF condition at time_1 THEN result at time_2". This looks like: "IF he_bays(TV, today) THEN he_bayes(recorder, in_one_year)".
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 [1].
During the few last years, a wide variety of algorithms have been proposed. The most popular algorithm is certainly the iterative one: Apriori [9]. It consists in three steps. First aboard, it considers all the attributes/properties describing the set of data as the initial itemsets. Then, it combines the couples of item-sets in order to obtain larger item-sets. Finally, it searchs for the rules that can be derived from each itemset.
MaxEclat and MaxClique [10] use graph theory to decompose the lattice into sublattices in order to mine maximal frequent item-sets. MaxMiner [11] is an exploring algorithm for the maximal frequent item-sets with a look-ahead pruning strategy. PincerSearch [12] follows both a bottom-up and a top-down search in the lattice at the same time while looking for the maximal frequent patterns. GenMax [13] uses a backtracking search to enumerate all maximal frequent item-sets and eliminates progressively non maximal ones. Mafia [14] works with a depth first search and uses pruning strategies to mine maximal frequent item-sets. DepthProject [15] follows dynamic re-ordering to reduce the search space. Salleb & al. [16] uses a boolean algebra approach that loads the data base in main memory as a binary decision diagram, and searchs for maximal frequent item-sets by making iteratively the product of vectors representing the items. The reader can find further description on these algorithms in [13,16].
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 [17]. So, it becomes very hard to read and interpret them. The induced rules can be classified in three categories:
-Useful rules: that a human expert can understand and use.
-Trivial rules: that represents evidence. They are valid but never used.
-Weak rules: those are not acceptable by the expert and not understandable. To remedy to this problem, many methods were proposed [17]. The basic one consists of calculating a minimal set of rules that allows us to re-produce the others. This can be done while calculating the rules [18], or after that using the concept lattice [19,20]. Another method searches only the rules where the condition or the result part matches a particular group of terms [21]. Agrawal et al. [9] maintains a partial order relation between the rules using two measures: the support and the confidence. Consider the rule: X → Y , where X (conditions) and Y (results) are sets of atomic propositions:
-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 [22] introduce the conviction measure and [17] propose five different measures like the benefit (interest) and the satisfaction.
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 [3,4], since we suggest that an item-set is completely represented by a formal concept as a couple of intent (the classic item-set) and extent (its support).
Let O be a set of objects (or examples), P a set of properties (or attributes) and R a binary relation defined between O and P [3,4]. The set of objects which have all properties in B :
The couple of operators (4,3) is a Galois Connection.
We call A the extent and B the intent of the concept (A, B).
The set of all concepts of the context (O, P, R) is denoted by (O, P, R). An ordering relation (<<) is easily defined on this set of concepts by :
( (O, P, R), <<) is a complete lattice. It is called the concept lattice (or GALOIS lattice) of (O, P, R), for which infimum and supremum can be described as follow: 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.
The most computationally expensive step to discover association rules is the calculation of the frequent item-sets [15]. Generally, this step consists of applying, iteratively, some heuristics to calculate candidate item-sets. At the iteration i, we combine the item-sets of the iteration i-1. After that, the support threshold (minsupp) is used to discard non-frequent candidates. The item-sets of iteration i-1, are also discarded. We keep the remaining item-sets of the latest iteration n (where n is the number of properties in the formal context).
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).
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.
Let FC i = (A i , B i ) be a formal concept. We define:
-Length of a concept FC i : the number of properties in the intent B i of the concept.
-Width of a concept FC i : the number of examples in the extent A i of the concept.
-Gain of a concept: is a function of the width and the length, given by:
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).
A formal concept FC i = (A i , B i ) containing a couple (o, p) is said to be optimal if it maximizes the gain function.
A coverage CV={ FC 1 , FC 2 , ..., FC k } of a context (O, P, R) is optimal if it is composed by optimal concepts.
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}).
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 PCF i = (A i , B i , R i ) be a pseudo-concept, where R i is the restriction of the binary relation R, to the subsets A i and B i . We define the: -Length of a pseudo-concept PCF i : the number of properties in B i .
-Width of a pseudo-concept PCF i : the number of examples in A i .
-Size of a pseudo-concept PCF i : the number of couples (of values equal to 1) in the pseudo-concept. When PCF i is a formal concept, we have:
-Gain of a pseudo-concept: is a function of the width, the length and the size given by ( 9) :
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 R 1 =P 1 by CV 1 . In the k th step, let R k-1 =P 1 ∪ ... ∪ P k-1 and let CV k-1 be its optimal coverage. The task is to construct the optimal coverage CV k of R k =R k-1 ∪ P k using only the initial coverage CV k-1 and the package P k . In the p th step, we obtain a set of concepts covering the relation R. 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 [9,23]. The Apriori method was programmed in C++ and integrated in our software package. We 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). Fig. 4: Comparing the CPU time
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.
Figure 5 presents the percentage of rules that are obtained by IAR in comparison with APRIORI. We remark that the percentage is always less than the half (0.5). We remark also that Apriori gives, always, a lot of rules compared to IAR.
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 [9]. 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 [9]. We measured their CPU time, the number of association rules, and the percentage of similar rules. We remarked that Apriori gives a great number of rules and takes a great time. The proposed method IAR is faster than Apriori. It gives a low number of rules that have the advantage of being the common rules.
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 [17,22], in order to identify the measure that gives expert-acceptable rules.