# Probability Density Machine: A New Solution of Class Imbalance Learning

Authors: Ruihan Cheng; Longfei Zhang; Shiqi Wu; Sen Xu; Shang Gao; Hualong Yu
Journal: Scientific Programming
 (2021)

---

## Abstract

Class imbalance learning (CIL) is an important branch of machine learning as, in general, it is difficult for classification models to learn from imbalanced data; meanwhile, skewed data distribution frequently exists in various real-world applications. In this paper, we introduce a novel solution of CIL called Probability Density Machine (PDM). First, in the context of Gaussian Naive Bayes (GNB) predictive model, we analyze the reason why imbalanced data distribution makes the performance of predictive model decline in theory and draw a conclusion regarding the impact of class imbalance that is only associated with the prior probability, but does not relate to the conditional probability of training data. Then, in such context, we show the rationality of several traditional CIL techniques. Furthermore, we indicate the drawback of combining GNB with these traditional CIL techniques. Next, profiting from the idea of K-nearest neighbors probability density estimation (KNN-PDE), we propose the PDM which is an improved GNB-based CIL algorithm. Finally, we conduct experiments on lots of class imbalance data sets, and the proposed PDM algorithm shows the promising results.


---

## Body

## 1. Introduction

Learning from imbalanced data is an important and hot topic in machine learning, as it has been widely applied to diagnose and classify diseases [1, 2], detect software defects [3, 4], analyze biology and pharmacology data [5, 6], evaluate credit risk [7], predict actionable revenue change and bankruptcy [8, 9], diagnose faults in the industrial procedure [10, 11], classify soil types [12, 13], and even predict crash injury severity [14] or analyze crime linkages [15]. Meanwhile, class imbalance learning (CIL) is also a challenging task. It is known that most existing supervised learning models are constructed on the theory of empirical risk minimization; thus, they always tend to favor the majority classes, but ignore the performance of the minority classes [16, 17].In the recent two decades, hundreds of CIL algorithms have been proposed to address the imbalanced classification problem [18, 19]. Specifically, these CIL methods could be roughly divided into three categories: data-level [20–27], algorithmic-level [28–35], and ensemble learning [36–42]. Data-level methods solve CIL problem by balancing the training data. Algorithmic-level methods directly modify classification models to adapt imbalanced data distribution. As for ensemble learning, it adopts either data-level or algorithmic-level approaches to combine with Bagging or Boosting paradigm for improving the accuracy and robustness of CIL.To explore the reason why imbalanced data hurt the traditional predictive models, several previous works have indicated some reasons from different aspects [34, 35, 43, 44]. Most viewpoints consider both skewed density distribution and the empirical risk minimization learning rule causing the degradation of modeling quality. In fact, for imbalanced data, the density distributions of different classes often vary sharply; however, their probability densities are generally invariable. This means if we could estimate the probability density distribution of each class accurately, it would become easier to solve CIL problem. Motivated by this viewpoint, we develop a novel solution called Probability Density Machine (PDM) for addressing CIL problem in this study.Firstly, to verify the validity of the idea, we analyze the reason why imbalanced data distribution hurts the performance of predictive model in theory, in the context of Gaussian Naive Bayes (GNB) predictive model [45, 46]. It is indicated that the negative impact of class imbalance only is associated with the prior probability (density distribution), but it is not related to the conditional probability (probability density distribution) of training data, which verifies our argument. Then, in the same theoretical framework, we explain the rationality of several traditional CIL techniques, including data-level and algorithm-level methods. Next, we indicate that the conditional probability estimation in GNB is generally inaccurate as the data might be far from the Gaussian distribution. Furthermore, we introduce the K-nearest-neighbors-probability-density-estimation- (KNN-PDE-) [47] alike algorithm to improve the accuracy of estimating probability density distribution and hereby propose the PDM algorithm. Finally, the effectiveness and feasibility of the proposed PDM model are verified by lots of experiments. In comparison with several traditional CIL solutions, the PDM shows promising results.The rest of this paper is organized as follows. Section2 reviews related work regarding CIL techniques briefly. Section 3 describes the CIL problem and analyzes the reason why class imbalance distribution hurts the performance of predictive model in the context of GNB and further explains the rationality of several traditional CIL solutions. In Section 4, we introduce an KNN-PDE-alike algorithm and then explain how to use it to develop PDM algorithm. Section 5 presents the experimental results and provides the corresponding discussion. Finally, Section 6 concludes the paper and outlines future work.


## 2. Related Work

In the recent two decades, several hundreds of different CIL methods have been proposed. These approaches can be roughly divided into three groups: data-level, algorithmic-level, and ensemble learning. Next, we wish to briefly review the work related to each of these three groups, respectively.Data-level, which is also called sampling, addresses CIL problem by rebalancing data distribution. It either increases the number of minority instances (oversampling) [20–23], or decreases the number of majority instances (undersampling) [24, 25], or uses both strategies simultaneously (hybrid sampling) [26, 27]. Random undersampling (RUS) [20] and random oversampling (ROS) [20] are the simplest sampling methods, where the former randomly removes majority instances, while the latter randomly copies minority samples. These two methods both have inherent drawbacks; i.e., RUS loses much information which is helpful for modeling, and ROS tends to make the classification models overfitting. The Synthetic Minority Oversampling Technique (SMOTE) [21] is an effective method to solve the problems brought by RUS and ROS. It generates synthetic minority instances between two adjacent real minority examples. However, SMOTE is inclined to propagate noises, which will also degrade the quality of training data. In recent years, some improved SMOTE algorithms have been proposed, including MWMOTE [22] that combines clustering technique and SMOTE to make new instances generate around those hard-to-learn samples and avoid emerging on wrong positions; MCT [23] which alters the class distribution of training data by cloning each minority class instance according to the similarity between it and the mode of the minority class; SMOTE-RSB [26] that takes advantage of rough set theory as a cleaning tool to search and remove minority noisy samples generated by SMOTE; and SMOTE-IPF [27] which adopts ensemble-based filters technique to prevent noise propagation. To avoid the information loss caused by RUS, Yu et al., [25] also integrate ant colony optimization into the procedure of undersampling to adaptively search those most important minority examples. All in all, the data-level technique has two major merits: (1) it is easier to be implemented as only data are manipulated; (2) it is irrelevant with classification models.Unlike data-level methods, the algorithmic-level approaches focus on modifying the classification model itself to make it adapt class imbalance environment. Cost-sensitive learning and threshold moving strategy are the most popular algorithmic-level CIL methods. Cost-sensitive learning adapts the imbalanced data distribution by assigning different misclassification penalties for the instances belonging to different classes. The allocation of misclassification penalties might be either empirical [28, 30] or personalized [29, 31–33]. In addition, many supervised learning models can be made to be sensitive to cost, including neural networks [28], support vector machine [29, 31–33], and Bayesian network [30]. Threshold moving adopts a postprocessing strategy to force the classification hyperplane trained by any traditional supervised learning model to move toward the area of majority instances [34, 35]. The moving distance can be determined by either empiricism or optimization technique.Ensemble learning is not an independent strategy to address CIL problem, but only a solution to promote the performance of other CIL methods. That is to say, ensemble learning must combine with one of the data-level or algorithmic-level methods to solve CIL problem. For examples, RUSBoost integrates RUS into boosting ensemble learning paradigm [36]; SMOTEBagging combines SMOTE with bagging ensemble learning paradigm [37]; AdaCost [38] and AdaC series algorithms [39] organize cost-sensitive learning and boosting; and EnSVM-OTHR [34] puts threshold moving strategy into bagging. Some recent studies also focus on class imbalance in high-dimension environment [40] and focus on how to improve the diversity of base models in CIL ensemble [41, 42]. Although ensemble learning always has a high time-complexity, it has presented potential to improve the quality of CIL models in various real-world applications.


## 3. Problem Description

### 3.1. Gaussian Naive Bayes (GNB) Predictive Model

