第9章預測建模：分類和回歸

五邑大學計算機學院何國輝數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

DataWarehouseandDataMining2/3/20231數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

DataWarehouseandDataMining第九章預測建模：分類和回歸2/3/20232數(shù)據(jù)挖掘的任務：除模式挖掘以外，還包括描述建模和預測建模。預測建模的目的是建立一個模型，該模型允許人們根據(jù)已知的屬性值來預測其它某個未知的屬性值。當被預測的屬性是范疇型時稱為分類。當被預測的屬性是數(shù)量型時稱為回歸。9.0

基本概念2/3/20233在預測模型中，一個變量被表達成其它變量的函數(shù)。預測建模的過程可以看作是學習一種映射或函數(shù)Y=f（X；θ）。其中f是模型結構的函數(shù)表達式，θ是f中的未知參數(shù)，X稱為輸入量，是一個p維向量，代表觀察到的對象的p的屬性值。Y通常被稱為響應變量，代表預測的結果。如果Y是數(shù)量型變量，則學習從向量X到Y的映射的過程稱為回歸。如果Y是范疇型變量，則稱之為分類。

9.1

預測建模簡介2/3/20234預測建模的訓練數(shù)據(jù)由n對（X，Y）組成。預測建模的過程就是根據(jù)訓練數(shù)據(jù)擬合出模型Y=f（X；θ）。模型中的擬合過程由以下幾步組成：確定模型f的結構。確定參數(shù)θ的值。θ值是通過在數(shù)據(jù)集上最小化（或最大化）一個評分函數(shù)確定的。如何搜素最佳θ值涉及到優(yōu)化問題。9.1

預測建模簡介（續(xù)）2/3/202359.1.1

用于預測的模型結構人們通常事先并不知道f（X；θ）的形式，為f選擇一個合適的函數(shù)形式是非常具有挑戰(zhàn)性的工作。2/3/202361.

用于回歸的模型主要包括：線性回歸模型非線性回歸模型分段線性模型2/3/20237（1）

線性回歸模型是最簡單的回歸模型。在這種模型中，響應變量Y是輸入變量X的線性函數(shù)，即：?=a0+a1X1+a2X2+...+apXp。其中：Xi（0≤i≤p）是輸入向量X的分量，模型的參數(shù)θ={a0，a1，a2，...，ap}?代表模型的預測值，而Y代表實際觀察到的值。擬合的質量由預測值?和實際值Y之間的差來衡量。2/3/20238（1）

線性回歸模型（續(xù)）2/3/20239（2）

非線性回歸模型通過在基本的線性回歸模型上添加多項式項，可以得到非線性回歸模型。幾何意義：多維空間中的一個超曲面。舉例：一個三次多項式回歸模型： ?=a0+a1X1+a2X22+a3X332/3/202310（2）

非線性回歸模型（續(xù)）通過對變量進行變換，可以將非線性模型轉換成線性的。令Z1=X1，Z2=X22，Z3=X33，可以將上述三次多項式回歸模型轉換成線性形式，結果為：

?=a0+a1Z1+a2Z2+a3Z3將線性模型擴展到非線性模型提高了模型的復雜度。線性模型是非線性模型的特例。2/3/202311（3）

分段線性模型響應變量Y是輸入向量X的局部線性函數(shù)，該模型在p維空間的不同區(qū)域具有不同的函數(shù)形式。是基本的線性回歸模型進行擴展的方法。當p=1時，該模型表示由k個不同的線段逼近的一條曲線。當p>1時，該模型表示由多個超平面逼近的一個曲面。2/3/2023122.

用于分類的預測模型主要有兩種：判別模型概率模型2/3/202313（1）

判別模型判別模型的輸入是輸入向量X，輸出是響應變量Y。Y的取值為{C1，C2，...，Cm}，其中Ci表示類別。目的：只要知道各個類別的決策區(qū)域，根據(jù)輸入向量X的取值，就可以確定響應變量Y的值，實現(xiàn)分類預測。2/3/202314（1）

