《數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘》(分類(lèi)規(guī)則)

第9第9章分類(lèi)規(guī)則挖掘與預(yù)測(cè)#第9章分類(lèi)規(guī)則挖掘與預(yù)測(cè)主要內(nèi)容?分類(lèi)與預(yù)測(cè)的基本概念?決策樹(shù)方法分類(lèi)規(guī)則挖掘的ID3算法其他分類(lèi)規(guī)則挖掘算法?分類(lèi)規(guī)則的評(píng)估微軟決策樹(shù)及其應(yīng)用9.1分類(lèi)與預(yù)測(cè)的基本概念1.什么是分類(lèi)數(shù)據(jù)分類(lèi)(dataclassfication)是數(shù)據(jù)挖掘的主要內(nèi)容之一，主要是通過(guò)分析訓(xùn)練數(shù)據(jù)樣本，產(chǎn)生關(guān)于類(lèi)別的精確描述。這種類(lèi)別通常由分類(lèi)規(guī)則組成，可以用來(lái)對(duì)未來(lái)的數(shù)據(jù)進(jìn)行分類(lèi)和預(yù)測(cè)。數(shù)據(jù)分類(lèi)(dataclassfication)是一個(gè)兩個(gè)步驟的過(guò)程：?第1步：建立一個(gè)模型，描述給定的數(shù)據(jù)類(lèi)集或概念集(簡(jiǎn)稱(chēng)訓(xùn)練集)。通過(guò)分析由屬性描述的數(shù)據(jù)庫(kù)元組來(lái)構(gòu)造模型。每個(gè)元組屬于一個(gè)預(yù)定義的類(lèi)，由類(lèi)標(biāo)號(hào)屬性確定。用于建立模型的元組集稱(chēng)為訓(xùn)練數(shù)據(jù)集，其中每個(gè)元組稱(chēng)為訓(xùn)練樣本。由于給出了類(lèi)標(biāo)號(hào)屬性，因此該步驟又稱(chēng)為有指導(dǎo)的學(xué)習(xí)。如果訓(xùn)練樣本的類(lèi)標(biāo)號(hào)是未知的，則稱(chēng)為無(wú)指導(dǎo)的學(xué)習(xí)(聚類(lèi))學(xué)習(xí)模型可用分類(lèi)規(guī)則、決策樹(shù)和數(shù)學(xué)公式的形式給出。?第2步：使用模型對(duì)數(shù)據(jù)進(jìn)行分類(lèi)。包括評(píng)估模型的分類(lèi)準(zhǔn)確性以及對(duì)類(lèi)標(biāo)號(hào)未知的元組按模型進(jìn)行分類(lèi)。圖9-1數(shù)據(jù)分類(lèi)過(guò)程2.常用的分類(lèi)規(guī)則挖掘方法分類(lèi)規(guī)則挖掘有著廣泛的應(yīng)用前景。對(duì)于分類(lèi)規(guī)則的挖掘通常有以下幾種方法，不同的方法適用于不同特點(diǎn)的數(shù)據(jù)：決策樹(shù)方法?貝葉斯方法人工神經(jīng)網(wǎng)絡(luò)方法約略集方法遺傳算法典型的分類(lèi)規(guī)則挖掘算法有ID3■C4.5■DBlearn等3.什么是預(yù)測(cè)預(yù)測(cè)(prediction)是構(gòu)造和使用模型評(píng)估無(wú)標(biāo)號(hào)樣本類(lèi)，或評(píng)估給定的樣本可能具有的屬性或區(qū)間值。分類(lèi)和回歸是兩類(lèi)主要的預(yù)測(cè)問(wèn)題。分類(lèi)是預(yù)測(cè)離散值，回歸用于預(yù)測(cè)連續(xù)或有序值。分類(lèi)和預(yù)測(cè)數(shù)據(jù)的預(yù)處理■數(shù)據(jù)清理：使用平滑技術(shù)消除或減少噪聲；處理空缺值。相關(guān)性分析：刪除與分類(lèi)或預(yù)測(cè)無(wú)關(guān)的屬性；刪除冗余屬性。數(shù)據(jù)變換：使用概念分層將數(shù)據(jù)概化到高的層次；連續(xù)值屬性概化為離散區(qū)間；數(shù)據(jù)規(guī)范化，即將某一屬性的所有值按比例縮放，使其落入指定的區(qū)間。分類(lèi)方法的評(píng)估標(biāo)準(zhǔn)?準(zhǔn)確率：模型正確預(yù)測(cè)新數(shù)據(jù)類(lèi)標(biāo)號(hào)的能力。?速度：產(chǎn)生和使用模型花費(fèi)的時(shí)間。健壯性：有噪聲數(shù)據(jù)或空缺值數(shù)據(jù)時(shí)模型正確分類(lèi)或預(yù)測(cè)的能力。伸縮性：對(duì)于給定的大量數(shù)據(jù)，有效地構(gòu)造模型的能力?？山忉屝裕簩W(xué)習(xí)模型提供的理解和觀察的層次。9.2決策樹(shù)方法決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS,然后發(fā)展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一個(gè)優(yōu)點(diǎn)是它能夠處理連續(xù)屬性。還有CART算法和Assistant算法也是比較有名的決策樹(shù)方法。什么是決策樹(shù)決策樹(shù)(DecisionTree)又稱(chēng)為判定樹(shù)，是運(yùn)用于分類(lèi)的一種樹(shù)結(jié)構(gòu)。其中的每個(gè)內(nèi)部結(jié)點(diǎn)(internalnode)代表對(duì)某個(gè)屬性的一次測(cè)試，每條邊代表一個(gè)測(cè)試結(jié)果，葉結(jié)點(diǎn)(leaf)代表某個(gè)類(lèi)(class)或者類(lèi)的分布(classdistribution)，最上面的結(jié)點(diǎn)是根結(jié)點(diǎn)。決策樹(shù)提供了一種展示類(lèi)似在什么條件下會(huì)得到什么值這類(lèi)規(guī)則的方法。下例是為了解決這個(gè)問(wèn)題而建立的一棵決策樹(shù)，從中可以看到?jīng)Q策樹(shù)的基本組成部分：決策結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)。例〗圖9-2給出了一個(gè)商業(yè)上使用的決策樹(shù)的例子。它表示了一個(gè)關(guān)心電子產(chǎn)品的用戶(hù)是否會(huì)購(gòu)買(mǎi)PCbuys_computer）的知識(shí)，用它可以預(yù)測(cè)某條記錄（某個(gè)人）的購(gòu)買(mǎi)意向。Age?圖9-2buys_computer的決策樹(shù)這棵決策樹(shù)對(duì)銷(xiāo)售記錄進(jìn)行分類(lèi)，指出一個(gè)電子產(chǎn)品消費(fèi)者是否會(huì)購(gòu)買(mǎi)一臺(tái)計(jì)算機(jī)“buys_computer”。每個(gè)內(nèi)部結(jié)點(diǎn)（方形框）代表對(duì)某個(gè)屬性的一次檢測(cè)。每個(gè)葉結(jié)點(diǎn)（橢圓框）代表一個(gè)類(lèi)：buys_computers=yes或者buys_computers=no在這個(gè)例子中，樣本向量為：（age,student,credit_rating;buys_computers）被決策數(shù)據(jù)的格式為:（age,student,credit_rating）輸入新的被決策的記錄，可以預(yù)測(cè)該記錄隸屬于哪個(gè)類(lèi)。使用決策樹(shù)進(jìn)行分類(lèi)構(gòu)造決策樹(shù)是采用自上而下的遞歸構(gòu)造方法。以多叉樹(shù)為例，如果一個(gè)訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬性值，則按照屬性的各種取值把這個(gè)訓(xùn)練數(shù)據(jù)集再劃分為對(duì)應(yīng)的幾個(gè)子集（分支），然后再依次遞歸處理各個(gè)子集。反之，則作為葉結(jié)點(diǎn)。決策樹(shù)構(gòu)造的結(jié)果是一棵二叉或多叉樹(shù)，它的輸入是一組帶有類(lèi)別標(biāo)記的訓(xùn)練數(shù)據(jù)。二叉樹(shù)的內(nèi)部結(jié)點(diǎn)（非葉結(jié)點(diǎn)）一般表示為一個(gè)邏輯判斷，如形式為（a=b）的邏輯判斷，其中a是屬性，b是該屬性的某個(gè)屬性值；樹(shù)的邊是邏輯判斷的分支結(jié)果。多叉樹(shù)（ID3）的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹(shù)的葉結(jié)點(diǎn)都是類(lèi)別標(biāo)記。使用決策樹(shù)進(jìn)行分類(lèi)分為兩步：第1步：利用訓(xùn)練集建立并精化一棵決策樹(shù)，建立決策樹(shù)模型。這個(gè)過(guò)程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)的過(guò)程。第2步：利用生成完畢的決策樹(shù)對(duì)輸入數(shù)據(jù)進(jìn)行分類(lèi)。對(duì)輸入的記錄，從根結(jié)點(diǎn)依次測(cè)試記錄的屬性值，直到到達(dá)某個(gè)葉結(jié)點(diǎn)，從而找到該記錄所在的類(lèi)。問(wèn)題的關(guān)鍵是建立一棵決策樹(shù)。這個(gè)過(guò)程通常分為兩個(gè)階段：建樹(shù)（TreeBuilding）:決策樹(shù)建樹(shù)算法見(jiàn)下，可以看得出，這是一個(gè)遞歸的過(guò)程，最終將得到一棵樹(shù)。剪枝（TreePruning）：剪枝是目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。9.3分類(lèi)規(guī)則挖掘的ID3算法由Quinlan在80年代中期提出的ID3算法是分類(lèi)規(guī)則挖掘算法中最有影響的算法。ID3即決策樹(shù)歸納（InductionofDecisionTree）。早期的ID算法只能就兩類(lèi)數(shù)據(jù)進(jìn)行挖掘（如正類(lèi)和反類(lèi)）；經(jīng)過(guò)改進(jìn)后，現(xiàn)在ID算法可以挖掘多類(lèi)數(shù)據(jù)。待挖掘的數(shù)據(jù)必須是不矛盾的、一致的，也就是說(shuō)，對(duì)具有相同屬性的數(shù)據(jù)，其對(duì)應(yīng)的類(lèi)必須是唯一的。在ID3算法挖掘后，分類(lèi)規(guī)則由決策樹(shù)來(lái)表示。1.ID3算法的基本思想由訓(xùn)練數(shù)據(jù)集中全體屬性值生成的所有決策樹(shù)的集合稱(chēng)為搜索空間，該搜索空間是針對(duì)某一特定問(wèn)題而提出的。系統(tǒng)根據(jù)某個(gè)評(píng)價(jià)函數(shù)決定搜索空間中的哪一個(gè)決策樹(shù)是“最好”的。評(píng)價(jià)函數(shù)一般依據(jù)分類(lèi)的準(zhǔn)確度和樹(shù)的大小來(lái)決定決策樹(shù)的質(zhì)量。如果兩棵決策樹(shù)都能準(zhǔn)確地在測(cè)試集進(jìn)行分類(lèi)，則選擇較簡(jiǎn)單的那棵。相對(duì)而言，決策樹(shù)越簡(jiǎn)單，則它對(duì)未知數(shù)據(jù)的預(yù)測(cè)性能越佳。尋找一棵“最好”的決策樹(shù)是一個(gè)NP完全問(wèn)題。ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹(shù)，同時(shí)保證找到一棵簡(jiǎn)單的決策樹(shù)—可能不是最簡(jiǎn)單的。ID3算法的基本思想描述如下：step1．任意選取一個(gè)屬性作為決策樹(shù)的根結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值創(chuàng)建樹(shù)的分支；step2．用這棵樹(shù)來(lái)對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行分類(lèi)，如果一個(gè)葉結(jié)點(diǎn)的所有實(shí)例都屬于同一類(lèi)，則以該類(lèi)為標(biāo)記標(biāo)識(shí)此葉結(jié)點(diǎn)；如果所有的葉結(jié)點(diǎn)都有類(lèi)標(biāo)記，則算法終止；step3．否則，選取一個(gè)從該結(jié)點(diǎn)到根路徑中沒(méi)有出現(xiàn)過(guò)的屬性為標(biāo)記標(biāo)識(shí)該結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值繼續(xù)創(chuàng)建樹(shù)的分支；重復(fù)算法步驟step2；這個(gè)算法一定可以創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹(shù)，然而，這棵決策樹(shù)不一定是簡(jiǎn)單的。顯然，不同的屬性選取順序?qū)⑸刹煌臎Q策樹(shù)。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡(jiǎn)單的決策樹(shù)。在ID3算法中，采用了一種基于信息的啟發(fā)式的方法來(lái)決定如何選取屬性。啟發(fā)式方法選取具有最高信息量的屬性，也就是說(shuō)，生成最少分支決策樹(shù)的那個(gè)屬性。2.ID3算法的描述算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹(shù)輸入：訓(xùn)練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹(shù)方法：（1）創(chuàng)建結(jié)點(diǎn)N；（2）ifsamples都在同一個(gè)類(lèi)Cthen（3）返回N作為葉結(jié)點(diǎn)，用類(lèi)C標(biāo)記；（4）ifattribute_list為空then（5）返回N作為葉結(jié)點(diǎn)，標(biāo)記samples中最普通的類(lèi)；//多數(shù)表決6)選擇attribute_list中具有最高信息增益的屬性test_attribute；//用信息增益作為屬性選擇度量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è)劃分ifsi為空then加上一個(gè)葉結(jié)點(diǎn)，標(biāo)記為標(biāo)記samples中最普通的類(lèi)；//多數(shù)表決else加上一個(gè)由Generate_decision_tree(si,attribute_list-test_attribute)返回的結(jié)點(diǎn)；2.屬性選擇度量在Generate_decision_tree算法的Step6，算法需選擇attribute_list中具有最高信息增益的屬性test_attribute。ID3算法在樹(shù)的每個(gè)結(jié)點(diǎn)上以信息增量(informationgain)作為度量來(lái)選擇測(cè)試屬性。這種度量稱(chēng)為屬性選擇度量或分裂的優(yōu)良性度量。選擇具有最高信息增益(或最大熵壓縮)的屬性作為當(dāng)前結(jié)點(diǎn)的測(cè)試屬性。該屬性使得對(duì)結(jié)果劃分中的樣本分類(lèi)所需要的信息量最小，并確保找到一棵簡(jiǎn)單的(但不一定是最簡(jiǎn)單的)決策樹(shù)。InformationGain指標(biāo)的原理來(lái)自于信息論。1948年，香農(nóng)(C?E.Shannon)提出了信息論。其中給岀了關(guān)于信息量(Information)和熵(Entropy)的定義，熵實(shí)際上是系統(tǒng)信息量的加權(quán)平均，也就是系統(tǒng)的平均信息量。設(shè)S是有s個(gè)訓(xùn)練樣本數(shù)據(jù)的集合，類(lèi)標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類(lèi)Ci(i=12,??3)，si是類(lèi)Ci中的樣本數(shù)，則對(duì)一個(gè)給定的訓(xùn)練樣本分類(lèi)所需要的期望信息為：I(S],s2,???，sm)=—￡Mi=1pilog2(pi)i其中pi是任意樣本屬于Ci的概率，可用si/s來(lái)估計(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)出來(lái)的分枝。設(shè)s甘是子集Sj中類(lèi)Ci的樣本數(shù)，則按照A劃分成子集的熵為：E(A)=ZMi=1((s!j+%+…％)/%)*1(si，s2,…，sm)信息增益(InformationGain),表示系統(tǒng)由于分類(lèi)獲得的信息量。由系統(tǒng)熵的減少值定量描述。用屬性A分類(lèi)后的信息增益為：Gain(A)=I處,s”…,sm)-E(A)熵是一個(gè)衡量系統(tǒng)混亂程度的統(tǒng)計(jì)量。熵越大，表示系統(tǒng)越混亂。分類(lèi)的目的是提取系統(tǒng)信息，使系統(tǒng)向更加有序、有規(guī)則組織的方向發(fā)展。所以自然而然的，最佳的分裂方案是使熵減少量最大的分裂方案。熵減少量就是InformationGain,所以，最佳分裂就是使Gain(A)最大的分裂方案。通常，這個(gè)最佳方案是用“貪心算法+深度優(yōu)先搜索”得到的。因?yàn)檫@是一個(gè)遞歸過(guò)程，所以?xún)H僅需要討論對(duì)某個(gè)特定結(jié)點(diǎn)N的分裂方法。分裂前設(shè)指向N的訓(xùn)練集為S,其中包含m個(gè)不同的類(lèi)，它們區(qū)分了不同的類(lèi)C.(fori=1,…,m)。設(shè)s.是S中屬于類(lèi)C.的記錄的個(gè)數(shù)。那么分裂之前，系統(tǒng)的總熵11i1(si，s2,…，sm)=-Lmi=1PilOg2(Pi)容易看出，總熵是屬于各個(gè)類(lèi)的記錄的信息量的加權(quán)平均。分裂后現(xiàn)在屬性A是帶有k個(gè)不同值的屬性｛a1,a2,^ak｝,A可以把S分成k個(gè)子集｛鳥(niǎo),S2,…,SJ其中S.=｛xIxeS&x.A=a.｝。如果A被選為測(cè)試屬性，那么那些子集表示從代表集合S的出發(fā)的所有樹(shù)枝。設(shè)，.表示在S.中類(lèi)為C：的記錄個(gè)數(shù)。那么，這時(shí)按A的每個(gè)屬性值(更一般的是取A的一個(gè)子集)進(jìn)行分裂后的信息量，也就是系統(tǒng)總熵為：E(A)=%=1((sij+s2j+??+Smj)/S)*I(sij+s2j+??%)((s1j+s2.+??+5回於)表示第j個(gè)子集的權(quán)重，s=ISI。子集Sj的信息量(子集的總熵)：I(sij+s2j+..+smj)=-￡=ip.log2(Pj)

