Computer Science ›› 2016, Vol. 43 ›› Issue (1): 40-43.doi: 10.11896/j.issn.1002-137X.2016.01.009

Previous Articles     Next Articles

New Heuristic Attribute Reduction Algorithm Based on Sample Selection

YANG Xi-bei, YAN Xu, XU Su-ping and YU Hua-long   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Attribute reduction is one of the important topics in rough set theory.Heuristic attribute reduction algorithm with greedy strategy is one of the widely used approaches to compute reduction.Traditional heuristic algorithm uses all of the samples in the information system.However,it should be noticed that for a data set,different samples contribute different importance to find reduction,and it follows that the time efficiency of the heuristic attribute reduction algorithm suffers from the redundant samples.To solve such problem,a heuristic attribute reduction algorithm based on sample selection was proposed.The algorithm is composed of three stages.Firstly,the most informative samples are selected.Secondly,a new information system is formed by using these selected samples.Finally,one of the reductions can be computed by using heuristic algorithm.The experimental results show that the proposed algorithm can efficiently reduce the computational time.

Key words: Information system,Sample selection,Rough set,Attribute reduction

[1] Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356
[2] Luo G Z,Yang X B.Limited dominance-based rough set model and knowledge reductions in incomplete decision system[J].Journal of Information Science and Engineering,2010,26(6):2199-2211
[3] Yang H L,Li S G,Wang S Y,et al.Bipolar fuzzy rough set mo-del on two different universes and its application[J].Know-ledge-Based Systems,2012,35:94-101
[4] Wang G Y,Zhang Q H,Ma X A,et al.Granular computingmodels for knowledge uncertainty[J].Journal of Software,2011,22(4):676-694
[5] Chen J K,Li J J.An application of rough sets to graph theory[J].Information Sciences,2012,201(19):114-127
[6] Celotto E,Ellero A,Ferretti P.Short-medium term tourist ser-vices demand forecasting with Rough Set Theory[J].Procedia Economics and Finance,2012,3(12):62-67
[7] Yeh C C,Lin F,Hsu C Y.A hybrid KMV model,random forests and rough set theory approach for credit rating[J].Knowledge-Based Systems,2012,33(3):166-172
[8] Skowron A,Rauszer C.The discernibility matrices and functions in information systems[M].Kluwer Academic Publishers,1992:331-362
[9] Min F,He H P,Qian Y H,et al.Test-cost-sensitive attribute reduction[J].Information Sciences,2011,181(22):4928-4942
[10] 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
[11] 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(in Chinese)王熙照,王婷婷,翟俊海.基于样例选取的属性约简算法[J].计算机研究与发展,2012,49(11):2305-2310
[12] Wu X D,Kumar X,Quinlan J R,et al.Top 10 algorithms in data mining[J].Knowledge and Information Systems,2008,14(1):1-37
[13] Hart P E.The condensed nearest neighbor rule[J].IEEETransactions on Information Theory,1968,14(3):515-516
[14] Miao D Q,Hu G R.A heuristic algorithm for reduction of knowledge[J].Journal of Computer Research and Development,1999,36(6):681-684(in Chinese)苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!