As a variant of the Naive Bayes (NB) model, GNB has been widely used to solve various real-world supervised learning issues [45, 46]. Although both NB and GNB are based on Bayes theorem, there exists an essential difference between them; i.e., NB can be only used to modeling the data with discrete features, while GNB is extended to deal with the data in continuous feature space. In order to model data with continuous features, GNB needs to destroy the feature-independent hypothesis adopted by NB. Actually, GNB assumes in data the instances belonging to each class satisfy an independent Gaussian distribution whose mean and variance can be directly obtained by calculating feature space. Then for any one given instance xi, it is easy to calculate its conditional probability P (xi|y) in a class y, and meanwhile it is not difficult to acquire the prior probability P (y) by directly counting the ratio of instances belonging to the class y in training set. According to the Bayes theorem, its posterior probability P (y|xi) can be calculated by(1)Py|xi=Pxi|yPyPxi|yPy+Pxi|∼yP∼y,where P (∼y) and P (xi|∼y) represent the prior probability of the ∼y class and the conditional probability of the instance xi in the class ∼y, respectively. Then, GNB decides the class label of xi by comparing P (y|xi) and P (∼y|xi) based on the following rule:(2)fxi=y,ifPxi|y>Pxi|∼y,∼y,else.


### 3.2. Why Class Imbalance Hurts GNB?

Next, in the context of GNB, we wish to analyze the reason why imbalanced data distribution will hurt the performance of traditional predictive models. Specifically, suppose we face a binary-class imbalanced classification task, and the training set can be represented asΦ=xi,yi|xi∈ℜn,yi∈Y1,Y2,1≤i≤s, where Y1 and Y2 denote the class labels of the majority and minority instances, respectively. According to the class label, Ф can be further split into two subsets Φ1=xi,yi|xi∈ℜn,yi=Y1,1≤i≤s1andΦ2=xi,yixi∈ℜn|,yi=Y2,1≤i≤s2, where s=s1+s2 and s1>s2. Furthermore, to simplify the analysis, we restrict the dimension of the feature space in Ф as 1, no matter if Y1 or Y2 satisfies a Gaussian distribution. Then, we can directly acquire the prior probability and the conditional probability of each class. According to the Bayesian formula, we can respectively calculate the posterior probability belonging to each class as follows:(3)PY1|X=PX|Y1PY1PX|Y1PY1+PX|Y2PY2,PY2|X=PX|Y2PY2PX|Y1PY1+PX|Y2PY2.Based on the assumption above, Figure1 shows why imbalanced data distribution can hurt the performance of predictive models.Figure 1
An example explaining why imbalanced data distribution hurts the performance of prediction models.As shown in Figure1, the classification boundary has been obviously pushed toward the minority class, owing to the fact that PY1 is larger than PY2. Considering the context of GNB, the classification boundary associates with the condition PY1|X=PY2|Xwhich can be equivalently expressed asPX|Y1PY1=PX|Y2PY2; hence ifPY1>PY2, then it means only whenPX|Y1<PX|Y2, we can select the corresponding X as the classification boundary. Therefore, we can say that the negative impact of class imbalance for traditional supervised learning models only associates with the difference of prior probability (density distribution) belonging to different classes, but is irrelevant to the conditional probability (probability density distribution) of each class in training data. In other words, class imbalance data possess probability density invariance. Ignoring the impact of prior probability, it is not difficult to deduce(4)PY1|XPY2|X∝X|Y1PX|Y2.Any CIL solution tries its best to eliminate or at least alleviate the influence of prior probability, further making the model totally satisfy or approximately conform to the condition in (4).


### 3.3. The Explanation of Rationality of Several Traditional CIL Techniques

According to the theoretical analysis above, it is not difficult to explain the rationality of some traditional CIL techniques.First, let us consider the data-level strategy. It solves the skewed density distribution problem by either increasingPY1, or decreasing PY2, or simultaneously increasing PY1and decreasing PY2, further making PY1=PY2. Obviously, this strategy satisfies the condition in (4).Next, cost-sensitive learning focuses on adjusting prior probability distribution by designating different costs for different classes. That means (3) can be transformed to(5)PY1|X=PX|Y1PY1PX×C1,PY2|X=PX|Y2PY2PX×C2,where C1 and C2 denote the cost of the majority class and minority class, respectively. Generally, the cost assignment relates with the class imbalance ratio (IR), i.e.,(6)C1C2=PY2PY1.Then it meansC1PY1=C2Y2, which also satisfies the condition in (4).Finally, we wish to investigate the rationality of threshold moving technique. It often adds a compensation thresholdλ for the decision value of minority class, i.e.,(7)PY2|X=PX|Y2PY2PX+λ,where λ is usually a positive value. Specifically, when λ=PX|Y2PY1−PY2/PX, it exactly satisfies the condition in (4).Therefore, the rationality of various CIL techniques can be explained well within the theoretical framework of GNB, and they all can be seen as different strategies to balance the prior probabilities, further making (4) be workable.


## 3.1. Gaussian Naive Bayes (GNB) Predictive Model

As a variant of the Naive Bayes (NB) model, GNB has been widely used to solve various real-world supervised learning issues [45, 46]. Although both NB and GNB are based on Bayes theorem, there exists an essential difference between them; i.e., NB can be only used to modeling the data with discrete features, while GNB is extended to deal with the data in continuous feature space. In order to model data with continuous features, GNB needs to destroy the feature-independent hypothesis adopted by NB. Actually, GNB assumes in data the instances belonging to each class satisfy an independent Gaussian distribution whose mean and variance can be directly obtained by calculating feature space. Then for any one given instance xi, it is easy to calculate its conditional probability P (xi|y) in a class y, and meanwhile it is not difficult to acquire the prior probability P (y) by directly counting the ratio of instances belonging to the class y in training set. According to the Bayes theorem, its posterior probability P (y|xi) can be calculated by(1)Py|xi=Pxi|yPyPxi|yPy+Pxi|∼yP∼y,where P (∼y) and P (xi|∼y) represent the prior probability of the ∼y class and the conditional probability of the instance xi in the class ∼y, respectively. Then, GNB decides the class label of xi by comparing P (y|xi) and P (∼y|xi) based on the following rule:(2)fxi=y,ifPxi|y>Pxi|∼y,∼y,else.


## 3.2. Why Class Imbalance Hurts GNB?

Next, in the context of GNB, we wish to analyze the reason why imbalanced data distribution will hurt the performance of traditional predictive models. Specifically, suppose we face a binary-class imbalanced classification task, and the training set can be represented asΦ=xi,yi|xi∈ℜn,yi∈Y1,Y2,1≤i≤s, where Y1 and Y2 denote the class labels of the majority and minority instances, respectively. According to the class label, Ф can be further split into two subsets Φ1=xi,yi|xi∈ℜn,yi=Y1,1≤i≤s1andΦ2=xi,yixi∈ℜn|,yi=Y2,1≤i≤s2, where s=s1+s2 and s1>s2. Furthermore, to simplify the analysis, we restrict the dimension of the feature space in Ф as 1, no matter if Y1 or Y2 satisfies a Gaussian distribution. Then, we can directly acquire the prior probability and the conditional probability of each class. According to the Bayesian formula, we can respectively calculate the posterior probability belonging to each class as follows:(3)PY1|X=PX|Y1PY1PX|Y1PY1+PX|Y2PY2,PY2|X=PX|Y2PY2PX|Y1PY1+PX|Y2PY2.Based on the assumption above, Figure1 shows why imbalanced data distribution can hurt the performance of predictive models.Figure 1
An example explaining why imbalanced data distribution hurts the performance of prediction models.As shown in Figure1, the classification boundary has been obviously pushed toward the minority class, owing to the fact that PY1 is larger than PY2. Considering the context of GNB, the classification boundary associates with the condition PY1|X=PY2|Xwhich can be equivalently expressed asPX|Y1PY1=PX|Y2PY2; hence ifPY1>PY2, then it means only whenPX|Y1<PX|Y2, we can select the corresponding X as the classification boundary. Therefore, we can say that the negative impact of class imbalance for traditional supervised learning models only associates with the difference of prior probability (density distribution) belonging to different classes, but is irrelevant to the conditional probability (probability density distribution) of each class in training data. In other words, class imbalance data possess probability density invariance. Ignoring the impact of prior probability, it is not difficult to deduce(4)PY1|XPY2|X∝X|Y1PX|Y2.Any CIL solution tries its best to eliminate or at least alleviate the influence of prior probability, further making the model totally satisfy or approximately conform to the condition in (4).


## 3.3. The Explanation of Rationality of Several Traditional CIL Techniques

