淺析數(shù)據(jù)挖掘分類方法中的決策樹算法

[摘 要]分類是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別中一個(gè)重要的研究領(lǐng)域。決策樹分類是一種重要的數(shù)據(jù)分類技術(shù)，本文通過對(duì)對(duì)各種決策樹分類算法的基本思想進(jìn)行闡述，并分析比較了各種算法的主要特性，為使用者選擇算法或研究者改進(jìn)算法提供借鑒。

[關(guān)鍵詞]算法 數(shù)據(jù)挖掘 分類 決策樹

一、引言

隨著社會(huì)的進(jìn)步和經(jīng)濟(jì)的發(fā)展，社會(huì)各領(lǐng)域活動(dòng)中會(huì)不斷產(chǎn)生大量的數(shù)據(jù)，人們把這些按照一定的數(shù)據(jù)模型保存在數(shù)據(jù)庫中。數(shù)據(jù)庫中隱藏著許多可以為商業(yè)和科研等活動(dòng)的決策提供所需要的知識(shí)，如何有效地獲取這些知識(shí)，數(shù)據(jù)挖掘技術(shù)中的分類方法正是解決這個(gè)問題的可行而有效的方法。

分類方法是一種重要的數(shù)據(jù)挖掘技術(shù)，分類的目的是根據(jù)數(shù)據(jù)集的特點(diǎn)構(gòu)造一個(gè)分類函數(shù)或分類模型，該模型能把未知類別的數(shù)據(jù)映射到給定類別的某一個(gè)中。該方法通常用于預(yù)測(cè)數(shù)據(jù)對(duì)象的離散類別。目前分類方法已被廣泛應(yīng)用于各行各業(yè)，如銀行信用評(píng)估、醫(yī)療診斷、高等教育評(píng)估和市場(chǎng)營(yíng)銷等實(shí)際應(yīng)用領(lǐng)域。本文將對(duì)數(shù)據(jù)挖掘分類方法中的決策樹算法加以分析。

二、數(shù)據(jù)分類技術(shù)概述

數(shù)據(jù)分類過程主要包含兩個(gè)步驟:第一步建立一個(gè)描述已知數(shù)據(jù)集類別或概念的模型;該模型是通過對(duì)數(shù)據(jù)庫中各數(shù)據(jù)行內(nèi)容的分析而獲得的。每一數(shù)據(jù)行都可以認(rèn)為是屬于一個(gè)確定的數(shù)據(jù)類別，其類別值是由一個(gè)屬性描述(即類別屬性)。分類學(xué)習(xí)方法所使用的數(shù)據(jù)集稱為訓(xùn)練樣本集和，因此分類學(xué)習(xí)又稱為監(jiān)督學(xué)習(xí)，它是在已知訓(xùn)練樣本類別情況下，通過學(xué)習(xí)建立相應(yīng)模型;而無監(jiān)督學(xué)習(xí)則是訓(xùn)練樣本的類別與類別個(gè)數(shù)均未知的情況下進(jìn)行的。通常分類學(xué)習(xí)所獲得的模型可以表示為分類規(guī)則形式、決策樹形式或數(shù)學(xué)形式。

第二步就是利用所獲得的模型進(jìn)行分類操作，首先對(duì)模型分類準(zhǔn)確率進(jìn)行估計(jì)，holdout方法就是一種簡(jiǎn)單的估計(jì)方法。它利用一組帶有類別的樣本進(jìn)行分類測(cè)試(測(cè)試樣本隨機(jī)獲得且與訓(xùn)練樣本相互獨(dú)立)。對(duì)于一個(gè)給定數(shù)據(jù)集所構(gòu)造出模型的準(zhǔn)確性可以通過由該模型所正確分類的數(shù)據(jù)樣本各書所占總測(cè)試樣本比例得到。

為了提高分類的準(zhǔn)確性、效率和可擴(kuò)展性，在進(jìn)行分類之前，通常要對(duì)數(shù)據(jù)進(jìn)行以下預(yù)處理。

1.數(shù)據(jù)清理。主要幫助出去數(shù)據(jù)中的噪聲，并妥善解決遺失數(shù)據(jù)的問題。

2.相關(guān)性分析。其目的是刪除那些與分類任務(wù)不相關(guān)的或冗余的屬性。

3.數(shù)據(jù)轉(zhuǎn)換。利用概念層次樹，數(shù)據(jù)能夠被泛化到更高的層次。例如屬性“收入”的數(shù)值就可以被泛化為“低、中等、高”的離散區(qū)間。

