決策樹(shù)技術(shù)研究綜述

李泓波　白勁波　楊高明　黃少偉

摘要：決策樹(shù)是一種重要的數(shù)據(jù)挖掘技術(shù)，廣泛應(yīng)用于電子商務(wù)、醫(yī)學(xué)、天文學(xué)和決策分析等多個(gè)領(lǐng)域。針對(duì)決策樹(shù)技術(shù)研究越來(lái)越受到重視的現(xiàn)實(shí)情況，通過(guò)介紹決策樹(shù)技術(shù)相關(guān)概念、理論及其發(fā)展過(guò)程，闡述決策樹(shù)技術(shù)的國(guó)內(nèi)外研究現(xiàn)狀，指出決策樹(shù)技術(shù)面臨的困難和挑戰(zhàn)，并展望其研究方向。

關(guān)鍵詞：決策樹(shù)；數(shù)據(jù)挖掘；現(xiàn)狀；研究方向

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）24-0001-04

Review on Decision Tree Technology Research

LI Hong-bo1， BAI Jin-bo2*， YANG Gao-ming3， HUANG Shao-wei1

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

Abstract： Decision tree is an important data mining technology， widely used in electronic commerce， medicine， astronomy， and decision analysis， and other fields. Aiming at the reality that the decision tree technology is paid more and more attention， this article points out the difficulties and challenges that the decision tree technology is facing， and prospects the research orientations by introducing the related concept， theory and its development process， elaborating its research status at home and abroad.

Keywords： decision tree； data mining； status； research orientation

1研究現(xiàn)狀

決策樹(shù)是一種重要的數(shù)據(jù)挖掘技術(shù)，常用于分類(lèi)預(yù)測(cè)以及規(guī)則提取等諸多領(lǐng)域[1-8]。決策樹(shù)采用貪婪策略，通過(guò)遞歸方式自頂向下進(jìn)行構(gòu)造。從發(fā)展脈絡(luò)上看，目前豐富的決策樹(shù)算法均起源于Hunt，Marin和Stone在1966年提出的單概念學(xué)習(xí)系統(tǒng)[9]。

1979年，Quinlan 提出ID3算法，并于1983年和1986年對(duì)其進(jìn)行進(jìn)一步的完善和發(fā)展。通過(guò)不懈的努力，Quinlan不但使ID3成為經(jīng)典的決策樹(shù)算法，還通過(guò)開(kāi)辦公司的方式使之成功走向應(yīng)用。1986年，Schlimmer 和Fisher 在ID3的基礎(chǔ)上，通過(guò)創(chuàng)建緩沖區(qū)，提出可伸縮的遞增式?jīng)Q策樹(shù)算法ID4。1988年，Utgoff 在ID4基礎(chǔ)上又提出效率更高的ID5算法。1993年，Quinlan 提出C4.5算法，突破了ID3算法只能處理布爾函數(shù)樣例的束縛。

為進(jìn)一步提高縮效率，研究者在ID4的基礎(chǔ)上又提出了一批可伸縮的決策樹(shù)算法，代表性的有SLIQ、SPRINT、RainForest、BOAT算法。目前來(lái)看，綜合指標(biāo)最佳的算法是BOAT，不但可伸縮而且效率更高（僅需掃描訓(xùn)練樣例集兩遍），并且是增量式學(xué)習(xí)算法[10]。

目前對(duì)決策樹(shù)技術(shù)的研究主要集中在已下幾個(gè)方面[11]：1）與其他技術(shù)相結(jié)合，如與神經(jīng)網(wǎng)絡(luò)[12-13]、模糊集[14-15]、遺傳算法及遺傳編程 [16-20]、多智能體[21-23]等原理和技術(shù)相結(jié)合；2）尋找可視化的交互式?jīng)Q策樹(shù)構(gòu)造方法[24]；3）尋找更好的剪枝算法[25]；4）尋找訓(xùn)練樣本集、檢驗(yàn)樣本集特性與生成樹(shù)特性之間的聯(lián)系[26-27]；5）包括半監(jiān)督學(xué)習(xí)在內(nèi)的非確定環(huán)境下的決策樹(shù)研究[28]；6）時(shí)間復(fù)雜度與分類(lèi)準(zhǔn)確性的折衷研究[29]。

