Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Andrews, Simon (2015)
Publisher: Elsevier
Languages: English
Types: Article
The fixpoints of Galois Connections form patterns in binary relational data, such as object-attribute relations, that are important in a number of data analysis fields, including Formal Concept Analysis (FCA), Boolean factor analysis and frequent itemset mining. However, the large number of such fixpoints present in a typical dataset requires efficient computation to make analysis tractable, particularly since any particular fixpoint may be computed many times. Because they can be computed in a canonical order, testing the canonicity of fixpoints to avoid duplicates has proven to be a key factor in the design of efficient algorithms. The most efficient of these algorithms have been variants of the Close-By-One (CbO) algorithm. In this article, the algorithms CbO, FCbO, In-Close, In-Close2 and a new variant, In-Close3, are presented together for the first time, with in-Close2 and In-Close3 being the results of breeding In-Close with FCbO. To allow them to be easily compared, the algorithms are presented in the same style and notation. The important advances in CbO are described and compared graphically using a simple example. For the first time, the algorithms are implemented using the same structures and techniques to provide a level playing field for evaluation. Their performance is tested and compared using a range of data sets and the most important features identified for a CbO ‘Best-of-Breed’. This article also presents, for the first time, the ‘partial-closure’ canonicity test.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] S. Andrews, In-close, a fast algorithm for computing formal concepts, in: S. Rudolph, F. Dau, S.O. Kuznetsov, (Eds.), ICCS 2009, CEUR WS, vol. 483, 2009. .
    • [2] S. Andrews, In-close2, a high performance formal concept miner, in: S. Andrews, S. Polovina, R. Hill, B. Akhgar (Eds.), Conceptual Structures for Discovering Knowledge - Proceedings of the 19th International Conference on Conceptual Structures (ICCS), Springer, 2011, pp. 50-62.
    • [3] S. Andrews, Appendix to a Best of Breed Approach to Designing a Fast Algorithm for Computing Fixpoints of Galois Connections, 2013. .
    • [4] S. Andrews, In-Close Program, 2013. .
    • [5] S. Andrews, C. Orphanides, Analysis of large data sets using formal concept lattices, in: [21], 2010, pp. 104-115.
    • [6] S. Andrews, C. Orphanides, Fcabedrock, a formal context creator, in: M. Croitoru, S. Ferre, D. Lukose (Eds.), ICCS 2010, LNCS, vol. 6208/2010, Springer, 2010.
    • [7] D. Borchman, A generalized next-closure algorithm - enumerating semilattice elements from a generating set, in: L. Szathmary, U. Priss, (Eds.), Proceedings of Concept Lattices and thie Applications (CLA) 2012, Universidad de Malaga, 2012, pp. 9-20.
    • [8] J.P. Bordat, Calcul pratique du treillis de Galois dune correspondance, Math. Sci. Hum. 96 (1986) 31-47.
    • [9] C. Carpineto, G. Romano, Concept Data Analysis: Theory and Applications, J. Wiley, 2004.
    • [10] M. Chein, Algorithme de recherche des sous-matrices premires dune matrice, Bull. Math. Soc. Sci. Math. R.S. Roumanie 13 (1969) 21-25.
    • [11] A. Frank, A. Asuncion, UCI Machine Learning Repository, 2010. .
    • [12] B. Ganter, Two Basic Algorithms in Concept Analysis, FB4-Preprint 831, TH Darmstadt, 1984.
    • [13] B. Ganter, R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag, 1998.
    • [14] R. Godin, R. Missaoui, H. Alaoui, Incremental concept formation algorithms based on Galois lattices, Comput. Intell. 11 (2) (1995) 246-267.
    • [15] B. Goethals, Frequent Itemset Implementations (fimi) Repository, 2010. .
    • [16] M. Kaytoue, S.O. Kuznetsov, A. Napoli, S. Duplessis, Mining gene expression data with pattern structures in formal concept analysis, Inf. Sci. 181 (10) (2011) 1989-2001.
    • [17] M. Kirchberg, E. Leonardi, Y.S. Tan, S. Link, R.K.L. Ko, B.S. Lee, Formal concept discovery in semantic web data, LNAI, vol. 7278, Springer-Verlag, Berlin Heidelberg, 2012.
    • [18] P. Krajca, J. Outrata, V. Vychodil, Parallel recursive algorithm for FCA, in: R. Belohavlek, S. Kuznetsov, (Eds.), Proceedings of Concept Lattices and their Applications, 2008.
    • [19] P. Krajca, J. Outrata, V. Vychodil, FCbO Program, 2012. .
    • [20] P. Krajca, V. Vychodil, J. Outrata, Advances in Algorithms Based on CbO, In: [21], 2010, pp. 325-337.
    • [21] M. Kryszkiewicz, S. Obiedkov, (Eds.), Proceeding of 7th International Conference on Concept Lattices and Their Applications, CLA 2010, Seville, University of Sevilla, 2010.
    • [22] S. Kuznetsov, Learning of simple conceptual graphs from positive and negative examples, in: J. Zytkow, J. Rauch (Eds.), PKDD'99, Lecture Notes in Computer Science, vol. 1704, Springer, 1999, pp. 384-391.
    • [23] S. Kuznetsov, S. Obiedkov, Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell. 14 (2002) 189-216.
    • [24] S.O. Kuznetsov, Mathematical aspects of concept analysis, Math. Sci. 80 (2) (1996) 1654-1698.
    • [25] S.O. Kuznetsov, On computing the size of a lattice and related decision problems, Order 18 (4) (2001) 313-321.
    • [26] C. Lindig, Fast concept analysis, in: Working with Conceptual Structures: Contributions to ICCS 2000, Shaker Verlag, Aachen, 2000, pp. 152-161.
    • [27] E. Norris, Maximal rectangular relations, in: Proceedings of the 1st Conference on Fundamentals of Computing Theory, Lecture Notes in Computer Science, vol. 56, Springer, 1977, pp. 476-481.
    • [28] L. Nourine, O. Raynaud, A fast algorithm for building lattices, Inf. Process. Lett. 71 (1999) 199-204.
    • [29] J. Outrata, V. Vychodil, Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data, Inf. Sci. 185 (1) (2012) 114-127.
    • [30] F. Strok, A. Neznanov, Comparing and analyzing the computational complexity of fca algorithms, in: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists, 2010, pp. 417-420.
    • [31] T. Tanabata, K. Sawase, H. Nobuhara, B. Bede, Interactive data mining for image databases based on FCA, J. Adv. Comput. Intell. Intell. Inf. 14 (3) (2010) 303-308.
    • [32] D. Van der Merwe, S. Obiedkov, D. Kourie, Addintent: a new incremental algorithm for constructing concept lattices, in: P. Eklund (Ed.), ICFCA 2004, Lecture Notes in Computer Science, vol. 2961, Springer, 2004, pp. 372-385.
    • [33] K.E. Wolff, A first course in formal concept analysis: how to understand line diagrams, Adv. Stat. Software 4 (1993) 429-438.
  • No related research data.
  • No similar publications.
  • BioEntity Site Name

Share - Bookmark

Funded by projects


Cite this article