×

A ‘best-of-breed’ approach for designing a fast algorithm for computing fixpoints of Galois connections. (English) Zbl 1360.68797

Summary: 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.

MSC:

68T30 Knowledge representation
06A15 Galois correspondences, closure operators (in relation to ordered sets)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[2] Andrews, S., In-close2, a high performance formal concept miner, (Andrews, S.; Polovina, S.; Hill, R.; Akhgar, B., Conceptual Structures for Discovering Knowledge - Proceedings of the 19th International Conference on Conceptual Structures (ICCS) (2011), Springer), 50-62
[6] Andrews, S.; Orphanides, C., Fcabedrock, a formal context creator, (Croitoru, M.; Ferre, S.; Lukose, D., ICCS 2010. ICCS 2010, LNCS, vol. 6208/2010 (2010), Springer)
[8] Bordat, J. P., Calcul pratique du treillis de Galois dune correspondance, Math. Sci. Hum., 96, 31-47 (1986) · Zbl 0626.06007
[9] Carpineto, C.; Romano, G., Concept Data Analysis: Theory and Applications (2004), J. Wiley · Zbl 1083.68117
[10] Chein, M., Algorithme de recherche des sous-matrices premires dune matrice, Bull. Math. Soc. Sci. Math. R.S. Roumanie, 13, 21-25 (1969) · Zbl 0209.06401
[13] Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundations (1998), Springer-Verlag
[14] Godin, R.; Missaoui, R.; Alaoui, H., Incremental concept formation algorithms based on Galois lattices, Comput. Intell., 11, 2, 246-267 (1995)
[16] Kaytoue, M.; Kuznetsov, S. O.; Napoli, A.; Duplessis, S., Mining gene expression data with pattern structures in formal concept analysis, Inf. Sci., 181, 10, 1989-2001 (2011)
[17] Kirchberg, M.; Leonardi, E.; Tan, Y. S.; Link, S.; Ko, R. K.L.; Lee, B. S., Formal concept discovery in semantic web data, (LNAI, vol. 7278 (2012), Springer-Verlag: Springer-Verlag Berlin Heidelberg)
[22] Kuznetsov, S., Learning of simple conceptual graphs from positive and negative examples, (Zytkow, J.; Rauch, J., PKDD’99. PKDD’99, Lecture Notes in Computer Science, vol. 1704 (1999), Springer), 384-391
[23] Kuznetsov, S.; Obiedkov, S., Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell., 14, 189-216 (2002) · Zbl 1024.68020
[24] Kuznetsov, S. O., Mathematical aspects of concept analysis, Math. Sci., 80, 2, 1654-1698 (1996) · Zbl 0885.06001
[25] Kuznetsov, S. O., On computing the size of a lattice and related decision problems, Order, 18, 4, 313-321 (2001) · Zbl 0991.06006
[26] Lindig, C., Fast concept analysis, (Working with Conceptual Structures: Contributions to ICCS 2000 (2000), Shaker Verlag: Shaker Verlag Aachen), 152-161
[27] Norris, E., Maximal rectangular relations, (Proceedings of the 1st Conference on Fundamentals of Computing Theory. Proceedings of the 1st Conference on Fundamentals of Computing Theory, Lecture Notes in Computer Science, vol. 56 (1977), Springer), 476-481 · Zbl 0373.92012
[28] Nourine, L.; Raynaud, O., A fast algorithm for building lattices, Inf. Process. Lett., 71, 199-204 (1999) · Zbl 0998.06005
[29] Outrata, J.; Vychodil, V., Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data, Inf. Sci., 185, 1, 114-127 (2012) · Zbl 1239.68070
[31] Tanabata, T.; Sawase, K.; Nobuhara, H.; Bede, B., Interactive data mining for image databases based on FCA, J. Adv. Comput. Intell. Intell. Inf., 14, 3, 303-308 (2010)
[32] Van der Merwe, D.; Obiedkov, S.; Kourie, D., Addintent: a new incremental algorithm for constructing concept lattices, (Eklund, P., ICFCA 2004. ICFCA 2004, Lecture Notes in Computer Science, vol. 2961 (2004), Springer), 372-385 · Zbl 1198.68251
[33] Wolff, K. E., A first course in formal concept analysis: how to understand line diagrams, Adv. Stat. Software, 4, 429-438 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.