Sampling Safety Coefficient for Multi-class Imbalance Oversampling Algorithm

doi:10.3778/j.issn.1673-9418.1911021

Abstract

Abstract:

For the problem in multi-class imbalance, traditional oversampling algorithms easily lead to the issue of overgeneralization and overlap result with poor classification performance. To improve the performance of multi-class learning, a sampling safety coefficient for multi-class imbalance oversampling (SSCMIO) algorithm is proposed. First, with the aim of preventing overgeneralization, the neighbor sampling safety coefficient is designed to assign a small weight to those neighborhoods that may cause excessive generalization. Then, by considering the global characteristics of the sample points, the reverse neighbor sampling safety coefficient is presented to prevent new samples that invade into other classes, which alleviates the overlap between classes. Finally, the C4.5 decision tree is used as the base classifier. Compared with 7 representative oversampling algorithms within 16 public real data sets, SSCMIO can obtain more than 11 optimal values on precision, recall, F-measure, MG and MAUC, the maximum increase with the 5 metrics is 0.4818, 0.3053, 0.3420, 0.2664, and 0.1307 respectively. The experimental results show that the SSCMIO algorithm can achieve better classification performance than other 7 algorithms.

Key words: sampling safety coefficient, oversampling, synthetic minority technique, multi-class imbalanced problems

摘要：

传统的过采样算法在处理多类不平衡问题时容易出现过度泛化和类别重叠，从而降低了分类性能。为了提高多类不平衡学习性能，提出了一种利用采样安全系数的多类不平衡过采样（SSCMIO）算法。首先为了防止过度泛化，采用近邻采样安全系数为那些会造成过度泛化的邻域分配一个较小的权重。然后考虑到样本点的全局特性，采用反向近邻采样安全系数防止新合成的样本点侵入到其他类别区域，减轻类别之间的重叠问题。最后以C4.5决策树作为基分类器，将SSCMIO算法与7种典型的过采样算法进行了对比实验。在16个公开的真实数据集上，SSCMIO算法在准确率、召回率、F-measure、MG、MAUC这5个指标上均能取得11个以上的最优值，在5个指标上最大提升分别是0.481 8、0.305 3、0.342 0、0.266 4、0.130 7。实验结果表明SSCMIO算法相比其他7种算法可以取得更好的分类性能。

关键词: 采样安全系数, 过采样, 合成少数类技术, 多类不平衡问题

DONG Minggang, LIU Ming, JING Chao. Sampling Safety Coefficient for Multi-class Imbalance Oversampling Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1776-1786.

董明刚，刘明，敬超. 利用采样安全系数的多类不平衡过采样算法[J]. 计算机科学与探索, 2020, 14(10): 1776-1786.

References

