Faster Algorithms for Constructing a Concept (Galois) Lattice - Clustering Challenges in Biological Network - page 181

second for the program to produce the concept lattice (about 530 vertices/concepts
and 1500 edges) in a Pentium IV 3.0GHz computer with 2G memory running
under Fedora 2 linux OS.
As FCA finds more and more applications, especially in bioinformatics, ef-
ficient algorithms for constructing concept/Galois lattices are much needed. Our
algorithm is faster than the existing algorithms for this problem, nevertheless, it
seems to have much room to improve. Furthermore, our algorithm can be eas-
ily modified to compute the minimal generators for redescription mining [38] di-
rectly.

Acknowledgment

We would like to thank Reinhard Laubenbacher for introducing us FCA. We thank
Naren Ramakrishnan for the discussion about redescription mining.

References

[1] J. Abello, A. Pogel, L. Miller. Breadth first search graph partitions and concept lat-

tices. J. of Universal Computer Science , 10(8), p934-954, 2004.

[2] F. Afrati, A. Gionis, H. Mannila. Approximating a collection of frequent sets. Proc.

10th ACM SIGKDD International Conference on Knowledge Discovery and Data
mining , p12-19, 2004.

[3] F. Baklouti, R.E. Grarvy. A fast and general algorithm for Galois lattices building. J.

of Symbolic Data Analysis , 3(1), p19-31, 2005. www.icons.rodan.pl/publications/

[4] M. Barbut and B. Montjardet. Ordre et Classifications: Algebre et combinatoire. Ha-

chette, 1970.

[5] J. Besson, C. Robardet, J-F. Boulicaut. Constraint-based mining of formal concepts

in transactional data. Proceedings of the 8th Pacific-Asia Conference on Knowledge
Discovery and Data Mining PaKDD04 , 2004. Springer-Verlag LNCS 3056, pp. 615-
624.

[6] E. Boros, V. Gurvich, L. Khachiyan, K. Makino. On maximal frequent and minimal

infrequent sets in binary matrices. Annals of Mathematics and Artificial Intelligence ,
39, p211-221, 2003. (STACS 2002)

[7] T. Calders, C. Rigotti, J.F. Boulicaut. A survey on condensed representations for

frequent sets. Constrained-based Mining , Springer, 3848, 2005.

[8] V. Choi, Y. Huang, V. Lam, D. Potter, R. Laubenbacher, K. Duca. Using Formal

Concept Analysis for Microarray Data Comparison. DIMACS Workshop on Clus-
tering Problems in Biological Networks. Piscataway, New Jersey, May 9-11, 2006.
Manuscript in preparation.

[9] G. Cong, K.L. Tan, A.K.H. Tung, F. Pan. Mining frequent closed patterns in mi-

croarray data. Proc. 4th IEEE International Conference on Data Mining , p363-366,
2004.