相對(duì)而言，國(guó)內(nèi)對(duì)決策樹(shù)技術(shù)的研究尚不夠活躍，但值得關(guān)注的是朱鳴和陳文偉提出的決策規(guī)則樹(shù)方法——IBLE方法。IBLE方法采用信道容量作為衡量樣例的目標(biāo)屬性的標(biāo)準(zhǔn)，是一個(gè)不依賴正、反例比例的量。而且，該方法迥異ID3算法的一個(gè)重要區(qū)別是每次遴選一組相對(duì)重要的屬性，依其建立的規(guī)則作為決策樹(shù)的非葉子結(jié)點(diǎn)，更富有效率并更準(zhǔn)確 [30]。

2 決策樹(shù)技術(shù)概覽

由ID3、ID4.5等算法生成的決策樹(shù)是一種類(lèi)似二叉樹(shù)和多叉樹(shù)的樹(shù)形結(jié)構(gòu)。決策樹(shù)中的非葉子結(jié)點(diǎn)代表一個(gè)目標(biāo)屬性，每個(gè)葉子結(jié)點(diǎn)表示一個(gè)分類(lèi)，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的所有結(jié)點(diǎn)表示一個(gè)分類(lèi)規(guī)則。

2.1 決策樹(shù)與歸納學(xué)習(xí)

決策樹(shù)的本質(zhì)是歸納學(xué)習(xí)，是一種從部分?jǐn)?shù)據(jù)中歸納出整體數(shù)據(jù)特征完備描述的技術(shù)。歸納學(xué)習(xí)是人類(lèi)知識(shí)增長(zhǎng)的一種重要方式。例如，看到烏鴉、喜鵲、黃鸝、燕子、大雁等鳥(niǎo)類(lèi)具備飛行的能力，在未對(duì)所有鳥(niǎo)類(lèi)都進(jìn)行觀察的情況下，歸納出以下的規(guī)則：鳥(niǎo)類(lèi)都具備飛行的能力。于是，按此規(guī)則可以進(jìn)一步預(yù)測(cè)云雀、百靈、鸚鵡都具備飛行的能力。雖然此規(guī)則未必適用所有鳥(niǎo)類(lèi)，如鴕鳥(niǎo)，但其基本是準(zhǔn)確的，準(zhǔn)確率可以達(dá)到百分之九十以上。決策樹(shù)的分類(lèi)預(yù)測(cè)能力，完全來(lái)自于它能夠從部分?jǐn)?shù)據(jù)歸納和概括出整體數(shù)據(jù)特征描述（決策樹(shù)技術(shù)通過(guò)測(cè)試和篩選訓(xùn)練樣本集合的屬性集合，并生成新的屬性子集的方式實(shí)現(xiàn)這種描述）的能力。

2.2決策樹(shù)應(yīng)用步驟

利用決策樹(shù)應(yīng)用大致可以分為以下四大步驟：

1）對(duì)訓(xùn)練樣本集進(jìn)行數(shù)據(jù)補(bǔ)齊、數(shù)據(jù)清洗、離散化、規(guī)范化等預(yù)處理；

2）使用ID3、ID4等具體算法，利用訓(xùn)練樣本集訓(xùn)練（構(gòu)建）一棵決策樹(shù)，并對(duì)決策樹(shù)進(jìn)行前剪枝或后剪枝處理。

3）對(duì)經(jīng)過(guò)訓(xùn)練的決策樹(shù)輸入檢驗(yàn)樣本集進(jìn)行檢驗(yàn)：如果對(duì)分類(lèi)結(jié)果不滿意，則轉(zhuǎn)（1）。

4）應(yīng)用訓(xùn)練好的決策樹(shù)對(duì)需要預(yù)測(cè)分類(lèi)的樣本進(jìn)行分類(lèi)。

2.3 決策樹(shù)的特點(diǎn)

目前存著許多分類(lèi)方法和技術(shù)，如貝葉斯信念網(wǎng)絡(luò)、BP網(wǎng)絡(luò)、支持向量機(jī)、關(guān)聯(lián)分類(lèi)、近鄰學(xué)習(xí)、粗糙集方法、模糊集方法等，決策樹(shù)之所以能夠如此流行并得到高度關(guān)注，一個(gè)重要原因是它具備一些區(qū)別于其他分類(lèi)方法的鮮明特點(diǎn)：

1）從理論上說(shuō)，決策樹(shù)技術(shù)可以處理任意高維的數(shù)據(jù)；

2）決策樹(shù)算法雖然簡(jiǎn)單，但比較高效；

3）決策樹(shù)技術(shù)具有較高的分類(lèi)預(yù)測(cè)準(zhǔn)確率；

