# A Survey ofk Nearest Neighbor Algorithms for Solving the Class Imbalanced Problem

Authors: Bo Sun; Haiyan Chen
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

k nearest neighbor (kNN) is a simple and widely used classifier; it can achieve comparable performance with more complex classifiers including decision tree and artificial neural network. Therefore, kNN has been listed as one of the top 10 algorithms in machine learning and data mining. On the other hand, in many classification problems, such as medical diagnosis and intrusion detection, the collected training sets are usually class imbalanced. In class imbalanced data, although positive examples are heavily outnumbered by negative ones, positive examples usually carry more meaningful information and are more important than negative examples. Similar to other classical classifiers, kNN is also proposed under the assumption that the training set has approximately balanced class distribution, leading to its unsatisfactory performance on imbalanced data. In addition, under a class imbalanced scenario, the global resampling strategies that are suitable to decision tree and artificial neural network often do not work well for kNN, which is a local information-oriented classifier. To solve this problem, researchers have conducted many works for kNN over the past decade. This paper presents a comprehensive survey of these works according to their different perspectives and analyzes and compares their characteristics. At last, several future directions are pointed out.


---

## Body

## 1. Introduction

k nearest neighbor (kNN) [1] has simple implementation and supreme performance and can achieve comparable performance with more sophisticated classifiers including decision tree [2], artificial neural network [3], and support vector machine [4]. Therefore, kNN has been listed as one of the top 10 algorithms in data mining and machine learning [5, 6]. kNN has been utilized in many applications, such as pattern recognition [7], feature selection [8], and outlier detection [9]. For a test example with unknown class label, kNN makes a decision by employing the local information surrounding the test example. Concretely, kNN first simply stores all the training examples; then, in the classification phase, it takes the class occurring most frequently in the k (k≥1) nearest training examples of the test example as the classification result. That is, kNN makes a decision according to the class distribution characteristics in the k neighborhood of a test example.Nowadays, machine learning and data mining techniques are widely used in many aspects of the information society. However, for some applications such as medical diagnosis [10], system intrusion detection [11], and network fraud detection [12], the collected training example set is usually class imbalanced, i.e., there is a large difference among the sizes of different classes. For instance, in medical diagnosis data, the majority examples are descriptions of normal patients (negative examples), and only a small proportion of examples are representatives of special patients suffering a rare disease (positive examples). But if a special patient is erroneously classified as a normal patient, the best treatment time will be missed and serious consequences will be caused. For computer network intrusion detection data, the majority examples denote the normal access data (negative examples) and only the minority examples denote the illegal access data (positive examples). Similarly, misclassifying illegal access as a legal one will lead to the disclosure of a unit’s inner data or the steal of bank account information. From the above two instances, it can be seen that, in class imbalanced data, although the positive class is heavily outnumbered by the negative class, the positive class is usually the one in which we are more interested and is more important than the negative class. The positive class is also named the minority class while the negative class is also called the majority class.Similar to classical classifiers such as decision tree, artificial neural network, and support vector machine,kNN is also proposed based on the assumption that a training set has approximately balanced class distribution, i.e., the classes have roughly the same number of training examples. In addition, these algorithms all employ the overall classification accuracy as the optimization objective in the classifier training phase, leading to their unsatisfactory performance on class imbalanced data. For kNN, it takes the majority class in the k neighborhood of a test example as the classification result; this majority voting-based classification rule further degrades its performance on a class imbalanced problem. This is because the positive examples are usually sparse in the k neighborhood of a test example [6], i.e., most examples in the k neighborhood are usually negative examples; thus, the positive examples are often misclassified as negative ones by kNN, leading to the poor classification performance for positive examples. For instance, in the binary classification problem shown in Figure 1 (circles denote negative examples, triangles denote positive examples, and the cross denotes a test example), when k equals 7, there are 4 negative examples (N1-N4) and 3 positive examples (P1-P3) in the k neighborhood; obviously, kNN classifies the test example as the negative class although it actually belongs to the positive class.Figure 1
ClassicalkNN performs poorly on positive examples (cited from Reference [12]).Experiments conducted in Reference [13] indicate that SMOTE oversampling integrated with Random Undersampling (RUS) [14] or SMOTE oversampling integrated with the cost-sensitive MataCost method [15] can both significantly improve the performance of C4.5 decision tree [2] on class imbalanced data. Unfortunately, these strategies do not work well for improving kNN in a class imbalanced scenario. The authors in [13] give the explanation from the following aspect: kNN makes a decision by investigating the local neighborhood of a test example, while the resampling and cost-sensitive strategies are global methods and are naturally inappropriate to kNN. Therefore, special methods for kNN need to be designed under the class imbalanced scenario.As can be seen from the above illustration, improvingkNN performance on imbalanced data is an important topic, which is of great significance to the expansion of its application fields and the enhancement of its practical utility. Over the past decade, researchers have conducted many works and proposed many methods. This paper tries to give a comprehensive survey of these works according to their perspectives and analyzes and compares their characteristics, which serves as a foundation for further study in this field.The rest of this paper is organized as follows. The weighting strategy-based methods are illustrated in Section2, the local geometrical structure-based methods are illustrated in Section 3, Section 4 introduces the fuzzy logic-based methods and followed by a category of methods based on missing positive example estimation in Section 5, Section 6 presents methods based on novel distance metrics while Section 7 presents dynamic-sized neighborhood-based methods, and conclusions and future work are presented in Section 8.


## 2. Methods Based on Weighting Strategy

This section introduces a category of methods that assigns weights to training examples in the neighborhood of a test example. In general, these methods can be divided into 5 subcategories as shown in the following.


### 2.1. Weighting Strategy Considering the Class Distribution around the Neighborhood

The authors in [12] claim that the reason for the unsatisfactory performance of kNN on the imbalanced data lies in the following: it only utilizes the local prior probabilities of each class in the neighborhood of a test example but does not employ the class distribution information around the neighborhood. In Figure 1, if the imbalanced class distribution around the test example’s neighborhood is considered, i.e., the area surrounded by the dotted rectangle, then the test example can be correctly classified as the positive class because in this dotted area, the positive nearest neighbors of the test example are much more than the negative ones. Therefore, the classification performance of kNN can be improved if such local class distribution information is utilized.Based on the above observation, a weighting-based method is proposed in [12] to assign a test example-dependent local weight to each class, i.e., the examples’ weight in a class varies with the change of test examples rather than being a constant value. Concretely, for test example xt∈ℝd, the weight wtl of examples in class Cl (1≤l≤L, L is the total number of classes in a classification problem) is calculated as follows. For the k/L number of nearest neighbors of xt in class Cl, if they are erroneously classified by traditional kNN, it is likely that these k/L neighbors belong to the minority class (the positive class) in the neighborhood of xt; in this case, the weight of class Cl is enlarged. Therefore, the learned weights take into consideration the class distribution information around the neighborhood.For the binary classification problem in Figure1, L=2, when k equals 7, we have k/L=7/2=4; the test example’s 4 nearest neighbors in positive class C1 are P1 to P4, while its 4 nearest neighbors in negative class C2 are N1 to N4. It can be seen that P1, P2, and P4 are misclassified to be negative examples as the majority members of their 7 nearest neighbors are all negative examples; thus, the weight of these positive examples should be enlarged. Based on the enlarged weight of positive class, in the classification phase of 7NN for the test example, the 3 positive neighbors P1 to P3 have much larger weight than the 4 negative neighbors, i.e., P1 to P3 make more contribution to the classification result; thus, the correct classification is achieved.However, the shortage of this weighting-based method is that approximatelyk (the exact number is k/L∗L) times of extra running of kNN is required around the neighborhood of each test example; thus, the computation cost is enlarged.


### 2.2. Weighting Strategy Based on Examples’ Informativeness

The authors in [16] believe that some examples carry more information than other examples: if an example is close to the test example and far from examples of other classes, then it is considered to be more informative. Following this idea, it is easily seen from Figure 2 that the example with index 2 carries more information than the one with index 1. The reason is that the two examples have roughly the same distance to the test example (the “query point” in Figure 2), but the example with index 1 is nearer to the class boundary, i.e., it is closer to the other classes. Based on the above consideration, the authors propose two informative kNN algorithms: the local information-based version LI-kNN and the global information-based version GI-kNN.Figure 2
Schematic diagram of examples’ information (cited from Reference [16]).


#### 2.2.1. The Idea of LI-kNN

LI-kNN first finds the k nearest neighbors xt1,xt2,⋯,xtk of test example xt in the training set, then employs the designed metric to evaluate the informativeness of each training example in the k neighborhood, i.e., the evaluation scope is local, and selects the first I (I<k) most informative examples xt1′,xt2′,⋯,xtI′. Finally, the majority class among the class labels yt1′,yt2′,⋯,ytI′ of these I examples is regarded as the classification result. That is to say, the weight of the I selected examples is set to 1 while the weight of the other (k−I) neighboring training examples is set to 0.


#### 2.2.2. The Idea of GI-kNN

After LI-kNN determines I most informative neighbors xt11′,xt12′,⋯,xt1I′ and then makes a decision for test example xt1, when classifying the next test example xt2, it separately determines the I most informative neighbors xt21′,xt22′,⋯,xt2I′ and does not utilize the informative neighbors xt11′,xt12′,⋯,xt1I′ of the previous test example xt1. However, GI-kNN believes that some informative neighbors of a test example may be also the members of other test examples’ informative neighbors. For instance, two informative neighbors xt11,xt12 of test example xt1 may be members of the informative neighbor sets of three test examples xt2,xt3 and xt4. In this case, training examples like xt11,xt12 are considered to be global informative, thus assigning a larger weight to these examples. Based on the above idea, GI-kNN tries to find the training examples with global informativeness and assigns larger weights to them compared with ordinary examples.To summarize, LI-kNN is a local strategy as it determines the informative examples in the k neighborhood of a test example. GI-kNN is a global strategy as it evaluates the informativeness of all the training examples and then assigns larger weights to the examples that are globally more informative, and besides, these weights are fixed when classifying all the subsequent test examples.Experimental results indicate that GI-kNN and LI-kNN are not very sensitive to the change of parameter I and can achieve comparable performance with SVM. One drawback of GI-kNN is that the robustness of its adopted informativeness metric needs to be enhanced when there exist noisy examples in the training set.


### 2.3. Class Confidence-Based Weighting Strategy

