基于決策樹的分類算法

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

2、，通過在訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來的特性，為每一個類找到一種準(zhǔn)確的描述或者模型。這種描述常常用謂詞表示。由此生成的類描述用來對未來的測試數(shù)據(jù)進(jìn)行分類。盡管這些未來的測試數(shù)據(jù)的類標(biāo)簽是未知的，我們?nèi)钥梢杂纱祟A(yù)測這些新數(shù)據(jù)所屬的類。注意是預(yù)測，而不能肯定。我們也可以由此對數(shù)據(jù)中的每一個類有更好的理解。也就是說：我們獲得了對這個類的知識。對分類器的好壞有三種評價或比較尺度：預(yù)測準(zhǔn)確度：預(yù)測準(zhǔn)確度是用得最多的一種比較尺度，特別是對于預(yù)測型分類任務(wù)，目前公認(rèn)的方法是10番分層交叉驗證法。計算復(fù)雜度：計算復(fù)雜度依賴于具體的實現(xiàn)細(xì)節(jié)和硬件環(huán)境，在數(shù)據(jù)挖掘中，由于操作對象是巨量的數(shù)據(jù)庫，因此空間和時間的復(fù)雜度問題

3、將是非常重要的一個環(huán)節(jié)。模型描述的簡潔度：對于描述型的分類任務(wù)，模型描述越簡潔越受歡迎；例如，采用規(guī)則表示的分類器構(gòu)造法就更有用。分類技術(shù)有很多，如決策樹、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、遺傳算法、關(guān)聯(lián)規(guī)則等。本文重點是詳細(xì)討論決策樹中相關(guān)算法。2 基于決策樹的數(shù)據(jù)分類算法及其性能2.1 ID3和C4.5算法決策樹技術(shù)是用于分類和預(yù)測的主要技術(shù)，決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)算法。它著眼于從一組無次序、無規(guī)則的事例中推理除決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點進(jìn)行屬性值的比較并根據(jù)不同屬性判斷從該節(jié)點向下的分支，然后進(jìn)行剪枝，最后在決策樹的葉節(jié)點得到結(jié)論。所以從根到葉

4、節(jié)點就對應(yīng)著一條合取規(guī)則，整棵樹就對應(yīng)著一組析取表達(dá)式規(guī)則。基于決策樹的分類有很多實現(xiàn)算法。ID3和C4.5是較早提出并普遍使用的決策樹算法。Quinlan提出的著名的ID3學(xué)習(xí)算法是較早的經(jīng)典算法。它通過選擇窗口來形成決策樹，是利用信息論中的互信息尋找訓(xùn)練集具有最大信息量的屬性字段，建立決策樹的一個節(jié)點，再根據(jù)該屬性字段的不同取值建立樹的分支；在每個分支子集中重復(fù)建立樹的下層節(jié)點和分支過程。C4.5算法和ID3算法相似，它是對ID3算法的一種改進(jìn)，它是根據(jù)信息增益（Information Gain）值選擇作為分裂結(jié)點的屬性及標(biāo)準(zhǔn),按照此標(biāo)準(zhǔn)將訓(xùn)練集分成若干個子集。這兩中種方法的優(yōu)點是描述簡單

5、，分類速度快，分類較準(zhǔn)確特別適合大規(guī)模的數(shù)據(jù)處理。但這兩種算法是借用信息論中的互信息或信息增益作為單一屬性能力的度量，試圖減少樹的平均深度，忽略了葉子數(shù)目的研究，其啟發(fā)式函數(shù)并不是最優(yōu)的，存在的主要問題還有：（1）抗噪性差，訓(xùn)練例子中正例和反例較難控制。（2）在構(gòu)造樹的過程中,需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序,因而導(dǎo)致算法的低效。（3）這兩種算法只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集使用,當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運(yùn)行。2.2 SLIQ算法SLIQ算法對C4.5決策樹分類算法的實現(xiàn)方法進(jìn)行了改進(jìn)。一般決策樹中，使用信息量作為評價節(jié)點分裂質(zhì)量的參數(shù)，SLIQ算法中使用gini指標(biāo)代替信息量

6、，gini指標(biāo)比信息量性能更好，且計算方便，對數(shù)據(jù)集包含n個類的數(shù)據(jù)集S，gini(S)定義為：gini(S) = 1 - pj*pjpj是S中第j類數(shù)據(jù)的頻率gini越小，Information Gain越大。區(qū)別于一般的決策樹 SLIQ采用二分查找樹結(jié)構(gòu) 對每個節(jié)點都需要先計算最佳分裂方案，然后執(zhí)行分裂。對于數(shù)值型連續(xù)字段分裂的形式A=v。所以，可以先對數(shù)值型字段排序，假設(shè)排序后的結(jié)果為v1,v2,vn，因為分裂只會發(fā)生在兩個節(jié)點之間，所以有n-1種可能性。通常取中點(vi + vi+1)/2作為分裂點，從小到大依次取不同的split point，取Information Gain指標(biāo)最大

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

