计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 54-62.doi: 10.11896/jsjkx.200800082
沈夏炯1,2, 杨继勇1,2, 张磊1,2,3
SHEN Xia-jiong1,2, YANG Ji-yong1,2, ZHANG Lei 1,2,3
摘要: 作为形式概念分析理论中的一个重要工具,属性探索算法能够以问题为导向,交互式地逐步发现系统知识,在知识的发现和获取中居于核心地位。但是,当形式背景的规模较大时,属性探索算法的计算过程过于耗时,严重制约了算法在当前大数据时代的推广与应用。耗时瓶颈主要存在于“寻找下一个与专家交互的问题”这一环节,传统算法在此过程中存在大量冗余计算。针对这个问题,在分析伪内涵和内涵与蕴涵集合的内在逻辑关系的基础上,提出并证明了3个定理,根据定理给出了一种基于不相关属性集合的属性探索算法,该算法在计算伪内涵与内涵的过程中,借助提出的定理,跳过违反该逻辑关系的属性集合是否为伪内涵或者内涵的判断过程,减小了算法的搜索空间,从而降低了算法的时间复杂度。所提算法最好的时间复杂度为O(mn2P2),最坏的时间复杂度为O(mn3P2)。实验结果表明,与传统算法相比,该算法具有较为明显的时间性能优势。
中图分类号:
[1]GANTER B,WILLE R.Formal concept analysis:mathematical foundations[M].Springer Science & Business Media,2012. [2]LI J H,WEI L,ZHANG Z,et al.Concept lattice theory andmethod and their research prospect [J].Pattern Recognition and Artificial Intelligence,2020,33(7):619-642. [3]JABBARI S,STOFFEL K.A Methodology for ExtractingKnowledge about Controlled Vocabularies from Textual Data using FCA-Based Ontology Engineering[C]//2018 IEEE International Conference on Bioinformatics and Biomedicine(BIBM).Madrid Spain,2018:1657-1661. [4]MAHANI A,BABA-ALI A R.A new rule-based knowledge extraction approach for imbalanced datasets[J].Knowledge and Information Systems,2019,61:1303-1329. [5]WEI L,LIU L,QI J J,et al.Rules acquisition of formal decision contexts based on three-way concept lattices[J].Information Sciences,2020,516:529-544. [6]MI Y L,LIU W Q,SHI Y,et al.Semi-supervised ConceptLearning by Concept-cognitive Learning and Concept Space[J].IEEE Transactions on Knowledge and Data Engineering,2020(99):1-1. [7]ZHI H L,LI Y N.Knowledge representation base on concept cluster[J].journal of Northwest University(Nature Science Edition),2020,50(4):529-536. [8]LI J H,HE J J,WU W Z.Optimization of class-attribute block in multi-granularity formal concept analysis[J].Journal of Shandong University(Natural Science),2020,55(5):1-12. [9]GANTER B,OBIEDKOV S,RUDOLPH S,et al.Conceptual exploration[M].Heidelberg:Springer,2016. [10]BORCHMANN D.A general form of attribute exploration[J].arXiv:1202.4824,2012. [11]BORCHMANN D.Exploring faulty data[C]//InternationalConference on Formal Concept Analysis.Springer,Cham,2015:219-235. [12]GLODEANU C V.Attribute Exploration with Fuzzy Attributes and Background Knowledge[C]//CLA.2013:69-80. [13]OBIEDKOV S,KOURIE D G,ELOFF J H P.Building accesscontrol models with attribute exploration[J].Computers & Security,2009,28(1/2):2-7. [14]ROBERT J,SEBASTIAN R.Attribute Exploration on the Web[C]//the 11th International Conference on Formal Concept Analysis.2013:19-34. [15]OBIEDKOV S,ROMASHKIN N.Collaborative conceptual exploration as a tool for crowdsourcing domain ontologies[C]//Proceedings of Russian and South African Workshop on Know-ledge Discovery Techniques Based on Formal Concept Analysis,CEUR Workshop Proceedings.2015,1552:58-70. [16]HANIKA T,ZUMBRÄGEL J.Towards collaborative concep-tual exploration[C]//International Conference on Conceptual Structures.Springer,Cham,2018:120-134. [17]CODOCEDO V,BAIXERIES J,KAYTOUE M,et al.Sampling Representation Contexts with Attribute Exploration[C]//International Conference on Formal Concept Analysis.Springer,Cham,2019:307-314. [18]RYSSEL U,DISTEL F,BORCHMANN D.Fast algorithms for implication bases and attribute exploration using proper premises[J].Annals of Mathematics and Artificial Intelligence,2014,70(1/2):25-53. [19]OLLBOLD J,KÖHLING R,BORCHMANN D.Attribute ex-ploration with proper premises and incomplete knowledge applied to the free radical theory of ageing[C]//International Conference on Formal Concept Analysis.Springer,Cham,2014:268-283. [20]KRIEGEL F.Parallel attribute exploration[C]//InternationalConference on Conceptual Structures.Springer,Cham,2016:91-106. [21]ZHAO X X,QIN P,WANG J.Research on attribute exploration algorithm[J].Computer Science and Exploration,2009,3(5):509-518. |
[1] | 曹扬晨, 朱国胜, 孙文和, 吴善超. 未知网络攻击识别关键技术研究 Study on Key Technologies of Unknown Network Attack Identification 计算机科学, 2022, 49(6A): 581-587. https://doi.org/10.11896/jsjkx.210400044 |
[2] | 徐慧慧, 晏华. 基于相对危险度的儿童先心病风险因素分析算法 Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children 计算机科学, 2021, 48(6): 210-214. https://doi.org/10.11896/jsjkx.200500082 |
[3] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
[4] | 温馨, 闫心怡, 陈泽华. 基于等价关系的最小乐观概念格生成算法 Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations 计算机科学, 2021, 48(3): 163-167. https://doi.org/10.11896/jsjkx.200100046 |
[5] | 张素梅, 张波涛. 一种基于量子耗散粒子群的评估模型构建方法 Evaluation Model Construction Method Based on Quantum Dissipative Particle Swarm Optimization 计算机科学, 2020, 47(6A): 84-88. https://doi.org/10.11896/JsJkx.190900148 |
[6] | 陈孟辉, 曹黔峰, 兰彦琦. 基于区块挖掘与重组的启发式算法求解置换流水车间调度问题 Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem 计算机科学, 2020, 47(6A): 108-113. https://doi.org/10.11896/JsJkx.190300151 |
[7] | 岳晓威, 彭莎, 秦克云. 基于面向对象(属性)概念格的形式背景属性约简方法 Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice 计算机科学, 2020, 47(6A): 436-439. https://doi.org/10.11896/JsJkx.191100011 |
[8] | 崔巍, 贾晓琳, 樊帅帅, 朱晓燕. 一种新的不均衡关联分类算法 New Associative Classification Algorithm for Imbalanced Data 计算机科学, 2020, 47(6A): 488-493. https://doi.org/10.11896/JsJkx.190600132 |
[9] | 王青松, 姜富山, 李菲. 大数据环境下基于关联规则的多标签学习算法 Multi-label Learning Algorithm Based on Association Rules in Big Data Environment 计算机科学, 2020, 47(5): 90-95. https://doi.org/10.11896/jsjkx.190300150 |
[10] | 郭庆春,马建敏. 对偶区间集概念格上区间集协调集的判定方法 Judgment Methods of Interval-set Consistent Sets of Dual Interval-set Concept Lattices 计算机科学, 2020, 47(3): 98-102. https://doi.org/10.11896/jsjkx.190500098 |
[11] | 朱岸青, 李帅, 唐晓东. Spark平台中的并行化FP_growth关联规则挖掘方法 Parallel FP_growth Association Rules Mining Method on Spark Platform 计算机科学, 2020, 47(12): 139-143. https://doi.org/10.11896/jsjkx.191000110 |
[12] | 郑添健, 侯金宏, 张维, 王驹. 循环描述逻辑系统FL0最大不动点模型的有穷基 Finite Basis of Implicational System Associated with Finite Models of Description Logic FL0 Under the Greatest Fixed Point Semantics 计算机科学, 2020, 47(11A): 92-96. https://doi.org/10.11896/jsjkx.200300188 |
[13] | 张蕾,蔡明. 基于主题融合和关联规则挖掘的图像标注 Image Annotation Based on Topic Fusion and Frequent Patterns Mining 计算机科学, 2019, 46(7): 246-251. https://doi.org/10.11896/j.issn.1002-137X.2019.07.037 |
[14] | 陆鑫赟, 王兴芬. 基于领域关联冗余的教务数据关联规则挖掘 Educational Administration Data Mining of Association Rules Based on Domain Association Redundancy 计算机科学, 2019, 46(6A): 427-430. |
[15] | 张维国. 面向知识推荐服务的选课决策 Decision Making of Course Selection Oriented by Knowledge Recommendation Service 计算机科学, 2019, 46(6A): 507-510. |
|