Nicolas Durand
email: nicolas.durand@univ-amu.fr

Mohamed Quafafou
email: mohamed.quafafou@univ-amu.fr

Approximation of Frequent Itemset Border by Computing Approximate Minimal Hypergraph Transversals

Keywords: frequent itemsets, borders, hypergraph transversals, approximation

In this paper, we present a new approach to approximate the negative border and the positive border of frequent itemsets. This approach is based on the transition from a border to the other one by computing the minimal transversals of a hypergraph. We also propose a new method to compute approximate minimal hypergraph transversals based on hypergraph reduction. The experiments realized on different data sets show that our propositions to approximate frequent itemset borders produce good results.

Introduction

The discovery of frequent itemsets has quickly become an important task of data mining [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF]. This corresponds to find the sets of items (i.e. attribute values) which appear together in at least a certain number of transactions (i.e. objects) recorded in a database. These sets of items are called frequent itemsets. The main use of the frequent itemsets is the generation of association rules. Nevertheless, the uses have been extended to other tasks of data mining such as supervised classification and clustering [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF]. Two points are important in the discovery of frequent itemsets. The first point is the reduction of the search space due to combinatorial explosion. The second point is the reduction of the number of generated itemsets to make easier the exploitation. In this paper, we focus on the second point. To reduce the number of itemsets, some condensed representations of frequent itemsets, such as the frequent closed itemsets, have been proposed [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF]. The maximal frequent itemsets (w.r.t. set inclusion) also represent a reduced collection of itemsets. They correspond to a subset of the set of the frequent closed itemsets. The regeneration of all the frequent itemsets is possible from the maximal frequent itemsets but they are not considered as a condensed representation of frequent itemsets because the database must be read to compute the frequencies. The maximal frequent itemsets and the minimal infrequent itemsets correspond respectively to the positive border and the negative border of the set of the frequent itemsets [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF]. These two borders are linked together by the computation of minimal hypergraph transversals (also called "minimal hitting sets") [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF][START_REF] De Marchi | Zigzag: a New Algorithm for Mining Large Inclusion Dependencies in Database[END_REF]. Thus, it is possible to switch to a border from the other one. The number of itemsets of the borders can still be huge.

In this paper, we propose a new approach to approximate the positive border of frequent itemsets in order to reduce the size of the border. This approach is based on the transition from a border to the other one by computing minimal hypergraph transversals. The approximation is obtained by the computation of approximate minimal transversals. Through the approximation, we also want to find new items which could be interesting for some applications like document recommendation. Another contribution is the proposition of a new method to approximate the minimal transversals of a hypergraph by reducing the hypergraph. To the best of our knowledge, this is the first time that such approaches are proposed. Some experiments have been performed on different data sets in order to evaluate the number of generated itemsets and the distance between the computed approximate borders and the exact borders. We focus on the comparison between our method and two other algorithms which compute approximate minimal transversals, in considering our approach of border approximation.

The rest of this paper is organized as follows. Section 2 defines the notations and the notions necessary for understanding the paper. The proposed approach of border approximation is detailed in Section 3. In Section 4, we present our method to compute approximate minimal hypergraph transversals. Related works are discussed in Section 5. The experiments and the results are presented in Section 6. We conclude in Section 7.

Preliminaries

Let D = (T , I, R) be a data mining context, T a set of transactions, I a set of items (denoted by capital letters), and R ⊆ T × I is a binary relation between transactions and items. Each couple (t, i) ∈ R denotes the fact that the transaction t is related to the item i. A transactional database is a finite and nonempty multi-set of transactions. Table 1 provides an example of a transactional database consisting of 6 transactions (each one identified by its "Id") and 8 items (denoted A . . . H).

A C E G t2 B C E G t3 A C E H t4 A D F H t5 B C F H t6 B C E F H
An itemset is a subset of I (note that we use a string notation for sets, e.g., AB for {A, B}). The complement of an itemset X (according to I) is noted X. A transaction t supports an itemset X iff ∀i ∈ X, (t, i) ∈ R. An itemset X is frequent if the number of transactions which support it, is greater than (or is equal to) a minimum threshold value, noted minsup. The set of all-frequent itemsets is noted S. Let us take the example of Before the presentation of the relationship between the positive border and the negative border of frequent itemsets, we need to introduce the notion of minimal transversals of a hypergraph. A hypergraph H = (V , E) is composed of a set V of vertices and a set E of hyperedges [START_REF] Berge | Hypergraphs: Combinatorics of Finite Sets[END_REF]. Each hyperedge e ∈ E is a set of vertices included or equal to V . The degree of a vertex v in H, denoted deg H (v), is the number of hyperedges of H containing v. Let τ be a set of vertices (τ ⊆ V ). τ is a transversal of H if it intersects all the hyperedges of H. A transversal is also called a "hitting set". The set of all the transversals of