The class confidence-weighted (CCW)kNN method [17] is proposed to assign weights to training examples in the neighborhood. As shown in Figure 3, the real boundary between the negative class (denoted by blue triangles) and the positive class (denoted by red circles) is represented by the solid blue line. There are 4 negative examples and 1 positive example in the k (k equals 5 in this case) neighborhood of the test example (denoted by the solid green circle), and the nearest training example of the test example is a negative one. In this case, the classification result is certainly the negative class if the traditional majority voting-based classification rule is adopted. However, the test example actually belongs to the positive class and the negative examples in its neighborhood are also positive ones in reality. Thus, for each training example in the neighborhood, the probability that it belongs to its current class should be considered.Figure 3
An instance of class confidence-weighted (CCW) method (cited from Reference [17]).Based on this idea, for each training examplextj,ytj=xtj1,xtj2,⋯,xtjd,ytj (j=1,2,⋯,k) in the neighborhood of test example xt, the confidence of its belonging to the current class ytj is calculated according to its attributes’ values xtj1,xtj2,⋯,xtjd and then this confidence serves as the weight wtj of this training example. For the instance shown in Figure 3, the mixture model and Bayesian network are employed in [17] to calculate the corresponding confidences of the 4 negative examples in the neighborhood and the values are 0.0245, 0.0173, 0.0171, and 0.0139, respectively. In addition, the calculated confidence of the positive example in the neighborhood is 0.1691. Obviously, the sum of the confidences of the 4 negative examples is much smaller than the confidence of the positive example, i.e., the weights of the 4 negative examples are much smaller than that of the positive example. In this way, the positive example in the neighborhood has much more influence on the classification result than the negative ones, ensuring that the test example can be correctly classified as a positive one. The conducted experiments also indicate that the class confidence-weighted method can correct kNN’s inherent bias to negative examples.On the other hand, the class confidence-weighed method has to calculate the class confidence for each training example in the neighborhood, which increases the computation cost to some extent.


### 2.4. Weighting Strategy Based on Nearest Neighbor Density

A nearest neighbor density-based weighted class-wisekNN (WCkNN) algorithm is proposed in [18], and its basic idea is as follows.First, thek nearest neighbor density of test example xt is determined in each class.This is implemented by constructing ak radius sphere Sl,kxt that takes test example xt as its center and contains at last k nearest examples from class Cl (1≤l≤L); then, the volume Vl,kxt of this k radius sphere is used to denote the density: 1/Vl,kxt. It is not hard to see that, for a test example, its k radius sphere in the positive class usually has much larger volume than the one in the negative class due to the sparse distribution of positive class examples. As the radius of k radius sphere Sl,kxt is determined by the distance dl,kxt between test example xt and its kth nearest neighbor in class Cl, thus dl,kxt is often used to approximately denote the volume of sphere Sl,kxt.Second, the posterior probability of test examples belonging to each class is calculated based on the abovek nearest neighbor density, which is shown in
(1)PCl∣xt=βldl,kxt,l=1,2,⋯,L.In formula (1), the weight βl of class Cl is obtained by employing a certain convex optimization technique to optimize a nonlinear metric on the training set, and from this formula, we have the following observations. (a) For a class balanced data, two classes C1 and C2 have equal weights (β1=β2); in this case, if examples in class C1 are more densely distributed around test example xt, i.e., V1,kxt<V2,kxt and d1,kxt<d2,kxt, then the probability of xt belonging to C1 is larger than that of C2. (b) For an imbalanced data, compared with negative class Cn, positive class Cp is more likely to be sparsely distributed around xt, i.e., dCp,kxt>dCn,kxt; fortunately, the effect of this imbalanced distribution can be overcome by assigning larger weight for the positive class, i.e., βp>βn.At last, the class having the largest posterior probability is considered as the classification result:y=argmaxlPCl∣xt, l=1,2,⋯,L..In terms of complexity, when classifying test examplext, WCkNN needs to run one time of kNN on each class to determine the k nearest neighbor density in this class. Thus, L (the total number of classes) times running of kNN are needed to classify a test example.


### 2.5. Weighting Strategy Integrated with Self-Adaptivek

The methods introduced above all use a constantk value, i.e., for each test example, k is the sum of the number of its positive neighbors and the number of its negative ones. Thus, the number of neighbors is not considered separately for each class.To further improve the performance of weightedkNN methods, the authors in [19] propose to integrate the self-adaptive k technique with the example weighting strategy. In terms of weight determination, the positive examples are assigned larger weights than the negative ones; in terms of neighborhood size, the positive class is given small neighborhood size kp while the negative class is given relative large neighborhood size kn, i.e., kn>kp. In this way, the test example’s kp positive neighbors and kn negative neighbors constitute its neighborhood with size kp+kn.Accordingly, the classification result is determined by two aspects: (a) the weighted sum of the test example’skp positive neighbors: Wpxt=∑i=1kpwti, and (b) the weighted sum of the test example’s kn negative neighbors: Wnxt=∑j=1knwtj. The class with a larger value is the corresponding decision result. To sum up, the self-adaptive k-based weighted kNN is simple and flexible. As to the formula used in the assignment of each class’s neighborhood size, more efforts need to be made to ensure that it is theoretically sound.


## 2.1. Weighting Strategy Considering the Class Distribution around the Neighborhood

The authors in [12] claim that the reason for the unsatisfactory performance of kNN on the imbalanced data lies in the following: it only utilizes the local prior probabilities of each class in the neighborhood of a test example but does not employ the class distribution information around the neighborhood. In Figure 1, if the imbalanced class distribution around the test example’s neighborhood is considered, i.e., the area surrounded by the dotted rectangle, then the test example can be correctly classified as the positive class because in this dotted area, the positive nearest neighbors of the test example are much more than the negative ones. Therefore, the classification performance of kNN can be improved if such local class distribution information is utilized.Based on the above observation, a weighting-based method is proposed in [12] to assign a test example-dependent local weight to each class, i.e., the examples’ weight in a class varies with the change of test examples rather than being a constant value. Concretely, for test example xt∈ℝd, the weight wtl of examples in class Cl (1≤l≤L, L is the total number of classes in a classification problem) is calculated as follows. For the k/L number of nearest neighbors of xt in class Cl, if they are erroneously classified by traditional kNN, it is likely that these k/L neighbors belong to the minority class (the positive class) in the neighborhood of xt; in this case, the weight of class Cl is enlarged. Therefore, the learned weights take into consideration the class distribution information around the neighborhood.For the binary classification problem in Figure1, L=2, when k equals 7, we have k/L=7/2=4; the test example’s 4 nearest neighbors in positive class C1 are P1 to P4, while its 4 nearest neighbors in negative class C2 are N1 to N4. It can be seen that P1, P2, and P4 are misclassified to be negative examples as the majority members of their 7 nearest neighbors are all negative examples; thus, the weight of these positive examples should be enlarged. Based on the enlarged weight of positive class, in the classification phase of 7NN for the test example, the 3 positive neighbors P1 to P3 have much larger weight than the 4 negative neighbors, i.e., P1 to P3 make more contribution to the classification result; thus, the correct classification is achieved.However, the shortage of this weighting-based method is that approximatelyk (the exact number is k/L∗L) times of extra running of kNN is required around the neighborhood of each test example; thus, the computation cost is enlarged.


## 2.2. Weighting Strategy Based on Examples’ Informativeness

The authors in [16] believe that some examples carry more information than other examples: if an example is close to the test example and far from examples of other classes, then it is considered to be more informative. Following this idea, it is easily seen from Figure 2 that the example with index 2 carries more information than the one with index 1. The reason is that the two examples have roughly the same distance to the test example (the “query point” in Figure 2), but the example with index 1 is nearer to the class boundary, i.e., it is closer to the other classes. Based on the above consideration, the authors propose two informative kNN algorithms: the local information-based version LI-kNN and the global information-based version GI-kNN.Figure 2
Schematic diagram of examples’ information (cited from Reference [16]).


### 2.2.1. The Idea of LI-kNN

LI-kNN first finds the k nearest neighbors xt1,xt2,⋯,xtk of test example xt in the training set, then employs the designed metric to evaluate the informativeness of each training example in the k neighborhood, i.e., the evaluation scope is local, and selects the first I (I<k) most informative examples xt1′,xt2′,⋯,xtI′. Finally, the majority class among the class labels yt1′,yt2′,⋯,ytI′ of these I examples is regarded as the classification result. That is to say, the weight of the I selected examples is set to 1 while the weight of the other (k−I) neighboring training examples is set to 0.


### 2.2.2. The Idea of GI-kNN

After LI-kNN determines I most informative neighbors xt11′,xt12′,⋯,xt1I′ and then makes a decision for test example xt1, when classifying the next test example xt2, it separately determines the I most informative neighbors xt21′,xt22′,⋯,xt2I′ and does not utilize the informative neighbors xt11′,xt12′,⋯,xt1I′ of the previous test example xt1. However, GI-kNN believes that some informative neighbors of a test example may be also the members of other test examples’ informative neighbors. For instance, two informative neighbors xt11,xt12 of test example xt1 may be members of the informative neighbor sets of three test examples xt2,xt3 and xt4. In this case, training examples like xt11,xt12 are considered to be global informative, thus assigning a larger weight to these examples. Based on the above idea, GI-kNN tries to find the training examples with global informativeness and assigns larger weights to them compared with ordinary examples.To summarize, LI-kNN is a local strategy as it determines the informative examples in the k neighborhood of a test example. GI-kNN is a global strategy as it evaluates the informativeness of all the training examples and then assigns larger weights to the examples that are globally more informative, and besides, these weights are fixed when classifying all the subsequent test examples.Experimental results indicate that GI-kNN and LI-kNN are not very sensitive to the change of parameter I and can achieve comparable performance with SVM. One drawback of GI-kNN is that the robustness of its adopted informativeness metric needs to be enhanced when there exist noisy examples in the training set.


## 2.2.1. The Idea of LI-kNN

LI-kNN first finds the k nearest neighbors xt1,xt2,⋯,xtk of test example xt in the training set, then employs the designed metric to evaluate the informativeness of each training example in the k neighborhood, i.e., the evaluation scope is local, and selects the first I (I<k) most informative examples xt1′,xt2′,⋯,xtI′. Finally, the majority class among the class labels yt1′,yt2′,⋯,ytI′ of these I examples is regarded as the classification result. That is to say, the weight of the I selected examples is set to 1 while the weight of the other (k−I) neighboring training examples is set to 0.


## 2.2.2. The Idea of GI-kNN

After LI-kNN determines I most informative neighbors xt11′,xt12′,⋯,xt1I′ and then makes a decision for test example xt1, when classifying the next test example xt2, it separately determines the I most informative neighbors xt21′,xt22′,⋯,xt2I′ and does not utilize the informative neighbors xt11′,xt12′,⋯,xt1I′ of the previous test example xt1. However, GI-kNN believes that some informative neighbors of a test example may be also the members of other test examples’ informative neighbors. For instance, two informative neighbors xt11,xt12 of test example xt1 may be members of the informative neighbor sets of three test examples xt2,xt3 and xt4. In this case, training examples like xt11,xt12 are considered to be global informative, thus assigning a larger weight to these examples. Based on the above idea, GI-kNN tries to find the training examples with global informativeness and assigns larger weights to them compared with ordinary examples.To summarize, LI-kNN is a local strategy as it determines the informative examples in the k neighborhood of a test example. GI-kNN is a global strategy as it evaluates the informativeness of all the training examples and then assigns larger weights to the examples that are globally more informative, and besides, these weights are fixed when classifying all the subsequent test examples.Experimental results indicate that GI-kNN and LI-kNN are not very sensitive to the change of parameter I and can achieve comparable performance with SVM. One drawback of GI-kNN is that the robustness of its adopted informativeness metric needs to be enhanced when there exist noisy examples in the training set.


