粗等价粒度下基于多种加速策略的增量式求核算法

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

摘要/Abstract

摘要： 提出一种全新的渐增式求核算法。首先基于全局等价类提出粗等价类概念并分析其性质,研究粗等价类下的求核与约简；深入研究3类粗等价类与核属性的内在联系,设计粗等价类下判断核属性的等价方法和渐增式求核方法,通过该方法可在一次增量计算中求得多个非核属性,从而设计双向剪枝策略；可从属性和实体双方面缩减计算域,无需遍历全部属性和实体,在无核情况下,剪枝策略仍然有效。设计多次Hash的属性增量划分算法来完成上述增量式计算,基于此给出完整的渐增式求核算法。最后用UCI中20个决策表及海量、超高维3类数据集从多个角度进行验证,实验结果证明了所提算法的有效性和高效性,其尤其适用于大型决策表,大多数情况下优于现有算法。算法可进一步作为新型约简和优化算法的基础。

关键词: 粗糙约简,粗等价类,渐增式求核,Hash

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

赵洁,张恺航,董振宁,梁俊杰,徐克付. 粗等价粒度下基于多种加速策略的增量式求核算法[J]. 计算机科学, 2017, 44(1): 226-234. https://doi.org/10.11896/j.issn.1002-137X.2017.01.043

ZHAO Jie, ZHANG Kai-hang, DONG Zhen-ning, LIANG Jun-jie and XU Ke-fu. Granularity of Rough Equivalence Class Based Incremental Attribute Core Computation Using Multiple Accelerating Strategies Pruning and Multiple Hashing[J]. Computer Science, 2017, 44(1): 226-234. https://doi.org/10.11896/j.issn.1002-137X.2017.01.043

参考文献

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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed