李如平

(安徽工商職業(yè)學(xué)院電子信息系，安徽合肥231100)

數(shù)據(jù)挖掘中決策樹(shù)分類算法的研究

李如平

(安徽工商職業(yè)學(xué)院電子信息系，安徽合肥231100)

決策樹(shù)方法是數(shù)據(jù)挖掘中一種重要的分類方法，決策樹(shù)是一個(gè)類似流程圖的樹(shù)型結(jié)構(gòu)，其中樹(shù)的每個(gè)內(nèi)部結(jié)點(diǎn)代表對(duì)一個(gè)屬性的測(cè)試，其分支代表測(cè)試的結(jié)果，而樹(shù)的每個(gè)葉結(jié)點(diǎn)代表一個(gè)類別。通過(guò)決策樹(shù)模型對(duì)一條記錄進(jìn)行分類，就是通過(guò)按照模型中屬性測(cè)試結(jié)果從根到葉找到一條路徑，最后葉節(jié)點(diǎn)的屬性值就是該記錄的分類結(jié)果。

數(shù)據(jù)挖掘，分類，決策樹(shù)

近年來(lái)，隨著數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)技術(shù)的廣泛應(yīng)用以及計(jì)算機(jī)技術(shù)的快速發(fā)展，人們利用信息技術(shù)搜集數(shù)據(jù)的能力大幅度提高，大量數(shù)據(jù)庫(kù)被用于商業(yè)管理、政府辦公、科學(xué)研究和工程開(kāi)發(fā)等。面對(duì)海量的存儲(chǔ)數(shù)據(jù)，如何從中有效地發(fā)現(xiàn)有價(jià)值的信息或知識(shí)，是一項(xiàng)非常艱巨的任務(wù)。數(shù)據(jù)挖掘就是為了應(yīng)對(duì)這種要求而產(chǎn)生并迅速發(fā)展起來(lái)的。數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫(kù)的數(shù)據(jù)中提取人們感興趣的知識(shí)，這些知識(shí)是隱含的、事先未知的潛在有用的信息，提取的知識(shí)表示為概念、規(guī)則、規(guī)律、模式等形式(姜靈敏等，2007)。

分類在數(shù)據(jù)挖掘中是一項(xiàng)非常重要的任務(wù)。分類的目的是學(xué)會(huì)一個(gè)分類函數(shù)或分類模型，把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)映射到給定類別中的某個(gè)類別。分類可用于預(yù)測(cè)，預(yù)測(cè)的目的是從歷史數(shù)據(jù)記錄中自動(dòng)推導(dǎo)出對(duì)給定數(shù)據(jù)的趨勢(shì)描述，從而能對(duì)未來(lái)數(shù)據(jù)進(jìn)行預(yù)測(cè)(趙翔，2005)。分類算法最知名的是決策樹(shù)方法，決策樹(shù)是用于分類的一種樹(shù)結(jié)構(gòu)。

1 決策樹(shù)介紹

決策樹(shù)(decision tree)技術(shù)是用于分類和預(yù)測(cè)的主要技術(shù)，決策樹(shù)學(xué)習(xí)是一種典型的以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，它著眼于從一組無(wú)次序、無(wú)規(guī)則的事例中推理出決策樹(shù)表示形式的分類規(guī)則(趙翔，2005)。它采用自頂向下的遞歸方式，在決策樹(shù)的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性的比較，并根據(jù)不同屬性判斷從該節(jié)點(diǎn)向下的分支，在決策樹(shù)的葉節(jié)點(diǎn)得到結(jié)論。所以從根到葉節(jié)點(diǎn)就對(duì)應(yīng)著一條合取規(guī)則，整棵樹(shù)就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則(張桂杰，2005)。

把決策樹(shù)當(dāng)成一個(gè)布爾函數(shù)。函數(shù)的輸入為物體或情況的一切屬性(property)，輸出為”是”或“否”的決策值。在決策樹(shù)中，每個(gè)樹(shù)枝節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)有關(guān)某項(xiàng)屬性的測(cè)試，每個(gè)樹(shù)葉節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)布爾函數(shù)值，樹(shù)中的每個(gè)分支，代表測(cè)試屬性其中一個(gè)可能的值。

