Improving performance of decision threshold moving-based strategies by integrating density-based clustering technique

1.   Introduction

In recent years, learning from imbalanced data distributions has gradually developed to be a hotspot issue in machine learning field due to this issue is emerging in more and more practical applications, including medical diagnosis ^[1], industrial fault diagnosis ^[2,3], network intrusion detection ^[4], financial fraud detection ^[5,6], text classification ^[7,8], bioinformatics ^[9], soil classification ^[10], air performance prediction ^[11], and criminal linkage detection ^[12].

In nature, class imbalance problem happens as the number of instances belonging to a specific class is overwhelming to that belonging to the other classes, further causing some traditional supervised learning algorithms exceedingly focus on the majority class, but depress the performance of minority classes. In recent two decades, a number of learning algorithms for addressing imbalanced classification problem have been proposed, and they could be roughly divided into four following categories: sampling ^[13,14,15], cost-sensitive learning ^[16,17,18], decision threshold moving (DTM) ^{[19,20,21,22]}, and ensemble learning ^{[23,24,25,26]}. Sampling can be regarded as a pre-processing technique for dealing with class imbalance learning problem as it balances the data distribution of different classes by either adding the instances belonging to the minority class or decreasing the instances belonging to the majority class. Cost-sensitive learning inserts the concept of cost or weight into traditional supervised learning algorithms, and it generally provides higher cost or weight for the instances belonging to the minority class to make the learning model focus more on such class. As the cost-sensitive learning technique is directly merged into traditional supervised learning algorithms, thus it can be seen as a in the processing technique for addressing imbalanced classification problem. As for DTM strategy, it first trains a biased model by a traditional classification algorithm, and then moves the trained classification hyperplane towards the majority class empirically or optimally. Therefore, the DTM strategy can be seen as a postprocessing class imbalance learning technique. Ensemble learning combines Bagging, Boosting or random space paradigm with one of single class imbalance learning strategies which are mentioned above to further improve the robustness of learning model. Specifically, among the existing class imbalance learning techniques, we can't say which one is always better than others as each one of them has its own pros and cons.

In this study, we focus on DTM class imbalance learning strategy because that its postprocessing mechanism makes it not only avoid to destroying the potential data distribution, but also be independent of classification algorithm. Its disadvantage lies in that it is not easy to find the appropriate threshold to maximize the classification performance. Then we have to face a problem, that is, how to determine the decision threshold? The existing DTM algorithms generally solve this problem based on one of two following strategies: empirical ^[19,20] and optimal ^[21,22]. The empirical strategies calculate the decision threshold according to class imbalance ratio, which tend to ignore the real data distribution. While the optimal strategies could adaptively provide an appropriate decision threshold based on the performance feedback from imbalanced training data, which do not need to directly explore the data distribution. Although the optimal DTM strategies have been verified to be effective, their performances are still limited by some potential factors about data distribution, for example, when there exists density variation in data distribution, the performance of the adjusted classifier cannot be guaranteed as the classification boundary can be only parallel translated, but cannot be changed direction. To address the problem referred above, we propose a modified DTM algorithm called clustering-based decision threshold moving (CDTM) in this paper.

Specifically, the proposed CDTM algorithm combines a popular density-based clustering algorithm named Density-Based Spatial Clustering of Applications with Node (DBSCAN) ^[27,28,29] and one of the traditional optimal DTM algorithms ^[21,22]. DBSCAN takes charge of dividing all majority instances into multiple different groups according to their density distribution information. Then, for each majority instance group, it is integrated with all minority instances to constitute a training subset. Next, on each training subset, an optimal DTM algorithm is conducted to search the best decision threshold. When a unseen instance is received, it is first decided which group it falls in by the Gaussian naïve bayes (GNB) rule ^[30,31], and then the corresponding DTM algorithm is called to classify for it. The proposed CTDM algorithm uses the idea of divide-and-conquer method, thus it can adapt the complex density variation existing in feature space well. In this paper, we adopt the optimal decision output compensation (ODOC) ^[22] as the basic strategy, and in context of support vector machine (SVM) ^[32,33] and extreme learning machine (ELM) ^[34,35] respectively, to verify the effectiveness and feasibility of CTDM. The experimental results on 40 benchmark class imbalance datasets indicate that the proposed CDTM algorithm is superior to several other state-of-the-art DTM algorithms in term of G-mean performance metric. The novelty of this work reflects at two following aspects: 1) to our best knowledge, it is the first DTM technique which can change the direction of original classification boundary, and 2) it can better adapt complex data distribution than the emerging DTM techniques as the idea of divide-and-conquer has been embedded inside it.