## 2.3. Class Confidence-Based Weighting Strategy

The class confidence-weighted (CCW)kNN method [17] is proposed to assign weights to training examples in the neighborhood. As shown in Figure 3, the real boundary between the negative class (denoted by blue triangles) and the positive class (denoted by red circles) is represented by the solid blue line. There are 4 negative examples and 1 positive example in the k (k equals 5 in this case) neighborhood of the test example (denoted by the solid green circle), and the nearest training example of the test example is a negative one. In this case, the classification result is certainly the negative class if the traditional majority voting-based classification rule is adopted. However, the test example actually belongs to the positive class and the negative examples in its neighborhood are also positive ones in reality. Thus, for each training example in the neighborhood, the probability that it belongs to its current class should be considered.Figure 3
An instance of class confidence-weighted (CCW) method (cited from Reference [17]).Based on this idea, for each training examplextj,ytj=xtj1,xtj2,⋯,xtjd,ytj (j=1,2,⋯,k) in the neighborhood of test example xt, the confidence of its belonging to the current class ytj is calculated according to its attributes’ values xtj1,xtj2,⋯,xtjd and then this confidence serves as the weight wtj of this training example. For the instance shown in Figure 3, the mixture model and Bayesian network are employed in [17] to calculate the corresponding confidences of the 4 negative examples in the neighborhood and the values are 0.0245, 0.0173, 0.0171, and 0.0139, respectively. In addition, the calculated confidence of the positive example in the neighborhood is 0.1691. Obviously, the sum of the confidences of the 4 negative examples is much smaller than the confidence of the positive example, i.e., the weights of the 4 negative examples are much smaller than that of the positive example. In this way, the positive example in the neighborhood has much more influence on the classification result than the negative ones, ensuring that the test example can be correctly classified as a positive one. The conducted experiments also indicate that the class confidence-weighted method can correct kNN’s inherent bias to negative examples.On the other hand, the class confidence-weighed method has to calculate the class confidence for each training example in the neighborhood, which increases the computation cost to some extent.


## 2.4. Weighting Strategy Based on Nearest Neighbor Density

A nearest neighbor density-based weighted class-wisekNN (WCkNN) algorithm is proposed in [18], and its basic idea is as follows.First, thek nearest neighbor density of test example xt is determined in each class.This is implemented by constructing ak radius sphere Sl,kxt that takes test example xt as its center and contains at last k nearest examples from class Cl (1≤l≤L); then, the volume Vl,kxt of this k radius sphere is used to denote the density: 1/Vl,kxt. It is not hard to see that, for a test example, its k radius sphere in the positive class usually has much larger volume than the one in the negative class due to the sparse distribution of positive class examples. As the radius of k radius sphere Sl,kxt is determined by the distance dl,kxt between test example xt and its kth nearest neighbor in class Cl, thus dl,kxt is often used to approximately denote the volume of sphere Sl,kxt.Second, the posterior probability of test examples belonging to each class is calculated based on the abovek nearest neighbor density, which is shown in
(1)PCl∣xt=βldl,kxt,l=1,2,⋯,L.In formula (1), the weight βl of class Cl is obtained by employing a certain convex optimization technique to optimize a nonlinear metric on the training set, and from this formula, we have the following observations. (a) For a class balanced data, two classes C1 and C2 have equal weights (β1=β2); in this case, if examples in class C1 are more densely distributed around test example xt, i.e., V1,kxt<V2,kxt and d1,kxt<d2,kxt, then the probability of xt belonging to C1 is larger than that of C2. (b) For an imbalanced data, compared with negative class Cn, positive class Cp is more likely to be sparsely distributed around xt, i.e., dCp,kxt>dCn,kxt; fortunately, the effect of this imbalanced distribution can be overcome by assigning larger weight for the positive class, i.e., βp>βn.At last, the class having the largest posterior probability is considered as the classification result:y=argmaxlPCl∣xt, l=1,2,⋯,L..In terms of complexity, when classifying test examplext, WCkNN needs to run one time of kNN on each class to determine the k nearest neighbor density in this class. Thus, L (the total number of classes) times running of kNN are needed to classify a test example.


## 2.5. Weighting Strategy Integrated with Self-Adaptivek

The methods introduced above all use a constantk value, i.e., for each test example, k is the sum of the number of its positive neighbors and the number of its negative ones. Thus, the number of neighbors is not considered separately for each class.To further improve the performance of weightedkNN methods, the authors in [19] propose to integrate the self-adaptive k technique with the example weighting strategy. In terms of weight determination, the positive examples are assigned larger weights than the negative ones; in terms of neighborhood size, the positive class is given small neighborhood size kp while the negative class is given relative large neighborhood size kn, i.e., kn>kp. In this way, the test example’s kp positive neighbors and kn negative neighbors constitute its neighborhood with size kp+kn.Accordingly, the classification result is determined by two aspects: (a) the weighted sum of the test example’skp positive neighbors: Wpxt=∑i=1kpwti, and (b) the weighted sum of the test example’s kn negative neighbors: Wnxt=∑j=1knwtj. The class with a larger value is the corresponding decision result. To sum up, the self-adaptive k-based weighted kNN is simple and flexible. As to the formula used in the assignment of each class’s neighborhood size, more efforts need to be made to ensure that it is theoretically sound.


## 3. Methods Based on Local Geometric Structure of Data

An algorithm named class conditional nearest neighbor distribution (CCNND) is presented in [20], which alleviates the class imbalanced problem by using the local geometric structure of data, and its basic idea is as follows.


### 3.1. Calculating thek Nearest Neighbor Distances in Each Class

For each training examplexm in class Cl (1≤l≤L), the distances to its k nearest neighbors (without considering itself) in class Cl are calculated: dl,kxm=distxm,xm1l,distxm,xm2l,⋯,distxm,xmkl, where distxm,xmql is the distance between xm and its qth (1≤q≤k) nearest neighbor xmql in class Cl.


### 3.2. Making Decisions Based on thek Nearest Neighbor Distances of Test Example in Each Class

First, for test examplext, the distances to its k nearest neighbors in class Cl (1≤l≤L) are calculated:dl,kxt=distxt,xt1l,distxt,xt2l,⋯,distxt,xtkl, where distxt,xtql is the distance between xt and its qth nearest neighbor xtql (1≤q≤k) in class Cl.Second, for each class, the number of its training examples with largerk nearest neighbor distances than the test example is determined: Nlxt=xm∣xm∈Cl∧dl,kxm>dl,kxt, l=1,2,⋯,L, where dl,kxm>dl,kxt is equivalent to distxm,xm1l>distxt,xt1l∧distxm,xm2l>distxt,xt2l∧⋯∧distxm,xmkl>distxt,xtkl. It can be seen that the more such examples of a class have, the closer its class center to the test example is, i.e., the more likely the test example belongs to this class. Thus, the classification result is denoted as yt=argmaxl∈1,2,⋯,LNlxt.The conducted experiments demonstrate that, compared with the classical resampling and cost-sensitive methods, CCNND can achieve comparable or even better performance. As shown in Figure4, the decision boundary obtained using CCNND is closer to the real boundary than that obtained using SVM and nearest neighbor. In addition, another advantage of CCNND is that it still works when the imbalance degree in a training set changes with time, e.g., in the case of online streaming data [21]. Therefore, CCNND can be applied in streaming data such as the oil and natural gas industrial data.Figure 4
The class boundary obtained by the CCNND algorithm (cited from Reference [20]).


## 3.1. Calculating thek Nearest Neighbor Distances in Each Class

For each training examplexm in class Cl (1≤l≤L), the distances to its k nearest neighbors (without considering itself) in class Cl are calculated: dl,kxm=distxm,xm1l,distxm,xm2l,⋯,distxm,xmkl, where distxm,xmql is the distance between xm and its qth (1≤q≤k) nearest neighbor xmql in class Cl.


## 3.2. Making Decisions Based on thek Nearest Neighbor Distances of Test Example in Each Class

First, for test examplext, the distances to its k nearest neighbors in class Cl (1≤l≤L) are calculated:dl,kxt=distxt,xt1l,distxt,xt2l,⋯,distxt,xtkl, where distxt,xtql is the distance between xt and its qth nearest neighbor xtql (1≤q≤k) in class Cl.Second, for each class, the number of its training examples with largerk nearest neighbor distances than the test example is determined: Nlxt=xm∣xm∈Cl∧dl,kxm>dl,kxt, l=1,2,⋯,L, where dl,kxm>dl,kxt is equivalent to distxm,xm1l>distxt,xt1l∧distxm,xm2l>distxt,xt2l∧⋯∧distxm,xmkl>distxt,xtkl. It can be seen that the more such examples of a class have, the closer its class center to the test example is, i.e., the more likely the test example belongs to this class. Thus, the classification result is denoted as yt=argmaxl∈1,2,⋯,LNlxt.The conducted experiments demonstrate that, compared with the classical resampling and cost-sensitive methods, CCNND can achieve comparable or even better performance. As shown in Figure4, the decision boundary obtained using CCNND is closer to the real boundary than that obtained using SVM and nearest neighbor. In addition, another advantage of CCNND is that it still works when the imbalance degree in a training set changes with time, e.g., in the case of online streaming data [21]. Therefore, CCNND can be applied in streaming data such as the oil and natural gas industrial data.Figure 4
The class boundary obtained by the CCNND algorithm (cited from Reference [20]).


## 4. Fuzzy Logic-Based Methods

In fuzzy logic-based [22] classification methods, the membership of belonging to each class is assigned to an example rather than a crisp class label, which can preserve abundant classification information and thus make a full classification. Based on this conclusion, a fuzzy weighted kNN algorithm is proposed in [22] by integrating the advantages of both fuzzy logic and weighted kNN, which is the first method introduced in Subsection 4.1, and the second method in Subsection 4.2 is a further improvement of fuzzy kNN itself.


### 4.1. Fuzzy WeightedkNN Algorithm

The fuzzy weightedkNN in [22] improves the weighted kNN method by utilizing the advantage of fuzzy logic, and it has the following three steps.


#### 4.1.1. Determining the Class Membership of Each Example

The membership of examplex∈ℝd for class Cl (1≤l≤L) is calculated using formula (2), where nCl is the number of training examples belonging to class Cl in the k neighborhood of example x and Cx is the true class label of x.
(2)μClx=0.51+nClk∗0.49,ifCl=Cx,nClk∗0.49,otherwise.For instance, in binary classification, if the true class of examplex1 is class C1 and there are 4 neighbors belonging to class C1 in its 5 neighborhood (i.e., k=5), then the membership of x1 for C1 is μC1x1=0.51+4/5∗0.49=0.902 while the one for C2 is μC2x1=1/5∗0.49=0.098.


#### 4.1.2. Determining the Weight of Each Class

