The Enemy of My Enemy Is My Friend: Class-to-Class Weighting in K-Nearest Neighbors Algorithm

The K-nearest neighbors algorithm (k-NN) is widely used in instance-based learning and case-based reasoning. The basic k-NN approach has been refined and augmented in many ways, including the use of local weighting, asymmetric metrics, and class-specific weighting, which enables the use of different similarity criteria for each class. This paper extends class-specific weighting with a method we call class-to-class (C2C) weighting. Beyond class-specific weighting, which learns feature weightings to identify the most similar cases to a class, C2C weighting also focuses on learning differences between classes to potentially apply those differences to classification. Once C2C weighting has learned how class C_1 is different from class C_2, given a new case is different from a C_1 case in a way similar to the way C_2 cases are different from C_1 cases, then the new case is assigned to class C_2. C2C offers two potential advantages: First, unlike global weighting, it is robust to deletion of the cases in a given class, because non-native class weightings can still make relatively good predictions. We demonstrate experimentally that this can be true even when a whole class of cases is dropped. Additionally, C2C might provide a new potential form of explainability, in explaining classifications based on pattern of differences. Preliminary results suggest that in normal settings C2C offers accuracy comparable to standard methods, though slightly lower. However, with our initial learning method, the native class weightings of C2C weighting are easily skewed and can lead to worse performance than traditional global weightings. We argue this is not an intrinsic flaw in C2C weighting, but rather an issue in the combination of C2C weighting with global weighting, and propose an approach to address this issue.