An Algorithm using Context Reduction for Efficient Incremental Generation of Concept Set

• Autorzy: Kovács László

Identyfikatory

DOI

10.3233/FI-2019-1776

• Języki publikacji: EN

Abstrakty

EN

The theory of Formal Concept Analysis (FCA) provides efficient methods for conceptualization of formal contexts. The methods of FCA are applied mainly on the field of knowledge engineering and data mining. The key element in FCA applications is the generation of a concept set. The main goal of this research work is to develop an efficient incremental method for the construction of concept sets. The incremental construction method is used for problems where context may change dynamically. The paper first proposes a novel incremental concept set construction algorithm called ALINC, where the insertion loop runs over the attribute set. The combination of object-level context processing and ALINC is an object level incremental algorithm (OALINC) where the context is built up object by object. Based on the performed tests, OALINC dominates the other popular batch or incremental methods for sparse contexts. For dense contexts, the OINCLOSE method, which uses the InClose algorithm for processing of reduced contexts, provides a superior efficiency. Regarding the OALINC/OINCLOSE algorithms, our test results with uniform distribution and real data sets show that our method provides very good performance in the full investigated parameter range. Especially good results are experienced for symmetric contexts in the case of word clustering using context-based similarity.

Słowa kluczowe

EN

concept set; FCA; formal concept analysis; InClose method; incremental concept set generation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 165, nr 1
• Strony: 43--73
• Opis fizyczny: Bibliogr. 41 poz., rys., tab., wykr.

Twórcy

autor

Kovács László

• Department of Information Technology, University of Miskolc, Miskolc-Egyetemvaros, H-3515, Hungary

Bibliografia