The weightwl of class Cl (1≤l≤L) is calculated using formula (3), where NCl denotes the number of examples in Cl, i.e., the size of this class. It is easy to see that the positive class is assigned a weight of 1 while the negative class is assigned a weight less than 1, and the more examples in the negative class the smaller its weight.
(3)wl=1NCl/minNC1,NC2,⋯,NCL,l=1,2,⋯,L.


#### 4.1.3. Making a Decision Based on the Class Memberships and the Class Weights

The class membershipμClxt of test example xt for class Cl (1≤l≤L) is calculated using formula (4), where μCl,jxt is the class membership of xt’s jth (j=1,2,⋯,k) nearest neighbor for class Cl and wj is the weight of the class to which this neighbor belongs.
(4)μClxt=∑j=1kwj∗μCl,jxt∑j=1kwj,l=1,2,⋯,L.At last, the decision is the class having the largest membership:yxt=argmaxl=1,2,⋯,LμClxt.


### 4.2. Self-Adaptivek-Based Fuzzy kNN

Although the weighted fuzzykNN introduced in Subsection 4.1 can achieve good performance, the fuzzy kNN algorithm itself can not accurately compute examples’ class membership under the class imbalanced scenario. To solve this problem, an improved fuzzy kNN algorithm based on self-adaptive k strategy is proposed in [23] and it contains the following steps.


#### 4.2.1. Determining the Neighborhood Sizek for Each Class

The basic idea is to use relatively large neighborhood for the negative class and small neighborhood for the positive class. Concretely, the neighborhood size of each class is determined using formula (5). Where NCl is the number of training examples in class Cl, λ is a constant (e.g., take the value 1) with the purpose of preventing the value of kCl from being too small.
(5)kCl=minλ+k∗NClmaxNCl∣l=1,2,⋯,L,k,NCl,where l=1,2,⋯,L.


#### 4.2.2. Calculating the Class Membership of Training Examples According to the Obtained Neighborhood Size

Formula (6) adopted here is different from formula (2): the corresponding class’s k value kCl is utilized when calculating the class membership of example x, and Cx is the true class label of x.
(6)μClx=0.51+nClkCl∗0.49,ifCl=Cx,nClkCl∗0.49,otherwise,where l=1,2,⋯,L.


#### 4.2.3. Determining the Class Membership of the Test Example

The class membership of test examplext for class Cl (l=1,2,⋯,L) is calculated using formula (7), where μClxt,jl is the class membership that example xt,jlbelongs to class Cl, and xt,jl is the jth 1≤j≤kCl neighbor of test example xt in class Cl. It can be seen from formula (7) that, in fact, test example xt’s class membership for class Cl is the distance weighted sum of the corresponding class memberships of xt’s kCl nearest neighbors.
(7)μClxt=∑j=1kClμClxt,jl1/xt−xt,jl2/p−1∑j=1kCl1/xt−xt,jl2/p−1,wherel takes values from 1,2,⋯,L and p is an integer and is larger than 1.At last, the class having the largest membership is the classification decision:yxt=argmaxl=1,2,⋯,LμClxt.By adopting different neighborhood sizes for different classes, this self-adaptivek-based fuzzy kNN can effectively alleviate the adverse influence of negative examples in the neighborhood of a positive example, making the obtained class membership more objective and thus improving the classification performance of fuzzy kNN on imbalanced data.


## 4.1. Fuzzy WeightedkNN Algorithm

The fuzzy weightedkNN in [22] improves the weighted kNN method by utilizing the advantage of fuzzy logic, and it has the following three steps.


### 4.1.1. Determining the Class Membership of Each Example

The membership of examplex∈ℝd for class Cl (1≤l≤L) is calculated using formula (2), where nCl is the number of training examples belonging to class Cl in the k neighborhood of example x and Cx is the true class label of x.
(2)μClx=0.51+nClk∗0.49,ifCl=Cx,nClk∗0.49,otherwise.For instance, in binary classification, if the true class of examplex1 is class C1 and there are 4 neighbors belonging to class C1 in its 5 neighborhood (i.e., k=5), then the membership of x1 for C1 is μC1x1=0.51+4/5∗0.49=0.902 while the one for C2 is μC2x1=1/5∗0.49=0.098.


### 4.1.2. Determining the Weight of Each Class

The weightwl of class Cl (1≤l≤L) is calculated using formula (3), where NCl denotes the number of examples in Cl, i.e., the size of this class. It is easy to see that the positive class is assigned a weight of 1 while the negative class is assigned a weight less than 1, and the more examples in the negative class the smaller its weight.
(3)wl=1NCl/minNC1,NC2,⋯,NCL,l=1,2,⋯,L.


### 4.1.3. Making a Decision Based on the Class Memberships and the Class Weights

The class membershipμClxt of test example xt for class Cl (1≤l≤L) is calculated using formula (4), where μCl,jxt is the class membership of xt’s jth (j=1,2,⋯,k) nearest neighbor for class Cl and wj is the weight of the class to which this neighbor belongs.
(4)μClxt=∑j=1kwj∗μCl,jxt∑j=1kwj,l=1,2,⋯,L.At last, the decision is the class having the largest membership:yxt=argmaxl=1,2,⋯,LμClxt.


## 4.1.1. Determining the Class Membership of Each Example

The membership of examplex∈ℝd for class Cl (1≤l≤L) is calculated using formula (2), where nCl is the number of training examples belonging to class Cl in the k neighborhood of example x and Cx is the true class label of x.
(2)μClx=0.51+nClk∗0.49,ifCl=Cx,nClk∗0.49,otherwise.For instance, in binary classification, if the true class of examplex1 is class C1 and there are 4 neighbors belonging to class C1 in its 5 neighborhood (i.e., k=5), then the membership of x1 for C1 is μC1x1=0.51+4/5∗0.49=0.902 while the one for C2 is μC2x1=1/5∗0.49=0.098.


## 4.1.2. Determining the Weight of Each Class

The weightwl of class Cl (1≤l≤L) is calculated using formula (3), where NCl denotes the number of examples in Cl, i.e., the size of this class. It is easy to see that the positive class is assigned a weight of 1 while the negative class is assigned a weight less than 1, and the more examples in the negative class the smaller its weight.
(3)wl=1NCl/minNC1,NC2,⋯,NCL,l=1,2,⋯,L.


## 4.1.3. Making a Decision Based on the Class Memberships and the Class Weights

The class membershipμClxt of test example xt for class Cl (1≤l≤L) is calculated using formula (4), where μCl,jxt is the class membership of xt’s jth (j=1,2,⋯,k) nearest neighbor for class Cl and wj is the weight of the class to which this neighbor belongs.
(4)μClxt=∑j=1kwj∗μCl,jxt∑j=1kwj,l=1,2,⋯,L.At last, the decision is the class having the largest membership:yxt=argmaxl=1,2,⋯,LμClxt.


## 4.2. Self-Adaptivek-Based Fuzzy kNN

Although the weighted fuzzykNN introduced in Subsection 4.1 can achieve good performance, the fuzzy kNN algorithm itself can not accurately compute examples’ class membership under the class imbalanced scenario. To solve this problem, an improved fuzzy kNN algorithm based on self-adaptive k strategy is proposed in [23] and it contains the following steps.


### 4.2.1. Determining the Neighborhood Sizek for Each Class

The basic idea is to use relatively large neighborhood for the negative class and small neighborhood for the positive class. Concretely, the neighborhood size of each class is determined using formula (5). Where NCl is the number of training examples in class Cl, λ is a constant (e.g., take the value 1) with the purpose of preventing the value of kCl from being too small.
(5)kCl=minλ+k∗NClmaxNCl∣l=1,2,⋯,L,k,NCl,where l=1,2,⋯,L.


### 4.2.2. Calculating the Class Membership of Training Examples According to the Obtained Neighborhood Size

Formula (6) adopted here is different from formula (2): the corresponding class’s k value kCl is utilized when calculating the class membership of example x, and Cx is the true class label of x.
(6)μClx=0.51+nClkCl∗0.49,ifCl=Cx,nClkCl∗0.49,otherwise,where l=1,2,⋯,L.


### 4.2.3. Determining the Class Membership of the Test Example

The class membership of test examplext for class Cl (l=1,2,⋯,L) is calculated using formula (7), where μClxt,jl is the class membership that example xt,jlbelongs to class Cl, and xt,jl is the jth 1≤j≤kCl neighbor of test example xt in class Cl. It can be seen from formula (7) that, in fact, test example xt’s class membership for class Cl is the distance weighted sum of the corresponding class memberships of xt’s kCl nearest neighbors.
(7)μClxt=∑j=1kClμClxt,jl1/xt−xt,jl2/p−1∑j=1kCl1/xt−xt,jl2/p−1,wherel takes values from 1,2,⋯,L and p is an integer and is larger than 1.At last, the class having the largest membership is the classification decision:yxt=argmaxl=1,2,⋯,LμClxt.By adopting different neighborhood sizes for different classes, this self-adaptivek-based fuzzy kNN can effectively alleviate the adverse influence of negative examples in the neighborhood of a positive example, making the obtained class membership more objective and thus improving the classification performance of fuzzy kNN on imbalanced data.


## 4.2.1. Determining the Neighborhood Sizek for Each Class

The basic idea is to use relatively large neighborhood for the negative class and small neighborhood for the positive class. Concretely, the neighborhood size of each class is determined using formula (5). Where NCl is the number of training examples in class Cl, λ is a constant (e.g., take the value 1) with the purpose of preventing the value of kCl from being too small.
(5)kCl=minλ+k∗NClmaxNCl∣l=1,2,⋯,L,k,NCl,where l=1,2,⋯,L.


## 4.2.2. Calculating the Class Membership of Training Examples According to the Obtained Neighborhood Size

Formula (6) adopted here is different from formula (2): the corresponding class’s k value kCl is utilized when calculating the class membership of example x, and Cx is the true class label of x.
(6)μClx=0.51+nClkCl∗0.49,ifCl=Cx,nClkCl∗0.49,otherwise,where l=1,2,⋯,L.


## 4.2.3. Determining the Class Membership of the Test Example

The class membership of test examplext for class Cl (l=1,2,⋯,L) is calculated using formula (7), where μClxt,jl is the class membership that example xt,jlbelongs to class Cl, and xt,jl is the jth 1≤j≤kCl neighbor of test example xt in class Cl. It can be seen from formula (7) that, in fact, test example xt’s class membership for class Cl is the distance weighted sum of the corresponding class memberships of xt’s kCl nearest neighbors.
(7)μClxt=∑j=1kClμClxt,jl1/xt−xt,jl2/p−1∑j=1kCl1/xt−xt,jl2/p−1,wherel takes values from 1,2,⋯,L and p is an integer and is larger than 1.At last, the class having the largest membership is the classification decision:yxt=argmaxl=1,2,⋯,LμClxt.By adopting different neighborhood sizes for different classes, this self-adaptivek-based fuzzy kNN can effectively alleviate the adverse influence of negative examples in the neighborhood of a positive example, making the obtained class membership more objective and thus improving the classification performance of fuzzy kNN on imbalanced data.