總熵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ù)集如下表所示：RIDageincomestudentcredit_ratingClass:Buyscomputer1<=30highnofairno2<=30highnoexcellentno331???40highnofairyes4>40mediumnofairyes5>40lowyesfairyes6>40lowyesexcellentno731???40lowyesexcellentyes8<=30mediumnofairno9<=30lowyesfairyes10>40mediumyesfairyes11<=30mediumyesexcellentyes1231???40mediumnoexcellentyes1331???40highyesfairyes14>40mediumnoexcellentno計(jì)算每一個(gè)屬性的信息增益：Gain（age）=I（s2,s2）－E（age）=0.246Gain（income）=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”的樣本都屬于同一類(lèi)“yes"，該分枝的端點(diǎn)應(yīng)該創(chuàng)建一個(gè)葉結(jié)點(diǎn)。

3.剪枝剪枝常常利用統(tǒng)計(jì)學(xué)方法，去掉最不可靠、可能是噪音的一些枝條。剪枝方法主要有兩類(lèi)：同步修剪和遲滯修剪。(1)先剪枝(pre-pruning)在建樹(shù)的過(guò)程中，當(dāng)滿足一定條件，例如InformationGain或者某些有效統(tǒng)計(jì)量達(dá)到某個(gè)預(yù)先設(shè)定的閾值時(shí)，結(jié)點(diǎn)不再繼續(xù)分裂，內(nèi)部結(jié)點(diǎn)成為一個(gè)葉結(jié)點(diǎn)。葉結(jié)點(diǎn)取子集中頻率最大的類(lèi)作為自己的標(biāo)識(shí)，或者可能僅僅存儲(chǔ)這些實(shí)例的概率分布函數(shù)。(2)后剪枝(pos-pruning)與建樹(shù)時(shí)的訓(xùn)練集獨(dú)立的訓(xùn)練數(shù)據(jù)進(jìn)入決策樹(shù)并到達(dá)葉結(jié)點(diǎn)時(shí)，訓(xùn)練數(shù)據(jù)的classlabel與葉結(jié)點(diǎn)的classlabel不同，這時(shí)稱(chēng)為發(fā)生了分類(lèi)錯(cuò)誤。當(dāng)樹(shù)建好之后，對(duì)每個(gè)內(nèi)部結(jié)點(diǎn)，算法通過(guò)每個(gè)枝條的出錯(cuò)率進(jìn)行加權(quán)平均，計(jì)算如果不剪枝該結(jié)點(diǎn)的錯(cuò)誤率。如果裁減能夠降低錯(cuò)誤率，那么該結(jié)點(diǎn)的所有兒子就被剪掉，而該結(jié)點(diǎn)成為一片葉。出錯(cuò)率用與訓(xùn)練集數(shù)據(jù)獨(dú)立的測(cè)試數(shù)據(jù)校驗(yàn)。最終形成一棵錯(cuò)誤率盡可能小的決策樹(shù)。如果在測(cè)試集中出現(xiàn)了類(lèi)交叉的情況，也就是說(shuō)，在待挖掘的數(shù)據(jù)中出現(xiàn)矛盾和不一致的情況。則在算法步驟3中將出現(xiàn)這樣一種情況：在一個(gè)樹(shù)結(jié)點(diǎn)中，所有的實(shí)例并不屬于一個(gè)類(lèi)卻找不到可以繼續(xù)分支的屬性。ID3使用以下兩種方案解決這個(gè)問(wèn)題：①選擇在該結(jié)點(diǎn)中所占比例最大的類(lèi)為標(biāo)記標(biāo)識(shí)該結(jié)點(diǎn)；根據(jù)該結(jié)點(diǎn)中不同類(lèi)的概率分布為標(biāo)記標(biāo)識(shí)該結(jié)點(diǎn)。根據(jù)該結(jié)點(diǎn)中不同類(lèi)的概率分布為標(biāo)記標(biāo)識(shí)該結(jié)點(diǎn)。如果在測(cè)試集中出現(xiàn)了某些錯(cuò)誤的實(shí)例，也就是說(shuō)，在待挖掘的數(shù)據(jù)中，本來(lái)應(yīng)該屬于同一結(jié)點(diǎn)的數(shù)據(jù)因?yàn)槟承╁e(cuò)誤的屬性取值而繼續(xù)分支。則在最終生成的決策樹(shù)中可能出現(xiàn)分支過(guò)細(xì)和錯(cuò)誤分類(lèi)的現(xiàn)象。ID3設(shè)置了一個(gè)閾值來(lái)解決這個(gè)問(wèn)題：只有屬性的信息量超過(guò)這個(gè)閾值時(shí)才創(chuàng)建分支，否則以類(lèi)標(biāo)志標(biāo)識(shí)該結(jié)點(diǎn)。該閾值的選取對(duì)決策樹(shù)的正確創(chuàng)建具有相當(dāng)?shù)闹匾?。如果閾值過(guò)小，可能沒(méi)有發(fā)揮應(yīng)有的作用；如果閾值過(guò)大，又可能刪除了應(yīng)該創(chuàng)建的分支。4.由決策樹(shù)提取分類(lèi)規(guī)則可以提取由決策樹(shù)表示的分類(lèi)規(guī)則，并以IF－THEN的形式表示。具體方法是：從根結(jié)點(diǎn)到葉

