Computer Science ›› 2021, Vol. 48 ›› Issue (3): 163-167.doi: 10.11896/jsjkx.200100046

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

Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations

WEN Xin1, YAN Xin-yi2, CHEN Ze-hua1   

  1. 1 College of Big Data Science,Taiyuan University of Technology,Taiyuan 030024,China
    2 College of Electrical and Power Engineering,Taiyuan University of Technology,Taiyuan 030024,China
  • Received:2020-01-07 Revised:2020-05-20 Online:2021-03-15 Published:2021-03-05
  • About author:WEN Xin,born in 1993,postgraduate.Her main research interests include granular computing and knowledge engineering.
    CHEN Ze-hua,born in 1974,professor, is a senior member of China Computer Federation.Her main research interests include data mining and knowledge discovery.
  • Supported by:
    National Natural Science Foundation of China(61703299) and National Key R&D Program of China(2018YFB1404500).

Abstract: Rule extraction of decision information system is an important topic in the field of data mining.Concept lattice theory and rough set theory are both theoretical tool for data analysis.This paper explores the relationship between these two theories,and uses the equivalent relationship to define the minimal optimistic concept lattice and its structure.The minimal optimistic concept is different from the traditional classic concept,but has a lattice structure,and a rule extraction algorithm for decision table is proposed.Based on granular computing,the algorithm computes the concepts in each layer from coarse to fine granularity space,and extracts decision rules according to the relationship between minimal optimistic concepts and decision equivalence classes.In order to achieve the purpose of knowledge reduction for decision information systems,the algorithm accelerates its convergent speed by setting the termination conditions.The definition of minimal optimistic concept is broader than classical concept,and the generation algorithm is simpler.The correctness and effectiveness of the new algorithm are verified by theorem proving and case analysis.Finally,the experimental results based on different data sets demonstrate that the proposed algorithm is more effective for rule extraction in most cases than other algorithms.

Key words: Concept lattice theory, Decision information system, Granular computing, Minimal optimistic concept, Rule extraction

CLC Number: 

  • TP181
[1]WANG G Y.Rough Set Theory and Knowledge Acquisition[M].Xi’an:Xi’an Jiaotong University Press,2001:147-152.
[2]MENG Z Q,SHI Z Z.On rule acquisition methods for data classification in heterogeneous incomplete decision systems[J].Knowledge-Based Systems,2020,193:1-22.
[3]MATSUMOTO Y,WATADA J.Knowledge Acquisition fromRough Sets Using Merged Decision Rules[J].Advanced Computational Intelligence and Intelligent Informatics,2018,22(3):404-410.
[4]CHEN Z H,ZHANG Y,XIE G.Mining algorithm for concise decision rules based on granular computing[J].Control & Decision,2015,30(1):143-148.
[5]WILLE R.Restructuring Lattice Theory:An Approach Basedon Hierarchies of Concepts [M].Springer Netherlands,1982:445-470.
[6]ZHI H L,LI J H.Granule description based knowledge disco-very from incomplete formal contexts via necessary attributeanalysis[J].Information Science,2019,485:347-361.
[7]WEI L,LIU L,QI J J,et al.Rules acquisition of formal decision contexts based on three-way concept lattices[J].Information Science,2020,516:529-544.
[8]LI J H,MEI C L,KUMAR C A,et al.On Rule Acquisition in Decision Formal Contexts[J].International Journal of Machine Learning & Cybernetics,2013,4(6):721-731.
[9]THUY N N,WONGTHANAVASU S.An efficient strippedcover-based accelerator for reduction of attributes in incomplete decision tables[J].Expert Systems With Applications,2020,143:113076.1-113076.15.
[10]WU W Z,QIAN Y H,LI T J,et al.On rule acquisition in incomplete multi-scale decision tables[J].Information Sciemces,2017,378:282-302.
[11]JOSÉ BENÍTEZ-CABALLERO M,MEDINA J,RAMÍREZ-POUSSA E,et al.Rough-set-driven approach for attribute reduction in fuzzy formal concept analysis[J].Fuzzy Sets and Systems,2019,391:117-138.
[12]XIAO Q M,LANG G M,LIU W J,et al.The approximations in rough concept lattice and approximable concept lattice[J].Journal of Intelligent & Fuzzy Systems,2017,33(6):3459-3467.
[13]LI J H,REN Y,MEI C L,et al.A comparative study of multigranulation rough sets and concept lattices via rule acquisition[J].Knowledge-Based Systems,2016,91:152-164.
[14]ZHU Z Q,LI H,DAI G Y,et al.A rough set multi-knowledge extraction algorithm and its formal concept analysis[C]//International Conference on Intelligent Systems Design and Applications.2015:25-29.
[15]LI J H,MEI C L,ZHANG H Y.Attribute Reduction Method for Formal Decision Contexts Based on Genetic Algorithm and its Application to Decision-making Analysis[J].Journal of Chinese Computer Systems,2015,36(8):1803-1808.
[16]KANG X P,MIAO D Q.A study on information granularity in formal concept analysis based on concept-bases[J].Knowledge-Based Systems,2016,105:147-159.
[1] FANG Lian-hua, LIN Yu-mei, WU Wei-zhi. Optimal Scale Selection in Random Multi-scale Ordered Decision Systems [J]. Computer Science, 2022, 49(6): 172-179.
[2] ZENG Hui-kun, MI Ju-sheng, LI Zhong-ling. Dynamic Updating Method of Concepts and Reduction in Formal Context [J]. Computer Science, 2021, 48(1): 131-135.
[3] RAO Meng,MIAO Duo-qian,LUO Sheng. Rough Uncertain Image Segmentation Method [J]. Computer Science, 2020, 47(2): 72-75.
[4] 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.
[5] YANG Feng. Symbolic Value Partition Algorithm Using Granular Computing [J]. Computer Science, 2018, 45(11A): 445-452.
[6] CHEN Li-fang, DAI Qi, FU Qi-feng. Design and Application of Extreme Learning Machine Model Based on Granular Computing [J]. Computer Science, 2018, 45(10): 59-63.
[7] SHANG Ao, PEI Xiao-peng, LV Ying-chun and CHEN Ze-hua. State Reduction Algorithm for Completely Specified Sequential Logic Circuit Based on Equivalence Relation [J]. Computer Science, 2018, 45(1): 118-121.
[8] YE Xiao-qing, LIU Dun and LIANG De-cui. Three-way Granular Recommendation Algorithm Based on Collaborative Filtering [J]. Computer Science, 2018, 45(1): 90-96.
[9] WU Jun and WANG Chun-zhi. Multiple Correlation Analysis and Application of Granular Matrix Based on Big Data [J]. Computer Science, 2017, 44(Z11): 407-410.
[10] ZHAO Ying-xiu, LIU Wen-qi, LI Jin-hai and ZHAO Ning. Credit Evaluation of P2P Lending User Based on Granular Computing and Information Fusion [J]. Computer Science, 2016, 43(9): 242-246.
[11] CHEN Fei, JIANG Lin and LI Jin-hai. New Note on Classical Measure of Knowledge Dependency and Attribute Significance [J]. Computer Science, 2016, 43(2): 273-276.
[12] CHEN Li-fang, CHEN Liang and LIU Bao-xiang. Research of SVM Multiclass Model Based on Granular Computing & Huffman Tree [J]. Computer Science, 2016, 43(1): 64-68.
[13] ZHENG Lu-bin, CHEN Yu-ming, ZENG Zhi-qiang and LU Jun-wen. Binary Granular Computing Model [J]. Computer Science, 2016, 43(1): 270-274.
[14] TANG Xiao, SHU Lan and ZHENG Wei. Premature Beat Signal Recognition Algorithm Based on Wavelet Transform and Rough Set [J]. Computer Science, 2015, 42(Z11): 32-35.
[15] CHEN Ya-fei and WANG Xia. Analysis of Factors of Effective Teaching Based on Inconsistent Decision Information Systems [J]. Computer Science, 2015, 42(6): 107-110.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!