Pattern classification using a new border identification paradigm: The nearest border technique

摘要

There are many paradigms for pattern classification such as the optimal Bayesian, kernel-based methods, inter-class border identification schemes, nearest neighbor methods, nearest centroid methods, among others. As opposed to these, this paper pioneers a new paradigm, which we shall refer to as the nearest border (NB) paradigm. The philosophy for developing such a NB strategy is as follows: given the training data set for each class, we shall attempt to create borders for each individual class. However, unlike the traditional border identification (BI) methods, we do not undertake this by using inter-class criteria; rather, we attempt to obtain the border for a specific class in the d-dimensional hyper-space by invoking only the properties of the samples within that class. Once these borders have been obtained, we advocate that testing is accomplished by assigning the test sample to the class whose border it lies closest to. This claim appears counter-intuitive, because unlike the centroid or the median, these border samples are often "outliers" and are, really, the points that represent the class the least. Moreover, inter-class BI methods intuitively outperform within-class ones. However, we have formally proven this claim, and the theoretical results have been verified by rigorous experimental testing on artificial and real-life data sets. While the solution we propose is distantly related to the reported solutions involving prototype reduction schemes (PRSs) and BI algorithms, it is, most importantly, akin to the recently proposed "anti-Bayesian" methods of classification.