決策樹剪枝研究

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

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

摘 ?要： 決策樹技術是一種重要的機器學習技術，現已廣泛應用于工業、商業、金融、醫療衛生等多個學科和領域，并成為學術熱點問題。在眾多的應用中，存在由于使用剪枝算法簡化決策樹而導致系統性能下降的情況。針對濫用剪枝問題，通過對決策樹技術的研究，闡述剪枝與過擬合現象的關系，并從奧卡姆剃刀原理、沒有免費午餐原理、人類本能、孤立點分析等方面對剪枝的合理性和必要性展開討論，提出了慎用剪枝的主張以及免剪枝措施。

關鍵詞： 決策樹; 機器學習; 過擬合; 剪枝; 免剪枝措施

中圖分類號：TP391 ? ? ? ? ?文獻標志碼：A ? ? 文章編號：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 引言

決策樹是一種重要的非參數機器學習技術，其本質為歸納學習，主要用于分類、預測和規則獲取等[1-9]，現已廣泛應用于工業、商業、金融、醫療衛生等多個學科和領域[10-13]。一般認為，決策樹應用大致分為數據預處理、決策樹訓練和剪枝、決策樹檢驗和應用四大步驟[9]。從目前研究看，在眾多實際應用中都采用了剪枝算法對決策樹進行簡化處理。然而，在有些情況下，剪枝處理會導致決策樹性能的下降。

1 過擬合現象與剪枝

1.1 過擬合

在訓練決策樹的過程中，可能會現一種稱為過擬合（也稱為過渡擬合或過適應）的現象。以下簡述過擬合的相關概念，并通過介紹這些概念的引入闡釋過擬合現象。

⑴ 訓練誤差：是指在訓練樣本集上決策樹誤分類所占的比例。

⑵ 泛化誤差：經過訓練樣本集訓練過的決策樹在進行分類預測樣本集上的期望誤差。

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

⑷ 過擬合：如果訓練誤差低而泛化誤差高，則稱為過擬合。出現過擬合現象主要有兩個原因：一是訓練樣本數量少，二是噪聲的存在。

1.2 剪枝

⑴ 剪枝的作用

人們發現，在有些時候，一棵經過訓練的決策樹過于“繁茂”，知識過多，或者說得到的規則集合過大。經過剪枝，可以得到一棵相對簡潔的決策樹，較少的規則使得在進行分類預測時，決策樹效率更高。同時，剪枝也可以減少過擬合現象的發生。

⑵ 先剪枝

所謂的先剪枝是指在決策樹的構造過程中，當滿足設定條件時，以當前分枝的樣例子集中出現次數最多的類別值作為當前分枝的節點標記名，而提前停止決策樹的構造。

⑶ 后剪枝

所謂的后剪枝是指在決策構造完成之后，刪去某些滿足某種條件的結點及其子孫結點和分枝，并以該結點分枝的樣例子集中出現次數最多的類別值作為當前分枝的節點標記名。

圖1為一棵剪枝前的決策樹，圖2為對前圖所示決策樹剪枝后的情形。

2 決策樹剪枝討論

一般說來，經訓練獲得一棵決策樹后，考慮到簡潔和效率因素，并為避免過擬合現象，往往要對其進行剪枝。但是，剪枝是否總是合理或必要則是個問題。

2.1 奧卡姆剃刀原理與剪枝

奧卡姆剃刀原理由14世紀哲學家奧卡姆提出，如今已經廣泛應用于哲學、管理學、社會科學、自然科學等多個領域，取得了輝煌成就。奧卡姆剃刀原理的哲學內涵非常豐富，其中的“思維經濟原則”后來演變為“如無必要，勿增實體”，也稱“簡單有效原則”。依據這一原則，如果一個問題存在多個解決方案，則應該選取前提條件最少且最簡單的那一個。因此，決策樹剪枝就是該原理的一次應用——盡量去除冗余“實體”，只保留必要“實體”。在很多情況下，一棵經過剪枝的決策樹，不但具有更加清晰的知識表示，而且更富執行效率。

然而，從目前的研究現狀看，存在濫用剪枝并導致決策樹分類性能下降的現象[14]。從本質上說，剪枝濫用現象來源于人們對奧卡姆剃刀原理的片面理解，一味強調“勿增實體”，而忽視“如非必要”這一前提條件。剪枝之所以在實踐中起作用，僅僅是因為這恰好與它們所要解決的問題相“匹配”[14]。

2.2 沒有免費午餐原理與剪枝

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

2.3 人類本能與剪枝

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

2.4 孤立點與剪枝

決策樹剪枝既能提高效率又能在很大程度上避免過擬合現象的發生，但也存在著一個很大的弊端，即將訓練樣例集中的孤立點等同于噪聲一樣處理，從而會使得與孤立點相關的規則（知識）被屏蔽掉，而這些規則往往具有重要價值。事實上，孤立點在科學研究中往往具有特殊的作用，孤立點檢測已經廣泛應用于網絡入侵檢測、電信和信用卡欺騙、氣象預報、客戶分類、RFID數據流及傳感器數據處理等諸多領域[16]。屏蔽掉孤立點相關規則，雖然會使得決策樹具有較強的泛化能力，但同時也可能失去重要規則（知識）。

3 免剪枝措施

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

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

⑴ 加強數據預處理。在訓練決策樹之前，加強對訓練樣例集進行數據清洗、數據補齊、離散化，以及規范化等處理，盡量平抑噪聲。

⑵ 擴大訓練樣例集規模。因決策樹本質上為歸納學習方法，而噪聲數據相對于正常數據畢竟所占比例較低，因此適當擴大訓練樣例集規模可以有效減少噪聲的影響。

⑶ 縮小測試屬性集合規模。在實際應用中，除分類屬性外，存在測試屬性強相關的情況。對測試屬性集合進行盡可能的約簡，去除強相關屬性，可以有效縮小決策樹規模和減少生成規則的維度。

4 結束語

本文通過闡釋剪枝與過擬合現象的關系，從奧卡姆剃刀原理前提條件被忽視、沒有免費午餐原理所揭示的獲得與付出的共生性、人類追求簡單性的本能，以及孤立點規則被屏蔽等多個方面對決策樹剪枝的合理性和必要性展開了討論，提出了慎用剪枝的主張以及免剪枝措施。

參考文獻（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.數據挖掘：概念與技術（第2版）[M].機械

工業出版社，2007.

[10] 梁循.數據挖掘算法與應用[M].北京大學出版社，2006.

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

書館中的應用[J].計算機時代，2014.4：30-33

[12] 陳玉珍.基于決策樹的高職學生創業傾向分析[J].計算機時

代，2010.3：31-35

[13] 張立敏，晉新敏.基于決策樹的心理危機預警模型研究[J].計

算機時代，2013.1：3-5

[14] Richard O. Duda， David G. Stork. 模式分類[M]. 北京-機

械工業出版社， 2003

[15] 鄭偉，馬楠.一種改進的決策樹剪枝算法[J].計算機與數字工

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

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

軟件學報，2006.17（6）：1009-1016