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

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

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

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

9.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

信息增益（續(xù)）計(jì)算熵Info（X，T）如果考慮某個(gè)輸入變量X，將訓(xùn)練集T按照X的值劃分為n個(gè)子集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ù)）計(jì)算增益Gain（X,T）

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

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

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

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

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

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

=0.940比特2/3/2023381.

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

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比特通過檢驗(yàn)x1獲得的信息增益是：

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

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

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

=0.892比特通過檢驗(yàn)x2獲得的信息增益是：

Gain(x2)

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

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

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

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

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

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

結(jié)果2/3/2023452.

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

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

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