The rest of this paper is organized as follows: Section 2 reviews the previous work related to DTM, as well indicates why all existing DTM algorithms could not adapt data distribution well. In Section 3, the proposed CTDM algorithm is described in detail. Section 4 provides some compared experimental results and gives the corresponding discussions. Finally, Section 5 concludes the findings of this paper, and indicates future work.

2.   Related work

As mentioned in Section 1, there are two different kinds of strategies to decide the threshold in DTM methods. One is empirical, and the other is optimal. In fact, the primitive DTM approaches tend to designate an empirical value for the threshold, e.g., SVM-THR algorithm which is proposed by Lin and Chen ^[20]. In SVM-THR, the threshold θ is calculated by the following equation:

where ${N}^{-}$ and ${N}^{+}$ denote the number of majority and minority instances in the training set, respectively. It is clear that the class imbalance ratio, i.e., ${N}^{-}/{N}^{+}$, is higher, then the threshold θ is larger. It seems to conform to the actual situation as in general, on a highly skewed data distribution, the minority class is inclined to be severer destroyed. However, the rule is not absolute as the impact of class imbalance distribution is not only related with the class imbalance ratio, but also associates several other factors ^[36]. Therefore, adopting the empirical threshold in DTM may under-compensate or over-compensate the classification boundary, further causing poor classification performance.

In comparison with the empirical DTM strategies, the optimal strategies can effectively adapt the data distribution. In ^[21], an optimal DTM strategy called OTHR is presented. The OTHR firstly trains a biased classification model which is required to provide soft output for each training instance, and then it collects all minority instances which have been misclassified by the trained model. Next, we determine all candidate thresholds according to the following equation,

where ${\theta }_{i}$ denotes the ith candidate threshold, while $h\left({x}_{i}^{+}\right)$ and $h\left({n}_{i}^{+}\right)$ represent the decision outputs of the ith misclassified minority instance and its nearest majority neighbor emerging in the direction of majority class. Finally, on the original training set, we compare the harmonic performance of F-measure and G-mean of adopting each candidate threshold, further determine the optimal threshold. The other optimal DTM strategy is ODOC ^[22] which regards the threshold designation as an optimization problem in continuous space. Therefore, the ODOC adopts mature optimization algorithms to search the best threshold for DTM. Specifically, for binary-class imbalance problem, the ODOC uses the golden section algorithm ^[37], while for multi-class imbalance problem, it uses the particle swarm optimization (PSO) algorithm. G-mean performance metric is used as the fitness function to evaluate the quality of threshold. We note that both OTHR and ODOC strategies do not explore data distribution directly, by adapt it in an indirect fashion.

However, we note that no matter empirical or optimal DTM strategies cannot adapt data distribution well. Figure 1 explains the corresponding reason. In Figure 1, it is not difficult to observe that the traditional DTM strategies can only parallelly move the initially trained classification boundary, but cannot change its direction, further providing a sub-optimal solution. Therefore, it is necessary to amend this bias by providing individual threshold for the instances lying in different regions in feature space.

3.   Methods

3.1.   Clustering majority instances by DBSCAN technique

To realize the individual DTM, we firstly adopt a well-known density-based clustering algorithm called DBSCAN ^[27,28,29] to divide majority instances into multiple disconnected groups. We select to use DBSCAN because density variation existing in data distribution often asks for more discrepant thresholds.

