決策樹方法的研究進展

曹 寧 高 瑩 徐根祺

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

1 數據挖掘的應用背景

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

數據挖掘，又稱數據庫中的知識發現，是指從大型數據庫或數據倉庫中提取隱含的、未知的、非平凡的及有潛在應用價值的知識或模式，它是數據庫研究中的一個很有應用價值的新領域，融合了數據庫、人工智能、機器學習、統計學等多個領域的理論和技術。

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

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

2 數據挖掘工具

根據挖掘方法，數據挖掘可分為：機器學習方法、統計方法、神經網絡方法和數據庫方法。 根據所采用的方法，數據挖掘工具可以大致分為以下六類：

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

（2）基于神經元網絡的工具：基于神經元網絡的工具由于具有對非線性數據的快速建模能力，因此越來越流行。 挖掘過程基本上是將數據簇聚，然后分類計算權伯。

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

（4）模糊發現方法：應用模糊邏輯進行數據查詢排序。

（5）統計方法：這此工具沒有使用人下智能技術，因此更適于分析現有信息，而不是從原始數據中發現數據模式和規則。

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

3 決策樹方法的優缺點

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

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

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

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

4.1 決策樹的精度

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

4.2 決策樹技術與其他技術的結合

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

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

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

4.4 不確定環境下決策樹研究

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

4.5 決策樹技術的軟件實現

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

5 小結

決策樹算法已經有了廣泛的應用，并且已經有了許多成熟的系統，這此系統廣泛應用于各個領域，如語音識別，模式識別，專家系統等。 但是，解決一個復雜的數據挖掘問題的任何算法都要面臨以下問題：從錯誤的數據中學習、從分布的數據中學習、從有偏的數據中學習、學習有彈性的概念、 學習那些抽象程度不同的概念、 整合定性與定量的發現等，歸納學習當中還有很多未開發的課題等待我們去研究。

［1］李卿.決策樹優化算法研究[D].西南交通大學,2009.

［2］萬永鋒.決策樹學習算法在金融自助設備監控系統中的應用[D].鄭州大學,2007.

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

［4］李明侖.基于動態模糊格的決策樹理論及應用研究[D].蘇州大學,2006.

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