According to the theoretical analysis above, it is not difficult to explain the rationality of some traditional CIL techniques.First, let us consider the data-level strategy. It solves the skewed density distribution problem by either increasingPY1, or decreasing PY2, or simultaneously increasing PY1and decreasing PY2, further making PY1=PY2. Obviously, this strategy satisfies the condition in (4).Next, cost-sensitive learning focuses on adjusting prior probability distribution by designating different costs for different classes. That means (3) can be transformed to(5)PY1|X=PX|Y1PY1PX×C1,PY2|X=PX|Y2PY2PX×C2,where C1 and C2 denote the cost of the majority class and minority class, respectively. Generally, the cost assignment relates with the class imbalance ratio (IR), i.e.,(6)C1C2=PY2PY1.Then it meansC1PY1=C2Y2, which also satisfies the condition in (4).Finally, we wish to investigate the rationality of threshold moving technique. It often adds a compensation thresholdλ for the decision value of minority class, i.e.,(7)PY2|X=PX|Y2PY2PX+λ,where λ is usually a positive value. Specifically, when λ=PX|Y2PY1−PY2/PX, it exactly satisfies the condition in (4).Therefore, the rationality of various CIL techniques can be explained well within the theoretical framework of GNB, and they all can be seen as different strategies to balance the prior probabilities, further making (4) be workable.


## 4. Methods

### 4.1. KNN-PDE-Alike Conditional Probability Density Estimation Strategy

Motivated by (4), we observe a new potential CIL solution, i.e., neglecting prior probability and directly estimating the conditional probability belonging to each class to make decision. The solution avoids the tedious procedure of balancing prior probabilities and solves CIL problem in nature. The problem seems to get easier; however, it is still difficult to provide an accurate estimation for conditional probability. At least for GNB, it cannot precisely measure the conditional probability, as in many real-world applications, the data do not satisfy the Gaussian distribution. Figure 2 presents two different groups of data with the same mean and variance, but different distributions. It is clear that the GNB is able to provide an accurate estimation for the first group of data, while on the second group of data, the estimation will be extremely biased.Figure 2
Two distributions with the same mean and variance: (a) a Gaussian distribution and (b) a manifold distribution.
(a)(b)In order to provide accurate and robust probability density estimation, we present a novel strategy named KNN-PDE-alike algorithm. As its name indicates, KNN-PDE-alike algorithm is quite similar to KNN-PDE algorithm [47], but it has better adaptability for various complex data distributions.In a group of data, KNN-PDE-alike algorithm firstly searches the Kth nearest neighbor for each instancexi and records the Euclidean distance between xi and its Kth nearest neighbor as diK. Obviously, a smaller diK denotes a higher probability density corresponding to xi, and vice versa. It is a counterintuitive value principle; hence, a transformation rule should be designed. In this study, we adopt a simple transformation rule that takes the reciprocal of distance to express the probability density. That is to say, for a sample xi, its probability density could be represented asoi=1/diK. Now, the probability density can be still represented as a function of the distance variance, which is inconsistent with the definition of probability density. Therefore, the rough probability density oi should be further refined by the following transformation:(8)Pxi=oi∑,where P (xi) denotes the refined probability density of xi and ∑ can be calculated by(9)∑=∑i=1soi.The transformation can be seen as a normalization procedure of generating probability density. In fact,P (xi) is still not real probability density; however, it reflects the real proportional relation among probability density of different examples. Therefore, we call this kind of probability density the relative probability density.According to the procedure description above, we provide the pseudocode of KNN-PDE-alike algorithm in Algorithm1.Algorithm 1: KNN-PDE-alike probability density estimation algorithm.
(i)
Input: A data set Ψ = {xi|xi& ℝn; n, 1≤i ≤ s}, the parameter KOutput: A 1 × s vector ɭ recording the relative probability density of all instancesProcedure:(1)
Fori = 1 : s(2)
Forj = 1 : s(3)
If (i ≠ j)(4)
Calculating the Euclidean distance betweenxi and xj, and recording it as dij;(5)
End if(6)
End for(7)
Sorting all distances for the instancexi in ascending order, then finding the Kth one and recording it as diK;(8)
TransformingdiK to be oi by the reciprocal rule;(9)
End for(10)
Calculating the sum of alloi, ∑ by (9)(11)
Fori = 1 : s(12)
Calculating the relative probability densityP (xi) by (8);(13)
RecordingP (xi) into the ith position in the vector ɭ;(14)
End for(15)
Output the vectorɭ.


### 4.2. Probability Density Machine (PDM) Algorithm

It is clear that we can accurately estimate the relative probability density for each sample by virtue of KNN-PDE-alike strategy. Also, the relative probability density can be regarded as a scaling transformation of the corresponding real conditional probability density. Therefore, according to (4), we can directly make decision for the class label of a sample by comparing its relative probability densities in different classes. We call this method as Probability Density Machine (PDM).However, we note that, in class imbalance data, different classes always have different number of samples, which means the relative probability densities in different classes calculated by (8) could not be compared directly, as they are scaled in different scales. To make them comparable, we should conduct an extra normalization step. For instance, xi, its normalization relative probability density in a majority class j can be calculated by(10)P′xi=Pxi×sjsmin,where P (xi) and P′ (xi) respectively denote the original and normalized relative probability density of the instance xi in jth class, while sj and smin respectively represent the number of instances in the jth class and the class which has the least instances.In addition, we should focus on another important parameter which might influence the accuracy of relative probability density estimation, i.e., the neighborhood parameter K. It is obviously inappropriate to designate a common K for all classes; hence, we design an adaptive assignment rule that is automatically associated with the number of instances included in a specific class. Furthermore, we also observe that it is not suitable for designating a too large or too small value for the parameter K, as a too large K tends to destroy the difference of different density regions, while a too small K would be sensitive to noises. Hence, in this study, we empirically designateK=s as the default setting. The influence of the parameter K on the quality of PDM algorithm will be further discussed in Section 5.According to the procedure description above, we provide the pseudocode of Probability Density Machine (PDM) algorithm in Algorithm2.Algorithm 2: Probability Density Machine (PDM) algorithm.
Input: An imbalanced training set Ψ = {(xi, yi) | xi∈&ℝn;n, 1≤i ≤ s, yi∈{Y1, Y2 ,..., Ym}}, a test instance x′Output: An predictive class label y’ for x′Training Procedure:(1)
Fori = 1 : m(2)
Forj = 1 : s(3)
If (yj ∈ Yi)(4)
Puttingxj into Φi;(5)
End if(6)
End for(7)
Recording the number of instances in Φi as si, and calculating the corresponding Ki;(8)
Calling KNN-PDE-alike algorithm to acquire and record ∑i;(9)
End for(10)
Ranking allsi to get smin;(11)
Calculating each parameter Ki based on si.Testing Procedure:(1)
Fori = 1 : m(2)
Forj = 1 : sj(3)
Calculating the Euclidean distance betweenx′ and xj, and recording it as dij;(4)
End for(5)
Sorting all distances in ascending order, then finding the Kith and recording it as dKi;(6)
TransformingdKi to be oi’ by the reciprocal rule;(7)
Calling ∑i and dKi to calculate the relative probability density Pi (x′) for x′ by (8);(8)
If (si > smin)(9)
Callingsi and smin to adjust the relative probability density Pi (x′) by (10);(10)
End if(11)
End for(12)
Rankingm relative probability densities in descending order;(13)
Output the class labely’∈{Y1, Y2 ,..., Ym} which ranks first as the prediction for the test instance x′.From the pseudocode of PDM algorithm, we observe that it is very similar with those lazy learning algorithm, e.g., K-nearest neighbors classifier, as it needs to conduct lots of operations in testing phase. Actually, there exists a significant difference between the PDM and those lazy learning algorithms; i.e., lazy learning does not need training, but the PDM needs to conduct a complex training procedure for acquiring the normalization factor ∑, the number of instancess, and the parameter K in each class, respectively. Therefore, we call PDM a semilazy learning algorithm.Furthermore, to verify the effectiveness of PDM algorithm, we also compare it with GNB algorithm on two imbalanced artificial data sets, where A1 contains 1000 majority instances satisfying the Gaussian distribution of mean = 0.5 and variance = 0.1 and 100 minority instances satisfying the Gaussian distribution of mean = 0.7 and variance = 0.1, while A2 contains 5000 majority instances and 100 minority instances which satisfy the same distribution as A1. That is to say, both data sets have the same distribution, but different class imbalance ratios. Figure3 presents the instance distribution of these two data sets, and the decision regions produced by GNB and PDM, respectively.Figure 3
Instance distributions and decision regions produced by GNB and PDM on two imbalanced artificial data sets, respectively. (a) Instance distribution of A1. (b) Instance distribution of A2. (c) Decision regions produced by GNB on A1. (d) Decision regions produced by GNB on A2. (e) Decision regions produced by PDM on A1. (f) Decision regions produced by PDM on A2.
(a)(b)(c)In Figure3, we observe that the GNB is very sensitive to the variance of class imbalance ratio (IR), and with the increase of IR, the decision region of minority class would be significantly shrunken. By contrast, the PDM seems to be robust as its decision boundary is approximately invariable at the background of varying IR. This fact verifies our deduction; i.e., the impact of imbalanced data distribution is only related to prior probability, but not the conditional probability, again.


