張林 張昊

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

決策樹(shù)算法分析及其在實(shí)際應(yīng)用中的改進(jìn)

張林1張昊2

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

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

決策樹(shù)；ID3；算法

1． 引言

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

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

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

2． 算法的描述

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

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

圖1 決策樹(shù)算法挖掘模型

2.1 主算法描述

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

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

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

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

2.2 建樹(shù)算法描述

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

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

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

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

3． 決策樹(shù)算法的優(yōu)缺點(diǎn)

3.1 優(yōu)點(diǎn)

決策樹(shù)算法具有以下一些優(yōu)點(diǎn)

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

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

（2）計(jì)算量相對(duì)于其它算法來(lái)說(shuō)是比較小的。

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

（3）運(yùn)算速度相對(duì)來(lái)說(shuō)比較快。

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

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

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

3.2 缺點(diǎn)

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

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

（2）決策樹(shù)算法是一種單變?cè)惴?，即每個(gè)節(jié)點(diǎn)僅含一個(gè)屬性，各屬性間的關(guān)聯(lián)性不夠緊密。

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

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

4． 算法在實(shí)際應(yīng)用中的改進(jìn)

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

4.1 算法的改進(jìn)

（1）對(duì)定量屬性的處理

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

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

（2）缺失值情況的處理

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

（3）樹(shù)的剪枝

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

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

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

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

（5）計(jì)算的簡(jiǎn)化

在利用決策樹(shù)算法進(jìn)行分類的過(guò)程中，我們需要計(jì)算各屬性的互信息，并選擇互信息最大的屬性作為分支點(diǎn)?；バ畔(U,V)=H(U)-H(U|V)。因?yàn)閷?duì)于每個(gè)分支點(diǎn)來(lái)說(shuō)信息熵H(U)是相同的，所以要求互信息最大的屬性即求條件熵H(U|V)最小的屬性。

4.2 偽代碼

5． 結(jié)束語(yǔ)

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

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

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

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

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

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

TP311.13

A

1672-0547（2010）06-0071-02

2010-10-16

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