Computing Formal Concepts by Attribute Sorting

• Autorzy: Krajca P. , Outrata J. , Vychodil V.
• Języki publikacji: EN

Abstrakty

EN

We present a novel approach to compute formal concepts of formal context. In terms of operations with Boolean matrices, the presented algorithm computes all maximal rectangles of the input Boolean matrix which are full of 1s. The algorithm combines basic ideas of previous approaches with our recent observations on the influence of attribute permutations and attribute sorting on the number of formal concepts which are computed multiple times. As a result, we present algorithm which computes formal concepts by successive context reduction and attribute sorting. We prove its soundness, discuss its complexity and efficiency, and show that it outperforms other algorithms from the CbO family in terms of substantially lower numbers of formal concepts which are computed multiple times.

Słowa kluczowe

EN

compute formal concepts; formal contexts; formal concept analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 115, nr 4
• Strony: 395--417
• Opis fizyczny: Bibliogr. 29 poz., tab., wykr.

Twórcy

autor

Krajca P.

autor

Outrata J.

autor

Vychodil V.

• DAMOL: Data Analysis and Modeling Laboratory Department of Computer Science Palacky University, Olomouc, Czech Republic,

Bibliografia

• [1] Agrawal R., Imielinski T., Swami A. N.: Mining association rules between sets of items in large databases, Proc. ACM Int. Conf. of Management of Data, 1993, 207-216.
• [2] Andrews S.: In-Close, a Fast Algorithm for Computing Formal Concepts, Supplementary Proceedings of ICCS '09 (S. Rudolph, F. Dau, S. O. Kuznetsov, Eds.), CEUR WS, vol. 483, 2009.
• [3] Belohlavek R., Vychodil V.: Discovery of optimal factors in binary data via a novel method of matrix decomposition, J. Comput. Syst. Sci., 76(1), 2010, 3-20.
• [4] Carpineto C., Romano G.: Concept data analysis. Theory and applications, J. Wiley, 2004.
• [5] Hereth Correia J., Stumme G., Wille R., Wille U.: Conceptual knowledge discovery-a human-centered approach, Applied Artificial Intelligence, 17(3), 2003, 281-302.
• [6] Ganter B.: Two basic algorithms in concept analysis, Proc. ICFCA 2010, LNCS 5986, 2010, 312-340 (reprint of Technical Report FB4-Preprint No. 831, TH Darmstadt, 1984).
• [7] Ganter B., Wille R.: Formal concept analysis. Mathematical foundations, Springer, Berlin, 1999.
• [8] Goldberg L.A.: Efficient Algorithms for Listing Combinatorial Structures, Cambridge University Press, 1993.
• [9] Hettich S., Bay S.D.: The UCI KDD Archive, University of California, Irvine, School of Information and Computer Sciences, 1999.
• [10] Johnson D. S, YannakakisM., Papadimitriou C.H.: On generating all maximal independent sets, Information Processing Letters, 27(3), 1988, 119-123.
• [11] Koester B.: FooCA - Web Information Retrieval with Formal Concept Analysis, Verlag Allgemeine Wissenschaft, 2006.
• [12] Krajca P., Outrata J., Vychodil V.: Parallel algorithm for computing fixpoints of Galois connections, Ann. Math. Artif. Intell., 59(2), 2010, 257-272.
• [13] Krajca P., Outrata J., VychodilV.: Advances in algorithms based on CbO, Proc. CLA 2010 (M. Kryszkiewicz, S. Obiedkov, Eds.), CEURWS, vol. 672, 2010, 325-337 (http://ceur-ws.org/Vol-672/paper29.pdf).
• [14] Kuznetsov S.O.: Interpretation on graphs and complexity characteristics of a search for specific patterns, Automatic Documentation and Mathematical Linguistics, 24(1), 1989, 37-45.
• [15] Kuznetsov S.O.: A fast algorithm for computing all intersections of objects in a finite semi-lattice (Bystryi algoritm postroeni_ vseh pereseqenii obъektov iz koneqnoi polurexetki, in Russian), Automatic Documentation and Mathematical Linguistics, 27(5), 1993, 11-21.
• [16] Kuznetsov S.O.: Learning of Simple ConceptualGraphs fromPositive and Negative Examples. Proc. PKDD, 1999, 384-391.
• [17] Kuznetsov S.O., Obiedkov S.A.: Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Int., 14, 2002, 189-216.
• [18] Kneale W., Kneale M.: The Development of Logic, Oxford University Press, USA, 1985.
• [19] Lindig C.: Fast concept analysis. Working with Conceptual Structures-Contributions to ICCS, 2000, 152-161.
• [20] van derMerwe D., Obiedkov S.A., Kourie D.G.: AddIntent: A New IncrementalAlgorithmfor Constructing Concept Lattices. Proc. ICFCA 2004, LNAI 2961, 2004, 205-206.
• [21] Miettinen P., Mielikäinen T., Gionis A., Das G.,Mannila H.: The discrete basis problem. Proc. PKDD, 2006, 335-346.
• [22] 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), 1978, 243-250.
• [23] Outrata J., Vychodil V.: Fast algorithm for computing fixpoints of Galois connections induced by objectattribute relational data, Inf. Sci., doi:10.1016/j.ins.2011.09.023.
• [24] Pasquier N., Bastide Y., Taouil R., Lakhal L.: Efficient mining of association rules using closed itemset lattices, Inf. Syst., 24(1), 1999, 25-46.
• [25] Snelting G., Tip F.: Reengineering class hierarchies using concept analysis, ACM Transactions on Programming Languages and Systems, 22(3), 2000, 540-582.
• [26] Tonella P.: Using a concept lattice of decomposition slices for program understanding and impact analysis, IEEE Transactions on Software Engineering, 29(6), 2003, 495-509.
• [27] Wille R.: Restructuring lattice theory: an approach based on hierarchies of concepts. Ordered Sets, 1982, 445-470, Dordrecht-Boston.
• [28] Zaki M. J., Hsiao C.-J.: CHARM: An Efficient Algorithm for Closed ItemsetMining. Proc. SIAMDM, 2002.
• [29] Zaki M. J.: Mining non-redundant association rules, Data Mining and Knowledge Discovery, 9, 2004, 223-248.