4）在決策樹(shù)的構(gòu)造過(guò)程中，無(wú)需任何的先驗(yàn)知識(shí)，也無(wú)需以交互方式設(shè)定參數(shù)；

5）獲取的知識(shí)用樹(shù)形結(jié)構(gòu)表示，既直觀又易于理解。

2.4 ID3決策樹(shù)建立算法

在決策樹(shù)技術(shù)的發(fā)展歷程中，先后經(jīng)歷了從不可伸縮到可伸縮、布爾函數(shù)分類(lèi)預(yù)測(cè)到多值函數(shù)預(yù)測(cè)等階段，涌現(xiàn)了多個(gè)優(yōu)秀的算法。以下以經(jīng)典的ID3算法[31]說(shuō)明決策樹(shù)技術(shù)的基本原理。

輸入：ID3（Examples，Target_attribute，Attributes），Examples即訓(xùn)練樣例集，Target_attribute是決策樹(shù)要預(yù)測(cè)的目標(biāo)屬性，Attributes是除去目標(biāo)屬性之外供學(xué)習(xí)到的決策樹(shù)測(cè)試的屬性列表。

輸出：一棵能正確分類(lèi)給定Examples的決策樹(shù)Root。

1.創(chuàng)建樹(shù)的Root結(jié)點(diǎn)

2.如果Examples都為正例，那么返回label = + 的單結(jié)點(diǎn)樹(shù)Root

3.如果Examples都為反例，那么返回label = - 的單結(jié)點(diǎn)樹(shù)Root

4. 如果Attributes為空，那么返回單結(jié)點(diǎn)樹(shù)Root，label = Examples中最普遍的Target_attribute值

5.否則開(kāi)始

1） A ← Attributes中分類(lèi)Examples能力最好的屬性

2） Root的決策屬性 ← A

3） 對(duì)于A的每個(gè)可能值vi

（1） 在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試 A = vi

（2） 令Examplesvi為Examples中滿足A屬性值為vi的子集

（3） 如果Examplesvi為空

① 在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，結(jié)點(diǎn)的label = Examples中最普遍的Target_attribute值

② 否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3（Examplesvi，Target_attribute，Attributes - |A|）

6. 結(jié)束

7. 返回Root

在算法的（1）處所描述的分類(lèi)能力最好的屬性為具有最高信息增益的屬性。

2.5 熵與信息增益

1）信息熵

ID3算法認(rèn)為，對(duì)于一個(gè)擁有n個(gè)反例和p個(gè)正例的樣例集合S來(lái)說(shuō)，能對(duì)其正確分類(lèi)的決策樹(shù)的信息量為：

[I（p，n）=-pp+nlog2pp+n-np+nlog2np+n] （1）

若以屬性A作為當(dāng)前樣例集S的根，并設(shè)A有v個(gè)值v1，v2，…，vv，并將分S為對(duì)應(yīng)的v個(gè)子集S1，S2，…，Sv，且某子集Si中含有Pi個(gè)正例和Ni個(gè)反例，規(guī)定Si的信息熵為：

[E（Si）=-PiPi+Nilog2PiPi+Ni-NiPi+Nilog2NiPi+Ni] （2）

又規(guī)定以屬性A為根進(jìn)行分類(lèi)的信息熵為：

[E（A）=i=1vpi+niP+NE（Si）] （3）

2）信息增益

ID3中規(guī)定，信息增益最大的屬性A可評(píng)為分類(lèi)最好屬性，其定義式為：

[Gain（A）=I（p，n）-E（A）] （4）

綜合公式（1）～（ 4），可以推知在當(dāng)前樣例集下，屬性A的信息增益最大時(shí)，其信息熵E（A）最小。

2.6 決策樹(shù)建立舉例

本小節(jié)以2.5中介紹的ID3算法為例，基于表1中描述的元組為訓(xùn)練樣本集S，簡(jiǎn)述決策樹(shù)建立過(guò)程。

首先，計(jì)算對(duì)S中元組分類(lèi)所需的期望信息：

[I（p，n）=-914log2914-514log2514=0.940bits]

下一步，計(jì)算每個(gè)屬性的期望信息需求。例如元組根據(jù)age屬性進(jìn)行劃分，對(duì)S中的元組進(jìn)行分類(lèi)所需的期望信息為：

[E（age）=514×（-25log225-35log235）]

[+414×（-44log244-04log204）]

[+514×（-35log235-25log225）]

[=0.694bits]

