決策樹算法分析及其在實際應(yīng)用中的改進

張林 張昊

（1.安徽三聯(lián)學(xué)院，安徽合肥230601；2.銅陵學(xué)院，安徽銅陵244000）

決策樹算法分析及其在實際應(yīng)用中的改進

張林1張昊2

（1.安徽三聯(lián)學(xué)院，安徽合肥230601；2.銅陵學(xué)院，安徽銅陵244000）

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

決策樹；ID3；算法

1． 引言

決策樹算法是數(shù)據(jù)挖掘常用算法之一，屬于歸納學(xué)習(xí)方法的一種。它以樣本為基礎(chǔ)，主要用于分類和預(yù)測，其結(jié)果比較容易轉(zhuǎn)換為分類規(guī)則。

決策樹是一種類似于流程圖的樹型結(jié)構(gòu)，樹的內(nèi)部節(jié)點為屬性或?qū)傩约?，樹的分枝為對屬性值的判斷，而樹葉節(jié)點則表示樣本所屬類或類的分布，即結(jié)論。

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

2． 算法的描述

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

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

圖1 決策樹算法挖掘模型

2.1 主算法描述

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

（2）用下述“建樹算法”對當(dāng)前子集構(gòu)造一棵決策樹。

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

（4）若存在判斷錯誤的例子則將該例子插入到子集中并轉(zhuǎn)到（1）繼續(xù)執(zhí)行，否則程序結(jié)束。

2.2 建樹算法描述

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

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

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

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

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

3.1 優(yōu)點

決策樹算法具有以下一些優(yōu)點

（1）能夠生成可理解的規(guī)則。

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

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

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

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

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

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

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

3.2 缺點

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

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

（2）決策樹算法是一種單變元算法，即每個節(jié)點僅含一個屬性，各屬性間的關(guān)聯(lián)性不夠緊密。

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

（4）決策樹算法在建樹過程中比較依賴于訓(xùn)練集，當(dāng)訓(xùn)練集改變時，各特征的互信息會隨訓(xùn)練集中例子數(shù)量的改變而改變，從而導(dǎo)致決策樹也隨之變化，這不利于變化的數(shù)據(jù)集的學(xué)習(xí)。

4． 算法在實際應(yīng)用中的改進

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

4.1 算法的改進

（1）對定量屬性的處理

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

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

（2）缺失值情況的處理

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

（3）樹的剪枝

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

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

（4）從決策樹中提取分類規(guī)則

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

（5）計算的簡化

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

4.2 偽代碼

5． 結(jié)束語

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

［1］謝印寶，宋道金.知識發(fā)現(xiàn)過程中數(shù)據(jù)采掘的方法和應(yīng)用[J].青島化工學(xué)院學(xué)報，2000，(3).

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

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

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

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

TP311.13

A

1672-0547（2010）06-0071-02

2010-10-16

張林（1981-），女，江蘇南京人，安徽三聯(lián)學(xué)院計算機系講師，研究方向：數(shù)據(jù)挖掘，數(shù)據(jù)結(jié)構(gòu)。