{'fraction_non_alphanumeric': 0.032028273234303385, 'fraction_numerical': 0.008669722237561434, 'mean_word_length': 4.727387729285263, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
NPC: Neighbors Progressive Competition Algorithm for Classification of Imbalanced Data Sets

Learning from many real-world datasets is limited by a problem called the class imbalance problem. A dataset is imbalanced when one class (the majority class) has significantly more samples than the other class (the minority class). Such datasets cause typical machine learning algorithms to perform poorly on the classification task. To overcome this issue, this paper proposes a new approach Neighbors Progressive Competition (NPC) for classification of imbalanced datasets. Whilst the proposed algorithm is inspired by weighted k-Nearest Neighbor (k-NN) algorithms, it has major differences from them. Unlike k- NN, NPC does not limit its decision criteria to a preset number of nearest neighbors. In contrast, NPC considers progressively more neighbors of the query sample in its decision making until the sum of grades for one class is much higher than the other classes. Furthermore, NPC uses a novel method for grading the training samples to compensate for the imbalance issue. The grades are calculated using both local and global information. In brief, the contribution of this paper is an entirely new classifier for handling the imbalance issue effectively without any manually-set parameters or any need for expert knowledge. Experimental results compare the proposed approach with five representative algorithms applied to fifteen imbalanced datasets and illustrate this algorithms effectiveness.


I. INTRODUCTION
Massive amounts of real-world data are gathered by different corporations every day. While these huge amounts of data have created great potential for knowledge discovery, the amount of knowledge extraction is sometimes limited by a common problem amongst real-world datasets, which is the class imbalance problem, i.e. when the number of data samples belonging to one class far surpasses the number of data samples belonging to each of the other classes. Some examples for such class imbalance problems would be diagnosis of rare diseases [1], detection of fraudulent telephone calls [2], network intrusion detection [3] and detection of oil spills in radar images [4]. Dealing with imbalance problem can be troublesome for classifiers as they tend to favor the class that most samples belong to [5]. Furthermore, the class with the least samples is usually the one of prime interest [6]. This class with the least samples is commonly referred to as "minority/positive class", while the other class is called "majority/negative class". Conventional machine learning research is concerned with balanced data sets in which the number of different class samples are approximately equal. Therefore, when faced with imbalanced data sets, the classifier does not learn the minority class features effectively, leading to misclassification of many minority samples [7]. Furthermore, when the class imbalance problem is combined with the "class overlapping problem", a very sophisticated classification problem will be at hand [8], [9].
One deciding factor of the class imbalance problem's severity is Imbalance Ratio (IR). Imbalance ratio is simply the ratio of the number of majority class samples to the number of minority class samples, and can be expressed as below: where -./ and -0% refer to the number of majority and minority class samples, respectively. Generally, data sets with higher imbalance ratios are harder to learn from.
Over the years, coming up with a fitting solution for handling the imbalanced data classification problem has been the focus of many researchers. Various different approaches have been suggested for handling the imbalance issue that can be categorized into the following three groups [10]:

A. Data level methods
Data level approaches work by resampling the training samples in order to achieve a more balanced dataset. This is done by either over-sampling the minority classes' samples, undersampling the majority classes' samples, or applying hybrid models which are a combination of over-sampling and undersampling techniques. Such methods are considered preprocessing approaches for dealing with the class imbalance problem. As a result, one inevitable disadvantage of this method is that it changes the original distribution of data. In addition, under-sampling can sacrifice valuable information from the majority class, while over-sampling increases the training computation's complexity and in some cases it can increase the potential for overfitting [11], [12]. One famous and widely used technique to avoid the overfitting problem is the "Synthetic Minority Oversampling Technique" (SMOTE) by Chawla et al. [11]. The main idea of this algorithm is to generate new minority class samples using linear interpolation between minority samples that lie close together. However, the drawback of SMOTE is that it can generate some minority samples that lie in the majority class region, which could not only lead to overgeneralization, but also cause overlapping between classes. Many hybrid algorithms were later on built upon SMOTE to overcome this drawback [13]; some of these hybrid algorithms are Borderline-SMOTE [14], Adaptive Synthetic Sampling (ADASYN) [15], Safe-level-SMOTE [16] and local neighborhood SMOTE [17].
On another note, according to the literature [18], the quality of resampling techniques is heavily dependent on the resampling factor. Moreover, the effectiveness of resampling also depends on the classifier that is later used for the data. In fact, there is no single resampling technique that always outperforms others, e.g. one resampling method might outperform other resampling techniques when used in collaboration with a Support Vector Machine (SVM), but perform worse than others when used in collaboration with a Decision Tree (DT). Lastly, the impact of a resampling technique on the classification task also depends on the dataset. In some cases, choosing the wrong resampling technique might negatively affect the classification task [18].

B. Algorithmic level methods
Algorithmic level methods include modifying previous machine learning algorithms in order to deal with the imbalance between classes directly; e.g. by assigning weights to training samples. An algorithm that has received a lot of attention in this prospect is k-Nearest Neighbor (k-NN) [19][20][21][22][23]. This is because k-NN is one of the most efficient and simplest classifiers in conventional machine learning tasks. However, k-NN's performance diminishes when the dataset is imbalanced [24]. One of the proposed methods to overcome this drawback is the K Exemplar-based Nearest Neighbor algorithm (ENN) [19]. ENN is categorized as a pattern-oriented method, so it relies on intensifying the influence of minority class samples. The ENN algorithm works by selecting the pivot minority class samples and expanding their boundaries into Gaussian balls. The Positive-biased Nearest Neighbor (PNN) [20] is another patternoriented method similar to ENN, but it does not have a training phase. Therefore, PNN is a faster algorithm than ENN. In contrast to the pattern-oriented methods, there are the distribution-oriented methods, which rely on acquiring useful prior knowledge of the data distribution. The Class Based Weighted k Nearest Neighbor is one of these methods as it weighs the samples based on the calculated misclassification rate of k-NN [21]. Informative k Nearest Neighbor-localized version (Ll-kNN) [22] and Class Conditional Nearest Neighbor Distribution (CCNND) [23] are two other examples of distribution-oriented methods.
Many of the previously mentioned algorithms rely on using global information to effectively make more accurate decisions; however, their learning models are often too complex. Moreover, some of them require many parameters to be tuned, so they are computationally expensive and time consuming [24]. To overcome this limitation, the Gravitational Fixed Radius Nearest Neighbor algorithm (GFRNN) was proposed in [24]. In the classification process, GFRNN assigns mass values to training samples, and then classifies the query sample based on the sum of gravitational forces caused by its neighbors within a distance of R. While GFRNN is a useful classifier for class imbalance problems, it does not use local information for defining the training samples' masses [25]. Further improvements for GFRNN have been proposed to address this limitation in literature [25].
It should also be noted that all of the discussed algorithms limit their decision criteria to a fixed number (or radius) of the query sample's neighbors. This number remains the same regardless of the query sample's position in the feature space.

C. Ensemble methods
Ensemble methods aim to improve the performance of a single classifier by training several classifiers and using their outputs to reach a single class label. An example for ensemble methods would be the SMOTEBoost algorithm [26].
Motivated by the drawbacks of previous algorithmic level methods, we propose a novel and efficient classification algorithm, Neighbors' Progressive Competition (NPC), for dealing with the class imbalance problem. Unlike the previous algorithms, the NPC considers progressively more neighbors of the query sample in its decision making until one class has a much higher grade than the other classes. Furthermore, unlike some of the previous methods, NPC does not use manually-set parameters, which require an expert's judgment, making it an easy-to-approach algorithm. Moreover, NPC does not have any parameters that require automated tuning; rather it relies on simple but meaningful calculations to make decisions. The proposed approach has been extensively tested on 15 imbalanced datasets and compared with 5 representative algorithms to validate the effectiveness and efficiency of NPC.
The remainder of this paper is organized as follows. We introduce the proposed method and its components in Section II. Experiments and results are presented and analyzed in Section III, and a conclusion is reached and future plans are discussed in Section IV.

A. Terminology and Fundamentals
In this paper, our focus is on the binary classification task for an imbalanced data set. Let 0 ∈ 0,1 be the corresponding class Imbalance Ratio ( ) is calculated for the training set of 788 according to Eq. (1). Furthermore, we define the distance measurement function ( . ) in Eq. (3) as the Euclidean distance between two samples and : Although in this paper we adopted the Euclidean distance, any other appropriate distance measurement can be used instead. Lastly, we define the query sample as the sample that needs to be classified.

B. The proposed method
In NPC, the grade values are based on global information and they are independent of the query sample, so they can be calculated before the query sample comes in. Later on, in the classification phase, the query sample determines how the grades will be assigned to the training data based on local information. This way of dividing the role of global and local information allows us to take advantage of them both with minimal computations. The grade value the training sample D , D ∈ 788 receives is based on the following factors: • Class label ( D ): The grades that are assigned to the minority and majority classes are computed using two different formulas to compensate for the class imbalance problem.
• Imbalance Ratio ( ): The higher the imbalance ratio, the more the grades need to favor the minority class samples. This is to compensate for the increased severity of the class imbalance problem.
• Rank ( H I ): Let us assume that the training sample D , D ∈ 788 is the 'th nearest neighbor of the query sample , then the rank of D ( H I ) is defined as: (4) The way the value of H I effects the grades is heavily dependent on the class label D . If D belongs to the minority class, a lower rank will yield D a higher grade, as one expects. As the ranks increase, the minority samples will yield lesser grades.
On the other hand, if D belongs to the majority class, a lower rank will result in a lower grade for D . This is very important because usually the first nearest neighbors of many minority samples are from the majority class; therefore, the classifier's decision for the class label of query should not be heavily biased by the lower ranked majority-class nearest neighbors. Furthermore, unlike k-NN based methods, NPC considers progressively more nearest neighbors as long as the two classes are close in grades. That means for higher ranked samples to be considered in the decision, the competition between lower ranked samples needs to be close. Since lower ranked minority samples have much higher grade values than lower ranked majority samples, the competition will only be close if the lower ranked neighbors were predominantly of the majority class. Therefore, higher ranked samples only start contributing if the nearest neighbors of were predominantly of the majority class; thus, a higher ranked majority class sample will have a large grade because it declares that the lower ranks were predominantly from the majority class. Hence, the classifier should start getting more confident in deciding the majority class as the winner.  Fig. 1 shows plots of these equations, demonstrating how the values of -0% and -./ change with the increase of H I in a dataset with 500 samples and an IR of 10. Since we know rank values are going to be every natural number from 1 to 788 and the class label is either 0 or 1, we can define a reference grades matrix , which holds all the grade values that will be assigned to the samples: , 2 = -0% .
This process is done before the query sample comes in. So, the grades are pre-calculated and kept in the matrix and can be conveniently looked up in the classification phase.
After the query sample comes in, the rank of every training sample is calculated and the grade values in are assigned to training samples according to their rank and label; e.g. for the minority sample D which is the 'th nearest neighbor of , the corresponding grade value is ( , 2). Then, the grades get accumulated starting from the first rank's grade and progressing onwards until the absolute value of this summation is greater than _ ℎ ℎ, where _ ℎ ℎ is the winning threshold and is equal to 0.7× . This dynamic formula for the winning threshold proved to be suitable over a wide range of datasets in our experiments. When the absolute value of the summation is greater than _ ℎ ℎ, the classifier makes a decision based on the sign of the summation; i.e. the query sample is labeled as a minority class sample if the sum of grades was positive, and it is labeled as a majority class sample if the sum of grades was negative. _ ℎ ℎ = 0.7× ; 4. For ∀ 0 ∈ 788 Do a. Calculate the ranks for every D ∈ 788 ; b. Assign grade values to training set from ; c. Calculate the cumulative sum of these grades from first to last rank and store in vector ; d. Find first array of with an absolute value greater than _ ℎ ℎ and store it in ; e. If >0: 0 =1; f. If <0: 0 =0; 5. End For 6. Return ( 788 ) Fig.1. The effect of a sample's rank and class on the absolute value of its grade for a dataset with 500 samples and an Imbalance Ratio of 10.

III. EXPERIMENTAL RESULTS
The effectiveness of the proposed method has been tested on 15 imbalanced datasets from the KEEL repository [27] (http://www.keel.es/dataset.php). The detailed descriptions of these datasets such as the number of features, number of instances and IR are available in Table I. The datasets are partitioned using Five-Fold Cross Validation (5FCV) [28]. The performance measures we use are the Geometric Means (GM) and the average processing time. GM is a very popular performance measure in imbalance learning as it represents the accuracy in minority and majority class samples simultaneously. To define GM, first we define the True Positive Rate ( R.gh ) and the True Negative Rate ( R.gh ) as follows: where TP, TN, FP and FN are values defined in the confusion matrix for two-class problem in Table II. Then, GM is defined as: Here we compare NPC with 5 existing and well-performing k-NN based algorithms, CCNND [23], ENN [19], LI-k-NN [22], PNN [20] and GFRNN [24]. The results of these experiments using the measure are available in Table III. The last three rows of Table III  It could also be seen that NPC achieves the best GM, best average rank and best final rank of all other algorithms over the 15 datasets. Furthermore, the average processing time of NPC, GFRNN, CCNND, ENN, LI-kNN and PNN on 3 largest datasets from Table I is reported in Table IV. The results in Table IV show that NPC achieves the second best average rank in terms of processing time, alongside PNN. It can also be seen that NPC requires less time than CCNND, ENN and LI-kNN while keeping competitive with GFRNN and PNN. Hence, it can be concluded that NPC is an efficient classifier. These results were achieved on AMD Turion Core 2 processors with 2.10 GHz, 4G RAM DDR2, Microsoft Windows 7, MATLAB environment.
Lastly, a non-parametric statistical test, named the Friedman test [29], is used to rank the performance of each algorithm. Here we applied the Friedman test and the Holm post hoc test to the results of Table III and the results are reported in Table V. The results of this table shows that NPC has achieved the best Friedman ranking compared to the other algorithms.

IV. CONCLUSION AND FUTURE WORK
In this paper, we proposed a novel learning model named NPC to address a critical problem in learning from many realworld datasets, the class imbalance problem. In NPC's classification process, grade values are assigned to every training sample based on local and global information. Afterwards, a competition is held for classifying the query   In the future, our plan is to extend the idea of using progressive neighbors, instead of using a preset number of neighbors, to other k-NN based classifiers such as GFRNN. We also plan to extend NPC to be used on multi-class imbalanced datasets.