判別模型（續(xù)）舉例：當X的取值介于0和a之間時，Y的取值為C1；X的取值介于a和b之間時，Y的取值為C2；X的取值大于b時，Y的取值為C3。2/3/202315（1）

判別模型（續(xù)）回歸模型與判別模型比較在回歸模型中，模型的函數(shù)形式表示的是Y如何與X關聯(lián)，響應變量Y代表和第p+1維，關心的重點是輸入X時Y的取值是什么。在判別分類中，響應變量Y同樣代表和第p+1維，但它的取值早已確定，是C1、C2、...、Ck中的一個。在實際的分類問題中，類別之間的邊界是不可能那么清晰的。2/3/202316（2）

概率模型分類的概率建模是要針對每一個類別Ci估計一種分布或密度函數(shù)ρ（X|Ci，θi），其中θi是該函數(shù)的參數(shù)，它反映了Ci類的主要特征。如果各個均值離得足夠遠，而且方差足夠小，則各個類在輸入空間中可以被很好地分割開來，從而使得分類的準確性最高。主要代表：貝葉斯分類方法。2/3/2023179.1.2

用于預測的評分函數(shù)給定訓練數(shù)據(jù)D={（X(1)，Y(1)），（X(2)，Y(2)），...，（X(n)，Y(n)）}，令?（i）為模型f（X；θ）使用參數(shù)值θ根據(jù)輸入向量X(i)做出的預測值，則評分函數(shù)應該為預測值?（i）與實際值Y(i)間差值的函數(shù)。2/3/2023189.1.2

用于預測的評分函數(shù)（續(xù)）幾種評分函數(shù)：對于回歸，普遍使用的評分函數(shù)--誤差平方和。對于分類，普遍使用的是--誤分類率。其中，當時，，否則等于1。2/3/2023199.1.3

用于預測的搜索和優(yōu)化策略搜索和優(yōu)化的目標是：確定預測模型f（X；θ）的形式f及其參數(shù)值θ，以使評分函數(shù)達到最小值（或最大值）常用的優(yōu)化方法：爬山法、最陡峭下降法、期望最大化法。常用的搜索方法：貪婪搜索法、分支界定法、寬度（深度）優(yōu)先遍歷法等。2/3/202320決策樹分類屬于判別模型。決策樹分類的主要任務是要確定各個類別的決策區(qū)域。在決策樹分類模型中，不同類別之間的邊界通過一個樹狀結構來表示。9.2

決策樹分類2/3/202321舉例：下圖給出了一個商業(yè)上使用的決策樹的例子。它表示了一個關心電子產品的用戶是否會購買PC（buys_computer）的知識，用它可以預測某條記錄（某個人）的購買意向。9.2

決策樹分類（續(xù)）2/3/202322其中：內部節(jié)點（方形框）代表對記錄中某個屬性的一次測試，葉子節(jié)點（橢圓形框）代表一個類別。9.2

決策樹分類（續(xù)）2/3/202323用決策樹進行分類的步驟：第一步，利用訓練集建立一棵決策樹，得到一個決策樹分類模型。第二步，利用生成的決策樹對輸入數(shù)據(jù)進行分類。對于輸入的記錄，從根節(jié)點依次測試記錄的屬性值，直至到達某個葉子節(jié)點，從而找到該記錄所屬的類別。9.2

決策樹分類（續(xù)）2/3/202324構造決策樹是采用自上而下的遞歸構造方法。以多叉樹為例，如果一個訓練數(shù)據(jù)集中的數(shù)據(jù)有幾種屬性值，則按照屬性的各種取值把這個訓練數(shù)據(jù)集再劃分為對應的幾個子集（分支），然后再依次遞歸處理各個子集。反之，則作為葉結點。問題的關鍵是建立一棵決策樹。這個過程通常分為兩個階段：建樹（TreeBuilding）：決策樹建樹算法見下，這是一個遞歸的過程，最終將得到一棵樹。剪枝（TreePruning）：剪枝的目的是降低由于訓練集存在噪聲而產生的起伏。9.2

決策樹分類（續(xù)）2/3/2023259.2.1

