Correcting the Hub Occurrence Prediction Bias in Many Dimensions

Nenad Tomašev ; Krisztian Buza ; Dunja Mladenić

Computer Science and Information Systems, Tome 13 (2016) no. 1.

Résumé

Data reduction is a common pre-processing step for k-nearest neighbor classification (kNN). The existing prototype selection methods implement different criteria for selecting relevant points to use in classification, which constitutes a selection bias. This study examines the nature of the instance selection bias in intrinsically high-dimensional data. In high-dimensional feature spaces, hubs are known to emerge as centers of influence in kNN classification. These points dominate most kNN sets and are often detrimental to classification performance. Our experiments reveal that different instance selection strategies bias the predictions of the behavior of hub-points in high-dimensional data in different ways. We propose to introduce an intermediate un-biasing step when training the neighbor occurrence models and we demonstrate promising improvements in various hubness-aware classification methods, on a wide selection of high-dimensional synthetic and real-world datasets.

Détail

Keywords: instance selection, data reduction, classification, bias, k-nearest neighbor, hubness, curse of dimensionality