結(jié)點(diǎn)的每一條路徑創(chuàng)建一條分類(lèi)規(guī)則，路徑上的每一個(gè)“屬性－值”對(duì)為規(guī)則的前件（即IF部分）的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)為規(guī)則的后件（即THEN部分）。〖例〗對(duì)于buys_computer的決策樹(shù)可提取以下分類(lèi)規(guī)則IFage=‘<=30'ANDstudent=‘no'THENbuys_computer=‘no'

IFage=‘<=30'ANDstudent=‘yes'THENbuys_computer=‘yes'IFage=‘30???40'THENbuys_computer=‘yes'IFage=‘>40'ANDcredit_rating=‘excellent'THENbuys_computer=‘no'IFage=‘>40'ANDcredit_rating=‘fair'THENbuys_computer=‘yes'5.ID3算法的改進(jìn)（1）離散化ID3算法對(duì)符號(hào)性屬性的知識(shí)挖掘比較簡(jiǎn)單，也就是說(shuō)，該算法對(duì)離散性屬性的挖掘更為直觀。算法將針對(duì)屬性的所有符號(hào)創(chuàng)建決策樹(shù)分支。但是，如果屬性值是連續(xù)性的，如一個(gè)人的身高，體重等，如果針對(duì)屬性的所有不同的值創(chuàng)建決策數(shù)，則將由于決策樹(shù)過(guò)于龐大而使該算法失效。為了解決該問(wèn)題，在用ID3算法挖掘具有連續(xù)性屬性的知識(shí)時(shí)，應(yīng)該首先把該連續(xù)性屬性離散化。最簡(jiǎn)單的方法就是把屬性值分成a<n和A>N兩段。如身高可以分為1米以下，1米以上或者分為1.5ii米以下，1.5米以上。如何選擇最佳的分段值呢？對(duì)任何一個(gè)屬性，其所有的取值在一個(gè)數(shù)據(jù)集中是有限的。假設(shè)該屬性取值為C,v,,v）,則在這個(gè)集合中，一共存在m-1個(gè)分段值，ID3算法采用計(jì)算信12m息量的方法計(jì)算最佳的分段值,然后進(jìn)一步構(gòu)建決策樹(shù)。（2）屬性選擇度量ID3算法中采用信息增量作為屬性選擇度量,但它僅適合于具有許多值的屬性。已經(jīng)提出了一些其他的屬性選擇度量方法,如增益率,它考慮了每個(gè)屬性的概率。（3）空缺值處理常用的空缺值處理方法有：若屬性A有空缺值,則可用A的最常見(jiàn)值、平均值、樣本平均值等填充。（4）碎片、重復(fù)和復(fù)制處理通過(guò)反復(fù)地將數(shù)據(jù)劃分為越來(lái)越小的部分,決策樹(shù)歸納可能面臨碎片、重復(fù)和復(fù)制等問(wèn)題。所謂碎片是指在一個(gè)給定的分枝中的樣本數(shù)太少，從而失去統(tǒng)計(jì)意義。解決的方法是：將分類(lèi)屬性值分組，決策樹(shù)結(jié)點(diǎn)可以測(cè)試一個(gè)屬性值是否屬于給定的集合。另一種方法是創(chuàng)建二叉判定樹(shù)，在樹(shù)的結(jié)點(diǎn)上進(jìn)行屬性的布爾測(cè)試，從而可以減少碎片。當(dāng)一個(gè)屬性沿樹(shù)的一個(gè)給定的分枝重復(fù)測(cè)試時(shí)，將出現(xiàn)重復(fù)。復(fù)制是拷貝樹(shù)中已經(jīng)存在的子樹(shù)。通過(guò)由給定的屬性構(gòu)造新的屬性（即屬性構(gòu)造），可以防止以上問(wèn)題的發(fā)生。（5）可伸縮性ID3算法對(duì)于相對(duì)較小的訓(xùn)練數(shù)據(jù)集是有效的，但對(duì)于現(xiàn)實(shí)世界中數(shù)據(jù)量很大的數(shù)據(jù)挖掘，有效性和可伸縮性將成為必須關(guān)注的問(wèn)題。面臨數(shù)以百萬(wàn)計(jì)的訓(xùn)練數(shù)據(jù)集，需要頻繁地將訓(xùn)練數(shù)據(jù)在主存和高速緩存換進(jìn)換出，從而使算法的性能變得低下。解決的方法是：將訓(xùn)練數(shù)據(jù)集劃分為子集，使得每個(gè)子集能夠放在內(nèi)存；然后由每個(gè)子集構(gòu)造一棵決策樹(shù)；最后，將每個(gè)子集得到的分類(lèi)規(guī)則組合起來(lái)，得到輸出的分類(lèi)規(guī)則。最近，已經(jīng)提出了一些強(qiáng)調(diào)可伸縮性的決策樹(shù)算法，如：SLIQ、SPRINT等。這兩種算法都使用了預(yù)排序技術(shù)，并采用了新的數(shù)據(jù)結(jié)構(gòu)，以利于構(gòu)造決策樹(shù)。ID3算法對(duì)大部分?jǐn)?shù)據(jù)集有效，但它不能挖掘域知識(shí)。同時(shí)，決策樹(shù)在計(jì)算機(jī)中存儲(chǔ)的方式?jīng)Q定了該分類(lèi)規(guī)則相對(duì)于其他形式的分類(lèi)規(guī)則（如公式）而言更晦澀難懂。因此，一般在算法結(jié)束后，需要把決策樹(shù)以用戶(hù)可視的方法顯示出來(lái)。〖例〗以下表所示的訓(xùn)練數(shù)據(jù)集為例，其中Salary為工資，Education為教育程度，Class為信用級(jí)別。假設(shè)以20，000作為Salary的分段值，則創(chuàng)建的決策樹(shù)如圖9-3所示；假設(shè)以16，000作為Salary的分段值，則創(chuàng)建的決策樹(shù)如圖9-4所示。SalaryEducationClass10,000高中一般40,000學(xué)士較好15,000學(xué)士一般75,000碩士較好18,000碩士較好訓(xùn)練數(shù)據(jù)集T圖9.3分段值為20，000的決策樹(shù)

