title: Random KNN feature selection - a fast and stable alternative to Random Forests.
abstract: BACKGROUND
  Successfully modeling high-dimensional data involving thousands of variables is challenging. This is especially true for gene expression profiling experiments, given the large number of genes involved and the small number of samples available. Random Forests (RF) is a popular and widely used approach to feature selection for such "small n, large p problems." However, Random Forests suffers from instability, especially in the presence of noisy and/or unbalanced inputs.
  
  
  RESULTS
  We present RKNN-FS, an innovative feature selection procedure for "small n, large p problems." RKNN-FS is based on Random KNN (RKNN), a novel generalization of traditional nearest-neighbor modeling. RKNN consists of an ensemble of base k-nearest neighbor models, each constructed from a random subset of the input variables. To rank the importance of the variables, we define a criterion on the RKNN framework, using the notion of support. A two-stage backward model selection method is then developed based on this criterion. Empirical results on microarray data sets with thousands of variables and relatively few samples show that RKNN-FS is an effective feature selection approach for high-dimensional data. RKNN is similar to Random Forests in terms of classification accuracy without feature selection. However, RKNN provides much better classification accuracy than RF when each method incorporates a feature-selection step. Our results show that RKNN is significantly more stable and more robust than Random Forests for feature selection when the input data are noisy and/or unbalanced. Further, RKNN-FS is much faster than the Random Forests feature selection method (RF-FS), especially for large scale problems, involving thousands of variables and multiple classes.
  
  
  CONCLUSIONS
  Given the superiority of Random KNN in classification performance when compared with Random Forests, RKNN-FS's simplicity and ease of implementation, and its superiority in speed and stability, we propose RKNN-FS as a faster and more stable alternative to Random Forests in classification problems involving feature selection for high-dimensional datasets.
authors.affiliation: The Department of Statistics, West Virginia University, Morgantown, WV 26506, USA.
authors.forename: Shengqiao
authors.initials: S
authors.lastname: Li
authors.forename: E James
authors.initials: EJ
authors.lastname: Harner
authors.forename: Donald A
authors.initials: DA
authors.lastname: Adjeroh
mesh_terms: D016000:Cluster Analysis; D020869:Gene Expression Profiling; D006801:Humans; D008957:Models, Genetic; D009369:Neoplasms / Q000235:genetics*; D020411:Oligonucleotide Array Sequence Analysis
references.citation: Bioinformatics. 2001 Jun;17(6):520-5
references.pmid: 11395428
references.citation: J Chem Inf Comput Sci. 2003 Nov-Dec;43(6):1947-58
references.pmid: 14632445
references.citation: Psychometrika. 1947 Jun;12(2):153-7
references.pmid: 20254758
references.citation: Brief Bioinform. 2011 Jan;12(1):86-9
references.pmid: 20360022
references.citation: Brief Bioinform. 2011 Jul;12(4):369-73
references.pmid: 21498552
references.citation: Bioinformatics. 2007 Oct 1;23(19):2507-17
references.pmid: 17720704
references.citation: J Chem Inf Comput Sci. 2000 Sep-Oct;40(5):1160-8
references.pmid: 11045809
references.citation: BMC Bioinformatics. 2006 Jan 06;7:3
references.pmid: 16398926
references.citation: J Chem Inf Model. 2005 Jul-Aug;45(4):952-64
references.pmid: 16045289
references.citation: BMC Bioinformatics. 2007 Jan 25;8:25
references.pmid: 17254353