### 4.3. Time-Complexity Analysis

Finally, we focus on the time complexity of the proposed PDM algorithm. As a semilazy learning algorithm, the conduction of the PDM algorithm can be divided into two subprocedures.Suppose the data set includess instances which can be divided into m classes, and each instance holds n attributes; it mainly costs O (s) time to divide the data subsets belonging to different classes and to determine the parameter K in each class, O (m2logm) time to find smin, O (s2n) time to calculate the distance among all instances, O (s2logs) time to sort the distances, and O (s) time to conduct reciprocal operation and to calculate the normalization factor ∑ in each class, in training subprocedure. Considering real-world applications, the number of training instances is generally much larger than the number of classes, thereby we can say that the number of training instances s mainly dominates the time complexity in training phase. On low-dimensional data, i.e., logs >> n, its time complexity is O (s2logs), while on high-dimensional and small sample data, i.e., logs << n, the time complexity becomes O (s2n).During testing subprocedure, for a testing instance, it will consumeO (sn) time to calculate distances, O (slogs) time to sort distances, O (m) time to conduct reciprocal operation and to calculate the relative probability density, and O (m2logm) time to provide prediction. In comparison with training subprocedure, the time complexity of testing subprocedure could be negligible.Based on the analysis above, we have to admit that the proposed PDM algorithm needs to sacrifice much more running time than that in GNB. PDM may be accurate, effective, and robust, but not efficient.


## 4.1. KNN-PDE-Alike Conditional Probability Density Estimation Strategy

Motivated by (4), we observe a new potential CIL solution, i.e., neglecting prior probability and directly estimating the conditional probability belonging to each class to make decision. The solution avoids the tedious procedure of balancing prior probabilities and solves CIL problem in nature. The problem seems to get easier; however, it is still difficult to provide an accurate estimation for conditional probability. At least for GNB, it cannot precisely measure the conditional probability, as in many real-world applications, the data do not satisfy the Gaussian distribution. Figure 2 presents two different groups of data with the same mean and variance, but different distributions. It is clear that the GNB is able to provide an accurate estimation for the first group of data, while on the second group of data, the estimation will be extremely biased.Figure 2
Two distributions with the same mean and variance: (a) a Gaussian distribution and (b) a manifold distribution.
(a)(b)In order to provide accurate and robust probability density estimation, we present a novel strategy named KNN-PDE-alike algorithm. As its name indicates, KNN-PDE-alike algorithm is quite similar to KNN-PDE algorithm [47], but it has better adaptability for various complex data distributions.In a group of data, KNN-PDE-alike algorithm firstly searches the Kth nearest neighbor for each instancexi and records the Euclidean distance between xi and its Kth nearest neighbor as diK. Obviously, a smaller diK denotes a higher probability density corresponding to xi, and vice versa. It is a counterintuitive value principle; hence, a transformation rule should be designed. In this study, we adopt a simple transformation rule that takes the reciprocal of distance to express the probability density. That is to say, for a sample xi, its probability density could be represented asoi=1/diK. Now, the probability density can be still represented as a function of the distance variance, which is inconsistent with the definition of probability density. Therefore, the rough probability density oi should be further refined by the following transformation:(8)Pxi=oi∑,where P (xi) denotes the refined probability density of xi and ∑ can be calculated by(9)∑=∑i=1soi.The transformation can be seen as a normalization procedure of generating probability density. In fact,P (xi) is still not real probability density; however, it reflects the real proportional relation among probability density of different examples. Therefore, we call this kind of probability density the relative probability density.According to the procedure description above, we provide the pseudocode of KNN-PDE-alike algorithm in Algorithm1.Algorithm 1: KNN-PDE-alike probability density estimation algorithm.
(i)
Input: A data set Ψ = {xi|xi& ℝn; n, 1≤i ≤ s}, the parameter KOutput: A 1 × s vector ɭ recording the relative probability density of all instancesProcedure:(1)
Fori = 1 : s(2)
Forj = 1 : s(3)
If (i ≠ j)(4)
Calculating the Euclidean distance betweenxi and xj, and recording it as dij;(5)
End if(6)
End for(7)
Sorting all distances for the instancexi in ascending order, then finding the Kth one and recording it as diK;(8)
TransformingdiK to be oi by the reciprocal rule;(9)
End for(10)
Calculating the sum of alloi, ∑ by (9)(11)
Fori = 1 : s(12)
Calculating the relative probability densityP (xi) by (8);(13)
RecordingP (xi) into the ith position in the vector ɭ;(14)
End for(15)
Output the vectorɭ.


## 4.2. Probability Density Machine (PDM) Algorithm

It is clear that we can accurately estimate the relative probability density for each sample by virtue of KNN-PDE-alike strategy. Also, the relative probability density can be regarded as a scaling transformation of the corresponding real conditional probability density. Therefore, according to (4), we can directly make decision for the class label of a sample by comparing its relative probability densities in different classes. We call this method as Probability Density Machine (PDM).However, we note that, in class imbalance data, different classes always have different number of samples, which means the relative probability densities in different classes calculated by (8) could not be compared directly, as they are scaled in different scales. To make them comparable, we should conduct an extra normalization step. For instance, xi, its normalization relative probability density in a majority class j can be calculated by(10)P′xi=Pxi×sjsmin,where P (xi) and P′ (xi) respectively denote the original and normalized relative probability density of the instance xi in jth class, while sj and smin respectively represent the number of instances in the jth class and the class which has the least instances.In addition, we should focus on another important parameter which might influence the accuracy of relative probability density estimation, i.e., the neighborhood parameter K. It is obviously inappropriate to designate a common K for all classes; hence, we design an adaptive assignment rule that is automatically associated with the number of instances included in a specific class. Furthermore, we also observe that it is not suitable for designating a too large or too small value for the parameter K, as a too large K tends to destroy the difference of different density regions, while a too small K would be sensitive to noises. Hence, in this study, we empirically designateK=s as the default setting. The influence of the parameter K on the quality of PDM algorithm will be further discussed in Section 5.According to the procedure description above, we provide the pseudocode of Probability Density Machine (PDM) algorithm in Algorithm2.Algorithm 2: Probability Density Machine (PDM) algorithm.
Input: An imbalanced training set Ψ = {(xi, yi) | xi∈&ℝn;n, 1≤i ≤ s, yi∈{Y1, Y2 ,..., Ym}}, a test instance x′Output: An predictive class label y’ for x′Training Procedure:(1)
Fori = 1 : m(2)
Forj = 1 : s(3)
If (yj ∈ Yi)(4)
Puttingxj into Φi;(5)
End if(6)
End for(7)
Recording the number of instances in Φi as si, and calculating the corresponding Ki;(8)
Calling KNN-PDE-alike algorithm to acquire and record ∑i;(9)
End for(10)
Ranking allsi to get smin;(11)
Calculating each parameter Ki based on si.Testing Procedure:(1)
Fori = 1 : m(2)
Forj = 1 : sj(3)
Calculating the Euclidean distance betweenx′ and xj, and recording it as dij;(4)
End for(5)
Sorting all distances in ascending order, then finding the Kith and recording it as dKi;(6)
TransformingdKi to be oi’ by the reciprocal rule;(7)
Calling ∑i and dKi to calculate the relative probability density Pi (x′) for x′ by (8);(8)
If (si > smin)(9)
Callingsi and smin to adjust the relative probability density Pi (x′) by (10);(10)
End if(11)
End for(12)
Rankingm relative probability densities in descending order;(13)
Output the class labely’∈{Y1, Y2 ,..., Ym} which ranks first as the prediction for the test instance x′.From the pseudocode of PDM algorithm, we observe that it is very similar with those lazy learning algorithm, e.g., K-nearest neighbors classifier, as it needs to conduct lots of operations in testing phase. Actually, there exists a significant difference between the PDM and those lazy learning algorithms; i.e., lazy learning does not need training, but the PDM needs to conduct a complex training procedure for acquiring the normalization factor ∑, the number of instancess, and the parameter K in each class, respectively. Therefore, we call PDM a semilazy learning algorithm.Furthermore, to verify the effectiveness of PDM algorithm, we also compare it with GNB algorithm on two imbalanced artificial data sets, where A1 contains 1000 majority instances satisfying the Gaussian distribution of mean = 0.5 and variance = 0.1 and 100 minority instances satisfying the Gaussian distribution of mean = 0.7 and variance = 0.1, while A2 contains 5000 majority instances and 100 minority instances which satisfy the same distribution as A1. That is to say, both data sets have the same distribution, but different class imbalance ratios. Figure3 presents the instance distribution of these two data sets, and the decision regions produced by GNB and PDM, respectively.Figure 3
Instance distributions and decision regions produced by GNB and PDM on two imbalanced artificial data sets, respectively. (a) Instance distribution of A1. (b) Instance distribution of A2. (c) Decision regions produced by GNB on A1. (d) Decision regions produced by GNB on A2. (e) Decision regions produced by PDM on A1. (f) Decision regions produced by PDM on A2.
(a)(b)(c)In Figure3, we observe that the GNB is very sensitive to the variance of class imbalance ratio (IR), and with the increase of IR, the decision region of minority class would be significantly shrunken. By contrast, the PDM seems to be robust as its decision boundary is approximately invariable at the background of varying IR. This fact verifies our deduction; i.e., the impact of imbalanced data distribution is only related to prior probability, but not the conditional probability, again.