## 5. Methods Based on Missing Positive Data Estimation

The class imbalanced problem is regarded as a missing positive data estimation problem in [24]. From this perspective, a method called Fuzzy-based Information Decomposition (FID) is proposed and its main idea is as follows.
(1)
tt>0 number of synthetic positive examples are generated, and at the beginning, all their attributes have missing values(2)
The values of each attribute are estimated according to the current training setConcretely, for thesth (s=1,2,⋯,d, d is the dimension of training data) attribute attrs:
(1)
Dividing all the available values onattrs into t intervalsAccording to the values of the current training set onattrs (i.e., attr1s,attr2s,⋯,attrNs) and the number t of positive examples to be generated, t intervals are obtained: q1=a,a+h, q2=a+h,a+2h,⋯,qt=a+t−1∗h,b, where attris is the value of the ith (i=1,2,⋯,N) training example on attribute attrs, N is the total number of current training examples, a and b are, respectively, the minimum and maximum values among attr1s,attr2s,⋯,attrNs, and h is the step length: h=b−a/t.
(2)
Generating a synthetic attribute value for each intervalFor themth 1≤m≤t interval qm, a synthetic value attrqms of attribute attrs is generated in the following way. The fuzzy membership μxi,qm of training example xi′si=1,2,⋯,N attribute value attris with respect to interval qm is calculated, which is used as the weight wim of example xi in estimating the mth missing value of attribute attrs. For instance, if the attribute value attrjs of example xjj=1,2,⋯,N is a “neighbor” to the center a+m−1∗h+a+m∗h/2 of interval qm, i.e., their distance is less than the step length h, then the corresponding fuzzy membership μxj,qm is calculated and served as the weight wjm=μxj,qm of example xj; otherwise, the weight of example xj is set to 0: wjm=0. Therefore, the mth estimated value for attribute attrs can be represented in formula (8).
(8)attrqms=∑j=1Nwjm⋅attrjs=∑j=1Nμxj,qm⋅attrjs.The weights satisfy that∑j=1Nwjm=1.That is to say, only when an example’s attribute value is close to the center of intervalqm (m=1,2,⋯,t) can it effectively influences the calculation of the mth synthetic attribute value attrqms. Thus, the mth estimated value for attribute attrs is the weighted sum of these effective training examples on this attribute.The advantage of FID is that it can deal with data with arbitrary dimension as itseparately generates the missing values for each attribute. Traditional methods like Random OverSampling (ROS) [14] and Clustering Based OverSampling (CBOS) [25] have the tendency of overfitting due to the replication of existing positive examples; for methods like SMOTE [26] and Majority Weighted Minority (MWM) oversampling [27], an approximate positive example needs to be selected before generating a synthetic positive example using linear interpolation. However, these traditional methods have poor performance when the positive examples in the original training set are not enough. Fortunately, FID can overcome this problem as it generates the synthetic values separately for each attribute. As to the disadvantage of FID, when calculating a synthetic value for an attribute, the memberships of all training examples’ values on this attribute with respect to the current interval need to be computed, leading to high computation and time complexity in the case of large training set size.


## 6. Novel Distance Metric-Based Methods

Euclidean distance is usually adopted as the metric to evaluate the similarity between two examples. However, this metric does not treat the positive and negative examples separately in the calculation of distance. To make up this shortcoming, the following works, respectively, present a novel distance metric that is sensitive to positive examples.


### 6.1. Distance Metric for Exemplar Positive Examples

The authors in [28] propose a method called k exemplar-based Nearest Neighbor (k-ENN), which improves the classification performance to positive examples by extending each exemplar positive example from a point in the feature space to a Gaussian ball. In detail, the principle of k-ENN is as follows.


#### 6.1.1. Determining the Exemplar Positive Examples

For each positive examplexip (1≤i≤np, np is the total number of positive examples in the training set) in training set Dtr, find its nearest positive class neighbor xjp (i≠j) and compute their distance rip=distxip,xjp. In this way, a Gaussian ball centered at xip and with a radius of rip is constructed, i.e., a neighborhood Si of xip is obtained. As xjp is the nearest neighbor of xip in positive class, there are only two positive examples in Gaussian ball Si: xip and xjp, and the other negative examples occurring in Si are “false positives.” k-ENN considers positive example xip as an exemplar positive example if the false positive rate fpi in its Gaussian ball Si is less than a threshold: fpi<τ.For instance, Figure5 displays the Gaussian balls of three positive examples numbered 1 to 3, which are denoted using dashed circles. It is easy to see that there is no negative example (denoted by symbol “-”) in each Gaussian ball; thus, the three positive examples are all exemplar ones.Figure 5
Schematic diagram of positive exemplar (cited from Reference [28]).


#### 6.1.2. Defining the Distance Between the Test and Training Examples

When classifying test examplext, its distance to each training example xi (1≤i≤N) needs to be computed. In k-ENN, if xt is an exemplar positive example, then the distance is defined as
(9)dxt,xi=distxt,xi−rip.Ifxi is not an exemplar positive example, i.e., an ordinary positive example or a negative one, then the distance is still the Euclidean distance:
(10)dxt,xi=distxt,xi.The distance in formula (9) subtracts the radius of the Gaussian ball of exemplar positive example xi; in reality, it is the distance between test example xt and the boundary of xi’s Gaussian ball. In this way, the distance from exemplar positive examples to the test example is reduced such that these exemplar positives are given more attention in the classification phase, consequently improving the classification performance for positive examples.


### 6.2. Distance Based on Examples’ Weights

The example weighting-based distance is proposed in [29]; it considers the relative importance of each training example xi (1≤i≤N) when classifying test example xt, which is implemented by utilizing training examples’ weights rather than simply computing the Euclidean distance.
(11)dwxt,xi=xt−xiwi.It can be seen from formula (11) that, by assigning larger weights for positive training examples than for negative ones, the distances from positive examples to the test example can be reduced, which has the effect of improving the chance of positive examples being selected into the neighborhood, thus rectifying the inherent bias of kNN for negative examples and improving the classification performance of positive examples. As to the weights wi(i=1,2,..,N) assigned to the training examples, they are obtained by employing a gradient ascend technique to optimize the G-mean [30] metric.


## 6.1. Distance Metric for Exemplar Positive Examples

The authors in [28] propose a method called k exemplar-based Nearest Neighbor (k-ENN), which improves the classification performance to positive examples by extending each exemplar positive example from a point in the feature space to a Gaussian ball. In detail, the principle of k-ENN is as follows.


### 6.1.1. Determining the Exemplar Positive Examples

For each positive examplexip (1≤i≤np, np is the total number of positive examples in the training set) in training set Dtr, find its nearest positive class neighbor xjp (i≠j) and compute their distance rip=distxip,xjp. In this way, a Gaussian ball centered at xip and with a radius of rip is constructed, i.e., a neighborhood Si of xip is obtained. As xjp is the nearest neighbor of xip in positive class, there are only two positive examples in Gaussian ball Si: xip and xjp, and the other negative examples occurring in Si are “false positives.” k-ENN considers positive example xip as an exemplar positive example if the false positive rate fpi in its Gaussian ball Si is less than a threshold: fpi<τ.For instance, Figure5 displays the Gaussian balls of three positive examples numbered 1 to 3, which are denoted using dashed circles. It is easy to see that there is no negative example (denoted by symbol “-”) in each Gaussian ball; thus, the three positive examples are all exemplar ones.Figure 5
Schematic diagram of positive exemplar (cited from Reference [28]).


### 6.1.2. Defining the Distance Between the Test and Training Examples

When classifying test examplext, its distance to each training example xi (1≤i≤N) needs to be computed. In k-ENN, if xt is an exemplar positive example, then the distance is defined as
(9)dxt,xi=distxt,xi−rip.Ifxi is not an exemplar positive example, i.e., an ordinary positive example or a negative one, then the distance is still the Euclidean distance:
(10)dxt,xi=distxt,xi.The distance in formula (9) subtracts the radius of the Gaussian ball of exemplar positive example xi; in reality, it is the distance between test example xt and the boundary of xi’s Gaussian ball. In this way, the distance from exemplar positive examples to the test example is reduced such that these exemplar positives are given more attention in the classification phase, consequently improving the classification performance for positive examples.


## 6.1.1. Determining the Exemplar Positive Examples

For each positive examplexip (1≤i≤np, np is the total number of positive examples in the training set) in training set Dtr, find its nearest positive class neighbor xjp (i≠j) and compute their distance rip=distxip,xjp. In this way, a Gaussian ball centered at xip and with a radius of rip is constructed, i.e., a neighborhood Si of xip is obtained. As xjp is the nearest neighbor of xip in positive class, there are only two positive examples in Gaussian ball Si: xip and xjp, and the other negative examples occurring in Si are “false positives.” k-ENN considers positive example xip as an exemplar positive example if the false positive rate fpi in its Gaussian ball Si is less than a threshold: fpi<τ.For instance, Figure5 displays the Gaussian balls of three positive examples numbered 1 to 3, which are denoted using dashed circles. It is easy to see that there is no negative example (denoted by symbol “-”) in each Gaussian ball; thus, the three positive examples are all exemplar ones.Figure 5
Schematic diagram of positive exemplar (cited from Reference [28]).


## 6.1.2. Defining the Distance Between the Test and Training Examples

When classifying test examplext, its distance to each training example xi (1≤i≤N) needs to be computed. In k-ENN, if xt is an exemplar positive example, then the distance is defined as
(9)dxt,xi=distxt,xi−rip.Ifxi is not an exemplar positive example, i.e., an ordinary positive example or a negative one, then the distance is still the Euclidean distance:
(10)dxt,xi=distxt,xi.The distance in formula (9) subtracts the radius of the Gaussian ball of exemplar positive example xi; in reality, it is the distance between test example xt and the boundary of xi’s Gaussian ball. In this way, the distance from exemplar positive examples to the test example is reduced such that these exemplar positives are given more attention in the classification phase, consequently improving the classification performance for positive examples.


## 6.2. Distance Based on Examples’ Weights

The example weighting-based distance is proposed in [29]; it considers the relative importance of each training example xi (1≤i≤N) when classifying test example xt, which is implemented by utilizing training examples’ weights rather than simply computing the Euclidean distance.
(11)dwxt,xi=xt−xiwi.It can be seen from formula (11) that, by assigning larger weights for positive training examples than for negative ones, the distances from positive examples to the test example can be reduced, which has the effect of improving the chance of positive examples being selected into the neighborhood, thus rectifying the inherent bias of kNN for negative examples and improving the classification performance of positive examples. As to the weights wi(i=1,2,..,N) assigned to the training examples, they are obtained by employing a gradient ascend technique to optimize the G-mean [30] metric.


## 7. Methods Based on Dynamic-Sized Neighborhoods

