一种基于二进制表示的快速求核算法

doi:10.11896/j.issn.1002-137X.2016.12.013

摘要/Abstract

摘要： 在基于粗糙集的知识发现过程中,计算条件属性对论域的划分U/C和求解属性核是尤为关键的步骤。一般需要逐个比较对象的所有条件属性值才能得出结果。提出一种基于二进制表示的方法,只需比较对象的属性值的“和”。该方法先求得所有条件属性值的“和”,仅对该“和”进行一次比较,再通过判断该“和”是否重复,就能得出U/C,理论分析得到该算法的复杂度为O(|C||U|)；然后把计算U/C的思想应用于求解属性核,提出了一种新的快速计算属性核的高效算法。理论分析表明,无论信息系统是否一致,该算法的复杂度均可达到O(|C||U|)。随后通过一个实例阐明了算法的具体步骤,最后通过实验验证了算法的正确性和高效性。

关键词: 粗糙集,属性核,二进制表示,信息系统,高效算法

Abstract: Computing partitions of the domain (U/C) based on condition attributes and searching for attribute core are the most critical and time-consuming computation during the process of knowledge discovery based on rough sets.Gene-rally,them through comparing every attribute value of each object.In this paper,based on the binary representation,the “sum” of all the conditional attribute was got firstly.Comparing the “sums” once ,we can obtain U/C through judging whether the “sums” are repeated or not,and its time complexity is O(|C||U|).Then this method for computing U/C was used to design a new efficient algorithm for quickly computing attribute core,and its time complexity is O(|C||U|) whether information system is consistent or not.An example was used to illustrate the detail steps of the proposed algorithms.Finally,experimental results show that the new algorithms are not only exact but also efficient.

Key words: Rough set,Attribute core,Binary representation,Information systems,Efficient algorithm

胡帅鹏,张清华,姚龙洋. 一种基于二进制表示的快速求核算法[J]. 计算机科学, 2016, 43(12): 79-83. https://doi.org/10.11896/j.issn.1002-137X.2016.12.013

HU Shuai-peng, ZHANG Qing-hua and YAO Long-yang. Effective Algorithm for Computing Attribute Core Based on Binary Representation[J]. Computer Science, 2016, 43(12): 79-83. https://doi.org/10.11896/j.issn.1002-137X.2016.12.013

参考文献

