Estimation of Error Bound for k-Nearest Neighbor Classi er on Multi Class Data Sets

Abstract

A motivational problem that arises in machine learning is to estimate out-of-sample error rate of a k-nearest neighbor classi er. Without having any prior knowledge of distribution or any assumption of distribution it is required to estimate the maximum probability of misclassi cation of an unlabeled sample. Previous works include the assumption on data distribution as identical and independent distribution (i.i.d.). This method works for binary classi cation only. Our proposed algorithm is applicable for any data sets without having any knowledge of the underlying data distribution. Our algorithm will search the misclassi cation region in the data set and calculate the bound for an unlabeled test sample. Our method will always detect the class overlapping region within the data set irrespective of balanced and imbalanced. Our method is also designed for both two-class and multi-class data sets. Our experiments includes the bound validation for di erent scenarios. We have tested for random k value and xed range of k. Also veri ed for balanced and imbalanced data sets. We also demonstrated to nd optimal sets of k values where classi er error will be minimized.