Computer Science ›› 2019, Vol. 46 ›› Issue (12): 250-256.doi: 10.11896/jsjkx.181102031

• Artificial Intelligence • Previous Articles     Next Articles

Multi-scale Based Accelerator for Attribute Reduction

JIANG Ze-hua1, WANG Yi-bo2, XU Gang3, YANG Xi-bei1, WANG Ping-xin4   

  1. (School of Computer Science,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212003,China)1;
    (School of Computer Science and Engineering,Southeast University,Nanjing 211189,China)2;
    (School of Naval Architecture and Ocean Engineering,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212003,China)3;
    (School of Science,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212003,China)4
  • Received:2018-11-04 Online:2019-12-15 Published:2019-12-17

Abstract: The neighborhood rough set measures the similarity between samples by radius,consequently,different radii naturally construct the rough approximations with different scales.Traditional attribute reduction based on neighborhood rough set is frequently executed over multi-radius.The aims are to select an attribute subset with better generalization performance or to explore the trend line of the performances of the reducts in terms of different scales.However,it should be emphasized that the process should be repeatedly executed for each scale,if the traditional algorithm based on heuristic searching is used to compute the multiple scale reducts.The time consumption of computing reducts is too high to be accepted,especially the number of the scale is more,the time consumption will be more.To solve such a problem,the multi-scale based accelerated strategy for attribute reduction was proposed by means of the changing of radius.This strategy considers two trends of changing radius,from smaller radius to greater radius and from greater radius to smaller radius.Moreover,the traversal size of samples and attributes is reduced.Therefore,the current process to find reduct is executed based on the reduct related to the previous radius,which follows that the forward or backward heuristic searching for adding and deleting attributes can be realized.To validate the effectiveness of the accelerated strategy,8 UCI data sets,10-fold cross-validation and 20 radii were employed to conduct the experiment,and the time consumption of computing different reducts and the classification of different reducts were compared.The experimental results over 8 UCI data sets show that the proposed forward or backward accelerated searching can significantly reduce the time consumptions of finding reducts if the case of multi-scale is considered.Moreover,the proposed approach will not significantly decrease the classification performance,and can reduce the degree of over-fitting.

Key words: Attribute reduction, Heuristic searching, Multi-scale, Neighborhood rough set

CLC Number: 

  • TP181
[1]PAWLAK Z.Rough Sets[J].International Journal of Computer & Information Sciences,1982,11(5):341-356.
[2]DAI J H,GAO S C,ZHENG G J.Generalized Rough Set Models Determined by Multiple Neighborhoods Generated from a Similarity Relation[J].Soft Computing,2018,22(7):2081-2094.
[3]QIAN Y H,LIANG X Y,WANG Q,et al.Local Rough Set:A Solution to Rough Data Analysis in Big Data[J].International Journal of Approximate Reasonging,2018,97(1):38-63.
[4]HU Q H,AN S,YU D R.Soft Fuzzy Rough Sets for Robust Feature Evaluation and Selection[J].Information Sciences,2010,180(22):4384-4400.
[5]MIAO D Q,GAO C,ZHANG N,et al.Diversereduct Subspaces Based Co-training for Partially Labeled Data[J].International Journal of Approximate Reasoning,2011,52(8):1103-1117.
[6]CHEN H M,LI T R,LUO C,et al.A Decision-theoretic Rough Set Approach for Dynamic Data Mining[J].IEEE Transactions on Fuzzy Systems,2015,23(6):1958-1970.
[7]TAO F,MI J S.Variable Precision Multigranulation Decision- theoretic Fuzzy Rough Sets[J].Knowledge-Based Systems,2016,91(1):93-101.
[8]QIAN Y H,CHENG H H,WANG J T,et al.Grouping Granular Structures in Human Granulation Intelligence[J].Information Sciences,2017,382/383:150-169.
[9]CHEN Y F,YUE X D,FUJITA H.Three-way Decision Support for Diagnosis on Focal Liver Lesions[J].Knowledge-Based Systems,2017,127(C):85-99.
[10]LIU D,LIANG D C,WANG C C.A Novel Three-way Decision Model Based on Incomplete Information System[J].Knowledge-Based Systems,2016,91(C):32-45.
[11]HU Q H,PAN W W,ZHANG L,et al.Feature Selection for Monotonic Classification[J].IEEE Transactions on Fuzzy Systems,2012,20(1):69-81.
[12]JIA X Y,LIAO W H,TANG Z M,et al.Minimum Cost Attri- bute Reduction in Decision-theoretic Rough Set Models[J].Information Sciences,2013,219(1):151-167.
[13]MIN F,ZHU W.Attribute Reduction of Data with Error Ranges and Test Costs[J].Information Sciences,2012,211:48-67.
[14]SONG J J,TSANG E C C,CHEN D G,et al.Minimal Decision Cost Reduct in Fuzzy Decision-theoretic Rough Set Model[J].Knowledge-Based Systems,2017,126(C):104-112.
[15]JU H R,LI H X,YANG X B,et al.Cost-sensitive Rough Set:A Multi-granulation Approach[J].Knowledge-Based Systems,2017,123(1):137-153.
[16]YAO Y Y,ZHANG X Y.Class-specific Attribute Reducts in Rough Set Theory[J].Information Sciences,2017,418/419:601-618.
[17]MIN F,HE H P,QIAN Y H,et al.Test-cost-sensitive Attribute Reduction[J].Information Sciences,2011,181(22):4928-4942.
[18]YANG X B,QI Y S,SONG X N,et al.Test Cost Sensitive Multigranulation Rough Set:Model and Minimal Cost Selection[J].Information Sciences,2013,250(11):184-199.
[19]CHEN D G,YANG Y Y,DONG Z.An Incremental Algorithm for Attribute Reduction with Variable Precision Rough Sets[J].Applied Soft Computing,2016,45(1):129-149.
[20]FAN J,JIANG Y L,LIU Y.Quick Attribute Reduction with Generalized Indiscernibility Models[J].Information Sciences,2017,397/398:15-36.
[21]YAO Y Y,ZHAO Y.Discernibility Matrix Simplification for Constructing Attribute Reducts[J].Information Sciences,2009,179(7):867-882.
[22]WU W Z,QIAN Y H,LI T J,et al.On Rule Acquisition in Incomplete Multi-scale Decision Tables[J].Information Sciences,2017,378(C):282-302.
[23]ZHANG L,ZHANG B.Theory of Fuzzy Quotient Space(Methods of Fuzzy Granular Computing)[J].Journal of Software,2003,14(4):770-776.(in Chinese)
张铃,张拔.模糊熵空间理论(模糊粒度计算方法)[J].软件学报,2003,14(4):770-776.
[24]SUN L,PAN J F,ZHANG X Y,et al.Multi-label-specific Feature Selection Method Based on Neighborhood Rough Set[J].Computer Science,2018,45(1):173-178.(in Chinese)
孙林,潘俊方,张霄雨,等.一种基于邻域粗糙集的多标记专属特征选择方法[J].计算机科学,2018,45(1):173-178.
[25]XU S P,YANG X B,YU H L,et al.Neighborhood Collaborative Representation Based Classification Method[J].Computer Scie-nce,2017,44(9):234-238.(in Chinese)
徐苏平,杨习贝,于化龙,等.一种基于邻域协同表达的分类方法[J].计算机科学,2017,44(9):234-238.
[26]HU Q H,YU D R,XIE Z X.Neighborhood Classifiers[J].Expert Systems with Applications,2008,34(2):866-876.
[27]YANG X B,LIANG S C,YU H L,et al.Pseudo-label Neighbor- hood Rough Set:Measures and Attribute Reductions[J].International Journal of Approximate Reasoning,2019,105(1):115-129.
[28]WEI W,WEI Q,WANG F.Comparative Study of Uncertainty Measure in Rough Set[J].Journal of Nanjing University(Natural Sciences),2015,51(4):714-722.(in Chinese)
魏巍,魏琪,王锋.粗糙集的不确定性度量比较研究[J].南京大学学报(自然科学版),2015,51(4):714-722.
[29]ZHANG X,MEI C L,CHEN D G,et al.Feature Selection in Mixed Data:A Mehhod Using a Novel Fuzzy Rough Set-based Information Entropy[J].Pattern Recognition,2016,56(1):1-15.
[30]GAO Y,CHEN X J,YANG X B,et al.Neighborhood Attribute Reduction:A Multicriterion Strategy Based on Sample Selection[J].Information,2018,9(11):282-302.
[31]HU Q H,PEDRYCZ W,YU D R,et al.Selecting Discrete and Continuous Features Based on Neighborhood Decision Error Minimization[J].IEEE Transactions on Systems Man and Cybernetics Part B,2009,40(1):137-150.
[32]WANG C Z,HU Q H,WANG X Z,et al.Feature Selection Based on Neighborhood Discrimination Index[J].IEEE Transactions on Neural Networks and Learning Systems,2018,29(1):2986-2999.
[33]YANG X B,YAO Y Y.Ensemble Selector for Attribute Reduction[J].Applied Soft Computing,2018,70(1):1-11.
[34]LI Z Y,YANG X B,XU S P,et al.Attribute Reduction Approach to Neighborhood Decision Agreement[J].Journal of Henan Normal University(Natural Science Edition),2017,45(5):68-73.(in Chinese)
李智远,杨习贝,徐苏平,等.邻域决策一致性的属性约简方法研究[J].河南师范大学学报(自然科学版),2017,45(5):68-73.
[35]LI Z Y,YANG X B,CHEN X J,et al.Attribute Reduction Constrained by Class-specific Approximate Quality[J].Journal of Henan Normal University(Natural Science Edition),2018,46(3):112-118.(in Chinese)
李智远,杨习贝,陈向坚,等.类别近似质量约束下的属性约简方法研究[J].河南师范大学学报(自然科学版),2018,46(3):112-118.
[1] LI Yao, LI Tao, LI Qi-fan, LIANG Jia-rui, Ibegbu Nnamdi JULIAN, CHEN Jun-jie, GUO Hao. Construction and Multi-feature Fusion Classification Research Based on Multi-scale Sparse Brain Functional Hyper-network [J]. Computer Science, 2022, 49(8): 257-266.
[2] WANG Xin-tong, WANG Xuan, SUN Zhi-xin. Network Traffic Anomaly Detection Method Based on Multi-scale Memory Residual Network [J]. Computer Science, 2022, 49(8): 314-322.
[3] WEI Kai-xuan, FU Ying. Re-parameterized Multi-scale Fusion Network for Efficient Extreme Low-light Raw Denoising [J]. Computer Science, 2022, 49(8): 120-126.
[4] SUN Fu-quan, CUI Zhi-qing, ZOU Peng, ZHANG Kun. Brain Tumor Segmentation Algorithm Based on Multi-scale Features [J]. Computer Science, 2022, 49(6A): 12-16.
[5] FANG Lian-hua, LIN Yu-mei, WU Wei-zhi. Optimal Scale Selection in Random Multi-scale Ordered Decision Systems [J]. Computer Science, 2022, 49(6): 172-179.
[6] FAN Xin-nan, ZHAO Zhong-xin, YAN Wei, YAN Xi-jun, SHI Peng-fei. Multi-scale Feature Fusion Image Dehazing Algorithm Combined with Attention Mechanism [J]. Computer Science, 2022, 49(5): 50-57.
[7] CHEN Yu-si, AI Zhi-hua, ZHANG Qing-hua. Efficient Neighborhood Covering Model Based on Triangle Inequality Checkand Local Strategy [J]. Computer Science, 2022, 49(5): 152-158.
[8] SUN Lin, HUANG Miao-miao, XU Jiu-cheng. Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief [J]. Computer Science, 2022, 49(4): 152-160.
[9] WANG Zi-yin, LI Lei-jun, MI Ju-sheng, LI Mei-zheng, XIE Bin. Attribute Reduction of Variable Precision Fuzzy Rough Set Based on Misclassification Cost [J]. Computer Science, 2022, 49(4): 161-167.
[10] HU Yan-li, TONG Tan-qian, ZHANG Xiao-yu, PENG Juan. Self-attention-based BGRU and CNN for Sentiment Analysis [J]. Computer Science, 2022, 49(1): 252-258.
[11] WANG Dong, ZHOU Da-ke, HUANG You-da , YANG Xin. Multi-scale Multi-granularity Feature for Pedestrian Re-identification [J]. Computer Science, 2021, 48(7): 238-244.
[12] LI Yan, FAN Bin, GUO Jie, LIN Zi-yuan, ZHAO Zhao. Attribute Reduction Method Based on k-prototypes Clustering and Rough Sets [J]. Computer Science, 2021, 48(6A): 342-348.
[13] YUAN Xing-xing, WU Qin. Object Detection in Remote Sensing Images Based on Saliency Feature and Angle Information [J]. Computer Science, 2021, 48(4): 174-179.
[14] YANG Kun, ZHANG Juan, FANG Zhi-jun. Multi-patch and Multi-scale Hierarchical Aggregation Network for Fast Nonhomogeneous ImageDehazing [J]. Computer Science, 2021, 48(11): 250-257.
[15] ZENG Hui-kun, MI Ju-sheng, LI Zhong-ling. Dynamic Updating Method of Concepts and Reduction in Formal Context [J]. Computer Science, 2021, 48(1): 131-135.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!