Large data processing is an essential problem in many data mining application. Our work explores the algorithms calculating a Generalized Galois Lattice (G2L) over a large collection of data. A G2L contains all the so-called closed sets of a collection of tuples (individuals characterized by a set of properties), G2Ls generalize to multivalued data the GL already popular in the concept analysis using the binary values. They appear an attractive tool for data mining. The G2L or GL calculus is CPU intensive. In practice, the current techniques limit the approach only to small sets of data only, e.g., a hundred tuples with a few dozens of properties each. Our research consists in building scalable distributed G2L calculus algorithms. We think this research direction promising and probably the only way towards our goal. We first have implemented and analyzed some centralized algorithms. One termed ELL seems to be the most efficient. We have defined therefore a scalable distributed version of ELL termed SD-ELL. It recursively partitions the set of tuples for the G2L computation over sufficiently many sites to let ELL execute fast enough at each site. The closed sets produced by each site enter a common scalable distributed data structure (SDDS). We then plan to test the resulting behavior and analyze the performance of the algorithm and of some promising variants.
A Galois Lattice (GL) allows extracting concepts and rules from other concepts.
Several algorithms determine the GL over a given context C, provided the size of C is
small, [
Further analysis has shown that the most promising way towards larger sets of data, the only of interest to the data mining, was to find some scalable distributed variant of G2L calculus. This goal becomes the subject of our work.
We have defined therefore a scalable distributed version of ELL termed SD-ELL. It recursively partitions the set of tuples for the G2L computation over sufficiently many sites to let ELL execute fast enough at each site. The closed sets produced by each site enter a common scalable distributed data structure (SDDS). We then plan to test the resulting behavior and analyze the performance of the algorithm.
The rest of the paper is organized as follows. In Section 2, we recall the definition of a
G2L. Section 2 recalls the main idea in ELL. Section 3 overviews the principles of our
scalable distributed extension, exploring the recursive G2L calculation in [
Concept lattice [
Definition 1. A lattice is a mathematical structure F = < F, , , , 0F, 1F >, where F is a partially ordered set by the relation , with the largest element 1F, a smallest element 0F, and , are internal composition laws of sup (or supremum), and inf (or infimum).
In many situations F is the Cartesian product of several lattices Fj = <Fj, j, j, j, 0Fj,1Fj>, for j J = {1,..., n}. We write this F=F1 x...x F x...x Fn.
The relation on F is defined by z = (z1, ...,zj, ...,zn) t = (t1, ...,tj, ...,tn) iff zj j tj for each j of J . We note z t = (..., zj j tj,....), z t = (..., zj j tj, .... ), OF = (....,OFj, ... ), 1F = (..., 1Fj, ). (For standard Galois lattices, we have for each j: Fj = {0, 1}, 0 < 1, 0 j 0 = 0, 0 j 1 = 1 j 0 = 1 j =1, 0 j 0 = 0 j 1 = 1 j 0 = 0, 1 j 1 = 1. So OF = (...., 0, ...), and 1F = (..., 1,...)).
Let m be a finite positive integer, I = {1,..., m} = [1, ,m], and F any lattice. Let d:I F be any mapping from I to F. A context C is defined as an array with rows d (i), i = 1, ..., m.
Formalism: The context provides, for each individual or object i of I, its description d(i)=(d1(i), d2(i), , dj(i),..., dn(i)) F = F1 x x Fn, according to the attributes or properties j J. (In the standard case, dj(i)=1 means that i has property j, and dj(i) = 0 means that i has not the property j). So, in the general case, C is an m x n array of elements dj (i) of F, and for each individual i and each property j, dj (i) is the value of this property for i.
Let C = <I, F, d> be a context. We define E = P(I), |E|=2l and f: E F as follows: for each subset X of I, f(X) = d(i): i X} if X , and f( ) = 1F.
So, f(X) is the infimum of the descriptions d(i) of elements i of X. And in the standard case f(X) is an element z = (z1,..., zj, ...) of F, and zj = j {dj(i) : i X} = 1, iff dj(i)=1, for each i of X. This means that zj = 1 iff j is a property which belongs to all i in X. For this reason, we call f (X) the intent of X.
For each i of I, we have f({i}) = d(i), and f is decreasing (if X X I then f(X ) f(X)).
We define g: F E by g(z) = {i I: z d(i)}, for each z of F.
We say that g(z) is the extent of z. (In standard case, g(z) is the set of all individuals who have all properties of z, zj = 1).
We can see that g is also a decreasing mapping.
The ordered pair (f, g) is called a Galois connection. From it we derive two other mappings: h : P(I) P(I), by h = g f, and k = F F by k = f g.
So, for each subset X of I, we have h(X) = g(f(X)) = {i I: f(X) d(i)}, and for each z of F, we have k(z) = f(g(z)) = {d(i): i g (z)}.
We can see that h and k are closure operators. This means that each of them is an increasing, extensive, and idempotent operator. More explicitly, for each X, X of E, and z, z of F:
X X implies that h(X) h(X ), z z implies that k(z) k(z ); X h(X), z k(z); h(h( X)) = h(X), k(k( z)) = k(z) .
Any subset X of I such that X = h(X) is called a I-closed set, and each z of F such that z = k(z) is called F-closed element.
Let us define H = {X I: h(X) = X} the set of all closed subsets of I, and K = {z F: z = k(z)}, the set of all closed elements of F.
One can proof that there is a bijective mapping between H and K. The ordered pairs (X, z) H x K such that f(X) = z, and therefore such that g(z) = X, are called the concepts associated with the context C.
The set of all such concepts constitutes the Galois lattice GL(C) associated with this context C. (the order relation on GL(C) is defined by (X, z) (X, z ) iff X X and z z.)
This algorithm was proposed in [
Main idea: For two disjoint subsets X0 and K of the set of objects I, let ELL (X0, K) denote a procedure which lists all the closed sets of I obtained by extending X0 with some elements of K.
In other words, ELL (X0, K) lists all the closed sets, which strictly contain X0 and are contained in X0 U K. Obviously, ELL (Ø, I) lists all the non-empty closed sets of I. ELL (X, K) proceeds by dichotomy as follows: If (K Ø)
Choose an element i0 K Find the closed sets which contain i0
Find the closed sets which do not contain i0
Endif The key point of the proposed algorithm is that the search time of such closed sets is considerably reduced by using the following proposition.
Proposition: Let X0 and K Ø be two disjoint subsets of I. Let i0 K.
We have: h(X0 U {i0}) = X0 U A where A = {i I\X0: f(X0) f(i0) f(i)} If a closed set contains X0 and i0, then it also contains A. Hence, if A K then X0UA is the smallest closed set containing X0 and i0 and contained in X0 U K. If a closed set contains X0 and does not contain i0, then it also does not contain any element of the set: R = {i K: f(X0) f(i) f(i0)}.
A (vs. R) is used for Attraction (vs. Rejection). The proof of this proposition is in [
GL = Ø // GL is a list of concepts Var i0: element of I, z, z0: elements of F; X, A, R: subsets of I; begin z0 = f(X0); if K Ø then begin Choose an element i0 of K; z = z0 f(i0); A = {i I\X0: z f(i)}; if A K then begin
X = X0 U A; insert node (X, z) in GL; ELL (X, K\A); end;
R = {i K: z0 f(i) f(i0)}; ELL (X0, K\R); end end The procedure ELL (Ø, I) starts with any i0 I (I is non empty). Then it determines the set A. Observing that i0 A, we have the strict inclusions Ø X and I\A I. Hence if A K, ELL (X, I\A) will run with a strictly smaller second parameter. Since i0 R, we see that the same holds for ELL (X, I\R).
More generally ELL (X, K\A) and ELL (X0, I\R) run with a strictly smaller second parameter than that of ELL (X, K). Since I is finite, this parameter which is a subset of I, will reach the void set and the procedure will terminate.
This algorithm lists all closed sets without duplicates. Let us show that each closed set F occurs exactly once. Starting with GL = Ø, X0 = Ø and K = I, let i0 I be fixed and consider two cases: i0 F and i0 F. If i0 F then
Either F is the smallest closed set which contains i0. Then according to the previous proposition (a), F=X=X0 U A and F will be listed by ELL (X0, K),
Or F is not the smallest closed set which contains i0. In this case X F and F will be listed by ELL (X, K\A).
If i0 F, then according to the previous proposition (c), F will be listed by ELL(X0,K\R). Since each insert only concerns the unique smallest closed set containing X0 and i0, we see that F occurs exactly once.
The only case not treated by the algorithm is whether the empty set is closed or not. The algorithm yields all the nodes (X, z) of the GL such that X Ø. Since f(Ø) = 1F and h(Ø) ={i I: 1F f(i)} = {i I : f (i) = 1F}, Ø is closed iff there is no i I such that f(i) = 1F.
2
We proposed a first solution in [
We have designed therefore a new solution to parallelize the work. It is based on a new algorithm, termed SD-ELL. The key idea is a recursive application of ELL.
SD-ELL is composed of two algorithms. The first one computes the sets of objects Ki ( i={1, , n}, n is the number of the computed sets Ki) and the second one is duplicated on different machines to compute all the closed sets corresponding to each Ki.
The algorithm presented in the following table permits computing the sets Ki. It proceeds as follows:
Choose an element i0 K Compute the sets A and R Verify if A K then (X, Z) is a closed itemset and Ki = K\A
Ki+1 = K\R The previous steps are reused with the parameters Xi and Ki. The process of decomposing Ki is stopped if |Ki| is smaller than a fixed threshold or the total number of machine, in which the closed itemsets corresponding to each Ki are computed, is used.
LF = Ø; List of (K, X, z) t = 1, q = 1, Xt = Ø, Kt = I, zt = 1F. while ((t q) and ((q - t + 1) site number)) begin X0 = Xt; K0 = Kt; z0=zt Choose an element i0 of K z = z0 f (i0); A = {i I\X0: z f(i)}; R = {i K: z0 f(i) f(i0)}; if A K0 then begin
X = X0 A; z = z0 f(i0); K = K0\A;
LF = LF (X, z)
q=q+1; Xq = X; Kq = K; zq = z;
end
q = q + 1; Xq = X0; Kq = K0\R; zq = z0; t = t + 1;
end
The second algorithm constituting SD-ELL is the iterative version of ELL (I-ELL)
duplicated on different machines. This version is detailed in [
O\A 1 2 3 4 5 6 a 12 12 10 13 17 0 b 16 12 13 14 10 14 c 6 8 16 11 10 3 d 10 12 14 10 14 8 e 12 11 11 13 13 4 f 13 13 8 13 10 13 g 12 11 12 12 14 11 h 6 8 10 14 12 10 For this example the threshold is 4 and the number of machine is 4.
The dispatcher executes the first algorithm (KCompute). KCompute starts with the parameters X0=Ø and K= I ={1,2,3,4,5,6}. An element i0 is chosen such as i0=1 and then the sets A, K1, R, and K2 are computed.
z = z0 f (i0) = {12,16,6,10,12,13,12,6}, A = {i I \ X0: z f (i)}={1}. Then A K: X1=X0UA={1} and C2({1};{12,16,6,10,12,13,12,6}) is a concept.
K1 = K\A = {2,3,4,5,6}; |K1| 4, K1 must then be decomposed.
R = {i K: z0 f (i) f (i0)} = {1} K2 = K\R = {2,3,4,5,6}; |K2| 4, K2 must also be decomposed.
The previous steps are reused with the parameters (X1 = {1}, K1) and (X0=Ø, K2). Decomposition of K1: Choosing i0 K1 such as i0 = 2.
z = z0 f (i0) = {12,12,6,10,11,13,11,6}, A = {i A
K1: The union of E1, E2, E3, E4, and the concepts calculated in the dispatcher is the set of all concepts corresponding to the context C.
A major problem for the final efficiency of SD-ELL is the storage of the collection of
the closed produced, presumably very large and of unknown size. Our tool is a
Scalable Distributed Data Structure (SDDS). An SDDS dynamically distributes over
the (server) nodes whose number dynamically scales with the file growth. The
application accesses the file through the client nodes making the data distribution
transparent. For scalability, the data address calculations do not involve any
centralized directory. The data are also basically stored in the distributed RAM, for
faster access than to the traditional disk-based structures [
Our first architecture for SD-ELL, illustrated below, calculus is to add to the SDDS structure of clients and servers, a dispatcher and our applications at each available client site. The dispatcher executes the first algorithm of SD-ELL. It then sends to the applications the parameters Ki and Xi. In parallel, on each client the iterative version is executed with its parameters. We obtain the closed itemsets that after the calculus partition the Galois lattice. The closed sets are sent by the clients to the servers, where they are saved.
K1, X1
Application I-ELL(K1,X1) E1
Client
E1
Dispatcher (KCompute)
Ki, Xi
Application I-ELL(Ki,Xi) Ei
Client
E i
Kn, Xn
Application I-ELL(Kn,Xn) En
Client
En Server
Server
Server
Server Name Buckets in RAM
Buckets in RAM
Buckets in RAM The dispatcher is a centralized component. To offset the potential drawbacks of this approach, we have designed also a more distributive solution. The dispatcher calculates only the set K1 and K2 (K1=K0\A and K2 =K0\R) and sends them to two applications. These applications become dispatchers on there turn. They send to other applications the parameters Ki and Xi if Ki is greater than a fixed threshold and there are available machines.
We will first implement and measure the 1st solution. Later we will also design the end one and compare the related trade-offs.
Our preliminary experimentations has shown that the processing time of the distributed SD-ELL algorithm out performs the processing time of the ELL algorithm. Besides, increasing the number of processors improves the processing time.
In [
By another way, [
In this paper, we propose a new algorithm (SD-ELL) which is a distributed version of
ELL, in order to deal with large databases. The architecture used for this distribution
allows to share the computation of closed sets of large databases on the different
applications and to store them in the server nodes. The storage of the great number of
closed sets is successful since the number of server nodes dynamically scales with the
growth of the closed itemsets file. Our ongoing research consists in continuing the
evaluating of the prototype performance measurements. A possible future research
direction consists in determining the links between the concepts and then comparing
our results with the results of [
We would like to express special thanks to Pr. Witold Litwin for his precious remarks and his help for using the SDDS.