Specifically, the DBSCAN is a traditional density clustering method that portrays the closeness of data distribution based on a pair of parameters (E, M), where E denotes the local neighborhood radius and M describes the threshold of the number of instances in a local neighborhood. DBSCAN searches for clusters by examining the E local neighborhood of each instance in the data set, and if the E neighborhood of an instance $x$ contains more than M instances, a cluster with $x$ as the core object would be created, and then the set of instances which are density reachable from these core objects is iteratively aggregated. This process is roughly described in Figure 2(a), where the red points represent the core instances and the circles denote their E local neighborhoods. The core objects connected by arrows mean that they are density reachable, and all instances in the E neighborhoods of these core objects are clustered into a single group. Then, we can divide instances into multiple disconnected regions, and each of them can be seen as an independent cluster (see Figure 2(b)). Specifically, the DBSCAN algorithm has been shown to discover the clusters with arbitrary shapes in data with noise.

In DBSCAN, there are two important issues requiring to be focused on: one is how to designate the pair of parameters (E, M), and the other is how to determine which cluster a new unseen instance belongs to. For the first issue, we know both parameters are very important for the final clustering results. In this paper, we empirically designated the pair of parameters as (0.15, 5) according to the feedback from lots of experiments. As for the second issue, we suppose that all instances in each cluster satisfy a multivariate Gaussian distribution, and hence adopt GNB rule ^[30,31] to judge which cluster an instance belongs to. Suppose $P\left({c}_{i}\right)$ and $P\left(x\right|{c}_{i})$ denote the prior probability of the cluster ${c}_{i}$, and the conditional probability of an instance $x$ relative to the cluster ${c}_{i}$, respectively. Then, the probability of the instance $x$ belonging to the cluster ${c}_{i}$ could be calculated as follows,

Obviously, it is more reasonable for adopting GNB to determine the cluster the instance falls in than comparing the distance between each cluster centroid and the instance as the GNB rule can adapt the potential density variation existing among different clusters well.

3.2.   Description about CDTM algorithm

In our proposed CDTM algorithm, the DTM strategy is conducted on each training subset that contains all majority instances from a specific cluster divided by DBSCAN and all minority training instances. Specifically, considering that the ODOC strategy has presented more robust performance than OTHR ^[22], we adopt the ODOC as the basic DTM strategy in our CDTM algorithm. That is to say, on each sub-optimization problem, the golden section optimization algorithm is used to search the best threshold. The procedure of the proposed CDTM algorithm is simply described as follows.

