《數(shù)據(jù)倉庫與數(shù)據(jù)挖掘》

《數(shù)據(jù)倉庫與數(shù)據(jù)挖掘》

分類規(guī)則挖掘與預(yù)測

要緊內(nèi)容

?分類與預(yù)測的基本概念

?決策樹方法

?分類規(guī)則挖掘的ID3算法

?其他分類規(guī)則挖掘算法

?分類規(guī)則的評估

?微軟決策樹及其應(yīng)用

9.1分類與預(yù)測的基本概念

1.什么是分類

數(shù)據(jù)分類(dataclassfication)是數(shù)據(jù)挖掘的要緊內(nèi)容之一，要緊是通過分析訓(xùn)練數(shù)據(jù)樣本，產(chǎn)

生關(guān)于類別的精確描述。這種類別通常由分類規(guī)則構(gòu)成，能夠用來對未來的數(shù)據(jù)進(jìn)行分類與預(yù)測。

數(shù)據(jù)分類(dataclassfication)是—兩個(gè)步驟的過程：

?第1步：建立一個(gè)模型，描述給定的數(shù)據(jù)類集或者概念集(簡稱訓(xùn)練集)。通過分析由屬性

描述的數(shù)據(jù)庫元組來構(gòu)造模型。每個(gè)元組屬于一個(gè)預(yù)定義的類，由類標(biāo)號屬性確定。用于建

立模型的元組集稱之訓(xùn)練數(shù)據(jù)集，其中每個(gè)元組稱之訓(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)行分類。

分類算法分類規(guī)則

模型評估

新數(shù)據(jù)分

新數(shù)

(b)分類------

圖9-1數(shù)據(jù)分類過程

2.常用的分類規(guī)則挖掘方法

分類規(guī)則挖掘有著廣泛的應(yīng)用前景。關(guān)于分類規(guī)則的挖掘通常有下列幾種方法，不一致的方法適

用于不一致特點(diǎn)的數(shù)據(jù)：

?決策樹方法

?貝葉斯方法

?人工神經(jīng)網(wǎng)絡(luò)方法

?約略集方法

?遺傳算法

典型的分類規(guī)則挖掘算法有：

?ID3

?C4.5

?DBlearn等

3.什么是預(yù)測

預(yù)測(prediction)是構(gòu)造與使用模型評估無標(biāo)號樣本類，或者評估給定的樣本可能具有的屬性

或者區(qū)間值。分類與回歸是兩類要緊的預(yù)測問題。分類是預(yù)測離散值，回歸用于預(yù)測連續(xù)或者有序

值。

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)生與使用模型花費(fèi)的時(shí)間。

?健壯性：有噪聲數(shù)據(jù)或者空缺值數(shù)據(jù)時(shí)模型正確分類或者預(yù)測的能力。

?伸縮性：關(guān)于給定的大量數(shù)據(jù)，有效地構(gòu)造模型的能力。

?可解釋性：學(xué)習(xí)模型提供的懂得與觀察的層次。

9.2決策樹方法

決策樹方法的起源是概念學(xué)習(xí)系統(tǒng)CLS,然后進(jìn)展到由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）

代表對某個(gè)屬性的一次測試，每條邊代表一個(gè)測試結(jié)果，葉結(jié)點(diǎn)（leaf）代表某個(gè)類（class）或者者類的分

布（classdistribution）,最上面的結(jié)點(diǎn)是根結(jié)點(diǎn)。

決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法。下例是為熟悉決這個(gè)問題而建立的

一棵決策樹，從中能夠看到?jīng)Q策樹的基本構(gòu)成部分：決策結(jié)點(diǎn)、分支與葉結(jié)點(diǎn)。

工例』圖9-2給出了一個(gè)商業(yè)上使用的決策樹的例子。它表示了一個(gè)關(guān)心電子產(chǎn)品的用戶是否會購買PC

（buys_computer）的知識，用它能夠預(yù)測某條記錄（某個(gè)人）的購買意向。

<=30?///30...40圖9^3x>iniys_computer的決策樹

每個(gè)內(nèi)部結(jié)點(diǎn)《兩形框）代春對府屬班的一次檢測W晦個(gè)葉結(jié)點(diǎn)（橢圓框）代表一個(gè)類:

;_computets=；