以數(shù)據(jù)庫為研究對(duì)象，數(shù)據(jù)挖掘分類模型的構(gòu)造算法主要有決策樹、貝葉斯、神經(jīng)網(wǎng)絡(luò)、基于關(guān)聯(lián)和基于數(shù)據(jù)庫技術(shù)的方法等。

三、決策樹(decision tree)分類算法

所謂決策樹就是一個(gè)類似流程圖的樹型結(jié)構(gòu)，決策樹是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無次序、無規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值的比較，并根據(jù)不同的屬性值從該結(jié)點(diǎn)向下分支，其中樹的每個(gè)內(nèi)部節(jié)點(diǎn)代表對(duì)一個(gè)屬性的測(cè)試，葉結(jié)點(diǎn)是要學(xué)習(xí)劃分的類。從根節(jié)點(diǎn)到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條分類規(guī)則，整個(gè)決策樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。樹的最高層點(diǎn)就是根節(jié)點(diǎn)。

決策樹的生成分為學(xué)習(xí)和測(cè)試兩個(gè)階段。決策樹學(xué)習(xí)階段采用自頂向下的遞歸方式。決策樹算法分兩個(gè)步驟:一是樹的生成，開始時(shí)所有數(shù)據(jù)都在根節(jié)點(diǎn)，然后遞歸地進(jìn)行數(shù)據(jù)劃分，直至生成葉結(jié)點(diǎn)。二是樹枝修剪，在一個(gè)決策樹剛剛建立起來的時(shí)候，它其中的許多分支都是根據(jù)訓(xùn)練樣本集合中的異常數(shù)據(jù)(由于噪聲等原因)構(gòu)造出來的。樹枝修剪就是去掉一些可能是噪聲或異常的數(shù)據(jù)。決策樹停止分割的條件是一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別;沒有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割。決策樹模型可以建立得很快，并適合應(yīng)用到大量的數(shù)據(jù)上。

目前已經(jīng)形成的決策樹算法有:ID3、C4.5、SLIQ、SPRINT、RainForest、CLS、CHAID、CART、FACT、GINT、SEE5等。其中比較有著名的是Quinlan提出的ID3算法，以及在ID3算法基礎(chǔ)上提出的C4.5算法。

1.ID3算法原理

基本決策樹構(gòu)造算法就是一個(gè)貪心算法，它采用自頂向下遞歸的方法構(gòu)造決策樹。著名的決策樹算法ID3算法的基本策略如下:

(1)樹以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)開始。

(2)如果樣本都在同一個(gè)類中，則這個(gè)節(jié)點(diǎn)成為樹葉結(jié)點(diǎn)并標(biāo)記為該類別。

(3)否則算法使用信息熵(稱為信息增益)作為啟發(fā)知識(shí)來幫助選擇合適的將樣本分類的屬性，以便將樣本集劃分為若干子集。該屬性就是相應(yīng)節(jié)點(diǎn)的“測(cè)試”或“判定”屬性。同時(shí)所有屬性應(yīng)當(dāng)是離散值。

(4)對(duì)測(cè)試屬性的每個(gè)已知的離散值創(chuàng)建一個(gè)分支，并據(jù)此劃分樣本。

(5)算法使用類似的方法，遞歸地形成每個(gè)劃分上的樣本決策樹。一個(gè)屬性一旦出現(xiàn)在某個(gè)結(jié)點(diǎn)上，那么它就不能再出現(xiàn)在該結(jié)點(diǎn)之后所產(chǎn)生的子樹結(jié)點(diǎn)中。

(6)整個(gè)遞歸過程在下列條件之一成立時(shí)停止。

給定結(jié)點(diǎn)的所有樣本屬于同一類。

沒有剩余屬性可以用來進(jìn)一步劃分樣本，這時(shí)候該結(jié)點(diǎn)作為樹葉，并用剩余樣本中所出現(xiàn)最多的類型作為葉子結(jié)點(diǎn)的類型。

某一分枝沒有樣本，在這種情況下以訓(xùn)練樣本集中占多數(shù)的類創(chuàng)建一個(gè)樹葉。

ID3算法的核心是在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的類別信息。某屬性的信息增益按下列方法計(jì)算，通過計(jì)算得到每個(gè)屬性的信息增益，比較它們的大小，就可以獲得最大信息增益的屬性。

設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假設(shè)類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類別()。設(shè)是類別中的樣本個(gè)數(shù)，那么要對(duì)一個(gè)給定數(shù)據(jù)對(duì)象進(jìn)行分類所需要的信息量為:

其中是任意一個(gè)數(shù)據(jù)對(duì)象屬于類別的概率。其中 log函數(shù)是以2為底，其原因是信息使用二進(jìn)制編碼。

設(shè)屬性A具有v個(gè)不同的值{}。利用屬性A可以將集合S劃分為v個(gè)子集{}，其中包含了S集合中屬性A取()值的數(shù)據(jù)樣本。若屬性A被選為測(cè)試屬性，設(shè)為子集中屬于類別的樣本數(shù)。由A劃分成子集的熵或信息期望可以計(jì)算如下:

熵值越小，子集劃分的純度越高。對(duì)于給定的子集，其信息期望計(jì)算為，其中是

中樣本屬于類別的概率。

這樣利用屬性A對(duì)當(dāng)前分支結(jié)點(diǎn)進(jìn)行相應(yīng)樣本集合劃分所獲得的信息增益就是:

決策樹歸納算法計(jì)算每個(gè)屬性的信息增益，并從中挑選出信息增益最大的屬性作為給定集合 的測(cè)試屬性并由此產(chǎn)生相應(yīng)的分支結(jié)點(diǎn)。所產(chǎn)生的結(jié)點(diǎn)被標(biāo)記為相應(yīng)的屬性，并根據(jù)這一屬性的不同取值分別產(chǎn)生相應(yīng)的分支，每個(gè)分支代表一個(gè)被劃分的樣本子集。

ID3算法的優(yōu)點(diǎn)是理論清晰，方法簡(jiǎn)單，學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是:

只能處理值是離散的屬性，不能處理連續(xù)值的屬性。

計(jì)算信息增益時(shí)偏向于選擇取值較多的屬性，不太合理。

對(duì)訓(xùn)練集合眾屬性值或類別給錯(cuò)的數(shù)據(jù)(即噪聲)比較敏感。

在構(gòu)造樹的過程中需要多次掃描數(shù)據(jù)集，因而導(dǎo)致算法的低效。

只適合駐留于內(nèi)存中的數(shù)據(jù)集使用，對(duì)訓(xùn)練集合大得無法在內(nèi)存容納的數(shù)據(jù)集無法運(yùn)行。

2.樹枝修剪

在一個(gè)決策剛剛建立起來的時(shí)候，由于許多分支是由訓(xùn)練樣本集和中的異常數(shù)據(jù)(由于噪聲等原因)構(gòu)造出來的，決策樹過于“枝繁葉茂”，這樣既降低了樹的可理解和可用性，同時(shí)也使決策樹本身對(duì)歷史數(shù)據(jù)的依賴性增大，也就是說這是這棵決策樹對(duì)此歷史數(shù)據(jù)可能非常準(zhǔn)確，一旦應(yīng)用到新的數(shù)據(jù)時(shí)準(zhǔn)確性卻急劇下降，這種情況被稱為訓(xùn)練過度。為了使得到的決策樹所蘊(yùn)含的規(guī)則具有普遍意義，必須對(duì)決策樹進(jìn)行修剪。樹枝修剪的任務(wù)主要是刪去一個(gè)或更多的樹枝，并用葉子替換這些樹枝，使決策樹簡(jiǎn)單化，以提高今后分類識(shí)別的速度和分類識(shí)別新數(shù)據(jù)的能力。

通常采用兩種方法進(jìn)行樹枝的修剪，它們分別是:

(1)事前修剪方法。該方法通過提前停止分支生成過程，即通過在當(dāng)前節(jié)點(diǎn)上就判斷是否需要繼續(xù)劃分該節(jié)點(diǎn)所含訓(xùn)練樣本寄來實(shí)現(xiàn)。一旦停止分支，當(dāng)前節(jié)點(diǎn)就成為一個(gè)葉節(jié)點(diǎn)。該葉節(jié)點(diǎn)中可能包含多個(gè)不同類別的訓(xùn)練樣本。由于該修剪是在分支之前做出的，所以稱之為事前修剪。

(2)事后修剪方法。該方法是從另一個(gè)角度解決訓(xùn)練過度的問題。它在允許決策樹得到最充分生長(zhǎng)的基礎(chǔ)上，再根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉節(jié)點(diǎn)或分支。修剪后，被修剪的分支節(jié)點(diǎn)就成為一個(gè)葉節(jié)點(diǎn)，并將其標(biāo)記為它所包含樣本中類別個(gè)數(shù)最多的類別。

