Weighted K-NN Algorithm And Its Application

The performance of K-Nearest Neighbor classification algorithm depends on the selection of distance metrics. The Euclidean distance is usually chosen as the similarity measure in the conventional K-NN algorithm, which usually relates to all attributes. When feature weight parameters are introduced to the distance formula, the performance of classification will depend on the weight values and accordingly can be improved by adjusting weight values. A learning feature weights algorithm is introduced to improve the accuracy of classification. Mathematically it corresponds to a linear transformation for a set of points in the Euclidean space. At the same time, different near neighbors have different roles to determine the final classes of testing samples. We not only learned feature weights for each feature, but also weighted the contribution of each of the k neighbors according to their distance to the testing samples, that is, give greater weights to closer neighbors. So we can improve the accuracy of classification. For K value learning in K-NN, this paper puts forward a validity function for judging clustering in order to lead us to use it in K-nearest neighbor classification; then introduces "Generalization Capability of a case"to K-nearest neighbor. According to the proposed approach, the cases with better Generalization Capability are maintained as the representative cases while those redundant cases found in their coverage are removed. We can find a new less but almost complete training data set; consequently reduce complexity of seeking near neighbors.