Decision tree improvement method for imbalanced data

doi:10.11772/j.issn.1001-9081.2018071513

Abstract

Abstract:

Focusing on the problem that serious imbalance between abnormal data and normal data in anomaly detection will lead to performance degradation of decision tree, three improved methods for C4.5 decision tree were proposed, which are C4.5+δ, UDE (Uniform Distribution Entropy) and IDEF (Improved Distribution Entropy Function). Firstly, it was deduced that the attribute selection criterion of C4.5 tends to choose the ones with imbalanced splitting. Secondly, why imbalanced splitting decreases the accuracy of anomaly (minority) detection was analyzed. Thirdly, the attribute selection criterion-information gain ratio of C4.5 was improved by introducing relaxation factor and uniform distribution entropy, or substituting distribution entropy function. Finally, three improved decision trees were verified on WEKA platform and NSL-KDD dataset. Experimental results show that three proposed improved methods can increase the accuracy of anomaly detection. Compared with C4.5, the accuracies of C4.5+7, UDE and IDEF on KDDTest-21 dataset are improved by 3.16, 3.02 and 3.12 percentage points respectively, which are better than the methods using Rényi entropy or Tsallis entropy as splitting criterion. Furthermore, using improved decision trees to detect anomalies in the industrial control system can not only improve the recall ratio of anomalies, but also reduce false positive rate.

Key words: imbalanced data, anomaly detection, decision tree, C4.5, information gain ratio

摘要：

针对异常检测中异常数据与正常数据的比例严重不平衡导致决策树性能下降的问题，提出了C4.5决策树的三种改进方法——C4.5+δ、均匀分布熵（UDE）和改进分布熵函数（IDEF）。首先，推导了C4.5算法中属性选择准则会倾向于选择偏斜划分的属性；然后，分析了偏斜划分使得异常（少数类）检测精度下降的原因；其次，分别通过引入缓和因子、均匀分布熵或替换分布熵函数改进了C4.5算法的属性选择准则——信息增益率；最后，利用WEKA平台和NSL-KDD数据集对改进的决策树进行验证。实验结果表明，三种改进方法均能提高异常检测精度。其中，相比于C4.5，C4.5+7、UDE和IDEF算法在KDDTest-21数据集上的少数类检测精度（灵敏度）分别提高了3.16、3.02和3.12个百分点，均优于采用Rényi熵和Tsallis熵作为分裂准则的方法。此外，利用三种改进的决策树检测工业控制系统中的异常，不仅可以提高异常的查全率还能减小误报率。

关键词: 不平衡数据, 异常检测, 决策树, C4.5, 信息增益率

CLC Number:

TP181

WANG Wei, XIE Yaobin, YIN Qing. Decision tree improvement method for imbalanced data[J]. Journal of Computer Applications, 2019, 39(3): 623-628.

王伟, 谢耀滨, 尹青. 针对不平衡数据的决策树改进方法[J]. 计算机应用, 2019, 39(3): 623-628.

References