最為典型的決策樹(shù)學(xué)習(xí)系統(tǒng)是ID3，它起源于概念學(xué)習(xí)系統(tǒng)CLS，最后又演化為能處理連續(xù)屬性的C4.5(C5.0)等。它是一種指導(dǎo)的學(xué)習(xí)方法，該方法先根據(jù)訓(xùn)練子集形成決策樹(shù)。如果該樹(shù)不能對(duì)所有給出的訓(xùn)練子集正確分類，那么選擇一些其它的訓(xùn)練子集加入到原來(lái)的子集中，重復(fù)該過(guò)程一直到時(shí)形成正確的決策集。當(dāng)經(jīng)過(guò)一批訓(xùn)練實(shí)例集的訓(xùn)練產(chǎn)生一棵決策樹(shù)，決策樹(shù)可以根據(jù)屬性的取值對(duì)一個(gè)未知實(shí)例集進(jìn)行分類。使用決策樹(shù)對(duì)實(shí)例進(jìn)行分類的時(shí)候，由樹(shù)根開(kāi)始對(duì)該對(duì)象的屬性逐漸測(cè)試其值，并且順著分支向下走，直至到達(dá)某個(gè)葉結(jié)點(diǎn)，此葉結(jié)點(diǎn)代表的類即為該對(duì)象所處的類。

決策樹(shù)是應(yīng)用非常廣泛的分類方法，目前有多種決策樹(shù)方法，如 ID3，C4.5，PUBLIC，CART，CN2，SLIQ，SPRINT等。大多數(shù)已開(kāi)發(fā)的決策樹(shù)是一種核心算法的變體，下面先介紹一下決策樹(shù)分類的基本思想決策樹(shù)構(gòu)造與剪枝，然后詳細(xì)介紹ID3和C4.5算法及決策樹(shù)算法的分析及改進(jìn)等。

2 決策樹(shù)構(gòu)造與剪枝

決策樹(shù)分類算法通常分為兩個(gè)步驟，決策樹(shù)生成和決策樹(shù)剪枝。

2.1 決策樹(shù)構(gòu)造

決策樹(shù)構(gòu)造算法的輸入是一組帶有類別標(biāo)記的例子，構(gòu)造的結(jié)果是一棵二叉樹(shù)或多叉樹(shù)。二叉樹(shù)的內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))一般表示為一個(gè)邏輯判斷，如形式為(ai=vi)的邏輯判斷，其中ai是屬性，vi是該屬性的某個(gè)值。樹(shù)的邊是邏輯判斷的分支結(jié)果。多叉樹(shù)的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹(shù)的葉子結(jié)點(diǎn)都是類別標(biāo)記。

構(gòu)造決策樹(shù)的方法是采用自上而下的遞歸構(gòu)造(毛國(guó)君等，2007)。以多叉樹(shù)為例，它的構(gòu)造思路是，以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開(kāi)始建樹(shù)，如果樣本都在同一個(gè)類，則將其作為葉子結(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)容即是該類別標(biāo)記。否則，根據(jù)某種策略選擇一個(gè)屬性，按照屬性和各個(gè)取值，把例子集合劃分為若干子集合，使得每個(gè)子集上的所有例子在該屬性上具有同樣的屬性值。然后再依次遞歸處理各個(gè)子集。這種思路實(shí)際上就是“分而治之”的道理。二叉樹(shù)同理，差別僅在于要如何選擇好的邏輯判斷。

構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣的一組例子，可以有很多決策樹(shù)符合這組例子(朱明，2008)。研究結(jié)果表明，一般情況下，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇合適的產(chǎn)生分支的屬性。屬性選擇依賴于對(duì)各種例子子集的不純度(Impurity)度量方法。不純度度量方法包括信息增益(Information Gain)、信息增益比(Gain Ratio)、Gini-index、距離度量、x2統(tǒng)計(jì)、證據(jù)權(quán)重、最小描述長(zhǎng)度等。不同的度量由不同的效果，特別是對(duì)于多值屬性，選擇合適的度量方法對(duì)于結(jié)果的影響是很大的。ID3，C4.5，C5.0算法使用信息增益的概念來(lái)構(gòu)造決策樹(shù)，而CART算法x則使用Gini-index，其中每個(gè)分類的決定都與前面所選擇的目標(biāo)分類相關(guān)。

2.2 決策樹(shù)的剪枝

數(shù)據(jù)挖掘的對(duì)象是現(xiàn)實(shí)世界的數(shù)據(jù)，這些數(shù)據(jù)一般不可能是完美的，可能某些屬性字段上缺值;可能缺少必須的數(shù)據(jù)而造成數(shù)據(jù)不完整;可能數(shù)據(jù)不準(zhǔn)確、含有噪聲甚至是錯(cuò)誤的，所以要討論噪聲問(wèn)題?；镜臎Q策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練例子擬合。有噪聲情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合，即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能。剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。

1)兩種基本的剪枝策略。

①前期剪枝(Forward-Pruning)是在樹(shù)的生長(zhǎng)過(guò)程完成前就進(jìn)行剪枝(馬麗等，2008)。在樹(shù)的生長(zhǎng)過(guò)程中，決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。

例如某些有效統(tǒng)計(jì)量達(dá)到某個(gè)預(yù)先設(shè)定的閾值時(shí)，節(jié)點(diǎn)不再繼續(xù)分裂，內(nèi)部節(jié)點(diǎn)成為一個(gè)葉子節(jié)點(diǎn)。葉子節(jié)點(diǎn)取子集中頻率最大的類作為自己的標(biāo)識(shí)，或者可能僅僅存儲(chǔ)這些實(shí)例的概率分布函數(shù)。前期剪枝會(huì)引起樹(shù)在不完全成熟之前停止工作，即樹(shù)可能在不應(yīng)停止的時(shí)候而停止擴(kuò)展，或稱之為horizon效應(yīng)，而且，選取一個(gè)適當(dāng)?shù)拈撝凳抢щy的。較高的閾值可能導(dǎo)致過(guò)分簡(jiǎn)化的樹(shù)，而較低的閾值可能使樹(shù)簡(jiǎn)化的太少。即使這樣，預(yù)先修剪對(duì)大規(guī)模的實(shí)際應(yīng)用還是值得研究的，因?yàn)樗喈?dāng)高效。人們有望在未來(lái)的算法中解決horizon效應(yīng)。

②)后期剪枝(Post-Pruning)是當(dāng)決策樹(shù)的生長(zhǎng)過(guò)程完成之后再進(jìn)行剪枝(馬麗等，2008)。它是一種擬合-化簡(jiǎn)(Fitting-and-simplifying)的兩階段方法(毛國(guó)君等，2007)。首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹(shù)，然后由下向上從樹(shù)的葉子開(kāi)始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合，如果存在某個(gè)葉子剪去后測(cè)試集上的準(zhǔn)確度或其它測(cè)度不降低(不變得更壞)，則剪去該葉子，否則停機(jī)。

如果節(jié)點(diǎn)的子樹(shù)不應(yīng)按某種規(guī)則被修剪，則由下向上的評(píng)價(jià)規(guī)則將使該節(jié)點(diǎn)避免被按同一規(guī)則修剪。與此相對(duì)的是自上向下的策略，即從根開(kāi)始依次修剪節(jié)點(diǎn)，直到無(wú)法修剪為止。這樣作的風(fēng)險(xiǎn)在于，按某種規(guī)則剪掉了某個(gè)節(jié)點(diǎn)，但其子類是不應(yīng)按這一規(guī)則被剪掉的。

2)對(duì)樹(shù)進(jìn)行修剪優(yōu)化時(shí)應(yīng)遵循的原則。

①最小描述長(zhǎng)度原則(MDL)(張桂杰，2005)。它的思想是最簡(jiǎn)單的解釋是期望的，做法是對(duì)決策樹(shù)進(jìn)行二進(jìn)位編碼。編碼所需二進(jìn)位最少的樹(shù)即為“最佳剪枝樹(shù)”。

②期望錯(cuò)誤率最小原則(張桂杰，2005)。它的思想是選擇期望錯(cuò)誤率最小的子樹(shù)剪枝，即對(duì)樹(shù)中的內(nèi)部節(jié)點(diǎn)計(jì)算其剪枝/不剪枝可能出現(xiàn)的期望錯(cuò)誤率，比較后加以取舍。