buys_efi(fiftputers=noexcellen

件中，樣本向題一

tingjifcuysicomputers

的格式為：、-一一,

(age,student,credit_rating)

輸入新的被決策的記錄，能夠預(yù)測該記錄隸屬于哪個(gè)類。

2.使用決策樹進(jìn)行分類

構(gòu)造決策樹是使用自上而下的遞歸構(gòu)造方法。以多叉樹為例，假如一個(gè)訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬

性值，則按照屬性的各類取值把這個(gè)訓(xùn)練數(shù)據(jù)集再劃分為對應(yīng)的幾個(gè)子集(分支)，然后再依次遞歸處理各

個(gè)子集。反之，則作為葉結(jié)點(diǎn)。

決策樹構(gòu)造的結(jié)果是一棵二叉或者多叉樹，它的輸入是一組帶有類別標(biāo)記的訓(xùn)練數(shù)據(jù)。二叉樹的內(nèi)部結(jié)

點(diǎn)(非葉結(jié)點(diǎn))通常表示為一個(gè)邏輯推斷，如形式為(a=b)的邏輯推斷，其中a是屬性，b是該屬性的某個(gè)

屬性值；樹的邊是邏輯推斷的分支結(jié)果。多叉樹(ID3)的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾

個(gè)屬性值，就有幾條邊。樹的葉結(jié)點(diǎn)都是類別標(biāo)記。

使用決策樹進(jìn)行分類分為兩步：

?第1步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個(gè)過程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取

知識，進(jìn)行機(jī)器學(xué)習(xí)的過程。

?第2步：利用生成完畢的決策樹對輸入數(shù)據(jù)進(jìn)行分類。對輸入的記錄，從根結(jié)點(diǎn)依次測試記錄的屬性

值，直到到達(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即決策樹

歸納(InductionofDecisionTree)。早期的ID算法只能就兩類數(shù)據(jù)進(jìn)行挖掘(如正類與反類)；通過

改進(jìn)后，現(xiàn)在ID算法能夠挖掘多類數(shù)據(jù)。待挖掘的數(shù)據(jù)務(wù)必是不矛盾的、一致的，也就是說，對具

有相同屬性的數(shù)據(jù)，其對應(yīng)的類務(wù)必是唯一的。在ID3算法挖掘后，分類規(guī)則由決策樹來表示。

1.ID3算法的基本思想

由訓(xùn)練數(shù)據(jù)集中全體屬性值生成的所有決策樹的集合稱之搜索空間，該搜索空間是針對某一特

定問題而提出的。系統(tǒng)根據(jù)某個(gè)評價(jià)函數(shù)決定搜索空間中的哪一個(gè)決策樹是“最好”的。評價(jià)函數(shù)通

常根據(jù)分類的準(zhǔn)確度與樹的大小來決定決策樹的質(zhì)量。假如兩棵決策樹都能準(zhǔn)確地在測試集進(jìn)行分

類，則選擇較簡單的那棵。相對而言，決策樹越簡單，則它對未知數(shù)據(jù)的預(yù)測性能越佳。尋找一棵“最

好”的決策樹是一個(gè)NP完全問題。

ID3使用一種自頂向下的方法在部分搜索空間創(chuàng)建決策樹，同時(shí)保證找到一棵簡單的決策樹一可

能不是最簡單的。

ID3算法的基本思想描述如下：

step1.任意選取一個(gè)屬性作為決策樹的根結(jié)點(diǎn)，然后就這個(gè)屬性所有的取值創(chuàng)建樹的分支；

step2.用這棵樹來對訓(xùn)練數(shù)據(jù)集進(jìn)行分類，假如一個(gè)葉結(jié)點(diǎn)的所有實(shí)例都屬于同一類，則以該類為

標(biāo)記標(biāo)識此葉結(jié)點(diǎn)；假如所有的葉結(jié)點(diǎn)都有類標(biāo)記，則算法終止；

step3.否則，選取一個(gè)從該結(jié)點(diǎn)到根路徑中沒有出現(xiàn)過的屬性為標(biāo)記標(biāo)識該結(jié)點(diǎn)，然后就這個(gè)屬性

所有的取值繼續(xù)創(chuàng)建樹的分支；重復(fù)算法步驟step2；

這個(gè)算法一定能夠創(chuàng)建一棵基于訓(xùn)練數(shù)據(jù)集的正確的決策樹，然而，這棵決策樹不一定是簡單的。

顯然，不一致的屬性選取順序?qū)⑸刹灰恢碌臎Q策樹。因此，適當(dāng)?shù)剡x取屬性將生成一棵簡單的決策

樹。在ID3算法中，使用了一種基于信息的啟發(fā)式的方法來決定如何選取屬性。啟發(fā)式方法選取具有

最高信息量的屬性，也就是說，生成最少分支決策樹的那個(gè)屬性。

2.ID3算法的描述

算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹

輸入：訓(xùn)練數(shù)據(jù)集samples,用離散值屬性表示；候選屬性的集合attribute」ist。

輸出：一棵決策樹

方法：

(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)選擇attributejist中具有最高信息增益的屬性test_attribute；〃用信息增益作為屬性選擇度量

(7)標(biāo)記結(jié)點(diǎn)N為test_attribute；

(8)foreachtest_attribute中的已知值ai〃劃分samples

(9)由結(jié)點(diǎn)N生長出一個(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ù)表決

(13)else加上一個(gè)由Generate_decision_tree(si,attribute_Iist-test_attribute)返回的結(jié)點(diǎn)；

2.屬性選擇度量

在Generate_decision_tree算法的Step6,算法需選擇attribute_Iist中具有最高信息增益的屬性

test_attribute0ID3算法在樹的每個(gè)結(jié)點(diǎn)上以信息增量(informationgain)作為度量來選擇測試屬性。

這種度量稱之屬性選擇度量或者分裂的優(yōu)良性度量。選擇具有最高信息增益(或者最大蠟壓縮)的屬

性作為當(dāng)前結(jié)點(diǎn)的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需要的信息量最小，并確保找到

一棵簡單的(但不一定是最簡單的)決策樹。

InformationGain指標(biāo)的原理來自于信息論。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ù)的集合，類標(biāo)號屬性具有m個(gè)不一致值，定義m個(gè)不一致類Ci(i=l,2,...,m),

si是類Ci中的樣本數(shù)，則對一個(gè)給定的訓(xùn)練樣本分類所需要的期望信息為：

I(Si,S2,…，Sm)=-2Mi=ipiIog2(pi)i

其中pi是任意樣本屬于Ci的概率，可用si/s來估計(jì)。

設(shè)屬性A具有k個(gè)不一致值{al,a2,…,ak},則可用屬性A將S劃分為k個(gè)子集{Sl,S2,...,Sk},Sj中包含

的樣本在屬性A上具有值ajo假如選擇A作為測試屬性，則這些子集對應(yīng)于由包含集合S的結(jié)點(diǎn)生長出來

的分枝。設(shè)Sij是子集Sj中類Ci的樣本數(shù)，則按照A劃分成子集的燧為：

E(A)=2"i=i((Slj+S2j+...+Smj)/Slj)*I(Sl,S2,...,Sm)

信息增益(InformationGain),表示系統(tǒng)由于分類獲得的信息量。由系統(tǒng)煙的減少值定量描述。用屬性

A分類后的信息增益為：

Gain(A)=I(si,S2,...,sm)-E(A)

嫡是一個(gè)衡量系統(tǒng)混亂程度的統(tǒng)計(jì)量。端越大，表示系統(tǒng)越混亂。分類的目的是提取系統(tǒng)信息，使

系統(tǒng)向更加有序、有規(guī)則組織的方向進(jìn)展。因此自然而然的，最佳的分裂方案是使牖減少量最大的分裂方

