极小信息损失的兼容子背景获取与概念格压缩

doi:10.16451/j.cnki.issn1003-6059.202506003

Abstract
Figure/Table
References
Related Citation (15)

Download: PDF (699 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

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.

Key words： Formal Context Arrow-Closed Relation Compatible Subcontext Congruence Relations Concept Lattice Compression

Received: 24 May 2025

ZTFLH:	O29
	TP18

Fund:Supported by National Natural Science Foundation of China(No.62006190), Natural Science Basic Research Program of Shaanxi Province(No.2025JC-YBQN-048)

Corresponding Authors: REN Ruisi, Ph.D., associate professor. Her research interests include formal concept analysis, three-way decision and cognitive computing.

About author:: ZHANG Luzhen, Master student. Her research interests include formal concept analysis and three-way decision.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	ZHANG Luzhen
	REN Ruisi

Cite this article:

ZHANG Luzhen,REN Ruisi. Acquisition of Compatible Subcontexts and Concept Lattice Compression with Minimal Information Loss[J]. Pattern Recognition and Artificial Intelligence, 2025, 38(6): 520-537.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.202506003 OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2025/V38/I6/520

[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.