《數據倉庫與數據挖掘》

《數據倉庫與數據挖掘》

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

要緊內容

?分類與預測的基本概念

?決策樹方法

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

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

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

?微軟決策樹及其應用

9.1分類與預測的基本概念

1.什么是分類

數據分類(dataclassfication)是數據挖掘的要緊內容之一，要緊是通過分析訓練數據樣本，產

生關于類別的精確描述。這種類別通常由分類規(guī)則構成，能夠用來對未來的數據進行分類與預測。

數據分類(dataclassfication)是—兩個步驟的過程：

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

描述的數據庫元組來構造模型。每個元組屬于一個預定義的類，由類標號屬性確定。用于建

立模型的元組集稱之訓練數據集，其中每個元組稱之訓練樣本。由于給出了類標號屬性，因

此該步驟又稱之有指導的學習。假如訓練樣本的類標號是未知的，則稱之無指導的學習(聚

類)。學習模型可用分類規(guī)則、決策樹與數學公式的形式給出。

?第2步：使用模型對數據進行分類。包含評估模型的分類準確性與對類標號未知的元組按

模型進行分類。

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

模型評估

新數據分

新數

(b)分類------

圖9-1數據分類過程

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

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

用于不一致特點的數據：

?決策樹方法

?貝葉斯方法

?人工神經網絡方法

?約略集方法

?遺傳算法

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

?ID3

?C4.5

?DBlearn等

3.什么是預測

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

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

值。

4.分類與預測數據的預處理

?數據清理：使用平滑技術消除或者減少噪聲；處理空缺值。

?有關性分析：刪除與分類或者預測無關的屬性；刪除冗余屬性。

?數據變換：使用概念分層將數據概化到高的層次；連續(xù)值屬性概化為離散區(qū)間；數據規(guī)范化，馬

上某一屬性的所有值按比例縮放，使其落入指定的區(qū)間。

5.分類方法的評估標準

?準確率：模型正確預測新數據類標號的能力。

?速度：產生與使用模型花費的時間。

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

?伸縮性：關于給定的大量數據，有效地構造模型的能力。

?可解釋性：學習模型提供的懂得與觀察的層次。

9.2決策樹方法

決策樹方法的起源是概念學習系統(tǒng)CLS,然后進展到由Quiulan研制ID3方法，然后到著名的C4.5

算法，C4.5算法的一個優(yōu)點是它能夠處理連續(xù)屬性。還有CART算法與Assistant算法也是比較有名的決策

樹方法。

1.什么是決策樹

決策樹（DecisionTree）又稱之判定樹，是運用于分類的一種樹結構。其中的每個內部結點（internalnode）

代表對某個屬性的一次測試，每條邊代表一個測試結果，葉結點（leaf）代表某個類（class）或者者類的分

布（classdistribution）,最上面的結點是根結點。

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

一棵決策樹，從中能夠看到決策樹的基本構成部分：決策結點、分支與葉結點。

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

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

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

每個內部結點《兩形框）代春對府屬班的一次檢測W晦個葉結點（橢圓框）代表一個類:

;_computets=；

