數(shù)據(jù)挖掘中的基于決策樹的分類方法

1 分類的概念及分類器的評(píng)判

分類是數(shù)據(jù)挖掘中的一個(gè)重要課題。分類的目的是學(xué)會(huì)一個(gè)分類函數(shù)或分類模型（也常常稱作分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)映射到給定類別中的某一個(gè)。分類可用于提取描述重要數(shù)據(jù)類的模型或預(yù)測未來的數(shù)據(jù)趨勢(shì)。
分類可描述如下：輸入數(shù)據(jù)，或稱訓(xùn)練集（training set）是一條條記錄組成的。每一條記錄包含若干條屬性（attribute），組成一個(gè)特征向量。訓(xùn)練集的每條記錄還有一個(gè)特定的類標(biāo)簽（類標(biāo)簽）與之對(duì)應(yīng)。該類標(biāo)簽是系統(tǒng)的輸入，通常是以往的一些經(jīng)驗(yàn)數(shù)據(jù)。一個(gè)具體樣本的形式可為樣本向量：(v1,v2,…,…vn:c)。在這里vi表示字段值，c表示類別。

分類的目的是：分析輸入數(shù)據(jù)，通過在訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來的特性，為每一個(gè)類找到一種準(zhǔn)確的描述或者模型。這種描述常常用謂詞表示。由此生成的類描述用來對(duì)未來的測試數(shù)據(jù)進(jìn)行分類。盡管這些未來的測試數(shù)據(jù)的類標(biāo)簽是未知的，我們?nèi)钥梢杂纱祟A(yù)測這些新數(shù)據(jù)所屬的類。注意是預(yù)測，而不能肯定。我們也可以由此對(duì)數(shù)據(jù)中的每一個(gè)類有更好的理解。也就是說：我們獲得了對(duì)這個(gè)類的知識(shí)。

對(duì)分類器的好壞有三種評(píng)價(jià)或比較尺度：

預(yù)測準(zhǔn)確度：預(yù)測準(zhǔn)確度是用得最多的一種比較尺度，特別是對(duì)于預(yù)測型分類任務(wù)，目前公認(rèn)的方法是10番分層交叉驗(yàn)證法。
計(jì)算復(fù)雜度：計(jì)算復(fù)雜度依賴于具體的實(shí)現(xiàn)細(xì)節(jié)和硬件環(huán)境，在數(shù)據(jù)挖掘中，由于操作對(duì)象是巨量的數(shù)據(jù)庫，因此空間和時(shí)間的復(fù)雜度問題將是非常重要的一個(gè)環(huán)節(jié)。

模型描述的簡潔度：對(duì)于描述型的分類任務(wù)，模型描述越簡潔越受歡迎；例如，采用規(guī)則表示的分類器構(gòu)造法就更有用。

分類技術(shù)有很多，如決策樹、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、遺傳算法、關(guān)聯(lián)規(guī)則等。本文重點(diǎn)是詳細(xì)討論決策樹中相關(guān)算法。

2 基于決策樹的數(shù)據(jù)分類算法及其性能

2.1 ID3和C4.5算法

決策樹技術(shù)是用于分類和預(yù)測的主要技術(shù)，決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它著眼于從一組無次序、無規(guī)則的事例中推理除決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同屬性判斷從該節(jié)點(diǎn)向下的分支，然后進(jìn)行剪枝，最后在決策樹的葉節(jié)點(diǎn)得到結(jié)論。所以從根到葉節(jié)點(diǎn)就對(duì)應(yīng)著一條合取規(guī)則，整棵樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。基于決策樹的分類有很多實(shí)現(xiàn)算法。ID3和C4.5是較早提出并普遍使用的決策樹算法。

Quinlan提出的著名的ID3學(xué)習(xí)算法是較早的經(jīng)典算法。它通過選擇窗口來形成決策樹，是利用信息論中的互信息尋找訓(xùn)練集具有最大信息量的屬性字段，建立決策樹的一個(gè)節(jié)點(diǎn)，再根據(jù)該屬性字段的不同取值建立樹的分支；在每個(gè)分支子集中重復(fù)建立樹的下層節(jié)點(diǎn)和分支過程。C4.5算法和ID3算法相似，它是對(duì)ID3算法的一種改進(jìn)，它是根據(jù)信息增益（Information Gain）值選擇作為分裂結(jié)點(diǎn)的屬性及標(biāo)準(zhǔn),按照此標(biāo)準(zhǔn)將訓(xùn)練集分成若干個(gè)子集。這兩中種方法的優(yōu)點(diǎn)是描述簡單，分類速度快，分類較準(zhǔn)確特別適合大規(guī)模的數(shù)據(jù)處理。但這兩種算法是借用信息論中的互信息或信息增益作為單一屬性能力的度量，試圖減少樹的平均深度，忽略了葉子數(shù)目的研究，其啟發(fā)式函數(shù)并不是最優(yōu)的，存在的主要問題還有：（1）抗噪性差，訓(xùn)練例子中正例和反例較難控制。（2）在構(gòu)造樹的過程中,需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序,因而導(dǎo)致算法的低效。（3）這兩種算法只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集使用,當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。

