Computer Science ›› 2017, Vol. 44 ›› Issue (1): 226-234, 258.doi: 10.11896/j.issn.1002-137X.2017.01.043

Previous Articles     Next Articles

Granularity of Rough Equivalence Class Based Incremental Attribute Core Computation Using Multiple Accelerating Strategies Pruning and Multiple Hashing

ZHAO Jie, ZHANG Kai-hang, DONG Zhen-ning, LIANG Jun-jie and XU Ke-fu   

  • Online:2018-11-13 Published:2018-11-13

Abstract: A new incremental core computation algorithm was proposed.Firstly,rough equivalence class(REC) was proposed based on the smallest computational granularity of global equivalences,the character of REC was analyzed and core and reduction computation under REC was studied.Then relationship of core attributes and REC were studied and then an equal method of judging core attribution and incremental core computation method based on 0-REC were designed,through which multiple non-core attributions can be gained in one calculation.Based on which,bilateral pruning strategies were proposed to reduce calculation field of both attributes and entities,so it need not travel all the attributes and entities.The pruning strategies still work even there is no core.At last,20 decision sets of UCI,massive and ultra-high dimension were used to verify the strategies and algorithms.The results show that the algorithm is effective and efficient,and in most conditions,the algorithm of this paper is superior to the current algorithms,and fit for massive decision table especially.The algorithm can be the basis of new reduction and optimization algorithms.

Key words: Reduction under rough set,Rough equivalence class,Incremental core computation,Hash