buys_efi(fiftputers=noexcellen

件中，樣本向題一

tingjifcuysicomputers

的格式為：、-一一,

(age,student,credit_rating)

輸入新的被決策的記錄，能夠預測該記錄隸屬于哪個類。

2.使用決策樹進行分類

構造決策樹是使用自上而下的遞歸構造方法。以多叉樹為例，假如一個訓練數據集中的數據有幾種屬

性值，則按照屬性的各類取值把這個訓練數據集再劃分為對應的幾個子集(分支)，然后再依次遞歸處理各

個子集。反之，則作為葉結點。

決策樹構造的結果是一棵二叉或者多叉樹，它的輸入是一組帶有類別標記的訓練數據。二叉樹的內部結

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

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

個屬性值，就有幾條邊。樹的葉結點都是類別標記。

使用決策樹進行分類分為兩步：

?第1步：利用訓練集建立并精化一棵決策樹，建立決策樹模型。這個過程實際上是一個從數據中獲取

知識，進行機器學習的過程。

?第2步：利用生成完畢的決策樹對輸入數據進行分類。對輸入的記錄，從根結點依次測試記錄的屬性

值，直到到達某個葉結點，從而找到該記錄所在的類。

問題的關鍵是建立一棵決策樹。這個過程通常分為兩個階段：

?建樹(TreeBuilding)：決策樹建樹算法見下，能夠看得出，這是一個遞歸的過程，最終將得到一棵樹。

?剪枝(TreePruning)：剪枝是目的是降低由于訓練集存在噪聲而產生的起伏。

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

由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。ID3即決策樹

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

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

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

1.ID3算法的基本思想

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

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

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

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

好”的決策樹是一個NP完全問題。

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

能不是最簡單的。

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

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

step2.用這棵樹來對訓練數據集進行分類，假如一個葉結點的所有實例都屬于同一類，則以該類為

標記標識此葉結點；假如所有的葉結點都有類標記，則算法終止；

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

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

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

顯然，不一致的屬性選取順序將生成不一致的決策樹。因此，適當地選取屬性將生成一棵簡單的決策

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

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

2.ID3算法的描述

算法：Generate_decision_tree由給定的訓練數據產生一棵決策樹

輸入：訓練數據集samples,用離散值屬性表示；候選屬性的集合attribute」ist。

輸出：一棵決策樹

方法：

(1)創(chuàng)建結點N；

(2)ifsamples都在同一個類Cthen

(3)返回N作為葉結點，用類C標記；

(4)ifattribute_list為空then

(5)返回N作為葉結點，標記samples中最普通的類；

〃多數表決

(6)選擇attributejist中具有最高信息增益的屬性test_attribute；〃用信息增益作為屬性選擇度量

(7)標記結點N為test_attribute；

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

(9)由結點N生長出一個條件為test_attribute=ai的分枝；

(10)設si為samples中test_attribute=ai的樣本集合；

〃一個劃分

(11)ifsi為空then

(12)加上一個葉結點，標記為標記samples中最普通的類；

〃多數表決

(13)else加上一個由Generate_decision_tree(si,attribute_Iist-test_attribute)返回的結點；

2.屬性選擇度量

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

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

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

性作為當前結點的測試屬性。該屬性使得對結果劃分中的樣本分類所需要的信息量最小，并確保找到

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

InformationGain指標的原理來自于信息論。1948年，香農(C.E.Shannon)提出了信息論。其中給出了

關于信息量(Information)與燧(Entropy)的定義，墉實際上是系統(tǒng)信息量的加權平均，也就是系統(tǒng)的

平均信息量。

設S是有s個訓練樣本數據的集合，類標號屬性具有m個不一致值，定義m個不一致類Ci(i=l,2,...,m),

si是類Ci中的樣本數，則對一個給定的訓練樣本分類所需要的期望信息為：

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

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

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

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

的分枝。設Sij是子集Sj中類Ci的樣本數，則按照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)

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

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

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

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

由于這是一個遞歸過程，因此僅僅需要討論對某個特定結點N的分裂方法。

(1)分裂前

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

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

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

容易看出，總端是屬于各個類的記錄的信息量的加權平均。

(2)分裂后

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

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

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

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

k

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

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

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

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

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

建一個結點，并以該屬性為標記，對屬性的每一個值創(chuàng)建分枝，并據此劃分樣本。

K例】顧客數據庫訓練數據集如下表所示：

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

計算每一個屬性的信息增益：

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)建一個以age為標記

的結點，并對每一個屬性值引出一個分蘆枝age="31…40”的樣本都屬于同一類“yes”，該分枝的

端點應該創(chuàng)建一個葉結點。a

incomestudent加,

_rating31..

highnofairno

highnoexcellentno

mediumnofairno

lowyesfairyes

mediumyesexcellentyes

3.剪枝

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

與遲滯修剪。

(1)先剪枝(pre-pruning)

在建樹的過程中，當滿足一定條件，比如InformationGain或者者某些有效統(tǒng)計量達到某個預先設

定的閾值時，結點不再繼續(xù)分裂，內部結點成為一個葉結點。葉結點取子集中頻率最大的類作為自己的標

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

(2)后剪枝(pos-pruning)

與建樹時的訓練集獨立的訓練數據進入決策樹并到達葉結點時，訓練數據的classlabel與葉結點的

classlabel不一致，這時稱之發(fā)生了分類錯誤。當樹建好之后，對每個內部結點，算法通過每個枝條的出

錯率進行加權平均，計算假如不剪枝該結點的錯誤率。假如裁減能夠降低錯誤率，那么該結點的所有兒子

就被剪掉，而該結點成為一片葉。出錯率用與訓練集數據獨立的測試數據校驗。最終形成一棵錯誤率盡可

能小的決策樹。

假如在測試集中出現(xiàn)了類交叉的情況，也就是說，在待挖掘的數據中出現(xiàn)矛盾與不一致的情況。

則在算法步驟3中將出現(xiàn)這樣一種情況：在一個樹結點中，所有的實例并不屬于一個類卻找不到能

夠繼續(xù)分支的屬性。ID3使用下列兩種方案解決這個問題：

①選擇在該結點中所占比例最大的類為標記標識該結點；

②根據該結點中不一致類的概率分布為標記一一標識該結點。

假如在測試集中出現(xiàn)了某些錯誤的實例，也就是說，在待挖掘的數據中，本來應該屬于同一結

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

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

否則以類標志標識該結點。該閾值的選取對決策樹的正確創(chuàng)建具有相當的重要性。假如閾值過小，

可能沒有發(fā)揮應有的作用；假如閾值過大，又可能刪除了應該創(chuàng)建的分支。

4.由決策樹提取分類規(guī)則

能夠提取由決策樹表示的分類規(guī)則，并以IF-THEN的形式表示。具體方法是：從根結點到葉

結點的每一條路徑創(chuàng)建一條分類規(guī)則，路徑上的每一個“屬性一值”對為規(guī)則的前件（即IF部分）

的一個合取項，葉結點為規(guī)則的后件（即THEN部分）。

k例』關于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算法的改進

(1)離散化

ID3算法對符號性屬性的知識挖掘比較簡單，也就是說，該算法對離散性屬性的挖掘更為直觀。

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

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

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

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

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

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

算信息量的方法計算最佳的分段值，然后進一步構建決策樹。

(2)屬性選擇度量

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

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

(3)空缺值處理

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

等填充。

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

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

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

解決的方法是：將分類屬性值分組，決策樹結點能夠測試一個屬性值是否屬于給定的集合。另

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

當一個屬性沿樹的一個給定的分枝重復測試時，將出現(xiàn)重復。復制是拷貝樹中已經存在的子樹。

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

(5)可伸縮性

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

效性與可伸縮性將成為務必關注的問題。面臨數以百萬計的訓練數據集，需要頻繁地將訓練數據在

主存與高速緩存換進換出，從而使算法的性能變得低下。

解決的方法是：將訓練數據集劃分為子集，使得每個子集能夠放在內存；然后由每個子集構造

一棵決策樹；最后，將每個子集得到的分類規(guī)則組合起來，得到輸出的分類規(guī)則。

最近，已經提出了一些強調可伸縮性的決策樹算法，如：SLIQ、SPRINT等。這兩種算法都

使用了預排序技術，并使用了新的數據結構，以利于構造決策樹。

ID3算法對大部分數據集有效，但它不能挖掘域知識。同時，決策樹在計算機中存儲的方式決

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

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

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

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

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

SalaryEducationClass

10,000高中通常

40,000學士較好

15,000學士通常

75,000碩士較好

18,000碩士較好

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

Salary>16,000

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

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

的評價

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

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

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

ifthereisaperson(age>40)and(creditratingisexcellent)thenhewillnotbuya

computer.

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

通常決策樹的劣勢：

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

Irvine機器學習知識庫中，最大能夠同意的數據集僅僅為700KB,2000條記錄。而現(xiàn)代的數據倉庫動輒存

儲幾個G-Bytes的海量數據。用往常的方法是顯然不行的。

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

且降低了分類的準確性。

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

9.4.1分類規(guī)則挖掘的C4.5算法

1.C4.5算法概述

C4.5算法是ID3算法的擴展，但是它比ID3算法改進的部分是它能夠處理連續(xù)型的屬性。首先將連續(xù)型

屬性離散化，把連續(xù)型屬性的值分成不一致的區(qū)間，根據是比較各個屬性Gian值的大小。

2?"離散化''的方法

把連續(xù)型屬性值”離散化”的具體方法是：

1)尋找該連續(xù)型屬性的最小值，并把它賦值給MIN,

尋找該連續(xù)型屬性的最大值，并把它賦值給MAX；

2)設置區(qū)間［MIN,MAX］中的N個等分斷點Ai,它們分別是

Ai=MIN+((MAX-MIN)/N)*i

其中，i=1,2,,N

3)分別計算把［MIN,Ai］與(Ai,MAX)(i=1,2,,N)作為區(qū)間值時的Gain值，并進行比較

4)選取Gain值最大的Ak做為該連續(xù)型屬性的斷點，把屬性值設置為［MIN,Ak］與(Ak,MAX)兩個區(qū)

間值。

3.Gain函數

決策樹是建立在信息理論(InformationTheory)的基礎上的，決策樹的方法循環(huán)地尋找某一標準，它

能夠帶來與本次分類有關的最大信息。構造好的決策樹的關鍵在于如何選擇好的屬性。關于同樣一組記錄集,

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

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

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

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

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

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

選擇的目標分類有關。

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

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

分配的不純度。

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

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

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

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

不純度的最佳評估方法是平均信息量，也就是信息燧(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é)”衡量)，根據它能夠確定在什么樣的層次上選擇什么

樣的變量來分類。

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值手工設置}

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

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

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

values)；可能數據不準確含有噪聲或者者是錯誤的；可能是缺少務必的數據造成了數據的不完整。另外決策

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

性的字段比較難作出準確的預測。而且通常算法在分類的時候，只是根據一個屬性來分類的。

在有噪聲的情況下，完全擬合將導致過分擬合(overfitting),即對訓練數據的完全擬合反而不具有很

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

術也可能產生子樹復制與碎片問題。

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

9.4.2DBlearn算法

1.DBlearn算法概述

DBlearn算法用域知識生成基于關系數據庫的預定義子集的描述。DBlearn算法使用自底向上的

搜索策略，使用以屬性層次形式的域知識，同時該算法使用了關系代數。該算法的事務集是一個關系

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

系統(tǒng)使用關系表作為知識結構：對每一類，它構建一個關系表。這個關系表的屬性是實例集屬性的子

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

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

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

?；膯栴}；假如閾值太大，則生成的規(guī)則比較全面，但同時也可能產生沒有完全通?；c規(guī)則復雜

的問題。

一些屬性域被局部排序從而構成一個層次結構，每一個值都是該值所在層次下面全部值的通常

化。

在從關系表中生成分類規(guī)則時，DBlearn算法使用了兩個基本的算子：

(1)刪除：假如在關系表中有屬性之間存在著關聯(lián)關系，則刪除直到只剩下彼此互不關聯(lián)的屬性。

如年齡與出生年月這兩個屬性存在著年齡=現(xiàn)在時間一出生年月的關聯(lián)關系，因此務必刪除其中一個

屬性，保留另一個屬性。

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

列都能夠通?；癁橛啄辏?-12歲能夠通?；癁橥甑?。

在一個關系表上運行以上兩個算子有可能產生完全一樣的元組，DBlearn算法通過刪除多余的

元組來縮減關系表的大小從而得到類描述表。

2.DBlearn算法描述

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

些錯誤的實例)。

DBIearn算法描述如下：

stepl.從數據庫中選擇與任務有關的數據，如一個包含且只包含一類數據的數據表。

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

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

個更高級別的值，則該屬性被刪除。刪除重復的元組直到表的大小達到用戶定義的閾值。

step3.簡化結果。比如，假如該數據表上的一些元組除了一個屬性不一樣，其他的屬性值都是一模

一樣的，而這個不一樣的屬性的取值能夠通?；癁橐粋€更高層次的符號且這個屬性的取值范圍包含了

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

樣的屬性，它的值用那個符號表示。

step4.把這個數據表轉換成公式。

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

終獲得規(guī)則。在數據挖掘的過程中，該算法是域知識挖掘的一個典型例子。該算法通過改進能夠挖掘

那些包含噪聲數據的不純凈數據，同時能夠做增量學習。

9.4.3分類規(guī)則挖掘的OC1算法

1.OC1算法概述

OC1算法是ObliqueClassifier1的縮寫，即斜面分類1算法。它基于線性規(guī)劃的理論，以斜面

超平面的思想為基礎，使用自頂向下的方法在條件屬性都是正實數類型的搜索空間創(chuàng)建斜面決策樹。

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

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

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

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

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

個超平面(n")。(當n=2時，集合確定一條直線；當n=3時，集合確定一個平面。)

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

是中滿足AUNb的向量U構成的半空間，是R"中滿足的向量U構成的半空間。

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

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

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

面。

R引理』ID3決策樹的每一個結點等價于一個軸平行超平面。(證明略)

大部分決策樹都是在每一個結點檢查某個屬性的值，或者者對該數值屬性進行分段檢查。因此，

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

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

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

(證明略)

2.0C1算法的基本思想

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

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

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

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

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

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

空間中尋找一個''最佳”劃分搜索空間的斜面超平面，以此斜面超平面標識當前結點，把搜索空間分

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

面直至算法終止。

3.OC1算法描述

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

空間；

step2.用這棵樹來對搜索空間進行分類，假如一個半空間的所有實例都屬于同一類，則以該類為標

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

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

法步驟steplo

OC1算法在每一個決策樹結點處的算法描述如下：

/*尋找當前搜索空間的“最佳”斜面超平面參數*/

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

step2.隨機選擇一個斜面超平面”。，令“最佳”斜面超平面/等于該斜面超平面”。，計算該斜面超

平面“0的純潔度小

step3.重復R次下列步驟：

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

依次振蕩斜面超平面兒的系數；

｝直到純潔度/?沒有進一步改進；

step3.2：重復最多J次｛

選擇一個隨機方向，以該隨機方向改變斜面超平面%;

假如改變后的斜面超平面純潔度/"得到改進，轉到步驟1;

)

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

否則令1=/°;

step4.輸出純潔度I對應的超平面。

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

⑴在決策數的每一個結點處如何生成一個斜面超平面?。?/p>

⑵計算超平面純潔度的方法;

4.OC1算法的改進

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

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

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

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

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

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

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

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

“男”對應的編碼為“1000”，符號“女”對應的編碼為“2000”，根據斜面超平面方程EQ”，把實例

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

例很小，但由于其對應的編碼遠遠大于性別為“男”的實例，因此。性別的取值只能在很小的范圍振蕩，

從而影響進一步選擇“最佳”斜面超平面。

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

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

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

（2）OC1改進算法的描述

該部分的算法描述如下：

step1.掃描搜索空間；

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

step3.計算每一個符號屬性的概率分布值；

step4.生成編碼表；

（3）結果分析

下表給出了OC1算法與改進的OC1算法在同一個搜索空間，同樣的隨機改進系數（隨機跳躍次

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

算機科學系捐贈的塔斯馬尼亞州（澳大利亞州名）基礎工業(yè)漁業(yè)部的鮑魚數據庫的數據倉庫的一個采

樣切片。

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

不管是從平均值、最大值還是最小值進行比較，都遠遠高于原算法，大大增強了決策樹（分類規(guī)則）

的正確性與可預測性。

次數OC1算法OC1改進算法

第一次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改進算法的比較

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

1.SLIQ算法概述

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

掘項目)是IBMAlmadenResearchCenter于1996年提出的一種高速可調節(jié)的數據挖掘分類算法。該算法

通過預排序技術，著重解決當訓練集數據量巨大，無法全部放入內存時，如何高速準確地生成決策樹。能同

時處理離散字段與連續(xù)字段。

SLIQ的優(yōu)點：

(1)運算速度快，對屬性值只作一次排序。

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

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

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

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

2.SLIQ算法的關鍵技術

(1)可伸縮性指標

通常決策樹中，使用信息量作為評價結點分裂質量的參數。SLIQ算法中，使用gini指標(giniindex)

代替信息量(Information),gini指標比信息量性能更好，且計算方便。對數據集包含n個類的數據集S,

gini(S)定義為：

gini(S)=1-Epj*pj

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

(2)屬性的分裂方法

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

分裂。

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

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

作為分裂點。從小到大依次取不一致的splitpoint,取InformationGain指標最大(gini最小)的一個就是

分裂點。由于每個結點都需要排序，因此這項操作的代價極大，降低排序成本成為一個重要的問題，SLIQ

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

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

S\尋找當分裂成S，與S-S，兩塊時的gini指標，取到gini最小的時候，就是最佳分裂方法。顯然，這是一

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

度的優(yōu)化。

(3)剪枝

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

Set的一個子集或者者與TrainingSet獨立的數據集進行操作。

3.算法描述

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

輸出數據：用線性表方式表示的二叉決策樹。

算法：

Createnode(root);

Preparefordataofattributelistandclasslist;〃數據準備

Enterqueue(root);〃算法的操縱結構是一個隊列，

該隊列存放當前的所有葉結點

While(notempty(queue))do

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

foralltheleafnodesinthequeuedo

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

Cleanthenewinternalnodeandthepureleafnodeoutofthequeue;〃對應該分裂的類

表進行更換

Letthenewleafnodeenterthequeue;

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

圖9-3計算分裂指標的例子一一當前待分裂Salary,右邊為classhistogram的變化過程。屬性表從上往

下掃描兄;卅隊列里面的結點有峽N36BN3

SnlnryInclc、

InitialHistograms

GN2

廚二結底能扮裂成解門逋;N3轉為內

N3

N2N3

BN3

UpdntcdnsshistORramsand

N3EvaluatefirstsplitfornodeN2<salary?<?=■15)

Z3BB

SalaryListCZIQSSI.ist

R0R

N2

Updateclasshistogram*nnd

EvaluatefirstsplitfornodeN3(salaryv-40)

N6

1.CART算法概述

CART算法可用來自動探測出高度復雜數據的潛在結構，重要模式與關系.這種探測出的知識又可用來構造精確與可靠的

預測模型，應用于分類客戶、準確直郵、偵測通信卡及信用卡詐騙與管理信用風險。

技術上講，CART技術可稱之二元回歸分化技術.由于根結點總是被分為兩個子結點并不斷分化，故稱之二元回歸。

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

(1)分裂樹點

(2)確定何時結束分裂

(3)為每一葉結點指定類型或者預測值

2.CART算法的分裂規(guī)則的選擇

將一個結點分化成兩個子結點，CART總是問些“是”或者“非”的問題。來分化根結點成二個子結點，以“是”為回

答的案例歸入左子樹結點，而“否”為回答的案例歸為右子樹結點。

K例X貸款申請中風險分析。有訓練集包含100個高風險與100個低風險的測試案例，構造一棵二叉樹如圖1