Abstract：As the data scale increases, the size of concept lattice grows exponentially. Effective concept lattice compression is a critical challenge in formal concept analysis. To compress concept lattices with their structure preserved, congruence relations on the lattice are utilized. First, the ↗ and ↙ relations in the original formal context are derived from attribute concepts and object concepts, respectively. Then, the initial sets of deletion attributes(objects) are defined, and by leveraging a pruning strategy, a compatible subcontext of the original formal context is obtained through arrow-closed relations. It is proven that when singleton sets of attributes(objects) are considered as the initial sets of deletion attributes(objects), compatible subcontexts with minimal information loss from the original formal context are obtained under arrow-closed relations. Consequently, compatible subcontexts with minimized information loss are utilized to determine congruence relations on the concept lattice, thereby compressing the concept lattice. Finally, an algorithm for determining congruence relations on concept lattice via compatible subcontexts is designed. Experiments validate the feasibility and effectiveness of the proposed algorithm.
[1] WILLE R.Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts // RIVAL I, ed. Ordered Sets. Berlin, Germany: Springer, 1982: 445-470. [2] GANTER B, WILLE R.Formal Concept Analysis: Mathematical Foun-dations. Berlin, Germany: Springer, 1999. [3] 胡可云,陆玉昌,石纯一.概念格及其应用进展.清华大学学报(自然科学版), 2000, 40(9): 77-81. (HU K Y, LU Y C, SHI C Y.Advances in Concept Lattice and Its Application. Journal of Tsinghua University(Science & Technology), 2000, 40(9): 77-81.) [4] ZOU C F, ZHANG D Q, WAN J F, et al. Using Concept Lattice for Personalized Recommendation System Design. IEEE Systems Journal, 2017, 11(1): 305-314. [5] NGUYEN P H P, CORBETT D. A Basic Mathematical Framework for Conceptual Graphs. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(2): 261-271. [6] 李金海,魏玲,张卓,等.概念格理论与方法及其研究展望.模式识别与人工智能, 2020, 33(7): 619-642. (LI J H, WEI L, ZHANG Z, et al. Concept Lattice Theory and Method and Their Research Prospect. Pattern Recognition and Artificial Intelligence, 2020, 33(7): 619-642.) [7] YAN H H, ZOU C F, LIU J Q, et al. Formal Concept Analysis and Concept Lattice: Perspectives and Challenges. International Journal of Autonomous and Adaptive Communications Systems, 2015, 8(1): 81-96. [8] WU W Z, LEUNG Y, MI J S.Granular Computing and Knowledge Reduction in Formal Contexts. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1461-1474. [9] 魏玲,李强.面向属性概念格基于覆盖的压缩.电子科技大学学报, 2012, 41(2): 299-304. (WEI L, LI Q.Covering-Based Reduction of Property-Oriented Concept Lattices. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 299-304.) [10] 何苗. 基于聚类思想的概念格压缩.陕西理工学院学报(自然科学版), 2016, 32(3): 78-82. (HE M.Concept Lattice Compression Based on Clustering. Journal of Shaanxi University of Technology(Natural Science Edition), 2016, 32(3): 78-82.) [11] LIN Y D, LI J J, TAN A H, et al. Granular Matrix-Based Know-ledge Reductions of Formal Fuzzy Contexts. International Journal of Machine Learning and Cybernetics, 2020, 11(3): 643-656. [12] KUZNETSOV S, OBIEDKOV S, ROTH C.Reducing the Representation Complexity of Lattice-Based Taxonomies // Proc of the 15th International Conference on Conceptual Structures. Berlin, Germany: Springer, 2007: 241-254. [13] 魏玲,赵思雨,祁建军.对称形式背景及其概念约简.西北大学学报(自然科学版), 2023, 53(5): 794-802. (WEI L, ZHAO S Y, QI J J.Symmetric Formal Context and Its Concept Reduct. Journal of Northwest University(Natural Science Edition), 2023, 53(5): 794-802.) [14] HAO F, GAO J, BISOGNI C.et al. Exploring Invariance of Concept Stability for Attribute Reduction in Three-Way Concept La-ttice. Soft Computing, 2023, 27(2): 723-735. [15] 马文胜,侯锡林.形式概念分析中的同效关系与概念约简.计算机科学, 2023, 50(4): 63-76. (MA W S, HOU X L.Same Effect Relation and Concept Reduction in Formal Concept Analysis. Computer Science, 2023, 50(4): 63-76.) [16] SNASEL V, ABDULLA H M D, POLOVINCAK M. Behavior of the Concept Lattice Reduction to Visualizing Data After Using Matrix Decompositions // Proc of the International Conference on Innovations in Information Technologies. Washington, USA: IEEE, 2007: 392-396. [17] CHEUNG K S K, VOGEL D. Complexity Reduction in Lattice-Based Information Retrieval. Information Retrieval, 2005, 8(2): 285-299. [18] DHILLON I S, MODHA D S.Concept Decompositions for Large Sparse Text Data Using Clustering. Machine Learning, 2001, 42(1/2): 143-175. [19] DOBŠA J, DALBELO-BAŠIĆ B. Comparison of Information Retrieval Techniques: Latent Semantic Indexing and Concept Indexing[J/OL].[2025-04-18]. https://hrcak.srce.hr/file/116419. [20] KUMAR C A, SRINIVAS S.Concept Lattice Reduction Using Fuzzy K-means Clustering. Expert Systems with Applications, 2010, 37(3): 2696-2704. [21] MAHONEY M W, DRINEAS P.CUR Matrix Decompositions for Improved Data Analysis. PNAS, 2009, 106(3): 697-702. [22] SUMANGALI K, KUMAR C A.Concept Lattice Simplification in Formal Concept Analysis Using Attribute Clustering. Journal of Ambient Intelligence and Humanized Computing, 2019, 10(6): 2327-2343. [23] DAVEY B A, PRIESTLEY H A. Introduction to Lattices and Order. 2nd Edition. Cambridge, UK: Cambridge University Press, 2002. [24] ZHANG W X, WEI L, QI J J.Attribute Reduction Theory and Approach to Concept Lattice. Science in China Series F(Information Sciences), 2005, 48(6): 713-726. [25] MA Y, LIU Z G, ZHANG X D.Granular Computing in Formal Concept // YAO J T, ed. Novel Developments in Granular Computing: Applications for Advanced Human Reasoning and Soft Computation. New York, USA: IGI Global, 2010: 370-407.
2025, Vol. 38 
