決策樹方法的研究進展

曹 寧 高 瑩 徐根祺

（1.西京學(xué)院 工程技術(shù)系，陜西 西安710123；2.日立永濟電氣設(shè)備〈西安〉有限公司，陜西 西安710016）

1 數(shù)據(jù)挖掘的應(yīng)用背景

隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展及數(shù)據(jù)庫管理系統(tǒng)的推廣應(yīng)用，存儲在數(shù)據(jù)庫中的數(shù)據(jù)量急劇增大， 大量數(shù)據(jù)背后必定蘊藏著許多信息，如何從數(shù)據(jù)庫中抽取出有用信息逐漸成為商業(yè)界普遍關(guān)心的問題。數(shù)據(jù)挖掘的概念為解決這一問題而提出并在近年來引起學(xué)術(shù)界的廣泛關(guān)注，成為學(xué)術(shù)研究的熱點。

數(shù)據(jù)挖掘，又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)，是指從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、未知的、非平凡的及有潛在應(yīng)用價值的知識或模式，它是數(shù)據(jù)庫研究中的一個很有應(yīng)用價值的新領(lǐng)域，融合了數(shù)據(jù)庫、人工智能、機器學(xué)習(xí)、統(tǒng)計學(xué)等多個領(lǐng)域的理論和技術(shù)。

數(shù)據(jù)挖掘的任務(wù)是從大量的數(shù)據(jù)中發(fā)現(xiàn)模式或知識。模式按其作用可分為兩類：一類稱為描述型模式，它是對數(shù)據(jù)中存在的規(guī)律做出描述。 如泛化模式、聚類模式、關(guān)聯(lián)模式及時間序列模式。 另一類是預(yù)測型模式，它依據(jù)從己有數(shù)據(jù)獲得的知識對未知數(shù)據(jù)的某些性質(zhì)進行預(yù)測。包括分類模式和回歸模式。其中，分類模式是一種重要的預(yù)測型模式。

用于挖掘分類模式的方法有很多，如決策樹方法，貝葉斯網(wǎng)絡(luò)，遺傳算法，基于關(guān)聯(lián)的分類方法，粗糙集，k-最臨近方法，等等。其中決策樹方法以其易被人理解、需要信息覓少、效率及準確率較高等優(yōu)點占據(jù)著重要地位。 決策樹方法自產(chǎn)生至今，先后涌現(xiàn)出多種算法，包括ID3 、C4.5 、 CART, SLIQ、 SPRINTPUBLIC， 基于人機交互的方法等。他們的共同特點是對訓(xùn)練樣本集進行挖掘后都會生成一棵形如二叉樹或多叉樹的決策樹。樹的葉子節(jié)點代表某一類別，非葉節(jié)點，包括根節(jié)點及內(nèi)節(jié)點代表某個一般屬性(非類別屬性)的一個測試，測試的一個結(jié)果形成非葉節(jié)點的一個分枝。從根節(jié)點到葉子節(jié)點的一條路徑形成一條分類規(guī)則。 一棵決策樹能夠很方便的轉(zhuǎn)化為若干條分類規(guī)則。人們可以依據(jù)分類規(guī)則直觀地對未知類別的樣本進行預(yù)測。

2 數(shù)據(jù)挖掘工具

根據(jù)挖掘方法，數(shù)據(jù)挖掘可分為：機器學(xué)習(xí)方法、統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)方法和數(shù)據(jù)庫方法。 根據(jù)所采用的方法，數(shù)據(jù)挖掘工具可以大致分為以下六類：

（1）基于規(guī)則和決策樹的工具：大部分數(shù)據(jù)挖掘工具采用規(guī)則發(fā)現(xiàn)和決策樹分類技術(shù)來發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則， 其核心是某種歸納算法，如ID3 和C4.5 算法。 它通常是對數(shù)據(jù)庫中的數(shù)據(jù)進行挖掘生成規(guī)則和決策樹，然后對新數(shù)據(jù)進行分析和預(yù)測。

（2）基于神經(jīng)元網(wǎng)絡(luò)的工具：基于神經(jīng)元網(wǎng)絡(luò)的工具由于具有對非線性數(shù)據(jù)的快速建模能力，因此越來越流行。 挖掘過程基本上是將數(shù)據(jù)簇聚，然后分類計算權(quán)伯。

（3）數(shù)據(jù)可視化方法：這類工具大大擴展了傳統(tǒng)商業(yè)圖形的能力，支持多維數(shù)據(jù)的可視化，同時提供了進行數(shù)據(jù)分析的圖形方法。

（4）模糊發(fā)現(xiàn)方法：應(yīng)用模糊邏輯進行數(shù)據(jù)查詢排序。

（5）統(tǒng)計方法：這此工具沒有使用人下智能技術(shù)，因此更適于分析現(xiàn)有信息，而不是從原始數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則。

（6）綜合方法：許多工具采用了多種挖掘方法，一般規(guī)模較大。

3 決策樹方法的優(yōu)缺點