[1] ESKIN E, ARNOLD A, PRERAU M, et al. A geometric framework for unsupervised anomaly detection[J]. Applications of Data Mining in Computer Security, 2002, 6:77-101.
[2] ISERMANN R, BALLE P. Trends in the application of model-based fault detection and diagnosis of technical processes[J]. Control Engineering Practice, 1997, 5(5):709-719.
[3] KOU Y, LU C T, SIRWONGWATTANA S, et al. Survey of fraud detection techniques[C]//Proceedings of the 2004 IEEE International Conference on Networking, Sensing and Control. Piscataway, NJ:IEEE, 2004:749-754.
[4] 王莉莉,付忠良,陶攀,等.基于主动学习不平衡多分类AdaBoost算法的心脏病分类[J].计算机应用,2017,37(7):1994-1998.(WANG L L, FU Z L, TAO P, et al. Heart disease classification based on active imbalance multi-class AdaBoost algorithm[J]. Journal of Computer Applications, 2017, 37(7):1994-1998.)
[5] FU K, CHENG D, TU Y, et al. Credit card fraud detection using convolutional neural networks[C]//Proceedings of the 2016 International Conference on Neural Information Processing. Berlin:Springer, 2016:483-490.
[6] DANENAS P, GARSVA G. Selection of support vector machines based classifiers for credit risk domain[J]. Expert Systems with Applications, 2015, 42(6):3194-3204.
[7] MARTIN-DIAZ I, MORINIGO-SOTELO D, DUQUE-PEREZ O, et al. Early fault detection in induction motors using AdaBoost with imbalanced small data and optimized sampling[J]. IEEE Transactions on Industry Applications, 2017, 53(3):3066-3075.
[8] 赵楠,张小芳,张利军.不平衡数据分类研究综述[J]. 计算机科学,2018,45(S1):22-27.(ZHAO N, ZHANG X F, ZHANG L J. Overview of imbalanced data classification[J]. Computer Science, 2018, 45(S1):22-27.)
[9] IRTAZA A, ADNAN S M, AHMED K T, et al. An ensemble based evolutionary approach to the class imbalance problem with applications in CBIR[J]. Applied Sciences, 2018, 8(4):495.
[10] GALAR M, FERNANDEZ A, BARRENECHEA E, et al. EUSBoost:enhancing ensembles for highly imbalanced data-sets by evolutionary undersampling[J]. Pattern Recognition, 2013, 46(12):3460-3471.
[11] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE:synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2011, 16(1):321-357.
[12] LAURIKKALA J. Improving identification of difficult small classes by balancing class distribution[C]//Proceedings of the 8th Conference on Artificial Intelligence in Medicine in Europe. Berlin:Springer, 2001:63-66.
[13] KUBAT M, MATWIN S. Addressing the curse of imbalanced training sets:one-sided selection[C]//Proceedings of the 14th International Conference on Machine Learning. New York:ACM, 1997:179-186.
[14] TAHIR M A, KITTLER J, MIKOLAJCZYK K, et al. A multiple expert approach to the class imbalance problem using inverse random under sampling[C]//Proceedings of the 8th International Workshop on Multiple Classifier Systems. Berlin:Springer, 2009:82-91.
[15] IMRAN M, RAO V S, AMARASIMHA T, et al. A novel technique on class imbalance big data using analogous over sampling approach[J]. International Journal of Computational Intelligence Research, 2017, 13(10):2407-2417.
[16] LIMA C F L, de ASSIS F M, de SOUZA C P. Decision tree based on Shannon, Rényi and Tsallis entropies for intrusion tolerant systems[C]//Proceedings of the 5th International Conference on Internet Monitoring and Protection. Piscataway, NJ:IEEE, 2010:117-122.
[17] BOONCHUAY K, SINAPIROMSARAN K, LURSINSAP C. Decision tree induction based on minority entropy for the class imbalance problem[J]. Pattern Analysis and Applications, 2017, 20(3):769-782.
[18] KIRSHNERS A, PARSHUTIN S, GORSKIS H. Entropy-based classifier enhancement to handle imbalanced class problem[J]. Procedia Computer Science, 2017, 104:586-591.
[19] LI X, ZHAO H, ZHU W. A cost sensitive decision tree algorithm with two adaptive mechanisms[J]. Knowledge-Based Systems, 2015, 88:24-33.
[20] 郑燕,王杨,郝青峰,等.用于不平衡数据分类的代价敏感超网络算法[J].计算机应用,2014,34(5):1336-1340.(ZHENG Y, WANG Y, HAO Q F, et al. Cost-sensitive hypernetworks for imbalanced data classification[J]. Journal of Computer Applications, 2014, 34(5):1336-1340.)
[21] LEE S J, XU Z, LI T, et al. A novel bagging C4.5 algorithm based on wrapper feature selection for supporting wise clinical decision making[J]. Journal of Biomedical Informatics, 2018, 78:144-155.
[22] QUINLAN J R. C4.5:Programs for Machine Learning[M]. San Francisco, CA:Morgan Kaufmann, 1993:17-26.
[23] FRANK E, HALL M A, WITTEN L H. The WEKA workbench. online appendix for "Data mining:practical machine learning tools and techniques"[EB/OL]. (2016-11-22)[2018-05-04]. https://www.cs.waikato.ac.nz/ml/weka/Witten_et_al_2016_appendix.pdf.
[24] DHANABAL L, SHANTHARAJAH S P. A study on NSL-KDD dataset for intrusion detection system based on classification algorithms[J]. International Journal of Advanced Research in Computer and Communication Engineering, 2015, 4(6):446-452.
[25] ADEPU S, MATHUR A. An investigation into the response of a water treatment system to cyber attacks[C]//Proceedings of the 17th IEEE International Symposium on High Assurance Systems Engineering. Washington, DC:IEEE Computer Society, 2016:141-148.
[26] GOH J, ADEPU S, JUNEJO K N, et al. A dataset to support research in the design of secure water treatment systems[C]//Proceedings of the 11th International Conference on Critical Information Infrastructures Security. Berlin:Springer, 2016:88-99.