決策樹(shù)剪枝研究

李泓波+彭三城+白勁波+楊高明+黃少偉

DOI：10.16644/j.cnki.cn33-1094/tp.2016.02.001

摘 ?要： 決策樹(shù)技術(shù)是一種重要的機(jī)器學(xué)習(xí)技術(shù)，現(xiàn)已廣泛應(yīng)用于工業(yè)、商業(yè)、金融、醫(yī)療衛(wèi)生等多個(gè)學(xué)科和領(lǐng)域，并成為學(xué)術(shù)熱點(diǎn)問(wèn)題。在眾多的應(yīng)用中，存在由于使用剪枝算法簡(jiǎn)化決策樹(shù)而導(dǎo)致系統(tǒng)性能下降的情況。針對(duì)濫用剪枝問(wèn)題，通過(guò)對(duì)決策樹(shù)技術(shù)的研究，闡述剪枝與過(guò)擬合現(xiàn)象的關(guān)系，并從奧卡姆剃刀原理、沒(méi)有免費(fèi)午餐原理、人類(lèi)本能、孤立點(diǎn)分析等方面對(duì)剪枝的合理性和必要性展開(kāi)討論，提出了慎用剪枝的主張以及免剪枝措施。

關(guān)鍵詞： 決策樹(shù); 機(jī)器學(xué)習(xí); 過(guò)擬合; 剪枝; 免剪枝措施

中圖分類(lèi)號(hào)：TP391 ? ? ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? 文章編號(hào)：1006-8228（2016）02-01-03

Study on decision tree pruning

Li Hongbo1， Peng Sancheng1， Bai Jinbo2， Yang Gaoming3， Huang Shaowei1

（1. School of Computer/School of Software， Zhaoqing University， Zhaoqing， Guangdong 526161， China; 2. College of Economics & Management， Zhaoqing University; 3. College of Computer Science and Engineering， Anhui University of Science & Technology）

Abstract： Decision tree technology is an important machine learning technology， has been widely used in industrial， commercial， financial， medical and health care， and other disciplines and fields， and become the academic hot issue. There are decision tree performance degradation phenomena existing in many applications because of using of pruning algorithms to simplify the decision tree. In view of the problem of abusing pruning， through a brief introduction to decision tree technology， explaining the relationship between pruning and over fitting phenomenon， and discussing on the rationality and necessity of pruning from several aspect， such as Occam's razor theorem， no free lunch theorem， the human instinct， outlier analysis， etc.， the careful pruning claims and avoiding pruning measures are put forward.

Key words： decision tree; machine learning; over fitting; pruning; avoiding pruning measure

0 引言

決策樹(shù)是一種重要的非參數(shù)機(jī)器學(xué)習(xí)技術(shù)，其本質(zhì)為歸納學(xué)習(xí)，主要用于分類(lèi)、預(yù)測(cè)和規(guī)則獲取等[1-9]，現(xiàn)已廣泛應(yīng)用于工業(yè)、商業(yè)、金融、醫(yī)療衛(wèi)生等多個(gè)學(xué)科和領(lǐng)域[10-13]。一般認(rèn)為，決策樹(shù)應(yīng)用大致分為數(shù)據(jù)預(yù)處理、決策樹(shù)訓(xùn)練和剪枝、決策樹(shù)檢驗(yàn)和應(yīng)用四大步驟[9]。從目前研究看，在眾多實(shí)際應(yīng)用中都采用了剪枝算法對(duì)決策樹(shù)進(jìn)行簡(jiǎn)化處理。然而，在有些情況下，剪枝處理會(huì)導(dǎo)致決策樹(shù)性能的下降。

1 過(guò)擬合現(xiàn)象與剪枝

1.1 過(guò)擬合

在訓(xùn)練決策樹(shù)的過(guò)程中，可能會(huì)現(xiàn)一種稱為過(guò)擬合（也稱為過(guò)渡擬合或過(guò)適應(yīng)）的現(xiàn)象。以下簡(jiǎn)述過(guò)擬合的相關(guān)概念，并通過(guò)介紹這些概念的引入闡釋過(guò)擬合現(xiàn)象。

⑴ 訓(xùn)練誤差：是指在訓(xùn)練樣本集上決策樹(shù)誤分類(lèi)所占的比例。

⑵ 泛化誤差：經(jīng)過(guò)訓(xùn)練樣本集訓(xùn)練過(guò)的決策樹(shù)在進(jìn)行分類(lèi)預(yù)測(cè)樣本集上的期望誤差。