因此，以屬性age進(jìn)行劃分的信息增益為

[Gain（age）=0.940-0.694=0.246bits]

類(lèi)似可求得

[Gain（income）=0.029bits]

[Gain（student）=0.151bits]

[Gain（credit_rating）=0.048bits]

由于age屬性具有最大的信息增益，所以被選作分裂屬性。根結(jié)點(diǎn)用age標(biāo)記，并對(duì)應(yīng)于它的每個(gè)屬性值長(zhǎng)出一個(gè)分枝。然后，元組據(jù)此劃分，如圖1所示。

圖1 按屬性age分類(lèi)產(chǎn)生的決策樹(shù)分枝

在每一個(gè)分枝所對(duì)應(yīng)的訓(xùn)練子集上，重復(fù)前述步驟，即可得到最終的決策樹(shù)。

3 未來(lái)研究方向

結(jié)合目前的研究 [9-10，30-33]，未來(lái)決策樹(shù)技術(shù)的研究應(yīng)該包括以下幾個(gè)方面。

1）基于量子免疫克隆算法的決策樹(shù)優(yōu)化。

決策樹(shù)本身的優(yōu)化需要面對(duì)以下理論問(wèn)題（洪家榮教授首次證明了這幾個(gè)問(wèn)題都是NP難問(wèn)題）：①最優(yōu)覆蓋問(wèn)題，即決策樹(shù)中葉子結(jié)點(diǎn)數(shù)目最少；②最簡(jiǎn)公式問(wèn)題，即保證決策樹(shù)的每個(gè)葉子深度最小；③最優(yōu)示例學(xué)習(xí)問(wèn)題，即決策樹(shù)葉子最少且每個(gè)葉子的深度最小[33]。對(duì)于決策樹(shù)的自身優(yōu)化，學(xué)術(shù)界已經(jīng)有了一些研究成果，提出了一些近似或啟發(fā)算法。但這些算法還存在一些不足，如易陷入局部最優(yōu)、時(shí)間成本高、分類(lèi)預(yù)測(cè)準(zhǔn)確率較低等。

由于量子計(jì)算所擁有的量子相干特性，可以有效避免一些啟發(fā)式算法陷于局部最優(yōu)，免疫算法易實(shí)現(xiàn)數(shù)據(jù)的分布式存儲(chǔ)，克隆算法具有強(qiáng)大的自適應(yīng)能力，因此，決策樹(shù)的優(yōu)化還應(yīng)結(jié)合量子計(jì)算、免疫算法、克隆算法等相關(guān)技術(shù)，以便實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ)。

2）基于IBLE方法和支持向量機(jī)相結(jié)合的決策規(guī)則樹(shù)研究。

IBLE方法具有實(shí)現(xiàn)簡(jiǎn)單，學(xué)習(xí)正確性較高，所得知識(shí)在表示和內(nèi)容上與專(zhuān)家知識(shí)有較高的一致性等優(yōu)點(diǎn)，但在處理小樣本的情況下性能較差。而支持向量機(jī)特別適于處理小樣本的情況，將二者相結(jié)合，可以期望會(huì)有更好的表現(xiàn)。

3）不確定環(huán)境下的決策樹(shù)研究。

不確定環(huán)境下的決策研究一直是一個(gè)熱點(diǎn)。但如何比較科學(xué)地確定決策閾值，目前還是一個(gè)鮮有人涉足的課題。

4）連續(xù)屬性值離散化問(wèn)題的研究。

由于決策樹(shù)技術(shù)要求屬性值為離散值，因此連續(xù)值在使用前需要進(jìn)行離散化處理。按慣常作法，一般將連續(xù)值離散為7個(gè)以內(nèi)的離散值。離散值的個(gè)數(shù)及其具體數(shù)值直接影響到?jīng)Q策樹(shù)的分類(lèi)質(zhì)量和效率，科學(xué)地取值以及科學(xué)地確定離散值數(shù)量，是一個(gè)值得深入研究的課題。

4 小結(jié)

本文介紹了決策樹(shù)技術(shù)及其發(fā)展過(guò)程，綜述了近幾年決策樹(shù)技術(shù)的國(guó)內(nèi)外研究現(xiàn)狀，展望了進(jìn)一步的研究方向。

參考文獻(xiàn)：

[1] Liang Chun-quan， Zhang Yang， Shi Peng， et al. Learning accurate very fast decision trees from uncertain data streams. International Journal of Systems Science， 2015，46（16）：3032-3050