③奧卡姆剃刀原則。如無(wú)必要，勿增實(shí)體(朱明，2008)。即“在與觀察相容的理論中，應(yīng)當(dāng)選擇最簡(jiǎn)單的一個(gè)”，決策樹(shù)越小就越容易被理解，其存儲(chǔ)與傳輸?shù)拇鷥r(jià)也就越小。

3 ID3算法

ID3算法是1986年Quinlan提出的一個(gè)著名決策樹(shù)生成方法，是目前引用率很高的一種算法。ID3算法是運(yùn)用信息熵理論，選擇當(dāng)前樣本集中最大信息增益的屬性值作為測(cè)試屬性;樣本集的劃分則依據(jù)測(cè)試屬性值進(jìn)行，測(cè)試屬性有多少不同取值就將樣本集劃分為多少子樣本集，同時(shí)，決策樹(shù)上相應(yīng)于該樣本集的節(jié)點(diǎn)長(zhǎng)出新的葉子節(jié)點(diǎn)。由于決策樹(shù)的結(jié)構(gòu)越簡(jiǎn)單越能從本質(zhì)的層次上概括事物的規(guī)律，期望非葉節(jié)點(diǎn)到達(dá)后代節(jié)點(diǎn)的平均路徑總是最短，即生成的決策樹(shù)的平均深度最小，這就要求在每個(gè)節(jié)點(diǎn)選擇好的劃分。系統(tǒng)的不確定性越小，信息的傳遞就越充分。ID3算法根據(jù)信息理論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標(biāo)準(zhǔn)，用信息增益值度量:信息增益值越大，不確定性越小。因此，算法在每個(gè)非葉節(jié)點(diǎn)選擇信息增益最大的屬性作為測(cè)試屬性。

ID3算法將對(duì)挖掘樣本集分為訓(xùn)練樣本集和測(cè)試樣本集，決策樹(shù)的構(gòu)建是在對(duì)訓(xùn)練樣本集的學(xué)習(xí)上產(chǎn)生的，決策樹(shù)生成之后，再運(yùn)用測(cè)試樣本集對(duì)樹(shù)進(jìn)行后剪技，將分類預(yù)測(cè)準(zhǔn)確率不符合條件的葉節(jié)點(diǎn)剪去。

1)信息理論(Informaiton theory)和熵(Entropy)。信息論是C.E Shannon為解決信息傳遞(通信)過(guò)程問(wèn)題而建立的理論，一個(gè)傳遞信息的系統(tǒng)是由發(fā)送端和接收端以及連接兩者的通道三者組成。熵是對(duì)事件對(duì)應(yīng)的屬性的不確定性的度量。一個(gè)屬性的熵值越小、子集劃分的純度越高，熵值熵越大，它蘊(yùn)含的不確定信息越大，約有利于數(shù)據(jù)的分類(張桂杰，2005)。

2)信息增益(Informmation Gain)。信息增益基于信息論中熵(Entropy)的概念，是指期望信息或者信息熵的有效減少量(通常用“字節(jié)”衡量)，根據(jù)它能夠確定在什么樣的層次上選擇什么樣的變量來(lái)分類(毛國(guó)君等，2007;朱明，2008)。ID3總是選擇具有最高信息增益(或最大熵)的屬性作為當(dāng)前結(jié)點(diǎn)的測(cè)試屬性。該屬性使得對(duì)結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或“不純性”。信息增益計(jì)算如下:

設(shè)S是s個(gè)訓(xùn)練樣本數(shù)據(jù)集，S中類標(biāo)識(shí)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci(i=1，2，3…，m)。設(shè)si是類Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由下式得出:

其中pi是任意樣本屬于Ci的概率，一般可用si/s來(lái)估計(jì)。

設(shè)屬性A具有n 個(gè)不同值{a1，a2，…，an}，可以用屬性A將S劃分為n個(gè)子集{S1，S2，…，Sn}，其中Sj包含S中這樣一些樣本，它們?cè)贏上具有值aj。如果A作為測(cè)試屬性，則這些子集對(duì)應(yīng)于由包含集合S的結(jié)點(diǎn)生長(zhǎng)出來(lái)的分支。

設(shè)sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵由下式給出:

根據(jù)上面的期望信息計(jì)算公式，對(duì)于給定的子集Sj，其期望信息由下式計(jì)算:

對(duì)屬性A作為決策分類屬性的度量值即信息增益可以由下面的公式得到:

3)ID3算法的分析。ID3通過(guò)不斷的循環(huán)處理，逐步求精決策樹(shù)，直至找到一個(gè)完全正確的決策樹(shù)。ID3算法構(gòu)造的決策樹(shù)是從頂向下歸納形成了一組類似If…Then的規(guī)則。其最原始的程序只是用來(lái)區(qū)分象棋中的走步，所以區(qū)分的類別只有兩種，即真或假，其屬性值也是一些離散有限的值，頁(yè)今ID3算法已發(fā)展到允許多于兩個(gè)類別，而其屬性值可以是整數(shù)或?qū)崝?shù)。其優(yōu)缺點(diǎn)總結(jié)如下:

①優(yōu)點(diǎn)。ID3在選擇重要特征時(shí)利用了信息增益的概念，算法的基礎(chǔ)理論清晰，使得算法較簡(jiǎn)單，該算法的計(jì)算時(shí)間是例子個(gè)數(shù)、特征個(gè)數(shù)、結(jié)點(diǎn)個(gè)數(shù)之積的線性函數(shù)。而且搜索空間是完全假設(shè)空間，目標(biāo)函數(shù)必在搜索空間中，不存在無(wú)解的危險(xiǎn)。全盤(pán)使用訓(xùn)練數(shù)據(jù)，而不像候選剪除算法一個(gè)一個(gè)地考慮訓(xùn)練例。這樣做的優(yōu)點(diǎn)是可以利用全部訓(xùn)練例的統(tǒng)計(jì)性質(zhì)進(jìn)行決策，從而抵抗噪音。

②缺點(diǎn)。信息增益的計(jì)算依賴于特征值數(shù)目較多的特征，這樣不太合理，一個(gè)簡(jiǎn)單的辦法對(duì)特征進(jìn)行分解，可以把特征值統(tǒng)統(tǒng)化為二值特征。ID3對(duì)噪聲較為敏感。Quinlan定義訓(xùn)練例子中的錯(cuò)誤就是噪聲。它包括兩個(gè)方面，一是特征值取錯(cuò)，二是類別給錯(cuò)。當(dāng)訓(xùn)練集增加時(shí)，ID3的決策樹(shù)也會(huì)隨之變化。在建樹(shù)過(guò)程中各特征的信息增益隨例子的增加而變化，這對(duì)漸近學(xué)習(xí)不夠方便。

4 C4.5 算法

C4.5(Classsification 4.5)算法是 Quinlan 在1993年提出的，它既是ID3算法的后繼，也成為以后諸多算法的基礎(chǔ)。除了擁有ID3算法的功能外，C4.5算法引用了新的方法并增加了新的功能。在應(yīng)用于單機(jī)的決策樹(shù)算法中，C4.5算法不僅分類準(zhǔn)確率高而且速度快。

C4.5算法在ID3的基礎(chǔ)上增加了信息增益比例的概念和連續(xù)型屬性，屬性值空缺情況的處理，對(duì)樹(shù)剪枝也有了較成熟的方法，通過(guò)使用不同的修剪技術(shù)以避免樹(shù)的過(guò)度擬合，它克服了ID3在應(yīng)用中的不足。首先用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向于選擇取值多的屬性的不足。其次，能夠完成對(duì)連續(xù)屬性的離散化處理，還能夠?qū)Σ煌暾臄?shù)據(jù)進(jìn)行處理。C4.5算法采用的知識(shí)表示形式為決策機(jī)構(gòu)樹(shù)，并最終可以形成產(chǎn)生式規(guī)則。

1)信息增益比例的概念。信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展起來(lái)的，一個(gè)屬性的信息增益比例用下面的公式給出:

這里設(shè)屬性A具有v個(gè)不同值{a1，a2，…，av}?？梢杂脤傩訟將S劃分為v個(gè)子集{S1，S2，S3}，其中Sj包含S中這樣一些樣本，它們?cè)贏上具有值aj。假如我們以屬性 A的值為基準(zhǔn)對(duì)樣本進(jìn)行分割，SplitI(A)就是前面熵的概念(毛國(guó)君等，2007;朱明，2008)。

