{'fraction_non_alphanumeric': 0.033422973492124475, 'fraction_numerical': 0.008221283134844411, 'mean_word_length': 4.7695035460992905, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, '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}}
A Density-based Under-sampling Algorithm for Imbalance Classification

Imbalance classification is an interesting issue in machine learning and data mining. In recent years, many related algorithms have been proposed to solve such an issue. Among them, under-sampling is an effective and timesaving data pre-processing method, which balances the dataset by removing some examples from the majority class. However, these proposed under-sampling methods often lose some useful information or ignore noise in the datasets, which will result in the performance degradation. This paper proposes a density-based under-sampling algorithm (DBU) to solve these two problems. In feature space, similar examples are close to each other and noisy example is far from other examples belonging to the same class. Thus the similar examples have a high density while the noisy example has a low density. DBU uses the local density peaks to represent the whole majority class, so that it can retain the useful information and eliminate the noisy examples automatically. To evaluate our algorithm, experiments are conducted on 15 two-class imbalanced datasets. Experimental results show that DBU achieves the better results than other under-sampling methods.


Introduction
Imbalance classification has attracted many researchers' attentions in data mining and machine learning [1,2]. Focusing on two-class problem, a dataset is imbalanced when the number of examples in one class (minority class) is less than the other (majority class) [3]. Many learning algorithms proposed for balanced data always have difficulties to represent the distribution of imbalanced data properly, thus they perform poorly for the imbalanced data. In other words, because the data distribution of imbalanced dataset is skewed, these standard classifiers always classify the minority class examples into majority class [4]. Actually, the minority class is often more interesting and important than the majority class [5].
Many algorithms have been proposed to alleviate the class imbalance problem. These algorithms can be mainly categorized into two groups: algorithmic-level algorithms and data-level algorithms. Algorithmic-level algorithms modify the traditional classifiers for balanced dataset, such that the modified algorithms (SVDD [6], Cost-sensitive methods [7], and Boosting SVM [8]) can be applied to imbalanced dataset. Data-level algorithms oversample the minority class [9] or under-sample the majority class [10] to build a balanced dataset before constructing the classifiers. Compared with algorithmic-level algorithms, data-level algorithms are widely used in imbalance classification because they can be independently performed before the classifier training tasks. In these two sampling strategies, the oversampling methods, which address the imbalance problem by generating synthetic minority class examples, may lead to the over-fitting in the model construction process [11]. As a result, some researchers believe that the under-sampling strategy is superior to the oversampling strategy [12]. However, the under-sampling strategy usually loses some useful information about the majority class [19]. Real-world dataset always contains many similar examples. For the similar examples, one under-sampling strategy is to use one of these similar examples to represent them all while the remaining examples are treated as redundant information. Lin et al. [19] propose a clustering-based under-sampling algorithm (called CBU for short) to retain the useful information. CBU uses the k-means clustering algorithm to cluster the similar examples together and combines the clustering centers with the minority class examples to build a balanced dataset. However, the k-means clustering algorithm is sensitive to initial condition and is not robust to noise. Actually, noise is another important factor affecting the accuracy of classification. In this paper, we propose a densitybased under-sampling algorithm to solve these problems (called DBU for short). Our DBU has its basis in the assumptions that similar examples are relatively close to each other and noise is far from other examples belonging to the same class in feature space. Thus, similar examples have a relative high density and noise has a relative low density. We use the local density peaks to represent the whole majority class, so that it can retain the useful information as much as possible and remove the noise at the same time. Firstly, we estimate the approximately probabilistic distribution of majority class examples by kernel density estimation. Then, we introduce a new evaluation metric to find the local density peaks and remove the noisy examples automatically. Finally, we combine these local density peaks with the original minority class examples to build a balanced dataset. This paper is organized as follows. Section 2 recalls the problems of imbalance classification and some under-sampling algorithms. Section 3 describes our DBU in detail. Section 4 compares our DBU with other under-sampling methods, and Section 5 summarizes this paper.

The Problems of Imbalance Classification
Imbalance ratio is a factor that affects the classification, but it is not the only one. , it can be treated as the example corrupted by class label noise. In this paper, the definition of noise is extended, which any example corrupted by class label noise or attribute noise can be treated as noise [31].

Some Well-known Under-sampling Algorithms
Many under-sampling algorithms have been proposed including RUS, CNN, TL, OSS, NCL and CBU. The details of these algorithms are as follows.   [18]. For any example in the training set, NCL classifies it according to its three nearest neighbors. If a majority class example is classified into minority class, then NCL removes this majority class example. Analogously, if a minority class example is classified into majority class, then NCL removes its nearest neighbors belonging to the majority class.  CBU: Lin et al. [19] cluster the majority class to generate k clusters by using the k-means clustering algorithm [20], with each cluster containing the similar examples. Then they use these cluster centers to represent the whole majority class.

The Proposed Method
Not all examples in the dataset are useful for classification [13]. Some examples may be useless for classification, while some may degrade the classification performance. The former is called redundant example and the latter is called noise.  [27] propose a clustering algorithm (called CFSFDP for short) in which a new approach is introduced to find the local density peaks. However, CFSFDP estimates the densities by setting a cut-off distance artificially, which may affect the clustering results. To overcome this drawback, we use kernel density estimation to estimate an approximately probabilistic distribution for the majority class. Besides, in order to reduce the risk of selecting noise as the element of balanced dataset in the under-sampling process, we modify the metric  in CFSFDP by assigning different weights to local density  and distance . The details of our DBU are as follows.

Local Density 
Kernel density estimation (KDE) is a non-parametric method for estimating the probability distribution density, which combines all the kernel functions generated from the given data to obtain an estimated kernel density function. The KDE function is shown in Equation (1) Where X i is a data in the given sample, n is the number of data points, K(•) is a kernel function and h is the bandwidth of kernel function. In this paper, we use Gaussian kernel to obtain the KDE function of majority class. The original Gaussian kernel function is shown in Equation (2) Where m is the number of attributes. The function d a (x, y), the distance between x and y for attribute a, is calculated by Equation (5).
The function diff a is defined in Equation (6).
Where σ a is the standard deviation of attribute a. The function vdm a is defined in Equation (7).
,, , Where N a,x is the number of x in attribute a, N a,x,c is the number of x in attribute a with the output class be c, C is the number of output classes in dataset D. In Equation (3), the bandwidth h reflects the overall flatness of KDE curve. An inappropriate value of h can cause the KDE curve to be over-smoothing or under-smoothing [24]. Silverman's rule of thumb is an effective method to calculate the optimal bandwidth (h * ) for Gaussian kernel [23].
Where  is the standard deviation. However, the standard deviation is sensitive to noise, thus our DBU uses a corrected standard deviation to replace it [25].

Distance 
For the distance  i of example i, it is measured by calculating its minimum distance to any other example with a higher density [27]. Specially, for the highest density example, we take  i =max j (d ij ). Note that  i is much larger than the typical nearest neighbor distance only for the local density peaks.

Metric 
As Figure 2b shows, local density peaks are the examples (point 1, 9, 10 and 20) with a high density  and a large distance , while noise (point 26, 27 and 28) are the examples with a low density  and an anomalously large distance . CFSFDP measures the probability of an example being a density peak according to the product value of density  and distance . However, as Figure 2c shows, noisy examples (point 26, 27 and 28) have a high value , when =•. This may increase the risk of selecting noise as an element of balanced dataset. In this paper, we introduce a new metric ' to decrease this risk by assigning different weights to the local density  and distance . The definition of ' is shown in Equation (11).
Where α indicates the relative importance of local density  and distance . In this paper, we set α=0.4 according to the experimental results. As Figure 2d shows, when we set α=0. 4

Step 3. S_Ma selects top Nexamples from Ma in descending order of
Step 4. D'= S_MaMi Step 5. return D'

Datasets
In this paper, the experiments are conducted on 15 two-class datasets from the KEEL dataset repository (http://www.keel.es/). To validate our DBU, we use the fivefold cross-validation approach to build the training and test set. The characteristics of these datasets are shown in Table 1. Num is the number of examples, Atts is the number of attributes and IR is the imbalance ratio.

Evaluation Criterion
Average accuracy is a commonly used evaluation criterion in the traditional classification. This evaluation criterion has been proved unsuitable for imbalance classification, since it may lead to the misclassification of minority class examples. Consequently, other evaluation criteria have been proposed successively, including F-Measure, ROC and AUC [28]. In this paper, we use AUC as the evaluation criterion in the follow experiments.

Experimental Results
In this paper, the experiments are conducted with C4.5 as the baseline classifier. Note that C4.5 uses the default parameters in the Weka software package. The experiments can be divided into two parts. In the first experiment, we compare our DBU with RUS, CNN, TL, OSS, NCL and CBU on the 15 two-class KEEL datasets. Table 2 shows the AUC results obtained by C4.5. The best result in each experiment is highlighted in bold and Avg. represents the average AUC result. From Table 2, we observe that our DBU achieves the highest average AUC result. Table 3 shows the Wilcoxon's test results for the comparisons between DBU and other algorithms, where R + and Rare the sums of ranks and P Wilcoxon is the p-value of Wilcoxon's test result. If P Wilcoxon <0.05, it means that the comparison is significantly different. From Table 3, we conclude that our DBU achieves significantly different results than other algorithms. In the second experiment, we corrupt the class labels and attributes of some majority class examples by introducing class noise and attribute noise respectively. Given a noise level x, the introduction schemes are as follows [29].  Table 4 and 6 show the AUC results on class and attribute noisemodified datasets respectively. For both the class and attribute noise-modified datasets, the average AUC results of all these algorithms decrease. Our DBU wins the highest average AUC results no matter which type the noise is (class or attribute noise).

Conclusions
In this paper, we propose an anti-noise under-sampling algorithm, which uses local density peaks to represent the entire majority class. Two experiments are conducted to verify the effectiveness of our DBU. The first experiment is conducted on 15 two-class KEEL datasets and the second experiment is conducted on their noise-modified datasets. Experimental results have shown that our method has the best results on both the imbalanced datasets and their noise-modified datasets. The important fact that makes our DBU suitable for imbalance classification is that it removes the noisy examples and retains the useful information at the same time.