## 4.3. Time-Complexity Analysis

Finally, we focus on the time complexity of the proposed PDM algorithm. As a semilazy learning algorithm, the conduction of the PDM algorithm can be divided into two subprocedures.Suppose the data set includess instances which can be divided into m classes, and each instance holds n attributes; it mainly costs O (s) time to divide the data subsets belonging to different classes and to determine the parameter K in each class, O (m2logm) time to find smin, O (s2n) time to calculate the distance among all instances, O (s2logs) time to sort the distances, and O (s) time to conduct reciprocal operation and to calculate the normalization factor ∑ in each class, in training subprocedure. Considering real-world applications, the number of training instances is generally much larger than the number of classes, thereby we can say that the number of training instances s mainly dominates the time complexity in training phase. On low-dimensional data, i.e., logs >> n, its time complexity is O (s2logs), while on high-dimensional and small sample data, i.e., logs << n, the time complexity becomes O (s2n).During testing subprocedure, for a testing instance, it will consumeO (sn) time to calculate distances, O (slogs) time to sort distances, O (m) time to conduct reciprocal operation and to calculate the relative probability density, and O (m2logm) time to provide prediction. In comparison with training subprocedure, the time complexity of testing subprocedure could be negligible.Based on the analysis above, we have to admit that the proposed PDM algorithm needs to sacrifice much more running time than that in GNB. PDM may be accurate, effective, and robust, but not efficient.


## 5. Experiments and Discussion

### 5.1. Data Set Description

We collected 30 binary-class and 10 multiclass imbalanced data sets to verify the effectiveness and feasibility of the proposed PDM algorithm. The collection includes 13 data sets acquired from UCI machine learning repository [48] and 27 data sets collected from Keel data repository [49]. These data sets have different number of instances, number of attributes, number of classes, and class imbalance ratios (IR). The detailed description about these data sets is provided in Table 1.Table 1
Data sets used in this paper.
Data setNo. of classesNo. of instancesMinority classMajority classIRSourceAbalone924177Class9Remainder classes5.06UCIAbalone1924177Class19Remainder classes129.53UCIBanknote21372Class1Class01.25UCICtg1522126Class1, 5Remainder classes28.53UCICtg2322126Class2, 3Remainder classes11.08UCIILPD2583Nonliver patientLiver patient2.49UCIMfeatmor022000Class0Remainder classes9.00UCIMfeatmor0122000Class0, 1Remainder classes4.00UCIPageblocks234525473Class2–5Class18.77UCISeeds2v132210Class2Class1, 32.00UCISegment122310Class1Class2–76.00UCISegment1222310Class1, 2Class3–72.50UCIWilt24839Class1Class217.54UCIEcoli0v12220Class1Class01.86KeelEcoli12336Class1Remainder classes3.36KeelTic-tac-toe2958NegativePositive1.89KeelGlass02214Class0Remainder classes2.06KeelGlass12214Class1Remainder classes1.82KeelHaberman2306PositiveNegative2.78KeelVowel02988Class0Remainder classes9.98KeelPoker8v621477Class8Class685.88KeelVehicle02846Class0Remainder classes3.25KeelVehicle22846Class2Remainder classes2.88KeelYeast121484Class1Remainder classes2.46KeelHeart2270NegativePositive1.25KeelAppendicitis2106PositiveNegative4.05KeelBands2365Class1Class01.70KeelBupa2345Class1Class01.38KeelSonar2208Class0Class11.14KeelWdbc2569Class1Class01.68KeelPage-blocks55472———KeelFlare61066———KeelMovement_libras15360———KeelWinequality-red41599———KeelWine3178———KeelVowel11990———KeelLetter2620000———KeelTexture115500———KeelSatimage66435———KeelNewthyroid3215———KeelNote: IR denotes the class imbalance ratio.


### 5.2. Experimental Settings

All experiments were run on a 2.60 GHz Intel (R) Core (TM) i7 6700HQ 8 cores CPU with 16 GB RAM using MATLAB 2013a running environment.To show the effectiveness and superiority of the proposed PDM algorithm, we compared it with the following algorithms:(1)
GNB: it adopts GNB classifier [45, 46] to directly train the data without considering the skewed data distribution.(2)
CS-GNB: it first trains GNB classifier [45, 46] on original data and then empirically assigns decision costs for the posterior probability in each class (see (5) and (6)).(3)
RUS-GNB: it firstly calls random undersampling (RUS) algorithm [20] to generate a balanced training set from original data and then trains GNB classifier [45, 46] on the new balanced data.(4)
ROS-GNB: it firstly calls random oversampling (ROS) algorithm [20] to generate a balanced training set from original data and then trains GNB classifier [45, 46] on the new balanced data.(5)
SMOTE-GNB: it firstly calls Synthetic Minority Oversampling Technique (SMOTE) algorithm [21] to generate a balanced training set from original data and then trains GNB classifier [45, 46] on the new balanced data. In SMOTE, it adopts a default parameter K = 5.As we know, when we evaluate the performance of a CIL classifier, the total classification accuracy is not an excellent performance evaluation metric any longer; hence, we adopted F-measure and G-mean as performance evaluation metrics, where F-measure tests the tradeoff between precision and recall, while G-mean tests the tradeoff among the accuracy of each class.To impartially compare the performance of various algorithms, we adopted 10 times’ randomly external 5-fold cross validation to calculate the average performance as final results.


### 5.3. Results and Discussion

