Classical algorithms for generating the concept lattice (C; ) of a binary table (O; I; R) have a complexity in O(jCj jIj2 jOj). Although the number of concepts is exponential in the size of the table in the worst case, the generation of a concept is output polynomial. In practice, the number of concepts is often polynomial in the size of the table. However, the cost of generating a concept remains high when the table is composed of a large number of objects. We propose in this paper an algorithm for generating the lattice with limited object access, which can improve the computation time. Experiments were conducted with Joomla!, a content management system based on relational algebra, and located on a MySQL database.
Galois lattices (or concept lattices) were rst introduced in a formal way in the
graph and ordered structures theory [1{3]. Later, they were developed in the eld
of Formal Concept Analysis (FCA) [
Galois lattice is a graph providing a representation of all the possible correspondences between a set of objects (or examples) O and a set of attributes (or features) I. The technological improvements of the last decades enable use of these structures for data mining problems though they are exponential in space/time (worst case). It has to be noted that in practice, in most cases, the size of the lattice remains reasonable.
In addition, some applications o er to only generate some concepts from
the huge amount of available data. Bordat's algorithm [
In this paper, we propose the Limited Object Access algorithm (LOA algorithm), an extension of Bordat's immediate successors generation with a limited access to objects. This algorithm, compounded with an on-demand strategy, and with sophisticated key-indexation techniques to improve objects's access, aims to improve time computation for a large amount of objects. However, worst case theoretical complexity remains the same as Bordat's algorithm. Experiments were conducted with Joomla!, a content management system based on relational algebra, and located on a MySQL database.
This paper is organized as follows. In section 2, we describe the Galois lattice structure and the Bordat's generation algorithm. In section 3, we describe our limited object access algorithm, illustrated by an example and some experiments. 2 2.1
Description and generation of a concept lattice
The concept lattice is a particular graph de ned and generated from a relation R
between objects O and attributes I. This graph is composed of a set of concepts
ordered by a relation verifying the properties of a lattice, i.e. an order relation
(transitive, re exive and antisymmetric relation) such that, for each pair of
concepts in the graph, there exists both a lower bound and an upper bound.
Therefore, a lattice contains a minimum (resp. maximum) element according to
the relation called the bottom (resp. top) of the lattice. The Hasse diagram of
a graph [
We associate to a set of objects A O the set f (A) of attributes in relation R with the objects of A:
f (A) = fy 2 I j xRy 8 x 2 Ag
with the attributes of B:
g(B) = fx 2 O j xRy 8 y 2 Bg These two functions f and g de ned between objects and attributes form a Galois correspondence. The relation between the set of objects and the set of attributes is described by a formal context. A formal context C is a triplet C = (O; I; R) (or C = (O; I; (f; g))) represented by a table.
A formal concept represents maximal objects-attributes correspondences (following relation R) by a pair (A; B) with A O and B I, which veri es f (A) = B and g(B) = A. The whole set of formal concepts thus corresponds to all the possible maximal correspondences between a set of objects O and a set of attributes I.
Two formal concepts (A1; B1) and (A2; B2) are in relation in the lattice when they verify the following inclusion property:
The whole set of formal concepts tted out by the order relation is called concept lattice or Galois lattice because it veri es the lattice properties: the relation is clearly an order relation, and for each pair of concepts (A1; B1) and (A2; B2), there exists the greatest lower bound (resp. the least upper bound) called meet (resp. join) denoted (A1; B1) ^ (A2; B2) (resp. (A1; B1) _ (A2; B2)) de ned by: (A1; B1) ^ (A2; B2) = (g(B1 \ B2); (B1 \ B2)) (A1; B1) _ (A2; B2) = ((A1 \ A2); f (A1 \ A2)) (1) (2) The concepts ? = (O; f (O)) and > = (g(I); I) respectively correspond to the bottom and the top of the concept lattice.
In formal concept analysis (FCA) concept lattices are used to analyse data
when organised by a binary relation between objects and attributes. See the
book of Ganter and Wille [
In the following, we abuse notation and use X + x (respectively, X n x) for X [ fxg (respectively, Xnfxg). 2.2
Numerous generation algorithms for concept lattices have been proposed in
literature [
All of these proposed algorithms have a polynomial complexity with respect
to the number of concepts (at best quadratic in [
Some applications o er to only generate some concepts from the huge amount
of available data. Bordat's algorithm [
FA = fg(x + B) : x 2 InBg
(3)
Corollary 2 (Bordat [
Bordat's algorithm recursively computes all the concepts of C by computing immediate successors for each concept (A; B), starting from the bottom concept ? = (f (G); G), until all concepts are generated. Immediate successors are generated using Corollary 2 in O(jIj2 jOj): the set system has rst to be generated in a linear time ; then inclusion-maximal subsets of FB, can easily be computed in O(jIj2 jOj). 3 3.1
Limited Object Access Algorithm (LOA)
Large data are often described by a huge amount of objects, as in databases for example where the number of recordings (i.e. objects) can be huge, indexed using sophisticated key-indexation techniques. In this section, we describe our Limited Object Access algorithm (LOA algorithm), an extension of Bordat's immediate successors generation with a limited object access. This algorithm, compounded with an on-demand strategy aims to improve time computation for large amount of objects.
Our algorithm considers the restriction of a concept lattice to the attributes. A nice result establishes that any concept lattice (C; C ) is isomorphic to the lattice (CI ; ) de ned on the set I of attributes, with CI the restriction of C to the attributes in each concept. The lattice (CI ; ) is also known as the closed sets lattice on the attributes I of a context (O; I; R), where the set system CI is composed of all closed set - i.e. xed points - for the closure operator ' = g f . See the survey of Caspard and Monjardet [12] for more details about closed set lattices.
Using the closed sets lattice (CI ; ) instead of the whole concept lattice (C; C ) gives raise to a storage improvement, for example in case of large amount of objects.
A closed sets lattice can be generated using an algorithm similar to Bordat's algorithm, and therefore enabling an on-demand generation in order to reduce the whole amount of closed sets. This algorithm (see Alg. 1) recursively computes immediate successors (see Alg. 2) of a closed set B, starting from the bottom closed set ? = '(;), until I is generated.
The Immediates Successors LOA algorithm we propose (see Alg. 3)
reinforces the object access limitation by considering the cardinality of the subset
g(X + B) instead of the subset itself to compute the inclusion-maximal subsets
of FA using the following property:
1 In [
More precisely, the Immediates Successors LOA algorithm (see Alg. 3) rst initialize the set Succ of immediate successors of a closed set B with the emptyset. The set Succ is then updated by considering each attribute x of InB and another already inserted potential successor X InB by considering the following four cases, where cB(Y ) denotes the cardinality of g(B + Y ) for a Y of attributes: Merge x with X: When g(x + B) = g(X + B), then x and X belongs to the same closed set, and thus have to be merged in a same potential successor of B. By Proposition 3, this case is tested by cB(X + x) = cB(X) and cB(X) = cB(x).
Eliminate X: When g(X + B) g(x + B), then the closed set containing X isn't inclusion-maximal in FA, and thus hasn't to be considered as a potential successor of B. By Proposition 3, this case is tested by cB(X + x) = cB(X) and cB(X) < cB(x).
Eliminate x: When g(x + B) g(X + B), then the closed set containing x isn't inclusion-maximal if FA, and thus hasn't to be considered as a potential successor of B. By Proposition 3, this case is tested by cB(X + x) = cB(X) and cB(x) < cB(X).
Insert x: When x is neither eliminated or merged with X, then it is added as a potential successor of B ; another attribute is then considered. 3.2
To illustrate our algorithm, we use the following context where numbers from 1 to 9 are described by some properties: the number is a prime number, an odd or even number, a square, a composite number or a factorial number.
(p)rime o(dd) (e)ven (s)quare (c)omposite (f)actorial Name: Closed Set Lattice Data: A context K = (O; I; R) Result: The Hasse diagram (CI ; ) of the lattice (CI ; ) begin
CI = ff (O)g; foreach B 2 CI not marked do
SuccB=Immediates successors (K; B); foreach X 2 SuccB do
B0 = B + X; if B0 62 CI then add B0 to CI ; add a cover relation B B0 end mark B end return (CI ; ) end Algorithm 1: Generation of the Hasse diagram of the closed set lattice (CI ; ) Name: Immediates Successors Data: A context K ; A closed set B of the closed set lattice (CI ; ) of K Result: The immediate successors of B in the lattice begin initialize the set system FA with ;; foreach x 2 InB do
add g(x + B) to FA end Succ=maximal inclusion subsets of FA; return Succ end Algorithm 2: Generation of the immediate successors of a closed set in the Hasse diagram of the lattice (CI ; )
Name: Immediates Successors LOA Data: A context K ; A closed set B of the closed set lattice (CI ; ) of K Result: The immediate successors of B in the lattice begin initialize the SuccB family to an empty set; foreach x 2 I n B do add = true; foreach X 2 SuccB do nn Merge x and X in the same potential successor if cB(x) = cB(X) then if cB(X + x) = cB(x) then replace X by X + x in SuccB; add=false; break; end end end nn Eliminate x as potential successor if cB(x) < cB(X) then if cB(X + x) = cB(x) then
add=false; break; end nn Eliminate X as potential successor if cB(x) > cB(X) then if cB(X + x) = cB(X) then
delete X from SuccB end end end nn Insert x as a new potential successor ; if add then add fxg to SuccB end return SuccB; end Algorithm 3: Generation of the immediate successors of a closed set in the Hasse diagram of the lattice (CI ; ) The complexity of computing the immediate successors of a closed set B using the Immediates Successors LOA algorithm is: (jIj jBj)(jIj 2 jBj)
O(cB(X)) SuccF ; f[o]g f[o]; [e]g f[o]; [e]g f[o]; [e]g f[o]; [e]g f[o]; [ef]g using the big O notation.
This has to be compared with O(jIj2 jOj) of the Immediates Successors algorithm. In addition the cost O(CB(x)) of computing the cardinality of objects satisfying the required properties can be based on multiple keys and robust algorithms used in databases that do not need to load all data for computing a cardinality. 54 attributes: the 6 attributes of the example, and attributes corresponding to the property to be multiple of f3 50g. 100000 objects: the integers between 1 and 100000
The dataset is stored in a database MySQL 5.5.14. We have implemented our Immediates Successors LOA algorithm using PhP 5.3.6. The counting of objects satisfying a set of properties is realised by the SQL request comparing indexes with a constant: select count (*) from att1=1 and att2=1
We compare the processing time of our Immediates Successors LOA algorithm in the two following cases: Indexed: Each attribute is de ned to be an index. Objects are indexed by their attributes, and MySQL can quickly retrieve them in the dataset using a Btree indexation with a logarithmic complexity [13]: O(cB(X)) = O(logjIj). Not indexed: Objects are not indexed and a scan of all the lines is necessary to retrieve objects. The complexity is then similar to those of the Immediates Successors algorithm: O(cB(X)) = O(jIj jBj).
We compare the processing time of computing the immediate successors of the botom element ; in this two cases (indexed and not indexed): (a) 100000 rst integers as objects ; a number of attributes between 6 to 54.
(b) 54 attributes ; integers between 1000 and 100000 In the results, the time processing is really improved with an indexed dataset, and seems to be near to linear in O(jIj + jOj). Immediate successors of the ; for 100000 objects and 54 attributes are computed in 3 seconds with the indexed algorithm, and in 18 seconds with the not indexed one.
Moreover, the explain of the count operation shows that an index-merge operation is realized on indexes corresponding to an intersect computation: mysql> explain select count(*) from numbers where p=1 and o=1; +----+-------------+------+---------+------+-----------------------+ | id | select_type | key | key_len | rows | Extra | +----+-------------+------+---------+------+-----------------------+ | 1 | index_merge | p,o | 1,1 | 2 | Using intersect(p,o); | | | | | | | Using where; | | | | | | | Using index | +----+-------------+------+---------+------+-----------------------+ 1 row in set (0.00 sec)
Therefore, optimizing the intersection operation, with an adaptated sort on the lines for example, would be a possible optimization of our algorithm. 4
Conclusion In this paper, we described a new algorithm for computing the immediate successors of a concept using the counting of objects satisfying a set of properties. By separating the counting from the rest of the algorithm, new systems for exploring concept lattices can now rely on optimization algorithms used in relational databases. If the tests we will realize on PostgreSQL and MySQL databases are successfull in terms of manipulating a huge amounts of data, we plan to propose a library for extending content management system such as Joomla!. 10. Gely, A.: A generic algorithm for generating closed sets of binary relation. Third International Conference on Formal Concept Analysis (ICFCA 2005) (2005) 223{ 234 11. Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. Journal of Experimental and Theorical Arti cial Intelligence 14 (2002) 189{216 12. Caspard, N., Monjardet, B.: The lattice of closure systems, closure operators and implicational systems on a nite set: a survey. Discrete Applied Mathematics 127 (2003) 241{269 13. Bayer, R. et McCreight, E.M.: Organization and maintenance of large ordered indexes. Acta Informatica 1 (1972) 173{189