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

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

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

訓(xùn)練：訓(xùn)練集——>特征選取——>訓(xùn)練——>分類(lèi)器

分類(lèi)：新樣本——>特征選取——>分類(lèi)——>判決 

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

（1）決策樹(shù) 

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

(2) KNN法(K-Nearest Neighbor)

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

KNN方法雖然從原理上也依賴(lài)于極限定理，但在類(lèi)別決策時(shí)，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本的不平衡問(wèn)題。另外，由于KNN方法主要靠周?chē)邢薜泥徑臉颖荆皇强颗袆e類(lèi)域的方法來(lái)確定所屬類(lèi)別的，因此對(duì)于類(lèi)域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。

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

該算法比較適用于樣本容量比較大的類(lèi)域的自動(dòng)分類(lèi)，而那些樣本容量較小的類(lèi)域采用這種算法比較容易產(chǎn)生誤分。 

(3) SVM法

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

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

(4) VSM法

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

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

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

(5) Bayes法

Bayes法是一種在已知先驗(yàn)概率與類(lèi)條件概率的情況下的模式分類(lèi)方法，待分樣本的分類(lèi)結(jié)果取決于各類(lèi)域中樣本的全體。

設(shè)訓(xùn)練樣本集分為M類(lèi)，記為C=｛c1，…，ci，…cM}，每類(lèi)的先驗(yàn)概率為P(ci)，i=1，2，…，M。當(dāng)樣本集非常大時(shí)，可以認(rèn)為P(ci)=ci類(lèi)樣本數(shù)/總樣本數(shù)。對(duì)于一個(gè)待分樣本X，其歸于cj類(lèi)的類(lèi)條件概率是P(X/ci)，則根據(jù)Bayes定理，可得到cj類(lèi)的后驗(yàn)概率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)是最大后驗(yàn)概率判決準(zhǔn)則，將式(1)代入式(2)，則有：

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

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

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

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

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

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

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

分類(lèi)是數(shù)據(jù)挖掘中的一個(gè)重要課題。分類(lèi)的目的是學(xué)會(huì)一個(gè)分類(lèi)函數(shù)或分類(lèi)模型（也常常稱(chēng)作分類(lèi)器），該模型能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)映射到給定類(lèi)別中的某一個(gè)。分類(lèi)可用于提取描述重要數(shù)據(jù)類(lèi)的模型或預(yù)測(cè)未來(lái)的數(shù)據(jù)趨勢(shì)。

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

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

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

預(yù)測(cè)準(zhǔn)確度：預(yù)測(cè)準(zhǔn)確度是用得最多的一種比較尺度，特別是對(duì)于預(yù)測(cè)型分類(lèi)任務(wù)，目前公認(rèn)的方法是10番分層交叉驗(yàn)證法。

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

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

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

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

2.1 ID3和C4.5算法

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

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

2.2 SLIQ算法

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

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

gini(S) = 1 – ∑pj*pj

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

區(qū)別于一般的決策樹(shù) SLIQ采用二分查找樹(shù)結(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的所有可能的值，分裂測(cè)試將要取遍S的所有子集S’。尋找當(dāng)分裂成S’和S-S’兩塊時(shí)的gini指標(biāo)，取到gini最小的時(shí)候，就是最佳分裂方法。顯然，這是一個(gè)對(duì)集合S的所有子集進(jìn)行遍歷的過(guò)程共需要計(jì)算2|S| 次，代價(jià)也是很大的。

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

在C4.5中,樹(shù)的構(gòu)造是按照深度優(yōu)先策略完成的,需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描,費(fèi)時(shí)很多。SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹(shù),即在決策樹(shù)的每一層只需對(duì)每個(gè)屬性列表掃描一次,就可以為當(dāng)前決策樹(shù)中每個(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ù)大小) 輸出數(shù)據(jù) 包括用線性方式表示的二分決策樹(shù)

算法的控制：算法的控制結(jié)構(gòu)是一個(gè)隊(duì)列，這個(gè)隊(duì)列存放當(dāng)前的所有葉子節(jié)點(diǎn)。這是為了控制廣度優(yōu)先搜索的結(jié)束。當(dāng)隊(duì)列空時(shí)，說(shuō)明所有的葉子都已經(jīng)被處理過(guò)，這時(shí)建樹(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)，將所有類(lèi)標(biāo)識(shí)放入類(lèi)表，類(lèi)表中的leaf字段指向該記錄對(duì)應(yīng)的決策樹(shù)的葉子，初始狀態(tài)下，所有記錄指向樹(shù)根，對(duì)屬性表進(jìn)行預(yù)排序，交換屬性值vi，同時(shí)交換I，生成有序的屬性表序列。排序完成后屬性表中的i是屬性值指向類(lèi)表的指針。完成屬性表的排序后，數(shù)據(jù)初始化工作就完成。

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

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

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

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

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

對(duì)整個(gè)屬性表的每個(gè)屬性進(jìn)行一次完全的遍歷之后 對(duì)每個(gè)節(jié)點(diǎn)而言，最佳分裂方案包括用哪個(gè)屬性進(jìn)行分類(lèi)以及分類(lèi)的閾值是什么已經(jīng)形成。并且存放在決策樹(shù)的節(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í)類(lèi)表)。這一步的主要任務(wù)是對(duì)應(yīng)該分裂的類(lèi)表進(jìn)行更改。

（4）結(jié)果輸出

算法生成的決策樹(shù)通過(guò)前序遍歷的方式存入輸出表。

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

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

2.3 SPRINT算法

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

初始化樣本集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長(zhǎng)出分支節(jié)點(diǎn)N1,N2，放人隊(duì)列中.將該分割點(diǎn)的屬性列表分割，并用該列表的rids生成記錄所在節(jié)點(diǎn)的哈希表，用哈希表分割其他屬性列表，列表分割同時(shí)生成屬性直方圖。

串行環(huán)境下，剛開(kāi)始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à)是原來(lái)的三倍。（2）節(jié)點(diǎn)分割要?jiǎng)?chuàng)建哈希表，加大系統(tǒng)負(fù)擔(dān)。（3）節(jié)點(diǎn)分割處理相對(duì)復(fù)雜。

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