Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (4): 54-62.doi: 10.11896/jsjkx.200800082

• Computer Science Theory • Previous Articles     Next Articles

Attribute Exploration Algorithm Based on Unrelated Attribute Set

SHEN Xia-jiong1,2, YANG Ji-yong1,2, ZHANG Lei 1,2,3   

  1. 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).

PDF (PC)

654

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(mn2P2),the worst time is O(mn3P2).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

CLC Number: 

  • TP301
[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] CAO Yang-chen, ZHU Guo-sheng, SUN Wen-he, WU Shan-chao. Study on Key Technologies of Unknown Network Attack Identification [J]. Computer Science, 2022, 49(6A): 581-587.
[2] XU Hui-hui, YAN Hua. Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children [J]. Computer Science, 2021, 48(6): 210-214.
[3] 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.
[4] WEN Xin, YAN Xin-yi, CHEN Ze-hua. Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations [J]. Computer Science, 2021, 48(3): 163-167.
[5] YUE Xiao-wei, PENG Sha and QIN Ke-yun. Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice [J]. Computer Science, 2020, 47(6A): 436-439.
[6] GUO Qing-chun,MA Jian-min. Judgment Methods of Interval-set Consistent Sets of Dual Interval-set Concept Lattices [J]. Computer Science, 2020, 47(3): 98-102.
[7] ZHU An-qing, LI Shuai, TANG Xiao-dong. Parallel FP_growth Association Rules Mining Method on Spark Platform [J]. Computer Science, 2020, 47(12): 139-143.
[8] 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.
[9] HAN Cheng-cheng, LIN Qiang, MAN Zheng-xing, CAO Yong-chun, WANG Hai-jun, WANG Wei-lan. Mining Nuclear Medicine Diagnosis Text for Correlation Extraction Between Lesions and Their Representations [J]. Computer Science, 2020, 47(11A): 524-530.
[10] LU Xin-yun, WANG Xing-fen. Educational Administration Data Mining of Association Rules Based on Domain Association Redundancy [J]. Computer Science, 2019, 46(6A): 427-430.
[11] ZHANG Wei-guo. Decision Making of Course Selection Oriented by Knowledge Recommendation Service [J]. Computer Science, 2019, 46(6A): 507-510.
[12] 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.
[13] LI Zhi-xing, REN Shi-ya, WANG Hua-ming, SHEN Ke. Knowledge Reasoning Method Based on Unstructured Text-enhanced Association Rules [J]. Computer Science, 2019, 46(11): 209-215.
[14] WANG Bin, MA Jun-jie, FANG Xin-xiu, WEI Tian-you. Association Rule Mining Algorithm Based on Timestamp and Vertical Format [J]. Computer Science, 2019, 46(10): 71-76.
[15] ZHENG Shu-fu,YU Gao-feng. Attribute Transfer and Knowledge Discovery Based on Formal Context [J]. Computer Science, 2018, 45(6A): 117-119.
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.