In this paper, we propose the first approach to deal with enumeration problems with huge number of solutions, when interestingness measures are not known. The idea developed in the following is to partially enumerate the solutions, i.e. to enumerate only a representative sample of the set of all solutions. Clearly many works are done in data sampling, where a data set is given and the objective is to compute a representative sample. But, to our knowledge, we are the first to deal with sampling when data is given implicitly, i.e. data is obtained using an algorithm. The experiments show that the proposed approach gives good results according to several criteria (size, frequency, lexicographical order).
Most of problems in data mining ask for the enumeration of all solutions that
satisfy some given property [
There are several approachs to enumerate all solutions to a given enumeration
problem. Johnson et al. [
In this paper, we deal with enumeration problems with huge number of solutions, when interestingness measures are not known. This case happens when the expert has no idea about data and knowledges that are looking for. The objective is to enumerate only a representative sample of the set of all solutions. Clearly many works are done in data sampling, where are given a data set and the objective is to compute a representative sample. To our knowledges, this idea is new for sampling when data is given implicitly, i.e. data is obtained using an algorithm. One can use the naive approach which first enumerates all the solutions and then applies sampling methods, which is not possible for huge number of solutions.
To evaluate our approach, we consider a challenging enumeration problem,
which is related to mining maximal frequent item sets [
Golovach et al. [
A hypergraph H = (V, E ) consists of a finite collection E of sets over a finite set V . The elements of E are called hyperedges, or simply edges. An hypergraph is said simple if for any E, E0 ∈ E E 6⊆ E0. A transversal (or hitting set) of H is a set T ⊆ V that intersects every edge of E . A vertex x in a transversal T is said to be redundant if T \ {x} is still a transversal. A transversal is minimal if it does not contain any redundant vertex. The set T of all minimal transversal of H = (V, E ) constitutes together with V also a hypergraph T r(H) = (V, T ), which is called the transversal hypergraph of H. We denote by k = PE∈E | E |. Example 1. Consider the hypergraph H = (V, E ): V = {1, 2, 3, 4, 5} and E = {E1, E2, E3} with E1 = {1, 3, 4}, E2 = {1, 3, 5} and E3 = {1, 2}. The set of all minimal transversals is T = {{1}, {2, 3}, {2, 4, 5}} and k = 3 + 3 + 2 = 8
Given a simple hypergraph H = (V, E ), the transversal hypergraph
enumeration problem concerns the enumeration without repetitions of T r(H). This
problem has been intensively studied due to its link with several problems isuch as
data mining and learning [
We introduce the partial (or incomplete) search algorithm for enumerating minimal transversals of an hypergraph H. The search space is the set of all transversals which is very large. The strategy is divided into two steps: – The initialization procedure considers a transversal T of H and then applies a reduction (at random) algorithm to T in order to obtain a minimal transversal Tm of H. This step is detailed in section 4.1. – The local search algorithm considers a minimal transversal Tm and then applies local changes to Tm in which we add and delete vertices according to some ordering of the vertices. This step is detailed in section 4.2 These steps are repeated for at most k transversals depending on the input hypergraph H. Figure 1 illustrates the proposed approach. Let H(V, E ) be the input hypergraph, E ∈ E and x ∈ E. The initialization step starts with the transversal (V \ E) ∪ {x} and then applies a reduction algorithm to obtain a minimal transversal. The following property shows that the set (V \ E) ∪ {x} is a transversal and any minimal transversal contained in (V \ E) ∪ {x} contains the vertex x.
Property 1. Let H = (V, E ) be a simple hypergraph, E ∈ E and x ∈ E. Then (V \ E) ∪ {x} a transversal of H. Moreover, any minimal transversal T ⊆ (V \ E) ∪ {x} will contain x.
Proof. Let H = (V, E ) be a simple hypergraph and E0 ∈ E with E 6= E0. Since H is simple then there exists at least one element y ∈ E0 such that y 6∈ E. So y ∈ (V \ E) and thus E0 ∩ (V \ E) 6= ∅. We conclude that (V \ E) ∪ {x} is a transversal since x ∈ E.
Now let T ⊆ (V \E) ∪{x} be a minimal transversal. Then E ∩ (V \E) ∪{x} = {x} and thus x must belong to T otherwise T does not intersect E.
According to property 1, we can apply the initialization procedure to any pair (x, E) where E ∈ E and x ∈ E. In other words, the initialization is applied to at most k transversals of H as shown in Algorithm 1.
Algorithm 1: Initialization
Input : A hypergraph H(V, E ) and σ an ordering of V Output: A sample of minimal transversals begin
ST RAN S = ∅; for E ∈ E do for x ∈ E do
T = (V \ E) ∪ {x};{Initial transversal} Tm = Reduce(T, σ);
ST RAN S = ST RAN S ∪ {Tm}; return(ST RAN S);
Now we describe the reduction process, which takes a transversal T and a random ordering σ of V and returns a minimal transversal Tm. Indeed, we delete vertices from T according to the ordering σ until we obtain a minimal transversal.
Input : A transversal T and an ordering σ = σ1...σ|V | of the vertices of
H.
Output: A minimal transversal for i = 1 to |V | do if T \ {σi} is a transversal then
T ← T \ {σi} ;
Example 2 (continued). Suppose we are given the hypergraph in example 1 and σ = (1, 2, 3, 4, 5) for the input to Algorithm 1. First, it takes the hyperedge E = {1, 3, 4} and for x = 1 we obtain the minimal transversal {1}, for x = 3 we obtain {2, 3} and for x = 4 we obtain {2, 4, 5}. Then the algorithm continue with the hyper edges {1, 3, 5} and {1, 2}. Finally the algorithm returns ST RAN S = {{1}, {2, 3}, {2, 4, 5}}, i.e. the other iterations do not add new minimal transversals.
Theorem 1. Algorithm 1 computes at most k minimal transversals of an input hypergraph H = (V, E ).
Proof. The initialization procedure considers at most k minimal transversals of H. Since a minimal transversal can be obtained several times, the result follows.
The following proposition shows that any minimal transversal of the hypergraph H = (V, E ) can be obtained using the initialization procedure. Indeed, the choice of the ordering σ is important in the proposed strategy.
Proposition 1. Let H = (V, E ) be an hypergraph and T be a minimal transversal of H. Then, there exists a total order σ, E ∈ E and x ∈ E such that T = Reduce((V \ E) ∪ {x}, σ).
Proof. Let T be a minimal transversal of H = (V, E ). Then there exists at least one hyperedge E ∈ E such that T ∩ E = {x}, x ∈ V , otherwise T is not minimal. Thus T ⊆ (V \ E) ∪ {x}. Now, if we take the elements that are not in T before the elements in T in σ, the algorithm Reduce((V \ E) ∪ {x}, σ) returns T .
The initialization procedure guaranties that for any vertex x ∈ V at least one minimal transversal containing x is listed. The experiments in section 5, shows the sample of minimal transversals obtained by the initialization procedure is a representative sample of the set of all minimal transversals. 4.2
The local search algorithm takes each minimal transversal found in the initialization step and searches for new minimal transversals to improve the initial solution. The search of neighbors is based on vertices orderings.
Let H = (V, E ) be an hypergraph and x ∈ V . We define the frequency of x as the number of minimal transversals of H that contain x. The algorithm takes a minimal transversal T and a bound N max which bounds the number of iterations and the number of neighboors generated by T . Each iteration of the while loop, starts with a minimal transversal T and computes two orderings as follows: – σc is an ordering according to the increasing order of frequency of vertices in V \ T in minimal transversals already obtained by the current call. This ordering has a better coverage of the solution set, i.e. by keeping the rarest vertices in the transversals. – σ is a random ordering of the vertices in T .
Input : A minimal transversal T of H = (V, E ) and an integer N max Output: A set of minimal transversals Q = T ; i = 1; while i ≤ N max do σc ← the set V \ T sorted in increasing order of frequency of vertices in minimal transversals in Q; σ ← sort T at random; Add elements the elements in σc to T until a vertex x ∈ T \ σc becomes redundant in T ; T =Reduce(T, σ); Q = Q ∪ {T }; i = i + 1; return(Q);
Now we give the global procedure of the proposed approach.
transversals
Input : An hypergraph H = (V, E ) and an integer N max Output: A sample of minimal transversals of H
4: Global procedure for partial enumeration of minimal σ =choose a random ordering of V ; ST RAN = Q = Initialization(H, σ); while Q 6= ∅ do
T = choose a minimal transversal T in Q;
ST RAN S = ST RAN S ∪ N eighboor(T, N max);
In the following, we describe experiments to evaluate the results that have been obtained. 5
The purpose of the experiments is to see if the proposed approach allow us to
generate a representative set of solutions. For this reason, we have conducted
the experiments on two different classes of hypergraphs (see [
In the following, we denote Tpartial the set of minimal transversals generated by Algorithm 4, and Texact the set of all minimal transversals. First, we analyze Tpartial. the percentage Tpartial and then we evaluate the representativeness of the sample
Texact We will distinguish between minimal transversals that are obtained using Algorithm 1 (or the initialization procedure) and those that are generated using the local search. For these tests we set the maximal number of neighboors N max to 3.
Tables 1 and 2 show the results for the two classes of hypergraph instances, namely ”lose” and random ”p8”.
– instance: instance name. – instance size: the size of the instance (number of edges × number of vertices). – total # of transv.: the exact number of minimal transversals | Texact |.
The second (resp. last) three columns give the results for the initialization procedure (resp. Global algorithm): – # transv. found : the number of minimal transversals found. – % transv. found : the percentage of minimal transversals found. – cpu (s): the run time in seconds
According to these tests, we can see that the percentage of minimal transversals found using the initialization procedure is very low, but it decreases as far as the size of Texact increases. Clearly, this percentage is strongly related to the input. Indeed, the number k (entropy) of the hypergraph increases according to the size of the input hypergraph. We can also see that the local search increases significantly the number of solutions found by a factor 2 to 2.5 approximatively. But it remains coherent with the chosen value N max = 3. It argues that the local search finds other transversals that are not found either by the initialization procedure nor previous local search. Notice that the parameter N max can be increased whenever the size of Tpartial is not sufficient. To evaluate the representativeness of Tpartial, we consider three criteria: – Size of the minimal transversals in Tpartial. – Frequency of vertices in Tpartial. – Lexicographical rank of the minimal transversals in Tpartial.
Each criteria is illustrated using a bar graph for two instances from different classes. The bar graphs in figures 2 and 3 are surprising. Indeed the bar graphs vary nearly in the same manner with respect to the initialization and the local search algorithm for all the considered criteria.
Figures 4 and 5 show that the set Tpartial is also representative even when considering minimal transversals with the same size. Indeed, minimal transversals having the same size are spread out using a norm. We notice that the points corresponding to minimal transversals in Tpartial are scattered in the image.
This experiment allows us to conclude that the sample Tpartial produced by Algorithm 4 is representative relatively to the criteria under consideration. Other results can be found in http://www2.isima.fr/˜toussain/ 6
We are convinced that the initialization procedure is the most important in this approach. Indeed, the set of minimal transversals obtained using this procedure is a representative sample, since it garantee that for any vertex of the hypergraph there is at least one minimal transversal which contains it (see property 1). Moreover the local search procedure can be used to increase the number of solutions, and as we have seen in the experiments, it keeps the same properties as the initialization procedure.
We hope that this approach improves enumeration in big data and will be
of interests to the readers to investigate heuristics methods [
This paper opens new challenges related to partial and approximate
enumeration problems. For example, given an hypergraph H = (V, E ), is there an
algorithm that for any given ε, it enumerates a set Tpartial ⊆ T r(H) such that
(1 − ε)|T r(H)| ≤ |Tpartial| ≤ |T r(H)|? We also require that the algorithm is
output-polynomial in the sizes of H, Tpartial and 1ε . To our knowledge, there is
no work on approximate algorithms for enumeration problems, but results on
approximate counting problems may be applied [
Acknowledgment: This work has been funded by the french national research agency (ANR DAG project, 2009-2013) and CNRS (Mastodons PETASKY project, 2012-2015).