案。懶減少量就是InformationGain,因此，最佳分裂就是使Gain(A)最大的分裂方案。通常，這個(gè)最佳方

案是用“貪心算法+深度優(yōu)先搜索”得到的。

由于這是一個(gè)遞歸過程，因此僅僅需要討論對某個(gè)特定結(jié)點(diǎn)N的分裂方法。

(1)分裂前

設(shè)指向N的訓(xùn)練集為S,其中包含m個(gè)不一致的類，它們區(qū)分了不一致的類G(fori=l,…，m)。設(shè)

&是S中屬于類G的記錄的個(gè)數(shù)。那么分裂之前，系統(tǒng)的總端：

I(Sl,S2,...,Sm)=-EMi=lPi10g2(Pi)

容易看出，總端是屬于各個(gè)類的記錄的信息量的加權(quán)平均。

(2)分裂后

現(xiàn)在屬性A是帶有k個(gè)不一致值的屬性{ai,a2,…ak},A能夠把S分成k個(gè)子集{Si,S2,…,Sk}其中S,>=

{X|XGS&x.A=aj}o假如A被選為測試屬性，那么那些子集表示從代表集合S的出發(fā)的所有樹枝。設(shè)Sij

表示在Sj中類為C的記錄個(gè)數(shù)。那么，這時(shí)按A的每個(gè)屬性值(更通常的是取A的一個(gè)子集)進(jìn)行分裂

后的信息量，也就是系統(tǒng)總熠為：

k

E(A)=Xj=l((Slj+S2j+..+Smj)/S)*I(Slj+S2j+..+Smj)

((Slj+S2j+..+Smj)/S)表示第j個(gè)子集的權(quán)重，S=ISI。子集Sj的信息量(子集的總燧)：

I(Slj+S2j+..+Smj)=￡i=lPij10g2(PU)

總煙E(A)是各個(gè)子集信息量的加權(quán)平均。

算法計(jì)算每個(gè)屬性的信息增益，具有最高信息增益的屬性選擇作為給定訓(xùn)練數(shù)據(jù)集合S的測試屬性。創(chuàng)

建一個(gè)結(jié)點(diǎn)，并以該屬性為標(biāo)記，對屬性的每一個(gè)值創(chuàng)建分枝，并據(jù)此劃分樣本。

K例】顧客數(shù)據(jù)庫訓(xùn)練數(shù)據(jù)集如下表所示：

RIDageincomestudentcredit_ratingClass:

Buys_computer

1<=30highnofairno

2<=30highnoexcellentno

331...40highnofairyes

4>40mediumnofairyes

5>40lowyesfairyes

6>40lowyesexcellentno

731…40lowyesexcellentyes

8<=30mediumnofairno

9<=30lowyesfairyes

10>40mediumyesfairyes

11<=30mediumyesexcellentyes

1231...40mediumnoexcellentyes

1331…40highyesfairyes

14>40mediumnoexcellentno

計(jì)算每一個(gè)屬性的信息增益：

Gain(age)=1(s2,s2)—E(age)=0.246

Gain(income)=0.029

Gain(student)=0.151

Gain(credit_rating)=0.048

由于屬性age在所有屬性中具有最高的信息增益，因此它被選擇為測試屬性。創(chuàng)建一個(gè)以age為標(biāo)記

的結(jié)點(diǎn)，并對每一個(gè)屬性值引出一個(gè)分蘆枝age="31…40”的樣本都屬于同一類“yes”，該分枝的

端點(diǎn)應(yīng)該創(chuàng)建一個(gè)葉結(jié)點(diǎn)。a

incomestudent加,

_rating31..

highnofairno

highnoexcellentno

mediumnofairno

lowyesfairyes

mediumyesexcellentyes

3.剪枝

剪枝常常利用統(tǒng)計(jì)學(xué)方法，去掉最不可靠、可能是噪音的一些枝條。剪枝方法要緊有兩類：同步修剪

與遲滯修剪。

(1)先剪枝(pre-pruning)

在建樹的過程中，當(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)取子集中頻率最大的類作為自己的標(biāo)

識，或者者可能僅僅存儲這些實(shí)例的概率分布函數(shù)。

(2)后剪枝(pos-pruning)

與建樹時(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)樹建好之后，對每個(gè)內(nèi)部結(jié)點(diǎn)，算法通過每個(gè)枝條的出

錯(cuò)率進(jìn)行加權(quán)平均，計(jì)算假如不剪枝該結(jié)點(diǎn)的錯(cuò)誤率。假如裁減能夠降低錯(cuò)誤率，那么該結(jié)點(diǎn)的所有兒子

就被剪掉，而該結(jié)點(diǎn)成為一片葉。出錯(cuò)率用與訓(xùn)練集數(shù)據(jù)獨(dú)立的測試數(shù)據(jù)校驗(yàn)。最終形成一棵錯(cuò)誤率盡可

能小的決策樹。

假如在測試集中出現(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)識該結(jié)點(diǎn)；

②根據(jù)該結(jié)點(diǎn)中不一致類的概率分布為標(biāo)記一一標(biāo)識該結(jié)點(diǎn)。

假如在測試集中出現(xiàn)了某些錯(cuò)誤的實(shí)例，也就是說，在待挖掘的數(shù)據(jù)中，本來應(yīng)該屬于同一結(jié)

點(diǎn)的數(shù)據(jù)由于某些錯(cuò)誤的屬性取值而繼續(xù)分支。則在最終生成的決策樹中可能出現(xiàn)分支過細(xì)與錯(cuò)誤

分類的現(xiàn)象。ID3設(shè)置了一個(gè)閾值來解決這個(gè)問題：只有屬性的信息量超過這個(gè)閾值時(shí)才創(chuàng)建分支，

否則以類標(biāo)志標(biāo)識該結(jié)點(diǎn)。該閾值的選取對決策樹的正確創(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è)“屬性一值”對為規(guī)則的前件（即IF部分）