H is: T r(H) = {τ ⊆ V | ∀e i ∈ E, τ ∩ e i = ∅}. A transversal τ of H is minimal if no proper subset is a transversal of H.
The set of all minimal transversals of H is noted M inT r(H). The relationship between the notion of borders and minimal transversals has been presented in [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF] and [START_REF] De Marchi | Zigzag: a New Algorithm for Mining Large Inclusion Dependencies in Database[END_REF].

In [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF], the following property has been showed: Bd -(S) = M inT r(Bd + (S)) where Bd + (S) is the hypergraph formed by the items of I (i.e. the vertices) and the complement of the itemsets of the positive border of S (i.e. the hyperedges).

In [START_REF] De Marchi | Zigzag: a New Algorithm for Mining Large Inclusion Dependencies in Database[END_REF], the following property has been showed: Bd + (S) = M inT r(Bd -(S)) where Bd -(S) is the hypergraph formed by the items of I (i.e. the vertices) and the itemsets of the negative border of S (i.e. the hyperedges).

The term dualization refers to the use of the previous properties to compute the negative border from the positive border, and vice versa. The size of the borders can be huge according to minsup. In the two next sections, we propose a new approach to approximate the borders and to reduce their size. In this way, the exploitation of the itemsets of the borders will be easier.

Proposed approach of border approximation

The proposed approach of border approximation exploits the dualizations between the positive border and the negative border. Let f and g be the functions that allow to compute respectively the negative border from the positive border and the positive border from the negative border:

f : 2 I → 2 I x → M inT r(x) g : 2 I → 2 I x → M inT r(x)
The principle of the proposed approach is to replace the function f by a function f which performs an approximate computation of the negative border. The new function f uses an approximate minimal transversals computation, noted M inT r: f : 2 I → 2 I

x → M inT r(x) From the positive border, the approach computes an approximate negative border (noted Bd -(S)):

f (Bd + (S)) = M inT r(Bd + (S)) = Bd -(S)
. The return to a positive border (via the function g) allows to obtain an approximate positive border (noted Bd + (S)): g( Bd -(S)) = M inT r( Bd -(S)) = Bd + (S). Thus, our approach produces the approximate negative border Bd -(S) and the corresponding approximate positive border Bd + (S). Let us take the example of Table 1 and let us compute the approximate border:

Bd -(S) = f (Bd + (S)) = M inT r(Bd + (S)) = M inT r({A, BC, CE, CH, F H} = M inT r({BCDEF GH, ADEF GH, ABDF GH, ABDEF G, ABCDEG}).
Let us assume that the approximate minimal transversals computation provides the following result: Bd -(S) = {D, E, G, AF, AH, BF, BH}. The approximate positive border is obtained by dualization:

Bd + (S) = g( Bd -(S)) = M inT r( Bd -(S)) = {ABDEG, DEF GH} = {CF H, ABC}.
We can remark that A, B, C and BC are frequent itemsets (according to minsup = 3) and here ABC is considered as a frequent itemset. CF H is not frequent (its support is equal to 2) but it is almost frequent. These two itemsets can be interesting for applications like document recommendation. For instance, without our approach, F H is frequent and CF H is not frequent. The item C is potentially interesting. If the items are documents, with our approach, the item C can be recommended to a user.

Computation of approximate minimal transversals

In order to complete the approach presented in the previous section, we proposed a method to compute the approximated minimal transversals of a hypergraph. The method is based on the reduction of the initial hypergraph. The aim is to compute the minimal transversals on the reduced hypergraph (smaller than the initial hypergraph). The proposed algorithm of reduction is specially designed to compute minimal transversals. It exploits the fact that the hyperedges formed by the complements of the itemsets of the positive border, strongly intersect (i.e. the average degree of a vertex is high). Indeed, in the example this hypergraph is: {BCDEF GH, ADEF GH, ABDF GH, ABDEF G, ABCDEG}. The proposed method is composed of two steps: (1) Reduction of the hypergraph, (2) Computation of the (exact) minimal transversals of the reduced hypergraph. At the end, the minimal transversals obtained from the reduced hypergraph are declared as the approximate minimal transversals of the initial hypergraph.

Reduction of the hypergraph

The hypergraph reduction of the initial hypergraph is based on the intersections of its hyperedges and on the degree of each vertex. The representative graph [START_REF] Berge | Hypergraphs: Combinatorics of Finite Sets[END_REF] (also called "line-graph") of the hypergraph is thus generated. Let us recall that the representative graph of the hypergraph H is a graph whose vertices represent the hyperedges of H and two vertices are adjacent if and only if the corresponding hyperedges in H intersect. In our algorithm, we add values to the edges of the representative graph. Algorithm 1 presents the reduction of a hypergraph H. The algorithm is composed of three steps: (1) Computation of the degree of each vertex in H (lines 1-3), ( 2 VR

for all v ∈ V do 2: Compute degH(v) 3: end for 4: V ← {v i } i = 1, . . . , m; {each v i ∈ V represents ei ∈ E} 5: E ← {}; 6: for all v i ∩ v j = ∅ do 7: E ← E ∪ {(v i , v j )}; 8: w (v i ,v j ) ← v∈{ψ -1 (v i )∩ψ -1 (v j )} degH (v)
← VR ∪ {ψ -1 (v maxi) ∩ ψ -1 (v maxj)}; 15: ER ← ER ∪ {{ψ -1 (v maxi) ∩ ψ -1 (v maxj)}}; 16:
Delete the edges e ∈ E where v maxi or v maxj is present 17: end while 18: return HR;

Valued representative graph generation (lines 1-9) Let be H = (V, E) a hypergraph (|V | = n and |E| = m). The algorithm constructs a valued graph G=(V , E ) where V = {v i } (i = 1, . . . , m) and E = {e k } (k = 1, . . . , l). A vertex v i represents a hyperedge e i from H. Let be ψ : E → V the bijective function who associates a hyperedge e i to a vertex v i . A hyperedge between v i and v j shows that the intersection between the hyperedges ψ -1 (v i ) and ψ -1 (v j ) (e i and e j from H) is not empty. The weight of an edge is based on the degree of each vertex in the corresponding intersection. To evaluate the weight of a generated edge, we use the degree of each vertex from the initial hypergraph.

The idea is that a vertex very present has a good chance to be in a minimal transversal. This expresses a "degree" of transversality. If the degree of a vertex is equal to the number of hyperedges then this vertex is a minimal tranversal. Let us note that this heuristic is used by several algorithms that compute transversals [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF][START_REF] Ruchkys | A Parallel Approximation Hitting Set Algorithm for Gene Expression Analysis[END_REF]. The weight of an edge e k = (v i , v j ), noted w e k , is the sum of the degree of the vertices present in the intersection which has led to create this edge (see [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF]).

w

e k = v∈{ψ -1 (v i )∩ψ -1 (v j )} deg H (v). ( 1
)
Generation of the reduced hypergraph (lines 10-17) After the creation of the valued representative graph, the algorithm performs a selection of edges with a greedy approach. It selects the edge having the higher weight value while there are edges left in G. Each selected edge is transformed to a hyperedge of the reduced hypergraph. This hyperedge contains the vertices from H corresponding to the intersection of the two vertices of the edge. We obtain, at the end, a set of hyperedges corresponding to the reduced hypergraph H R =(V R ,E R ). Let us remark that if several edges have the same weight, the first found edge is selected. Let us consider the example of Table 1 as a hypergraph H (6 hyperedges, 8 vertices). The reduced hypergraph is H R = (V R , E R ) where V R = {A, B, C, E, F, H} and E R = {{A, C, E}, {B, C, F, H}}).

Minimal transversal computation

The last step is the computation of the (exact) minimal transversals of the reduced hypergraph. These transversals correspond to the approximate minimal transversals of the initial hypergraph: M inT r(H) = M inT r(H R ). Let us take our example, the minimal transversals of H R are: {C, AB, AF , AH, BE, EF , EH}. We consider them as the approximate minimal transversals of H. Let us remark that the (exact) minimal transversals of H are: {AB, AC, CD, CF , CH, EF , EH, GH, AF G, BDE}.

Related works

Numerous methods have been proposed to reduce the number of itemsets. In [START_REF] Moens | Randomly Sampling Maximal Itemsets[END_REF], the authors have studied the problem of randomly sampling maximal itemsets without explicit enumeration of the complete search space. They have employed a simple random walk that only allows additions of singletons to the current set untill a maximal set is found. In [START_REF] Vreeken | Krimp: Mining Itemsets that Compress[END_REF], the authors have used the Minimum Description Length (MDL) principle: the best set of itemsets is that set that compresses the database best. In [START_REF] Afrati | Approximating a Collection of Frequent Sets[END_REF], the approximation of a collection of frequent itemsets by the k best covering sets has been studied. The proposed algorithm takes in input the whole collection of the frequent itemsets or the positive border. The authors have explained the difficulties to use a greedy algorithm to obtain, from the positive border, k covering sets belonging to the initial collection. Our approach computes an approximate border from a border given completely in input. In that respect, we are close to the works presented in [START_REF] Afrati | Approximating a Collection of Frequent Sets[END_REF]. The exact positive border is the algorithm's input. Nevertheless, we do not want to find some covering sets and the itemsets of the approximate border do not necessarily belong to the initial collection. Our approach is more controllable than MDL used in [START_REF] Vreeken | Krimp: Mining Itemsets that Compress[END_REF]. We have the possibility to have several different methods to approximate the negative border ( f ). Moreover, we have an understanding mapping between the exact border and the approximation border.

The computation of minimal transversals is a central point in hypergraph theory [START_REF] Berge | Hypergraphs: Combinatorics of Finite Sets[END_REF]. The algorithms to compute the minimal transversals come from different domains: graph theory, logic and data mining [START_REF] Hagen | Algorithmic and Computational Complexity Issues of MONET[END_REF]. This is a NP-hard problem. The algorithms of approximation of minimal transversals are rare. Some works approximate the minimal transversals in order to obtain some ones or only one [START_REF] Ruchkys | A Parallel Approximation Hitting Set Algorithm for Gene Expression Analysis[END_REF]. Some works are based on an evolutionary computation [START_REF] Vinterbo | Minimal Approximate Hitting Sets and Rule Templates[END_REF] where the transversality and the minimality are transcribed in a fitness function where a parameter, noted , is the fraction of hyperedges needed to intersect by any generated transversals. In [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF], the Staccato algorithm computes low-cost approximate minimal transversals with a depth-first search strategy. It has been designed for model-based diagnosis. We have adapted Staccato in order to compute approximated minimal transversals in general. Staccato sorts the vertices according to their degree in increasing order. At each step, only the first λ (%) vertices of the remaining hypergraph are used. The more the λ value is high, the more the result is close to the set of the minimal transversals. The algorithm presented in [START_REF] Rioult | Nonredundant Generalized Rules and Their Impact in Classification[END_REF], that we call δ-M T miner, produces minimal transversals which can miss at most δ hyperedges. It uses a breadth-first search strategy and several itemset discovery techniques. We have a different approach to compute approximate minimal transversals. We propose to apply a hypergraph reduction and then to compute the minimal transversals of the reduced hypergraph. These transversals are considered as the approximate minimal transversals of the initial hypergraph. Moreover, we don't need to set any parameters.

Experiments

Data and Protocol

Four data sets have been used: Mushroom, Chess, Connect and Kosarak. They have been downloaded from the FIMI web site1 . Mushroom contains data on 23 species of gilled mushrooms. Chess contains some strategies for chess sets. Connect contains strategies for the game of connect-4. Kosarak contains anonymized click-stream data of a hungarian on-line news portal. The data sets (see Table 2) have been chosen to cover the different types of existing data sets according to the classification proposed by Gouda & Zaki [START_REF] Gouda | Efficiently Mining Maximal Frequent Itemsets[END_REF].

The protocol of the experiments is as follows: For each data set and for some minimum support threshold values, (1) Compute the positive border according the minimum support threshold value, with IBE [14], (2) Compute the (exact) negative border with Border-Dif f [START_REF] Dong | Mining Border Descriptions of Emerging Patterns from Dataset-Pairs[END_REF], the approximate negative border with 1-M T miner [START_REF] Rioult | Nonredundant Generalized Rules and Their Impact in Classification[END_REF], the approximate negative border with Staccato [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF], and the approximate negative border with our method (noted AM T HR -Approximate Minimal Transversals by Hypergraph Reduction), (3) Dualize to the positive borders (1 exact border and 3 approximate borders) with the Border-Dif f algorithm which computes minimal transversals. For δ-M T miner (cf. Section 5), we have set δ to 1 because this value has produced the best results for δ-M T miner.

For Staccato (cf. Section 5), we have chosen the highest values of λ before being impraticable: λ=0.8 for Mushroom, λ=0.65 for Chess, λ=0.7 for Connect, and λ=0.95 for Kosarak. In Steps 2 and 3, some statistics are computed: the number of itemsets of the computed border, the average size of the itemsets of the computed border, and the distance between the set of the itemsets of the computed border and the set of itemsets of the exact border. To evaluate the distance between two borders, we have used the distance of Karonski & Palka based on the Hausdorff distance. The cosine distance (see ( 2)) have been chosen to compute the distance between two elements (i.e. two itemsets). The distance D between two set of itemsets X and Y is defined in (3).

d(X, Y ) = 1 - |X ∩ Y | |X| × |Y | . (2)
D(X , Y) = 1 2 {h(X , Y), h(Y, X )} where h(X , Y) = max X∈X {min Y ∈Y d(X, Y )}. (3)

Results and Discussion

Due to space constraints, Figures about the average size of an itemset of the computed borders, are not presented in the paper. All the figures are available online 2 . Moreover, we do not present the execution times because this is not our main objective. For information, the computation of Bd -(S) with AM T HR is longer than with the other algorithms. The computation of Bd + (S) is the fastest with AM T HR. Fig. 1, 2, 3 and 4 present, for each data sets, the number of itemsets of the computed negative borders and the distance between the computed negative borders and the exact negative borders. We can observe that the cardinality of Bd -(S) is lower than the cardinality of Bd -(S) for each data sets. For information, the itemsets of Bd -(S) are shorter than the itemsets of Bd -(S). They To resume, we can note that the proposed method, AM T HR, has reduced the number of itemsets of the generated positive borders, while keeping a reasonable distance to the exact positive borders. Moreover, our method seems to be robust according to the different types of data sets.

Conclusion

We have proposed a new approach of approximation of frequent itemset borders based on the computation of approximate minimal hypergraph transversals. From the exact positive border, an approximate negative border is computed and then the corresponding approximate positive border is generated by dualization. The proposed computation of approximate minimal transversals is based on hypergraph reduction. There is no need to set any parameters. In the experiments, we have showed that our method produces an approximate positive border smaller than the exact positive border, while keeping a reasonable distance with the exact border. These results confirm that the proposed method is interesting to find potentially interesting new items. In the future, we will thus develop a recommendation system using the approximate positive borders. In that way, we will able to evaluate the quality of the approximation.

  ) Generation of the valued representative graph of H (lines 4-9), (3) Generation of the reduced hypergraph from the valued representative graph (lines 10-17). The complexity of the algorithm is in O(m 2 ) where m is the number of hyperedges of the initial hypergraph. Algorithm 1 HR (Hypergraph Reduction) Require: a hypergraph H=(V , E) where |V |=n and |E|=m Ensure: the reduced hypergraph HR 1:

; 9: end for 10 :

 10 VR ← {}; 11: ER ← {}; 12: while E = ∅ do 13:Select e max = (v maxi, v maxj) having the maximal weight value 14:

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .

 12345678 Fig. 1. Negative borders computed on Mushroom (according to minsup).

Table 1 .

 1 Example of transactional database

	Id	Items
	t1

Table

  1, if minsup=3 then the itemset H is frequent because 4 transactions support it (t 3 , t 4 , t 5 and t 6 ). AE is not frequent because only t 1 and t 3 support it.The set of all maximal frequent itemsets (resp. minimal infrequent itemsets), w.r.t. set inclusion, in D is the positive border (resp. negative border )[START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF] of S and is noted Bd + (S) (resp. Bd -(S)):Bd + (S) = {X ∈ S | ∀Y ⊃ X, Y / ∈ S} and Bd -(S) = {X ∈ 2 I \ S | ∀Y ⊂ X, Y ∈ S}. Letus take the example of Table 1, if minsup=3, Bd + (S) = {A, BC, CE, CH, F H} and Bd -(S) = {D, G, AB, AC, AE, AF, AH, BE, BF, BH, CF, EF, EH}.

Table 2 .

 2 Data sets used in the experiments.

	Dataset #transactions #items Avg. size of a trans. Gouda & Zaki
	Mushroom	8124	119	23	type 4
	Chess	3196	75	37	type 1
	Connect	67557	129	43	type 2
	Kosarak	990002	41270	8,1	type 3

Frequent Itemset Mining Implementations, http://fimi.ua.ac.be/data/