2)合并具有連續(xù)值的屬性。ID3算法最初假定屬性離散值，但在實(shí)際應(yīng)用中，很多屬性值是連續(xù)的。針對(duì)連續(xù)屬性值，C4.5首先根據(jù)屬性的值，對(duì)數(shù)據(jù)集排序，用不同的閾值將數(shù)據(jù)集動(dòng)態(tài)地進(jìn)行劃分，當(dāng)輸入改變時(shí)，取兩個(gè)實(shí)際值中的中點(diǎn)作為一個(gè)閾值，取兩個(gè)劃分，所有樣本都在這兩個(gè)劃分中，得到所有可能的閾值、增益及增益比，在每一個(gè)屬性會(huì)變?yōu)閭z個(gè)取值，即小于閾值或大于等于閾值。

針對(duì)屬性有連續(xù)數(shù)值的情況，比如說(shuō)A有連續(xù)的屬性值，則在訓(xùn)練集中可以按升序方式排列a1，a2，…，am。如果 A共有 n種取值，則對(duì)每個(gè)取值vj(j=1，2，…，n)將所有的記錄進(jìn)行劃分。這些記錄被劃分成為兩個(gè)部分:一部分在vj的范圍內(nèi)，而另一部分則大于vj。針對(duì)每個(gè)劃分分別計(jì)算增益比率，選擇增益最大的劃分來(lái)對(duì)相應(yīng)的屬性進(jìn)行離散化。

3)規(guī)則的產(chǎn)生。一旦樹(shù)被建立，就可把樹(shù)轉(zhuǎn)化成If-Then規(guī)則。規(guī)則存儲(chǔ)于一個(gè)二維數(shù)組中，每一行代表樹(shù)中的一個(gè)規(guī)則，即從根到葉之間的一個(gè)路徑，表中的每列存放著樹(shù)中的結(jié)點(diǎn)。

5 決策樹(shù)分類算法的分析

基于決策樹(shù)的分類算法自提出至今，種類不下幾十種。各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性及分類預(yù)測(cè)的準(zhǔn)確性等方面各有千秋。決策樹(shù)分類算法的發(fā)展可分為這樣幾個(gè)階段:首先，最早出現(xiàn)的ID3算法采用信息熵原理選擇測(cè)試屬性分割樣本集，只能處理具有離散型屬性和屬性值齊全的樣本，生成形如多叉樹(shù)的決策樹(shù)。后來(lái)出現(xiàn)的C4.5算法經(jīng)過(guò)改進(jìn)，能夠直接處理連續(xù)型屬性，能夠處理屬性值空缺的訓(xùn)練樣本。ID3系列算法和C4.5系列算法在對(duì)訓(xùn)練樣本集的學(xué)習(xí)中盡可能多地挖掘信息，但其生成決策樹(shù)分枝較多，規(guī)模較大。為了簡(jiǎn)化決策樹(shù)算法，提高生成的決策樹(shù)的效率，又出現(xiàn)了一些其它決策樹(shù)算法。

決策樹(shù)分類算法的優(yōu)點(diǎn)主要是能生成可以理解的規(guī)則，計(jì)算量相對(duì)來(lái)說(shuō)不是很大，可以處理多種數(shù)據(jù)類型，決策樹(shù)可以清晰的顯示哪些屬性比較重要。與此同時(shí)它也存在一些缺點(diǎn)如對(duì)連續(xù)性的字段比較難預(yù)測(cè)，對(duì)有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作，當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快。

6 決策樹(shù)分類算法的改進(jìn)

針對(duì)決策樹(shù)分類算法的缺點(diǎn)，下面將從屬性的選擇，如何對(duì)連續(xù)性屬性進(jìn)行離散化等算法改進(jìn)方面進(jìn)行介紹。

1)屬性選擇。為了避免噪聲和干擾屬性對(duì)數(shù)據(jù)分類的影響，在建立決策樹(shù)之前先進(jìn)行對(duì)屬性重要性排序，再用神經(jīng)網(wǎng)絡(luò)技術(shù)對(duì)其中最重要的若干屬性進(jìn)行訓(xùn)練并檢驗(yàn)其預(yù)測(cè)精度，然后屬性重要性次序向兩端分別加減一個(gè)鄰近的屬性再進(jìn)行訓(xùn)練及檢驗(yàn)并和原檢驗(yàn)結(jié)果比較，這樣反復(fù)多次直到找到分類效果最佳的n個(gè)屬性為止，這樣得到n個(gè)分類效果最好的屬性。