Table2 and Table 3 present the F-measure and G-mean results of six algorithms on 40 imbalanced data sets.Table 2
F-measure of various algorithms on 40 imbalanced data sets.
Data setGNBCS-GNBRUS-GNBROS-GNBSMOTE-GNBPDMAbalone90.67860.55660.49550.55450.56140.6161Abalone190.92970.70170.66860.70070.71250.7060Banknote0.83200.84110.84260.84070.84220.9956Ctg150.72070.78840.67500.69720.76720.9577Ctg230.93860.92900.93790.93390.93570.9473ILPD0.55410.46490.53380.55810.56360.6511Mfeatmor00.99900.99850.99900.99900.99900.9990Mfeatmor010.88020.83270.80190.85080.85440.9854Pageblocks23450.89580.90840.91230.89660.90060.9269Seeds2v130.95520.95070.95500.95050.95520.9738Segment10.85350.84880.80420.83700.84590.9847Segment120.73550.77360.63950.70940.71750.9917Wilt0.90450.62570.42230.62640.67020.9390Ecoli0v10.93450.97240.91750.94630.94640.9796Ecoli10.73110.87470.60530.68570.75010.8999Tic-tac-toe0.68440.64750.64780.64470.65040.9958Glass00.65270.65900.64670.65840.66000.7382Glass10.61170.59160.56930.59990.59510.7366Haberman0.70210.69000.61190.70490.71640.5608Vowel00.94090.95650.88830.88990.89380.9878Poker8v60.98330.72160.33120.75050.81870.9926Vehicle00.65310.65490.65180.64700.65330.9183Vehicle20.80790.81550.73330.77720.78280.8883Yeast10.18930.56560.19430.17930.20610.7462Heart0.84920.84560.84550.84370.84550.7584Appendicitis0.82070.79750.77070.79810.81450.7690Bands0.23350.59190.23060.23090.25260.6787Bupa0.55060.49320.46750.50400.49830.6165Sonar0.68400.67760.66060.69250.67940.7883Wdbc0.92970.92600.94350.92710.93230.8845Page-blocks0.91610.85030.78710.86500.87700.8823Flare0.64590.69530.56740.64030.64550.4152Movement_libras0.60350.60660.59220.61290.61800.7302Winequality-red0.55740.53480.33170.48170.38540.4822Wine0.98070.98060.98340.97520.98340.9778Vowel0.68000.67040.68610.67530.68090.8604Letter0.64000.63450.63140.63920.63970.8801Texture0.77230.75650.77060.77220.77250.9660Satimage0.80580.80230.77800.80390.80310.8655Newthyroid0.95850.95840.94380.96080.96080.7676∗In each row, the best result has been highlighted in boldface.Table 3
G-mean of various algorithms on 40 imbalanced data sets.
Data setGNBCS-GNBRUS-GNBROS-GNBSMOTE-GNBPDMAbalone90.60240.59660.55300.59330.59820.6397Abalone190.24020.60580.62050.60510.61450.6432Banknote0.82830.83960.84120.83900.84080.9960Ctg150.75650.81810.71890.73720.78610.6456Ctg230.80080.85370.87970.83980.84740.9200ILPD0.60830.52390.59040.61150.61720.4377Mfeatmor00.99450.99270.99450.99450.99450.9945Mfeatmor010.86130.84780.83240.87010.86850.9713Pageblocks23450.66340.69950.61560.69990.72950.6681Seeds2v130.95790.95550.95550.95440.95810.9715Segment10.89290.88810.85280.87960.88690.9460Segment120.77660.74210.69110.75430.76050.9853Wilt0.71480.66630.52800.66550.69450.5542Ecoli0v10.90570.96130.87980.92290.92320.9785Ecoli10.77440.89090.66530.73840.79200.8804Tic-tac-toe0.58910.63520.63580.63000.63950.9937Glass00.68440.68920.68040.69420.69240.5874Glass10.63030.59800.58640.62060.61200.6243Haberman0.40900.36650.50630.47200.51260.5981Vowel00.92630.83450.90080.90380.89830.9471Poker8v60.00000.47110.23630.34180.44260.5300Vehicle00.68940.67610.70520.69490.70240.9166Vehicle20.71640.66790.73650.74720.76950.7762Yeast10.20590.62050.21290.18550.23250.7160Heart0.84310.83990.83820.83830.83880.7567Appendicitis0.76530.74990.74860.76030.77210.7419Bands0.14740.59440.13210.14270.20150.6872Bupa0.55480.48380.45250.49890.49100.5506Sonar0.68370.67590.65930.69030.67920.7862Wdbc0.92270.91700.93340.92030.92480.8994Page-blocks0.80670.73780.76640.81860.83590.7897Flare0.65630.72740.58460.64960.66040.5625Movement_libras0.73220.73120.72540.73920.74070.8236Winequality-red0.45530.09250.60740.65400.64170.6642Wine0.98690.98650.98860.98280.98880.9840Vowel0.80570.79860.80970.80310.80550.9161Letter0.78730.78310.78130.78670.78710.9334Texture0.86310.85260.86190.86300.86320.9809Satimage0.86800.86650.85250.86770.86770.9155Newthyroid0.93710.93500.93440.94280.94280.8821Note: in each row, the best result has been highlighted in boldface.From the results in Tables2 and Table 3, it is not difficult to draw some conclusions as below.(1)
We observed an interesting result; i.e., although GNB fails to consider class imbalance issue in data distribution, it performs no worse than CS-GNB, RUS-GNB, ROS-GNB, and SMOTE-GNB algorithms on most data sets. Specifically, GNB acquires the best F-measure and G-mean results on 7 and 5 data sets, respectively. We think this counterintuitive phenomenon is perhaps associated with two different reasons. The first and also the most important reason lies in that the instance distribution in lots of used data sets might be very similar with Gaussian distribution. In addition, on those data sets which GNB performs better, perhaps there exists a large margin among different classes, further causing a biased model that also could accurately classify most instances.(2)
Class imbalance ratio seems to be an important influence factor on the performance of GNB, which is specifically significant in terms of G-mean metric. In particular, on abalone19 and poker8v6 data sets which hold very high class imbalance ratios, GNB only acquires 0.2402 and 0.0000 G-mean values. The results prove our theoretical deduction again.(3)
Among those GNB variants, SMOTE-GNB shows obviously better performance than its three competitors. It is not difficult to analyze the reasons why RUS tends to lose some important information to describe the real data distribution and ROS decreases the accuracy of probability density estimation as only inserting some synthetic minority instances on those intrinsic positions, and although a cost-sensitive strategy avoids the impact of biased prior probability, it still could not provide a robust estimation for real conditional probability density. As a synthetic oversampling technique, SMOTE fills the space among intrinsic minority instances, further promoting the accuracy of conditional probability density estimation. This explains why SMOTE-GNB outperforms the other algorithms.(4)
It is clear that our proposed PDM model is superior to the other five algorithms. Specifically, PDM has acquired the best results on 29 and 26 data sets in terms of F-measure and G-mean, respectively. Actually, PDM promotes the modeling quality from two different aspects: one is totally balancing the prior probabilities and the other is providing approximately accurate conditional probability density estimation for any types of data distribution. The results also further indicate the effectiveness and feasibility of the proposed PDM algorithm in this study.


### 5.4. Significance Analysis in Statistics

To present a thorough understanding of the comparison of various algorithms, we also provide their statistical results. We employ Friedman ranking test and Holm post-hoc test [50, 51] to differentiate the performance of the comparative methods on 40 data sets. The statistical analysis results obtained at the confidence level of α = 0.05 are presented in Table 4 and Table 5.Table 4
Statistical analysis results of comparative algorithms in terms of F-measure at the confidence level ofα = 0.05.
AlgorithmAverage rankingpHolmHypothesisPDM2.05———GNB2.960.03650.0500RejectedCS-GNB3.850.00000.0167RejectedRUS-GNB4.950.00000.0100RejectedROS-GNB4.260.00000.0125RejectedSMOTE-GNB2.930.02910.0250Not rejectedTable 5
Statistical analysis results of comparative algorithms in terms of G-mean at the confidence level ofα = 0.05.
AlgorithmAverage rankingpHolmHypothesisPDM2.48———GNB3.480.01680.0250RejectedCS-GNB4.130.00010.0125RejectedRUS-GNB4.530.00000.0100RejectedROS-GNB3.740.00250.0167RejectedSMOTE-GNB2.660.65400.0500Not rejectedThe statistical results in Table4 and 5 show that the proposed PDM algorithm acquires the lowest average ranking values in both terms of F-measure and G-mean metrics, indicating that it is the best one among the comparative algorithms. For both metrics, the Holm post-hoc test rejects all comparative algorithms except SMOTE-GNB as their p values are smaller than the corresponding Holm values, which verifies that the PDM significantly outperforms these comparative algorithms. Of course, we cannot say there exists a significant difference between the PDM and the SMOTE-GNB, though the former has a lower average ranking than the latter. All in all, the proposed PDM algorithm presents more superior performance and lower average ranking than all other competitors and thereby we can safely recommend it as an effective solution to address CIL problem.


### 5.5. Discussion about the Impact of Parameter K

