计算机科学 ›› 2018, Vol. 45 ›› Issue (1): 84-89.doi: 10.11896/j.issn.1002-137X.2018.01.013

• CRSSC-CWI-CGrC-3WD 2017 • 上一篇    下一篇

概念格中基于粗糙熵的属性约简方法

李美争,李磊军,米据生,解滨   

  1. 河北师范大学信息技术学院 石家庄050024;河北省网络与信息安全重点实验室 石家庄050024,河北师范大学数学与信息科学学院 石家庄050024;河北省计算数学与应用重点实验室 石家庄050024,河北师范大学数学与信息科学学院 石家庄050024;河北省计算数学与应用重点实验室 石家庄050024,河北师范大学信息技术学院 石家庄050024;河北省网络与信息安全重点实验室 石家庄050024
  • 出版日期:2018-01-15 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金项目(61502144,7,61672206,2),河北省高等学校自然科学基金项目(QN2017095,QN2016133),河北省高校创新团队领军人才培育计划项目(LJRC022),河北省博士后择优资助

Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice

LI Mei-zheng, LI Lei-jun, MI Ju-sheng and XIE Bin   

  • Online:2018-01-15 Published:2018-11-13

摘要: 属性约简是概念格理论的研究重点内容之一。通过将粗糙熵引入概念格理论中,定义了一种粗糙熵约简。首先,基于所有概念外延定义了形式背景的粗糙熵,并分析了它的性质;其次,定义了形式背景的粗糙熵约简,并揭示了粗糙熵约简与概念格约简之间的关系;在此基础上,基于属性重要度设计了计算粗糙熵的启发式算法,并通过实验验证了该算法的有效性。

关键词: 概念格,属性约简,启发式算法,粗糙熵

Abstract: Attribute reduction is one of the crucial issues in the theory study of concept lattice.In this paper,rough entropy was introduced to conduct a kind of attribute reduction.Firstly,rough entropy in a formal context was defined via the whole set of all concept extents,and the properties of rough entropy were analyzed.Secondly,a rough entropy based attribute reduction of a formal context was given,and the relationship between the rough entropy-based reduct and the concept lattice-based reduct was revealed.Based on this,a heuristic algorithm based on the attribute significance was proposed to compute a rough entropy-based reduct,and some numerical experiments were conducted to show the efficiency of the proposed methods.

Key words: Concept lattice,Attribute reduction,Heuristic algorithm,Rough entropy