的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)為規(guī)則的后件（即THEN部分）。

k例』關(guān)于buys_computer的決策樹可提取下列分類規(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算法對符號性屬性的知識挖掘比較簡單，也就是說，該算法對離散性屬性的挖掘更為直觀。

算法將針對屬性的所有符號創(chuàng)建決策樹分支。但是，假如屬性值是連續(xù)性的，如一個(gè)人的身高，體重

等，假如針對屬性的所有不一致的值創(chuàng)建決策數(shù)，則將由于決策樹過于龐大而使該算法失效。

為熟悉決該問題，在用ID3算法挖掘具有連續(xù)性屬性的知識時(shí)，應(yīng)該首先把該連續(xù)性屬性離散化。

最簡單的方法就是把屬性值分成與A,〉N兩段。如身高能夠分為1米下列，1米以上或者者分為

1.5米下列，1.5米以上。如何選擇最佳的分段值呢？對任何一個(gè)屬性，其所有的取值在一個(gè)數(shù)據(jù)集中

是有限的。假設(shè)該屬性取值為(%,%??…,”)，則在這個(gè)集合中，一共存在m-1個(gè)分段值，ID3算法使用計(jì)

算信息量的方法計(jì)算最佳的分段值，然后進(jìn)一步構(gòu)建決策樹。

(2)屬性選擇度量

ID3算法中使用信息增量作為屬性選擇度量，但它僅適合于具有許多值的屬性。已經(jīng)提出了一些

其他的屬性選擇度量方法，如增益率，它考慮了每個(gè)屬性的概率。

(3)空缺值處理

常用的空缺值處理方法有：若屬性A有空缺值，則可用A的最常見值、平均值、樣本平均值

等填充。

(4)碎片、重復(fù)與復(fù)制處理

通過反復(fù)地將數(shù)據(jù)劃分為越來越小的部分，決策樹歸納可能面臨碎片、重復(fù)與復(fù)制等問題。所

謂碎片是指在一個(gè)給定的分枝中的樣本數(shù)太少，從而失去統(tǒng)計(jì)意義。

解決的方法是：將分類屬性值分組，決策樹結(jié)點(diǎn)能夠測試一個(gè)屬性值是否屬于給定的集合。另

一種方法是創(chuàng)建二叉判定樹，在樹的結(jié)點(diǎn)上進(jìn)行屬性的布爾測試，從而能夠減少碎片。

當(dāng)一個(gè)屬性沿樹的一個(gè)給定的分枝重復(fù)測試時(shí)，將出現(xiàn)重復(fù)。復(fù)制是拷貝樹中已經(jīng)存在的子樹。

通過由給定的屬性構(gòu)造新的屬性(即屬性構(gòu)造)，能夠防止以上問題的發(fā)生。

(5)可伸縮性

ID3算法關(guān)于相對較小的訓(xùn)練數(shù)據(jù)集是有效的，但關(guān)于現(xiàn)實(shí)世界中數(shù)據(jù)量很大的數(shù)據(jù)挖掘，有

效性與可伸縮性將成為務(wù)必關(guān)注的問題。面臨數(shù)以百萬計(jì)的訓(xùn)練數(shù)據(jù)集，需要頻繁地將訓(xùn)練數(shù)據(jù)在

主存與高速緩存換進(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算法對大部分?jǐn)?shù)據(jù)集有效，但它不能挖掘域知識。同時(shí)，決策樹在計(jì)算機(jī)中存儲的方式?jīng)Q

定了該分類規(guī)則相關(guān)于其他形式的分類規(guī)則（如公式）而言更晦澀難懂。因此，通常在算法結(jié)束后，

需要把決策樹以用戶可視的方法顯示出來。

k例』下列表所示的訓(xùn)練數(shù)據(jù)集為例，其中Salary為工資，Education為教育程度，Class為信用

級別。假設(shè)以20,000作為Salary的分段值，則創(chuàng)建的決策樹如圖9-3所示；假設(shè)以16,000作為

Salary的分段值，則創(chuàng)建的決策樹如圖9-4所示。

SalaryEducationClass

10,000高中通常

40,000學(xué)士較好

15,000學(xué)士通常

75,000碩士較好

18,000碩士較好

圖9.3分段值為20,000的決策樹

Salary>16,000

/39.4分段值為16,000的決策:

?斗圖9.4能夠看出，Salary的分節(jié)，構(gòu)建的決策樹也不一樣。

的評價(jià)

與其他方美舁JEd比,決策樹有如下優(yōu)點(diǎn):給

(1)速度快：計(jì)算量相對較小，且容易轉(zhuǎn)化成分類規(guī)則。只要沿著樹根向下一直走到葉，沿途的分裂條件

就能夠唯一確定一條分類的謂詞。比如，沿著結(jié)點(diǎn)Age->CreditRating->no走下來就能得到一條謂詞：

ifthereisaperson(age>40)and(creditratingisexcellent)thenhewillnotbuya

computer.

(2)準(zhǔn)確性高：挖掘出的分類規(guī)則準(zhǔn)確性高，便于懂得。

通常決策樹的劣勢：

(1)缺乏伸縮性：由于進(jìn)行深度優(yōu)先搜索，因此算法受內(nèi)存大小限制，難于處理大訓(xùn)練集。一個(gè)例子：在

Irvine機(jī)器學(xué)習(xí)知識庫中，最大能夠同意的數(shù)據(jù)集僅僅為700KB,2000條記錄。而現(xiàn)代的數(shù)據(jù)倉庫動(dòng)輒存

儲幾個(gè)G-Bytes的海量數(shù)據(jù)。用往常的方法是顯然不行的。

(2)為了處理大數(shù)據(jù)集或者連續(xù)量的種種改進(jìn)算法(離散化、取樣)不僅增加了分類算法的額外開銷，而

且降低了分類的準(zhǔn)確性。

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

其中，i=1,2,,N

3)分別計(jì)算把［MIN,Ai］與(Ai,MAX)(i=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)鍵在于如何選擇好的屬性。關(guān)于同樣一組記錄集,