Next, we wish to discuss the sensibility of parameter K. As we know, K is also sole parameter in the PDM algorithm. In Section4, we design it as a function of the number of instances s. To make clear whether the modeling quality of PDM is sensitive to K or not, we vary the value of K in the range of s/4,s/2,s,2s,4s and then observe the variation of performance of PDM. The results on three different data sets are presented in Figure 4.Figure 4
The performance variation with the variation of the parameter (K), where, inX-axis, 1, 2, 3, 4, and 5 denote s/4,s/2,s,2s,4s, respectively.In Figure4, we observe that the classification performance of PDM is extremely sensitive to the parameter K, as with the variation of K, the classification performance changes drastically. Therefore, in practical applications, this parameter should be carefully selected and designated.From the results in Figure4, we also find that although for different performance metrics each data set has different best K values, all curves still show a common varying trend; i.e., with the increase of K, the performance firstly improves until a peak value, and then it will decline sharply. The observation is in accordance with our analysis in Section 4. That is to say, either too small or too large K value goes against the accurate estimation for conditional probability density. A too small K value would be sensitive to noises, while a too large K value would tend to destroy the difference of different density regions. According to the results presented in Figure 4, we suggest to designate K as a value lying between s/2 and 2s. In real-world applications, the best K value can be determined by an internal cross-validation, too.


## 5.1. Data Set Description

We collected 30 binary-class and 10 multiclass imbalanced data sets to verify the effectiveness and feasibility of the proposed PDM algorithm. The collection includes 13 data sets acquired from UCI machine learning repository [48] and 27 data sets collected from Keel data repository [49]. These data sets have different number of instances, number of attributes, number of classes, and class imbalance ratios (IR). The detailed description about these data sets is provided in Table 1.Table 1
Data sets used in this paper.
Data setNo. of classesNo. of instancesMinority classMajority classIRSourceAbalone924177Class9Remainder classes5.06UCIAbalone1924177Class19Remainder classes129.53UCIBanknote21372Class1Class01.25UCICtg1522126Class1, 5Remainder classes28.53UCICtg2322126Class2, 3Remainder classes11.08UCIILPD2583Nonliver patientLiver patient2.49UCIMfeatmor022000Class0Remainder classes9.00UCIMfeatmor0122000Class0, 1Remainder classes4.00UCIPageblocks234525473Class2–5Class18.77UCISeeds2v132210Class2Class1, 32.00UCISegment122310Class1Class2–76.00UCISegment1222310Class1, 2Class3–72.50UCIWilt24839Class1Class217.54UCIEcoli0v12220Class1Class01.86KeelEcoli12336Class1Remainder classes3.36KeelTic-tac-toe2958NegativePositive1.89KeelGlass02214Class0Remainder classes2.06KeelGlass12214Class1Remainder classes1.82KeelHaberman2306PositiveNegative2.78KeelVowel02988Class0Remainder classes9.98KeelPoker8v621477Class8Class685.88KeelVehicle02846Class0Remainder classes3.25KeelVehicle22846Class2Remainder classes2.88KeelYeast121484Class1Remainder classes2.46KeelHeart2270NegativePositive1.25KeelAppendicitis2106PositiveNegative4.05KeelBands2365Class1Class01.70KeelBupa2345Class1Class01.38KeelSonar2208Class0Class11.14KeelWdbc2569Class1Class01.68KeelPage-blocks55472———KeelFlare61066———KeelMovement_libras15360———KeelWinequality-red41599———KeelWine3178———KeelVowel11990———KeelLetter2620000———KeelTexture115500———KeelSatimage66435———KeelNewthyroid3215———KeelNote: IR denotes the class imbalance ratio.


## 5.2. Experimental Settings

All experiments were run on a 2.60 GHz Intel (R) Core (TM) i7 6700HQ 8 cores CPU with 16 GB RAM using MATLAB 2013a running environment.To show the effectiveness and superiority of the proposed PDM algorithm, we compared it with the following algorithms:(1)
GNB: it adopts GNB classifier [45, 46] to directly train the data without considering the skewed data distribution.(2)
CS-GNB: it first trains GNB classifier [45, 46] on original data and then empirically assigns decision costs for the posterior probability in each class (see (5) and (6)).(3)
RUS-GNB: it firstly calls random undersampling (RUS) algorithm [20] to generate a balanced training set from original data and then trains GNB classifier [45, 46] on the new balanced data.(4)
ROS-GNB: it firstly calls random oversampling (ROS) algorithm [20] to generate a balanced training set from original data and then trains GNB classifier [45, 46] on the new balanced data.(5)
SMOTE-GNB: it firstly calls Synthetic Minority Oversampling Technique (SMOTE) algorithm [21] to generate a balanced training set from original data and then trains GNB classifier [45, 46] on the new balanced data. In SMOTE, it adopts a default parameter K = 5.As we know, when we evaluate the performance of a CIL classifier, the total classification accuracy is not an excellent performance evaluation metric any longer; hence, we adopted F-measure and G-mean as performance evaluation metrics, where F-measure tests the tradeoff between precision and recall, while G-mean tests the tradeoff among the accuracy of each class.To impartially compare the performance of various algorithms, we adopted 10 times’ randomly external 5-fold cross validation to calculate the average performance as final results.


## 5.3. Results and Discussion

