管理信息化數(shù)據(jù)倉(cāng)數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘分類規(guī)則

管理信息化數(shù)據(jù)倉(cāng)數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘分類規(guī)則第9章分類規(guī)則挖掘與預(yù)測(cè)第9章分類規(guī)則挖掘與預(yù)測(cè)主要內(nèi)容分類與預(yù)測(cè)的基本概念決策樹方法分類規(guī)則挖掘的ID3算法其他分類規(guī)則挖掘算法分類規(guī)則的評(píng)估微軟決策樹及其應(yīng)用9.1分類與預(yù)測(cè)的基本概念1.什么是分類第9章分類規(guī)則挖掘與預(yù)測(cè)數(shù)據(jù)分類（dataclassfication）是數(shù)據(jù)挖掘的主要內(nèi)容之一，主要是通過分析訓(xùn)練數(shù)據(jù)樣本，產(chǎn)生關(guān)于類別的精確描述。這種類別通常由分類規(guī)則組成，可以用來對(duì)未來的數(shù)據(jù)進(jìn)行分類和預(yù)測(cè)。數(shù)據(jù)分類（dataclassfication）是一個(gè)兩個(gè)步驟的過程：第1步：建立一個(gè)模型，描述給定的數(shù)據(jù)類集或概念集（簡(jiǎn)稱訓(xùn)練集）。通過分析由屬性描述的數(shù)據(jù)庫(kù)元組來構(gòu)造模型。每個(gè)元組屬于一個(gè)預(yù)定義的類，由類標(biāo)號(hào)屬性確定。用于建立模型的元組集稱為訓(xùn)練數(shù)據(jù)集，其中每個(gè)元組稱為訓(xùn)練樣本。由于給出了類標(biāo)號(hào)屬性，因此該步驟又稱為有指導(dǎo)的學(xué)習(xí)。如果訓(xùn)練樣本的類標(biāo)號(hào)是未知的，則稱為無指導(dǎo)的學(xué)習(xí)（聚類）。學(xué)習(xí)模型可用分類規(guī)則、決策樹和數(shù)學(xué)公式的形式給出。第2步：使用模型對(duì)數(shù)據(jù)進(jìn)行分類。包括評(píng)估模型的分類準(zhǔn)確性以及對(duì)類標(biāo)號(hào)未知的元組按模型進(jìn)行分類。第9章分類規(guī)則挖掘與預(yù)測(cè)分類規(guī)則（a）學(xué)習(xí)新數(shù)據(jù)分（b）測(cè)試數(shù)圖9-1數(shù)據(jù)分類過程2.常用的分類規(guī)則挖掘方法分類規(guī)則挖掘有著廣泛的應(yīng)用前景。對(duì)于分類規(guī)則的挖掘通常有以下幾種方法，不同的方法適用于不同特點(diǎn)的數(shù)據(jù)：決策樹方法第9章分類規(guī)則挖掘與預(yù)測(cè)貝葉斯方法人工神經(jīng)網(wǎng)絡(luò)方法約略集方法遺傳算法典型的分類規(guī)則挖掘算法有：ID3C4.5DBlearn等3.什么是預(yù)測(cè)預(yù)測(cè)（prediction）是構(gòu)造和使用模型評(píng)估無標(biāo)號(hào)樣本類，或評(píng)估給定的樣本可能具有的屬性或區(qū)間值。分類和回歸是兩類主要的預(yù)測(cè)問題。分類是預(yù)測(cè)離散值，回歸用于預(yù)測(cè)連續(xù)或第9章分類規(guī)則挖掘與預(yù)測(cè)有序值。4.分類和預(yù)測(cè)數(shù)據(jù)的預(yù)處理數(shù)據(jù)清理：使用平滑技術(shù)消除或減少噪聲；處理空缺值。相關(guān)性分析：刪除與分類或預(yù)測(cè)無關(guān)的屬性；刪除冗余屬性。數(shù)據(jù)變換：使用概念分層將數(shù)據(jù)概化到高的層次；連續(xù)值屬性概化為離散區(qū)間；數(shù)據(jù)規(guī)范化，即將某一屬性的所有值按比例縮放，使其落入指定的區(qū)間。5.分類方法的評(píng)估標(biāo)準(zhǔn)準(zhǔn)確率：模型正確預(yù)測(cè)新數(shù)據(jù)類標(biāo)號(hào)的能力。速度：產(chǎn)生和使用模型花費(fèi)的時(shí)間。健壯性：有噪聲數(shù)據(jù)或空缺值數(shù)據(jù)時(shí)模型正確分類或預(yù)測(cè)的能力。伸縮性：對(duì)于給定的大量數(shù)據(jù)，有效地構(gòu)造模型的能力。第9章分類規(guī)則挖掘與預(yù)測(cè)可解釋性：學(xué)習(xí)模型提供的理解和觀察的層次。9.2決策樹方法決策樹方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個(gè)優(yōu)點(diǎn)是它能夠處理連續(xù)屬性。還有CART算法和Assistant算法也是比較有名的決策樹方法。1.什么是決策樹決策樹（DecisionTree）又稱為判定樹，是運(yùn)用于分類的一種樹結(jié)構(gòu)。其中的每個(gè)內(nèi)部結(jié)點(diǎn)（internalnode）代表對(duì)某個(gè)屬性的一次測(cè)試，每條邊代表一個(gè)測(cè)試結(jié)果，葉結(jié)點(diǎn)（leaf）代表某個(gè)類（class）或者類的分布（classdistribution立的一棵決策樹，從中可以看到?jīng)Q策樹的基本組成部分：決策結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)。第9章分類規(guī)則挖掘與預(yù)測(cè)〖例〗圖9-2給出了一個(gè)商業(yè)上使用的決策樹的例子。它表示了一個(gè)關(guān)心電子產(chǎn)品的用戶是否會(huì)購(gòu)買PC（buys_puter）的知識(shí)，用它可以預(yù)測(cè)某條記錄（某個(gè)人）的購(gòu)買意向。圖9-2buys_puter的決策樹這棵決策樹對(duì)銷售記錄進(jìn)行分類，指出一個(gè)電子產(chǎn)品消費(fèi)者是否會(huì)購(gòu)買一臺(tái)計(jì)算機(jī)“buys_puter”。每個(gè)內(nèi)部結(jié)點(diǎn)（方形框）代表對(duì)某個(gè)屬性的一次檢測(cè)。每個(gè)葉結(jié)點(diǎn)（橢圓框）代表一個(gè)類：buys_puters=yes或者buys_puters=no在這個(gè)例子中，樣本向量為：（age,student,credit_rating;buys_puters）被決策數(shù)據(jù)的格式為:第9章分類規(guī)則挖掘與預(yù)測(cè)（age,student,credit_rating）輸入新的被決策的記錄，可以預(yù)測(cè)該記錄隸屬于哪個(gè)類。2.使用決策樹進(jìn)行分類構(gòu)造決策樹是采用自上而下的遞歸構(gòu)造方法。以多叉樹為例，如果一個(gè)訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)有幾歸處理各個(gè)子集。反之，則作為葉結(jié)點(diǎn)。（非葉結(jié)點(diǎn)）一般表示為一個(gè)邏輯判斷，如形式為(a=b)的邏輯判斷，其中a是屬性，b是該屬性的某ID3有幾個(gè)屬性值，就有幾條邊。樹的葉結(jié)點(diǎn)都是類別標(biāo)記。使用決策樹進(jìn)行分類分為兩步：第9章分類規(guī)則挖掘與預(yù)測(cè)第1獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)的過程。第2屬性值，直到到達(dá)某個(gè)葉結(jié)點(diǎn)，從而找到該記錄所在的類。問題的關(guān)鍵是建立一棵決策樹。這個(gè)過程通常分為兩個(gè)階段：建樹（TreeBuilding）：決策樹建樹算法見下，可以看得出，這是一個(gè)遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝是目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。9.3分類規(guī)則挖掘的ID3算法由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹歸納（InductionofDecisionTreeID算法只能就兩類數(shù)據(jù)進(jìn)行挖掘（如正類和反第9章分類規(guī)則挖掘與預(yù)測(cè)ID算法可以挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說，對(duì)具有相同屬性的數(shù)據(jù)，其對(duì)應(yīng)的類必須是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。1.ID3算法的基本思想由訓(xùn)練數(shù)據(jù)集中全體屬性值生成的所有決策樹的集合稱為搜索空間，該搜索空間是針對(duì)某一特定問題而提出的。系統(tǒng)根據(jù)某個(gè)評(píng)價(jià)函數(shù)決定搜索空間中的哪一個(gè)決策樹是“最好的。評(píng)價(jià)函數(shù)一般依據(jù)分類的準(zhǔn)確度和樹的大小來決定決策樹的質(zhì)量。如果兩棵決策樹都能準(zhǔn)確地在測(cè)試集進(jìn)行分類，則選擇較簡(jiǎn)單的那棵。相對(duì)而言，決策樹越簡(jiǎn)單，則它對(duì)未知數(shù)據(jù)的預(yù)測(cè)性能越佳。尋找一棵“最好”的決策樹是一個(gè)NP完全問題。ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時(shí)保證找到一棵簡(jiǎn)單的決策樹—可能不是最簡(jiǎn)單的。第9章分類規(guī)則挖掘與預(yù)測(cè)ID3算法的基本思想描述如下：step1．任意選取一個(gè)屬性作為決策樹的根結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值創(chuàng)建樹的分支；step2．用這棵樹來對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行分類，如果一個(gè)葉結(jié)點(diǎn)的所有實(shí)例都屬于同一類，則以該類為標(biāo)記標(biāo)識(shí)此葉結(jié)點(diǎn)；如果所有的葉結(jié)點(diǎn)都有類標(biāo)記，則算法終止；step3．否則，選取一個(gè)從該結(jié)點(diǎn)到根路徑中沒有出現(xiàn)過的屬性為標(biāo)記標(biāo)識(shí)該結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值繼續(xù)創(chuàng)建樹的分支；重復(fù)算法步驟step2；這個(gè)算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡(jiǎn)單的。顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡(jiǎn)單的決策樹。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有最高信息量的屬性，也就是說，生成最少分支決策樹的那個(gè)屬性。2.ID3算法的描述第9章分類規(guī)則挖掘與預(yù)測(cè)算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹輸入：訓(xùn)練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹方法：（1）創(chuàng)建結(jié)點(diǎn)N；（2）ifsamples都在同一個(gè)類Cthen（3）返回N作為葉結(jié)點(diǎn)，用類C標(biāo)記；（4）ifattribute_list為空then（5）返回N作為葉結(jié)點(diǎn)，標(biāo)記samples中最普通的類；//多數(shù)表決（6）選擇attribute_list中具有最高信息增益的屬性test_attribute；//用信息增益作為屬性選擇第9章分類規(guī)則挖掘與預(yù)測(cè)度量（7）標(biāo)記結(jié)點(diǎn)N為test_attribute；（8）foreachtest_attribute中的已知值ai//劃分samples（9）由結(jié)點(diǎn)N生長(zhǎng)出一個(gè)條件為test_attribute＝ai的分枝；（10）設(shè)si為samples中test_attribute＝ai的樣本集合；//一個(gè)劃分（11）ifsi為空then（12）加上一個(gè)葉結(jié)點(diǎn)，標(biāo)記為標(biāo)記samples中最普通的類；//多數(shù)表決（13else加上一個(gè)由Generate_decision_tree（si,attribute_list-test_attribute）返回的結(jié)點(diǎn)；2.屬性選擇度量第9章分類規(guī)則挖掘與預(yù)測(cè)在Generate_decision_tree算法的Step6，算法需選擇attribute_list中具有最高信息增益的屬性test_attribute。ID3算法在樹的每個(gè)結(jié)點(diǎn)上以信息增量（informationgain）作為度量來選擇測(cè)試屬性。這種度量稱為屬性選擇度量或分裂的優(yōu)良性度量。選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點(diǎn)的測(cè)試屬性。該屬性使得對(duì)結(jié)果劃分中的樣本分類所需要的信息量最小，并確保找到一棵簡(jiǎn)單的（但不一定是最簡(jiǎn)單的）決策樹。InformationGain指標(biāo)的原理來自于信息論。1948年，香農(nóng)（C.E.Shannon）提出了信息論。其中給出了關(guān)于信息量（InformationEntropy是系統(tǒng)的平均信息量。設(shè)S是有s個(gè)訓(xùn)練樣本數(shù)據(jù)的集合，類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci（i=1,2,…,msi是類Ci中的樣本數(shù)，則對(duì)一個(gè)給定的訓(xùn)練樣本分類所需要的期望信息為：I(s1,s2,…,sm)＝－ΣMi=1pilog2(pi)第9章分類規(guī)則挖掘與預(yù)測(cè)其中pi是任意樣本屬于Ci的概率，可用si/s來估計(jì)。設(shè)屬性A具有k個(gè)不同值{a1,a2,…,ak}，則可用屬性A將S劃分為k個(gè)子集{S1,S2,…,Sk}，Sj中包含的樣本在屬性A上具有值aj。如果選擇A作為測(cè)試屬性，則這些子集對(duì)應(yīng)于由包含集合S的結(jié)點(diǎn)生長(zhǎng)出來的分枝。設(shè)sij是子集Sj中類Ci的樣本數(shù)，則按照A劃分成子集的熵為：E（A）＝ΣMi=1（（s1j+s2j+…+smj）/s1j）*I(s1,s2,…,sm)InformationGainA分類后的信息增益為：Gain(A)=I(s1,s2,…,sm)–E(A)InformationGainGain(A)第9章分類規(guī)則挖掘與預(yù)測(cè)這個(gè)最佳方案是用“貪心算法+深度優(yōu)先搜索”得到的。因?yàn)檫@是一個(gè)遞歸過程，所以僅僅需要討論對(duì)某個(gè)特定結(jié)點(diǎn)N的分裂方法。（1）分裂前設(shè)指向N的訓(xùn)練集為SmCi(fori=1,…,m)si是S中屬于類Ci的記錄的個(gè)數(shù)。那么分裂之前，系統(tǒng)的總熵：I(s1,s2,…,sm)=-∑Mi=1pilog2(pi)容易看出，總熵是屬于各個(gè)類的記錄的信息量的加權(quán)平均。（2）分裂后現(xiàn)在屬性A是帶有k個(gè)不同值的屬性{a1,a2,…ak}A可以把S分成k個(gè)子集{S1,S2,…,Sk}其中Sj={x|x∈S&x.A=aj}ASsij表示在Sj中類為Ci的記錄個(gè)數(shù)。那么，這時(shí)按A的每個(gè)屬性值（更一般的是取A的一個(gè)子集）進(jìn)行分裂后的信息量，也就第9章分類規(guī)則挖掘與預(yù)測(cè)是系統(tǒng)總熵為：E(A)=∑kj=1((s1j+s2j+..+smj)/s)*I(s1j+s2j+..+smj)((s1j+s2j+..+smj)/s)表示第j個(gè)子集的權(quán)重，s=|S|。子集Sj的信息量（子集的總熵）：I(s1j+s2j+..+smj)=-∑Mi=1pijlog2(pij)總熵E(A)是各個(gè)子集信息量的加權(quán)平均。算法計(jì)算每個(gè)屬性的信息增益，具有最高信息增益的屬性選擇作為給定訓(xùn)練數(shù)據(jù)集合S的測(cè)試屬性。創(chuàng)建一個(gè)結(jié)點(diǎn)，并以該屬性為標(biāo)記，對(duì)屬性的每一個(gè)值創(chuàng)建分枝，并據(jù)此劃分樣本。〖例〗顧客數(shù)據(jù)庫(kù)訓(xùn)練數(shù)據(jù)集如下表所示：RIDageinestudentcredit_ratingClass:Buys_puter1<=30highnofairno2<=30highnoexcellentno第9章分類規(guī)則挖掘與預(yù)測(cè)331…40highnofairyes4>40mediumnofairyes5>40lowyesfairyes6>40lowyesexcellentno731…40lowyesexcellentyes8<=30mediumnofairno9<=30lowyesfairyes10>40mediumyesfairyes11<=30mediumyesexcellentyes1231…40mediumnoexcellentyes1331…40highyesfairyes14>40mediumnoexcellentno計(jì)算每一個(gè)屬性的信息增益：Gain（age）=I（s2,s2）－E（age）=0.246第9章分類規(guī)則挖掘與預(yù)測(cè)Gain（ine）=0.029Gain（student）=0.151Gain（credit_rating）=0.048由于屬性age在所有屬性中具有最高的信息增益，因此它被選擇為測(cè)試屬性。創(chuàng)建一個(gè)以age為標(biāo)記的結(jié)點(diǎn)，并對(duì)每一個(gè)屬性值引出一個(gè)分枝。落在分枝age=“31…40”的樣本都屬于同一類“yes”,該分枝的端點(diǎn)應(yīng)該創(chuàng)建一個(gè)葉結(jié)點(diǎn)。inestudentcredit_ratingClasshighnofairnohighnoexcellentno第9章分類規(guī)則挖掘與預(yù)測(cè)mediumnofairnolowyesfairyesmediumyesexcellentyes3.剪枝和遲滯修剪。（1）先剪枝（pre-pruning）在建樹的過程中，當(dāng)滿足一定條件，例如InformationGain或者某些有效統(tǒng)計(jì)量達(dá)到某個(gè)預(yù)先設(shè)定的閾能僅僅存儲(chǔ)這些實(shí)例的概率分布函數(shù)。（2）后剪枝（pos-pruning）第9章分類規(guī)則挖掘與預(yù)測(cè)與建樹時(shí)的訓(xùn)練集獨(dú)立的訓(xùn)練數(shù)據(jù)進(jìn)入決策樹并到達(dá)葉結(jié)點(diǎn)時(shí)，訓(xùn)練數(shù)據(jù)的classlabel與葉結(jié)點(diǎn)的classlabel不同，這時(shí)稱為發(fā)生了分類錯(cuò)誤。當(dāng)樹建好之后，對(duì)每個(gè)內(nèi)部結(jié)點(diǎn)，算法通過每個(gè)枝條的出錯(cuò)率而該結(jié)點(diǎn)成為一片葉。出錯(cuò)率用與訓(xùn)練集數(shù)據(jù)獨(dú)立的測(cè)試數(shù)據(jù)校驗(yàn)。最終形成一棵錯(cuò)誤率盡可能小的決策樹。如果在測(cè)試集中出現(xiàn)了類交叉的情況，也就是說，在待挖掘的數(shù)據(jù)中出現(xiàn)矛盾和不一致的情況。則在算法步驟3中將出現(xiàn)這樣一種情況：在一個(gè)樹結(jié)點(diǎn)中，所有的實(shí)例并不屬于一個(gè)類卻找不到可以繼續(xù)分支的屬性。ID3使用以下兩種方案解決這個(gè)問題：①選擇在該結(jié)點(diǎn)中所占比例最大的類為標(biāo)記標(biāo)識(shí)該結(jié)點(diǎn)；②根據(jù)該結(jié)點(diǎn)中不同類的概率分布為標(biāo)記一一標(biāo)識(shí)該結(jié)點(diǎn)。如果在測(cè)試集中出現(xiàn)了某些錯(cuò)誤的實(shí)例，也就是說，在待挖掘的數(shù)據(jù)中，本來應(yīng)該屬于同一結(jié)點(diǎn)的數(shù)據(jù)因?yàn)槟承╁e(cuò)誤的屬性取值而繼續(xù)分支。則在最終生成的決策樹中可能出現(xiàn)分支過第9章分類規(guī)則挖掘與預(yù)測(cè)細(xì)和錯(cuò)誤分類的現(xiàn)象。ID3設(shè)置了一個(gè)閾值來解決這個(gè)問題：只有屬性的信息量超過這個(gè)閾值時(shí)才創(chuàng)建分支，否則以類標(biāo)志標(biāo)識(shí)該結(jié)點(diǎn)。該閾值的選取對(duì)決策樹的正確創(chuàng)建具有相當(dāng)?shù)闹匾浴Ｈ绻撝颠^小，可能沒有發(fā)揮應(yīng)有的作用；如果閾值過大，又可能刪除了應(yīng)該創(chuàng)建的分支。4.由決策樹提取分類規(guī)則可以提取由決策樹表示的分類規(guī)則，并以IF－THEN的形式表示。具體方法是：從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑創(chuàng)建一條分類規(guī)則，路徑上的每一個(gè)“屬性－值對(duì)為規(guī)則的前件（即IF部分）的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)為規(guī)則的后件（即THEN〖例〗對(duì)于buys_puter的決策樹可提取以下分類規(guī)則：IFage＝‘<=30’ANDstudent＝‘no’THENbuys_puter＝‘no’IFage＝‘<=30’ANDstudent＝‘yes’第9章分類規(guī)則挖掘與預(yù)測(cè)THENbuys_puter＝‘yes’IFage＝‘30…40’THENbuys_puter＝‘yes’IFage＝‘>40’ANDcredit_rating＝‘excellent’THENbuys_puter＝‘no’IFage＝‘>40’ANDcredit_rating＝‘fair’THENbuys_puter＝‘yes’5.ID3算法的改進(jìn)（1）離散化ID3算法對(duì)符號(hào)性屬性的知識(shí)挖掘比較簡(jiǎn)單，也就是說，該算法對(duì)離散性屬性的挖掘更為直觀。算法將針對(duì)屬性的所有符號(hào)創(chuàng)建決策樹分支。但是，如果屬性值是連續(xù)性的，如一個(gè)人的身高，體重等，如果針對(duì)屬性的所有不同的值創(chuàng)建決策數(shù)，則將由于決策樹過于龐大而使該算法失第9章分類規(guī)則挖掘與預(yù)測(cè)效。為了解決該問題，在用ID3算法挖掘具有連續(xù)性屬性的知識(shí)時(shí)，應(yīng)該首先把該連續(xù)性屬性離散化。最簡(jiǎn)單的方法就是把屬性值分成和兩段。如身高可以分為1米以下，1米以上或者分為1.5米以下，1.5米以上。如何選擇最佳的分段值呢？對(duì)任何一個(gè)屬性，其所有的取值在一個(gè)數(shù)據(jù)集中是有限的。假設(shè)該屬性取值為，則在這個(gè)集合中，一共存在m-1個(gè)分段值，ID3算法采用計(jì)算信息量的方法計(jì)算最佳的分段值，然后進(jìn)一步構(gòu)建決策樹。（2）屬性選擇度量ID3算法中采用信息增量作為屬性選擇度量，但它僅適合于具有許多值的屬性。已經(jīng)提出了一些其他的屬性選擇度量方法，如增益率，它考慮了每個(gè)屬性的概率。（3）空缺值處理常用的空缺值處理方法有：若屬性A有空缺值，則可用A的最常見值、平均值、樣本平均值等填第9章分類規(guī)則挖掘與預(yù)測(cè)充。（4）碎片、重復(fù)和復(fù)制處理通過反復(fù)地將數(shù)據(jù)劃分為越來越小的部分，決策樹歸納可能面臨碎片、重復(fù)和復(fù)制等問題。所謂碎片是指在一個(gè)給定的分枝中的樣本數(shù)太少，從而失去統(tǒng)計(jì)意義。解決的方法是：將分類屬性值分組，決策樹結(jié)點(diǎn)可以測(cè)試一個(gè)屬性值是否屬于給定的集合。另一種方法是創(chuàng)建二叉判定樹，在樹的結(jié)點(diǎn)上進(jìn)行屬性的布爾測(cè)試，從而可以減少碎片。當(dāng)一個(gè)屬性沿樹的一個(gè)給定的分枝重復(fù)測(cè)試時(shí)，將出現(xiàn)重復(fù)。復(fù)制是拷貝樹中已經(jīng)存在的子樹。通過由給定的屬性構(gòu)造新的屬性（即屬性構(gòu)造），可以防止以上問題的發(fā)生。（5）可伸縮性ID3算法對(duì)于相對(duì)較小的訓(xùn)練數(shù)據(jù)集是有效的，但對(duì)于現(xiàn)實(shí)世界中數(shù)據(jù)量很大的數(shù)據(jù)挖掘，有效性和可伸縮性將成為必須關(guān)注的問題。面臨數(shù)以百萬計(jì)的訓(xùn)練數(shù)據(jù)集，需要頻繁地將訓(xùn)練數(shù)據(jù)在主存和第9章分類規(guī)則挖掘與預(yù)測(cè)高速緩存換進(jìn)換出，從而使算法的性能變得低下。解決的方法是：將訓(xùn)練數(shù)據(jù)集劃分為子集，使得每個(gè)子集能夠放在內(nèi)存；然后由每個(gè)子集構(gòu)造一棵決策樹；最后，將每個(gè)子集得到的分類規(guī)則組合起來，得到輸出的分類規(guī)則。最近，已經(jīng)提出了一些強(qiáng)調(diào)可伸縮性的決策樹算法，如：SLIQ、SPRINT等。這兩種算法都使用了預(yù)排序技術(shù)，并采用了新的數(shù)據(jù)結(jié)構(gòu)，以利于構(gòu)造決策樹。ID3算法對(duì)大部分?jǐn)?shù)據(jù)集有效，但它不能挖掘域知識(shí)。同時(shí)，決策樹在計(jì)算機(jī)中存儲(chǔ)的方式?jīng)Q定了該分類規(guī)則相對(duì)于其他形式的分類規(guī)則（如公式）而言更晦澀難懂。因此，一般在算法結(jié)束后，需要把決策樹以用戶可視的方法顯示出來?！祭揭韵卤硭镜挠?xùn)練數(shù)據(jù)集為例，其中Salary為工資，Education為教育程度，Class為信用級(jí)20000作為Salary的分段值，則創(chuàng)建的決策樹如圖9-316000作為Salary的分段值，則創(chuàng)建的決策樹如圖9-4所示。第9章分類規(guī)則挖掘與預(yù)測(cè)SalaryEducationClass10，000高中一般40，000學(xué)士較好15，000學(xué)士一般75，000碩士較好18，000碩士較好訓(xùn)練數(shù)據(jù)集T圖9.3分段值為20，000的決策樹Salary>16000圖9.4分段值000的決策樹Y和圖9.4可以看出，Salary的分一樣，構(gòu)建的決策樹也不一樣。6.決策樹方法的評(píng)價(jià)第9章分類規(guī)則挖掘與預(yù)測(cè)與其他分類算法相比，決策樹有如下優(yōu)點(diǎn)：（1）速度快：計(jì)算量相對(duì)較小，且容易轉(zhuǎn)化成分類規(guī)則。只要沿著樹根向下一直走到葉，沿途的分裂條件就能夠唯一確定一條分類的謂詞。例如，沿著結(jié)點(diǎn)Age->CreditRating->no走下來就能得到一條謂詞：ifthereisaperson(age>40)and(creditratingisexcellent)thenhewillnotbuyaputer.（2）準(zhǔn)確性高：挖掘出的分類規(guī)則準(zhǔn)確性高，便于理解。一般決策樹的劣勢(shì)：（1Irvine機(jī)器學(xué)習(xí)知識(shí)庫(kù)中，最大可以允許的數(shù)據(jù)集僅僅為700KB，2000條記錄。而現(xiàn)代的數(shù)據(jù)倉(cāng)庫(kù)動(dòng)輒存儲(chǔ)幾個(gè)G-Bytes的海量數(shù)據(jù)。用以前的方法是顯然不行的。（2）為了處理大數(shù)據(jù)集或連續(xù)量的種種改進(jìn)算法（離散化、取樣）不僅增加了分類算法的額外開銷，而且降低了分類的準(zhǔn)確性。第9章分類規(guī)則挖掘與預(yù)測(cè)9.4分類規(guī)則挖掘的其他算法9.4.1分類規(guī)則挖掘的C4.5算法1.C4.5算法概述C4.5算法是ID3算法的擴(kuò)展，但是它比ID3算法改進(jìn)的部分是它能夠處理連續(xù)型的屬性。首先將連續(xù)型屬性離散化，把連續(xù)型屬性的值分成不同的區(qū)間，依據(jù)是比較各個(gè)屬性Gian值的大小。2."離散化"的方法把連續(xù)型屬性值"離散化"的具體方法是：1）尋找該連續(xù)型屬性的最小值，并把它賦值給MIN，尋找該連續(xù)型屬性的最大值，并把它賦值給MAX；2）設(shè)置區(qū)間[MIN，MAX]中的N個(gè)等分?jǐn)帱c(diǎn)Ai，它們分別是Ai=MIN+（（MAX–MIN）/N）*i第9章分類規(guī)則挖掘與預(yù)測(cè)其中，i=1,2,...,N3）分別計(jì)算把[MIN，Ai]和（Ai，MAXi=1,2,...,N）作為區(qū)間值時(shí)的Gain值，并進(jìn)行比較4）選取Gain值最大的Ak做為該連續(xù)型屬性的斷點(diǎn)，把屬性值設(shè)置為[MIN，Ak]和（Ak，MAX）兩個(gè)區(qū)間值。3.Gain函數(shù)決策樹是建立在信息理論（InformationTheory）的基礎(chǔ)上的，決策樹的方法循環(huán)地尋找某一標(biāo)準(zhǔn)，它能夠帶來與本次分類相關(guān)的最大信息。構(gòu)造好的決策樹的關(guān)鍵在于如何選擇好的屬性。對(duì)于同樣一組記錄集，可以有很多決策樹能符合這組記錄集。人們研究出，一般情況下，樹越小則樹的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹，關(guān)鍵在于選擇恰當(dāng)屬性。屬性選擇依賴于各種對(duì)例子子集的不純度（impurity）度量方法。不純度度量方法包括信息增益（informatingain信息增益比（gainratioGini-index、距離度量（distancemeasureJ-measure、G統(tǒng)計(jì)、χ2統(tǒng)計(jì)、證據(jù)權(quán)重（weightofevidenceMLPortogonalitymeasurerelevanceRelief第9章分類規(guī)則挖掘與預(yù)測(cè)C4.5informationgain選擇的目標(biāo)分類有關(guān)。（1）信息理論（InformationTheory）和熵（Entropy）A和B不純度。情況1.如果P（A=1和P（B=0，那么知道這個(gè)變量的值一定為A，不存在不純度，因此已知變量結(jié)果值不會(huì)帶來任何的信息。情況2.如果P（A=P（B=0.5，那么它的不純度明顯地高于P（A=0.1和P（B=0.9的情況。在這種情況下，已知變量的結(jié)果值就會(huì)攜帶信息。不純度的最佳評(píng)估方法是平均信息量，也就是信息熵（Entropy）：S=-Σ(pi*log(Pi))第9章分類規(guī)則挖掘與預(yù)測(cè)在上面的例子中，情況1和情況2的信息熵分別是：S1=-(1*log1+0*log0)=0S2=-(0.5*log0.5+0.5*log0.5)=0.301（2）信息增益（informationgain）信息增益是指信息熵的有效減少量（通常用"字節(jié)"量來分類。4.C4.5算法描述FunctionC4.5(R:asetofnon-goalattributessomeofwhichwithcontinuousvalues,C:thegoalattribute,S:atrainingset)returnsadecisiontree;begin第9章分類規(guī)則挖掘與預(yù)測(cè)IfSisemptythenreturnasinglenodewithvalueFailure;IfSconsistsofrecordsallwiththesamevalueforthegoalattributethenreturnasinglenodewiththatvalue;IfRisemptythenreturnasinglenodewithasvaluethemostfrequentofthevaluesofthegoalattributethatarefoundinrecordsofS;[notethatthentherewillbeerrors,thatis,recordsthatwillbeimproperlyclassified];forallattributesofR(Ri)doifvaluesofRiarecontinuousthenbegin第9章分類規(guī)則挖掘與預(yù)測(cè)LetA1betheminimumofRi;LetAmbethemaximumofRi;{m值手工設(shè)置}forjfrom2tom-1doAj=A1+j*(A1-Am)/m;LetAbethevaluepointofRiwithlargestGain(Ri,S)basedon{<=Aj,>Aj};end;LetDbetheattributewithlargestGain(D,S)amongattributesinR;Let{dj|j=1,2,..,m}bethevaluesofattributeD;Let{Sj|j=1,2,..,m}bethesubsetsofSconsistingrespectivelyofrecordswithvaluedjforattributeD;第9章分類規(guī)則挖掘與預(yù)測(cè)ReturnatreewithrootlabeledDandarcslabeledd1,d2,..,dmgoingrespectivelytothetreesC4.5(R-{D},C,S1),C4.5(R-{D},C,S2),..,C4.5(R-{D},C,Sm);endC4.5。missingvalues可能數(shù)據(jù)不準(zhǔn)確含有噪聲或者是錯(cuò)誤的；可能是缺少必須的數(shù)據(jù)造成了數(shù)據(jù)的不完整。另外決策樹技術(shù)本身也存在一些不足的地方，例如當(dāng)類別很多的時(shí)候，它的錯(cuò)誤就可能出現(xiàn)甚至很多。而且它對(duì)連續(xù)性的字段比較難作出準(zhǔn)確的預(yù)測(cè)。而且一般算法在分類的時(shí)候，只是根據(jù)一個(gè)屬性來分類的。overfitting測(cè)性能。剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹得到簡(jiǎn)化而變得更容易理解。另外，決策樹技術(shù)也可第9章分類規(guī)則挖掘與預(yù)測(cè)能產(chǎn)生子樹復(fù)制和碎片問題。在算法具體實(shí)現(xiàn)時(shí)必須考慮以上這些問題。9.4.2DBlearn算法1.DBlearn算法概述DBlearn算法用域知識(shí)生成基于關(guān)系數(shù)據(jù)庫(kù)的預(yù)定義子集的描述。DBlearn算法采用自底向上的搜索策略，使用以屬性層次形式的域知識(shí)，同時(shí)該算法使用了關(guān)系代數(shù)。該算法的事務(wù)集是一個(gè)關(guān)系表，即一個(gè)具有若干個(gè)屬性的n元組。系統(tǒng)采用關(guān)系表作為知識(shí)結(jié)構(gòu)：對(duì)每一類，它構(gòu)建一個(gè)關(guān)系表。這個(gè)關(guān)系表的屬性是實(shí)例集屬性的子集。一個(gè)元組可以看作是一個(gè)屬性值關(guān)聯(lián)的邏輯公式。搜索空間的開始是整個(gè)實(shí)例集，而最終目的是為了生成一個(gè)類描述的表。類描述表的大小不能超過用戶定義的閾值。閾值的大小決定了類描述表的大小。如果閾值太小，則生成的規(guī)則更簡(jiǎn)單，但同時(shí)也可以能丟失了一些有用的信息從而產(chǎn)生過度一第9章分類規(guī)則挖掘與預(yù)測(cè)般化的問題；如果閾值太大，則生成的規(guī)則比較詳細(xì)，但同時(shí)也可能產(chǎn)生沒有完全一般化和規(guī)則復(fù)雜的問題。一些屬性域被局部排序從而構(gòu)成一個(gè)層次結(jié)構(gòu)，每一個(gè)值都是該值所在層次下面全部值的一般化。在從關(guān)系表中生成分類規(guī)則時(shí)，DBlearn算法使用了兩個(gè)基本的算子：（1）刪除：如果在關(guān)系表中有屬性之間存在著關(guān)聯(lián)關(guān)系，則刪除直到只剩下彼此互不關(guān)聯(lián)的屬性。如年齡和出生年月這兩個(gè)屬性存在著年齡=現(xiàn)在時(shí)間—出生年月的關(guān)聯(lián)關(guān)系，因此必須刪除其中一個(gè)屬性，保留另一個(gè)屬性。（2）一般化：屬性的值被一般化為層次在它之上的值從而生成規(guī)則。如就年齡這個(gè)屬性而言，5歲以下都可以一般化為幼年，5-12歲可以一般化為童年等。在一個(gè)關(guān)系表上運(yùn)行以上兩個(gè)算子有可能產(chǎn)生完全一樣的元組，DBlearn算法通過刪除多第9章分類規(guī)則挖掘與預(yù)測(cè)余的元組來縮減關(guān)系表的大小從而得到類描述表。2.DBlearn算法描述DBlearn算法創(chuàng)建一個(gè)完全但不一定一致的分類規(guī)則，即該分類規(guī)則覆蓋所有的實(shí)例集（包括那些錯(cuò)誤的實(shí)例）。DBlearn算法描述如下：step1．從數(shù)據(jù)庫(kù)中選擇和任務(wù)相關(guān)的數(shù)據(jù)，如一個(gè)包含且只包含一類數(shù)據(jù)的數(shù)據(jù)表。step2．在該數(shù)據(jù)表上執(zhí)行一般化操作：如果在某個(gè)屬性上存在很多不同的值同時(shí)提供了一個(gè)更高級(jí)別的值，則該屬性被一般化為更高級(jí)別的值；如果在某個(gè)屬性上存在很多不同的值而不能提供一個(gè)更高級(jí)別的值，則該屬性被刪除。刪除重復(fù)的元組直到表的大小達(dá)到用戶定義的閾值。step3．簡(jiǎn)化結(jié)果。例如，如果該數(shù)據(jù)表上的一些元組除了一個(gè)屬性不一樣，其他的屬性值都是一模一樣的，而這個(gè)不一樣的屬性的取值可以一般化為一個(gè)更高層次的符號(hào)且這個(gè)屬性的取值范圍包含了該第9章分類規(guī)則挖掘與預(yù)測(cè)更高層次符號(hào)所代表的全部數(shù)據(jù)。則這些元組可以用一個(gè)元組代替，這個(gè)元組的屬性就是那個(gè)不一樣的屬性，它的值用那個(gè)符號(hào)表示。step4．把這個(gè)數(shù)據(jù)表轉(zhuǎn)換成公式。DBlearn算法是一個(gè)相對(duì)比較簡(jiǎn)單的分類規(guī)則挖掘算法，通過對(duì)屬性取值不斷進(jìn)行一般化操作從而最終獲得規(guī)則。在數(shù)據(jù)挖掘的過程中，該算法是域知識(shí)挖掘的一個(gè)典型例子。該算法經(jīng)過改進(jìn)可以挖掘那些包含噪聲數(shù)據(jù)的不純凈數(shù)據(jù)，同時(shí)可以做增量學(xué)習(xí)。9.4.3分類規(guī)則挖掘的OC1算法1.OC1算法概述OC1算法是ObliqueClassifier1的縮寫，即斜面分類1算法。它基于線性規(guī)劃的理論，以斜面超平面的思想為基礎(chǔ)，采用自頂向下的方法在條件屬性都是正實(shí)數(shù)類型的搜索空間創(chuàng)建斜面決策樹。第9章分類規(guī)則挖掘與預(yù)測(cè)在執(zhí)行OC1決策樹算法前，首先需要對(duì)搜索空間做凈化和清理工作以消除條件屬性間的函數(shù)依賴關(guān)系。凈化后的搜索空間中的每一個(gè)元組（記錄）可以看作是一個(gè)m+1維向量，其中(1im)對(duì)應(yīng)于第i個(gè)實(shí)數(shù)類型的條件屬性，c對(duì)應(yīng)于決策屬性（元組的類）。所有的條件屬性可以看作是一個(gè)m維向量?！级x〗是一個(gè)n維歐幾里得空間，設(shè)且，，則集合稱為中的一個(gè)超平面(n4)n=2時(shí)，集合確定一條直線；當(dāng)n=3時(shí)，集合確定一個(gè)平面。）〖定義〗一個(gè)超平面將分成兩個(gè)半空間，記為和。其中是中滿足的向量U構(gòu)成的半空間，是中滿足的向量U構(gòu)成的半空間?！级x〗一組單位向量(1，0，0，…，0)，(0，1，0，…，0)，…，(0，0，0，…，1)是中的一組基，用符號(hào)ξ，ξ，…ξ來表示該組單位向量?！级x〗設(shè)Г是一個(gè)超平面，如果=ξ，則Г是一個(gè)軸平行超平面，否則Г是一個(gè)斜面超平面。第9章分類規(guī)則挖掘與預(yù)測(cè)〖引理〗ID3決策樹的每一個(gè)結(jié)點(diǎn)等價(jià)于一個(gè)軸平行超平面。（證明略）大部分決策樹都是在每一個(gè)結(jié)點(diǎn)檢查某個(gè)屬性的值，或者對(duì)該數(shù)值屬性進(jìn)行分段檢查。因此，稱這種決策樹為“軸平行”決策樹?！级ɡ怼接贸矫姘岩唤Mn個(gè)的d維向量分成兩個(gè)半空間，如果nd+1則存在種方法；如果nd+1則存在種方法。（證明略）2.OC1算法的基本思想根據(jù)以上定理，最多存在有限種不同的決策樹。從理論上可以采用一種窮舉的方法來尋找一棵最優(yōu)決策樹，但在實(shí)際中這是不可行的算法。如前所述，尋找一棵最優(yōu)決策樹是一個(gè)NP完全問題。尋找一棵斜面超平面決策樹也是一個(gè)NP完全問題。因此，用OC1算法只能找到一棵比較小的決策樹，但不一定找到一棵最小的決策樹。第9章分類規(guī)則挖掘與預(yù)測(cè)OC1算法構(gòu)建一棵斜面超平面決策樹，其基本思想是：采用自頂向下的方法從條件屬性都是正實(shí)數(shù)類型的搜索空間開始創(chuàng)建斜面決策樹。如果搜索空間都屬于同一類，則算法終止，否則，在搜索空間中尋找一個(gè)“最佳”劃分搜索空間的斜面超平面，以此斜面超平面標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)，把搜索空間分成兩個(gè)半空間搜索空間（左子樹和右子樹）。反復(fù)在每個(gè)半空間搜索空間繼續(xù)尋找“最佳”斜面超平面直至算法終止。3.OC1算法描述step1．就當(dāng)前搜索空間創(chuàng)建決策樹的根結(jié)點(diǎn)，該結(jié)點(diǎn)的斜面超平面把搜索空間分為左半空間和右半空間；step2．用這棵樹來對(duì)搜索空間進(jìn)行分類，如果一個(gè)半空間的所有實(shí)例都屬于同一類，則以該類為標(biāo)記標(biāo)識(shí)此半空間；如果所有的半空間都有類標(biāo)記，則算法終止；step3．否則，分別以左半空間和右半空間為搜索空間，繼續(xù)創(chuàng)建根結(jié)點(diǎn)的左子樹和右子樹；重復(fù)算法第9章分類規(guī)則挖掘與預(yù)測(cè)步驟step1。OC1算法在每一個(gè)決策樹結(jié)點(diǎn)處的算法描述如下：/*尋找當(dāng)前搜索空間的“最佳”斜面超平面參數(shù)*/step1．尋找當(dāng)前搜索空間的“最佳”軸平行超平面，計(jì)算該軸平行超平面的純潔度；step2．隨機(jī)選擇一個(gè)斜面超平面，令“最佳”斜面超平面等于該斜面超平面，計(jì)算該斜面超平面的純潔度；step3．重復(fù)R次以下步驟：step3．1：重復(fù)執(zhí)行{依次振蕩斜面超平面的系數(shù)；}直到純潔度沒有進(jìn)一步改進(jìn)；step3．2：重復(fù)最多J次{第9章分類規(guī)則挖掘與預(yù)測(cè)選擇一個(gè)隨機(jī)方向，以該隨機(jī)方向改變斜面超平面；如果改變后的斜面超平面純潔度得到改進(jìn)，轉(zhuǎn)到步驟1；}step3．3：如果斜面超平面的純潔度小于“最佳”軸平行超平面的純潔度，令I(lǐng)=；否則令I(lǐng)=；step4．輸出純潔度I對(duì)應(yīng)的超平面。根據(jù)OC1算法描述可以看出，最重要的算法實(shí)現(xiàn)方式包括：(1)在決策數(shù)的每一個(gè)結(jié)點(diǎn)處如何生成一個(gè)斜面超平面；(2)計(jì)算超平面純潔度的方法；4.OC1算法的改進(jìn)（1）OC1算法改進(jìn)的基本思想OC1算法采用自頂向下的方法在條件屬性都是正實(shí)數(shù)類型的搜索空間創(chuàng)建斜面決策樹，如果條件屬性是第9章分類規(guī)則挖掘與預(yù)測(cè)符號(hào)型則不能適用該算法。關(guān)于符號(hào)型條件屬性的問題，很容易想到的解決辦法就是將其對(duì)應(yīng)到正實(shí)數(shù)類型上，再在其上采用OC1算法挖掘分類規(guī)則。如對(duì)條件屬性“性別，符號(hào)“男對(duì)應(yīng)“1”，符號(hào)“女”對(duì)應(yīng)“2”。針對(duì)不同的條件屬性，可以創(chuàng)建不同的編碼表，從而使OC1算法適用于符號(hào)型條件屬性的分類規(guī)則挖掘。但是這樣創(chuàng)建的編碼表具有很強(qiáng)的隨意性和主觀性，不能真正反應(yīng)數(shù)據(jù)的真實(shí)狀況。如在搜索空間T中，條件屬性“性別“男的實(shí)例占了97%為“女的實(shí)例只有3%。假設(shè)在編碼表中符號(hào)“男”對(duì)應(yīng)的編碼為“1000”，符號(hào)“女”對(duì)應(yīng)的編碼為“2000”，根據(jù)斜面超平面方程，把實(shí)例代入方程，可以得到表達(dá)式。顯然，盡管性別為“女”的實(shí)例在搜索空間的比例很小，但由于其對(duì)應(yīng)的編碼遠(yuǎn)遠(yuǎn)大于性別為“男”的實(shí)例，因此的取值只能在很小的范圍振蕩，從而影響進(jìn)一步選擇“最佳”斜面超平面。為了解決這個(gè)問題，可采用了一種基于分布的編碼方式。首先，掃描整個(gè)搜索空間（實(shí)例集），得到所第9章分類規(guī)則挖掘與預(yù)測(cè)有條件屬性為符號(hào)型的離散數(shù)據(jù)，創(chuàng)建編碼表，計(jì)算每個(gè)離散數(shù)據(jù)在該搜索空間出現(xiàn)的頻率。根據(jù)每個(gè)符號(hào)對(duì)應(yīng)的概率創(chuàng)建編碼表，可以有效地解決上文中所提出的問題。（2）OC1改進(jìn)算法的描述該部分的算法描述如下：step1．掃描搜索空間；step2．統(tǒng)計(jì)每一個(gè)符號(hào)屬性出現(xiàn)的次數(shù)；step3．計(jì)算每一個(gè)符號(hào)屬性的概率分布值；step4．生成編碼表；（3）結(jié)果分析下表給出了OC1算法和改進(jìn)的OC1算法在同一個(gè)搜索空間，同樣的隨機(jī)改進(jìn)系數(shù)（隨機(jī)跳躍次數(shù)5同樣的振蕩次數(shù)（20）下搜索的正確率比較分析。該搜索空間是基于塔斯馬尼亞州大學(xué)計(jì)算機(jī)科學(xué)系第9章分類規(guī)則挖掘與預(yù)測(cè)捐贈(zèng)的塔斯馬尼亞州(澳大利亞州名)基礎(chǔ)工業(yè)漁業(yè)部的鮑魚數(shù)據(jù)庫(kù)的數(shù)據(jù)倉(cāng)庫(kù)的一個(gè)采樣切片。由根據(jù)表可以看出，改進(jìn)的OC1算法在同樣的搜索空間和一樣的搜索系數(shù)情況下，決策樹的正確度無論是從平均值、最大值還是最小值進(jìn)行比較，都遠(yuǎn)遠(yuǎn)高于原算法，大大增強(qiáng)了決策樹（分類規(guī)則）的正確性和可預(yù)測(cè)性。次數(shù)OC1算法OC1改進(jìn)算法第一次0.760.84第二次0.700.77第三次0.660.80第四次0.730.78第五次0.690.78平均值0.7080.794第9章分類規(guī)則挖掘與預(yù)測(cè)最大值0.760.84最小值0.660.77表OC1算法和OC1改進(jìn)算法的比較9.4.4分類規(guī)則挖掘的SLIQ算法1.SLIQ算法概述SLIQSupervisedLearningInQuest,其中Quest是IBMAlmadenIBMAlmadenResearchCenter于1996年提出的一種高速可調(diào)節(jié)的數(shù)據(jù)挖掘分類算法。該算法通過預(yù)排序技術(shù)，著重解決當(dāng)訓(xùn)練集數(shù)據(jù)量巨大，無法全部放入內(nèi)存時(shí)，如何高速準(zhǔn)確地生成決策樹。能同時(shí)處理離散字段和連續(xù)字段。SLIQ的優(yōu)點(diǎn)：（1）運(yùn)算速度快，對(duì)屬性值只作一次排序。第9章分類規(guī)則挖掘與預(yù)測(cè)（2）利用整個(gè)訓(xùn)練集的所有數(shù)據(jù)，不做取樣處理，不喪失精確度。（3）輕松處理磁盤常駐的大型訓(xùn)練集，適合處理數(shù)據(jù)倉(cāng)庫(kù)的海量歷史數(shù)據(jù)。（4）更快的，更小的目標(biāo)樹。（5）低代價(jià)的MDL剪枝算法2.SLIQ算法的關(guān)鍵技術(shù)（1）可伸縮性指標(biāo)一般決策樹中，使用信息量作為評(píng)價(jià)結(jié)點(diǎn)分裂質(zhì)量的參數(shù)。SLIQ算法中，使用gini指標(biāo)（giniindex）代替信息量（Informationgini指標(biāo)比信息量性能更好，且計(jì)算方便。對(duì)數(shù)據(jù)集包含n個(gè)類的數(shù)據(jù)集S，gini（S）定義為：gini(S)=1–∑pj*pjpj是S中第j類數(shù)據(jù)的頻率。gini越小，InformationGain越大。第9章分類規(guī)則挖掘與預(yù)測(cè)（2）屬性的分裂方法區(qū)別于一般的決策樹，SLIQ采用二分查找樹結(jié)構(gòu)。對(duì)每個(gè)結(jié)點(diǎn)都需要先計(jì)算最佳分裂方案，然后執(zhí)行分裂。對(duì)于數(shù)值型連續(xù)字段（numericattribute）分裂的形式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)。從小到大依次取不同的splitpoint，取InformationGain指標(biāo)最大（gini裂點(diǎn)。因?yàn)槊總€(gè)結(jié)點(diǎn)都需要排序，所以這項(xiàng)操作的代價(jià)極大，降低排序成本成為一個(gè)重要的問題，SLIQ算法對(duì)排序有很好的解決方案，在后面對(duì)算法的描述中，將很詳細(xì)的看到這一點(diǎn)。對(duì)于離散型字段（categoricalattributeS（AA的所有可能的值，分裂測(cè)試將要取遍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ōu)化。第9章分類規(guī)則挖掘與預(yù)測(cè)（3）剪枝SLIQ的剪枝算法MDL屬于后剪枝（pos-prunning）[3.1.1.2]算法。通常的后剪枝的數(shù)據(jù)源采用一個(gè)TrainingSet的一個(gè)子集或者與TrainingSet獨(dú)立的數(shù)據(jù)集進(jìn)行操作。3.算法描述輸出數(shù)據(jù)：用線性表方式表示的二叉決策樹。算法：Createnode(root);Preparefordataofattributelistandclasslist;//數(shù)據(jù)準(zhǔn)備Enterqueue(root);//算法的控制結(jié)構(gòu)是一個(gè)隊(duì)列,該隊(duì)列存放當(dāng)前的所有葉結(jié)點(diǎn)While(notempty(queue))do第9章分類規(guī)則挖掘與預(yù)測(cè)EvaluateSplits();//計(jì)算最佳分裂foralltheleafnodesinthequeuedoUpdateLabels();//升級(jí)結(jié)點(diǎn)（創(chuàng)建子結(jié)點(diǎn)、執(zhí)行結(jié)點(diǎn)分裂）Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;//對(duì)應(yīng)該分裂的類表進(jìn)行更改Letthenewleafnodeenterthequeue;MDLpruning(root);//利用MDL算法進(jìn)行剪枝圖9-3計(jì)算分裂指標(biāo)的例子――當(dāng)前待分裂屬性Salaryclasshistogram下掃描，葉隊(duì)列里面的結(jié)點(diǎn)有N2,N3。圖9－5執(zhí)行結(jié)點(diǎn)分裂的例子――結(jié)點(diǎn)N3分裂成N6、N7，N3轉(zhuǎn)為內(nèi)部結(jié)點(diǎn)。9.4.5CART算法第9章分類規(guī)則挖掘與預(yù)測(cè)1.CART算法概述CART.這種探測(cè)出的知識(shí)又可用來構(gòu)造精確和可靠的預(yù)測(cè)模型，應(yīng)用于分類客戶、準(zhǔn)確直郵、偵測(cè)通信卡及信用卡詐騙和管理信用風(fēng)險(xiǎn)。技術(shù)上講，CART技術(shù)可稱為二元回歸分化技術(shù).因?yàn)楦Y(jié)點(diǎn)總是被分為兩個(gè)子結(jié)點(diǎn)并不斷分化，故稱為二元回歸。CART分析的技術(shù)要點(diǎn)包括一系列規(guī)則，可用于：（1）分裂樹點(diǎn)（2）確定何時(shí)結(jié)束分裂（3）為每一葉結(jié)點(diǎn)指定類型或預(yù)測(cè)值2.CART算法的分裂規(guī)則的選擇將一個(gè)結(jié)點(diǎn)分化成兩個(gè)子結(jié)點(diǎn)，CART總是問些“是”或“非”的問題。來分化根結(jié)點(diǎn)成二個(gè)子結(jié)點(diǎn)，以“是”為回答的案例歸入左子樹結(jié)點(diǎn)，而”否”為回答的案例歸為右子樹結(jié)點(diǎn)?！祭劫J款申請(qǐng)中風(fēng)險(xiǎn)分析。有訓(xùn)練集包含100個(gè)高風(fēng)險(xiǎn)和100個(gè)低風(fēng)險(xiǎn)的測(cè)試案例，構(gòu)造一棵二叉樹如圖1所示：100個(gè)高是否圖9-8貸款風(fēng)險(xiǎn)分析對(duì)于上圖中所得200年35個(gè)65個(gè)第9章分類規(guī)則挖掘與預(yù)測(cè)個(gè)案例，假設(shè)每個(gè)案例都有10個(gè)相關(guān)的數(shù)據(jù)變量，那么CART算法要比較200×10即2000種分裂的可能。接下來需要根據(jù)分裂質(zhì)量標(biāo)準(zhǔn)來評(píng)估每一個(gè)分化。最常用的一個(gè)標(biāo)準(zhǔn)是GINI標(biāo)準(zhǔn)，基本原則是根據(jù)該分化是否有效地分隔幾個(gè)類別。除了GINI標(biāo)準(zhǔn)外，還可以用Twoing標(biāo)準(zhǔn)和規(guī)則Twoing標(biāo)準(zhǔn)。其中GINI標(biāo)準(zhǔn)在樹成長(zhǎng)時(shí)明顯地包括費(fèi)用信息，而Twoing標(biāo)準(zhǔn)和規(guī)則Twoing標(biāo)準(zhǔn)則在計(jì)算風(fēng)險(xiǎn)和結(jié)點(diǎn)分配時(shí)使用費(fèi)用，或者把費(fèi)用信息合并入先驗(yàn)以應(yīng)用到模型。為了更有效地處理數(shù)據(jù)類型的選擇，也可以運(yùn)用連續(xù)自變變量的線性組合來作為分化的基礎(chǔ)?！八阉骱头只钡倪^程，直到進(jìn)一步的分化不可能繼續(xù)。不能繼續(xù)的情況如：某個(gè)樹點(diǎn)包含完全一致的案例，則無法進(jìn)一步分化；一個(gè)結(jié)點(diǎn)包含太少案例時(shí)，也會(huì)停止分化。(一般取10為標(biāo)準(zhǔn)，少于10即為太少)。數(shù)量最多的種類來確定分類。如上圖的決策樹，假設(shè)它已經(jīng)構(gòu)建完成，那么按多數(shù)原則，就確定左結(jié)點(diǎn)為低第9章分類規(guī)則挖掘與預(yù)測(cè)風(fēng)險(xiǎn)類，右結(jié)點(diǎn)為高風(fēng)險(xiǎn)類。3.CART算法的實(shí)現(xiàn)（1）以貸款申請(qǐng)中的風(fēng)險(xiǎn)分析為例，先確定一個(gè)訓(xùn)練集，如以100個(gè)高風(fēng)險(xiǎn)和100個(gè)低風(fēng)險(xiǎn)的數(shù)據(jù)集為訓(xùn)練集。假設(shè)每條客戶記錄有字段：姓名(Char)、年收入(Money)、工齡(Int)、籍貫(Char)、是否為高負(fù)債(Bool)（2）根據(jù)訓(xùn)練集中的字段及每個(gè)案例在該字段上的取值，按順序掃描訓(xùn)練集，并記錄結(jié)果。a.對(duì)于類型為數(shù)字型的字段，如DateTime、Int、Float、Money等，只要依次取每條記錄的該字段的取值，然后按是否大于該值來掃描訓(xùn)練集。建立一個(gè)表來記錄結(jié)果，基于數(shù)據(jù)庫(kù)中的數(shù)據(jù)一致性、減少數(shù)據(jù)冗余及方便后面對(duì)這個(gè)記錄的操作，可以建立如下的表格tb_Result來存放結(jié)果。序號(hào)Result1（int）Result2（int）1234第9章分類規(guī)則挖掘與預(yù)測(cè)其中序號(hào)字段每次從1開始編號(hào)，添加一條記錄，則序號(hào)加1。Result1用來記錄掃描時(shí)判斷為“是”的高風(fēng)險(xiǎn)的案例數(shù)，如在掃描數(shù)字型字段時(shí)就記錄大于掃描值的高風(fēng)險(xiǎn)案例的數(shù)目；在掃描字符型數(shù)據(jù)時(shí)就用來記錄在該字段上的字符串與掃描字符串Result2”的低風(fēng)險(xiǎn)的案例數(shù)。個(gè)表來記錄結(jié)果，而不必因?yàn)樽侄尾煌白侄晤愋偷牟煌O(shè)計(jì)不同的表來記錄結(jié)果。由于每次使用tb_Result的時(shí)候，序號(hào)都是從1開始編號(hào)的，所以tb_Result中的記錄結(jié)果是與訓(xùn)練集中的記錄一一對(duì)應(yīng)的，只要根據(jù)序號(hào)的對(duì)應(yīng)關(guān)系，能夠很方便的獲得tb_Result表中的某條記錄對(duì)應(yīng)分化規(guī)則。如下圖：t