High-Efficient Parameter-Pruning Algorithm of Decision Tree for Large Dataset

doi:10.19678/j.issn.1000-3428.0066519

Abstract

Abstract:

Decision tree(DT) have a good effect on data classification but easily develop overfitting. The solution to this problem is to prune the DT. However, the pruning algorithm has shortcomings; for example, prepruning is prone to underfitting, the postpruning time is extended, and Web-search pruning is only suitable for small datasets. This study proposes an efficient parameter-pruning algorithm for the DT to solve the above problems. Based on the network security situation awareness model, the architecture of the pruned decision-tree situation awareness system is established, and the data flow of the network is analyzed. During the process of generating the DT, enumeration and binary search algorithms are used to determine the maximum depth of the DT, and a depth-first search algorithm is used to determine the minimum number of split nodes and the maximum number of features. Finally, the three optimal parameters are combined to complete the pruning from top to bottom. The experimental results show that this algorithm has a low risk of overfitting in large datasets. The accuracy of the training and testing sets exceed 95%. Compared to the Pessimistic Error-Pruning(PEP) algorithm that exhibits the best performance in post-pruning algorithms, the pruning algorithm is almost 20 times faster.

Key words: Decision Tree(DT), pruning, overfitting, security situational awareness, generalization

摘要：

决策树在数据分类上具有较好的效果，但容易产生过拟合的现象，解决方案是对决策树进行剪枝处理，然而传统剪枝算法普遍存在预剪枝容易欠拟合、后剪枝时间消耗多、网络搜索剪枝仅适用于小型数据集等问题。为了解决以上问题，提出一种高效的决策树参数剪枝算法。根据网络安全态势感知模型，建立剪枝决策树态势感知系统架构，分析网络数据流。在生成决策树的过程中，利用枚举与二分搜索算法找出决策树最大深度，采用深度优先搜索算法找到节点最小分裂数和最大特征数，最终结合这3个最优参数自上而下完成剪枝。实验结果表明，所提算法在大型数据集上的过拟合风险较小，训练集与测试集准确率都在95%以上，同时相比于后剪枝算法中表现较好的悲观错误剪枝算法快了近20倍。

关键词: 决策树, 剪枝, 过拟合, 安全态势感知, 泛化性

Zhaoxian XIE, Xingmin ZOU, Wenjing ZHANG. High-Efficient Parameter-Pruning Algorithm of Decision Tree for Large Dataset[J]. Computer Engineering, 2024, 50(1): 156-165.

谢兆贤, 邹兴敏, 张文静. 面向大型数据集的高效决策树参数剪枝算法[J]. 计算机工程, 2024, 50(1): 156-165.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0066519

https://www.ecice06.com/EN/Y2024/V50/I1/156

Figures/Tables 18

Fig.1 Architecture of network security situational awareness system

Fig.2 Architecture of pruning decision tree situation awareness system

Fig.3 Procedure of PAP algorithm

Fig.4 Comparison before and after data balance

Fig.5 Model of SMOTE algorithm

Fig.6 Sample information gain

Fig.7 Fitting degree of the model before pruning

Fig.8 Accuracy of training set under the optimal depth

Fig.9 Accuracy under the minimum split sample number and maximum feature number

Fig.10 Fitting situation under the optimal parameters

Fig.11 Fitting degree of three pruning algorithms

References 25

1	龚俭, 臧小东, 苏琪, 等. 网络安全态势感知综述. 软件学报, 2017, 28(4): 1010- 1026.
	GONG J, ZANG X D, SU Q, et al. Survey of network security situation awareness. Journal of Software, 2017, 28(4): 1010- 1026.
2	刘龙霞, 吴军华. 基于分类树和贪心算法的测试数据自动生成方法. 计算机工程与设计, 2011, 32(8): 2734-2736, 2820.
	LIU L X, WU J H. Automated test data generation method based on classification-tree and greedy algorithm. Computer Engineering and Design, 2011, 32(8): 2734-2736, 2820.
3	BRUNELLO A, MARZANO E, MONTANARI A, et al. Decision tree pruning via multi-objective evolutionary computation. International Journal of Machine Learning and Computing, 2017, 7(6): 167- 175. doi: 10.18178/ijmlc.2017.7.6.641
4	焦亚男, 马杰. 一种改进的MEP决策树剪枝算法. 河北工业大学学报, 2019, 48(6): 24- 30.
	JIAO Y N, MA J. An improved MEP decision tree pruning algorithm. Journal of Hebei University of Technology, 2019, 48(6): 24- 30.
5	郑伟, 马楠. 一种改进的决策树后剪枝算法. 计算机与数字工程, 2015, 43(6): 960-966, 971.
	ZHENG W, MA N. An improved post-pruning algorithm for decision tree. Computer & Digital Engineering, 2015, 43(6): 960-966, 971.