[1] He H B, Garcia E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1263-1284.
[2] Krawczyk B. Learning from imbalanced data: open challenges and future directions[J]. Progress in Artificial Intelligence, 2016, 5(4): 221-232.
[3] Zhang C, Tan K C, Li H, et al. A cost-sensitive deep belief network for imbalanced classification[J]. IEEE transactions on Neural Networks and Learning Systems, 2018, 30(1): 1-14.
[4] García S, Zhang Z L, Altalhi A, et al. Dynamic ensemble selection for multi-class imbalanced datasets[J]. Information Sciences, 2018, 445/446: 22-37.
[5] Tsai C F, Lin W C, Hu Y H, et al. Under-sampling class imbalanced datasets by combining clustering analysis and instance selection[J]. Information Sciences, 2019, 477: 47-54.
[6] Chawla N V, Bowyer K W, Hall L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2002, 16(1): 321-357.
[7] He H B, Bai Y, Garcia E A, et al. ADASYN: adaptive synthetic sampling approach for imbalanced learning[C]//Proceedings of the 2008 IEEE International Joint Conference on Neural Networks, Hong Kong, China, Jun 1-8, 2008. Washington: IEEE Computer Society, 2008: 1322-1328.
[8] Han H, Wang W Y, Mao B H. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[C]//LNCS 3644: Proceedings of the 2005 International Conference on Intelligent Computing, Hefei, Aug 23-26, 2005. Berlin, Heidelberg: Springer, 2005: 878-887.
[9] Yan Y T, Zhu Y W, Wu Z B, et al. Constructive covering algorithm-based SMOTE over-sampling method[J]. Journal of Frontiers of Computer Science and Technology，2020, 14(6): 975-984. 严远亭, 朱原玮, 吴增宝, 等. 构造性覆盖算法的SMOTE过采样方法[J]. 计算机科学与探索， 2020, 14(6): 975-984.
[10] Huang H S, Wei J A, Kang P D. New over-sampling SVM classification algorithm based on unbalanced data sample characteristics[J]. Control and Decision, 2018, 33(9): 16-25.黄海松, 魏建安, 康佩栋. 基于不平衡数据样本特性的新型过采样SVM分类算法[J]. 控制与决策, 2018, 33(9): 16-25.
[11] Barua S, Islam M M, Yao X, et al. MWMOTE majority weighted minority oversampling technique for imbalanced data set learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(2): 405-425.
[12] Zhu T, Lin Y, Liu Y. Synthetic minority oversampling technique for multiclass imbalance problems[J]. Pattern Recognition, 2017, 72: 327-340.
[13] Nekooeimehr I, Lai-yuen S K. Adaptive semiunsupervised weighted oversampling (A-SUWO) for imbalanced datasets[J]. Expert Systems with Applications, 2016, 46: 405-416.
[14] Wang C X , Zhang T, Ma C S. Improved SMOTE algorithm for imbalanced datasets[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(6): 91-98. 王超学, 张涛, 马春森. 面向不平衡数据集的改进型SMOTE算法[J]. 计算机科学与探索, 2014, 8(6): 91-98.
[15] Alcalá-Fdez J, Fernández A, Luengo J, et al. Keel data-mining software tool: data set repository, integration of algorithms and experimental analysis framework[J]. Journal of Multiple- Valued Logic & Soft Computing, 2011, 17: 255-287.
[16] Fernández A, García S, del Jesus M J, et al. A study of the behaviour of linguistic fuzzy rule based classification systems in the framework of imbalanced data-sets[J]. Fuzzy Sets and Systems, 2008, 159(18): 2378-2398.
[17] Cohen W W. Fast effective rule induction[M]. San Francisco: Morgan Kaufmann, 1995.
[18] Hall M, Frank E, Holmes G, et al. The WEKA data mining software: an update[J]. ACM SIGKDD Explorations Newsletter, 2009, 11(1): 10-18.
[19] Wu Y F, Liang J Y, Wang J H. Classification algorithm based on hybrid sampling for unbalanced data[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(2): 342-349. 吴艺凡, 梁吉业, 王俊红. 基于混合采样的非平衡数据分类算法[J]. 计算机科学与探索, 2019, 13(2): 342-349.
[20] Zhao N, Zhang X F, Zhang L J. Overview of imbalanced data classification[J]. Computer Science, 2018, 45(6A): 22-27.赵楠，张小芳，张利军. 不平衡数据分类研究综述[J]. 计算机科学，2018, 45(6A): 22-27.
[21] Li Y X, Chai Y, Hu Y Q, et al. Review of imbalanced data classification methods[J]. Control and Decision, 2019, 34(4): 673-688. 李艳霞，柴毅，胡友强，等. 不平衡数据分类方法综述[J]. 控制与决策, 2019, 34(4): 673-688.
[22] Sander J, Ester M, Kriegel H P, et al. Density-based clustering in spatial databases: the algorithm GDBSCAN and its applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2): 169-194.
[23] Sun Y, Kamel M S, Wang Y. Boosting for learning multiple classes with imbalanced class distribution[C]//Proceedings of the 6th International Conference on Data Mining, Hong Kong, China, Dec 18-22, 2006. Washington: IEEE Computer Society, 2006: 592-602.
[24] Hand D J, Till R J. A simple generalisation of the area under the ROC curve for multiple class classification problems[J]. Machine Learning, 2001, 45(2): 171-186.
[25] Guo H, Liu H, Wu C, et al. Logistic discrimination based on G-mean and F-measure for imbalanced problem[J]. Journal of Intelligent & Fuzzy Systems, 2016, 31(3): 1155-1166.
[26] Bradley A P. The use of the area under the ROC curve in the evaluation of machine learning algorithms[J]. Pattern Recognition, 1997, 30(7): 1145-1159.
[27] Hanley J A, Mcneil B J. The meaning and use of the area under a receiver operating characteristic (ROC) curve[J]. Radiology, 1982, 143(1): 29-36.