能夠有很多決策樹能符合這組記錄集。人們研究出，通常情況下，樹越小則樹的預(yù)測能力越強(qiáng)。要構(gòu)造盡可

能小的決策樹，關(guān)鍵在于選擇恰當(dāng)屬性。屬性選擇依靠于各類對例子子集的不純度(impurity)度量方法。

不純度度量方法包含信息增益(informatingain)、信息增益比(gainratio)>Gini-index、距離度量(distance

measure)、J-measure、G統(tǒng)計(jì)、x2統(tǒng)計(jì)、證據(jù)權(quán)重(weightofevidence)>最小描述長(MLP)、正交法

(ortogonalitymeasure)＞有關(guān)度(relevance)與Reliefo不一致的度量有不一致的效果，特別是關(guān)于多值

屬性。C4.5算法使用信息增益(informationgain)的概念來構(gòu)造決策樹，其中每個(gè)分類的決定都與前面所

選擇的目標(biāo)分類有關(guān)。

(1)信息理論(InformationTheory)與燃(Entropy)

考慮一個(gè)任意的變量，它有兩個(gè)不一致的值A(chǔ)與B。假設(shè)已知這個(gè)變量不一致值的概率分配，將估測該概率

分配的不純度。

情況1.假如P(A)=1與P(B)=0,那么明白這個(gè)變量的值一定為A,不存在不純度，因此已知變量結(jié)果

值不可能帶來任何的信息。

情況2.假如P(A)=P(B)=0.5,那么它的不純度明顯地高于P(A)=0.1與P(B)=0.9的情況。在這

種情況下，已知變量的結(jié)果值就會攜帶信息。

不純度的最佳評估方法是平均信息量，也就是信息燧(Entropy)：

S=-S(pi*log(Pi))

在上面的例子中，情況1與情況2的信息埔分別是：

S1=-(1*log1+0*log0)=0

S2=-(0.5*log0.5+0.5*log0.5)=0.301

(2)信息增益(informationgain)

信息增益是指信息端的有效減少量(通常用“字節(jié)”衡量)，根據(jù)它能夠確定在什么樣的層次上選擇什么

樣的變量來分類。

4.C4.5算法描述

FunctionC4.5(R:asetofnon-goalattributessomeofwhichwithcontinuousvalues,

C:thegoalattribute,

S:atrainingset)returnsadecisiontree;

begin

IfSisemptythen

returnasinglenodewithvalueFailure;

IfSconsistsofrecordsallwiththesamevalueforthegoalattributethen

returnasinglenodewiththatvalue;

IfRisemptythen

returnasinglenodewithasvaluethemostfrequentofthevaluesofthegoalattribute

thatarefoundinrecordsofS;

[notethatthentherewillbeerrors,thatis,recordsthatwillbeimproperlyclassified];

forallattributesofR(Ri)do

ifvaluesofRiarecontinuousthen

begin

LetAlbetheminimumofRi;

LetAmbethemaximumofRi;{m值手工設(shè)置}

forjfrom2tom-1doAj=Al+j*(Al-Am)/m;

LetAbethevaluepointofRiwithlargestGain(Ri,S)based

on{<=Aj,>Aj};

end;

LetDbetheattributewithlargestGain(D,S)

amongattributesinR;

Let{dj|j=l,2,m}bethevaluesofattributeD;

Let{Sj|j=l,2,m}bethesubsetsofSconsisting

respectivelyofrecordswithvaluedjforattributeD;

ReturnatreewithrootlabeledDandarcslabeled

dl,d2,dmgoingrespectivelytothetrees

C4.5(R-{D},C,SI),C4.5(R-{D},C,S2),C4.5(R-{D},C,Sm);

endC4.5o

但是，所用的基于分類挖掘的決策樹算法沒有考慮噪聲問題，生成的決策樹很完美，這只只是是理論

上的，在實(shí)際應(yīng)用過程中，大量的現(xiàn)實(shí)世界中的數(shù)據(jù)都不是以的意愿來定的，可能某些字段上缺值(missing

values)；可能數(shù)據(jù)不準(zhǔn)確含有噪聲或者者是錯(cuò)誤的；可能是缺少務(wù)必的數(shù)據(jù)造成了數(shù)據(jù)的不完整。另外決策

樹技術(shù)本身也存在一些不足的地方，比如當(dāng)類別很多的時(shí)候，它的錯(cuò)誤就可能出現(xiàn)甚至很多。而且它對連續(xù)

性的字段比較難作出準(zhǔn)確的預(yù)測。而且通常算法在分類的時(shí)候，只是根據(jù)一個(gè)屬性來分類的。

在有噪聲的情況下，完全擬合將導(dǎo)致過分?jǐn)M合(overfitting),即對訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很

好的預(yù)測性能。剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹得到簡化而變得更容易懂得。另外，決策樹技

術(shù)也可能產(chǎn)生子樹復(fù)制與碎片問題。

在算法具體實(shí)現(xiàn)時(shí)務(wù)必考慮以上這些問題。

9.4.2DBlearn算法

1.DBlearn算法概述

DBlearn算法用域知識生成基于關(guān)系數(shù)據(jù)庫的預(yù)定義子集的描述。DBlearn算法使用自底向上的

搜索策略，使用以屬性層次形式的域知識，同時(shí)該算法使用了關(guān)系代數(shù)。該算法的事務(wù)集是一個(gè)關(guān)系

表，即一個(gè)具有若干個(gè)屬性的n元組。

系統(tǒng)使用關(guān)系表作為知識結(jié)構(gòu)：對每一類，它構(gòu)建一個(gè)關(guān)系表。這個(gè)關(guān)系表的屬性是實(shí)例集屬性的子

集。一個(gè)元組能夠看作是一個(gè)屬性值關(guān)聯(lián)的邏輯公式。搜索空間的開始是整個(gè)實(shí)例集，而最終目的是

為了生成一個(gè)類描述的表。類描述表的大小不能超過用戶定義的閾值。閾值的大小決定了類描述表的