⑶ 噪聲：對(duì)于噪聲的定義尚未統(tǒng)一，為對(duì)其有多角度的觀察和更加開(kāi)放的目光進(jìn)行審視，下面給出兩個(gè)經(jīng)典的定義。一個(gè)定義來(lái)自著名模式識(shí)別專家Duda;另一個(gè)來(lái)自決策樹(shù)技術(shù)專家Quinlan。Duda給出的定義是：噪聲是一個(gè)非常廣義的概念，如果一個(gè)感知到的模式屬性（值）并非來(lái)自真正模式的模型，而是來(lái)自環(huán)境中的某種隨機(jī)性或者是傳感器的性能缺憾，那么就是噪聲[14]。Quinlan的定義是：訓(xùn)練樣本中的錯(cuò)誤就是噪聲;它包含兩方面，一是屬性值取錯(cuò)，二是分類(lèi)類(lèi)別取錯(cuò)。概括地說(shuō)，Duda和Quinlan都認(rèn)為，噪聲產(chǎn)生的原因是訓(xùn)練樣本集合存在錯(cuò)誤數(shù)值，這些數(shù)值跳出了其正常的取值范圍。

⑷ 過(guò)擬合：如果訓(xùn)練誤差低而泛化誤差高，則稱為過(guò)擬合。出現(xiàn)過(guò)擬合現(xiàn)象主要有兩個(gè)原因：一是訓(xùn)練樣本數(shù)量少，二是噪聲的存在。

1.2 剪枝

⑴ 剪枝的作用

人們發(fā)現(xiàn)，在有些時(shí)候，一棵經(jīng)過(guò)訓(xùn)練的決策樹(shù)過(guò)于“繁茂”，知識(shí)過(guò)多，或者說(shuō)得到的規(guī)則集合過(guò)大。經(jīng)過(guò)剪枝，可以得到一棵相對(duì)簡(jiǎn)潔的決策樹(shù)，較少的規(guī)則使得在進(jìn)行分類(lèi)預(yù)測(cè)時(shí)，決策樹(shù)效率更高。同時(shí)，剪枝也可以減少過(guò)擬合現(xiàn)象的發(fā)生。

⑵ 先剪枝

所謂的先剪枝是指在決策樹(shù)的構(gòu)造過(guò)程中，當(dāng)滿足設(shè)定條件時(shí)，以當(dāng)前分枝的樣例子集中出現(xiàn)次數(shù)最多的類(lèi)別值作為當(dāng)前分枝的節(jié)點(diǎn)標(biāo)記名，而提前停止決策樹(shù)的構(gòu)造。

⑶ 后剪枝

所謂的后剪枝是指在決策構(gòu)造完成之后，刪去某些滿足某種條件的結(jié)點(diǎn)及其子孫結(jié)點(diǎn)和分枝，并以該結(jié)點(diǎn)分枝的樣例子集中出現(xiàn)次數(shù)最多的類(lèi)別值作為當(dāng)前分枝的節(jié)點(diǎn)標(biāo)記名。

圖1為一棵剪枝前的決策樹(shù)，圖2為對(duì)前圖所示決策樹(shù)剪枝后的情形。

2 決策樹(shù)剪枝討論

一般說(shuō)來(lái)，經(jīng)訓(xùn)練獲得一棵決策樹(shù)后，考慮到簡(jiǎn)潔和效率因素，并為避免過(guò)擬合現(xiàn)象，往往要對(duì)其進(jìn)行剪枝。但是，剪枝是否總是合理或必要?jiǎng)t是個(gè)問(wèn)題。

2.1 奧卡姆剃刀原理與剪枝

奧卡姆剃刀原理由14世紀(jì)哲學(xué)家?jiàn)W卡姆提出，如今已經(jīng)廣泛應(yīng)用于哲學(xué)、管理學(xué)、社會(huì)科學(xué)、自然科學(xué)等多個(gè)領(lǐng)域，取得了輝煌成就。奧卡姆剃刀原理的哲學(xué)內(nèi)涵非常豐富，其中的“思維經(jīng)濟(jì)原則”后來(lái)演變?yōu)椤叭鐭o(wú)必要，勿增實(shí)體”，也稱“簡(jiǎn)單有效原則”。依據(jù)這一原則，如果一個(gè)問(wèn)題存在多個(gè)解決方案，則應(yīng)該選取前提條件最少且最簡(jiǎn)單的那一個(gè)。因此，決策樹(shù)剪枝就是該原理的一次應(yīng)用——盡量去除冗余“實(shí)體”，只保留必要“實(shí)體”。在很多情況下，一棵經(jīng)過(guò)剪枝的決策樹(shù)，不但具有更加清晰的知識(shí)表示，而且更富執(zhí)行效率。

然而，從目前的研究現(xiàn)狀看，存在濫用剪枝并導(dǎo)致決策樹(shù)分類(lèi)性能下降的現(xiàn)象[14]。從本質(zhì)上說(shuō)，剪枝濫用現(xiàn)象來(lái)源于人們對(duì)奧卡姆剃刀原理的片面理解，一味強(qiáng)調(diào)“勿增實(shí)體”，而忽視“如非必要”這一前提條件。剪枝之所以在實(shí)踐中起作用，僅僅是因?yàn)檫@恰好與它們所要解決的問(wèn)題相“匹配”[14]。

2.2 沒(méi)有免費(fèi)午餐原理與剪枝

沒(méi)有免費(fèi)午餐原理揭示了獲得與付出的共生性。許多剪枝算法雖然能提高效率或避免過(guò)擬合現(xiàn)象的發(fā)生，但同時(shí)也要付出很大的代價(jià)。例如，先剪枝算法由于前瞻性不足而過(guò)早停止生長(zhǎng)，導(dǎo)致視野效應(yīng)，難以確定被剪結(jié)點(diǎn)的子結(jié)點(diǎn)對(duì)分類(lèi)的貢獻(xiàn)程度，往往不能得到比較優(yōu)化的決策樹(shù)[15]。再如，后剪枝算法雖然可避免先剪枝算法帶來(lái)的弊端，但或者具有較高的時(shí)間復(fù)雜度，或者需要額外的檢驗(yàn)樣例集，或者不能得到較優(yōu)的決策樹(shù)。因此，經(jīng)過(guò)剪枝的決策樹(shù)也許更易理解、更富效率，但其性能卻未必最佳。正如Duda所指出的那樣：不存在與“語(yǔ)境無(wú)關(guān)”（context-free）或與“應(yīng)用無(wú)關(guān)”（usage-free）的任何理由來(lái)認(rèn)定某種學(xué)習(xí)或分類(lèi)算法比另外一種更好[14]。

2.3 人類(lèi)本能與剪枝

既然剪枝后的決策樹(shù)不一定擁有最佳性能，那么是什么原因使我們更偏愛(ài)剪枝后的決策樹(shù)呢？一種解釋是：由于在強(qiáng)大的自然選擇作用下，為了生存，人類(lèi)更喜歡理解簡(jiǎn)單、耗時(shí)最少的分類(lèi)器[14]。在人類(lèi)社會(huì)早期，自然條件十分惡劣，為保證在種間和種內(nèi)競(jìng)爭(zhēng)中保持優(yōu)勢(shì)并成為勝出者，人類(lèi)更喜歡高效率的工具。經(jīng)過(guò)幾十萬(wàn)年的沉淀，這種認(rèn)知已經(jīng)深深印入了人類(lèi)集體意識(shí)中，選擇簡(jiǎn)單、高效的工具已經(jīng)變成了人類(lèi)的一種本能。因此，對(duì)決策樹(shù)的剪枝行為也許恰恰是人類(lèi)本能的反映。

2.4 孤立點(diǎn)與剪枝

決策樹(shù)剪枝既能提高效率又能在很大程度上避免過(guò)擬合現(xiàn)象的發(fā)生，但也存在著一個(gè)很大的弊端，即將訓(xùn)練樣例集中的孤立點(diǎn)等同于噪聲一樣處理，從而會(huì)使得與孤立點(diǎn)相關(guān)的規(guī)則（知識(shí)）被屏蔽掉，而這些規(guī)則往往具有重要價(jià)值。事實(shí)上，孤立點(diǎn)在科學(xué)研究中往往具有特殊的作用，孤立點(diǎn)檢測(cè)已經(jīng)廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測(cè)、電信和信用卡欺騙、氣象預(yù)報(bào)、客戶分類(lèi)、RFID數(shù)據(jù)流及傳感器數(shù)據(jù)處理等諸多領(lǐng)域[16]。屏蔽掉孤立點(diǎn)相關(guān)規(guī)則，雖然會(huì)使得決策樹(shù)具有較強(qiáng)的泛化能力，但同時(shí)也可能失去重要規(guī)則（知識(shí)）。

3 免剪枝措施

雖然決策樹(shù)剪枝可以提高效率，避免過(guò)擬合現(xiàn)象，但由于剪枝行為可能只是迎合了人類(lèi)本能，或忽視了奧卡姆剃刀原理的前提，并需要額外代價(jià)，有可能造成決策性能下降，以及存在丟失重要規(guī)則的可能，因此本文主張慎用剪枝，在有些情況下不用剪枝。

為避免剪枝，建議采取以下措施。

⑴ 加強(qiáng)數(shù)據(jù)預(yù)處理。在訓(xùn)練決策樹(shù)之前，加強(qiáng)對(duì)訓(xùn)練樣例集進(jìn)行數(shù)據(jù)清洗、數(shù)據(jù)補(bǔ)齊、離散化，以及規(guī)范化等處理，盡量平抑噪聲。

⑵ 擴(kuò)大訓(xùn)練樣例集規(guī)模。因決策樹(shù)本質(zhì)上為歸納學(xué)習(xí)方法，而噪聲數(shù)據(jù)相對(duì)于正常數(shù)據(jù)畢竟所占比例較低，因此適當(dāng)擴(kuò)大訓(xùn)練樣例集規(guī)?？梢杂行p少噪聲的影響。

⑶ 縮小測(cè)試屬性集合規(guī)模。在實(shí)際應(yīng)用中，除分類(lèi)屬性外，存在測(cè)試屬性強(qiáng)相關(guān)的情況。對(duì)測(cè)試屬性集合進(jìn)行盡可能的約簡(jiǎn)，去除強(qiáng)相關(guān)屬性，可以有效縮小決策樹(shù)規(guī)模和減少生成規(guī)則的維度。

4 結(jié)束語(yǔ)

本文通過(guò)闡釋剪枝與過(guò)擬合現(xiàn)象的關(guān)系，從奧卡姆剃刀原理前提條件被忽視、沒(méi)有免費(fèi)午餐原理所揭示的獲得與付出的共生性、人類(lèi)追求簡(jiǎn)單性的本能，以及孤立點(diǎn)規(guī)則被屏蔽等多個(gè)方面對(duì)決策樹(shù)剪枝的合理性和必要性展開(kāi)了討論，提出了慎用剪枝的主張以及免剪枝措施。

參考文獻(xiàn)（References）：

[1] Liang Chunquan， Zhang Yang， Shi Peng， et al. Learning

accurate very fast decision trees from uncertain data streams[J]. International Journal of Systems Science，2015.46（16）：3032-3050

[2] Li Peipei， Wu Xindong， Hu Xuegang， et al. Learning

concept-drifting data streams with random ensemble decision trees[J]. Neurocomputing，2015.166：68-83

[3] Kretser Heidi E， Wong Ramacandra， Roberton Scott， et al.

Mobile decision-tree tool technology as a means to detect wildlife crimes and build enforcement networks[J]. Biological Conservation，2015.189（SI）：33-38

[4] Dhurandhar Amit. Bounds on the moments for an

ensemble of random decision trees[J]. Knowledge and Information Systems，2015.44（2）：279-298

[5] Czajkowski Marcin， Grzes Marek， Kretowski Marek.

Multi-test decision tree and its application to microarray data classification[J]. Artificial Intelligence in Medicine，2014.61（1）：35-44

[6] Mehenni Tahar， Moussaoui Abdelouahab. Data mining

from multiple heterogeneous relational databases using decision tree classification[J].Pattern Recognition Letters，2014.40：136-136

[7] Tuerkcan Silvan， Masson Jean-Baptiste. Bayesian Decision

Tree for the Classification of the Mode of Motion in Single-Molecule Trajectories[J]. Plos One，2013.8（12）：e82799

[8] Lupascu Carmen Alina; Tegolo Domenico; Trucco

Emanuele. Accurate estimation of retinal vessel width using bagged decision trees and an extended multiresolution Hermite model[J]. Medical Image Analysis，2013.17（8）：1164-1180

[9] 韓家煒，Kam ber. M.數(shù)據(jù)挖掘：概念與技術(shù)（第2版）[M].機(jī)械

工業(yè)出版社，2007.

[10] 梁循.數(shù)據(jù)挖掘算法與應(yīng)用[M].北京大學(xué)出版社，2006.

[11] 郭宇紅，王路寧，毛玉琪.SPSS Clementine決策樹(shù)建模在圖

書(shū)館中的應(yīng)用[J].計(jì)算機(jī)時(shí)代，2014.4：30-33

[12] 陳玉珍.基于決策樹(shù)的高職學(xué)生創(chuàng)業(yè)傾向分析[J].計(jì)算機(jī)時(shí)

代，2010.3：31-35

[13] 張立敏，晉新敏.基于決策樹(shù)的心理危機(jī)預(yù)警模型研究[J].計(jì)

算機(jī)時(shí)代，2013.1：3-5

[14] Richard O. Duda， David G. Stork. 模式分類(lèi)[M]. 北京-機(jī)

械工業(yè)出版社， 2003

[15] 鄭偉，馬楠.一種改進(jìn)的決策樹(shù)剪枝算法[J].計(jì)算機(jī)與數(shù)字工

程，2015.43（6）：960-966，971

[16] 孫煥良，鮑玉斌，于戈等.一種基于劃分的孤立點(diǎn)檢測(cè)算法[J].

軟件學(xué)報(bào)，2006.17（6）：1009-1016