The methods introduced above construct the neighborhoods with equal size for all the test examples: traditionalkNN constructs the neighborhood by finding k nearest training examples for a test example, while self-adaptive k strategy-based kNN constructs the neighborhood by finding kp positive neighboring examples and knnegative neighbors for each test example, and in a classification problem, the number (kp+kn) of nearest neighbors does not change with respect to test examples. Different from these methods, the methods illustrated in this section construct test example-dependent neighborhood sizes, i.e., for a classification problem, the neighborhood size changes with different test examples. The aim of doing so is to ensure the existence of sufficient positive examples in the neighborhood, and the positive examples in the neighborhood of a test example are all closer to the test example and have similar posterior class probabilities to it. Based on whether parameters are required in determining the dynamic neighborhood size, this kind of method can be divided into two categories.


### 7.1. Dynamic-Sized NeighborhoodkNN with Parameters

#### 7.1.1. Positive-Biased Nearest Neighbor PNN

The Positive-biased Nearest Neighbor (PNN) algorithm is designed in [31] to improve the sensitivity of kNN to positive class. PNN first dynamically constructs the neighborhood of a test example and then adjusts the classification result according to the local class distribution in the neighborhood.
(1)
Constructing the “k/2 Positive Nearest Neighborhood (k/2-PNN)” for each test example to expand the neighborhood for decision makingCompute the distances from test examplext to all the training examples and rearrange the training examples in ascending order according to their distances, then find the k/2 number of positive nearest neighbors of xt that constitute the neighborhood Sk/2pxt. Sk/2pxt usually contains more examples than xt’s k neighborhood Skxt, i.e., r=∣Sk/2pxt∣>k. As displayed in Figure 6(a), the test example is denoted using symbol “∗” and the positive and negative examples are denoted using symbols “+” and “-,” respectively. When k=5, the neighborhood having k/2=5/2=3 positive training examples contains r=8 examples in total, in this case r>k, and an “extended neighborhood” Sk/2pxt is obtained for test example xt.
(2)
Making decision based on whether “k/2-PNN” is a positive subconceptFigure 6
Schematic diagram of neighborhood in PNN.
(a)
r>k(b)
r<k(c)
r<k(d)
r=kIf the ratio of positive examples inSk/2pxt is much higher than that in the overall training set D, then Sk/2pxt is considered to be a positive class subconcept and k/2/k>1/2 is set as the posterior probability of the test example for the positive class, i.e., xt is classified as a positive class example. Otherwise, if Sk/2pxt is not a positive subconcept, then the ratio (i.e., k/2/r) of positive examples in Sk/2pxt is regarded as the posterior probability of xt for the positive class; in this case, the probability is usually less than 0.5, i.e., xt is classified as a negative example.For instance, if the neighborhood in Figure6(a) is a positive class subconcept, then the probability of the test example with respect to the positive class is P+∣xt=k/2/k=3/5>1/2; thus, the classification result of PNN is the positive class; otherwise, the probability is P+∣xt=k/2/r=3/8<1/2; thus, the test example is classified as a negative example. For the case that there are less than k examples in Sk/2pxt as shown in Figures 6(b) and 6(c), which rarely occurs under the class imbalanced scenario, it indicates that the positive examples are densely distributed around the test example and the corresponding probability is P+∣xt=k/2/r=3/4>1/2, i.e., the decision of PNN is the positive class. For the case that Sk/2pxt has the same size with k neighborhood Skxt as shown in Figure 6(d), PNN degrades to kNN.Experiments in [31] indicate that the simple and effective decision bias of PNN can better classify positive examples, and PNN usually outperforms k-ENN [28] and achieves comparable performance with CCW-kNN [17] mentioned in previous sections. In terms of efficiency, PNN has a much lower computation cost than the two methods that require a “training phase”: (1) k-ENN needs to determine all the exemplar positive examples in the training phase to expand its decision boundary while (2) CCW-kNN computes the weight of each training example by using the mixture model and the Bayesian network. Therefore, both the two methods have a high computation cost. In addition, PNN also outperforms oversampling techniques like SMOTE as well as cost-sensitive strategies like MetaCost.


#### 7.1.2.k Rare-Class Nearest Neighbor Algorithm

k Rare-class Nearest Neighbor (kRNN) is proposed in [32], which has a similar idea with PNN introduced in the previous subsection. kRNN also constructs a test example-dependent dynamic-sized neighborhood and then adjusts the posterior probability of the test example according to the positive examples’ distribution in the extended neighborhood. The differences between kRNN and PNN mainly lie in the following two aspects.
(1)
For test examplext, its neighborhood constructed by kRNN contains at least k′ positive examples, where k′ is set to be a constant and takes values 1 or 3 in most cases(2)
When calculating the test example’s posterior probability of belonging to the positive class, the local and global confidence intervals of the positive class are both utilized, making the obtained probabilityP+∣xt more accurate than the one (i.e., k/2/k) obtained by PNNIt is experimentally demonstrated thatkRNN significantly improves the classification performance of kNN for positive class and often outperforms the resampling and cost-sensitive strategies employing base classifiers like decision tree and support vector machine.


### 7.2. Dynamic-Sized NeighborhoodkNN without Parameters

#### 7.2.1. Gravitational Fixed Radius Nearest Neighbor (GFRNN)

The methods introduced above often have many parameters and complex structure [33], leading to their high time complexity. These methods include the class weighted kNN [12], the examples’ informativeness-based kNN (e.g., LI-kNN [16]), the class confidence-weighted kNN [17], the class conditional nearest neighbor distribution (CCNND) [20] as well as k-ENN [28], and PNN [31] in the previous subsection. In addition, the global information is not fully utilized in these methods.To overcome these drawbacks, a gravitational fixed radius nearest neighbor (GFRNN) algorithm is proposed in [34], which is inspired by the concept of gravitation in classical dynamics. GFRNN is formed by introducing the “gravitation between example pair” into the fixed radius nearest neighbor method. Concretely, GFRNN operates as follows.
(1)
The distance between each example pair is first calculated, and then, their average value is adopted as the neighborhood radiusR of a test example, which is shown in(12)R=12NN−1∑xi,xj∈Ddistxi,xj.In formula (12), D denotes the training set. Thus, the neighborhood of test example xt can be described in formula (13), which is constituted by training examples having a distance no more than R with xt.
(13)Sxt=xi∣xi∈D∧distxi,xt≤R.(2)
Computing the gravitation between each training example in the neighborhood and the test example, which can be achieved using(14)fxt,xi=Gmxtmxidxt,xi2,i=1,2,⋯,Sxt.To simplify the computation, both the gravitational constantG and the mass mxt of test example xt are set to 1, where mass mxt is essentially the weight of test example xt. Thus, only the mass mxi of training example xi in the neighborhood needs to be determined. To balance the effects of the positive and negative examples in the neighborhood, the mass of each training example is calculated using formula (15), where Dp (Dn) denotes the set of positive (negative) examples in training set D. It is easy to see that the mass (weight) of positive examples in the neighborhood is the ratio between the number of negative examples and that of positive examples in training set D, i.e., the class imbalance ratio IR. In addition, the mass (weight) of negative examples is set to 1 in GFRNN.
(15)mxi=IR,ifxi∈Sxt∧xi∈Dp,1,ifxi∈Sxt∧xi∈Dn.(3)
Making a decision according to the gravitation of training examples in the neighborhood to the test example(16)Fxt=∑i=1nposxtIRdxt,xi−∑j=1nnegxt1dxt,xj,wherenposxt and nnegxt in formula (16) are, respectively, the numbers of positive and negative examples in the neighborhood Sxt of test example xt. Formula (16) indicates that GFRNN makes a decision in this way: if the gravitation sum of positive examples in Sxt is larger than that of the negative examples, then xt is classified to be a positive example; otherwise, xt is classified as a negative example.It can be learned from the above illustration that, in determining the neighborhood for a test example, GFRNN does not require any parameter and only utilizes thisglobal information: the average distance among training example pairs. In addition, another global information, i.e., the class imbalance ratio IR in the training set, is used as the weight of positive neighbors. To sum up, GFRNN has the following advantage: it can effectively address the class imbalanced problem and does not require the initialization or adjustment of any parameters, which further extends the family of kNN classification algorithms. On the other hand, GFRNN only employs the overall class imbalance ratio IR in the training set to set weights for positive neighbors but does not utilize any local information concerning training examples, which can be seen as its disadvantage. To solve this problem, the following two works, respectively, present a solution.


#### 7.2.2. Two Improvement Algorithms for GFRNN

(1) The First Improvement Algorithm. An entropy and gravitation-based dynamic radius nearest neighbor (EGDRNN) is proposed in [35]; its differences with GFRNN mainly lie in the following two aspects.
(a)
Neighborhood radius determinationEGDRNN determines the radius of test examplext’s neighborhood by first computing its average distance avgdistDpxt to the positive examples Dpos in training set D and its average distance avgdistDnxt to the negative examples Dneg in training set D, respectively, and then taking the sum of these two values as the neighborhood radius, which is shown in formula (17).
(17)Rxt=avgdistDpxt+avgdistDnxt=1npos∑i=1nposdistxt,xi+1nneg∑j=1nnegdistxt,xj.Therefore, the radius determined by EGDRNN for a test example depends on the location of test example with respect to the positive and negative classes and varies with different test examples.(b)
Weighting strategy for examples in neighborhoodIn addition to IR, EGDRNN also introduces the information entropy concept to make examples in different locations have different degrees of importance. Concretely, for training examplexi (i=1,2,⋯,∣Sxt∣) in neighborhood, EGDRNN computes its information entropy Exi using formula (18). C1 and C2 denote the positive and negative classes, respectively; pxi,C1 denotes the probability of example xi belonging to the positive class while pxi,C2 denotes the probability of example xi for the negative class, where probability pxi,C1 is calculated using the proportion of positive examples in the k neighborhood of example xi while pxi,C2 is calculated using the corresponding proportion of negative examples. It can be seen that the smaller the information entropy of xi the higher the certainty degree of its belonging to a certain class; otherwise, the larger the information entropy, the lower the certainty degree, i.e., it is closer to the decision boundary.
(18)Exi=−pxi,C1lnpxi,C1−pxi,C2lnpxi,C2.To sum up, for a test example, the gravitation sum of examples in its neighborhood is calculated as follows:(19)Fxt=∑i=1nposxtIR∗Exidxt,xi−∑j=1nnegxtExjdxt,xj.Formula (19) demonstrates that EGDRNN pays more attention to the positive examples in the neighborhood as well as the examples that are close to the class boundary. Experimental results indicate that EGDRNN not only achieves a high classification accuracy but also has the lowest time cost among the comparison algorithms.(2) The Second Improvement Algorithm. The improvements made in [33] lie in the following aspects. When determining the weight for neighboring training example xi (i=1,2,⋯,∣Sxt∣), in addition to IR, the gravitation from other examples xj (xj∈D,xj≠xi) to the current example xi is also considered to calculate its weight. The authors in [30] believe that, for a training example, the larger the sum of gravitation from other examples, the denser its surrounding examples (local information), and they regard such training example as unimportant and assign relatively low mass (weight) for it. In this way, both the global example information (i.e., IR) and this local information are utilized in determining the weights for neighbors.