In addition, we also provide a flowchart to describe how to train a CDTM model (see Figure 3). Specifically, in CDTM training procedure, the classifier is required to provide soft outputs. Specifically, in this paper, we used two different soft-output classifiers, namely SVM ^[32,33] and ELM ^[34,35], respectively. While in the testing procedure, each test instance ${x}_{i}^{{'}}$ first requires determining which cluster it belongs to, and then its amended output could be calculated by,

where $h\left({x}_{i}^{{'}}\right)$ and $h{'}\left({x}_{i}^{{'}}\right)$ respectively denote the original and amended decision output for the testing instance ${x}_{i}^{{'}}$, and ${\theta }_{j}$ denotes the threshold of the cluster the instance belongs to.

In Figure 4, we use two artificial imbalanced data sets to show the difference between the traditional DTM strategies and the proposed CDTM strategy, further illustrate the necessarily of developing CDTM algorithm. It is clear that in contrast to DTM, the proposed CDTM tend to capture detailed information referring to data distribution, thus it can better adapt the data distribution and provide more appropriate amended boundary.

3.3.   Time complex analysis

Except classification performance, the time complex is also an important metric to evaluate the quality of a learning algorithm.

Suppose there are N training instances, then for CDTM algorithm, the DBSCAN clustering procedure requires $O\left({N}^{2}\right)$ training time, and the SVM training procedure also needs to consume $O\left({N}^{2}\right)$ time, but in worst case, it can cost $O\left({N}^{3}\right)$ time. In contrast to SVM, training ELM is more time-saving as it only consumes $O\left({L}^{2}N\right)$ time, where L denotes the number of layer-nodes. Finally, the golden section search procedure requires costing only $O\left({log}_{2}N\right)$ time. Therefore, we can say that although the CDTM algorithm is always more time-consuming than several traditional DTM algorithms, its time-complex is still acceptable.

4.   Experiments

4.1.   Datasets

In our experiments, we used 40 binary-class imbalanced datasets acquired from Keel data repository ^[38] to verify the effectiveness and superiority of the proposed CDTM algorithm. Specifically, these datasets have a wide variation at aspect of number of instances, features and class imbalance ratios. The details about these used datasets could be found in Table 1.

4.2.   Experimental settings

All experiments were run on a 2.40 GHz Intel(R) Core (TM) i5 10200H 8-core CPU with 16 GB RAM, and the Python 3.8 environment.

In context of SVM ^[32,33] and ELM ^[34,35], we respectively compared the proposed CDTM algorithm with four other algorithms. One is baseline without any process for class imbalance, and three others are THR ^[20], OTHR ^[21] and ODOC ^[22] strategies, respectively.

To guarantee the impartiality of compared experiments, for each classifier, we used the same parameter settings. Specifically, the SVM uses RBF kernel with default parameters, that is, the kernel width σ = 0.01 and the penalty factor C = 1, while the ELM uses sigmoid activation function with 20 hidden nodes. As for our proposed CDTM algorithm, it used the empirical DBSCAN parameter pair (0.15, 5) which has been indicated in Section 3.

Specifically, all experiments were conducted on standardized datasets. That means for each dataset, its each feature should be first proportionally scaled into [0, 1] by,

where ${x}_{ij}$ and ${x}_{ij}^{{'}}$ respectively denote the original and standardized values for the ith instance on the jth feature, while ${x}_{maxj}$ and ${x}_{minj}$ represent the maximal and minimal values in the original jth feature space throughout all training instances.

In addition, we adopted a most popular performance metric, i.e., G-mean ^[39], to evaluate and compare the quality of various compared algorithms. G-mean metric can be calculated as follows:

where ${Acc}_{+}$ and ${Acc}_{-}$ represent the predicted accuracy of positive (minority) class and negative (majority) class, respectively. Therefore, we can say that the G-mean metric reflects the tradeoff between the classification performance of the minority class and that of the majority class.

Finally, to exclude some random factors for experimental results, we also conducted 10 times' external five-folds cross validation, and further provided experimental results in the form of mean ± standard deviation.

4.3.   Comparison between the proposed CDTM and several other DTM algorithms

Tables 2 and 3 present the G-mean results of various DTM strategies in context of SVM and ELM, respectively.

The results in Tables 2 and 3 not only show some known conclusions, but also reveal some new interesting phenomenon. First, we all know that the imbalanced data distribution is generally harmful for traditional classification models, especially when class imbalance ratio is high, this phenomenon tends to be severer. This conclusion is verified by the results in these two tables, again. It is clear that any one DTM strategy performs better and the baseline algorithm, namely SVM or ELM. In addition, we know that in general, the optimal DTM strategies outperform to the empirical ones. This conclusion has also been verified by the results in Tables 2 and 3. Obviously, both OTHR and ODOC strategies have produced significantly better results than the THR strategy as they could adapt data distribution well. Next, we know that the ODOC is more robust than OTHR ^[22], which has also been confirmed in our experimental results. Specifically, in context of SVM, the ODOC yields 13 best results while the OTHR only performs best on 6 datasets, and in context of ELM, the gap between their performances seems to be less, although the ODOC still performs a little better than the OTHR.

In these two tables, we also observe some new and interesting phenomenon. First of all, the proposed CDTM algorithm improves classification performance in comparison to several other DTM algorithms. This conclusion conforms to our anticipation that compared to several other DTM algorithms, the CDTM explores more details about data distribution, and hence it could better adapt the data distribution. Specifically, in contexts of SVM and ELM, the proposed CDTM algorithm performs best on 18 and 22 datasets, respectively. Furthermore, we note that on datasets with low class imbalance ratio, the CDTM has not shown the significant superiority in comparison with the ODOC, but on those highly imbalanced datasets, it performs significantly better. We believe that it attributes to the complexity of data distribution. In general, the datasets with low class imbalance ratios mean simple data distributions, while on this kind of dataset, the learning model generated by the complex CDTM algorithm tends to be overfitting. However, the datasets with high class imbalance ratios often have complex data distributions, which are appropriate for calling CDTM algorithm. According to the experimental results observed in Tables 2 and 3, we can safely draw a conclusion, that is, the proposed CDTM algorithm is robust, as well it is more appropriate used in the scenario with highly skewed data distributions.

4.4.   Significance analysis in statistics

To present a thorough comparison of the various algorithms, we also provide their statistical results. We employed the Friedman test and Holm post-hoc test ^[40] to differentiate the performance of the comparative algorithms throughout 40 datasets. The Friedman test, or the Friedman bidirectional Rank variance analysis, is a statistical test of homogeneity of multiple (related) samples. The Friedman test is defined as:

where P is the number of datasets, J is the number of algorithms, and r_i is the average ranking of the ith algorithm. In such context, the statistical analysis results obtained at the confidence level of α = 0.05 are presented in Tables 4 and 5.

The statistical results in Tables 4 and 5 show that in both contexts of SVM and ELM, the proposed CDTM algorithm has acquired the lowest Friedman's average rankings. Specifically, in context of SVM, the CDTM significantly outperforms to the baseline SVM, THR and OTHR, but we cannot say that it is significantly better than ODOC though it has a lower average ranking than ODOC. As for ELM, the CDTM performs significantly better than the baseline ELM and THR, and meanwhile, it isn't significantly better than two other DTM strategies in statistics.

4.5.   Comparison about running time

Finally, we compared the running time of various algorithms in contexts of SVM and ELM, respectively. The results are presented in Tables 6 and 7.

From the results in Tables 6 and 7, it is not difficult to observe that in both contexts of SVM and ELM, the baseline algorithm is most time-saving, and then the empirical DTM strategy THR is more time-saving than two other optimal DTM strategies, that is, OTHR and ODOC, while the proposed CDTM algorithm is most time-consuming among all strategies. The results conform to the results of time complexity analysis in Section 3 as the CDTM introduces an extra DBSCAN clustering procedure, and meanwhile, it trains more sub-classifiers than several other algorithms. Fortunately, the proposed CDTM algorithm only slightly increases running time compared with two other optimization idea-based DTM algorithms, and thus it can satisfy the requirements of practical applications.

5.   Conclusions

In this paper, a modified decision threshold moving algorithm called CDTM was proposed for classifying imbalanced data. Specifically, the CDTM algorithm introduces DBSCAN clustering technique to deeply capture detailed information about data distribution, and further provides individual and adaptive threshold in different feature regions. It can be seen as a combination of DTM technique and divide-and-conquer method. The proposed algorithm amends the drawbacks of traditional DTM algorithms to some extent. Experimental results on 40 benchmark class imbalance datasets show that the proposed CDTM algorithm is helpful for improving classification performance than several other state-of-the-art DTM algorithms, especially on data with highly class imbalance ratios, the superiority of CDTM is more significant. Additionally, the proposed CDTM algorithm is relatively time-saving, which meets the demands of practical applications in the real-world.

In future work, we wish to develop better individual DTM algorithms with stronger data distribution exploration ability. In addition, how to make individual DTM algorithms adapt multi-class imbalance data will be investigated, too.

Acknowledgments

This study was supported in part by the National Natural Science Foundation of China under grants No. 62176107 and No. 62076111.

Conflict of interest

The authors declare there is no conflict of interest.