• [1] Andrews S. In-close, a fast algorithm for computing formal concept, International Conference on Conceptual Structures (ICCS), Moscow, 2009 pp. 1-14. URL http://shura.shu.ac.uk/id/eprint/38.
• [2] Andrews S. In-Close2, a High Performance Formal Concept Miner, Proceedings of Conference on Conceptual Structures, ICSS 2011, 2011 pp. 50-56. doi:10.1007/978-3-642-22688-5_4.
• [3] Beydoun G. Formal concept analysis for an e-learning semantic web, Expert Systems with Applications, 2009;36(8):10952-10961. URL http://dx.doi.org/10.1016/j.eswa.2009.02.023.
• [4] Birkhoff G. Lattice Theory, Amer. Math. Soc. Coll. Pub., Vol 25, 1940.
• [5] Bordat J. Calcul Pratique du Treillis de Galois d’une Correspondance, Mathmatiques et Sciences Humaines, 1986;96:31-47.
• [6] Carpineto C, Romano G. A Lattice Conceptual Clustering System and Its application to Browsing Retrieval, Machine Learning, 1996;24(2):95-122. doi:10.1023/A:1018050230279.
• [7] Cimiano P. Conceptual Knowledge Processing with Formal Concept Analysis and Ontologies, Concept Lattices: Second International Conference on Formal Analysis, IFCIA, 2004. doi:10.1007/978-3-540-24651-0_18.
• [8] Codocedo V, Napoli A. Formal Concept Analysis and Information Retrieval A Survey, ICFCA 2015. Lecture Notes in Computer Science, vol. 9113, 2015 pp. 61-77. doi:10.1007/978-3-319-19545-2_4.
• [9] Ferre S. Incremental Concept Formation made more efficient by the use of Associative Concepts, INRIA Research Report no 4569, 2002. URL https://hal.inria.fr/inria-00072019.
• [10] Ferre S, Ridoux O. The use of associative concepts in the incremental building of a logical context, Proceedings of Conf. Conceptual Structures. ICCS, vol. 2393, 2002 pp. 299-313. doi:10.1007/3-540-45483-7_23.
• [11] Ganter B, Kuznetsov S. Formalizing hypotheses with concepts, Proceedings of Conceptual Structures, vol. 1867, 2000 pp. 342-355. doi:10.1007/10722280_24.
• [12] Ganter B, Wille R. Formal Concept Analysis: Mathematical Foundation, Springer, Heidelberg, New York, 1999. ISBN 978-3-540-62771-5.
• [13] Godin R, Missaoui R, Alaoui H. Learning Algorithms Using a Galois Lattice Structure, Proceedings of the Third International Conference on Tools for Artificial Intelligence, S. Lee, B. Wah, N. G. Bourbakis, W. T. Tsai (Ed.), San Jose, Calif.: IEEE Computer Society Press, 1991 pp. 22-29. doi:10.1109/TAI.1991.167072.
• [14] Godin R, Missaoui R, Alaoui H. Incremental concept formation algorithms based on Galois (concept) lattices, Computer Intelligence, 1995;11(2):246-267. URL https://doi.org/10.1111/j.1467-8640.1995.tb00031.x.
• [15] Ignatov, D.: Introduction to formal concept analysis and its applications in information retrieval and related fields, Russian Summer School in Information Retrieval, 2014, 42-141.
• [16] Kaytoue M, Kuznetsov S, Napoli A, Duplessis S. Mining gene expression data with pattern structures in formal concept analysis, Information Sciences, 2011;181(10):1989-2001. URL https://doi.org/10.1016/j.ins.2010.07.007.
• [17] Korei A, Radeleczki S. Box elements in concept lattices, Contributions to ICFCA 2006, 4-th International Conference on Formal Concept Analysis. 2006 pp. 41-55.
• [18] Kouriea DG, Obiedkovab S, Watsona BW, van der Merwe D. An incremental algorithm to construct a lattice of set intersections, Science of Computer Programming, 2009;74:128-142. URL https://doi.org/10.1016/j.scico.2008.09.015.
• [19] Krajca P, Outrata J, Vychodil V. Parallel Recursive Algorithm for FCA, Proceeding of the Sixth International Conference on Concept Lattices and their Applications, 2008, pp. 71-82.
• [20] Krajca P, Outrata J, Vychodil V. Advances in algorithms based on CbO, Proceedings of CLA. 2010 pp. 325-337.
• [21] Kriegel F, Borchmann D. Next Closures: Parallel Computation of the Canonical Base, Proceedings of CLA, 2015 pp. 181-192.
• [22] Kuznetsov S. Learning of Simple Conceptual Graphs from Positive and Negative Examples, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, vol. 1704, 1999 pp. 384-391. doi:10.1007/978-3-540-48247-5_47.
• [23] Kuznetsov S. Machine learning and formal concept analysis, Lecture Notes in Computer Science LNCS vol. 2961, Springer, 2004 pp. 287-312. doi:10.1007/978-3-540-24651-0_25.
• [24] Kuznetsov S, Obiedkov S. Comparing performance of algorithms for generating concept lattices, Journal of Experimentation and Theoretical Articial Intelligence, 2002;14(2):189-216. doi:10.1080/09528130210164170.
• [25] Li J, He Z, Zhu Q. An Entropy-Based Weighted Concept Lattice for Merging Multi-Source Geo-Ontologies, Entropy, 2013;15:2303-2318; doi:10.3390/e15062303.
• [26] Makhalova T, Kuznetsov S. On Overfitting of Classifiers Making a Lattice, ICFCA, vol. 10308, 2017 pp. 184-197. doi:10.1007/978-3-319-59271-8_12.
• [27] Merwe D, Obiedkov S, Kourie D. AddIntent: A new incremental algorithm for constructing concept lattices, Proceedings of P.W. Eklund(Ed.), ICFCA Concept Lattices, Sydney, Australia, LNCS vol. 2961, 2004 pp. 372-385. doi:10.1007/978-3-540-24651-0_31.
• [28] Norris EM. An Algorithm for Computing the Maximal Rectangles in a Binary Relation, Revue Roumaine de Mathmatiques Pures et Appliques, 1978;23(2):243-250.
• [29] Nourine L, Raynaud O. A fast algorithm for building lattices, Information Processing Letters, 1999;71(5-6):199-204. URL https://doi.org/10.1016/S0020-0190(99)00108-8.
• [30] Outrata J. A lattice-free concept lattice update algorithm based on *CbO*, CLA 2013, 2013 pp. 261-274.
• [31] Outrata J, Vychodil V. Fast algorithm for computing xpoints of Galois connections induced by object-attribute relational data, Information Sciences 2012;185(1):114-127. URL https://doi.org/10.1016/j.ins.2011.09.023.
• [32] Oystein O. Galois Connexions, Transactions of the American Mathematical Society 1944;55:493-513.
• [33] Piskov L, Horvth T. Comparing Performance of Formal Concept Analysis and Closed Frequent Itemset Mining Algorithms on Real Data, Proceedings of CLA, 2013 pp. 299-304.
• [34] Piskova L, Horvath T. Comparing Performance of Formal Concept Analysis and Closed Frequent Itemset Mining Algorithms on Real Data, Proceedings of CLA, 2013 pp. 299-308.
• [35] Stumme G, Maedche A. FCA-Merge: Bottom-up merging of ontologies, IJCAI, vol. 1, 2001 pp. 225-230. ISBN: 1-55860-812-5 978-1-558-60812-2.
• [36] Szathmary L, Valtchev P, Napoli A, Godin R, Boc A, Makarenkov V. Fast Mining of Iceberg Lattices: A Modular Approach Using Generators, Proc of The Eighth International Conference on Concept Lattices and Their Applications, 2011 pp. 191-206. URL https://hal.inria.fr/hal-00640898.
• [37] Tilley T, et al. A survey of formal concept analysis support for software engineering activities, Formal concept analysis, LNCS vol. 3626, 2005 pp. 250-271. doi:10.1007/11528784_13.
• [38] Valtchev P, Missaoui R. Generating frequent item sets incrementally: Two novel approaches based on Galois lattice theory, Journal of Experimental and Theoretical Artificial Intelligence, 2002;14(2-3):115-142. URL https://doi.org/10.1080/09528130210164198.
• [39] Wille R. Restructuring lattice theory: An approach based on hierarchies of concepts, In: Rival I. (eds) Ordered Sets, NATO Advanced Study Institutes Series, Springer, vol. 83, 1982. doi:10.1007/978-94-009-7798-3_15.
• [40] Zhao Y, Yao Y. Classification based on logical concept analysis, Proc. of Computational Studies of Intelligence, LNCS vol. 4013, 2006, pp. 419-430. doi:10.1007/11766247_36.
• [41] Zou L, Zhang Z, Long J. A fast incremental algorithm for constructing concept lattices, Expert Systems with Applications, 2015;42(1):4474-4481. URL https://doi.org/10.1016/j.eswa.2015.01.044.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).