2.2 SLIQ算法

SLIQ算法對(duì)C4.5決策樹分類算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn)。

一般決策樹中，使用信息量作為評(píng)價(jià)節(jié)點(diǎn)分裂質(zhì)量的參數(shù)，SLIQ算法中使用gini指標(biāo)代替信息量，gini指標(biāo)比信息量性能更好，且計(jì)算方便，對(duì)數(shù)據(jù)集包含n個(gè)類的數(shù)據(jù)集S，gini(S)定義為：

gini(S) = 1 - ∑pj*pj

pj是S中第j類數(shù)據(jù)的頻率gini越小，Information Gain越大。

區(qū)別于一般的決策樹 SLIQ采用二分查找樹結(jié)構(gòu) 對(duì)每個(gè)節(jié)點(diǎn)都需要先計(jì)算最佳分裂方案，然后執(zhí)行分裂。

對(duì)于數(shù)值型連續(xù)字段分裂的形式A<=v。所以，可以先對(duì)數(shù)值型字段排序，假設(shè)排序后的結(jié)果為v1,v2,…,…vn，因?yàn)榉至阎粫?huì)發(fā)生在兩個(gè)節(jié)點(diǎn)之間，所以有n-1種可能性。通常取中點(diǎn)(vi + vi+1)/2作為分裂點(diǎn)，從小到大依次取不同的split point，取Information Gain指標(biāo)最大(gini最小)的一個(gè)就是分裂點(diǎn),因?yàn)槊總€(gè)節(jié)點(diǎn)都需要排序，所以這項(xiàng)操作的代價(jià)極大。

對(duì)于離散型字段(categorical attribute)，設(shè)S(A)為A的所有可能的值，分裂測試將要取遍S的所有子集S'。尋找當(dāng)分裂成S'和S-S'兩塊時(shí)的gini指標(biāo)，取到gini最小的時(shí)候，就是最佳分裂方法。顯然，這是一個(gè)對(duì)集合S的所有子集進(jìn)行遍歷的過程共需要計(jì)算2|S| 次，代價(jià)也是很大的。
SLIQ算法對(duì)此采用了預(yù)排序的技術(shù),以便能夠消除在決策樹的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行排序的需要。所謂預(yù)排序,就是針對(duì)每個(gè)屬性的取值,把所有的記錄按照從小到大的順序進(jìn)行排序。

在C4.5中,樹的構(gòu)造是按照深度優(yōu)先策略完成的,需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描,費(fèi)時(shí)很多。SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹,即在決策樹的每一層只需對(duì)每個(gè)屬性列表掃描一次,就可以為當(dāng)前決策樹中每個(gè)葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。
SLIQ的剪枝算法MDL屬于遲滯剪枝(post-prunning)算法，通常的遲滯剪枝的數(shù)據(jù)源采用一個(gè)Training Set的一個(gè)子集或者與Training Set獨(dú)立的數(shù)據(jù)集進(jìn)行操作。

SLIQ算法具體實(shí)現(xiàn)

輸入與輸出：輸入與輸出采用下面的方案 輸入數(shù)據(jù)包括訓(xùn)練集配置信息(決策樹大小) 輸出數(shù)據(jù) 包括用線性方式表示的二分決策樹
算法的控制：算法的控制結(jié)構(gòu)是一個(gè)隊(duì)列，這個(gè)隊(duì)列存放當(dāng)前的所有葉子節(jié)點(diǎn)。這是為了控制廣度優(yōu)先搜索的結(jié)束。當(dāng)隊(duì)列空時(shí)，說明所有的葉子都已經(jīng)被處理過，這時(shí)建樹算法結(jié)束。

（1）數(shù)據(jù)準(zhǔn)備

系統(tǒng)輸入是訓(xùn)練集，訓(xùn)練集是樣本向量(v1,v2,…,…vn ：c)組成的集合，每個(gè)屬性對(duì)應(yīng)訓(xùn)練集的一列，訓(xùn)練集進(jìn)入以后，分成一個(gè)一個(gè)的屬性表：

(Attribute List){(vi,i)| i<=training data num && i>=0}

i是屬性vi的記錄索引號(hào)，將所有類標(biāo)識(shí)放入類表，類表中的leaf字段指向該記錄對(duì)應(yīng)的決策樹的葉子，初始狀態(tài)下，所有記錄指向樹根，對(duì)屬性表進(jìn)行預(yù)排序，交換屬性值vi，同時(shí)交換I，生成有序的屬性表序列。排序完成后屬性表中的i是屬性值指向類表的指針。完成屬性表的排序后，數(shù)據(jù)初始化工作就完成。

（2）計(jì)算最佳分裂

當(dāng)完成數(shù)據(jù)預(yù)處理之后 算法進(jìn)入往復(fù)的求最佳分裂指標(biāo)的階段。這一階段 經(jīng)過一次對(duì)所有屬性表的遍歷，可以找出所有葉子節(jié)點(diǎn)的最佳分裂方案，在這個(gè)階段有一個(gè)重要的結(jié)構(gòu)，類直方圖(class histogram)，它位于決策樹的每個(gè)頂點(diǎn)內(nèi)，存放每個(gè)節(jié)點(diǎn)當(dāng)前的類信息——左、右子樹的每個(gè)類各擁有多少節(jié)點(diǎn)。

當(dāng)前屬性A是數(shù)值型字段時(shí) 每次作遍歷時(shí)類直方圖亦隨之改變，隨時(shí)表征以當(dāng)前屬性A的當(dāng)前值v為閾值的節(jié)點(diǎn)分裂方式對(duì)葉子L的分裂狀況由Class Histogram即可算出某個(gè)分裂方案的gini值，完成對(duì)A的遍歷后，gini值最小既Information Gain最高的A的值就是用屬性A分裂的最佳閾值。新方案可以存入決策樹節(jié)點(diǎn)。

當(dāng)前屬性是離散型字段時(shí)，在遍歷過程中記錄下每個(gè)屬性值對(duì)應(yīng)的類的個(gè)數(shù)，遍歷完成后，利用貪心算法得到Information Gain最高的A的子集，

即為所求的用A的分裂方案，新方案可以存入決策樹節(jié)點(diǎn)。

對(duì)整個(gè)屬性表的每個(gè)屬性進(jìn)行一次完全的遍歷之后 對(duì)每個(gè)節(jié)點(diǎn)而言，最佳分裂方案包括用哪個(gè)屬性進(jìn)行分類以及分類的閾值是什么已經(jīng)形成。并且存放在決策樹的節(jié)點(diǎn)內(nèi)。

（3）升級(jí)節(jié)點(diǎn)

當(dāng)最佳分裂參數(shù)已經(jīng)存放在節(jié)點(diǎn)中以后，算法的下一步是創(chuàng)建子節(jié)點(diǎn)，執(zhí)行節(jié)點(diǎn)分裂(升級(jí)類表)。這一步的主要任務(wù)是對(duì)應(yīng)該分裂的類表進(jìn)行更改。

（4）結(jié)果輸出

算法生成的決策樹通過前序遍歷的方式存入輸出表。

SLIQ的優(yōu)點(diǎn)有：（1）運(yùn)算速度快，對(duì)屬性值只作一次排序。（2）利用整個(gè)訓(xùn)練集的所有數(shù)據(jù)，不作取樣處理，不喪失精確度。（3）輕松處理磁盤常駐的大型訓(xùn)練集，適合處理數(shù)據(jù)倉庫的海量歷史數(shù)據(jù)。（4）更快的更小的目標(biāo)樹。（5）低代價(jià)的MDL剪枝算法。
SLIQ的存在的缺點(diǎn)有：（1）由于需要將類別列表存放于內(nèi)存,而類別列表的長度與訓(xùn)練集的長度是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。（2）由于采用了預(yù)排序技術(shù),而排序算法的復(fù)雜度本身并不是與記錄個(gè)數(shù)成線性關(guān)系,因此使得SLIQ算法不可能達(dá)到隨記錄數(shù)目增長的線性可擴(kuò)展性。

2.3 SPRINT算法

為了減少數(shù)據(jù)量，SPRINT算法改進(jìn)了SLIQ決策樹算法實(shí)現(xiàn)時(shí)的數(shù)據(jù)結(jié)構(gòu)，去掉駐留于內(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串行算法

算法的基本步驟如下:

Procedure BuildTree (S , A )

(S:訓(xùn)練樣本集，A:分類屬性集合)

初始化樣本集S，生成有序?qū)傩粤斜砗?a href='/map/zhifangtu/' style='color:#000;font-size:inherit;'>直方圖，創(chuàng)建節(jié)點(diǎn)隊(duì)列，放人N

while隊(duì)列不為空

從隊(duì)列中取出第一個(gè)節(jié)點(diǎn)N

if N純or為空then

標(biāo)記為葉節(jié)點(diǎn)，continue

for N的每一個(gè)分割點(diǎn)F

計(jì)算該節(jié)點(diǎn)F上的gini值，選出最佳分割點(diǎn)F* ,N長出分支節(jié)點(diǎn)N1,N2，放人隊(duì)列中.將該分割點(diǎn)的屬性列表分割，并用該列表的rids生成記錄所在節(jié)點(diǎn)的哈希表，用哈希表分割其他屬性列表，列表分割同時(shí)生成屬性直方圖。

串行環(huán)境下，剛開始SPRINT比SLIQ時(shí)間消耗高一些，樣本繼續(xù)增加后，SLIQ時(shí)間消耗要比SPRINT高。在并行環(huán)境下采用并行算法，相同處理器時(shí)相應(yīng)時(shí)間SLIQ要大于SPRINT。

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ù)雜。

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