決策樹算法分析及其在實際應用中的改進

張林 張昊

（1.安徽三聯學院，安徽合肥230601；2.銅陵學院，安徽銅陵244000）

決策樹算法分析及其在實際應用中的改進

張林1張昊2

（1.安徽三聯學院，安徽合肥230601；2.銅陵學院，安徽銅陵244000）

決策樹算法是數據挖掘常用算法之一，屬于歸納學習方法的一種。它以樣本為基礎，主要用于分類和預測，其結果比較容易轉換為分類規則。ID3算法是一種以貪心算法為核心的典型的歸納學習算法，它采用自頂向下的遞歸方式生成一棵決策樹。ID3算法中使用的數據是理想情況下的數據，在實際應用中，數據在大多數情況下是不能滿足算法在理想情況下要求條件，因而也就不能直接使用決策樹算法進行分類。所以，在實際應用決策樹算法之前，還需要先對數據進行一些處理或改進。

決策樹；ID3；算法

1． 引言

決策樹算法是數據挖掘常用算法之一，屬于歸納學習方法的一種。它以樣本為基礎，主要用于分類和預測，其結果比較容易轉換為分類規則。

決策樹是一種類似于流程圖的樹型結構，樹的內部節點為屬性或屬性集合，樹的分枝為對屬性值的判斷，而樹葉節點則表示樣本所屬類或類的分布，即結論。

決策樹算法屬于貪心算法的一種，通常采用自頂向下的遞歸方式來構造一棵決策樹。在學習過程中只要樣本能夠用“屬性——值”的方式來表示即可使用該算法，而無需用戶了解更多的背景知識。

2． 算法的描述

建立決策樹的算法有很多，每種算法都有自己的優勢和不足，本文主要介紹經典的由J.R.Quinlan于1986年提出的ID3算法。

ID3算法是一種以貪心算法為核心的典型的歸納學習算法，它采用自頂向下的遞歸方式生成一棵決策樹[1][5]，其挖掘模型如圖1所示：

圖1 決策樹算法挖掘模型

2.1 主算法描述

（1）從訓練集中隨機選擇一個既含正例又含反例的子集。

（2）用下述“建樹算法”對當前子集構造一棵決策樹。

（3）用訓練集中子集以外的例子對所得到的決策樹進行判定，找出判斷錯誤的例子。

（4）若存在判斷錯誤的例子則將該例子插入到子集中并轉到（1）繼續執行，否則程序結束。

2.2 建樹算法描述

（1）對于當前例子集合，計算各屬性特征的互信息。

（2）選擇互信息最大的屬性特征Ak。

（3）把在Ak處取值相同的例子歸于同一子集。

（4）對既含正例又含反例的子集遞歸調用建樹算法，而對僅含正例或反例的子集則返回調用處。

3． 決策樹算法的優缺點

3.1 優點

決策樹算法具有以下一些優點

（1）能夠生成可理解的規則。

決策樹是以樹型結構表示最終分類結果的，是一種比較接近于人們對現實世界事務認知的表示方式[2][3]。因此，決策樹算法的可解釋性和所生成的可理解的規則就顯得非常重要了。

（2）計算量相對于其它算法來說是比較小的。

在系統開發的過程中，工作效率通常是比較重要的。決策樹算法的計算量相對其它算法來說不是很大，這可以在很大程度上縮短計算時間，提高系統的執行效率。

（3）運算速度相對來說比較快。

在計算量相對較小的情況下，比較容易轉化成分類規則。只要沿著樹根向下一直走到樹葉，沿途的分裂條件就能夠唯一確定一條分類的謂詞。

（4）準確性相對較高，可以較為清晰的顯示出屬性的重要程度。

信息熵是描述屬性重要程度的度量標識，而決策樹正是通過計算信息熵來選擇分裂屬性的[4]。因此，通過決策樹，用戶可以很清晰地了解哪些字段比較重要。而系統開發者在進行系統開發的過程中，也可利用決策樹算法挖掘出準確性較高且易于理解的分類規則。

3.2 缺點

決策樹算法雖是一個很有實用價值的較為簡單的示例學習算法，但也存在著一些缺點：

（1）決策樹算法往往偏向于選擇取值較多的屬性為分支點，而取值較多的屬性在很多情況下卻未必是最優的屬性，因此，即使按照熵值最小的原則進行屬性劃分，在實際情況中，應該首先判斷的屬性卻未必那么重要。

