基于不相关属性集合的属性探索算法

doi:10.11896/jsjkx.200800082

计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 54-62.doi: 10.11896/jsjkx.200800082

基于不相关属性集合的属性探索算法

沈夏炯^1,2, 杨继勇^1,2, 张磊^1,2,3

1 河南大学河南省大数据分析与处理重点实验室河南开封475000
2 河南大学计算机与信息工程学院河南开封475000
3 河南大学数据与知识工程研究所河南开封475000

收稿日期:2020-06-24 修回日期:2020-11-21 出版日期:2021-04-15 发布日期:2021-04-09
通讯作者: 张磊(zhanglei@henu.edu.cn)
基金资助:
国家自然科学基金(61701170);河南省科技厅科技攻关计划基金(202102310340);河南省高等学校青年骨干教师培养计划项目(2019GGJS040,2020GGJS027);河南省高等学校重点科研项目(21A110005)

Attribute Exploration Algorithm Based on Unrelated Attribute Set

SHEN Xia-jiong^1,2, YANG Ji-yong^1,2, ZHANG Lei ^1,2,3

1 Henan Key Laboratory of Big Data Analysis and Processing,Henan University,Kaifeng,Henan 475000,China
2 College of Computer and Information Engineering Henan University,Kaifeng,Henan 475000,China
3 Institute of Data and Knowledge Engineering,Henan University,Kaifeng,Henan 475000,China

Received:2020-06-24 Revised:2020-11-21 Online:2021-04-15 Published:2021-04-09
About author:SHEN Xia-jiong,born in 1963,Ph.D,professor,Ph.D supervisor,is a member of China Computer Fededration.His main research interests include data analysis,software engineering,distributed/parallel computing,formal concept analysis,access control and so on.(shenxj@henu.edu.cn)
ZHANG Lei,born in 1981,Ph.D,asso-ciate professor.His main research interests include machine learning,big data,information security,access control,formal concept analysis and so on.
Supported by:
National Natural Science Foundation of China(61701170),Scientific and Technological Project of Henan Pro-vince(202102310340),Foundation of University Young Key Teacher of Henan Province(2019GGJS040,2020GGJS027) and Key Scientific Research Projects of Colleges and Universities in Henan Province(21A110005).

摘要/Abstract

摘要： 作为形式概念分析理论中的一个重要工具,属性探索算法能够以问题为导向,交互式地逐步发现系统知识,在知识的发现和获取中居于核心地位。但是,当形式背景的规模较大时,属性探索算法的计算过程过于耗时,严重制约了算法在当前大数据时代的推广与应用。耗时瓶颈主要存在于“寻找下一个与专家交互的问题”这一环节,传统算法在此过程中存在大量冗余计算。针对这个问题,在分析伪内涵和内涵与蕴涵集合的内在逻辑关系的基础上,提出并证明了3个定理,根据定理给出了一种基于不相关属性集合的属性探索算法,该算法在计算伪内涵与内涵的过程中,借助提出的定理,跳过违反该逻辑关系的属性集合是否为伪内涵或者内涵的判断过程,减小了算法的搜索空间,从而降低了算法的时间复杂度。所提算法最好的时间复杂度为O(mn²P²),最坏的时间复杂度为O(mn³P²)。实验结果表明,与传统算法相比,该算法具有较为明显的时间性能优势。

关键词: 概念格, 关联规则, 伪内涵, 形式概念分析, 知识发现, 属性探索

Abstract: As an important tool in the theory of formal concept analysis,the attribute exploration algorithm is problem-oriented and can interactively discover system knowledge step by step,which plays a central role in knowledge discovery and acquisition.However,if the size of formal context is large,the calculation process of attribute exploration algorithm will spend too much time to restrict seriously the promotion and application of the algorithm in the current era of big data.The bottleneck of time-consuming mainly lies in “finding the next problem to interact with experts”,traditional algorithms have a lot of redundant computation in this process.Aiming at this problem,three theorems are put forward and proved based on analyzing the logic relation between pseudo-intent,intent and implication set.According to these theorems,an attribute exploration algorithm based on an unrelated collection is given.During pseudo-intent and intent calculation,this algorithm,by means of the proposed theorems,can skip the process of determining whether or not an attribute set that violates the logical relationship is a pseudo-intent or intent,so as to reduce the search space and time complexity of the algorithm.The best time is O(mn²P²),the worst time is O(mn³P²).The experi-mental results show that the proposed algorithm has an obvious time performance advantage compared with the traditional algorithm.

Key words: Association rules, Attribute exploration, Concept lattice, Formal concept analysis, Knowledge discovery, Pseudo-intent

中图分类号:

TP301

沈夏炯, 杨继勇, 张磊. 基于不相关属性集合的属性探索算法[J]. 计算机科学, 2021, 48(4): 54-62. https://doi.org/10.11896/jsjkx.200800082

SHEN Xia-jiong, YANG Ji-yong, ZHANG Lei. Attribute Exploration Algorithm Based on Unrelated Attribute Set[J]. Computer Science, 2021, 48(4): 54-62. https://doi.org/10.11896/jsjkx.200800082

参考文献

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

相关文章 15

[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]	郑添健, 侯金宏, 张维, 王驹. 循环描述逻辑系统FL₀最大不动点模型的有穷基 Finite Basis of Implicational System Associated with Finite Models of Description Logic FL₀ 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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于不相关属性集合的属性探索算法

Attribute Exploration Algorithm Based on Unrelated Attribute Set

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0