建樹階段遞歸處理過程采用分而治之的方法。通過不斷地將訓練樣本劃分成子集來構造決策樹。假設給定的訓練集T總共有m個類別，則針對T構造決策樹時，會出現(xiàn)以下三種情況：如果T中所有樣本的類別相同，那么決策樹只有一個葉子節(jié)點。如果T中沒有可用于繼續(xù)分裂的變量，則將T中出現(xiàn)頻率最高的類別作為當前節(jié)點的類別。如果T包含的樣本屬于不同的類別，根據(jù)變量選擇策略，選擇最佳的變量和劃分方式將T分為幾個子集T1、T2、...、Tk，每個數(shù)據(jù)子集構成一個內部節(jié)點。2/3/2023269.2.1

建樹階段（續(xù)）對于某個內部節(jié)點繼續(xù)進行判斷，重復上述操作，直到滿足決策樹的終止條件為止。終止條件是：節(jié)點對應的所有樣本屬于同一個類別，或者T中沒有可用于進一步分裂的變量。2/3/2023279.2.1

建樹階段（續(xù)）決策樹構建算法：輸入：訓練集T，輸入變量集A，目標（類別）變量Y輸出：決策樹TreeGenerate_decision_tree（T，A，Y）1；如果T為空，返回出錯信息；2；如果T的所有樣本都屬于同一個類別C，則用C標識當前節(jié)點并返回；2/3/2023289.2.1

建樹階段（續(xù)）3；如果沒有可分的變量，則用T中出現(xiàn)頻率最高的類別標識當前節(jié)點并返回；4；根據(jù)變量選擇策略選擇最佳變量X將T分為k個子集（T1、T2、...、Tk）；如何選擇分裂變量呢？5；用X標識當前節(jié)點；6；對T的每個子集Ti，生成新節(jié)點：7；NewNode=Generate_decision_tree（Ti，A-X，Y）8；生成一個分枝，該分枝由節(jié)點X指向NewNode；9；返回當前節(jié)點。2/3/2023299.2.1

建樹階段（續(xù)）有兩種比較流行的分裂變量選擇方法：信息增益（InformationGain）：指標的原理來自于信息論。1948年，香農（C.E.Shannon）提出了信息論。其中給出了關于信息量（Information）和熵（Entropy）的定義，熵實際上是系統(tǒng)信息量的加權平均，也就是系統(tǒng)的平均信息量。增益比（Gain_ratio）2/3/2023301.

信息增益由Quinlan在80年代中期提出的ID3算法是分類規(guī)則挖掘算法中最有影響的算法。該算法提出了使用信息增益作為衡量節(jié)點分裂質量的標準。信息增益最大的變量被認為是最佳的分裂變量。2/3/2023311.

信息增益（續(xù)）計算信息增益的思路：首先計算不考慮任何輸入變量的情況下，要確定T中任一樣本所屬類別需要的信息Info(T);計算引入每個輸入變量X后，要確定T中任一樣本所屬類別需要的信息Info（X，T）；計算兩者的差Info(T)-Info（X，T），此即為變量X的信息增益，記為Gain（X,T）。2/3/2023321.

信息增益（續(xù)）計算熵Info(T)如果不考慮任何輸入變量，而將訓練集T中的所有樣本僅按照響應變量Y的值分到m個不相交的類別C1、C2、...、Cm的話，要確定任一樣本所屬的類別需要的信息為：mInfo(T)＝－Σi=1

(|Ci|/|T|).log2(|Ci|/|T|))以2為底的原因是：信息按二進制位編碼2/3/2023331.

信息增益（續(xù)）計算熵Info（X，T）如果考慮某個輸入變量X，將訓練集T按照X的值劃分為n個子集T1、T2、...、Tn的話，要確定T中任一樣本所屬的類別需要的信息為：其中：

注：Sj為Tj中屬于類別Cj的樣本子集。nInfo(X，T)＝－Σi=1

(|Ti|/|T|).Info(Ti)mInfo(Ti)＝－Σj=1

(|Sj|/|Ti|).log2(|Sj|/|Ti|)2/3/2023341.

信息增益（續(xù)）計算增益Gain（X,T）

Gain（X,T）=Info（T）-Info（X，T）

