基于多尺度属性粒策略的快速正域约简算法

doi:10.11772/j.issn.1001-9081.2019049238

计算机应用 ›› 2019, Vol. 39 ›› Issue (12): 3426-3433.DOI: 10.11772/j.issn.1001-9081.2019049238

• 第十七届中国机器学习会议(CCML 2019)论文 • 上一篇下一篇

基于多尺度属性粒策略的快速正域约简算法

陈曼如^1,2, 张楠^1,2, 童向荣^1,2, 东野升龙^1,2, 杨文静^1,2

1. 数据科学与智能技术山东省高校重点实验室(烟台大学), 山东烟台 264005;
2. 烟台大学计算机与控制工程学院, 山东烟台 264005

收稿日期:2019-04-29 修回日期:2019-07-03 出版日期:2019-12-10 发布日期:2019-08-26
作者简介:陈曼如(1993-),女,宁夏银川人,硕士研究生,主要研究方向:粗糙集、数据挖掘、机器学习;张楠(1979-),男,山东烟台人,讲师,博士,CCF会员,主要研究方向:粗糙集、粒计算、人工智能;童向荣(1975-),男,山东烟台人,教授,博士,主要研究方向:多智能体系统、分布式人工智能;东野升龙(1996-),男,山东临沂人,主要研究方向:粗糙集、数据挖掘、人工智能;杨文静(1996-),女,山东济宁人,硕士研究生,主要研究方向:粗糙集、数据挖掘、机器学习。
基金资助:
国家自然科学基金资助项目（61572418，61572419，11801491）；山东省自然科学基金资助项目（ZR2018BA004）。

Multi-scale attribute granule based quick positive region reduction algorithm

CHEN Manru^1,2, ZHANG Nan^1,2, TONG Xiangrong^1,2, DONGYE Shenglong^1,2, YANG Wenjing^1,2

1. Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes(Yantai University), Yantai Shandong 264005, China;
2. School of Computer Science and Control Engineering, Yantai University, Yantai Shandong 264005, China

Received:2019-04-29 Revised:2019-07-03 Online:2019-12-10 Published:2019-08-26
Contact: 张楠
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572418, 61572419, 11801491), the Natural Science Foundation of Shandong Province (ZR2018BA004).

摘要/Abstract

摘要： 传统启发式正域属性约简算法在每次迭代的过程中需要添加当前正域依赖度最大的属性进入已选定的特征属性子集，算法迭代次数多且效率低，难以应用于高维大规模数据集的特征选择中。针对上述问题，研究决策系统中正域之间的单调关系，给出了多尺度属性粒（MSAG）的形式化描述，提出了一种基于多尺度属性粒的快速正域约简算法（MAG-QPR）。由于多尺度属性粒包含多个属性，可以对已选定的特征属性子集提供较大的正域，因此，通过每次迭代添加MSAG，可以达到减少迭代次数和使选定的特征属性子集能更快地趋近于条件属性全集的正域分辨能力的目的，从而提高了启发式正域约简算法的效率。在实验部分，选取8组UCI数据进行实验，对于数据集Lung Cancer、Flag和German，MAG-QPR与基于正向近似的正域保持属性约简算法（FSPA-PR）、基于正向近似的条件熵属性约简算法（FSPA-SCE）、后向贪婪正域保持属性约简算法（BGRAP）和后向贪婪启发式广义决策保持属性约简算法（BGRAG）的运行时间加速比分别为9.64、15.70、5.03、2.50；3.93、7.55、1.69、4.57；3.61、6.49、1.30、9.51。实验结果表明，所提算法MAG-QPR提高了算法效率，具有更好的分类精度。

关键词: 属性约简, 粗糙集, 多尺度属性粒, 正域约简, 快速约简算法

