A novel ensemble method for k-nearest neighbor. (January 2019)

• Record Type: Journal Article
• Authors: Zhang, Youqiang; Cao, Guo; Wang, Bisheng; Li, Xuesong
• Is Part Of: Pattern recognition. Volume 85(2019:Jan.)
• Page Start: 13
• Page End: 25
• Publication Date: 2019-01
• Subjects: Distance metric -- k-nearest neighbor -- Ensemble learning -- Random subspace -- Evidence theory; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2018.08.003
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We proposed a weighted heterogeneous distance metric (WHDM). We presented WHDM and Dempster–Shafer theory based k NN algorithm. We proposed a multimodal perturbation method (RRSB) for k NN ensemble. The effectiveness of our algorithms was shown on multiple UCI data sets and a KDD data set. Abstract: In this paper, to address the issue that ensembling k -nearest neighbor ( k NN) classifiers with resampling approaches cannot generate component classifiers with a large diversity, we consider ensembling k NN through a multimodal perturbation-based method. Since k NN is sensitive to the input attributes, we propose a weighted heterogeneous distance Metric (WHDM). By using a WHDM and evidence theory, a progressive k NN classifier is developed. Based on a progressive k NN, the random subspace method, attribute reduction, and Bagging, a novel algorithm termed RRSB (reduced random subspace-based Bagging) is proposed for construct ensemble classifier, which can increase the diversity of component classifiers without damaging the accuracy of the component classifiers. In detail, RRSB adopts the perturbation on the learning parameter with a weighted heterogeneous distance metric, the perturbation on the input space with random subspace and attribute reduction, the perturbation on the training data with Bagging, and the perturbation on the output target of k neighbors with evidence theory. In the experimental stage, the value of k, the different perturbations on RRSB and the ensemble size are analyzed. In addition, RRSB is compared with other multimodal perturbation-based ensemble algorithms on multiple UCI data sets and a KDD data set. The results from the experiments demonstrate the effectiveness of RRSB for k NN ensembling.