一种单位代价收益决策树剪枝算法

J4 ›› 2016, Vol. 38 ›› Issue (05): 1023-1030.

一种单位代价收益决策树剪枝算法

周美琴，陈诗旭，袁鼎荣，朱新华

（广西师范大学广西“多源信息挖掘与安全”重点实验室，广西桂林 541004）

收稿日期:2015-06-10 修回日期:2015-08-01 出版日期:2016-05-25 发布日期:2016-05-25
基金资助:
国家自然科学基金（61462010,61363036)

A pruning algorithm of decision
tree based on unit cost gains

ZHOU Meiqin,CHEN Shixu，YUAN Dingrong,ZHU Xinhua

（Guangxi Key Lab of MultiSource Information Mining & Security,Guangxi Normal University,Guilin 541004,China）

Received:2015-06-10 Revised:2015-08-01 Online:2016-05-25 Published:2016-05-25

摘要/Abstract

摘要：

目前关于决策树剪枝优化方面的研究主要集中于预剪枝和后剪枝算法。然而，这些剪枝算法通常作用于传统的决策树分类算法，在代价敏感学习与剪枝优化算法相结合方面还没有较好的研究成果。基于经济学中的效益成本分析理论，提出代价收益矩阵及单位代价收益等相关概念，采用单位代价收益最大化原则对决策树叶节点的类标号进行分配，并通过与预剪枝策略相结合，设计一种新型的决策树剪枝算法。通过对生成的决策树进行单位代价收益剪枝，使其具有代价敏感性，能够很好地解决实际问题。实验结果表明，该算法能生成较小规模的决策树，且与REP、EBP算法相比具有较好的分类效果。

关键词: 代价, 收益, 剪枝算法, 决策树

Abstract:

At present, the research on pruning optimization of the decision tree focuses on prepruning and postpruning algorithms. However, these pruning algorithms are usually effective for the traditional decision tree classification algorithms. The research on the pruning optimization algorithm integrated with cost sensitive learning has no better results. We design a new pruning algorithm based on the benefit cost analysis theory of economics. We define the concepts of cost gains matrix and unit cost gains. Furthermore, the class labels of decision tree leaves are distributed on the principle of maximizing the gains of unit cost. Pruning the decision tree based on the unit cost gains can solve practical problems well. Experimental results show that the proposed algorithm outperforms current pruning algorithms, which can generate a smaller decision tree and which has a better classification effect in comparison with the REP and EBP algorithms.

Key words: cost;gains;pruning algorithm;decision tree

周美琴，陈诗旭，袁鼎荣，朱新华. 一种单位代价收益决策树剪枝算法[J]. J4, 2016, 38(05): 1023-1030.

ZHOU Meiqin,CHEN Shixu，YUAN Dingrong,ZHU Xinhua. A pruning algorithm of decision
tree based on unit cost gains [J]. J4, 2016, 38(05): 1023-1030.

参考文献［17］

［1］	Yan Wei.A software project estimation method based on decision trees［J］.Computer Engineering & Science,2009,31(8):117120．(in Chinese)
［2］	Guo Dongmei, Li Chaopin. An expert system for acaridida classification and indentification based on decision trees［J］.Computer Engineering & Science,2012,34(3):192195.(in Chinese)
［3］	Li Daoguo, Miao Duoqian, Yu Bing. Research and improvement of decision tree s prune algorithm［J］.Computer Engineering,2005,31(8):1921．(in Chinese)
［4］	Xu Jing,Liu Xumin, Guan Yong, et al.Pruning algorithm of decision tree based on condition misclassification［J］.Computer Engineering,2010,36（23）：5052．(in Chinese)
［5］	Zheng Wei,Ma Nan.An improved postpruning algorithm for decision tree［J］.Computer & Digital Engineering,2015,43(6):960966.(in Chinese)
［6］	You Junping,Wei Jinmao,Wang Mingyang.Decision tree pruning method based on RST［J］.Computer Engineering & Science,2007,29(1):123125．(in Chinese)
［7］	Li Renliang,Li Yijie.Decision trees pruning based on multistrategy and its application［J］．Computer Simulation,2010,27(11):7881．
［8］	Elkan C. The foundations of costsensitive learning［C］∥Proc of the 17th International Joint Conference on Artificial Intelligence(IJCAI01),2001:973978．
［9］	Suan L,Sunil V.A survey of costsensitive decision tree induction algorithms［J］.ACM Compute Surv,2013,45（2）：Article 16．
［10］	Zhang S.Decision tree classifiers sensitive to heterogeneous costs ［J］.Journal of Systems and Software,2012,85(4):771779．
［11］	Mingers J.An empirical comparison of pruning methods for decision tree induction ［J］.Machine Learning,1989,4(2):227243．
［12］	Breiman L,Friedman J,Olshen R A,et al.Classification and regression trees［M］.USA:Belmont,1984．
［13］	Quinlan J R. Simplifying decision trees［J］.International Journal of ManMachine Studies,1987,27(3):221234．
［14］	Niblett T,Bratko I.Learning decision rules in noisy domains［C］∥Proc of the 6th Annual Technical Conference on Research and Development in Expert Systems,1986:2534．
［15］	Windeatt T,Ardeshir G.An empirical comparison of pruning methods for ensemble classifiers ［J］.Electronic Edition,2001(2189):208217．
［16］	Mei K,Rovnyak S M.Responsebased decision trees to trigger oneshot stabilizing control［J］.IEEE Transactions on Power Systems,2004,19(1):531537．
［17］	Xu Xianghua, Zhu Jie, Guo Qiang. Decision tree dynamic pruning method based on minimum description length in speech recognition［J］,Acta Acustica,2006,31(4):370376．(in Chinese)
［18］	Newman D J,Blake C,Merz C J.UCI repository of machine learning data bases［EB/OL］.［20100110］.available:http://archive.ics.uci.edu/ml/datasets.html.
［19］	Mei K,Rovnyak S M.Responsebased decision trees to trigger oneshot stabilizing control［J］.IEEE Transactions on Power Systems,2004,19(1):531537．
	附中文参考文献：
［1］	阎巍.基于决策树的软件项目估算方法［J］.计算机工程与科学,2009,31(8):117120．
［2］	郭冬梅,李朝品.基于检索决策树的螨种分类鉴定专家系统［J］.计算机工程与科学,2012,34(3):192195.
［3］	李道国,苗夺谦,俞冰.决策树剪枝算法的研究与改进［J］.计算机工程,2005,31(8):1921．
［4］	徐晶,刘旭敏,关永,等.基于条件误分类的决策树剪枝算法［J］.计算机工程，2010,36（23）：5052．
［5］	郑伟,马楠.一种改进的决策树后剪枝算法［J］.计算机与数字工程,2015,43(6):960966,971．
［6］	由军平,卫金茂,王名扬.基于粗集理论的决策树剪枝［J］.计算机工程与科学,2007,29(1):123125．
［7］	李仁良,李义杰.基于多策略的决策树剪枝算法及其应用［J］.计算机仿真,2010,27(11):7881．
［17］	徐向华,朱杰,郭强.语音识别中基于最小描述长度准则的决策树动态剪枝算法［J］.声学学报,2006,31(4):370376．

[1]	崔弘, 赵双, 张广胜, 苏金树. 基于机器学习的移动代理应用流量识别方法[J]. 计算机工程与科学, 2022, 44(04): 654-664.
[2]	刘云, 郑文凤, 张轶. 代价约束算法对入侵检测特征提取的优化研究[J]. 计算机工程与科学, 2022, 44(03): 447-453.
[3]	贾俊杰, 段超强. 基于评分离散度的托攻击检测算法[J]. 计算机工程与科学, 2022, 44(03): 554-562.
[4]	陈丽芳, 代琪, 赵佳亮. 不平衡数据多粒度集成分类算法研究[J]. 计算机工程与科学, 2021, 43(05): 917-925.
[5]	曹婷婷, 张忠林. 代价敏感的KPCA-Stacking不均衡数据分类算法[J]. 计算机工程与科学, 2021, 43(03): 525-533.
[6]	王鑫, 陈建凯, 翟俊海, . 区间值属性单调决策树算法的扩展[J]. 计算机工程与科学, 2020, 42(03): 557-563.
[7]	陈丽芳,冯力静,刘保相. 神经网络规则优化建模与应用[J]. 计算机工程与科学, 2019, 41(12): 2247-2254.
[8]	陈力1，费洪晓2，丁海伦2，成琳2，翟纪宇2. 基于双决策树的数据采样方法[J]. 计算机工程与科学, 2019, 41(01): 130-135.
[9]	任胜兵，廖湘荡. 基于代价敏感支持向量机的软件缺陷预测研究[J]. 计算机工程与科学, 2018, 40(10): 1787-1795.
[10]	廖淑娇1,2，朱清新1，梁锐1. 测试代价受限下数据的属性和粒度选择方法[J]. 计算机工程与科学, 2018, 40(08): 1468-1474.
[11]	陈诗军1，王慧强2，陈大伟1，刘秀兵2,胡海婧2. 基于改进禁忌搜索的基站布局优化算法[J]. 计算机工程与科学, 2018, 40(02): 341-347.
[12]	谢小军1,2,俞春强3,王博1,何弦1,徐章艳1,2. 基于免疫量子粒子群优化的测试代价敏感属性约简算法[J]. 计算机工程与科学, 2017, 39(07): 1371-1378.
[13]	潘志辉，杨丹，张小洪，徐玲. 基于代价敏感神经网络的警告分类研究[J]. 计算机工程与科学, 2017, 39(06): 1097-1103.
[14]	张元鸣，陈苗，陆佳炜，徐俊，肖刚. 基于MapReduce的Bagging决策树优化算法[J]. 计算机工程与科学, 2017, 39(05): 841-848.
[15]	黄慧萍，肖世德，孟祥印. 基于攻防博弈的SCADA系统信息安全评估方法[J]. 计算机工程与科学, 2017, 39(05): 877-884.