8、個屬性列表在每個結(jié)點處都進(jìn)行一遍掃描,費(fèi)時很多。SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹,即在決策樹的每一層只需對每個屬性列表掃描一次,就可以為當(dāng)前決策樹中每個葉子結(jié)點找到最優(yōu)分裂標(biāo)準(zhǔn)。SLIQ的剪枝算法MDL屬于遲滯剪枝(post-prunning)算法，通常的遲滯剪枝的數(shù)據(jù)源采用一個Training Set的一個子集或者與Training Set獨(dú)立的數(shù)據(jù)集進(jìn)行操作。SLIQ算法具體實現(xiàn)輸入與輸出：輸入與輸出采用下面的方案 輸入數(shù)據(jù) 包括訓(xùn)練集配置信息(決策樹大小) 輸出數(shù)據(jù) 包括用線性方式表示的二分決策樹算法的控制：算法的控制結(jié)構(gòu)是一個隊列，這個隊列存放當(dāng)前的所有葉子節(jié)點。這是為了控制廣度優(yōu)先

9、搜索的結(jié)束。當(dāng)隊列空時，說明所有的葉子都已經(jīng)被處理過，這時建樹算法結(jié)束。（1）數(shù)據(jù)準(zhǔn)備系統(tǒng)輸入是訓(xùn)練集，訓(xùn)練集是樣本向量(v1,v2,vn ：c)組成的集合，每個屬性對應(yīng)訓(xùn)練集的一列，訓(xùn)練集進(jìn)入以后，分成一個一個的屬性表：(Attribute List)(vi,i)| i=0i是屬性vi的記錄索引號，將所有類標(biāo)識放入類表，類表中的leaf字段指向該記錄對應(yīng)的決策樹的葉子，初始狀態(tài)下，所有記錄指向樹根，對屬性表進(jìn)行預(yù)排序，交換屬性值vi，同時交換I，生成有序的屬性表序列。排序完成后屬性表中的i是屬性值指向類表的指針。完成屬性表的排序后，數(shù)據(jù)初始化工作就完成。（2）計算最佳分裂當(dāng)完成數(shù)據(jù)預(yù)處理之后

10、 算法進(jìn)入往復(fù)的求最佳分裂指標(biāo)的階段。這一階段 經(jīng)過一次對所有屬性表的遍歷，可以找出所有葉子節(jié)點的最佳分裂方案，在這個階段有一個重要的結(jié)構(gòu)，類直方圖(class histogram)，它位于決策樹的每個頂點內(nèi)，存放每個節(jié)點當(dāng)前的類信息左、右子樹的每個類各擁有多少節(jié)點。當(dāng)前屬性A是數(shù)值型字段時 每次作遍歷時類直方圖亦隨之改變，隨時表征以當(dāng)前屬性A的當(dāng)前值v為閾值的節(jié)點分裂方式對葉子L的分裂狀況由Class Histogram即可算出某個分裂方案的gini值，完成對A的遍歷后，gini值最小既Information Gain最高的A的值就是用屬性A分裂的最佳閾值。新方案可以存入決策樹節(jié)點。當(dāng)前屬性

11、是離散型字段時，在遍歷過程中記錄下每個屬性值對應(yīng)的類的個數(shù)，遍歷完成后，利用貪心算法得到Information Gain最高的A的子集，即為所求的用A的分裂方案，新方案可以存入決策樹節(jié)點。對整個屬性表的每個屬性進(jìn)行一次完全的遍歷之后 對每個節(jié)點而言，最佳分裂方案包括用哪個屬性進(jìn)行分類以及分類的閾值是什么已經(jīng)形成。并且存放在決策樹的節(jié)點內(nèi)。（3）升級節(jié)點當(dāng)最佳分裂參數(shù)已經(jīng)存放在節(jié)點中以后，算法的下一步是創(chuàng)建子節(jié)點，執(zhí)行節(jié)點分裂(升級類表)。這一步的主要任務(wù)是對應(yīng)該分裂的類表進(jìn)行更改。（4）結(jié)果輸出算法生成的決策樹通過前序遍歷的方式存入輸出表。SLIQ的優(yōu)點有：（1）運(yùn)算速度快，對屬性值只作一次排

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

13、并到每個屬性列表中。這樣，在尋找當(dāng)前結(jié)點的最優(yōu)分裂標(biāo)準(zhǔn)時，遍歷每個屬性列表就不必參照其他信息。但是，對非分裂屬性的屬性列表進(jìn)行分裂變得很困難，需要用哈希表記錄下每個記錄屬于個孩子結(jié)點。SPRINT串行算法算法的基本步驟如下:Procedure BuildTree (S , A )(S:訓(xùn)練樣本集，A:分類屬性集合)初始化樣本集S，生成有序?qū)傩粤斜砗椭狈綀D，創(chuàng)建節(jié)點隊列，放人Nwhile隊列不為空從隊列中取出第一個節(jié)點Nif N純or為空then標(biāo)記為葉節(jié)點，continuefor N的每一個分割點F計算該節(jié)點F上的gini值，選出最佳分割點F* ,N長出分支節(jié)點N1,N2，放人隊列中.將該分割點的屬性列表分割，并用該列表的rids生成記錄所在節(jié)點的哈希表，用哈希表分割其他屬性列表，列表分割同時生成屬性直方圖。串行環(huán)境下，剛開始SPRINT比SLIQ時間消耗高一些，樣本繼續(xù)增加后，SLIQ時間消耗要比SPRINT高。在并行環(huán)境下采用并行算法，相同處理器時相應(yīng)時間SLIQ要大于SPRINT。SPRINT算法具備以下優(yōu)點:（1）訓(xùn)練樣本