6	周莉, 李静毅. 基于决策树算法的联级网络安全态势感知模型. 计算机仿真, 2021, 38(5): 264- 268.
	ZHOU L, LI J Y. Security situation awareness model of joint network based on decision tree algorithm. Computer Simulation, 2021, 38(5): 264- 268.
7	宋万洋, 李国和, 吴卫江, 等. 基于平衡准确率和规模的决策树剪枝算法. 科学技术与工程, 2016, 16(16): 79- 82.
	SONG W Y, LI G H, WU W J, et al. Pruning algorithm of decision tree by balance of accuracy and size. Science Technology and Engineering, 2016, 16(16): 79- 82.
8	MALIK A J, KHAN F A. A hybrid technique using binary particle swarm optimization and decision tree pruning for network intrusion detection. Cluster Computing, 2018, 21(1): 667- 680. doi: 10.1007/s10586-017-0971-8
9	SAWANT S S, WIEDMANN M, GÖB S, et al. Compression of deep convolutional neural network using additional importance-weight-based filter pruning approach. Applied Sciences, 2022, 12(21): 11184. doi: 10.3390/app122111184
10	于安池, 储茂祥, 杨永辉, 等. 具有强化学习策略的决策树算法. 合肥工业大学学报(自然科学版), 2021, 44(5): 616- 620.
	YU A C, CHU M X, YANG Y H, et al. Decision tree algorithm with reinforcement learning strategy. Journal of Hefei University of Technology(Natural Science), 2021, 44(5): 616- 620.
11	吕高锋, 谭靖, 乔冠杰, 等. 决策树报文分类算法. 国防科技大学学报, 2022, 44(3): 184- 193.
	LÜ G F, TAN J, QIAO G J, et al. Decision tree packet classification algorithm. Journal of National University of Defense Technology, 2022, 44(3): 184- 193.
12	MA L, XIAO H, TAO J, et al. An intelligent approach for reservoir quality evaluation in tight sandstone reservoir using gradient boosting decision tree algorithm. Open Geosciences, 2022, 14(1): 629- 645. doi: 10.1515/geo-2022-0354
13	CAO Y, WEI W, ZHOU J. Privacy protection data mining algorithm in blockchain based on decision tree classification. Web Intelligence, 2022, 20(2): 103- 112. doi: 10.3233/WEB-210485
14	PASHAMOKHTARI A, BATISTA G, HABIBI-GHARAKHEILI H. AdIo Tack: quantifying and refining resilience of decision tree ensemble inference models against adversarial volumetric attacks on IoT networks. Computers & Security, 2022, 120, 102801.
15	CAMPBELL T W, RODER H, GEORGANTAS R W III, et al. Exact Shapley values for local and model-true explanations of decision tree ensembles. Machine Learning with Applications, 2022, 9, 100345. doi: 10.1016/j.mlwa.2022.100345
16	CHEW Y J, OOI S Y, WONG K S, et al. Adoption of IP truncation in a privacy-based decision tree pruning design: a case study in network intrusion detection system. Electronics, 2022, 11(5): 805. doi: 10.3390/electronics11050805
17	MEI S, MONTANARI A. The generalization error of random features regression: precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2021, 75(4): 1- 15.
18	程家根, 祁正华, 陈天赋. 基于RBF神经网络的网络安全态势感知. 南京邮电大学学报(自然科学版), 2019, 39(4): 88- 95.
	CHENG J G, QI Z H, CHEN T F. Network security situation awareness based on RBF neural networks. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2019, 39(4): 88- 95.
19	ZHANG J N. Network security situational awareness based on genetic algorithm in wireless sensor networks[J/OL]. Journal of Sensors: 8292920[2022-11-12].https://doi.org/10.1155/2022/8292920.
20	MORDVANYUK N, BIFET A, LÓPEZ B. VEPRECO: vertical databases with pre-pruning strategies and common candidate selection policies to fasten sequential pattern mining. Expert Systems with Applications, 2022, 204, 117517. doi: 10.1016/j.eswa.2022.117517
21	NAND S, JOSHUA M. CausNet: generational orderings based search for optimal Bayesian networks via dynamic programming with parent set constraints. BMC Bioinformatics, 2023, 24(1): 46. doi: 10.1186/s12859-023-05159-6
22	ZHANG S Z, WANG Y C, LV Q. Exploring artificial intelligence architecture in data cleaning based on Bayesian networks[EB/OL]. [2022-11-12].https://dl.acm.org/doi/10.1155/2022/6731781.
23	马红明, 马浩, 杨迪, 等. 基于奇异阈值理论的电力营销数据在线清理方法[J/OL]. 电测与仪表: 1-9[2022-11-12].https://kns.cnki.net/kcms/detail/23.1202.TH.20211213.1353.004.html.
	MA H M, MA H, YANG D, et al. Online cleaning method of electric power marketing data based on singular threshold theory[J/OL]. Electrical Measurement and Instrumentation: 1-9[2022-11-12].https://kns.cnki.net/kcms/detail/23.1202.TH.20211213.1353.004.html.(in Chinese)
24	王曜, 郑列. 一种新的基于聚类的试探性SMOTE算法. 重庆理工大学学报(自然科学版), 2022, 36(4): 187- 195.
	WANG Y, ZHENG L. New tentative SMOTE algorithm based on clustering. Journal of Chongqing University of Technology (Natural Science), 2022, 36(4): 187- 195.
25	RAO S W, ZOU G P, YANG S Y, et al. Fault diagnosis of power transformers using ANN and SMOTE algorithm. International Journal of Applied Electromagnetics and Mechanics, 2022, 70(4): 345- 355. doi: 10.3233/JAE-210227

[1]	Wei GAO, Shuailong LI, Lin MAO, Lei WANG, Yingying LI, Lin HAN. One Acceleration Strategy for Operator Generation Based on TVM [J]. Computer Engineering, 2024, 50(8): 353-362.
[2]	Lili GENG, Baoning NIU. Convolutional Neural Network Pruning Based on Channel Similarity Entropy [J]. Computer Engineering, 2024, 50(7): 133-143.
[3]	Lin CHEN, Yuankai FAN, Zhenying HE, Xiaoqing LIU, Yang YANG, Lumin TANG. Combinatorial Generalization Ability Evaluation Method of SQL-to-text Model [J]. Computer Engineering, 2024, 50(3): 326-335.
[4]	DAI Lei, CAO Lin, GUO Yanan, ZHANG Fan, DU Kangning. Deepfake Cross-Model Defense Method Based on Generative Adversarial Network [J]. Computer Engineering, 2024, 50(10): 100-109.
[5]	DONG Fengkai, ZOU Xiaoqiang, WANG Jiahui, MA Liming, YANG Wenyuan, LIU Xiyao. Dual-Stream Generalized Face Forgery Detection Method Based on Intra-Inter Frame Self-Blending [J]. Computer Engineering, 2024, 50(10): 185-195.
[6]	FU Jiahao, YANG Jiayi, LI Aiguo. High-Utility Semantic Trajectory Pattern Mining for Security System [J]. Computer Engineering, 2023, 49(6): 62-70.
[7]	MA Jiaxiang, SONG Xiaoning. Soft Pruning Algorithm Based on Lottery Ticket Hypothesis [J]. Computer Engineering, 2023, 49(5): 97-104.
[8]	DU Ming, HAO Yan, ZHOU Junfeng, TAN Yuting. An Efficient Method for Mining Periodic Cliques [J]. Computer Engineering, 2023, 49(4): 68-76.
[9]	AN Zhiguo, PENG Zheng, YI Mancheng, LIU Jianxin, YU Sifan. Filter Competition Training of Neural Networks [J]. Computer Engineering, 2023, 49(4): 120-124.
[10]	CHENG Xiaohui, LI Yu, KANG Yanping. Double Standard Pruning of Convolution Network Based on Feature Extraction of Intermediate Graph [J]. Computer Engineering, 2023, 49(3): 105-112.
[11]	Kun FU, Minglei SUN, Yuhan HAO, Yinghua LIU. Adversarial Training Based Pseudo Label Constraint Auto-Encoder [J]. Computer Engineering, 2023, 49(11): 123-130.
[12]	HUANG Junyang, WANG Zhenyu, LIANG Jiaqing, XIAO Yanghua. NL2SQL Model Based on Self-Pruning Heterogeneous Graph [J]. Computer Engineering, 2022, 48(9): 71-77,88.
[13]	WANG Guodong, YE Jian, XIE Ying, QIAN Yueliang. Structured Pruning Algorithm with Adaptive Threshold Based on Gradient [J]. Computer Engineering, 2022, 48(9): 113-120.
[14]	SUN Jia, ZHANG Jianhui, BU Youjun, CHEN Bo, HU Nan, WANG Fangyu. Log Anomaly Detection Method Based on CNN-BiLSTM Model [J]. Computer Engineering, 2022, 48(7): 151-158,167.
[15]	LI Haomin, LI Guangping. Image Super-Resolution Reconstruction Algorithm Based on Sparse Neural Network [J]. Computer Engineering, 2022, 48(7): 247-253.

Please choose a citation manager

Content to export