Local-based k values for multi-label k-nearest neighbors rule

Abstract

Multi-label learning is a growing field in machine learning research. Many applications address instances that simultaneously belong to many categories, which cannot be disregarded if optimal results are desired. Among the many algorithms developed for multi-label learning, the multi-label k-nearest neighbor method is among the most successful. However, in a difficult classification task, such as multi-label learning, a challenge that arises in the k-nearest neighbor approach is the assignment of the appropriate value of k. Although a suitable value might be obtained using cross-validation, it is unlikely that the same value will be optimal for the whole space spanned by the training set. It is evident that different regions of the feature space would have different distributions of instances and labels that would require different values of k. The very complex boundaries among the many present labels make the necessity of local k values even more important than in the case with a single-label k-nearest neighbor. We present a simple yet powerful approach for setting a local value of k. We associate a potentially different k with every prototype and obtain the best value of that k by optimizing the criterion consisting of the local effect of the different k values in the neighborhood of the prototype. The proposed method has a fast training stage, as it only uses the neighborhood of each training instance to set the local k value. The complexity of the proposed method in terms of the testing time is similar to that of the standard multi-label k-nearest neighbor approach. Experiments performed on a set of 20 problems show that not only does our proposed method significantly outperform the standard multi-label k-nearest neighbor rule but also the locally adaptive multi-label k-nearest neighbor method can benefit from a local k value.