## 7.1. Dynamic-Sized NeighborhoodkNN with Parameters

### 7.1.1. Positive-Biased Nearest Neighbor PNN

The Positive-biased Nearest Neighbor (PNN) algorithm is designed in [31] to improve the sensitivity of kNN to positive class. PNN first dynamically constructs the neighborhood of a test example and then adjusts the classification result according to the local class distribution in the neighborhood.
(1)
Constructing the “k/2 Positive Nearest Neighborhood (k/2-PNN)” for each test example to expand the neighborhood for decision makingCompute the distances from test examplext to all the training examples and rearrange the training examples in ascending order according to their distances, then find the k/2 number of positive nearest neighbors of xt that constitute the neighborhood Sk/2pxt. Sk/2pxt usually contains more examples than xt’s k neighborhood Skxt, i.e., r=∣Sk/2pxt∣>k. As displayed in Figure 6(a), the test example is denoted using symbol “∗” and the positive and negative examples are denoted using symbols “+” and “-,” respectively. When k=5, the neighborhood having k/2=5/2=3 positive training examples contains r=8 examples in total, in this case r>k, and an “extended neighborhood” Sk/2pxt is obtained for test example xt.
(2)
Making decision based on whether “k/2-PNN” is a positive subconceptFigure 6
Schematic diagram of neighborhood in PNN.
(a)
r>k(b)
r<k(c)
r<k(d)
r=kIf the ratio of positive examples inSk/2pxt is much higher than that in the overall training set D, then Sk/2pxt is considered to be a positive class subconcept and k/2/k>1/2 is set as the posterior probability of the test example for the positive class, i.e., xt is classified as a positive class example. Otherwise, if Sk/2pxt is not a positive subconcept, then the ratio (i.e., k/2/r) of positive examples in Sk/2pxt is regarded as the posterior probability of xt for the positive class; in this case, the probability is usually less than 0.5, i.e., xt is classified as a negative example.For instance, if the neighborhood in Figure6(a) is a positive class subconcept, then the probability of the test example with respect to the positive class is P+∣xt=k/2/k=3/5>1/2; thus, the classification result of PNN is the positive class; otherwise, the probability is P+∣xt=k/2/r=3/8<1/2; thus, the test example is classified as a negative example. For the case that there are less than k examples in Sk/2pxt as shown in Figures 6(b) and 6(c), which rarely occurs under the class imbalanced scenario, it indicates that the positive examples are densely distributed around the test example and the corresponding probability is P+∣xt=k/2/r=3/4>1/2, i.e., the decision of PNN is the positive class. For the case that Sk/2pxt has the same size with k neighborhood Skxt as shown in Figure 6(d), PNN degrades to kNN.Experiments in [31] indicate that the simple and effective decision bias of PNN can better classify positive examples, and PNN usually outperforms k-ENN [28] and achieves comparable performance with CCW-kNN [17] mentioned in previous sections. In terms of efficiency, PNN has a much lower computation cost than the two methods that require a “training phase”: (1) k-ENN needs to determine all the exemplar positive examples in the training phase to expand its decision boundary while (2) CCW-kNN computes the weight of each training example by using the mixture model and the Bayesian network. Therefore, both the two methods have a high computation cost. In addition, PNN also outperforms oversampling techniques like SMOTE as well as cost-sensitive strategies like MetaCost.


### 7.1.2.k Rare-Class Nearest Neighbor Algorithm

k Rare-class Nearest Neighbor (kRNN) is proposed in [32], which has a similar idea with PNN introduced in the previous subsection. kRNN also constructs a test example-dependent dynamic-sized neighborhood and then adjusts the posterior probability of the test example according to the positive examples’ distribution in the extended neighborhood. The differences between kRNN and PNN mainly lie in the following two aspects.
(1)
For test examplext, its neighborhood constructed by kRNN contains at least k′ positive examples, where k′ is set to be a constant and takes values 1 or 3 in most cases(2)
When calculating the test example’s posterior probability of belonging to the positive class, the local and global confidence intervals of the positive class are both utilized, making the obtained probabilityP+∣xt more accurate than the one (i.e., k/2/k) obtained by PNNIt is experimentally demonstrated thatkRNN significantly improves the classification performance of kNN for positive class and often outperforms the resampling and cost-sensitive strategies employing base classifiers like decision tree and support vector machine.


## 7.1.1. Positive-Biased Nearest Neighbor PNN

The Positive-biased Nearest Neighbor (PNN) algorithm is designed in [31] to improve the sensitivity of kNN to positive class. PNN first dynamically constructs the neighborhood of a test example and then adjusts the classification result according to the local class distribution in the neighborhood.
(1)
Constructing the “k/2 Positive Nearest Neighborhood (k/2-PNN)” for each test example to expand the neighborhood for decision makingCompute the distances from test examplext to all the training examples and rearrange the training examples in ascending order according to their distances, then find the k/2 number of positive nearest neighbors of xt that constitute the neighborhood Sk/2pxt. Sk/2pxt usually contains more examples than xt’s k neighborhood Skxt, i.e., r=∣Sk/2pxt∣>k. As displayed in Figure 6(a), the test example is denoted using symbol “∗” and the positive and negative examples are denoted using symbols “+” and “-,” respectively. When k=5, the neighborhood having k/2=5/2=3 positive training examples contains r=8 examples in total, in this case r>k, and an “extended neighborhood” Sk/2pxt is obtained for test example xt.
(2)
Making decision based on whether “k/2-PNN” is a positive subconceptFigure 6
Schematic diagram of neighborhood in PNN.
(a)
r>k(b)
r<k(c)
r<k(d)
r=kIf the ratio of positive examples inSk/2pxt is much higher than that in the overall training set D, then Sk/2pxt is considered to be a positive class subconcept and k/2/k>1/2 is set as the posterior probability of the test example for the positive class, i.e., xt is classified as a positive class example. Otherwise, if Sk/2pxt is not a positive subconcept, then the ratio (i.e., k/2/r) of positive examples in Sk/2pxt is regarded as the posterior probability of xt for the positive class; in this case, the probability is usually less than 0.5, i.e., xt is classified as a negative example.For instance, if the neighborhood in Figure6(a) is a positive class subconcept, then the probability of the test example with respect to the positive class is P+∣xt=k/2/k=3/5>1/2; thus, the classification result of PNN is the positive class; otherwise, the probability is P+∣xt=k/2/r=3/8<1/2; thus, the test example is classified as a negative example. For the case that there are less than k examples in Sk/2pxt as shown in Figures 6(b) and 6(c), which rarely occurs under the class imbalanced scenario, it indicates that the positive examples are densely distributed around the test example and the corresponding probability is P+∣xt=k/2/r=3/4>1/2, i.e., the decision of PNN is the positive class. For the case that Sk/2pxt has the same size with k neighborhood Skxt as shown in Figure 6(d), PNN degrades to kNN.Experiments in [31] indicate that the simple and effective decision bias of PNN can better classify positive examples, and PNN usually outperforms k-ENN [28] and achieves comparable performance with CCW-kNN [17] mentioned in previous sections. In terms of efficiency, PNN has a much lower computation cost than the two methods that require a “training phase”: (1) k-ENN needs to determine all the exemplar positive examples in the training phase to expand its decision boundary while (2) CCW-kNN computes the weight of each training example by using the mixture model and the Bayesian network. Therefore, both the two methods have a high computation cost. In addition, PNN also outperforms oversampling techniques like SMOTE as well as cost-sensitive strategies like MetaCost.


## 7.1.2.k Rare-Class Nearest Neighbor Algorithm

k Rare-class Nearest Neighbor (kRNN) is proposed in [32], which has a similar idea with PNN introduced in the previous subsection. kRNN also constructs a test example-dependent dynamic-sized neighborhood and then adjusts the posterior probability of the test example according to the positive examples’ distribution in the extended neighborhood. The differences between kRNN and PNN mainly lie in the following two aspects.
(1)
For test examplext, its neighborhood constructed by kRNN contains at least k′ positive examples, where k′ is set to be a constant and takes values 1 or 3 in most cases(2)
When calculating the test example’s posterior probability of belonging to the positive class, the local and global confidence intervals of the positive class are both utilized, making the obtained probabilityP+∣xt more accurate than the one (i.e., k/2/k) obtained by PNNIt is experimentally demonstrated thatkRNN significantly improves the classification performance of kNN for positive class and often outperforms the resampling and cost-sensitive strategies employing base classifiers like decision tree and support vector machine.


## 7.2. Dynamic-Sized NeighborhoodkNN without Parameters

### 7.2.1. Gravitational Fixed Radius Nearest Neighbor (GFRNN)

The methods introduced above often have many parameters and complex structure [33], leading to their high time complexity. These methods include the class weighted kNN [12], the examples’ informativeness-based kNN (e.g., LI-kNN [16]), the class confidence-weighted kNN [17], the class conditional nearest neighbor distribution (CCNND) [20] as well as k-ENN [28], and PNN [31] in the previous subsection. In addition, the global information is not fully utilized in these methods.To overcome these drawbacks, a gravitational fixed radius nearest neighbor (GFRNN) algorithm is proposed in [34], which is inspired by the concept of gravitation in classical dynamics. GFRNN is formed by introducing the “gravitation between example pair” into the fixed radius nearest neighbor method. Concretely, GFRNN operates as follows.
(1)
The distance between each example pair is first calculated, and then, their average value is adopted as the neighborhood radiusR of a test example, which is shown in(12)R=12NN−1∑xi,xj∈Ddistxi,xj.In formula (12), D denotes the training set. Thus, the neighborhood of test example xt can be described in formula (13), which is constituted by training examples having a distance no more than R with xt.
(13)Sxt=xi∣xi∈D∧distxi,xt≤R.(2)
Computing the gravitation between each training example in the neighborhood and the test example, which can be achieved using(14)fxt,xi=Gmxtmxidxt,xi2,i=1,2,⋯,Sxt.To simplify the computation, both the gravitational constantG and the mass mxt of test example xt are set to 1, where mass mxt is essentially the weight of test example xt. Thus, only the mass mxi of training example xi in the neighborhood needs to be determined. To balance the effects of the positive and negative examples in the neighborhood, the mass of each training example is calculated using formula (15), where Dp (Dn) denotes the set of positive (negative) examples in training set D. It is easy to see that the mass (weight) of positive examples in the neighborhood is the ratio between the number of negative examples and that of positive examples in training set D, i.e., the class imbalance ratio IR. In addition, the mass (weight) of negative examples is set to 1 in GFRNN.
(15)mxi=IR,ifxi∈Sxt∧xi∈Dp,1,ifxi∈Sxt∧xi∈Dn.(3)
Making a decision according to the gravitation of training examples in the neighborhood to the test example(16)Fxt=∑i=1nposxtIRdxt,xi−∑j=1nnegxt1dxt,xj,wherenposxt and nnegxt in formula (16) are, respectively, the numbers of positive and negative examples in the neighborhood Sxt of test example xt. Formula (16) indicates that GFRNN makes a decision in this way: if the gravitation sum of positive examples in Sxt is larger than that of the negative examples, then xt is classified to be a positive example; otherwise, xt is classified as a negative example.It can be learned from the above illustration that, in determining the neighborhood for a test example, GFRNN does not require any parameter and only utilizes thisglobal information: the average distance among training example pairs. In addition, another global information, i.e., the class imbalance ratio IR in the training set, is used as the weight of positive neighbors. To sum up, GFRNN has the following advantage: it can effectively address the class imbalanced problem and does not require the initialization or adjustment of any parameters, which further extends the family of kNN classification algorithms. On the other hand, GFRNN only employs the overall class imbalance ratio IR in the training set to set weights for positive neighbors but does not utilize any local information concerning training examples, which can be seen as its disadvantage. To solve this problem, the following two works, respectively, present a solution.


