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

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：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ù)據(jù)挖掘技術(shù)，常用于分類預(yù)測以及規(guī)則提取等諸多領(lǐng)域[1-8]。決策樹采用貪婪策略，通過遞歸方式自頂向下進行構(gòu)造。從發(fā)展脈絡(luò)上看，目前豐富的決策樹算法均起源于Hunt，Marin和Stone在1966年提出的單概念學(xué)習(xí)系統(tǒng)[9]。

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

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

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

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

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

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

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

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

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

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

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

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

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

4）應(yīng)用訓(xùn)練好的決策樹對需要預(yù)測分類的樣本進行分類。

2.3 決策樹的特點

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

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

2）決策樹算法雖然簡單，但比較高效；

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

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

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

2.4 ID3決策樹建立算法

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

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

輸出：一棵能正確分類給定Examples的決策樹Root。

1.創(chuàng)建樹的Root結(jié)點

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

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

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

5.否則開始

1） A ← Attributes中分類Examples能力最好的屬性

2） Root的決策屬性 ← A

3） 對于A的每個可能值vi

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

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

（3） 如果Examplesvi為空

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

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

6. 結(jié)束

7. 返回Root

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

2.5 熵與信息增益

1）信息熵

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

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

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

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

又規(guī)定以屬性A為根進行分類的信息熵為：

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

2）信息增益

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

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

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

2.6 決策樹建立舉例

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

首先，計算對S中元組分類所需的期望信息：

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

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

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

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

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

[=0.694bits]

因此，以屬性age進行劃分的信息增益為

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

類似可求得

[Gain（income）=0.029bits]

[Gain（student）=0.151bits]

[Gain（credit_rating）=0.048bits]

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

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

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

3 未來研究方向

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

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

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

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

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

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

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

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

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

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

4 小結(jié)

本文介紹了決策樹技術(shù)及其發(fā)展過程，綜述了近幾年決策樹技術(shù)的國內(nèi)外研究現(xià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版. 機械工業(yè)出版社， 2007

[11] John Durkin， 蔡競峰， 蔡自興. 決策樹及其當(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ù)倉庫與數(shù)據(jù)挖掘教程[M]. 清華大學(xué)出版社，2006.

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

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

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