Table2 and Table 3 present the F-measure and G-mean results of six algorithms on 40 imbalanced data sets.Table 2
F-measure of various algorithms on 40 imbalanced data sets.
Data setGNBCS-GNBRUS-GNBROS-GNBSMOTE-GNBPDMAbalone90.67860.55660.49550.55450.56140.6161Abalone190.92970.70170.66860.70070.71250.7060Banknote0.83200.84110.84260.84070.84220.9956Ctg150.72070.78840.67500.69720.76720.9577Ctg230.93860.92900.93790.93390.93570.9473ILPD0.55410.46490.53380.55810.56360.6511Mfeatmor00.99900.99850.99900.99900.99900.9990Mfeatmor010.88020.83270.80190.85080.85440.9854Pageblocks23450.89580.90840.91230.89660.90060.9269Seeds2v130.95520.95070.95500.95050.95520.9738Segment10.85350.84880.80420.83700.84590.9847Segment120.73550.77360.63950.70940.71750.9917Wilt0.90450.62570.42230.62640.67020.9390Ecoli0v10.93450.97240.91750.94630.94640.9796Ecoli10.73110.87470.60530.68570.75010.8999Tic-tac-toe0.68440.64750.64780.64470.65040.9958Glass00.65270.65900.64670.65840.66000.7382Glass10.61170.59160.56930.59990.59510.7366Haberman0.70210.69000.61190.70490.71640.5608Vowel00.94090.95650.88830.88990.89380.9878Poker8v60.98330.72160.33120.75050.81870.9926Vehicle00.65310.65490.65180.64700.65330.9183Vehicle20.80790.81550.73330.77720.78280.8883Yeast10.18930.56560.19430.17930.20610.7462Heart0.84920.84560.84550.84370.84550.7584Appendicitis0.82070.79750.77070.79810.81450.7690Bands0.23350.59190.23060.23090.25260.6787Bupa0.55060.49320.46750.50400.49830.6165Sonar0.68400.67760.66060.69250.67940.7883Wdbc0.92970.92600.94350.92710.93230.8845Page-blocks0.91610.85030.78710.86500.87700.8823Flare0.64590.69530.56740.64030.64550.4152Movement_libras0.60350.60660.59220.61290.61800.7302Winequality-red0.55740.53480.33170.48170.38540.4822Wine0.98070.98060.98340.97520.98340.9778Vowel0.68000.67040.68610.67530.68090.8604Letter0.64000.63450.63140.63920.63970.8801Texture0.77230.75650.77060.77220.77250.9660Satimage0.80580.80230.77800.80390.80310.8655Newthyroid0.95850.95840.94380.96080.96080.7676∗In each row, the best result has been highlighted in boldface.Table 3
G-mean of various algorithms on 40 imbalanced data sets.
Data setGNBCS-GNBRUS-GNBROS-GNBSMOTE-GNBPDMAbalone90.60240.59660.55300.59330.59820.6397Abalone190.24020.60580.62050.60510.61450.6432Banknote0.82830.83960.84120.83900.84080.9960Ctg150.75650.81810.71890.73720.78610.6456Ctg230.80080.85370.87970.83980.84740.9200ILPD0.60830.52390.59040.61150.61720.4377Mfeatmor00.99450.99270.99450.99450.99450.9945Mfeatmor010.86130.84780.83240.87010.86850.9713Pageblocks23450.66340.69950.61560.69990.72950.6681Seeds2v130.95790.95550.95550.95440.95810.9715Segment10.89290.88810.85280.87960.88690.9460Segment120.77660.74210.69110.75430.76050.9853Wilt0.71480.66630.52800.66550.69450.5542Ecoli0v10.90570.96130.87980.92290.92320.9785Ecoli10.77440.89090.66530.73840.79200.8804Tic-tac-toe0.58910.63520.63580.63000.63950.9937Glass00.68440.68920.68040.69420.69240.5874Glass10.63030.59800.58640.62060.61200.6243Haberman0.40900.36650.50630.47200.51260.5981Vowel00.92630.83450.90080.90380.89830.9471Poker8v60.00000.47110.23630.34180.44260.5300Vehicle00.68940.67610.70520.69490.70240.9166Vehicle20.71640.66790.73650.74720.76950.7762Yeast10.20590.62050.21290.18550.23250.7160Heart0.84310.83990.83820.83830.83880.7567Appendicitis0.76530.74990.74860.76030.77210.7419Bands0.14740.59440.13210.14270.20150.6872Bupa0.55480.48380.45250.49890.49100.5506Sonar0.68370.67590.65930.69030.67920.7862Wdbc0.92270.91700.93340.92030.92480.8994Page-blocks0.80670.73780.76640.81860.83590.7897Flare0.65630.72740.58460.64960.66040.5625Movement_libras0.73220.73120.72540.73920.74070.8236Winequality-red0.45530.09250.60740.65400.64170.6642Wine0.98690.98650.98860.98280.98880.9840Vowel0.80570.79860.80970.80310.80550.9161Letter0.78730.78310.78130.78670.78710.9334Texture0.86310.85260.86190.86300.86320.9809Satimage0.86800.86650.85250.86770.86770.9155Newthyroid0.93710.93500.93440.94280.94280.8821Note: in each row, the best result has been highlighted in boldface.From the results in Tables2 and Table 3, it is not difficult to draw some conclusions as below.(1)
We observed an interesting result; i.e., although GNB fails to consider class imbalance issue in data distribution, it performs no worse than CS-GNB, RUS-GNB, ROS-GNB, and SMOTE-GNB algorithms on most data sets. Specifically, GNB acquires the best F-measure and G-mean results on 7 and 5 data sets, respectively. We think this counterintuitive phenomenon is perhaps associated with two different reasons. The first and also the most important reason lies in that the instance distribution in lots of used data sets might be very similar with Gaussian distribution. In addition, on those data sets which GNB performs better, perhaps there exists a large margin among different classes, further causing a biased model that also could accurately classify most instances.(2)
Class imbalance ratio seems to be an important influence factor on the performance of GNB, which is specifically significant in terms of G-mean metric. In particular, on abalone19 and poker8v6 data sets which hold very high class imbalance ratios, GNB only acquires 0.2402 and 0.0000 G-mean values. The results prove our theoretical deduction again.(3)
Among those GNB variants, SMOTE-GNB shows obviously better performance than its three competitors. It is not difficult to analyze the reasons why RUS tends to lose some important information to describe the real data distribution and ROS decreases the accuracy of probability density estimation as only inserting some synthetic minority instances on those intrinsic positions, and although a cost-sensitive strategy avoids the impact of biased prior probability, it still could not provide a robust estimation for real conditional probability density. As a synthetic oversampling technique, SMOTE fills the space among intrinsic minority instances, further promoting the accuracy of conditional probability density estimation. This explains why SMOTE-GNB outperforms the other algorithms.(4)
It is clear that our proposed PDM model is superior to the other five algorithms. Specifically, PDM has acquired the best results on 29 and 26 data sets in terms of F-measure and G-mean, respectively. Actually, PDM promotes the modeling quality from two different aspects: one is totally balancing the prior probabilities and the other is providing approximately accurate conditional probability density estimation for any types of data distribution. The results also further indicate the effectiveness and feasibility of the proposed PDM algorithm in this study.


## 5.4. Significance Analysis in Statistics

To present a thorough understanding of the comparison of various algorithms, we also provide their statistical results. We employ Friedman ranking test and Holm post-hoc test [50, 51] to differentiate the performance of the comparative methods on 40 data sets. The statistical analysis results obtained at the confidence level of α = 0.05 are presented in Table 4 and Table 5.Table 4
Statistical analysis results of comparative algorithms in terms of F-measure at the confidence level ofα = 0.05.
AlgorithmAverage rankingpHolmHypothesisPDM2.05———GNB2.960.03650.0500RejectedCS-GNB3.850.00000.0167RejectedRUS-GNB4.950.00000.0100RejectedROS-GNB4.260.00000.0125RejectedSMOTE-GNB2.930.02910.0250Not rejectedTable 5
Statistical analysis results of comparative algorithms in terms of G-mean at the confidence level ofα = 0.05.
AlgorithmAverage rankingpHolmHypothesisPDM2.48———GNB3.480.01680.0250RejectedCS-GNB4.130.00010.0125RejectedRUS-GNB4.530.00000.0100RejectedROS-GNB3.740.00250.0167RejectedSMOTE-GNB2.660.65400.0500Not rejectedThe statistical results in Table4 and 5 show that the proposed PDM algorithm acquires the lowest average ranking values in both terms of F-measure and G-mean metrics, indicating that it is the best one among the comparative algorithms. For both metrics, the Holm post-hoc test rejects all comparative algorithms except SMOTE-GNB as their p values are smaller than the corresponding Holm values, which verifies that the PDM significantly outperforms these comparative algorithms. Of course, we cannot say there exists a significant difference between the PDM and the SMOTE-GNB, though the former has a lower average ranking than the latter. All in all, the proposed PDM algorithm presents more superior performance and lower average ranking than all other competitors and thereby we can safely recommend it as an effective solution to address CIL problem.


## 5.5. Discussion about the Impact of Parameter K

Next, we wish to discuss the sensibility of parameter K. As we know, K is also sole parameter in the PDM algorithm. In Section4, we design it as a function of the number of instances s. To make clear whether the modeling quality of PDM is sensitive to K or not, we vary the value of K in the range of s/4,s/2,s,2s,4s and then observe the variation of performance of PDM. The results on three different data sets are presented in Figure 4.Figure 4
The performance variation with the variation of the parameter (K), where, inX-axis, 1, 2, 3, 4, and 5 denote s/4,s/2,s,2s,4s, respectively.In Figure4, we observe that the classification performance of PDM is extremely sensitive to the parameter K, as with the variation of K, the classification performance changes drastically. Therefore, in practical applications, this parameter should be carefully selected and designated.From the results in Figure4, we also find that although for different performance metrics each data set has different best K values, all curves still show a common varying trend; i.e., with the increase of K, the performance firstly improves until a peak value, and then it will decline sharply. The observation is in accordance with our analysis in Section 4. That is to say, either too small or too large K value goes against the accurate estimation for conditional probability density. A too small K value would be sensitive to noises, while a too large K value would tend to destroy the difference of different density regions. According to the results presented in Figure 4, we suggest to designate K as a value lying between s/2 and 2s. In real-world applications, the best K value can be determined by an internal cross-validation, too.


## 6. Concluding Remarks

In this study, from a theoretical perspective, we tried to analyze the reason why class imbalance distribution hurts the performance of predictive model in context of Gaussian Naive Bayes classifier. It is deduced that the hazard of imbalanced data distribution is only associated with prior probability, but not with conditional probability density. Accordingly, we analyzed the rationality of several popular class imbalance learning techniques and indicated the necessity of accurately estimating the conditional probability density in data distribution. Then, a robust probability density estimation algorithm named KNN-PDE-alike is proposed, and based on this algorithm, a novel class imbalance learning solution named PDM is further presented. Experimental results on 40 binary-class and multiclass imbalanced data sets have shown the effectiveness and superiority of the proposed PDM algorithm.The proposed PDM algorithm holds several merits as follows:(1)
It has a good theoretical basis(2)
It is insensitive to data distribution and is able to adapt various types of data distribution(3)
It can be directly used to classify not only binary-class imbalance data but also multiclass imbalance dataIn future work, the possibility of developing more robust and fast probability density estimation strategy will be investigated. The effectiveness and superiority of PDM will be further verified by applying it in more real-world class imbalance applications, too.



---

*Source: 7555587-2021-09-09.xml*