Abstract: In classical heuristic attribute reduction algorithm for positive region, the attribute with the maximum dependency degree of the current positive domain should be added into the selected feature attribute subset in each iteration, leading to the large number of iterations and the low efficiency of the algorithm, and making the algorithm hard to be applied in the feature selection of high-dimensional and large-scale datasets. In order to solve the problems, the monotonic relationship between the positive regions in a decision system was studied and the formal description for the Multi-Scale Attribute Granule (MSAG) was given, and a Multi-scale Attribute Granule based Quick Positive Region reduction algorithm (MAG-QPR) was proposed. Each MSAG contains several attributes and can provide a large positive region for the selected feature attribute subset. As a result, adding MSAG in each iteration can reduce the number of the iteration and make the selected feature attribute subset more quickly approach to the positive region resolving ability of the condition attribute universal set. Therefore, the computational efficiency of the heuristic attribute reduction algorithm for positive region is improved. With 8 UCI datasets used for experiments, on the datasets Lung Cancer, Flag and German, the running time acceleration ratios of MAG-QPR to the general improved Feature Selection algorithm based on the Positive Approximation-Positive Region (FSPA-PR), the general improved Feature Selection algorithm based on the Positive Approximation-Shannon's Conditional Entropy (FSPA-SCE), the Backward Greedy Reduction Algorithm for positive region Preservation (BGRAP) and the Backward Greedy Reduction Algorithm for Generalized decision preservation (BGRAG) are 9.64, 15.70, 5.03, 2.50; 3.93, 7.55, 1.69, 4.57; and 3.61, 6.49, 1.30, 9.51 respectively. The experimental results show that, the proposed algorithm MAG-QPR can improve the algorithm efficiency and has better classification accuracy.

Key words: attribute reduction, rough set, multi-scale attribute granule, positive region reduction, quick reduction algorithm

中图分类号:

陈曼如, 张楠, 童向荣, 东野升龙, 杨文静. 基于多尺度属性粒策略的快速正域约简算法[J]. 计算机应用, 2019, 39(12): 3426-3433.

CHEN Manru, ZHANG Nan, TONG Xiangrong, DONGYE Shenglong, YANG Wenjing. Multi-scale attribute granule based quick positive region reduction algorithm[J]. Journal of Computer Applications, 2019, 39(12): 3426-3433.

参考文献