### 7.2.2. Two Improvement Algorithms for GFRNN

(1) The First Improvement Algorithm. An entropy and gravitation-based dynamic radius nearest neighbor (EGDRNN) is proposed in [35]; its differences with GFRNN mainly lie in the following two aspects.
(a)
Neighborhood radius determinationEGDRNN determines the radius of test examplext’s neighborhood by first computing its average distance avgdistDpxt to the positive examples Dpos in training set D and its average distance avgdistDnxt to the negative examples Dneg in training set D, respectively, and then taking the sum of these two values as the neighborhood radius, which is shown in formula (17).
(17)Rxt=avgdistDpxt+avgdistDnxt=1npos∑i=1nposdistxt,xi+1nneg∑j=1nnegdistxt,xj.Therefore, the radius determined by EGDRNN for a test example depends on the location of test example with respect to the positive and negative classes and varies with different test examples.(b)
Weighting strategy for examples in neighborhoodIn addition to IR, EGDRNN also introduces the information entropy concept to make examples in different locations have different degrees of importance. Concretely, for training examplexi (i=1,2,⋯,∣Sxt∣) in neighborhood, EGDRNN computes its information entropy Exi using formula (18). C1 and C2 denote the positive and negative classes, respectively; pxi,C1 denotes the probability of example xi belonging to the positive class while pxi,C2 denotes the probability of example xi for the negative class, where probability pxi,C1 is calculated using the proportion of positive examples in the k neighborhood of example xi while pxi,C2 is calculated using the corresponding proportion of negative examples. It can be seen that the smaller the information entropy of xi the higher the certainty degree of its belonging to a certain class; otherwise, the larger the information entropy, the lower the certainty degree, i.e., it is closer to the decision boundary.
(18)Exi=−pxi,C1lnpxi,C1−pxi,C2lnpxi,C2.To sum up, for a test example, the gravitation sum of examples in its neighborhood is calculated as follows:(19)Fxt=∑i=1nposxtIR∗Exidxt,xi−∑j=1nnegxtExjdxt,xj.Formula (19) demonstrates that EGDRNN pays more attention to the positive examples in the neighborhood as well as the examples that are close to the class boundary. Experimental results indicate that EGDRNN not only achieves a high classification accuracy but also has the lowest time cost among the comparison algorithms.(2) The Second Improvement Algorithm. The improvements made in [33] lie in the following aspects. When determining the weight for neighboring training example xi (i=1,2,⋯,∣Sxt∣), in addition to IR, the gravitation from other examples xj (xj∈D,xj≠xi) to the current example xi is also considered to calculate its weight. The authors in [30] believe that, for a training example, the larger the sum of gravitation from other examples, the denser its surrounding examples (local information), and they regard such training example as unimportant and assign relatively low mass (weight) for it. In this way, both the global example information (i.e., IR) and this local information are utilized in determining the weights for neighbors.


## 7.2.1. Gravitational Fixed Radius Nearest Neighbor (GFRNN)

The methods introduced above often have many parameters and complex structure [33], leading to their high time complexity. These methods include the class weighted kNN [12], the examples’ informativeness-based kNN (e.g., LI-kNN [16]), the class confidence-weighted kNN [17], the class conditional nearest neighbor distribution (CCNND) [20] as well as k-ENN [28], and PNN [31] in the previous subsection. In addition, the global information is not fully utilized in these methods.To overcome these drawbacks, a gravitational fixed radius nearest neighbor (GFRNN) algorithm is proposed in [34], which is inspired by the concept of gravitation in classical dynamics. GFRNN is formed by introducing the “gravitation between example pair” into the fixed radius nearest neighbor method. Concretely, GFRNN operates as follows.
(1)
The distance between each example pair is first calculated, and then, their average value is adopted as the neighborhood radiusR of a test example, which is shown in(12)R=12NN−1∑xi,xj∈Ddistxi,xj.In formula (12), D denotes the training set. Thus, the neighborhood of test example xt can be described in formula (13), which is constituted by training examples having a distance no more than R with xt.
(13)Sxt=xi∣xi∈D∧distxi,xt≤R.(2)
Computing the gravitation between each training example in the neighborhood and the test example, which can be achieved using(14)fxt,xi=Gmxtmxidxt,xi2,i=1,2,⋯,Sxt.To simplify the computation, both the gravitational constantG and the mass mxt of test example xt are set to 1, where mass mxt is essentially the weight of test example xt. Thus, only the mass mxi of training example xi in the neighborhood needs to be determined. To balance the effects of the positive and negative examples in the neighborhood, the mass of each training example is calculated using formula (15), where Dp (Dn) denotes the set of positive (negative) examples in training set D. It is easy to see that the mass (weight) of positive examples in the neighborhood is the ratio between the number of negative examples and that of positive examples in training set D, i.e., the class imbalance ratio IR. In addition, the mass (weight) of negative examples is set to 1 in GFRNN.
(15)mxi=IR,ifxi∈Sxt∧xi∈Dp,1,ifxi∈Sxt∧xi∈Dn.(3)
Making a decision according to the gravitation of training examples in the neighborhood to the test example(16)Fxt=∑i=1nposxtIRdxt,xi−∑j=1nnegxt1dxt,xj,wherenposxt and nnegxt in formula (16) are, respectively, the numbers of positive and negative examples in the neighborhood Sxt of test example xt. Formula (16) indicates that GFRNN makes a decision in this way: if the gravitation sum of positive examples in Sxt is larger than that of the negative examples, then xt is classified to be a positive example; otherwise, xt is classified as a negative example.It can be learned from the above illustration that, in determining the neighborhood for a test example, GFRNN does not require any parameter and only utilizes thisglobal information: the average distance among training example pairs. In addition, another global information, i.e., the class imbalance ratio IR in the training set, is used as the weight of positive neighbors. To sum up, GFRNN has the following advantage: it can effectively address the class imbalanced problem and does not require the initialization or adjustment of any parameters, which further extends the family of kNN classification algorithms. On the other hand, GFRNN only employs the overall class imbalance ratio IR in the training set to set weights for positive neighbors but does not utilize any local information concerning training examples, which can be seen as its disadvantage. To solve this problem, the following two works, respectively, present a solution.


## 7.2.2. Two Improvement Algorithms for GFRNN

(1) The First Improvement Algorithm. An entropy and gravitation-based dynamic radius nearest neighbor (EGDRNN) is proposed in [35]; its differences with GFRNN mainly lie in the following two aspects.
(a)
Neighborhood radius determinationEGDRNN determines the radius of test examplext’s neighborhood by first computing its average distance avgdistDpxt to the positive examples Dpos in training set D and its average distance avgdistDnxt to the negative examples Dneg in training set D, respectively, and then taking the sum of these two values as the neighborhood radius, which is shown in formula (17).
(17)Rxt=avgdistDpxt+avgdistDnxt=1npos∑i=1nposdistxt,xi+1nneg∑j=1nnegdistxt,xj.Therefore, the radius determined by EGDRNN for a test example depends on the location of test example with respect to the positive and negative classes and varies with different test examples.(b)
Weighting strategy for examples in neighborhoodIn addition to IR, EGDRNN also introduces the information entropy concept to make examples in different locations have different degrees of importance. Concretely, for training examplexi (i=1,2,⋯,∣Sxt∣) in neighborhood, EGDRNN computes its information entropy Exi using formula (18). C1 and C2 denote the positive and negative classes, respectively; pxi,C1 denotes the probability of example xi belonging to the positive class while pxi,C2 denotes the probability of example xi for the negative class, where probability pxi,C1 is calculated using the proportion of positive examples in the k neighborhood of example xi while pxi,C2 is calculated using the corresponding proportion of negative examples. It can be seen that the smaller the information entropy of xi the higher the certainty degree of its belonging to a certain class; otherwise, the larger the information entropy, the lower the certainty degree, i.e., it is closer to the decision boundary.
(18)Exi=−pxi,C1lnpxi,C1−pxi,C2lnpxi,C2.To sum up, for a test example, the gravitation sum of examples in its neighborhood is calculated as follows:(19)Fxt=∑i=1nposxtIR∗Exidxt,xi−∑j=1nnegxtExjdxt,xj.Formula (19) demonstrates that EGDRNN pays more attention to the positive examples in the neighborhood as well as the examples that are close to the class boundary. Experimental results indicate that EGDRNN not only achieves a high classification accuracy but also has the lowest time cost among the comparison algorithms.(2) The Second Improvement Algorithm. The improvements made in [33] lie in the following aspects. When determining the weight for neighboring training example xi (i=1,2,⋯,∣Sxt∣), in addition to IR, the gravitation from other examples xj (xj∈D,xj≠xi) to the current example xi is also considered to calculate its weight. The authors in [30] believe that, for a training example, the larger the sum of gravitation from other examples, the denser its surrounding examples (local information), and they regard such training example as unimportant and assign relatively low mass (weight) for it. In this way, both the global example information (i.e., IR) and this local information are utilized in determining the weights for neighbors.


## 8. Conclusion

kNN is a simple and effective base learning algorithm and can achieve comparable classification performance with more complex classifiers such as decision tree and artificial neural networks. However, kNN does not work well on imbalanced data due to the usage of overall classification accuracy as its optimization objective as well as its majority voting-based classification rule. To solve this problem, researchers have conducted many works and proposed a lot of solutions. This paper gives a comprehensive survey of these works according to their adopted perspectives and analyzes and compares their characteristics. What is more, there are still some problems that deserve further study in this field. For instance, we list three of them in the following:
(1)
Most algorithms introduced in this paper mainly consider the case that there is only one positive class in imbalanced data; thus, in the case of two or more positive classes, how to adjust these algorithms to make them work is an important problem(2)
For the global information-based algorithm GI-kNN, how to improve the robustness of its adopted information metric to noisy training examples needs to be investigated(3)
For the online streaming data in which the class imbalance degree can change with time, only the class conditional nearest neighbor distribution algorithm CCNND introduced in Section2 is applicable to this scenario. Thus, more efforts need to be made to make other methods introduced in this paper also suitable to online streaming data



---

*Source: 5520990-2021-03-03.xml*