圖9.4分段值為16，000的決策樹(shù)由圖9.3和圖9.4可以看出，Salary的分段值不一樣，構(gòu)建的決策樹(shù)也不一樣。6.決策樹(shù)方法的評(píng)價(jià)與其他分類(lèi)算法相比，決策樹(shù)有如下優(yōu)點(diǎn)：(1)速度快：計(jì)算量相對(duì)較小，且容易轉(zhuǎn)化成分類(lèi)規(guī)則。只要沿著樹(shù)根向下一直走到葉，沿途的分裂條件就能夠唯一確定一條分類(lèi)的謂詞。例如，沿著結(jié)點(diǎn)Age->CreditRating->no走下來(lái)就能得到一條謂詞：ifthereisaperson(age>40)and(creditratingisexcellent)thenhewillnotbuyacomputer.（2）準(zhǔn)確性高：挖掘出的分類(lèi)規(guī)則準(zhǔn)確性高，便于理解。一般決策樹(shù)的劣勢(shì)：（1）缺乏伸縮性：由于進(jìn)行深度優(yōu)先搜索，所以算法受內(nèi)存大小限制，難于處理大訓(xùn)練集。一個(gè)例子：在Irvine機(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)算法（離散化、取樣）不僅增加了分類(lèi)算法的額外開(kāi)銷(xiāo)，而且降低了分類(lèi)的準(zhǔn)確性。9.4分類(lèi)規(guī)則挖掘的其他算法9.4.1分類(lèi)規(guī)則挖掘的C4.5算法C4.5算法概述C4.5算法是ID3算法的擴(kuò)展，但是它比ID3算法改進(jìn)的部分是它能夠處理連續(xù)型的屬性。首先將連續(xù)型屬性離散化，把連續(xù)型屬性的值分成不同的區(qū)間，依據(jù)是比較各個(gè)屬性Gian值的大小。"離散化"的方法把連續(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其中，i=1,2,...,N分別計(jì)算把［MIN，人口和(Ai，MAX)(i=1,2,...,N)作為區(qū)間值時(shí)的Gain值，并進(jìn)行比較選取Gain值最大的Ak做為該連續(xù)型屬性的斷點(diǎn)，把屬性值設(shè)置為［MIN，Ak］和(Ak，MAX)兩個(gè)區(qū)間值。Gain函數(shù)決策樹(shù)是建立在信息理論(InformationTheory)的基礎(chǔ)上的，決策樹(shù)的方法循環(huán)地尋找某一標(biāo)準(zhǔn)，它能夠帶來(lái)與本次分類(lèi)相關(guān)的最大信息構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的屬性。對(duì)于同樣一組記錄集，可以有很多決策樹(shù)能符合這組記錄集。人們研究出，一般情況下，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)屬性。屬性選擇依賴(lài)于各種對(duì)例子子集的不純度(impurity)度量方法。不純度度量方法包括信息增益(informatingain)、信息增益比(gainratio)、Gini-index、距離度量(distancemeasure)>J-measure、G統(tǒng)計(jì)、x2統(tǒng)計(jì)、證據(jù)權(quán)重(weightofevidence)>最小描述長(zhǎng)(MLP)、正交法(ortogonalitymeasure)>相關(guān)度(relevance)和Relief。不同的度量有不同的效果，特別是對(duì)于多值屬性。C4.5算法使用信息增益(informationgain)的概念來(lái)構(gòu)造決策樹(shù)，其中每個(gè)分類(lèi)的決定都與前面所選擇的目標(biāo)分類(lèi)有關(guān)。信息理論(InformationTheory)和熵(Entropy)考慮一個(gè)任意的變量，它有兩個(gè)不同的值A(chǔ)和B。假設(shè)已知這個(gè)變量不同值的概率分配，將估測(cè)該概率分配的不純度。情況1?如果P(A)=1和P(B)=0,那么知道這個(gè)變量的值一定為A,不存在不純度，因此已知變量結(jié)果值不會(huì)帶來(lái)任何的信息。情況2?如果P(A)=P(B)=0?5,那么它的不純度明顯地高于P(A)=0.1和P(B)=0.9的情況。在這種情況下,已知變量的結(jié)果值就會(huì)攜帶信息。不純度的最佳評(píng)估方法是平均信息量，也就是信息熵(Entropy)：S=-刀(pi*log(Pi))在上面的例子中,情況1和情況2的信息熵分別是：=-(1*log1+0*log0)=0=-(0.5*log0.5+0.5*log0.5)=0.301(2)信息增益(informationgain)信息增益是指信息熵的有效減少量(通常用"字節(jié)"衡量),根據(jù)它能夠確定在什么樣的層次上選擇什么樣的變量來(lái)分類(lèi)。4.C4.5算法描述FunctionC4.5(R:asetofnon-goalattributessomeofwhichwithcontinuousvalues,C:thegoalattribute,S:atrainingset)returnsadecisiontree;beginIfSisemptythenreturnasinglenodewithvalueFailure;IfSconsistsofrecordsallwiththesamevalueforthegoalattributethenreturnasinglenodewiththatvalue;IfRisemptythenreturnasinglenodewithasvaluethemostfrequentofthevaluesofthegoalattributethatarefoundinrecordsofS;[notethatthentherewillbeerrors,thatis,recordsthatwillbeimproperlyclassified];forallattributesofR(Ri)doifvaluesofRiarecontinuousthenbeginLetA1betheminimumofRi;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;ReturnatreewithrootlabeledDandarcslabeledd1,d2,..,dmgoingrespectivelytothetreesC4.5(R-{D},C,S1),C4.5(R-{D},C,S2),..,C4.5(R-{D},C,Sm);endC4.5。但是，所用的基于分類(lèi)挖掘的決策樹(shù)算法沒(méi)有考慮噪聲問(wèn)題，生成的決策樹(shù)很完美，這只不過(guò)是理論上的，在實(shí)際應(yīng)用過(guò)程中，大量的現(xiàn)實(shí)世界中的數(shù)據(jù)都不是以的意愿來(lái)定的，可能某些字段上缺值(missingvalues)；可能數(shù)據(jù)不準(zhǔn)確含有噪聲或者是錯(cuò)誤的；可能是缺少必須的數(shù)據(jù)造成了數(shù)據(jù)的不完整。另外決策樹(shù)技術(shù)本身也存在一些不足的地方，例如當(dāng)類(lèi)別很多的時(shí)候，它的錯(cuò)誤就可能出現(xiàn)甚至很多。而且它對(duì)連續(xù)性的字段比較難作出準(zhǔn)確的預(yù)測(cè)。而且一般算法在分類(lèi)的時(shí)候，只是根據(jù)一個(gè)屬性來(lái)分類(lèi)的。在有噪聲的情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合(overfitting)，即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能。剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。另外，決策樹(shù)技術(shù)也可能產(chǎn)生子樹(shù)復(fù)制和碎片問(wèn)題。在算法具體實(shí)現(xiàn)時(shí)必須考慮以上這些問(wèn)題。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ì)每一類(lèi)，它構(gòu)建一個(gè)關(guān)系表。這個(gè)關(guān)系表的屬性是實(shí)例集屬性的子集。一個(gè)元組可以看作是一個(gè)屬性值關(guān)聯(lián)的邏輯公式。搜索空間的開(kāi)始是整個(gè)實(shí)例集，而最終目的是為了生成一個(gè)類(lèi)描述的表。類(lèi)描述表的大小不能超過(guò)用戶(hù)定義的閾值。閾值的大小決定了類(lèi)描述表的大小。如果閾值太小，則生成的規(guī)則更簡(jiǎn)單，但同時(shí)也可以能丟失了一些有用的信息從而產(chǎn)生過(guò)度一般化的問(wèn)題；如果閾值太大，則生成的規(guī)則比較詳細(xì)，但同時(shí)也可能產(chǎn)生沒(méi)有完全一般化和規(guī)則復(fù)雜的問(wèn)題。一些屬性域被局部排序從而構(gòu)成一個(gè)層次結(jié)構(gòu)，每一個(gè)值都是該值所在層次下面全部值的一般化。在從關(guān)系表中生成分類(lèi)規(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算法通過(guò)刪除多余的元組來(lái)縮減關(guān)系表的大小從而得到類(lèi)描述表。DBlearn算法描述DBlearn算法創(chuàng)建一個(gè)完全但不一定一致的分類(lèi)規(guī)則，即該分類(lèi)規(guī)則覆蓋所有的實(shí)例集（包括那些錯(cuò)誤的實(shí)例）。DBlearn算法描述如下：step1．從數(shù)據(jù)庫(kù)中選擇和任務(wù)相關(guān)的數(shù)據(jù)，如一個(gè)包含且只包含一類(lèi)數(shù)據(jù)的數(shù)據(jù)表。step2．在該數(shù)據(jù)表上執(zhí)行一般化操作：如果在某個(gè)屬性上存在很多不同的值同時(shí)提供了一個(gè)更高級(jí)別的值，則該屬性被一般化為更高級(jí)別的值；如果在某個(gè)屬性上存在很多不同的值而不能提供一個(gè)更高級(jí)別的值，則該屬性被刪除。刪除重復(fù)的元組直到表的大小達(dá)到用戶(hù)定義的閾值。step3．簡(jiǎn)化結(jié)果。例如，如果該數(shù)據(jù)表上的一些元組除了一個(gè)屬性不一樣，其他的屬性值都是一模一樣的，而這個(gè)不一樣的屬性的取值可以一般化為一個(gè)更高層次的符號(hào)且這個(gè)屬性的取值范圍包含了該更高層次符號(hào)所代表的全部數(shù)據(jù)。則這些元組可以用一個(gè)元組代替，這個(gè)元組的屬性就是那個(gè)不一樣的屬性，它的值用那個(gè)符號(hào)表示。step4．把這個(gè)數(shù)據(jù)表轉(zhuǎn)換成公式。DBlearn算法是一個(gè)相對(duì)比較簡(jiǎn)單的分類(lèi)規(guī)則挖掘算法，通過(guò)對(duì)屬性取值不斷進(jìn)行一般化操作從而最終獲得規(guī)則。在數(shù)據(jù)挖掘的過(guò)程中，該算法是域知識(shí)挖掘的一個(gè)典型例子。該算法經(jīng)過(guò)改進(jìn)可以挖掘那些包含噪聲數(shù)據(jù)的不純凈數(shù)據(jù)，同時(shí)可以做增量學(xué)習(xí)。9.4.3分類(lèi)規(guī)則挖掘的OC1算法1.OC1算法概述OC1算法是ObliqueClassifier1的縮寫(xiě)，即斜面分類(lèi)1算法。它基于線性規(guī)劃的理論，以斜面超平面的思想為基礎(chǔ)，采用自頂向下的方法在條件屬性都是正實(shí)數(shù)類(lèi)型的搜索空間創(chuàng)建斜面決策樹(shù)在執(zhí)行OC1決策樹(shù)算法前，首先需要對(duì)搜索空間做凈化和清理工作以消除條件屬性間的函數(shù)依賴(lài)關(guān)系。凈化后的搜索空間中的每一個(gè)元組(記錄)可以看作是一個(gè)m+1維向量(v,v,,v,c)，其中12mv(1<iVm)對(duì)應(yīng)于第i個(gè)實(shí)數(shù)類(lèi)型的條件屬性，c對(duì)應(yīng)于決策屬性(元組的類(lèi))。所有的條件屬性可以i看作是一個(gè)m維向量(v,v,,v)。12m〖定義〗Rn是一一個(gè)n維歐幾里得空間，設(shè)pGRn且p主0，bGR1，則集合｛xIpTX二b,xGRn｝稱(chēng)為Rn中的一一個(gè)超平面(n>4)。(當(dāng)n=2時(shí)，集合確定一條直線；當(dāng)n=3時(shí)，集合確定一個(gè)平面。)〖定義〗一個(gè)超平面將Rn分成兩個(gè)半空間，記為H+(A,b)二(UIA-U>b)和H-(A,b)二(UIA-U<b)。其中H+(A,b)是Rn中滿足A?U>b的向量U構(gòu)成的半空間，H-(A,b)是Rn中滿足A?U<b的向量U構(gòu)成的半空間?！级x〗一組單位向量(1，0，0，…，0)，(0，1，0，…，0)，…，(0，0，0，…，1)是Rn中的一組基，用符號(hào)g，g，…g來(lái)表示該組單位向量。12n〖定義〗設(shè)「是一個(gè)超平面，如果pT=g(1<i<n)，則「是一個(gè)軸平行超平面，否則「是一個(gè)斜面超平i面?！家怼絀D3決策樹(shù)的每一個(gè)結(jié)點(diǎn)等價(jià)于一個(gè)軸平行超平面。(證明略)大部分決策樹(shù)都是在每一個(gè)結(jié)點(diǎn)檢查某個(gè)屬性的值，或者對(duì)該數(shù)值屬性進(jìn)行分段檢查。因此，稱(chēng)這種決策樹(shù)為“軸平行”決策樹(shù)?！级ɡ怼接贸矫姘岩唤Mn個(gè)的d維向量分成兩個(gè)半空間，如果n>d+1則存在2*工d(心)種方法；k=0k如果n<d+1則存在2n種方法。（證明略）2.OC1算法的基本思想根據(jù)以上定理，最多存在有限種不同的決策樹(shù)。從理論上可以采用一種窮舉的方法來(lái)尋找一棵最優(yōu)決策樹(shù)，但在實(shí)際中這是不可行的算法。如前所述，尋找一棵最優(yōu)決策樹(shù)是一個(gè)NP完全問(wèn)題。尋找一棵斜面超平面決策樹(shù)也是一個(gè)NP完全問(wèn)題。因此，用OC1算法只能找到一棵比較小的決策樹(shù)，但不一定找到一棵最小的決策樹(shù)。OC1算法構(gòu)建一棵斜面超平面決策樹(shù)，其基本思想是：采用自頂向下的方法從條件屬性都是正實(shí)數(shù)類(lèi)型的搜索空間開(kāi)始創(chuàng)建斜面決策樹(shù)。如果搜索空間都屬于同一類(lèi)，則算法終止，否則，在搜索空間中尋找一個(gè)“最佳”劃分搜索空間的斜面超平面，以此斜面超平面標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)，把搜索空間分成兩個(gè)半空間搜索空間（左子樹(shù)和右子樹(shù)）。反復(fù)在每個(gè)半空間搜索空間繼續(xù)尋找“最佳”斜面超平面直至算法終止。3.OC1算法描述step1．就當(dāng)前搜索空間創(chuàng)建決策樹(shù)的根結(jié)點(diǎn)，該結(jié)點(diǎn)的斜面超平面把搜索空間分為左半空間和右半空間；step2．用這棵樹(shù)來(lái)對(duì)搜索空間進(jìn)行分類(lèi)，如果一個(gè)半空間的所有實(shí)例都屬于同一類(lèi)，則以該類(lèi)為標(biāo)記標(biāo)識(shí)此半空間；如果所有的半空間都有類(lèi)標(biāo)記，則算法終止；step3．否則，分別以左半空間和右半空間為搜索空間，繼續(xù)創(chuàng)建根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)；重復(fù)算法步驟step1。OC1算法在每一個(gè)決策樹(shù)結(jié)點(diǎn)處的算法描述如下：/*尋找當(dāng)前搜索空間的“最佳”斜面超平面參數(shù)*/step1?尋找當(dāng)前搜索空間的“最佳”軸平行超平面H，計(jì)算該軸平行超平面H的純潔度I；aaastep2．隨機(jī)選擇一個(gè)斜面超平面H，令“最佳”斜面超平面H等于該斜面超平面H，計(jì)算該斜面超0o0平面H的純潔度I；0ostep3．重復(fù)R次以下步驟：step3．1：重復(fù)執(zhí)行｛依次振蕩斜面超平面H的系數(shù)；0｝直到純潔度Io沒(méi)有進(jìn)一步改進(jìn)；step3．2：重復(fù)最多J次｛選擇一個(gè)隨機(jī)方向，以該隨機(jī)方向改變斜面超平面H；0如果改變后的斜面超平面純潔度I得到改進(jìn)，轉(zhuǎn)到步驟1；o}step3．3：如果斜面超平面H的純潔度I小于“最佳”軸平行超平面H的純潔度I，令I(lǐng)=I0oaaa否則令I(lǐng)=I；ostep4．輸出純潔度I對(duì)應(yīng)的超平面。根據(jù)OC1算法描述可以看出，最重要的算法實(shí)現(xiàn)方式包括：(1)在決策數(shù)的每一個(gè)結(jié)點(diǎn)處如何生成一個(gè)斜面超平面H；0(2)計(jì)算超平面純潔度的方法；4.OC1算法的改進(jìn)(1)OC1算法改進(jìn)的基本思想OC1算法采用自頂向下的方法在條件屬性都是正實(shí)數(shù)類(lèi)型的搜索空間創(chuàng)建斜面決策樹(shù)，如果條件屬性是符號(hào)型則不能適用該算法。關(guān)于符號(hào)型條件屬性的問(wèn)題，很容易想到的解決辦法就是將其對(duì)應(yīng)到正實(shí)數(shù)類(lèi)型上，再在其上采用OC1算法挖掘分類(lèi)規(guī)則。如對(duì)條件屬性“性別”，符號(hào)“男”對(duì)應(yīng)“1”符號(hào)“女”對(duì)應(yīng)“2”。針對(duì)不同的條件屬性，可以創(chuàng)建不同的編碼表，從而使OC1算法適用于符號(hào)型條件屬性的分類(lèi)規(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ù)斜面超平面方程EQ，把實(shí)例HT.代入方程eq，可以得到表達(dá)式2dCx）+a二V。顯然，盡管性別為“女”的實(shí)例在搜索空間的比jHi=1iid+1j例很小，但由于其對(duì)應(yīng)的編碼遠(yuǎn)遠(yuǎn)大于性別為“男”的實(shí)例，因此a的取值只能在很小的范圍振蕩，性別從而影響進(jìn)一步選擇“最佳”斜面超平面。為了解決這個(gè)問(wèn)題，可采用了一種基于分布的編碼方式。首先，掃描整個(gè)搜索空間（實(shí)例集），得到所有條件屬性為符號(hào)型的離散數(shù)據(jù)，創(chuàng)建編碼表，計(jì)算每個(gè)離散數(shù)據(jù)在該搜索空間出現(xiàn)的頻率。根據(jù)每個(gè)符號(hào)對(duì)應(yīng)的概率創(chuàng)建編碼表，可以有效地解決上文中所提出的問(wèn)題。（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é)系捐贈(zèng)的塔斯馬尼亞州（澳大利亞州名）基礎(chǔ)工業(yè)漁業(yè)部的鮑魚(yú)數(shù)據(jù)庫(kù)的數(shù)據(jù)倉(cāng)庫(kù)的一個(gè)采樣切片。由根據(jù)表可以看出，改進(jìn)的OC1算法在同樣的搜索空間和一樣的搜索系數(shù)情況下，決策樹(shù)的正確度無(wú)論是從平均值、最大值還是最小值進(jìn)行比較，都遠(yuǎn)遠(yuǎn)高于原算法，大大增強(qiáng)了決策樹(shù)（分類(lèi)規(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最大值0.760.84最小值0.660.77表OC1算法和OC1改進(jìn)算法的比較9.4.4分類(lèi)規(guī)則挖掘的SLIQ算法1.SLIQ算法概述SLIQ快速可伸縮算法（SupervisedLearningInQuest,其中Quest是IBMAlmaden研究中心的數(shù)據(jù)挖掘項(xiàng)目）是IBMAlmadenResearchCenter于1996年提出的一種高速可調(diào)節(jié)的數(shù)據(jù)挖掘分類(lèi)算法。該算法通過(guò)預(yù)排序技術(shù)，著重解決當(dāng)訓(xùn)練集數(shù)據(jù)量巨大，無(wú)法全部放入內(nèi)存時(shí)，如何高速準(zhǔn)確地生成決策樹(shù)。能同時(shí)處理離散字段和連續(xù)字段。SLIQ的優(yōu)點(diǎn)：1)運(yùn)算速度快，對(duì)屬性值只作一次排序。2)利用整個(gè)訓(xùn)練集的所有數(shù)據(jù)，不做取樣處理，不喪失精確度。3)3)4)更快的，更小的目標(biāo)樹(shù)。(5)低代價(jià)的MDL剪枝算法2.SLIQ算法的關(guān)鍵技術(shù)(1)可伸縮性指標(biāo)一般決策樹(shù)中，使用信息量作為評(píng)價(jià)結(jié)點(diǎn)分裂質(zhì)量的參數(shù)。SLIQ算法中，使用gini指標(biāo)(giniindex)代替信息量(Information)，gini指標(biāo)比信息量性能更好，且計(jì)算方便。對(duì)數(shù)據(jù)集包含n個(gè)類(lèi)的數(shù)據(jù)集S,gini(S)定義為：gini(S)=1-Sp.*Pjp.是S中第j類(lèi)數(shù)據(jù)的頻率。gini越小，InformationGain越大。(2)屬性的分裂方法區(qū)別于一般的決策樹(shù)，SLIQ采用二分查找樹(shù)結(jié)構(gòu)。對(duì)每個(gè)結(jié)點(diǎn)都需要先計(jì)算最佳分裂方案，然后執(zhí)行分裂。對(duì)于數(shù)值型連續(xù)字段(numericattribute)分裂的形式Av=v。所以，可以先對(duì)數(shù)值型字段排序，假設(shè)排序后的結(jié)果為V[,v2,…,v,因?yàn)榉至阎粫?huì)發(fā)生在兩個(gè)結(jié)點(diǎn)之間，所以有n-1種可能性。通常取中點(diǎn)(v.+v)/212nii+1作為分裂點(diǎn)。從小到大依次取不同的splitpoint，取InformationGain指標(biāo)最大(gini最小)的一個(gè)就是分裂點(diǎn)。因?yàn)槊總€(gè)結(jié)點(diǎn)都需要排序，所以這項(xiàng)操作的代價(jià)極大，降低排序成本成為一個(gè)重要的問(wèn)題，SLIQ算法對(duì)排序有很好的解決方案，在后面對(duì)算法的描述中，將很詳細(xì)的看到這一點(diǎn)。對(duì)于離散型字段(categoricalattribute),設(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ì)算2isi次，代價(jià)也是很大的。SLIQ算法對(duì)此也有一定程度的優(yōu)化。(3)剪枝SLIQ的剪枝算法MDL屬于后剪枝(pos-prunning)[3?1?1?2]算法。通常的后剪枝的數(shù)據(jù)源采用一個(gè)TrainingSet的一個(gè)子集或者與TrainingSet獨(dú)立的數(shù)據(jù)集進(jìn)行操作。3?算法描述輸入數(shù)據(jù)：訓(xùn)練集，配置信息(決策樹(shù)大小)；輸出數(shù)據(jù)：用線性表方式表示的二叉決策樹(shù)。算法：Createnode(root);Preparefordataofattributelistandclasslist;//數(shù)據(jù)準(zhǔn)備Enterqueue(root);//算法的控制結(jié)構(gòu)是一個(gè)隊(duì)列,該隊(duì)列存放當(dāng)前的所有葉結(jié)點(diǎn)While(notempty(queue))doEvaluateSplits();//計(jì)算最佳分裂foralltheleafnodesinthequeuedoUpdateLabels();//升級(jí)結(jié)點(diǎn)(創(chuàng)建子結(jié)點(diǎn)、執(zhí)行結(jié)點(diǎn)分裂)