2)連續(xù)屬性離散化。離散化是分類過(guò)程中處理連續(xù)性的一種有效方法。離散化的效率和有效性直接影響到后續(xù)機(jī)器學(xué)習(xí)算法的效率和性能。很多分類規(guī)則只能處理離散屬性，如ID3算法，對(duì)連續(xù)屬性進(jìn)行離散化是一個(gè)必要的步驟。C4.5雖能夠處理連續(xù)屬性，但離散化也是系統(tǒng)集成的一個(gè)重要步驟。離散化不僅可以縮短推導(dǎo)分類器的時(shí)間，而且有助于提高數(shù)據(jù)的可理解性，得到解精度更高的分類規(guī)則。

從優(yōu)化的角度可以將離散化方法分為兩類:局部方法和全局方法。局部方法每次只對(duì)一個(gè)屬性進(jìn)行離散，而全局方法同時(shí)對(duì)所有屬性進(jìn)行離散。局部離散方法相對(duì)簡(jiǎn)單，全局方法因?yàn)榭紤]了屬性間的相互作用往往可以得到比局部化方法更好的結(jié)果，但全局方法計(jì)算代價(jià)很高。

7 結(jié)束語(yǔ)

通過(guò)以上研究和分析，可以得出構(gòu)造好的決策樹(shù)關(guān)鍵在于如何選擇好的邏輯判斷和屬性。隨著數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)技術(shù)的廣泛應(yīng)用，數(shù)據(jù)的海量增加，決策樹(shù)技術(shù)的效率有待提高，針對(duì)實(shí)際問(wèn)題時(shí)，需要對(duì)決策樹(shù)數(shù)據(jù)挖掘方法在適應(yīng)性、容噪性等方面進(jìn)行適當(dāng)?shù)母倪M(jìn)。

但小容，陳軒恕，劉飛，柳德偉.2009.數(shù)據(jù)挖掘中決策樹(shù)分類算法的研究與改進(jìn)［J］.軟件導(dǎo)刊，8(2):41-43.

董賀，榮光怡.2008.數(shù)據(jù)挖掘中數(shù)據(jù)分類算法的比較分析［J］.吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，4:107-108.

姜靈敏，馬于濤.2007.信息資源聚合與數(shù)據(jù)挖掘［M］.廣州:華南理工大學(xué)出版社，12-18.

馬麗，陳桂芬.2008.基于數(shù)據(jù)挖掘的決策樹(shù)算法應(yīng)用研究［J］.農(nóng)業(yè)網(wǎng)絡(luò)信息，11:45-47.

毛國(guó)君，段立娟，王實(shí)，石云.2007.數(shù)據(jù)挖掘原理與算法(第二版)［M］.北京:清華大學(xué)出版社，120-131.

張桂杰.2005.數(shù)據(jù)挖掘決策樹(shù)分類算法的研究與應(yīng)用［D］.長(zhǎng)春:長(zhǎng)春理工大學(xué).

趙翔.2005.數(shù)據(jù)挖掘中決策樹(shù)分類算法的研究［D］.鎮(zhèn)江:江蘇科技大學(xué).

朱明.2008.數(shù)據(jù)挖掘(第2版)［M］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社，63-102.

Research of Decision Tree Classification Algorithm in Data Mining

LI Ru-ping
(Anhui Business Vocational College，Department of Electronic and Information，Hefei，AH 231100，China)

Decision tree algorithm is one of the most important classification measures in data mining.Decision tree classifier as one type of classifier is a flow-chart like tree structure，where each intenal node denotes a test on an attribute，each branch represents an outcome of the test，and each leaf node represents a class.The method that a decision tree model is used to classify a record is to find a path that from root to leaf by measuring the attributes test，and the attribute on the leaf is classification result.

data mining;classification;decision tree

TP311.13

A

1674-3504(2010)02-192-05

10.3969/j.issn.1674-3504.2010.02.015

2010-02-28

李如平(1973—)，男，安徽肥東人，講師，碩士，主要研究方向:計(jì)算機(jī)應(yīng)用技術(shù)、信息管理。