數據挖掘中的基于決策樹的分類方法

1 分類的概念及分類器的評判

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

分類的目的是：分析輸入數據，通過在訓練集中的數據表現出來的特性，為每一個類找到一種準確的描述或者模型。這種描述常常用謂詞表示。由此生成的類描述用來對未來的測試數據進行分類。盡管這些未來的測試數據的類標簽是未知的，我們仍可以由此預測這些新數據所屬的類。注意是預測，而不能肯定。我們也可以由此對數據中的每一個類有更好的理解。也就是說：我們獲得了對這個類的知識。

對分類器的好壞有三種評價或比較尺度：

預測準確度：預測準確度是用得最多的一種比較尺度，特別是對于預測型分類任務，目前公認的方法是10番分層交叉驗證法。
計算復雜度：計算復雜度依賴于具體的實現細節和硬件環境，在數據挖掘中，由于操作對象是巨量的數據庫，因此空間和時間的復雜度問題將是非常重要的一個環節。

模型描述的簡潔度：對于描述型的分類任務，模型描述越簡潔越受歡迎；例如，采用規則表示的分類器構造法就更有用。

分類技術有很多，如決策樹、貝葉斯網絡、神經網絡、遺傳算法、關聯規則等。本文重點是詳細討論決策樹中相關算法。

2 基于決策樹的數據分類算法及其性能

2.1 ID3和C4.5算法

決策樹技術是用于分類和預測的主要技術，決策樹學習是以實例為基礎的歸納學習算法。它著眼于從一組無次序、無規則的事例中推理除決策樹表示形式的分類規則。它采用自頂向下的遞歸方式，在決策樹的內部節點進行屬性值的比較并根據不同屬性判斷從該節點向下的分支，然后進行剪枝，最后在決策樹的葉節點得到結論。所以從根到葉節點就對應著一條合取規則，整棵樹就對應著一組析取表達式規則?；?a href='/map/jueceshu/' style='color:#000;font-size:inherit;'>決策樹的分類有很多實現算法。ID3和C4.5是較早提出并普遍使用的決策樹算法。

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

2.2 SLIQ算法

SLIQ算法對C4.5決策樹分類算法的實現方法進行了改進。

一般決策樹中，使用信息量作為評價節點分裂質量的參數，SLIQ算法中使用gini指標代替信息量，gini指標比信息量性能更好，且計算方便，對數據集包含n個類的數據集S，gini(S)定義為：

gini(S) = 1 - ∑pj*pj

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

區別于一般的決策樹 SLIQ采用二分查找樹結構 對每個節點都需要先計算最佳分裂方案，然后執行分裂。

對于數值型連續字段分裂的形式A<=v。所以，可以先對數值型字段排序，假設排序后的結果為v1,v2,…,…vn，因為分裂只會發生在兩個節點之間，所以有n-1種可能性。通常取中點(vi + vi+1)/2作為分裂點，從小到大依次取不同的split point，取Information Gain指標最大(gini最小)的一個就是分裂點,因為每個節點都需要排序，所以這項操作的代價極大。

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

在C4.5中,樹的構造是按照深度優先策略完成的,需要對每個屬性列表在每個結點處都進行一遍掃描,費時很多。SLIQ采用廣度優先策略構造決策樹,即在決策樹的每一層只需對每個屬性列表掃描一次,就可以為當前決策樹中每個葉子結點找到最優分裂標準。
SLIQ的剪枝算法MDL屬于遲滯剪枝(post-prunning)算法，通常的遲滯剪枝的數據源采用一個Training Set的一個子集或者與Training Set獨立的數據集進行操作。

SLIQ算法具體實現

輸入與輸出：輸入與輸出采用下面的方案 輸入數據包括訓練集配置信息(決策樹大小) 輸出數據 包括用線性方式表示的二分決策樹
算法的控制：算法的控制結構是一個隊列，這個隊列存放當前的所有葉子節點。這是為了控制廣度優先搜索的結束。當隊列空時，說明所有的葉子都已經被處理過，這時建樹算法結束。

（1）數據準備

系統輸入是訓練集，訓練集是樣本向量(v1,v2,…,…vn ：c)組成的集合，每個屬性對應訓練集的一列，訓練集進入以后，分成一個一個的屬性表：

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

i是屬性vi的記錄索引號，將所有類標識放入類表，類表中的leaf字段指向該記錄對應的決策樹的葉子，初始狀態下，所有記錄指向樹根，對屬性表進行預排序，交換屬性值vi，同時交換I，生成有序的屬性表序列。排序完成后屬性表中的i是屬性值指向類表的指針。完成屬性表的排序后，數據初始化工作就完成。

（2）計算最佳分裂

當完成數據預處理之后 算法進入往復的求最佳分裂指標的階段。這一階段 經過一次對所有屬性表的遍歷，可以找出所有葉子節點的最佳分裂方案，在這個階段有一個重要的結構，類直方圖(class histogram)，它位于決策樹的每個頂點內，存放每個節點當前的類信息——左、右子樹的每個類各擁有多少節點。

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

當前屬性是離散型字段時，在遍歷過程中記錄下每個屬性值對應的類的個數，遍歷完成后，利用貪心算法得到Information Gain最高的A的子集，

即為所求的用A的分裂方案，新方案可以存入決策樹節點。

對整個屬性表的每個屬性進行一次完全的遍歷之后 對每個節點而言，最佳分裂方案包括用哪個屬性進行分類以及分類的閾值是什么已經形成。并且存放在決策樹的節點內。

（3）升級節點

當最佳分裂參數已經存放在節點中以后，算法的下一步是創建子節點，執行節點分裂(升級類表)。這一步的主要任務是對應該分裂的類表進行更改。

（4）結果輸出

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

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

2.3 SPRINT算法

為了減少數據量，SPRINT算法改進了SLIQ決策樹算法實現時的數據結構，去掉駐留于內存的類別列表，將其合并到每個屬性列表中。這樣，在尋找當前結點的最優分裂標準時，遍歷每個屬性列表就不必參照其他信息。但是，對非分裂屬性的屬性列表進行分裂變得很困難，需要用哈希表記錄下每個記錄屬于個孩子結點。

SPRINT串行算法

算法的基本步驟如下:

Procedure BuildTree (S , A )

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

初始化樣本集S，生成有序屬性列表和直方圖，創建節點隊列，放人N

while隊列不為空

從隊列中取出第一個節點N

if N純or為空then

標記為葉節點，continue

for N的每一個分割點F

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

串行環境下，剛開始SPRINT比SLIQ時間消耗高一些，樣本繼續增加后，SLIQ時間消耗要比SPRINT高。在并行環境下采用并行算法，相同處理器時相應時間SLIQ要大于SPRINT。

SPRINT算法具備以下優點:（1）訓練樣本量不受內存限制。（2）具有優秀的伸縮性、加速性和擴容性。（3）并行實現容易，效率高。

SPRINT算法具備以下缺點:（1）使用屬性列表，存儲代價是原來的三倍。（2）節點分割要創建哈希表，加大系統負擔。（3）節點分割處理相對復雜。

以上是幾種常用的基于決策樹的分類算法，隨著算法研究的進行，出現了許多其他基于決策樹的算法，它們與神經網絡、遺傳算法等技術結合，從不同的方面對算法進行了提高。相信以后會出現更多效率更好、準確度更高的算法。