基于全局正区域不一致性的快速求核算法

摘要/Abstract

摘要： 首先基于改进的Hash和位运算设计了快速等价类与正区域算法,将其作为求核基础；然后设计基于全局正区域不一致性的快速求核算法。区别于现有算法在求核过程中需要反复多次求正区域,深入分析了核属性a_i的特征,捕捉两类C－{a_i}所形成的正区域与全局正区域的不一致,不需要反复求完整的C－{a_i}正区域,通过3个定理证明了基于全局正区域不一致性识别核属性的正确性和有效性。使用UCI中21个数据集、超高维和海量数据集进行全面检验,结果表明无论是多/少实体、多/少属性和有/无核的决策表,本算法在大部分情况下都优于现有同类算法,尤其适用于大型决策表。

关键词: 粗糙集,核属性,全局正区域,不一致性

Abstract: This paper firstly proposed basic algorithms of positive region and equivalence class based on bit vector and improved Hash algorithm.Then the core attributes computation algorithm was designed based on global positive region inconsistency.Different from current algorithms which need to compute complete positive regions repeatedly when seeking attributes core,this paper studied the characteristics of core attributes,and caught the inconsistencies between the positive region of C－{a_i} and the global positive region.The complete positive regions of C－{a_i} don’t need to be computed repeatedly.Global positive region inconsistency based attributes core recognition was proved by 3 theories.21 data sets of UCI,ultra-high-dimensional data sets and massive data sets were used to test the algorithms proposed by this paper.And the results show the attributes core computation algorithm of this paper owns good performance no matter when the number of entities and attributes is more or less and especially is suitable for processing large decision table.

Key words: Rough set,Attributes core,Global positive region,Inconsistency

赵洁,梁俊杰,董振宁,陈旭,唐德育. 基于全局正区域不一致性的快速求核算法[J]. 计算机科学, 2015, 42(8): 259-264. https://doi.org/

ZHAO Jie, LIANG Jun-jie, DONG Zhen-ning, CHEN Xu and TANG De-yu. Global Positive Region Inconsistency Based Attributes Core Computation[J]. Computer Science, 2015, 42(8): 259-264. https://doi.org/

参考文献

[1] Pawlak Z.Rough sets[J].International Journal of Computer & Information Sciences,1982,11(5):341-356
[2] 王珏,王任,苗夺谦,等.基于Rough Set理论的“数据浓缩”[J].计算机学报,1998,21(5):393-400 Wang Jue,Wang Ren,Miao Duo-qian,et al.Data enriching based on rough set theory[J].Chinese Journal of Computers,1998,1(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] Yang T,Li Q,Zhou B.Related family:A new method for attri-bute reduction of covering information systems[J].Information Sciences,2013,228:175-191
[5] Zhang Z,Tian J.On Attribute Reduction with IntuitionisticFuzzy Rough Sets[J].International Journal of Uncertainty,Fuzziness and Knowledge-based Systems,2012,20(1):59-76
[6] Chen D,Hu Q,Yang Y.Parameterized attribute reduction with Gaussian kernel based fuzzy rough sets[J].Information Sciences,2011,181(23):5169-5179
[7] Bedi P,Chawla S.Use of fuzzy rough set attribute reduction in high scent web page recommendations[M]∥Rough Sets,Fuzzy Sets,Data Mining and Granular Computing.Springer,2009:192-200
[8] 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
[9] Meng Z,Shi Z.Extended rough set-based attribute reduction in inconsistent incomplete decision systems[J].Information Sciences,2012,204:44-69
[10] Qian Y,Liang J,Pedrycz W,et al.Positive approximation:An accelerator for attribute reduction in rough set theory[J].Artificial Intelligence,2010,174(9):597-618
[11] 葛浩,李龙澍,杨传健.基于冲突的增量式核属性更新算法[J].控制与决策,2011,26(7):984-990 Ge Hao,Li Long-shu,Yang Chuan-jian.Incremental updating algorithm of the computation of core based on the collision[J].Control and Decision,2011,6(7):984-990
[12] 冯少荣,张东站.一种高效的增量式属性约简算法[J].控制与决策,2011,26(4):495-500 Feng Shao-rong,Zhang Dong-zhan.Effective increment algorithm for attribute reduction[J].Control and Decision,2011,6(4):495-500
[13] 杨传健,葛浩,李龙澍.垂直划分二进制可分辨矩阵的属性约简[J].控制与决策,2013,28(4):563-568 Yang Chuan-jian,Ge Hao,Li Long-shu.Attribute reduction of vertically partitioned binary discernibility matrix[J].Control and Decision,2013,8(4):563-568
[14] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-822 Yang Ming.An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J].Chinese Journal of Computers,2007,0(5):815-822
[15] 刘少辉,盛秋戬,吴斌,等.Rough 集高效算法的研究[J].计算机学报,2003,26(5):524-529 Liu Shao-hui,Sheng Qiu-jian,Wu Bin,et al.Research on efficient algorithms for rough set methods[J].Chinese Journal of Computers,2003,6(5):524-529
[16] 刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法[J].计算机研究与发展,2003,40(5):637-642 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,0(5):637-642
[17] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max (O (|C|| U|),O (|C∧2|U/C|)) 的快速属性约简算法[J].计算机学报,2006,29(3):391-399 Xu Zhang-yan,Liu Zuo-ping,Yang Bing-ru,et al.Quick attribute reduction algorithm with complexity of max(O(|C||U|),O(|C|∧2)|U/C|))[J].Chinese Journal of Computers,2006,9(3):391-399
[18] 刘勇,熊蓉,褚健.Hash 快速属性约简算法[J].计算机学报,2009(8):1493-1499 Liu Yong,Xiong Rong,Chu Jian.Quick attribute reduction algorithm with hash[J].Chinese Journal of Computers,2009,2(8):1493-1499
[19] 葛浩,李龙澍,杨传健.基于冲突域的高效属性约简算法[J].计算机学报,2012,35(2):342-350 Ge Hao,Li Long-shu,Yang Chuan-jian.An efficient attribute reduction algorithm based on conflict region[J].Chinese Journal of Computers,2012,5(2):342-350
[20] 葛浩,李龙澍,杨传健.一种核属性快速求解算法[J].控制与决策,2009,24(5):738-742 Ge Hao,Li Long-shu,Yang Chuan-jian.Quick algorithm for computing core attribute[J].Control and Decision,2009,4(5):738-742
[21] 葛浩,杨传健,李龙澍.一种高效的核属性求解算法[J].计算机工程与应用,2010,46(26):138-141 Ge Hao,Li Long-shu,Yang Chuan-jian.Efficient algorithm for computing core attributes[J].Computer Engineering and Applications,2010,6(26):138-141
[22] 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