[2] Li Pei-pei， Wu Xin-dong， Hu Xuegang， et al. Learning concept-drifting data streams with random ensemble decision trees. 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. Biological conservation， 2015，189（SI）：33-38.

[4] Dhurandhar Amit. Bounds on the moments for an ensemble of random decision trees. 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. 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. 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. Plos One， 2013，8（12）： 82799.

[8] Lupascu Carmen Alina； Tegolo Domenico； Trucco Emanuele. Accurate estimation of retinal vessel width using bagged decision trees and an extended multiresolution Hermite model.Medical Image Analysis， 2013，17（8）：1164-1180.

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

[10] 韓家煒， Kam ber. M. 數(shù)據(jù)挖掘：概念與技術(shù)[M].2版. 機(jī)械工業(yè)出版社， 2007

[11] John Durkin， 蔡競(jìng)峰， 蔡自興. 決策樹(shù)及其當(dāng)前研究方向[J]. 控制工程，2005，12（1）：15-21.

[12] Boz o. Extracting decision trees from trained neural networks. Edmonton， Alberta， Cananda： Proc of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2002.

[13] Sethi L. Entropy nets： from decision trees to neural networks. Proc of IEEE， 1990， 78（10）：1605-1613.

[14] Olaru C， wehenkel L. A complete fuzzy decision tree technique. Fuzzy Sets and Systems， 2003， 138（2）：221-254.

[15] Dong M， Kothari R. Look-ahead based fuzzy decision tree induction. IEEE Transactions on Fuzzy Systems， 2002，9（3）：461-468.

[16] Cantu-Paz E， Kamath C. Inducing oblique decision trees with evolutionary Algorithms. IEEE Transactions on Evolutionary Computation， 2003，7（1）：54-68.

[17] Papagelis A， Kalles D. Breeding decision trees using evolutionary techniques. USA： Proceedings of ICML' 01， USA， 2001.

[18] Papagelis A， Kalles D. GA tree： genetically evolved decision trees. USA： Proceedings of ICTAI'00， 2000.

[19] Tur G， Guvenir H A. Decision tree induction using genetic programming. Ankara， Turkish： Proceedings of the Fifth Turkish Symposium on Artificial Intelligence and Neural Networks， 1996.

[20] Eggermont J. Evolving fuzzy decision trees with genetic programming and clustering. Milan， Italy： Proceedings of the 4th European Conference on Genetic Programming， 2001.

[21] Stone P， Veloso M. Using decision tree confidence factors for multiagent control. Minnesota， USA： Proceedings of the 2nd International Conference on Autonomous Robots， 2000.

[22] Stone P， Veloso M. A layered approach to learning client behaviors in the RoboCup soccer server. Applied Artificial Intelligence（AAI）， 1998， 12（2-3）： 165-187.

[23] Stone P， Veloso M. Multiagent system： a survey from a machine learning perspective. Autonomous Robots， 2000， 8（3）： 345-383.

[24] Ankerst M， Elsen C， Ester M， et al. Visual classification： an interactive approach to decision tree construction. San Diego： In Proceedings of International Conference on Knowledge Discovery and Data Mining， 1999.

[25] Fournier D， Cremilleux B. A quality index for decision tree pruning. Knowledge-based Systems， 2002，15（1）：37-43.

[26] Sebban M， Nock R， Chauchat J H， et al. Impact of learning set quality and size on decision tree performances. IJCSS，2000，1（1）：85-105.

[27] Oates T， Jensen D. The effects of training set size on decision tree complexity. Nashville， Tennessee： Proc of the 14th International Conference on Machine Learning，1997.

[28] Elouedi Z， Mellouli K， Smets Ph. Decision Trees using the belief function theory. Madrid， Spain： Proceedings of the Eighth International Conference IPMU， 2000.

[29] Yildiz O T， Alpaydin E. Omnivariate decision trees. IEEE Transactions on Neural Networks， 2001， 12（6）：1539-1546.

[30] 陳文偉. 數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘教程[M]. 清華大學(xué)出版社，2006.

[31] Tom M. Mitchell. 機(jī)器學(xué)習(xí)[M]. 機(jī)械工業(yè)出版社，2003.

[32] 陳文偉， 廖建文. 決策支持系統(tǒng)及其開(kāi)發(fā)[M].3版.清華大學(xué)出版社，2008.

[33] 朱明. 數(shù)據(jù)挖掘[M].2版.中國(guó)科學(xué)技術(shù)大學(xué)出版社，2008.