大小。假如閾值太小，則生成的規(guī)則更簡單，但同時(shí)也能夠能丟失了一些有用的信息從而產(chǎn)生過度通

?；膯栴}；假如閾值太大，則生成的規(guī)則比較全面，但同時(shí)也可能產(chǎn)生沒有完全通?；c規(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)系，因此務(wù)必刪除其中一個(gè)

屬性，保留另一個(gè)屬性。

(2)通?；簩傩缘闹当煌ǔ；癁閷哟卧谒系闹祻亩梢?guī)則。如就年齡這個(gè)屬性而言，5歲下

列都能夠通?；癁橛啄辏?-12歲能夠通?；癁橥甑取?/p>

在一個(gè)關(guān)系表上運(yùn)行以上兩個(gè)算子有可能產(chǎn)生完全一樣的元組，DBlearn算法通過刪除多余的

元組來縮減關(guān)系表的大小從而得到類描述表。

2.DBlearn算法描述

DBlearn算法創(chuàng)建一個(gè)完全但不一定一致的分類規(guī)則，即該分類規(guī)則覆蓋所有的實(shí)例集(包含那

些錯(cuò)誤的實(shí)例)。

DBIearn算法描述如下：

stepl.從數(shù)據(jù)庫中選擇與任務(wù)有關(guān)的數(shù)據(jù)，如一個(gè)包含且只包含一類數(shù)據(jù)的數(shù)據(jù)表。

step2.在該數(shù)據(jù)表上執(zhí)行通?；僮鳎杭偃缭谀硞€(gè)屬性上存在很多不一致的值同時(shí)提供了一個(gè)更高

級別的值，則該屬性被通常化為更高級別的值；假如在某個(gè)屬性上存在很多不一致的值而不能提供一

個(gè)更高級別的值，則該屬性被刪除。刪除重復(fù)的元組直到表的大小達(dá)到用戶定義的閾值。

step3.簡化結(jié)果。比如，假如該數(shù)據(jù)表上的一些元組除了一個(gè)屬性不一樣，其他的屬性值都是一模

一樣的，而這個(gè)不一樣的屬性的取值能夠通常化為一個(gè)更高層次的符號且這個(gè)屬性的取值范圍包含了

該更高層次符號所代表的全部數(shù)據(jù)。則這些元組能夠用一個(gè)元組代替，這個(gè)元組的屬性就是那個(gè)不一

樣的屬性，它的值用那個(gè)符號表示。

step4.把這個(gè)數(shù)據(jù)表轉(zhuǎn)換成公式。

DBIearn算法是一個(gè)相對比較簡單的分類規(guī)則挖掘算法，通過對屬性取值不斷進(jìn)行通?；僮鲝亩?/p>

終獲得規(guī)則。在數(shù)據(jù)挖掘的過程中，該算法是域知識挖掘的一個(gè)典型例子。該算法通過改進(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)建斜面決策樹。

在執(zhí)行OC1決策樹算法前，首先需要對搜索空間做凈化與清理工作以消除條件屬性間的函數(shù)依

靠關(guān)系。凈化后的搜索空間中的每一個(gè)元組(記錄)能夠看作是一個(gè)m+1維向量(%,1???/“”)，其中

匕(14i?m)對應(yīng)于第i個(gè)實(shí)數(shù)類型的條件屬性，c對應(yīng)于決策屬性(元組的類)。所有的條件屬性能夠