（2）決策樹算法是一種單變元算法，即每個節點僅含一個屬性，各屬性間的關聯性不夠緊密。

（3）決策樹算法對噪聲比較敏感，且不易去除，這容易使得特征的取值或分類出錯。

（4）決策樹算法在建樹過程中比較依賴于訓練集，當訓練集改變時，各特征的互信息會隨訓練集中例子數量的改變而改變，從而導致決策樹也隨之變化，這不利于變化的數據集的學習。

4． 算法在實際應用中的改進

ID3算法中使用的數據是理想情況下的數據，在實際應用中，數據在大多數情況下是不能滿足算法在理想情況下要求的條件的，因而也就不能直接使用決策樹算法進行分類。所以，在實際應用決策樹算法之前，還需要先對數據進行一些處理或改進。

4.1 算法的改進

（1）對定量屬性的處理

在實際應用中，數據的屬性除了有定性屬性（即離散型屬性）之外，還有大量的定量屬性（即連續型屬性）。ID3算法對所處理的屬性，要求的是定性屬性。因此，為了處理定量屬性，就要求對算法進行擴展，使之能夠處理連續型的定量屬性。

事實上，ID3算法的提出者J.R.Quinlan于1993年又提出了ID3算法的改進版本——C4.5算法，該算法不僅繼承了ID3算法的全部優點，還增加了對連續屬性離散化等功能。

（2）缺失值情況的處理

在建立決策樹的過程中，訓練樣本中經常會出現某些屬性有缺失值的情況。對于這種情況一般有兩種解決方法：一種方法是將缺失值看作屬性的某種可能取值，另一種方法則是將有缺失值的實例全部忽略掉。若在某種程度上屬性的缺失值情況明顯的話，一般采用第一種方法，而如果缺失值的屬性在決策中未發揮作用或作用不顯著的話，則通常采用第二種方法。

（3）樹的剪枝

決策樹的剪枝問題是決策樹技術中的一個重要部分。在決策樹創建過程中，由于受到訓練樣本數、數據的噪音和孤立點等方面的影響，很多分支反映的是訓練數據中的異?，F象，一般性差，甚至可能出現荒謬的結論。為了解決這種過度擬合（Overfitting，即推出過多與訓練數據集相一致的假設，因而不具有很好的預測性能）問題，我們需要對決策樹進行必要的剪枝。

常用的樹剪枝技術有先剪枝（pre-pruning）和后剪枝（post-pruning）兩種。先剪枝也稱為前剪枝或預剪枝，是一種限制決策樹過度生長的技術，而后剪枝則是等決策樹生成后再進行剪枝的一種剪枝技術。

（4）從決策樹中提取分類規則

決策樹的規則是以IF-THEN的形式表示的，從決策樹中提取分類規則可分為兩個步驟——獲得簡單規則和獲得精簡規則[5]。

（5）計算的簡化

在利用決策樹算法進行分類的過程中，我們需要計算各屬性的互信息，并選擇互信息最大的屬性作為分支點?；バ畔(U,V)=H(U)-H(U|V)。因為對于每個分支點來說信息熵H(U)是相同的，所以要求互信息最大的屬性即求條件熵H(U|V)最小的屬性。

4.2 偽代碼

5． 結束語

數據挖掘技術在信息社會中的地位已越來越重要，決策樹算法作為分類數據挖掘中的重要方法，在未來的研究中將得到進一步的完善和發展。事實上，就決策樹算法本身而言，還有很多問題亟待解決。例如：測試屬性選擇標準、數據預處理、決策樹剪枝和應用領域的擴展等，都是值得研究的課題。

［1］謝印寶，宋道金.知識發現過程中數據采掘的方法和應用[J].青島化工學院學報，2000，(3).

［2］孫艷.決策樹挖掘算法在教評體系中的應用研究[J].廊坊師范學院學報（自然科學版），2009，(1).

［3］肖志明.決策樹算法在高校教學評價中的應用研究[J].廣西輕工業，2008，(2).

［4］徐小云，岳志強.數據挖掘中算法概述[J].科技信息，2008，(21).

［5］安淑芝.數據倉庫與數據挖掘[M].北京：清華大學出版社,2005.

TP311.13

A

1672-0547（2010）06-0071-02

2010-10-16

張林（1981-），女，江蘇南京人，安徽三聯學院計算機系講師，研究方向：數據挖掘，數據結構。