3.C4.5算法

C4.5算法在ID3算法的基礎(chǔ)上，在以下幾個(gè)方面進(jìn)行了改進(jìn):

(1)用信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性不足。

(2)在樹構(gòu)造過程中進(jìn)行剪枝。

(3)能夠完成對(duì)連續(xù)屬性的離散化處理。

(4)能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

C4.5算法產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。但是和ID3算法一樣在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，導(dǎo)致算法低效;此外，C4.5也只適合于駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。

4.其他決策樹算法

ID3算法和C4.5算法的有效性已經(jīng)通過對(duì)許多小數(shù)據(jù)集的學(xué)習(xí)歸納得到了驗(yàn)證。但當(dāng)應(yīng)用這些算法對(duì)大規(guī)?，F(xiàn)實(shí)世界數(shù)據(jù)庫進(jìn)行數(shù)據(jù)挖掘時(shí)，算法的有效性和可擴(kuò)展性就成為應(yīng)用的關(guān)鍵。近年來，數(shù)據(jù)挖掘領(lǐng)域中又提出了許多有關(guān)決策樹可擴(kuò)展問題的解決方法。其中比較有代表性的算法有SLIQ方法和SPRINT方法。

SLIQ算法對(duì)C4.5決策樹算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn)，在決策樹的構(gòu)造過程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。所謂預(yù)排序，就是針對(duì)每個(gè)屬性的取值，把所有的記錄按照從小到大的順序進(jìn)行排序，以消除在決策樹的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行的排序。集體實(shí)現(xiàn)時(shí)，需要為訓(xùn)練數(shù)據(jù)集的每個(gè)屬性創(chuàng)建一個(gè)屬性列表，為類別屬性創(chuàng)建一個(gè)類別表。廣度優(yōu)先策略構(gòu)造決策樹，即在決策樹的每一層只需對(duì)每個(gè)屬性列表掃描一次，就可以為當(dāng)前決策樹中每個(gè)葉結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個(gè)數(shù)和屬性個(gè)數(shù)增長(zhǎng)的可伸縮性。

SPRINT算法去掉了SLIQ中需要駐留于內(nèi)存的類別列表，將其合并到每個(gè)屬性列表中。這樣，在尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，遍歷每個(gè)屬性列表就不必參照其他信息。但是，對(duì)非分裂屬性的屬性列表進(jìn)行分裂變得很困難，需要用哈希表記錄下每個(gè)記錄屬于個(gè)孩子結(jié)點(diǎn)。SPRINT算法具備以下優(yōu)點(diǎn):(1)訓(xùn)練樣本量不受內(nèi)存限制。(2)具有優(yōu)秀的伸縮性、加速性和擴(kuò)容性。(3)并行實(shí)現(xiàn)容易，效率高。SPRINT算法具備以下缺點(diǎn):(1)使用屬性列表，存儲(chǔ)代價(jià)是原來的三倍。(2)節(jié)點(diǎn)分割要?jiǎng)?chuàng)建哈希表，加大系統(tǒng)負(fù)擔(dān)。(3)節(jié)點(diǎn)分割處理相對(duì)復(fù)雜。

此外，RainForest也是一個(gè)基于決策樹歸納的數(shù)據(jù)挖掘系統(tǒng)。RainForest可根據(jù)當(dāng)前可用內(nèi)存的大小，自適應(yīng)地安排決策樹歸納算法的具體操作過程。它保持一個(gè)AVC集合(屬性—值，類別)，用以描述每個(gè)屬性的類別分布。RainForest的歸納速度要高于SPRINT方法。

四、結(jié)束語

以上是幾種常用的基于決策樹的分類算法，隨著算法研究的進(jìn)行，出現(xiàn)了許多其他基于決策樹的算法，它們與神經(jīng)網(wǎng)絡(luò)、遺傳算法等技術(shù)結(jié)合，從不同的方面對(duì)算法進(jìn)行了改進(jìn)和提高。我們也可以相信未來還會(huì)出現(xiàn)更多、更好、效率更高的分類算法。

參考文獻(xiàn):

[1] Jiawei Han Micheline Kambr.Data Mining: Concepts and Techniqyes[M].高等教育出版社，2001.

[2]毛國(guó)君 段立娟: 數(shù)據(jù)挖掘原理與算法[M].清華大學(xué)出版社，2005.7

[3]蘇新寧 楊建林: 數(shù)據(jù)倉庫和數(shù)據(jù)挖掘[M].清華大學(xué)出版社，2006.4