Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (1): 125-130.doi: 10.11896/jsjkx.200800013

• Database & Big Data & Data Science • Previous Articles     Next Articles

Method of Concept Reduction Based on Concept Discernibility Matrix

WANG Xia1,2, PENG Zhi-hua1, LI Jun-yu1,2, WU Wei-zhi1,2   

  1. 1 School of Mathematics,Physics and Information Science,Zhejiang Ocean University,Zhoushan,Zhejiang 316022,China
    2 Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province (Zhejiang Ocean University),Zhoushan, Zhejiang 316022,China
  • Received:2020-08-03 Revised:2020-09-23 Online:2021-01-15 Published:2021-01-15
  • About author:WANG Xia,born in 1980,Ph.D,asso-ciate professor.Her main research intere-sts include formal concept analysis,rough set theory and granular computing.
  • Supported by:
    National Natural Science Foundation of China (41631179,61773349,61976194) and Zhejiang Provincial Natural Science Foundation of China (LY18F030017).

PDF (PC)

792

Abstract: The concept reduction of a formal context based on Boolean factor analysis can preserve all binary relations of the formal context.That is the relations between objects and attributes contained in a concept reduction based on Boolean factor analysis are consistent with the binary relations represented by the formal context.Inspired by the idea of discernibility matrix solving attribute reduct in a concept lattice,a concept discernibility matrix is defined in a formal context,and a method of concept reduct based on the concept discernibility matrix is proposed to find all concept reducts.Firstly,a new discernibility matrix is defined in a formal context,which is called concept discernibility matrix of the formal context.Both the rows and columns of the matrix are the formal concepts.Each element of the matrix is a set consisted of all pairs of object and attribute,which belong to the formal concept in the corresponding row,but not to the formal concept in the corresponding column.Secondly,the relationship between the concept discernibility matrix and the concept consistent set is studied,and the method of judging concept consistent set is givenby using the concept discernibility matrix.Then,all formal concepts of a formal context are divided into three categories:core concept,relatively necessary concept and unnecessary concept according to their relationship to concept reducts.And characteristics of core concept,relatively necessary concept and unnecessary concept are discussed in detail.Moreover,methods of judging these three kinds of formal concepts are developed respectively by using the concept discernibility matrix.The detailed process of solving all concept reducts of a formal context is given by an example based on the concept discernibility matrix.Finally,solution steps to find all concept reducts are given by using the concept discernibility matrix,and the complexity of each step is simply analyzed.

Key words: Concept characteristic, Concept discernibility matrix, Concept reduction, Formal concept, Formal context

CLC Number: 

  • TP301
