1
Introduction
Discovering useful knowledge from large-scale databases has attracted a considerable attention during the last decade. Frequent pattern mining is one of the fundamental problems for knowledge discovery.  Since the pioneering paper by Agrawal et al.[1], various algorithms have been proposed to solve the frequent pattern mining problem (cf., e.g., [15, 6]). Recently, we have attacked the problem of effi- ciently generating the frequent patterns in a trans- action database by using a data structure called Zero-suppressed Binary Decision Diagrams (abbr. ZBDDs), see [7, 8].  ZBDDs are a special case of Binary Decision Diagrams (abbr. BDDs)[2].  Us- ing ZBDDs one can implicitly enumerate sets of combinations. Moreover, one can then perform ef- ficiently various operations including the discovery and analysis of frequent patterns. After generating frequent item set data, we sometimes faced with another problem that the results of itemsets are too large and compli- cated to retrieve useful information. It is impor- tant for practical data mining to extract the key For example, structures from the itemset data. closed/maximal itemset mining[16, 14, 13] extracts a partial set of itemsets with a special property, and it reveals a kind of structural information in the database. In this context, recently our re- search group have developed several new method such as disjoint itemset decomposition[9], and sym- metric itemset mining[10]. Both the two methods are based on ZBDD representation for transaction databases, and efficiently find hidden structural in- formation using set operations supported by ZBDD manipulation. In this paper, we propose a new aspect of item- set mining by considering a property of cofactor im- plication. The cofactor implication is an extension or generalization of symmetric itemset[10]. Here we discuss the meaning of the cofactor implication for the data mining applications, and show an efficient algorithm of extracting all non-trivial item pairs with the cofactor implication by using ZBDD op- erations.  Finally, we show an experimental result to see how many itemsets can be extracted by using the cofactor implication, compared with symmet- ric itemset mining. Our result indicates that the use of the cofactor implication has a possibility of discovering a new aspect of structural information hidden in the databases.
Database   Representation   Us-
2
ing  ZBDDs
In this section, we first describe the database rep- resentation to be discussed. Here we consider databases of the following type.  Let M̸= ∅ be any set. We refer to the elements of M as to items. In our examples below, we use M = {a,b,c}. Then the set of all possible combinations is the power set φ ( M ) of M . Any subset C ⊆ φ ( M ) is said to be a set of combinations. The elements of a set of combinations are sets of items, e.g., { a,c}.  To simplify notation, we write ac instead of {a,c} and we refer to the elements of a set of combinations as to tuples. A transaction database is just a list of tuples. A  Binary Decision Diagram (BDD) is a graph representation for a Boolean function.  An Example is shown in Fig. 1 for F (a,b,c) = abc V abc. Given a variable ordering (in our example a,b,c), one can use Bryant's algorithm[2] to con- struct the BDD for any given Boolean function. For many Boolean functions appearing in practice this algorithm is quite efficient and the resulting BDDs are much more efficient representations than binary decision trees. BDDs were originally invented to represent Boolean functions. But we can also map a set of combinations into Boolean space of n variables, where n is the cardinality of the item set M (see Fig. 2). So, one could also use BDDs to represent sets of combinations. However, one can even ob- tain a more efficient representation by using Zero- suppressed BDDs (ZBDDs)[7]. If there are many similar combinations then the subgraphs are shared resulting in a smaller repre- sentation. In addition, ZBDDs have a special type of node deletion rule.  As shown in Fig. 3, All nodes whose 1-edge directly points to the 0-terminal node are deleted.  Because of this, the nodes of items that do not appear in any sets of combinations are au- tomatically deleted as shown in Fig.1. This ZBDD reduction rule is extremely effective if we handle a set of sparse combinations. If the average appear- ance ratio of each item is 1%, ZBDDs are possi- bly more compact than ordinary BDDs, up to 100 times. ZBDD representation has another good prop- erty that each path from the root node to the 1- terminal node corresponds to each combination in the set. Namely, the number of such paths in the ZBDD equals to the number of combinations in the set. This beautiful property indicates that, even if there are no equivalent nodes to be shared, the ZBDD structure explicitly stores all items of each combination, as well as using an explicit lin- ear linked list data structure. In other words, (the order of) ZBDD size never exceeds the explicit rep- resentation. If more nodes are shared, the ZBDD is more compact than linear list. Using a ZBDD-based data structure, we can ma- nipulate compressed representation of large-scale transaction databases on the main memory.  Re- cently, our research group has developed an ef- ficient algorithm "ZBDD-growth"[11] to generate ZBDDs compactly representing all frequent item- sets for given databases. Our method is not only enumerating/listing the frequent patterns but also efficiently analyzing the huge size of mining re- sults by using ZBDD operations. For example, ex¬ tracting all patterns including a certain items, or computing the intersection/union/difference set for given two sets of patterns. The computation time of those operations does not directly depend on the number of patterns but almost linear to the (com- pressed) ZBDD size. It is an important advantage of using ZBDDs.
Cofactor Implication Based on
3
ZBDDs
In this section, we present the definition of the co- factor implication and discuss the properties. As a Boolean function: F = abc V abc As a set of combinations: S = {ac, b}
3.1
Symmetry of Items in Sets of Com-
binations
In our previous work[10], we defined symmetry of items in transaction databases, and we pre- sented an efficient algorithm to find all symmet- Here we explain ric items in a given database. For exam- the meaning of symmetry of items. ple, we consider the following set of itemsets: S = { abc, acd, ad, bcd, bd, c, cd}.  In this case, the item a and b are symmetric but the other pairs of vari- ables are not symmetric. Figure 4 show a method of symmetry checking. First we classify the combi- nations into four categories: (1) Sab, both a and b included, (2) S Σ , only α is included, (3) S撒, only b is included, and (4) S ∞ , neither included. Namely, it can be written as: S = a b Sab U a Saf U b Saf Then, we can determine the symmetry of a and b by comparing S or and S t b . If the two subsets are equivalent, a and b are exchangeable without any effect. For the above example, we can see that a and b are symmetric because S = S æ = {cd,d}. By using quick equivalence checking based on ZBDD operations, we can efficiently detect symmetric itemsets in a large-scale transaction database.  Previous experimental results[12] show that our method is applicable to a real-life biologi- cal database, which consists of 6,560 items of amino acid information related to influenza viruses. We succeeded in extracting all possible 64 groups of symmetric items from the database in a feasible computation time. Even if we do not know the ac- tual meaning of each item, we can expect that the group of items would have somehow strong corre- lation if the symmetric property holds.
3.2
Symmetric Property and Cofactor
Operation
Symmetric property is useful for extracting a kind of structural information from databases, however, in some cases, it is too strict to check Sor and Sæb are completely identical. For example, if the database includes a bit of noise, the symmetric property is broken and we lose the chance to dis- cover an interesting correlation. Therefore, we now consider to relax or to generalize the symmetric condition. Let us consider the relationship between ZBDD data structure and symmetric property. A ZBDD decision node corresponds to the following expres- sion of set operations. S = x S x U S x , where x is the item symbol of the decision node, S x and S = are the subgraphs pointed by the 1-edge and the 0-edge, respectively. This operation, to obtain S x and S z from S , is called cofactor operation. It can be performed in a constant time (just looking pointers) if the item x is in the highest position in ZBDD variable ordering. Otherwise, the computa- tion time is linear to the number of ZBDD nodes with the items higher than x . In the transaction databases, S x represents the set of item patterns co-occurring with x in some tuples, and S = represents the set of patterns never co-occurring with x in the database. In this paper, we call S x and S x the positive cofactor and negative cofactor , respectively, if we distinguish the two kind of cofactors. Symmetric items can be detected by generating the four sub-factors Sxy, Sxy, Sxy, which are the two stages of cofactor operations with respect to the items x and y. The condition Sxy = Sxy means that the sub-patterns co-occurring only with x and the sub-patterns co-occurring only with y are the completely identical. It is a naive idea to relax the symmetric con- dition that S x 7 and S x y are not completely iden- tical but S x T implies S x Y . We call this condition cofactor implication. If and only if the cofactor im- plication holds bidirectionally, symmetric property holds. Therefore, the cofactor implication is a par- tial condition for symmetry of items. For example, in the following sets of combina- tions: S = { abc, acd, ad, bc, bcd, c, cd}, the patterns co-occurring with a but not with b are {cd,d}, and the patterns co-occurring with b but not with a are {c,cd,d}. Thus, the cofactor impli- cation holds from a to b.

3.3
Properties of Cofactor Implication
Let us discuss the meaning of the cofactor implica- tion in transaction databases. First, we can see that the cofactor implication is transitive as well as the symmetric condition. For example, if the cofactor implication holds from x to y and from y to z, then it also holds from x to z.  Notice that the cofactor implication has the direction. This is different from the symmetric property. Next, if the cofactor implication holds from x to y in a transaction database, all the patterns co- occurring with item x also co-occurs with item y . When the database represents a kind of knowledge, the cofactor implication represents a correlation be- tween the two concepts used in the knowledge.  An- alyzing co-occurrence words is a basic method in the area of natural language processing[3].  Con- sidering the cofactor implication would be an in- teresting idea to apply the recent state-of-the-art data mining techniques to the knowledge analysis and natural language processing. Table 1 shows the list of various relationships of two items and their conditions based on the four cofactors, Sxy, Sxy, Sxy, Sxy. In this table, the con- dition S xy ≡ ∅ (or S xy ≡ ∅) represents the direct implication property on the occurrences of x and y. This condition is commonly used to check the implication of items in transaction databases. It is contrastive that our cofactor implication is not di- rectly checking the item occurrences but comparing the cofactors obtained by the items. In addition, S xy ≡ 0 implies S xy ⊆ S xy , namely, the set of item pairs with the cofactor implication always includes ones with the ordinary direct implication.  If we found a set of item pairs such that the cofactor im¬ plication holds but the ordinary implication does not hold, the result indicates a new aspect of item correlations which have never been considered. In our definition of the cofactor implication, we should be careful that we do not use Sxy for the checking condition. There is the case that a sub- pattern P co-occurs with only x but not with only y, and that P still co-occurs with xy. If we con- sider such cases, the definition of cofactor implica- tion can be modified as: Sxy ⊆ (Sxy ∪ Sxy) However, if we use this modified definition, the property is not always transitive, and x and y are not always symmetric when the cofactor implica- tion holds bidirectionally. In this paper, we con- sider only the simple definition: S x ⊆ S x y, which has beautiful properties.
4
ZBDD-based
for
algorithm
checking cofactor implication
In this section, we describe an efficient ZBDD- based algorithm of finding all the pairs of items such that the cofactor implication is holds for a given database S . The "naive" checking method is to generate ZB- DDs for S xy and S xy by cofactor operations for each pair of items x and y , and then compare the im- plication of the two cofactors. S xy and S xy can be computed in a constant time only if the two items CoImplyAll( S ) { ← () : for each item x used in S { ( S x , S x ) ← (Cofactors of S by x ) ; I x ← CoImplyItems( S = , S x ) , for each item y ∈ I x return I CoImplyItems( S = , S x ) { if (S x ≡ ∅) return ∅ ;
if (S x ≡ {1} && (S x ≡ ∅ | |S x ≡ {1}) ) return ∅ ; — Cache(S = , S x ) if (I x exists) return I x ; ( S = , S x ).top ; /* Highest ordered item in S = , S x */ (S xy, S xy) ← (Cofactors of S x by y) ; if ( S xy ≡ ∅)    I x ← CoImplyItems( S xy, S xy) ; else  I x ← CoImplyItems( S xy , S xy ) ;
else  I x ← CoImplyItems( S xy , S xy ) ∩ CoImplyItems( S xy , S xy ) ; if (S xy ⊆ S xy)   I x ← I x ∪ {y} ; Cache( S x , S x ) ← I x ; Figure 5: Sketch of the cofactor implication checking algorithm. x and y are at the nearly highest positions. Other- wise, the cofactor operation requires a linear time to the ZBDD size in average, so the total compu- tation time becomes O(n 2 | S |), where n is the num- ber of items and | S | is the number of ZBDD nodes for S . To improve this time complexity, we devel- oped an efficient recursive algorithm as presented in Fig. 5. Our algorithm consists of the two parts. In the first part "CoImplyAll()," we choose one of item x used in S , and then call the other part "CoIm- plyItems()" to find the set of items I x such that for any item y ∈ I x the cofactor implication from x to y holds. The core of our algorithm, CoImplyItems(), is recursively implemented based on the cofactor op- eration with the highest ordered item y. The problem for ( S , S x ) is divided into the two sub- problems for ( Sxy, Sxy ) and ( Sxy, Sxy ), and the re- sults of each sub-problems are computed recur- sively.  The main result for ( S x , S x ) is obtained as the intersection of the results of the two sub- problems. Finally, the checking condition for item y itself, S xy ⊆ S xy is determined and y is added into I x if it holds. As well as the many of ZBDD- based operations, this algorithm uses a hash-based cache technique to avoid duplicated recursive calls. The number of recursive calls can be bounded by the number of ZBDD nodes if the hash table works well. It is difficult to evaluate the exact complexity of CoImplyItems() due to the behavior of the hash- based cache.  Since CoImplyItems() is called from CoImplyAll() for only n times, our algorithm can be up to n times faster than O ( n 2 | S |) by the naive algorithm.
5
Experimental Results
We implemented our cofactor implication check- ing algorithm. The program is based on our own ZBDD package, and additional 70 lines of C++
We code for the symmetry checking algorithm. used a 2.8GHz Pentium-4 PC, 1.5 GB of main memory, with SuSE Linux 9 and GNU C++ com- piler. On this platform, we can manipulate up to 40,000,000 nodes of ZBDDs with up to 65,000 dif- ferent items. For evaluating the performance, we applied our method to the practical databases chosen from FIMI2003 benchmark set[5]. We first constructed a ZBDD for the set of all tuples in the database, and then apply our cofactor implication checking algo- rithm for the ZBDD. Table 2 shows the specifica- tions of database examples and the sizes of ZBDDs for them. In our experiments, so far we do not con- sider the number of frequency of each tuple, only dealing with binary information. The experimental results are shown in Table 3. In this table, we show our previous results of sym- metry checking[10] and this paper's results of co- factor implication checking.  The numbers of the cofactor implications are classified into the two cat- egories: the ordinary direct implications and the others, which are newly detected ones. We can observe that much larger number of the cofactor implications are detected compared with the sym- metric ones. This is a reasonable result since the cofactor implication is a partial condition of the
symmetry.
On the computation time, our implementation of cofactor implication checking is competitive to the symmetric checking algorithm, and in some ex- amples, our method is even faster than symmet- ric checking.  Since our results also including all the symmetric item pairs, we can use the cofac- tor implication checking algorithm as an alterna- tive method for the symmetric checking. We also compared the computation time with the naive al- gorithm to check all the n 2 pairs of items.  Our algorithm is 10 to 100 times faster than the naive one. In our experiments, we detected a small number of the cofactor implications which are not the ordi- nary direct implications. Those item pairs have no direct relationship of implication, but the implica¬ tion property holds between the co-occurring sub- patterns.  Figure 6 and 7 illustrate the diagrams of those cofactor implications generated by graph drawing software graphviz[4]. In the diagrams, the two nodes mutually connected indicate the sym- metric item groups. We can observe a number of correlated item clusters based on the connecting edges of the cofactor implications.  Those clusters possibly represent interesting structural informa- tion hidden in the database, which has not been discovered before.
6
Conclusion
In this paper, we proposed a new aspect of item- set mining based on the cofactor implication. We defined the cofactor implication as a relaxation of the symmetric condition, and discuss the meaning and the properties of the cofactor implication in the transaction databases. We also presented an effi- cient checking algorithm using ZBDD data struc- ture, and showed the experimental results for the actual database benchmark examples. The experi- mental results show that our method is very power- ful and will be useful for discovering hidden inter- esting information in the given data.  As our future work, we will apply our method to real-life data mining problems, in order to compare our result of the item correlations with the original meaning of the items in the databases. Analyzing co-occurrence words is a basic method in the area of natural language process- ing.  Our result indicates a new possibility of ap- plying the recent state-of-the-art data mining tech- niques to the knowledge analysis and natural lan- guage processing.
Acknowledgment
The author would like to thank Thomas Zeugmann, Hiroki Arimura, and Makoto Haraguchi of Hokkaido University for their valuable discussions and comments. This research was partially supported by Japan Soci- ety for the Promotion of Science, Grant-in-Aid for Sci- entific Research (B) on "ZBDD-based Database Anal- ysis," 17300041, 2007, and Grant-in-Aid for Specially Promoted Research on "Semi-Structured Data Mining," 17002008.