//對(duì)應(yīng)該分裂的類(lèi)Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;//對(duì)應(yīng)該分裂的類(lèi)Letthenewleafnodeenterthequeue;MDLpruning(root);//利用MDL算法進(jìn)行剪枝圖9-3計(jì)算分裂指標(biāo)的例子當(dāng)前待分裂屬性Salary,右邊為classhistogram的變化過(guò)程。屬性表從上往下掃描，葉隊(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算法1.CART算法概述CART算法可用來(lái)自動(dòng)探測(cè)出高度復(fù)雜數(shù)據(jù)的潛在結(jié)構(gòu)，重要模式和關(guān)系.這種探測(cè)出的知識(shí)又可用來(lái)構(gòu)造精確和可靠的預(yù)測(cè)模型，應(yīng)用于分類(lèi)客戶(hù)、準(zhǔn)確直郵、偵測(cè)通信卡及信用卡詐騙和管理信用風(fēng)險(xiǎn)。技術(shù)上講，CART技術(shù)可稱(chēng)為二元回歸分化技術(shù).因?yàn)楦Y(jié)點(diǎn)總是被分為兩個(gè)子結(jié)點(diǎn)并不斷分化，故稱(chēng)為二元回歸。CART分析的技術(shù)要點(diǎn)包括一系列規(guī)則，可用于：（1）分裂樹(shù)點(diǎn)（2）確定何時(shí)結(jié)束分裂（3）為每一葉結(jié)點(diǎn)指定類(lèi)型或預(yù)測(cè)值2.CART算法的分裂規(guī)則的選擇將一個(gè)結(jié)點(diǎn)分化成兩個(gè)子結(jié)點(diǎn)，CART總是問(wèn)些“是”或“非”的問(wèn)題。來(lái)分化根結(jié)點(diǎn)成二個(gè)子結(jié)點(diǎn)，以“是”為回答的案例歸入左子樹(shù)結(jié)點(diǎn)，而”否”為回答的案例歸為右子樹(shù)結(jié)點(diǎn)。〖例〗貸款申請(qǐng)中風(fēng)險(xiǎn)分析。有訓(xùn)練集包含100個(gè)高風(fēng)險(xiǎn)和100個(gè)低風(fēng)險(xiǎn)的測(cè)試案例，構(gòu)造一棵二叉樹(shù)如圖1所示：圖9-8貸款風(fēng)險(xiǎn)分析對(duì)于上圖中所得到的二叉樹(shù)，CART算法先檢驗(yàn)分析中所有變量可生出的所有分裂，再選其優(yōu)者。如上圖中有200個(gè)案例，假設(shè)每個(gè)案例都有10個(gè)相關(guān)的數(shù)據(jù)變量，那么CART算法要比較200X10即2000種分裂的可能。接下來(lái)需要根據(jù)分裂質(zhì)量標(biāo)準(zhǔn)來(lái)評(píng)估每一個(gè)分化。最常用的一個(gè)標(biāo)準(zhǔn)是GINI標(biāo)準(zhǔn)，基本原則是根據(jù)該分化是否有效地分隔幾個(gè)類(lèi)別。除了GINI標(biāo)準(zhǔn)外，還可以用Twoing標(biāo)準(zhǔn)和規(guī)則Twoing標(biāo)準(zhǔn)。其中GINI標(biāo)準(zhǔn)在樹(shù)成長(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ù)類(lèi)型的選擇，也可以運(yùn)用連續(xù)自變變量的線性組合來(lái)作為分化的基礎(chǔ)。通過(guò)質(zhì)量標(biāo)準(zhǔn)評(píng)估每一個(gè)分化后，要選取一個(gè)最佳分化來(lái)構(gòu)建決策樹(shù)，并繼續(xù)對(duì)每一個(gè)子結(jié)點(diǎn)重復(fù)進(jìn)行“搜索和分化”的過(guò)程，直到進(jìn)一步的分化不可能繼續(xù)。不能繼續(xù)的情況如：某個(gè)樹(shù)點(diǎn)包含完全一致的案例，則無(wú)法進(jìn)一步分化；一個(gè)結(jié)點(diǎn)包含太少案例時(shí)，也會(huì)停止分化。(一般取10為標(biāo)準(zhǔn)，少于10即為太少)。當(dāng)決策樹(shù)構(gòu)建完成后，需要要對(duì)決策樹(shù)的終結(jié)點(diǎn)的案例進(jìn)行分類(lèi)。一種最簡(jiǎn)單的分類(lèi)方法就是對(duì)數(shù)原則，即用數(shù)量最多的種類(lèi)來(lái)確定分類(lèi)。如上圖的決策樹(shù)，假設(shè)它已經(jīng)構(gòu)建完成，那么按多數(shù)原則，就確定左結(jié)點(diǎn)為低風(fēng)險(xiǎn)類(lèi)，右結(jié)點(diǎn)為高風(fēng)險(xiǎn)類(lèi)。3.CART算法的實(shí)現(xiàn)以貸款申請(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è)每條客戶(hù)記錄有字段：姓名(Char)、年收入(Money)、工齡(Int)、籍貫(Char)、是否為高負(fù)債(Bool)。(為了舉例字段的典型性，所以列舉了上述這些字段，實(shí)際情況肯定不止這些字段，不過(guò)這些字段基本覆蓋了在規(guī)則分化中要考慮的情況。)（2）根據(jù)訓(xùn)練集中的字段及每個(gè)案例在該字段上的取值，按順序掃描訓(xùn)練集，并記錄結(jié)果。a.對(duì)于類(lèi)型為數(shù)字型的字段，如DateTime、Int、Float、Money等，只要依次取每條記錄的該字段的取值，然后按是否大于該值來(lái)掃描訓(xùn)練集。建立一個(gè)表來(lái)記錄結(jié)果，基于數(shù)據(jù)庫(kù)中的數(shù)據(jù)一致性、減少數(shù)據(jù)冗余及方便后面對(duì)這個(gè)記錄的操作，可以建立如下的表格tb_Result來(lái)存放結(jié)果。序號(hào)Resultl(int)Result2(int)1234其中序號(hào)字段每次從1開(kāi)始編號(hào)，添加一條記錄，則序號(hào)加1。Resultl用來(lái)記錄掃描時(shí)判斷為“是”的高風(fēng)險(xiǎn)的案例數(shù),如在掃描數(shù)字型字段時(shí)就記錄大于掃描值的高風(fēng)險(xiǎn)案例的數(shù)目；在掃描字符型數(shù)據(jù)時(shí)就用來(lái)記錄在該字段上的字符串與掃描字符串相同的高風(fēng)險(xiǎn)的記錄數(shù)；在掃描布爾型數(shù)據(jù)時(shí)，用來(lái)記錄取值為“是”的高風(fēng)險(xiǎn)案例數(shù)目。Result2用來(lái)記錄掃描時(shí)判斷為“是”的低風(fēng)險(xiǎn)的案例數(shù)。用序號(hào)字段，而不直接用掃描字段來(lái)記錄，是為了實(shí)現(xiàn)表的重用，節(jié)省數(shù)據(jù)庫(kù)開(kāi)支，這樣在掃描所有的字段的時(shí)候都可以共用這個(gè)表來(lái)記錄結(jié)果，而不必因?yàn)樽侄尾煌白侄晤?lèi)型的不同而要設(shè)計(jì)不同的表來(lái)記錄結(jié)果。由于每次使用tb_Result的時(shí)候，序號(hào)都是從1開(kāi)始編號(hào)的，所以tb_Result中的記錄結(jié)果是與訓(xùn)練集中的記錄一一對(duì)應(yīng)的，只要根據(jù)序號(hào)的對(duì)應(yīng)關(guān)系，能夠很方便的獲得tb_R