[1] WILLE R.Restructuring Lattice Theory:An Approach Basedon Hierarchies of Concepts [M]∥Ordered Sets.Springer Nether-lands,1982:445-470.
[2] PRISS U.Formal Concept Analysis In Information Science [J].Arist,2006,40(1):521-543.
[3] POELMANS J,IGNATOV D I,KUZNETSOV S O,et al.Formal Concept Analysis in Knowledge Processing:A Survey on Applications[J].Expert Systems with Applications,2013,40(16):6538-6560.
[4] TILLEY T,EKLUND P.Citation Analysis Using Formal Concept Analysis:A Case Study in Software Engineering [C]∥Proceedings of the 18th International Workshop on Database and Expert Systems Applications.Washington,USA:IEEE,2007:545-550.
[5] POELMANS J,IGNATOV D I,VIAENE S,et al.Text Mining Scientific Papers:A Survey on FCA-Based Information Retrieval Research [C]∥Proceeding of the 12th Industrial Conference on Advances in Data Mining:Applications and Theoretical Aspects.Berlin,Germany:Springer,2012:273-287.
[6] LAKHAL L,STUMME G.Efficient Mining of AssociationRules Based on Formal Concept Analysis [C]∥Formal Concept Analysis.Berlin,Germany:Springer,2005:180-195.
[7] LIANG J Y,WANG J H.An Algorithm for Extracting Rule-Generating Sets Based on Concept Lattice[J].Journal of Computer Research nd Development,2004,41(8):1339-1344.(in Chinese) 梁吉业,王俊红.基于概念格的规则产生集挖掘算法[J].计算机研究与发展,2004,41(8):1339-1344.
[8] SHAO M W,LI K W.Attribute reduction in generalized one-sided formal contexts[J].Information Sciences,2016,378:317-327.
[9] CHEUNG K S,VOGEL D.Complexity reduction in lattice-based information retrieval[J].Information Retrieval,2005,8(2):285-299.
[10] EˇLOHLVEK R,SKLENˇV,ZACPAL J.Crisply generated fuzzy concepts [C]∥International Conference on Formal Concept Analysis.Berlin Heidelberg:Springer,2005:269-284.
[11] KUMAR C A,SRINIVAS S.Concept lattice reduction usingfuzzy K-means clustering[J].Expert systems with applications,2010,37(3):2696-2704.
[12] WU W Z,LEUNG Y,MI J S.Granular Computing and Know-ledge Reduction in Formal Contexts [J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1461-1474.
[13] LI J H,MEI C L,LV Y J.Knowledge Reduction in DecisionFormal Contexts [J].Knowledge-Based Systems,2011,24(5):709-715.
[14] LI J H,MEI C L,LV Y J.Incomplete Decision Contexts:Approximate Concept Construction,Rule Acquisition and Know-ledge Reduction [J].International Journal of Approximate Reasoning,2013,54(1):149-165.
[15] SHAO M W,LEUNG Y,WU W Z.Rule Acquisition and Complexity Reduction in Formal Decision Contexts[J].International Journal of Approximate Reasoning,2014,55(1):259-274.
[16] LI L J,MI J S,XIE B.Attribute Reduction Based on Maximal Rules in Decision Formal Context[J].International Journal of Computational Intelligence Systems,2014,7(6):1044-1053.
[17] 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.(in Chinese) 张文修,魏玲,祁建军.概念格的属性约简理论与方法[J].中国科学:E 辑,2005,35(6):628-639.
[18] MI J S,LEUNG Y,WU W Z.Approaches to Attribute Reduction in Concept Lattices Induced by Axialities[J].Knowledge-Based Systems,2010,23(6):504-511.
[19] SHAO M W,LEUNG Y,WANG X Z,et al.Granular Reducts of Formal Fuzzy Contexts [J].Knowledge-Based Systems,2016,114:156-166.
[20] LI M Z,WANG G Y.Approximate Concept Construction With Three-Way Decisions and Attribute Reduction in Incomplete Contexts [J].Knowledge-Based Systems,2016,91:165-178.
[21] WANG J H,LIANG J Y,QIAN Y H.A Heuristic Method to Attribute Reduction for Concept Lattice [C]∥International Conference on Machine Learning and Cybernetics.New York:IEEE Press,2010,1:483-487.
[22] LV Y J,LI J H.Heuristic Algorithms for Attribute Reduction on Concept Lattice[J].Computer Engineering and Applications,2009,45(2):154-157.(in Chinese) 吕跃进,李金海.概念格属性约简的启发式算法[J].计算机工程与应用,2009,45(2):154-157.
[23] LIANG J Y,XU Z B.Uncertainty Measures of Roughness of Knowledge and Rough Sets in Incomplete Information Systems [C]∥Proceedings of the 3rd World Congress on Intelligent Control and Automation,2000.New York:IEEE Press,2000:2526-2529.
[24] LIANG J Y,XU Z B.The Algorithm on Knowledge Reduction in Incomplete Information Systems [J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(1):95-103.
[25] HUANG B,ZHOU X Z,SHI Y C.Entropy of Knowledge and Rough Set Based on General Binary Relation [J].Systems Engineering-Theory & Practice,2004,24(1):93-96.(in Chinese) 黄兵,周献中,史迎春.基于一般二元关系的知识粗糙熵与粗集粗糙熵[J].系统工程理论与实践,2004,24(1):93-96.
[26] GANTER B,WILLE R.Formal Concept Analysis:Mathematical Foundations [M].Berlin,Germany:Springer,1999.
[27] YAO Y Y,ZHAO Y.Discernibility matrix simplification forconstructing attribute reducts[J].Information Sciences,2009,179(7):867-882.
[28] LICHMAN M.UCI machine learning repository [EB/OL].http://archive.ics.uci.edu/ml.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!