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

數(shù)據(jù)倉庫，數(shù)據(jù)庫或者其它信息庫中隱藏著許多可以為商業(yè)、科研等活動的決策提供所需要的知識。分類與預測是兩種數(shù)據(jù)分析形式，它們可以用來抽取能夠描述重要數(shù)據(jù)集合或預測未來數(shù)據(jù)趨勢的模型。分類方法（Classification）用于預測數(shù)據(jù)對象的離散類別（Categorical Label）；預測方法（Prediction ）用于預測數(shù)據(jù)對象的連續(xù)取值。

分類技術在很多領域都有應用，例如可以通過客戶分類構造一個分類模型來對銀行貸款進行風險評估；當前的市場營銷中很重要的一個特點是強調客戶細分?？蛻纛悇e分析的功能也在于此，采用數(shù)據(jù)挖掘中的分類技術，可以將客戶分成不同的類別，比如呼叫中心設計時可以分為：呼叫頻繁的客戶、偶然大量呼叫的客戶、穩(wěn)定呼叫的客戶、其他，幫助呼叫中心尋找出這些不同種類客戶之間的特征，這樣的分類模型可以讓用戶了解不同行為類別客戶的分布特征；其他分類應用如文獻檢索和搜索引擎中的自動文本分類技術；安全領域有基于分類技術的入侵檢測等等。機器學習、專家系統(tǒng)、統(tǒng)計學和神經(jīng)網(wǎng)絡等領域的研究人員已經(jīng)提出了許多具體的分類預測方法。下面對分類流程作個簡要描述： 

訓練：訓練集——>特征選取——>訓練——>分類器

分類：新樣本——>特征選取——>分類——>判決 

最初的數(shù)據(jù)挖掘分類應用大多都是在這些方法及基于內存基礎上所構造的算法。目前數(shù)據(jù)挖掘方法都要求具有基于外存以處理大規(guī)模數(shù)據(jù)集合能力且具有可擴展能力。下面對幾種主要的分類方法做個簡要介紹： 

（1）決策樹 

決策樹歸納是經(jīng)典的分類算法。它采用自頂向下遞歸的各個擊破方式構造決策樹。樹的每一個結點上使用信息增益度量選擇測試屬性?？梢詮纳傻?a href='/map/jueceshu/' style='color:#000;font-size:inherit;'>決策樹中提取規(guī)則。

(2) KNN法(K-Nearest Neighbor)

KNN法即K最近鄰法，最初由Cover和Hart于1968年提出的，是一個理論上比較成熟的方法。該方法的思路非常簡單直觀：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計算復雜度，提高分類的效率。

該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。 

(3) SVM法

SVM法即支持向量機(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相對優(yōu)良的性能指標。該方法是建立在統(tǒng)計學習理論基礎上的機器學習方法。通過學習算法，SVM可以自動尋找出那些對分類有較好區(qū)分能力的支持向量，由此構造出的分類器可以最大化類與類的間隔，因而有較好的適應能力和較高的分準率。該方法只需要由各類域的邊界樣本的類別來決定最后的分類結果。

支持向量機算法的目的在于尋找一個超平面H(d),該超平面可以將訓練集中的數(shù)據(jù)分開，且與類域邊界的沿垂直于該超平面方向的距離最大，故SVM法亦被稱為最大邊緣(maximum margin)算法。待分樣本集中的大部分樣本不是支持向量，移去或者減少這些樣本對分類結果沒有影響，SVM法對小樣本情況下的自動分類有著較好的分類結果。 

(4) VSM法

VSM法即向量空間模型(Vector Space Model)法，由Salton等人于60年代末提出。這是最早也是最出名的信息檢索方面的數(shù)學模型。其基本思想是將文檔表示為加權的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通過計算文本相似度的方法來確定待分樣本的類別。當文本被表示為空間向量模型的時候，文本的相似度就可以借助特征向量之間的內積來表示。

在實際應用中，VSM法一般事先依據(jù)語料庫中的訓練樣本和分類體系建立類別向量空間。當需要對一篇待分樣本進行分類的時候，只需要計算待分樣本和每一個類別向量的相似度即內積，然后選取相似度最大的類別作為該待分樣本所對應的類別。

由于VSM法中需要事先計算類別的空間向量，而該空間向量的建立又很大程度的依賴于該類別向量中所包含的特征項。根據(jù)研究發(fā)現(xiàn)，類別中所包含的非零特征項越多，其包含的每個特征項對于類別的表達能力越弱。因此，VSM法相對其他分類方法而言，更適合于專業(yè)文獻的分類。 

(5) Bayes法

Bayes法是一種在已知先驗概率與類條件概率的情況下的模式分類方法，待分樣本的分類結果取決于各類域中樣本的全體。

設訓練樣本集分為M類，記為C=｛c1，…，ci，…cM}，每類的先驗概率為P(ci)，i=1，2，…，M。當樣本集非常大時，可以認為P(ci)=ci類樣本數(shù)/總樣本數(shù)。對于一個待分樣本X，其歸于cj類的類條件概率是P(X/ci)，則根據(jù)Bayes定理，可得到cj類的后驗概率P(ci/X)：

P(ci/x)=P(x/ci)·P(ci)/P(x)(1)

若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，則有x∈ci(2)

式(2)是最大后驗概率判決準則，將式(1)代入式(2)，則有：

若P(x/ci)P(ci)=Maxj［P(x/cj)P(cj)］，i=1，2，…，M，j=1，2，…，M，則x∈ci

這就是常用到的Bayes分類判決準則。經(jīng)過長期的研究，Bayes分類方法在理論上論證得比較充分，在應用上也是非常廣泛的。

Bayes方法的薄弱環(huán)節(jié)在于實際情況下，類別總體的概率分布和各類樣本的概率分布函數(shù)(或密度函數(shù))常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達文本的主題詞相互獨立，這樣的條件在實際文本中一般很難滿足，因此該方法往往在效果上難以達到理論上的最大值。 

（6）神經(jīng)網(wǎng)絡

神經(jīng)網(wǎng)絡分類算法的重點是構造閾值邏輯單元，一個值邏輯單元是一個對象，它可以輸入一組加權系數(shù)的量，對它們進行求和，如果這個和達到或者超過了某個閾值，輸出一個量。如有輸入值X1, X2, …, Xn 和它們的權系數(shù)：W1, W2, …, Wn，求和計算出的 Xi*Wi ，產生了激發(fā)層 a = (X1 * W1)+(X2 * W2)+…+(Xi * Wi)+…+ (Xn * Wn)，其中Xi 是各條記錄出現(xiàn)頻率或其他參數(shù)，Wi是實時特征評估模型中得到的權系數(shù)。神經(jīng)網(wǎng)絡是基于經(jīng)驗風險最小化原則的學習算法，有一些固有的缺陷，比如層數(shù)和神經(jīng)元個數(shù)難以確定，容易陷入局部極小，還有過學習現(xiàn)象，這些本身的缺陷在SVM算法中可以得到很好的解決

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

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

分類是數(shù)據(jù)挖掘中的一個重要課題。分類的目的是學會一個分類函數(shù)或分類模型（也常常稱作分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。分類可用于提取描述重要數(shù)據(jù)類的模型或預測未來的數(shù)據(jù)趨勢。

分類可描述如下：輸入數(shù)據(jù)，或稱訓練集（training set）是一條條記錄組成的。每一條記錄包含若干條屬性（attribute），組成一個特征向量。訓練集的每條記錄還有一個特定的類標簽（類標簽）與之對應。該類標簽是系統(tǒng)的輸入，通常是以往的一些經(jīng)驗數(shù)據(jù)。一個具體樣本的形式可為樣本向量：(v1,v2,…,…vn:c)。在這里vi表示字段值，c表示類別。

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

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

預測準確度：預測準確度是用得最多的一種比較尺度，特別是對于預測型分類任務，目前公認的方法是10番分層交叉驗證法。

計算復雜度：計算復雜度依賴于具體的實現(xiàn)細節(jié)和硬件環(huán)境，在數(shù)據(jù)挖掘中，由于操作對象是巨量的數(shù)據(jù)庫，因此空間和時間的復雜度問題將是非常重要的一個環(huán)節(jié)。

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

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

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

2.1 ID3和C4.5算法

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

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

2.2 SLIQ算法

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

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

gini(S) = 1 – ∑pj*pj

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

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

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

對于離散型字段(categorical attribute)，設S(A)為A的所有可能的值，分裂測試將要取遍S的所有子集S’。尋找當分裂成S’和S-S’兩塊時的gini指標，取到gini最小的時候，就是最佳分裂方法。顯然，這是一個對集合S的所有子集進行遍歷的過程共需要計算2|S| 次，代價也是很大的。

SLIQ算法對此采用了預排序的技術,以便能夠消除在決策樹的每個結點對數(shù)據(jù)集進行排序的需要。所謂預排序,就是針對每個屬性的取值,把所有的記錄按照從小到大的順序進行排序。

在C4.5中,樹的構造是按照深度優(yōu)先策略完成的,需要對每個屬性列表在每個結點處都進行一遍掃描,費時很多。SLIQ采用廣度優(yōu)先策略構造決策樹,即在決策樹的每一層只需對每個屬性列表掃描一次,就可以為當前決策樹中每個葉子結點找到最優(yōu)分裂標準。

SLIQ的剪枝算法MDL屬于遲滯剪枝(post-prunning)算法，通常的遲滯剪枝的數(shù)據(jù)源采用一個Training Set的一個子集或者與Training Set獨立的數(shù)據(jù)集進行操作。

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

輸入與輸出：輸入與輸出采用下面的方案 輸入數(shù)據(jù) 包括訓練集配置信息(決策樹大小) 輸出數(shù)據(jù) 包括用線性方式表示的二分決策樹

算法的控制：算法的控制結構是一個隊列，這個隊列存放當前的所有葉子節(jié)點。這是為了控制廣度優(yōu)先搜索的結束。當隊列空時，說明所有的葉子都已經(jīng)被處理過，這時建樹算法結束。

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

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

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

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

（2）計算最佳分裂

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

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

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

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

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

（3）升級節(jié)點

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

（4）結果輸出

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

SLIQ的優(yōu)點有：（1）運算速度快，對屬性值只作一次排序。（2）利用整個訓練集的所有數(shù)據(jù)，不作取樣處理，不喪失精確度。（3）輕松處理磁盤常駐的大型訓練集，適合處理數(shù)據(jù)倉庫的海量歷史數(shù)據(jù)。（4）更快的更小的目標樹。（5）低代價的MDL剪枝算法。

SLIQ的存在的缺點有：（1）由于需要將類別列表存放于內存,而類別列表的長度與訓練集的長度是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。（2）由于采用了預排序技術,而排序算法的復雜度本身并不是與記錄個數(shù)成線性關系,因此使得SLIQ算法不可能達到隨記錄數(shù)目增長的線性可擴展性。

2.3 SPRINT算法

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

SPRINT串行算法

算法的基本步驟如下:

Procedure BuildTree (S , A )

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

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

while隊列不為空

從隊列中取出第一個節(jié)點N

if N純or為空then

標記為葉節(jié)點，continue

for N的每一個分割點F

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

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

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

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

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