決策樹，又稱判定樹，是一種類似二叉樹或多叉樹的樹結(jié)構(gòu)。樹中的每個非葉節(jié)點(包括根節(jié)點)對應(yīng)于訓(xùn)練樣本集中一個非類別屬性的測試，非葉節(jié)點的每一個分枝對應(yīng)屬性的一個測試結(jié)果，每個葉子節(jié)點則代表一個類或類分布。從根節(jié)點到葉子節(jié)點的一條路徑形成一條分類規(guī)則。 決策樹可以很方便地轉(zhuǎn)化為分類規(guī)則，是一種非常直觀的分類模式表示形式。

相對于其它分類方法，決策樹算法應(yīng)用最為廣泛，其獨特的優(yōu)點包括：（1）可以生成可以理解的規(guī)則；（2）計算量相對來說不是很大；（3）可以處理連續(xù)和種類字段；（4） 決策樹可以清晰地顯示哪些字段比較重要。

當然，決策樹也存在著很多的缺點：（1）對連續(xù)性的字段比較難預(yù)測；（2）對有時間順序的數(shù)據(jù)，需要很多預(yù)處理工作；（3）當類別太多時，錯誤可能會增加比較快；（4）一般算法分類的時候，只是根據(jù)一個字段來分類。

4 決策樹方法的主要研究進展

4.1 決策樹的精度

決策樹的預(yù)測精度一直是研究的重點，判斷各種決策樹的生成算法和剪枝算法的優(yōu)劣，精度是最重要的衡量指標。 構(gòu)造多變量決策樹是為了減小樹的規(guī)模，其最終目的是為了提高決策樹的精度。 如何提高決策樹的預(yù)測精度是決策樹方法的研究方向之一。

4.2 決策樹技術(shù)與其他技術(shù)的結(jié)合

在知識發(fā)現(xiàn)中，不可能用一種方法處理所有的數(shù)據(jù)集，完成各種數(shù)據(jù)采掘任務(wù)，需要研究同其它方法相結(jié)合的問題。并且，決策樹方法本身也可以和其它方法結(jié)合，現(xiàn)在已有人把決策樹方法同神經(jīng)網(wǎng)絡(luò)技術(shù)、模糊集理論、遺傳算法等相結(jié)合來進行研究，結(jié)果不同程度地提高了處理效率和精度。多種方法的交叉結(jié)合也是決策樹方法研究的方向之一。

4.3 尋找更好的簡化決策樹方法

簡化決策樹的研究工作主要有兩個方面，一是對比各種不同的簡化決策樹方法，分析它們各自的特性、優(yōu)點和缺點。另外一個就是尋找更好的與傳統(tǒng)方法不同的簡化決策樹的方法，這一直是決策樹技術(shù)研究的一個熱點。

4.4 不確定環(huán)境下決策樹研究

實際的數(shù)據(jù)集中存在著一些缺值數(shù)據(jù)，最簡單的方案是刪除帶有未屬性值的例子或是將未知屬性值用最常用的值代替，Quinlan J R 提出的一種解決方案是依據(jù)對象的其它屬性值和類信息來預(yù)測未知屬性的屬性值。 對缺值數(shù)據(jù)的處理一直是決策樹研究的熱點。

4.5 決策樹技術(shù)的軟件實現(xiàn)

將決策樹技術(shù)軟件化一直是決策樹技術(shù)的方向之一。如何開發(fā)出功能更加強大、使用更加方便、界面更加友好的軟件以實現(xiàn)決策樹技術(shù)，一直是大家努力的方向。

5 小結(jié)

決策樹算法已經(jīng)有了廣泛的應(yīng)用，并且已經(jīng)有了許多成熟的系統(tǒng)，這此系統(tǒng)廣泛應(yīng)用于各個領(lǐng)域，如語音識別，模式識別，專家系統(tǒng)等。 但是，解決一個復(fù)雜的數(shù)據(jù)挖掘問題的任何算法都要面臨以下問題：從錯誤的數(shù)據(jù)中學(xué)習(xí)、從分布的數(shù)據(jù)中學(xué)習(xí)、從有偏的數(shù)據(jù)中學(xué)習(xí)、學(xué)習(xí)有彈性的概念、 學(xué)習(xí)那些抽象程度不同的概念、 整合定性與定量的發(fā)現(xiàn)等，歸納學(xué)習(xí)當中還有很多未開發(fā)的課題等待我們?nèi)パ芯俊?/p>

［1］李卿.決策樹優(yōu)化算法研究[D].西南交通大學(xué),2009.

［2］萬永鋒.決策樹學(xué)習(xí)算法在金融自助設(shè)備監(jiān)控系統(tǒng)中的應(yīng)用[D].鄭州大學(xué),2007.

［3］戴南.基于決策樹的分類方法研究[D].南京師范大學(xué),2003

［4］李明侖.基于動態(tài)模糊格的決策樹理論及應(yīng)用研究[D].蘇州大學(xué),2006.

［5］成文麗.基于決策樹的數(shù)據(jù)挖掘算法的技術(shù)研究[D].太原理工大學(xué),2003.