×

Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data. (English) Zbl 1239.68070

Summary: Fixpoints of Galois connections induced by object-attribute data tables represent important patterns that can be found in relational data. Such patterns are used in several data mining disciplines including formal concept analysis, frequent itemset and association rule mining, and Boolean factor analysis. In this paper we propose efficient algorithm for listing all fixpoints of Galois connections induced by object-attribute data. The algorithm, called FCbO, results as a modification of Kuznetsov’s CbO in which we use more efficient canonicity test. We describe the algorithm, prove its correctness, discuss efficiency issues, and present an experimental evaluation of its performance and comparison with other algorithms.

MSC:

68T30 Knowledge representation
68T05 Learning and adaptive systems in artificial intelligence
06A15 Galois correspondences, closure operators (in relation to ordered sets)

Software:

FCALGS; UCI-ml; AddIntent
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Agrawal, T. Imielinski, A.N. Swami, Mining association rules between sets of items in large databases, in: Proceedings of the ACM International Conference of Management of Data, 1993, pp. 207-216.; R. Agrawal, T. Imielinski, A.N. Swami, Mining association rules between sets of items in large databases, in: Proceedings of the ACM International Conference of Management of Data, 1993, pp. 207-216.
[2] S. Andrews, In-Close, a Fast Algorithm for Computing Formal Concepts, in: S. Rudolph, F. Dau, S.O. Kuznetsov (Eds.): Supplementary Proceedings of ICCS ’09<http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-483/paper1.pdf>; S. Andrews, In-Close, a Fast Algorithm for Computing Formal Concepts, in: S. Rudolph, F. Dau, S.O. Kuznetsov (Eds.): Supplementary Proceedings of ICCS ’09<http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-483/paper1.pdf>
[3] Angiulli, F.; Cesario, E.; Pizzuti, C., Random walk biclustering for microarray data, Information Sciences, 178, 6, 1479-1497 (2008) · Zbl 1134.68052
[4] Asuncion, A.; Newman, D., UCI Machine Learning Repository (2007), University of California, Irvine, School of Information and Computer Sciences
[5] Belohlavek, R., Lattices of fixed points of fuzzy Galois connections, Math. Logic Quarterly, 47, 1, 111-116 (2001) · Zbl 0976.03025
[6] Belohlavek, R.; Sigmund, E.; Zacpal, J., Evaluation of IPAQ questionnaires supported by formal concept analysis, Inform. Sci., 181, 10, 1774-1786 (2011)
[7] Belohlavek, R.; Vychodil, V., Discovery of optimal factors in binary data via a novel method of matrix decomposition, J. Comput. Syst. Sci., 76, 1, 3-20 (2010) · Zbl 1180.15026
[8] Correia, J. H.; Stumme, G.; Wille, R.; Wille, U., Conceptual knowledge discovery - A human-centered approach, Appl. Artif. Intell., 17, 3, 281-302 (2003)
[9] B. Ganter, Two basic algorithms in concept analysis. (Technical Report FB4-Preprint No. 831). TH Darmstadt, 1984.; B. Ganter, Two basic algorithms in concept analysis. (Technical Report FB4-Preprint No. 831). TH Darmstadt, 1984. · Zbl 1274.68484
[10] Ganter, B.; Wille, R., Formal Concept Analysis. Formal Concept Analysis, Mathematical Foundations (1999), Springer: Springer Berlin · Zbl 0909.06001
[11] Goldberg, L. A., Efficient Algorithms for Listing Combinatorial Structures (1993), Cambridge University Press · Zbl 0821.68059
[12] Gratzer, G. A., General Lattice Theory (1998), Birkhauser
[13] S. Hettich, S.D. Bay, The UCI KDD Archive University of California, Irvine, School of Information and Computer Sciences, 1999.; S. Hettich, S.D. Bay, The UCI KDD Archive University of California, Irvine, School of Information and Computer Sciences, 1999.
[14] Johnson, D. S.; Yannakakis, M.; Papadimitriou, C. H., On generating all maximal independent sets, Inform. Process. Lett., 27, 3, 119-123 (1988) · Zbl 0654.68086
[15] Krajca, P.; Outrata, J.; Vychodil, V., Parallel algorithm for computing fixpoints of galois connections, Ann. Math. Artif. Intell., 59, 2, 257-272 (2010) · Zbl 1213.68604
[16] P. Krajca, J. Outrata, V. Vychodil, Advances in algorithms based on CbO, in: Proceedings of the CLA, 2010, pp. 325-337.; P. Krajca, J. Outrata, V. Vychodil, Advances in algorithms based on CbO, in: Proceedings of the CLA, 2010, pp. 325-337.
[17] P. Krajca, V. Vychodil, Comparison of data structures for computing formal concepts, in: Proc. MDAI, LNCS 5861, 2009, pp. 114-125.; P. Krajca, V. Vychodil, Comparison of data structures for computing formal concepts, in: Proc. MDAI, LNCS 5861, 2009, pp. 114-125. · Zbl 1273.68379
[18] Kuznetsov, S. O., Interpretation on graphs and complexity characteristics of a search for specific patterns, Automat. Document. Math. Linguist., 24, 1, 37-45 (1989) · Zbl 0737.68065
[19] Kuznetsov, S. O., A fast algorithm for computing all intersections of objects in a finite semi-lattice, Automat. Document. Math. Linguist., 27, 5, 11-21 (1993)
[20] Kuznetsov, S. O., On computing the size of a lattice and related decision problems, Order, 18, 313-321 (2001) · Zbl 0991.06006
[21] Kuznetsov, S. O., Learning of simple conceptual graphs from positive and negative examples, PKDD, 384-391 (1999)
[22] Kuznetsov, S. O.; Obiedkov, S. A., Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Int., 14, 189-216 (2002) · Zbl 1024.68020
[23] Kneale, W.; Kneale, M., The Development of Logic (1985), Oxford University Press: Oxford University Press USA · Zbl 0100.00807
[24] Lindig, C., Fast concept analysis. Fast concept analysis, Working with Conceptual Structures - Contributions to ICCS 2000 (2000), Shaker Verlag: Shaker Verlag Aachen
[25] Liu, H.; Wang, X.; He, J.; Han, J.; Xin, D.; Shao, Z., Top-down mining of frequent closed patterns from very high dimensional data, Inform. Sci., 179, 7, 899-924 (2009) · Zbl 1162.68561
[26] Medina, J.; Ojeda-Aciego, M., Multi-adjoint t-concept lattices, Inform. Sci., 180, 5, 712-725 (2010) · Zbl 1187.68587
[27] D. van der Merwe, S.A. Obiedkov, D.G. Kourie, AddIntent: A New Incremental Algorithm for Constructing Concept Lattices, in: Proceedings of the ICFCA 2004, LNAI 2961, 2004, pp. 205-206.; D. van der Merwe, S.A. Obiedkov, D.G. Kourie, AddIntent: A New Incremental Algorithm for Constructing Concept Lattices, in: Proceedings of the ICFCA 2004, LNAI 2961, 2004, pp. 205-206. · Zbl 1198.68251
[28] Miettinen, P.; Mielikäinen, T.; Gionis, A.; Das, G.; Mannila, H., The Discrete Basis Problem, PKDD (2006), Springer
[29] Mirkin, B., Mathematical Classification and Clustering (1996), Kluwer Academic Publishers · Zbl 0874.90198
[30] Norris, E. M., An algorithm for computing the maximal rectangles in a binary relation, Revue Roumaine de Mathématiques Pures et Appliquées, 23, 2, 243-250 (1978) · Zbl 0389.05003
[31] Snelting, G.; Tip, F., Reengineering class hierarchies using concept analysis, ACM Trans. Program. Lang. Syst., 22, 3, 540-582 (2000)
[32] Tonella, P., Using a concept lattice of decomposition slices for program understanding and impact analysis, IEEE Trans. Softw. Eng., 29, 6, 495-509 (2003)
[33] R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, Ordered Sets, Dordrecht-Boston, 1982, pp. 445-470.; R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, Ordered Sets, Dordrecht-Boston, 1982, pp. 445-470.
[34] Zaki, M. J., Mining non-redundant association rules, Data Min. Knowledge Discov., 9, 223-248 (2004)
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.