[1] WILLE R.Restructuring lattice theory:An approach based on hierarchies of concepts[M]//Ordered Sets.Dordrecht:Reidel,1982:445-470.
[2] GANTER B,WILLE R.Formal Concept Analysis:Mathematical Foundations[M].Berlin:Springer,1999:17-61.
[3] ZHANG W X,WEI L,QI J J.Attribute reduction theory and approach to concept lattice[J].Science in China (Series E),2005,35(6):628-639.
[4] ZHANG W X,WEI L,QI J J.Attribute reduction in concept lattice based on discernibility matrix[C]//10th International Conference Proceedings of Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing.Berlin:Springer,2005:157-165.
[5] WANG X,ZHANG W X.Knowledge reduction in concept lattices based on irreducible elements[J].Transaction on Computational Science V,2009,55(40):128-142.
[6] WU W Z,LEUNG Y,MI J S.Granular computing and knowledge reduction in formal contexts[J].IEEE Transactions on Knowledge and Data Engineer,2009,21(10):1461-1474.
[7] QI J J.Attribute reduction in formal contexts based on a new discernibility matrix[J].Journal of Applied Mathematics and Computing,2009,30(1):305-314.
[8] LIU J,MI J S.A novel approach to attribute reduction in formalconcept lattices,Rough Sets and Knowledge Technology[C]//Proceedings of Rough Sets and Knowledge Technology 3rd International Conference.Berlin:Springer,2008:426-433.
[9] WANG X,MA J M.A novel approach to attribute reduction in concept lattices[C]//Proceedings of Rough Sets and Knowledge Technology 1st International Conference.Berlin:Springer,2006,4062:522-529.
[10] LI L J,LI M Z,MI J S,et al.A simple discernibility matrix for attribute reduction in formal concept analysis based on granular concepts[J].Journal of Intelligent and Fuzzy Systems,2019,37(2):1-13.
[11] KONECNY J.On attribute reduction in concept lattices:me-thods based on discernibility matrix are outperformed by basic clarification and reduction[J].Information Sciences,2017,415-416:199-212.
[12] SKOWRON A,RAUSZER C.The discernibility matrices andfunctions in information systems[J].Intelligent Decision Support.Theory and Decision Library,1992,11:331-362.
[13] WEI L,QI J J,ZHANG W X.Attribute reduction theory of concept lattice based on decision formal contexts[J].Science in China (Series E),2008,32(2):195-208.
[14] CHEN J K,MI J S,XIE B,et al.A fast attribute reduction method for large formal decision contexts[J].International Journal of Approximate Reasoning,2019,106:1-17.
[15] JANOSTIK R,KONECNY J.General framework for consistencies in decision contexts[J].Information Sciences,2020,530:180-200.
[16] REN R S,WEI L.The attribute reductions of three-way concept lattices[J].Knowledge-Based Systems,2016,99:92-102.
[17] SHAO M W,LI K W.Attribute reduction in generalized one-sided formal contexts[J].Information Sciences,2017,378:317-327.
[18] SHAO M W,YANG H Z,WU W Z.Knowledge reduction informal fuzzy contexts[J].Knowledge-Based Systems,2015,73:265-275.
[19] CAO L,WEI L,QI J J.Concept reduction preserving binary relations[J].Pattern Recognition and Artificial Intelligence,2018,31(6):516-524.
[20] BELOHLÁVEK R,VYCHODIL V.Discovery of optimal factors in binary data via a novel method of matrix decomposition[J].Journal of Computer and System Sciences,2010,76(1):3-20.
[1] LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation [J]. Computer Science, 2021, 48(6): 234-240.
[2] SHEN Xia-jiong, YANG Ji-yong, ZHANG Lei. Attribute Exploration Algorithm Based on Unrelated Attribute Set [J]. Computer Science, 2021, 48(4): 54-62.
[3] ZHENG Tian-jian, HOU Jin-hong, ZHANG Wei, WANG Ju. Finite Basis of Implicational System Associated with Finite Models of Description Logic FL0 Under the Greatest Fixed Point Semantics [J]. Computer Science, 2020, 47(11A): 92-96.
[4] LIN Hong, QIN Ke-yun. Attribute Reduction for Decision Formal Contexts Based on Threek-way Decision Rules [J]. Computer Science, 2019, 46(3): 248-252.
[5] LI Zhong-ling, MI Ju-sheng, XIE Bin. Attribute Reduction in Inconsistent Decision Formal Contexts [J]. Computer Science, 2019, 46(12): 257-260.
[6] YAN An, YAN Xin-yi, CHEN Ze-hua. Formal Vector Method of Rule Extraction for Consistent Decision Information System [J]. Computer Science, 2019, 46(10): 236-241.
[7] ZHENG Shu-fu,YU Gao-feng. Attribute Transfer and Knowledge Discovery Based on Formal Context [J]. Computer Science, 2018, 45(6A): 117-119.
[8] QIN Ke-yun and LIN Hong. Relationships among Several Attribute Reduction Methods of Decision Formal Context [J]. Computer Science, 2018, 45(4): 257-259.
[9] ZHOU Chao, REN Zhi-yu, WU Wen-chao. Semantic Roles Mining Algorithms Based on Formal Concept Analysis [J]. Computer Science, 2018, 45(12): 117-122.
[10] CHANG Xin-xin, QIN Ke-yun. Approach for Granular Reduction in Formal Context Based on Objects-induced Three-way Concept Lattices [J]. Computer Science, 2018, 45(10): 225-228.
[11] JIANG Yu-ting, QIN Ke-yun. Property-oriented and Object-oriented Decision Rules in Decision Formal Contexts [J]. Computer Science, 2018, 45(10): 33-36.
[12] LIN Hong, QIN Ke-yun. Three-way Granular Reduction for Decision Formal Context [J]. Computer Science, 2018, 45(10): 47-50.
[13] WANG Zhen and WEI Ling. Attribute Reduction of Partially-known Formal Concept Lattices for Incomplete Contexts [J]. Computer Science, 2018, 45(1): 73-78.
[14] ZU Hong-jiao, XIE Bin and MI Ju-sheng. Concept Construction and Attribute Reduction in Incomplete Decision Formal Contexts [J]. Computer Science, 2017, 44(9): 83-87.
[15] NIU Jiao-jiao, FAN Min, LI Jin-hai and YIN Yun-qiang. Knowledge Discovery Method for Heterogeneous Data Based on Concept Lattice [J]. Computer Science, 2017, 44(9): 62-66.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.