[1] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5):341-356.
[2] 王国胤,姚一豫,于洪.粗糙集理论与应用研究综述[J].计算机学报,2009,32(7):1229-1246.(WANG G Y, YAO Y Y, YU H. A survey on rough set theory and applications[J]. Chinese Journal of Computers, 2009, 32(7):1229-1246.)
[3] MIAO D, ZHAO Y, YAO Y, et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model[J]. Information Sciences, 2009, 179(24):4140-4150.
[4] LI H, LI D, ZHAI Y, et al. A novel attribute reduction approach for multi-label data based on rough set theory[J]. Information Sciences, 2016, 367/368:827-847.
[5] YAO Y, ZHAO Y. Attribute reduction in decision-theoretic rough set models[J]. Information Sciences, 2008, 178(17):3356-3373.
[6] JIA X, SHANG L, ZHOU B, et al. Generalized attribute reduct in rough set theory[J]. Knowledge-Based Systems, 2016, 91(6):204-218.
[7] 张楠,苗夺谦,岳晓冬.区间值信息系统的知识约简[J].计算机研究与发展,2010,47(8):1362-1371.(ZHANG N, MIAO D Q, YUE X D. Approaches to knowledge reduction in interval-valued information systems[J]. Journal of Computer Research and Development, 2010, 47(8):1362-1371.)
[8] HU Q, ZHAO H, XIE Z, et al. Consistency based attribute reduction[C]//Proceedings of the 2007 Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNCS 4426. Berlin:Springer, 2007:96-107.
[9] GUAN Y Y, WANG H K. Set-valued information systems[J]. Information Sciences. 2006, 176(17):2507-25-25.
[10] SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[M]//SŁOWINSKI R. Intelligent Decision Support:Handbook of Applications and Advances to Rough Sets Theory. Dordrecht:Kluwer Academic Publishers, 1992:331-362.
[11] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(|C||U|), O(|C|²|U/C|))的快速属性约简算法[J].计算机学报,2006,29(3):391-399.(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|²|U/C|))[J]. Chinese Journal of Computers, 2006, 29(3):391-399.)
[12] 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/10):597-618.
[13] LIANG J, MI J, WEI W, et al. An accelerator for attribute reduction based on perspective of objects and attributes[J]. Knowledge-Based Systems, 2013, 44:90-100.
[14] 葛浩,李龙澍,杨传健.基于冲突域的高效属性约简算法[J].计算机学报,2012,35(2):342-350.(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.)
[15] 王熙照,王婷婷,翟俊海.基于样例选取的属性约简算法[J].计算机研究与发展,2012,49(11):2305-2310.(WANG X Z, WANG T T, ZHAI J H. An attribute reduction algorithm based on instance selection[J]. Journal of Computer Research and Development, 2012, 49(11):2305-2310.)
[16] 杨习贝,颜旭,徐苏平,等.基于样本选择的启发式属性约简方法研究[J].计算机科学,2016,43(1):40-43.(YANG X B, YAN X, XU S P, et al. New heuristic attribute reduction algorithm based on sample selection[J]. Computer Science, 2016, 43(1):40-43.)
[17] CHEN H, LI T, RUAN D, et al. A rough-set-based incremental approach for updating approximations under dynamic maintenance environments[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(2):274-284.
[18] CHEN H, LI T R, LUO C, et al. A rough set-based method for updating decision rules on attribute values' coarsening and refining[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(12):2886-2899.
[19] TENG S, LU M, YANG A, et al. Efficient attribute reduction from the viewpoint of discernibility[J]. Information Sciences, 2016, 326:297-314.
[20] SHU W, QIAN W. A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems[J]. Knowledge-Based Systems, 2014, 72:60-71.
[21] RAZA M S, QAMAR U. Feature selection using rough set-based direct dependency calculation by avoiding the positive region[J]. International Journal of Approximate Reasoning, 2018, 92:175-197.
[22] 苗夺谦,李道国.粗糙集理论、算法与应用[M].北京:清华大学出版社,2008:87-214.(MIAO D Q, LI D G. Rough Sets Theory Algorithms and Applications[M]. Beijing:Tsinghua University Press, 2008:87-214.)
[23] JING Y G, LI T, HUANG J, et al. A group incremental reduction algorithm with varying data values[J]. International Journal of Intelligent Systems, 2017, 32(9):900-925.
[24] JING Y, LI T, FUJITA H, et al. An incremental attribute reduction method for dynamic data mining[J]. Information Sciences, 2018, 465:202-218.
[25] 高学义.多目标属性约简研究[D].烟台:烟台大学,2018:16-30.(GAO X Y. Researches on multi-objective attribute reduction[D].Yantai:Yantai University, 2018:16-30.)

基于多尺度属性粒策略的快速正域约简算法

Multi-scale attribute granule based quick positive region reduction algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王小荣, 张玉召, 张振江. 基于双论域粗糙集的快捷货物运输方案选择[J]. 计算机应用, 2021, 41(5): 1500-1505.
[2]	彭莉, 张海清, 李代伟, 唐聃, 于曦, 何磊. 基于粗糙集理论的不完备数据分析方法的混合信息系统填补算法[J]. 计算机应用, 2021, 41(3): 677-685.
[3]	王磊. 改进粗糙集属性约简结合K-means聚类的网络入侵检测方法[J]. 计算机应用, 2020, 40(7): 1996-2002.
[4]	张伍, 陈红梅. 基于多核模糊粗糙集与蝗虫优化算法的高光谱波段选择[J]. 计算机应用, 2020, 40(5): 1425-1430.
[5]	章夏杰, 朱敬华, 陈杨. Spark下的分布式粗糙集属性约简算法[J]. 计算机应用, 2020, 40(2): 518-523.
[6]	欧彬利, 钟夏汝, 代建华, 杨田. 基于变精度覆盖粗糙集的入侵检测方法[J]. 计算机应用, 2020, 40(12): 3465-3470.
[7]	李孜颖, 石振国. 面向大数据任务的调度方法[J]. 计算机应用, 2020, 40(10): 2923-2928.
[8]	张伍, 陈红梅. 基于核模糊粗糙集的高光谱波段选择算法[J]. 计算机应用, 2020, 40(1): 258-263.
[9]	鲍迪, 张楠, 童向荣, 岳晓冬. 区间值决策表的正域增量式属性约简算法[J]. 计算机应用, 2019, 39(8): 2288-2296.
[10]	徐怡, 肖鹏. 基于容差关系的多粒度粗糙集中近似集动态更新方法[J]. 计算机应用, 2019, 39(5): 1247-1251.
[11]	孔贺庆, 张楠, 岳晓冬, 童向荣, 于天佑. 基于多特定决策类的不完备决策系统正域约简[J]. 计算机应用, 2019, 39(5): 1252-1260.
[12]	郑文彬, 李进金, 于佩秋, 林艺东. 变精度多粒度粗糙集近似集更新的矩阵算法[J]. 计算机应用, 2019, 39(11): 3140-3145.
[13]	谭永奇, 樊建聪, 任延德, 周晓明. 改进的属性约简算法及其在肝癌微血管侵犯预测中的应用[J]. 计算机应用, 2019, 39(11): 3221-3226.
[14]	李旭, 荣梓景, 阮晓曦. 关系决策系统中相对不可区分和区分关系的约简[J]. 计算机应用, 2019, 39(10): 2852-2858.
[15]	袁钟, 冯山. 基于邻域值差异度量的离群点检测算法[J]. 计算机应用, 2018, 38(7): 1905-1909.