[1] Pawlak Z.Rough sets[J].International Journal of Computer & Information Sciences,1982,38(11):341-356
[2] Pawlak Z.Rough set theory and its application to data analysis[J].Cybernetics and Systems,2010,29(7):661-688
[3] Qian Jin,Miao Duo-qian,Zhang Zhe-hua,et al.Hybrid approa-ches to attribute reduction based on indiscernibility and discer-nibility relation[J].International Journal of Approximate Reasoning,2011,52(2):212-230
[4] Zhang Yi-rong,Xian Ming,Xiao Shun-ping,et al.An Anomaly Intrusion Detection Technique of Support Vector Machine Based on Rough Set Attribute Reduction[J].Computer Science,2006,33(6):64-68(in Chinese) 张义荣,鲜明,肖顺平,等.一种基于粗糙集属性约简的支持向量异常入侵检测方法[J].计算机科学,2006,33(6):64-68
[5] Zhang Ying-chun,Su Bo-hong,Cao Juan.Study on application of attributive reduction based on Rough sets in Data Mining[J].Computer Science,2013,40(8):223-226(in Chinese) 张颖淳,苏伯洪,曹娟.基于粗糙集的属性约简在数据挖掘中的应用研[J].计算机科学,2013,40(8):223-226
[6] Li Ming,Deng Shao-bo,Feng Sheng-zhong,et al.Fast assignment reduction in inconsistent incomplete decision systems[J].Journal of Systems Engineering & Electronics,2014,25(1):83-94
[7] Zhang Qin-hua,Guo Yong-hong,Xiao Yu.Attribute Reduction Based on Approximation Set of Rough Set[J].Journal of Computational Information Systems,2014,10(16):6859-6866
[8] Wang Yong-sheng,Zheng Xue-feng,Suo Yan-feng.Dynamic algorithm for computer attribute reduction based on information granularity[J].Computer Science,2015,42(4):213-216(in Chinese) 王永生,郑雪峰,锁延锋.一种基于信息粒度的动态属性约简求解算法[J].计算机科学,2015,42(4):213-216
[9] Yang Xi-bei,Yan Xu,Xu Su-ping,et al.New Heuristic Attribute Reduction Algorithm Based on Sample Selection[J].Computer Science,2016,43(1):49-52(in Chinese) 杨习贝,颜旭,徐苏平,等.基于样本选择的启发式属性约简方法研究[J].计算机科学,2016,43(1):49-52
[10] R I,CT G,Enriquez S,et al.Attributing reductions in coral calcification to the saturation state of aragonite,comments on the effects of persistent natural acidification[J].Proceedings of the National Academy of Sciences of the United States of America,2014,111(3):E300-E301
[11] Wang Chang-zhong,He Qiang,Chen De-gang,et al.A novel me-thod for attribute reduction of covering decision systems[J].Information Sciences,2014,254(5):181-196
[12] Qian Jin,Lv Ping,Yue Xiao-dong,et al.Hierarchical attribute reduction algorithms for big data using MapReduce[J].Know-ledge-Based Systems,2015,73(12):18-31
[13] Skowron A,Rauszer C.The Discernibility Matrices and Func-tions in Information Systems[J].Theory & Decision Library,2012,11:331-362
[14] Hu Xiao-hua,Cercone N.Learning in Relational Data-bases:ARough Set Approach[J].Computational Intelligence,1995,11(2):323-338
[15] Ye Dong-yi,Chen Zhao-jiong.A new discernibility matrix andthe computation of a core[J].Chinese Journal of Electronic,2002,30(7):1086-1088(in Chinese) 叶东毅,陈昭炯.一个新的差别矩阵及其求核方法[J].电子学报,2002,30(7):1086-1088
[16] Wang Guo-yin.Calculation methods for core attributes of decision table [J].Chinese Journal of Computers,2003,26(5):611-615(in Chinese) 王国胤.决策表核属性的计算方法[J].计算机学报,2003,26(5):611-615
[17] Zhao Jun,Wang Guo-yin,Wu Zhong-fu,et al.An efficient ap-proach to compute the feature core[J].Mini-Micro Systems,2003,24(11):1950-1953(in Chinese) 赵军,王国胤,吴中福,等.一种高效的属性核计算方法[J].小型微型计算机系统,2003,24(11):1950-1953
[18] Yang Ming,Sun Zhi-hui.Improvement of discernibility matrixand the computation of core[J].Journal of Fudan University,2004,43(5):865-868(in Chinese) 杨明,孙志挥.改进的差别矩阵及其求核方法[J].复旦学报(自然科学版),2004,43(5):865-868
[19] Liu Shao-hui,Sheng Qiu-jian,Shi Zhong-zhi.A New Method for Fast Computing Positive Region[J].Journal of Computer Research and Development,2003,40(5):637-642(in Chinese) 刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法[J].计算机研究与发展,2003,40(5):637-642
[20] Xu Zhang-yan,Liu Zuo-peng,Yang Bing-ru,et al.A quick attribute reduction algorithm with complexity of max {O(|C||U|),O(|C|²|U/C|)}[J].Chinese Journal of Computers,2006,29(3):391-399(in Chinese) 徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max{O(|C||U|),O(|C|²|U/C|)}的快速属性约简算法[J].计算机学报,2006,29(3):391-399
[21] Xu Zhang-yan,Yang Bing-ru,Song Wei.Quick Computing Core Algorithm Based on Discernibility Matrix[J].Computer Engineer and Applications,2006,42(6):4-6(in Chinese) 徐章艳,杨炳儒,宋威.一个基于差别矩阵的快速求核算法[J].计算机工程与应用,2006,42(6):4-6
[22] Xu Zhang-yan,Yang Bing-ru,Cai Wei-dong,et al.Quick algorithm for computing core based on the positive region [J].Systems Engineering and Electronics,2006,28(12):1902-1905(in Chinese) 徐章艳,杨炳儒,蔡卫东,等.一个基于正区域的快速求核算法[J].系统工程与电子技术,2006,28(12):1902-1905
[23] Wang Guo-yin.Rough set theory and knowledge acquisition[M].Xi’an:Xi’an Jiao Tong University Press,2011(in Chinese) 王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed