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

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