看作是一個(gè)m維向量(h,匕,

(定義』是一個(gè)n維歐幾里得空間，設(shè)peR"且PHO,beR',則集合｛x|p，x=4xeQ｝稱之R"中的一

個(gè)超平面(n")。(當(dāng)n=2時(shí)，集合確定一條直線；當(dāng)n=3時(shí)，集合確定一個(gè)平面。)

K定義』一個(gè)超平面將R"分成兩個(gè)半空間，記為H+(A/)=(U|AUN力與”-(A，=(U|AW)。其中H+(A,b)

是中滿足AUNb的向量U構(gòu)成的半空間，是R"中滿足的向量U構(gòu)成的半空間。

工定義X一組單位向量(1,0,0,0),(0,1,0,0),…，(0,0,0,…，1)是R"中的一組

基，用符號配，??七”來表示該組單位向量。

(定義1設(shè)『是一個(gè)超平面，假如p，=5(14iW〃)，則「是一個(gè)軸平行超平面，否則「是一個(gè)斜面超平

面。

R引理』ID3決策樹的每一個(gè)結(jié)點(diǎn)等價(jià)于一個(gè)軸平行超平面。(證明略)

大部分決策樹都是在每一個(gè)結(jié)點(diǎn)檢查某個(gè)屬性的值，或者者對該數(shù)值屬性進(jìn)行分段檢查。因此，

稱這種決策樹為“軸平行”決策樹。

工定理U用超平面把一組n個(gè)的d維向量分成兩個(gè)半空間，假如n>d+l則存在2*￡，(泮))種方法；

假如n<d+l則存在2"種方法。

(證明略)

2.0C1算法的基本思想

根據(jù)以上定理，最多存在有限種不一致的決策樹。從理論上能夠使用一種窮舉的方法來尋找一棵

最優(yōu)決策樹，但在實(shí)際中這是不可行的算法。如前所述，尋找一棵最優(yōu)決策樹是一個(gè)NP完全問題。

尋找一棵斜面超平面決策樹也是一個(gè)NP完全問題。因此，用OC1算法只能找到一棵比較小的決策

樹，但不一定找到一棵最小的決策樹。

OC1算法構(gòu)建一棵斜面超平面決策樹，其基本思想是：使用自頂向下的方法從條件屬性都是正

實(shí)數(shù)類型的搜索空間開始創(chuàng)建斜面決策樹。假如搜索空間都屬于同一類，則算法終止，否則，在搜索

空間中尋找一個(gè)''最佳”劃分搜索空間的斜面超平面，以此斜面超平面標(biāo)識當(dāng)前結(jié)點(diǎn)，把搜索空間分

成兩個(gè)半空間搜索空間（左子樹與右子樹）。反復(fù)在每個(gè)半空間搜索空間繼續(xù)尋找“最佳”斜面超平

面直至算法終止。

3.OC1算法描述

step1.就當(dāng)前搜索空間創(chuàng)建決策樹的根結(jié)點(diǎn)，該結(jié)點(diǎn)的斜面超平面把搜索空間分為左半空間與右半

空間；

step2.用這棵樹來對搜索空間進(jìn)行分類，假如一個(gè)半空間的所有實(shí)例都屬于同一類，則以該類為標(biāo)

記標(biāo)識此半空間；假如所有的半空間都有類標(biāo)記，則算法終止；

step3.否則，分別以左半空間與右半空間為搜索空間，繼續(xù)創(chuàng)建根結(jié)點(diǎn)的左子樹與右子樹；重復(fù)算

法步驟steplo

OC1算法在每一個(gè)決策樹結(jié)點(diǎn)處的算法描述如下：

/*尋找當(dāng)前搜索空間的“最佳”斜面超平面參數(shù)*/

step1.尋找當(dāng)前搜索空間的“最佳”軸平行超平面乩，計(jì)算該軸平行超平面乩的純潔度小

step2.隨機(jī)選擇一個(gè)斜面超平面”。，令“最佳”斜面超平面/等于該斜面超平面”。，計(jì)算該斜面超

平面“0的純潔度小

step3.重復(fù)R次下列步驟：

step3.1；重復(fù)執(zhí)行｛

依次振蕩斜面超平面兒的系數(shù)；

｝直到純潔度/?沒有進(jìn)一步改進(jìn)；

step3.2：重復(fù)最多J次｛

選擇一個(gè)隨機(jī)方向，以該隨機(jī)方向改變斜面超平面%;

假如改變后的斜面超平面純潔度/"得到改進(jìn)，轉(zhuǎn)到步驟1;

)

step3.3：假如斜面超平面”。的純潔度小于“最佳”軸平行超平面”“的純潔度/“，令1=/“；

否則令1=/°;

step4.輸出純潔度I對應(yīng)的超平面。

根據(jù)OC1算法描述能夠看出，最重要的算法實(shí)現(xiàn)方式包含：

⑴在決策數(shù)的每一個(gè)結(jié)點(diǎn)處如何生成一個(gè)斜面超平面?。?/p>

⑵計(jì)算超平面純潔度的方法;

4.OC1算法的改進(jìn)

(1)0C1算法改進(jìn)的基本思想

OC1算法使用自頂向下的方法在條件屬性都是正實(shí)數(shù)類型的搜索空間創(chuàng)建斜面決策樹，假如條件

屬性是符號型則不能適用該算法。關(guān)于符號型條件屬性的問題，很容易想到的解決辦法就是將其對應(yīng)

到正實(shí)數(shù)類型上，再在其上使用OC1算法挖掘分類規(guī)則。如對條件屬性“性別”，符號“男”對應(yīng)“1”,

符號“女”對應(yīng)“2”。針對不一致的條件屬性，能夠創(chuàng)建不一致的編碼表，從而使OC1算法適用于

符號型條件屬性的分類規(guī)則挖掘。

但是這樣創(chuàng)建的編碼表具有很強(qiáng)的隨意性與主觀性，不能真正反應(yīng)數(shù)據(jù)的真實(shí)狀況。如在搜索空間T

中，條件屬性“性別”為“男''的實(shí)例占了97%,而為“女”的實(shí)例只有3%。假設(shè)在編碼表中符號

“男”對應(yīng)的編碼為“1000”，符號“女”對應(yīng)的編碼為“2000”，根據(jù)斜面超平面方程EQ”，把實(shí)例

7；代入方程EQ”，能夠得到表達(dá)式匕。顯然，盡管性別為“女”的實(shí)例在搜索空間的比

例很小，但由于其對應(yīng)的編碼遠(yuǎn)遠(yuǎn)大于性別為“男”的實(shí)例，因此。性別的取值只能在很小的范圍振蕩，

從而影響進(jìn)一步選擇“最佳”斜面超平面。

為熟悉決這個(gè)問題，可使用了一種基于分布的編碼方式。首先，掃描整個(gè)搜索空間(實(shí)例集)，

得到所有條件屬性為符號型的離散數(shù)據(jù)，創(chuàng)建編碼表，計(jì)算每個(gè)離散數(shù)據(jù)在該搜索空間出現(xiàn)的頻率。

根據(jù)每個(gè)符號對應(yīng)的概率創(chuàng)建編碼表，能夠有效地解決上文中所提出的問題。

（2）OC1改進(jìn)算法的描述

該部分的算法描述如下：

step1.掃描搜索空間；

step2.統(tǒng)計(jì)每一個(gè)符號屬性出現(xiàn)的次數(shù)；

step3.計(jì)算每一個(gè)符號屬性的概率分布值；

step4.生成編碼表；

（3）結(jié)果分析

下表給出了OC1算法與改進(jìn)的OC1算法在同一個(gè)搜索空間，同樣的隨機(jī)改進(jìn)系數(shù)（隨機(jī)跳躍次

數(shù)45）,同樣的振蕩次數(shù)（＜20）下搜索的正確率比較分析。該搜索空間是基于塔斯馬尼亞州大學(xué)計(jì)

算機(jī)科學(xué)系捐贈(zèng)的塔斯馬尼亞州（澳大利亞州名）基礎(chǔ)工業(yè)漁業(yè)部的鮑魚數(shù)據(jù)庫的數(shù)據(jù)倉庫的一個(gè)采

樣切片。

由根據(jù)表能夠看出，改進(jìn)的OC1算法在同樣的搜索空間與一樣的搜索系數(shù)情況下，決策樹的正確度

不管是從平均值、最大值還是最小值進(jìn)行比較，都遠(yuǎn)遠(yuǎn)高于原算法，大大增強(qiáng)了決策樹（分類規(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

最大值0.760.84

最小值0.660.77

表OC1算法與OC1改進(jìn)算法的比較

9.4.4分類規(guī)則挖掘的SLIQ算法

1.SLIQ算法概述

SLIQ快速可伸縮算法(SupervisedLearningInQuest,其中Quest是IBMAlmaden研究中心的數(shù)據(jù)挖

掘項(xiàng)目)是IBMAlmadenResearchCenter于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)算速度快，對屬性值只作一次排序。

(2)利用整個(gè)訓(xùn)練集的所有數(shù)據(jù)，不做取樣處理，不喪失精確度。

(3)輕松處理磁盤常駐的大型訓(xùn)練集，適合處理數(shù)據(jù)倉庫的海量歷史數(shù)據(jù)。

(4)更快的，更小的目標(biāo)樹。

(5)低代價(jià)的MDL剪枝算法

2.SLIQ算法的關(guān)鍵技術(shù)

(1)可伸縮性指標(biāo)

通常決策樹中，使用信息量作為評價(jià)結(jié)點(diǎn)分裂質(zhì)量的參數(shù)。SLIQ算法中，使用gini指標(biāo)(giniindex)

代替信息量(Information),gini指標(biāo)比信息量性能更好，且計(jì)算方便。對數(shù)據(jù)集包含n個(gè)類的數(shù)據(jù)集S,

gini(S)定義為：

gini(S)=1-Epj*pj

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

(2)屬性的分裂方法

區(qū)別于通常的決策樹，SLIQ使用二分查找樹結(jié)構(gòu)。對每個(gè)結(jié)點(diǎn)都需要先計(jì)算最佳分裂方案，然后執(zhí)行

分裂。

關(guān)于數(shù)值型連續(xù)字段(numericattribute)分裂的形式A<=v。因此，能夠先對數(shù)值型字段排序，假設(shè)排序后

的結(jié)果為VI,V2,…,Vn,由于分裂只會發(fā)生在兩個(gè)結(jié)點(diǎn)之間，因此有JI-1種可能性。通常取中點(diǎn)(Vi+Vi+l)/2

作為分裂點(diǎn)。從小到大依次取不一致的splitpoint,取InformationGain指標(biāo)最大(gini最小)的一個(gè)就是

分裂點(diǎn)。由于每個(gè)結(jié)點(diǎn)都需要排序，因此這項(xiàng)操作的代價(jià)極大，降低排序成本成為一個(gè)重要的問題，SLIQ

算法對排序有很好的解決方案，在后面對算法的描述中，將很全面的看到這一點(diǎn)。

關(guān)于離散型字段(categoricalattribute),設(shè)S(A)為A的所有可能的值，分裂測試將要取遍S的所有子集

S\尋找當(dāng)分裂成S，與S-S，兩塊時(shí)的gini指標(biāo)，取到gini最小的時(shí)候，就是最佳分裂方法。顯然，這是一

個(gè)對集合S的所有子集進(jìn)行遍歷的過程，共需要計(jì)算2⑸次，代價(jià)也是很大的。SLIQ算法對此也有一定程

度的優(yōu)化。

(3)剪枝

SLIQ的剪枝算法MDL屬于后剪枝(pos-prunning)[]算法。通常的后剪枝的數(shù)據(jù)源使用一個(gè)Training

Set的一個(gè)子集或者者與TrainingSet獨(dú)立的數(shù)據(jù)集進(jìn)行操作。

3.算法描述

輸入數(shù)據(jù)：訓(xùn)練集，配置信息(決策樹大小)；

輸出數(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

EvaluateSplits();//計(jì)算最佳分裂

foralltheleafnodesinthequeuedo

UpdateLabels();〃升級結(jié)點(diǎn)(創(chuàng)建子結(jié)點(diǎn)、執(zhí)行結(jié)點(diǎn)分裂）

Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;〃對應(yīng)該分裂的類

表進(jìn)行更換

Letthenewleafnodeenterthequeue;

MDLpruning(root);//利用MDL算法進(jìn)行剪枝

圖9-3計(jì)算分裂指標(biāo)的例子一一當(dāng)前待分裂Salary,右邊為classhistogram的變化過程。屬性表從上往

下掃描兄;卅隊(duì)列里面的結(jié)點(diǎn)有峽N36BN3

SnlnryInclc、

InitialHistograms

GN2

廚二結(jié)底能扮裂成解門逋;N3轉(zhuǎn)為內(nèi)

N3

N2N3

BN3

UpdntcdnsshistORramsand

N3EvaluatefirstsplitfornodeN2<salary?<?=■15)

Z3BB

SalaryListCZIQSSI.ist

R0R

N2

Updateclasshistogram*nnd

EvaluatefirstsplitfornodeN3(salaryv-40)

N6

1.CART算法概述

CART算法可用來自動(dòng)探測出高度復(fù)雜數(shù)據(jù)的潛在結(jié)構(gòu)，重要模式與關(guān)系.這種探測出的知識又可用來構(gòu)造精確與可靠的

預(yù)測模型，應(yīng)用于分類客戶、準(zhǔn)確直郵、偵測通信卡及信用卡詐騙與管理信用風(fēng)險(xiǎn)。

技術(shù)上講，CART技術(shù)可稱之二元回歸分化技術(shù).由于根結(jié)點(diǎn)總是被分為兩個(gè)子結(jié)點(diǎn)并不斷分化，故稱之二元回歸。

CART分析的技術(shù)要點(diǎn)包含一系列規(guī)則，可用于：

(1)分裂樹點(diǎn)

(2)確定何時(shí)結(jié)束分裂

(3)為每一葉結(jié)點(diǎn)指定類型或者預(yù)測值

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)。

K例X貸款申請中風(fēng)險(xiǎn)分析。有訓(xùn)練集包含100個(gè)高風(fēng)險(xiǎn)與100個(gè)低風(fēng)險(xiǎn)的測試案例，構(gòu)造一棵二叉樹如圖1