所有變量的信息增益計算完后，可以根據(jù)信息增益的大小多所有輸入變量進行排序，優(yōu)先使用信息增益大的變量。2/3/2023351.

信息增益（續(xù)）舉例：本例將如下表數(shù)據(jù)作為訓練集。2/3/2023361.

信息增益（續(xù)）2/3/2023371.

信息增益（續(xù)）其中：有9個樣本屬于類1，有5個樣本屬于類2。因此分區(qū)前的熵為：

Info(T)＝-9/14.log2(9/14)-5/14.log2(5/14)

=0.940比特2/3/2023381.

信息增益（續(xù)）根據(jù)屬性1把初始樣本集分區(qū)成3個子集（檢驗x1表示從3個值A，B或C中選擇其一）后，得出結果：

Infox1(T)＝5/14（-2/5log2(2/5)-3/5log2(3/5)）

+4/14（-4/4log2(4/4)-0/4log2(0/4)）

+5/14（-3/5log2(3/5)-2/5log2(2/5)）

=0.694比特通過檢驗x1獲得的信息增益是：

Gain(x1)=0.940–0.694=0.246比特2/3/2023391.

信息增益（續(xù)）類似地，根據(jù)屬性3檢驗x2表示從真或假兩個值選擇其一），類似地有： Infox2(T)＝6/14（-3/6log2(3/6)-3/6log2(3/6)）

+8/14（-6/8log2(6/8)-2/8log2(2/8)）

=0.892比特通過檢驗x2獲得的信息增益是：

Gain(x2)

=0.940–0.892=0.048比特2/3/2023401.

信息增益（續(xù)）依次類推，計算出其它屬性獲得的增益。通過獲得的兩個增益比較，按照增益準則，將選擇x1作為分區(qū)數(shù)據(jù)庫T的最初檢驗（作為根節(jié)點創(chuàng)建）。為了求得最優(yōu)檢驗還必須分析關于屬性2的檢驗，它是連續(xù)取值的數(shù)值型屬性。ID3算法無法解決數(shù)值型屬性，需要通過其改進型--C4.5算法。2/3/2023411.

信息增益（續(xù)）T1檢驗X1:屬性1=？T2T3ABC葉結點根據(jù)屬性1進行數(shù)據(jù)集劃分2/3/2023421.

信息增益（續(xù)）在得到前面的第一次劃分以后，再分別對劃分后的T1、T2、T3三個子集繼續(xù)分裂。其中T2對應的數(shù)據(jù)子集都屬于同一個類別類1，無需繼續(xù)分裂。2/3/2023431.

信息增益（續(xù)）結合C4.5算法后，得到的決策樹。X1:屬性1X4:屬性2X5:屬性3類1類2類1類2類1檢驗結點ABC<=70>70真假葉結點2/3/2023441.

信息增益（續(xù)）決策樹可以用偽代碼的形式表示，這種偽代碼用IF-THEN結構對決策樹進行分枝。If屬性1=A then if屬性2<=70 then 類別=類1; else 類別=類2;Elseif屬性1=Bthen 類別=類1;elseif屬性1=Cthen if屬性3=真then 類別=類2; else 類別=類1.

結果2/3/2023452.

增益比信息增益作為分裂變量選擇標準時，比較傾向于選擇那些取值比較多且均勻的變量，如：產品號、顧客號等。即：增益標準對緊湊型決策樹的構造有很好的效果，但也存在一個嚴重缺陷：對具有多輸出的檢驗有嚴重的偏差。Quinlan在1993年對ID3算法進行了改進，提出了一種新的決策樹分類算法C4.5。2/3/2023462.

增益比（續(xù)）C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進：1)用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；2)在樹構造過程中進行剪枝；3)能夠完成對連續(xù)屬性的離散化處理；4)能夠對不完整數(shù)據(jù)進行處理。2/3/2023472.

增益比（續(xù)）解決方法：根據(jù)info(S)的定義，指定一個附加的參數(shù)：其中：T1，T2，...，Tn為按照變量X的值對T進行劃分后的子集。含義：通過把集T分區(qū)成n個子集