Multi-scale attribute granule based quick positive region reduction algorithm

doi:10.11772/j.issn.1001-9081.2019049238

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (12): 3426-3433.DOI: 10.11772/j.issn.1001-9081.2019049238

• The 17th China Conference on Machine Learning (CCML 2019) • Previous Articles Next Articles

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

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

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

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

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

Abstract

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

摘要： 传统启发式正域属性约简算法在每次迭代的过程中需要添加当前正域依赖度最大的属性进入已选定的特征属性子集，算法迭代次数多且效率低，难以应用于高维大规模数据集的特征选择中。针对上述问题，研究决策系统中正域之间的单调关系，给出了多尺度属性粒（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提高了算法效率，具有更好的分类精度。

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

CLC Number:

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WANG Xiaorong, ZHANG Yuzhao, ZHANG Zhenjiang. Selection of express freight transportation schemes based on rough set over two universes [J]. Journal of Computer Applications, 2021, 41(5): 1500-1505.
[2]	PENG Li, ZHANG Haiqing, LI Daiwei, TANG Dan, YU Xi, HE Lei. Imputation algorithm for hybrid information system of incomplete data analysis approach based on rough set theory [J]. Journal of Computer Applications, 2021, 41(3): 677-685.
[3]	WANG Lei. Network intrusion detection method based on improved rough set attribute reduction and K-means clustering [J]. Journal of Computer Applications, 2020, 40(7): 1996-2002.
[4]	ZHANG Wu, CHEN Hongmei. Hyperspectral band selection based on multi-kernelized fuzzy rough set and grasshopper optimization algorithm [J]. Journal of Computer Applications, 2020, 40(5): 1425-1430.
[5]	ZHANG Xiajie, ZHU Jinghua, CHEN Yang. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[6]	OU Binli, ZHONG Xiaru, DAI Jianhua, YANG Tian. Intrusion detection method based on variable precision covering rough set [J]. Journal of Computer Applications, 2020, 40(12): 3465-3470.
[7]	LI Ziying, SHI Zhenguo. Scheduling method for big data tasks [J]. Journal of Computer Applications, 2020, 40(10): 2923-2928.
[8]	ZHANG Wu, CHEN Hongmei. Hyperspectral band selection algorithm based on kernelized fuzzy rough set [J]. Journal of Computer Applications, 2020, 40(1): 258-263.
[9]	BAO Di, ZHANG Nan, TONG Xiangrong, YUE Xiaodong. Incremental attribute reduction algorithm of positive region in interval-valued decision tables [J]. Journal of Computer Applications, 2019, 39(8): 2288-2296.
[10]	XU Yi, XIAO Peng. Dynamic updating method of approximations in multigranulation rough sets based on tolerance relation [J]. Journal of Computer Applications, 2019, 39(5): 1247-1251.
[11]	KONG Heqing, ZHANG Nan, YUE Xiaodong, TONG Xiangrong, YU Tianyou. Positive region preservation reduction based on multi-specific decision classes in incomplete decision systems [J]. Journal of Computer Applications, 2019, 39(5): 1252-1260.
[12]	ZHENG Wenbin, LI Jinjin, YU Peiqiu, LIN Yidong. Matrix-based algorithm for updating approximations in variable precision multi-granulation rough sets [J]. Journal of Computer Applications, 2019, 39(11): 3140-3145.
[13]	TAN Yongqi, FAN Jiancong, REN Yande, ZHOU Xiaoming. Improved attribute reduction algorithm and its application to prediction of microvascular invasion in hepatocellular carcinoma [J]. Journal of Computer Applications, 2019, 39(11): 3221-3226.
[14]	LI Xu, RONG Zijing, RUAN Xiaoxi. Attribute reduction of relative indiscernibility relation and discernibility relation in relation decision system [J]. Journal of Computer Applications, 2019, 39(10): 2852-2858.
[15]	YUAN Zhong, FENG Shan. Outlier detection algorithm based on neighborhood value difference metric [J]. Journal of Computer Applications, 2018, 38(7): 1905-1909.