[1] PAWLAK Z.Rough sets[J].International Journal of Computer & Information Sciences,1982,11(5):341-356.
[2] WANG J,WANG R,MIAO D Q.Data enriching based on rough set theory[J].Chinese Journal of Computers,1998,21(5):393-400.(in Chinese) 王珏,王任,苗夺谦.基于 Rough Set 理论的 “数据浓缩”[J].计算机学报,1998,21(5):393-400.
[3] WANG C,HE Q,CHEN D,et al.A novel method for attribute reduction of covering decision systems[J].Information Sciences,2014,254:181-196.
[4] WANG C,SHAO M,SUN B,et al.An improved attribute reduction scheme with covering based rough sets[J].Applied Soft Computing,2015,26:235-243.
[5] Tsang E C,Chen D,Yeung D S,et al.Attributes reduction using fuzzy rough sets[J].IEEE Transactions on Fuzzy Systems,2008,16(5):1130-1141.
[6] ZHANG Z,TIAN J.On Attribute Reduction with Intuitionstic Fuzzy Rough Sets[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2012,20(1):59-76.
[7] CHEN D,LI W,ZHANG X,et al.Evidence-theory-based nu-merical algorithms of attribute reduction with neighborhood-covering rough sets[J].International Journal of Approximate Reasoning,2014,55(3):908-923.
[8] FENG T,ZHANG S,MI J.The reduction and fusion of fuzzy covering systems based on the evidence theory[J].International Journal of Approximate Reasoning,2012,53(1):87-103.
[9] QIAN Y,LIANG J,PEDRYCZ W,et al.An efficient accelerator for attribute reduction from incomplete data in rough set framework[J].Pattern Recognition,2011,44(8):1658-1670.
[10] ZHENG K,HU J,ZHAN Z,et al.An enhancement for heuristic attribute reduction algorithm in rough set[J].Expert Systems with Applications,2014,41(15):6748-6754.
[11] LIU S H,SHENG S J,WU B,et al.Research on Efficient Algorithms for Rough Set Methods[J].Chinese Journal of Compu-ters,2003,26(5):524-529.(in Chinese) 刘少辉,盛秋戬,吴斌,等.Rough 集高效算法的研究[J].计算机学报,2003,26(5):524-529.
[12] LIU S H,SHENG Q J,SHI Z Z.A New Method for Fast Com-puting Positive Region[J].Journal of Computer Research and Development,2003,40(5):637-642.(in Chinese) 刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法[J].计算机研究与发展,2003,40(5):637-642.
[13] XU Z Y,LIU Z P,YANG B R,et al.A Quick Attribute Reduction Algorithm with Complexity of max (O(|C||U|),O(|C∧2|U/C|))[J].Chinese Journal of Computers,2006,29(3):391-399.(in Chinese) 徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(|C||U|),O(|C∧2|U/C|))的快速属性约简算法[J].计算机学报,2006,29(3):391-399.
[14] LIU Y,XIONG R,CHU J.Quick Attribute Reduction Algo-rithm with Hash[J].Chinese Journal of Computers,2009(8):1493-1499.(in Chinese) 刘勇,熊蓉,褚健.Hash快速属性约简算法[J].计算机学报,2009(8):1493-1499.
[15] GE H,LI L S,YANG C J.An Efficient Attribute Reduction Algorithm Based on Conflict Region[J].Chinese Journal of Computers,2012,35(2):342-350.(in Chinese) 葛浩,李龙澍,杨传健.基于冲突域的高效属性约简算法[J].计算机学报,2012,35(2):342-350.
[16] GE H,LI L S,YANG C J.Attribute Reduction Algorithm Based on Conflict Region Decreasing[J].Systems Engineering-Theory & Practice,2013,33(9):2371-2380.(in Chinese) 葛浩,李龙澍,杨传健.基于冲突域渐减的属性约简算法[J].系统工程理论与实践,2013,33(9):2371-2380.
[17] HEDAR A,WANG J,FUKUSHIMA M.Tabu search for attri-bute reduction in rough set theory[J].Soft Computing,2008,12(9):909-918.
[18] DING Wei-ping,WANG Jing-dong,GUAN Zhi-jin.Efficientrough attribute reduction based on Quantum Frog-leaping co-evolution[J].Acta Electronica sinica,2011,39(11):2597-2603.(in Chinese) 丁卫平,王建东,管致锦.基于量子蛙跳协同进化的粗糙属性快速约简[J].电子学报,2011,39(11):2597-2603.
[19] TAO Xin-min,WANG Yan,XU Jing,et al.Minimum rough set attribute reduction algorithm based on virus-coordinative discrete particle swarm optimization[J].Control and decision,2012,27(2):259-265.(in Chinese) 陶新民,王妍,徐晶,等.求解最小属性约简的病毒协同进化微粒群算法[J].控制与决策,2012,27(2):259-265.
[20] DING W,WANG J.A Novel Approach to Minimum Attribute Reduction based on Quantum-inspired Self-adaptive Cooperative Co-evolution[J].Knowledge-Based Systems,2013,50(3):1-13.
[21] GE H,LI L S,YANG C J.Incremental updating algorithm of the computation of core based on the collision[J].Control and Decision,2011,26(7):984-990.(in Chinese) 葛浩,李龙澍,杨传健.基于冲突的增量式核属性更新算法[J].控制与决策,2011,26(7):984-990.
[22] YANG M.An Incremental Updating Algorithm of the Computation of a Core Based on the Improved Discernibility Matrix[J].Chinese Journal of Computers,2006,29(3):407-413.(in Chinese) 杨明.一种基于改进差别矩阵的核增量式更新算法[J].计算机学报,2006,29(3):407-413.
[23] GE H,LI L S,YANG C J.Quick algorithm for computing core attribute[J].Control and Decision,2009,24(5):738-742.(in Chinese) 葛浩,李龙澍,杨传健.一种核属性快速求解算法[J].控制与决策,2009,24(5):738-742.
[24] GE H,LI L S,YANG C J.Efficient algorithm for computing core attributes[J].Computer Engineering and Applications,2010,46(26):138-141.(in Chinese) 葛浩,杨传健,李龙澍.一种高效的核属性求解算法[J].计算机工程与应用,2010,46(26):138-141.
[25] ZHAO Jie,LIANG Jun-jie,DONG Zhen-ning,et al.Global positive region inconsistency based Attributes Core computation [J].Computer Science,2015,42(8):259-264.(in Chinese) 赵洁,梁俊杰,董振宁,等.基于全局正域不一致性的快速求核算法[J].计算机科学,2015,42(8):259-264.
[26] ZHAO Jie,DONG Zheng-yu,ZHANG Kan-hang.Rough equivalence Class Based Attribute Reduction Algorithm with Bilateral-pruning strategies and Multiple Hashing[J].Control and Decision,2016,3(11):1921-1934(in Chinese) 赵洁,董振宁,张恺航.粗等价类双边剪枝策略下多次Hash的约简算法[J].控制与决策,2016,3(11):1921-1934.
[27] HU F,WANG G,XIA Y.Attribute core computation based on divide and conquer method[M].Rough Sets and Intelligent Systems Paradigms,Springer,2007:310-319.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .