數(shù)據(jù)挖掘 第3章分類

1、高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用王朝霞 主編 施建強 楊慧娟 陳建彪 副主編DATA MINING曹 潔 寧亞輝 王偉嘉 袁曉東 張衛(wèi)明 編者（按姓氏首字母排序） 劉 鵬 張 燕 總主編數(shù)據(jù)挖掘第三章分類of562高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用 分類是一種很重要的數(shù)據(jù)挖掘技術(shù)，也是數(shù)據(jù)挖掘研究的重點和熱點之一。分類的目的是分析輸入數(shù)據(jù)，通過訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來的特性，為每一個類找到一種準(zhǔn)確描述或者模型，這種描述常常用謂詞來表示。由此生成的類描述用來對未來的測試數(shù)據(jù)進(jìn)行分類。盡管這些未來測試數(shù)據(jù)的類標(biāo)簽是未知的，仍可以由此預(yù)測這些新數(shù)據(jù)所屬的類。也可以由此對數(shù)

2、據(jù)中每一個類有更好的理解。More應(yīng)用市場：醫(yī)療診斷、人臉檢測、故障診斷和故障預(yù)警 3.1基本概念第三章分類3.2決策樹3.3貝葉斯分類3.5實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)習(xí)題3.4支持向量機of563高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用 分類（Classification）是一種重要的數(shù)據(jù)分析形式，它提取刻畫重要數(shù)據(jù)類的模型。這種模型稱為分類器，預(yù)測分類的（離散的、無序的）類標(biāo)號。這些類別可以用離散值表示，其中值之間的次序沒有意義。3.1.1 分類的基本概念of5643.1 基本概念第三章 分類 分類也可定義為： 分類的任務(wù)就是通過學(xué)習(xí)得到一個目標(biāo)函數(shù)(Target Func

3、tion) ，把每個屬性集x映射到一個預(yù)先定義的類標(biāo)號y 。 數(shù)據(jù)分類過程有兩階段： （1）學(xué)習(xí)階段（構(gòu)建分類模型）。 （2）分類階段（使用模型預(yù)測給定數(shù)據(jù)的類標(biāo)號）。3.1.2 分類的過程of5653.1 基本概念第三章 分類建立分類模型的一般方法 分類器的性能和所選擇的訓(xùn)練集和測試集有著直接關(guān)系。一般情況下，先用一部分?jǐn)?shù)據(jù)建立模型，然后再用剩下的數(shù)據(jù)來測試和驗證這個得到的模型。如果使用相同的訓(xùn)練集和測試集，那么模型的準(zhǔn)確度就很難使人信服。保持法和交叉驗證是兩種基于給定數(shù)據(jù)隨機選樣劃分的，是常用的評估分類方法準(zhǔn)確率的技術(shù)。3.1.3 分類器性能的評估方法of5663.1 基本概念第三章 分類

4、73.2決策樹第三章分類3.1基本概念3.3貝葉斯分類3.5實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)習(xí)題3.4支持向量機of567高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用8 決策樹（Decision Tree）是一種類似于流程圖的樹結(jié)構(gòu)，其中每個內(nèi)部節(jié)點（非樹葉節(jié)點）表示在屬性上的測試，每個分支表示該測試上的一個輸出，而每個樹葉節(jié)點存放一個類標(biāo)號，樹的最頂層節(jié)點是根節(jié)點。決策樹生成方式一般情況下都是由上而下的。每次不同的事件或決策都有可能引發(fā)至少兩個以上的事件，形成不同的結(jié)果，這種決策方法用圖形表示出來很像一棵樹，所以稱之為決策樹。決策樹是一種簡單且廣泛使用的分類器。通過訓(xùn)練數(shù)據(jù)來構(gòu)建決策樹

5、，可高效地對未知的數(shù)據(jù)進(jìn)行分類。3.2.1 決策樹概述of5683.2 決策樹第三章 分類 決策樹是數(shù)據(jù)挖掘的有力工具之一，決策樹學(xué)習(xí)算法是從一組樣本數(shù)據(jù)集（一個樣本數(shù)據(jù)也可以稱為實例）為基礎(chǔ)的一種歸納學(xué)習(xí)算法，它著眼于從一組無次序、無規(guī)則的樣本數(shù)據(jù)（概念）中推理出決策樹表示形式的分類規(guī)則。9 基于決策樹的決策算法是屬于實用性很好的總結(jié)預(yù)測算法之一，是一個趨近于非連續(xù)型函數(shù)值的算法。決策樹在各行各業(yè)有著非常多的廣泛應(yīng)用，如在醫(yī)院的臨床決策、人臉檢測、故障診斷、故障預(yù)警、醫(yī)療數(shù)據(jù)挖掘、案例分析、分類預(yù)測的軟件系統(tǒng)等方面都有很大的用處。 決策樹的最佳用途是圖解說明如何領(lǐng)會決策與相關(guān)事件的相互作用。

6、 3.2.2 決策樹的用途和特性of5693.2 決策樹第三章 分類10 決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程。它提供一種在什么條件下會得到什么值的類似規(guī)則的方法。決策樹分為分類樹和回歸樹兩種，分類樹對離散變量做決策樹，回歸樹對連續(xù)變量做決策樹。 直觀看，決策樹分類器就像判斷模塊和終止塊組成的流程圖，終止塊表示分類結(jié)果（也就是樹的葉子）。判斷模塊表示對一個特征取值的判斷（該特征有幾個值，判斷模塊就有幾個分支）。3.2.3 決策樹工作原理of56103.2 決策樹第三章 分類買電腦的決策樹1111 上圖表示了一個關(guān)心電子產(chǎn)品的用戶是否會購買電腦，用它可以預(yù)測某條記錄（某個人）的購買意向。樹

7、中包含了三種節(jié)點：根節(jié)點（root rode），它沒有入邊，但有兩條或多條出邊。子節(jié)點（child node），恰有一條入邊和兩條或多條出邊。葉節(jié)點（leaf node ）或終節(jié)點（terminal node），恰有一條入邊，但沒有出邊。 在決策樹中，每個葉節(jié)點都賦予一個類標(biāo)號。非終節(jié)點（包括根節(jié)點和內(nèi)部節(jié)點）包含屬性測試條件，用以分開具有不同特性的記錄。這棵決策樹對銷售記錄進(jìn)行分類，指出一個電子產(chǎn)品消費者是否會購買一臺計算機。每個內(nèi)部節(jié)點（方形框）代表對某個屬性的一次檢測。每個葉節(jié)點（橢圓框）代表一個類。of56113.2 決策樹第三章 分類1212 決策樹分類算法應(yīng)用的完整流程應(yīng)包含建樹和

8、應(yīng)用。建樹是從經(jīng)驗數(shù)據(jù)中獲取知識，進(jìn)行機器學(xué)習(xí)，建立模型或者構(gòu)造分類器，是決策樹算法的工作重點，通常又將其分為建樹和剪枝兩個部分。 決策樹構(gòu)建的基本步驟如下： 1.開始，所有記錄看作一個節(jié)點。 2.遍歷每個變量的每一種分割方式，找到最好的分割點。 3.分割成多個節(jié)點N1，N2，,Nm（m的數(shù)量與當(dāng)前的屬性相關(guān)）。 4.對N1，N2，,Nm分別繼續(xù)執(zhí)行23步，直到每個節(jié)點足夠“純”為止。（“純”的含義是要么全部是“是”，要么全部是“否”）。3.2.4 決策樹構(gòu)建步驟of56123.2 決策樹第三章 分類131313 樹的主體建好后，接下來便是對其剪枝。 決策樹的剪枝一般通過極小化決策樹整體的損失

9、函數(shù)或代價函數(shù)來實現(xiàn)。 決策樹剪枝常用的方法有兩種：預(yù)剪枝和后剪枝。 預(yù)剪枝是根據(jù)一些原則盡早停止樹的增長，如樹的深度達(dá)到用戶所要的深度、節(jié)點中樣本個數(shù)少于用戶指定個數(shù)等。預(yù)剪枝在建立樹的過程中決定是否需要繼續(xù)劃分或分裂訓(xùn)練樣本來實現(xiàn)提前停止樹的構(gòu)造，一旦決定停止分枝，就將當(dāng)前節(jié)點標(biāo)記為葉節(jié)點。 后剪枝是通過在完全生長的樹上剪去分枝實現(xiàn)的，通過刪除節(jié)點的分支來剪去樹節(jié)點。of56133.2 決策樹第三章 分類141414 1.認(rèn)識決策樹 1）決策樹的生成過程 一棵決策樹的生成過程主要分為以下3個部分： （1）特征選擇：特征選擇是指從訓(xùn)練數(shù)據(jù)眾多的特征中選擇一個特征作為當(dāng)前節(jié)點的分裂標(biāo)準(zhǔn)，如何選

10、擇特征有著很多不同量化評估標(biāo)準(zhǔn)，從而衍生出不同的決策樹算法。 （2）決策樹生成：根據(jù)選擇的特征評估標(biāo)準(zhǔn)，從上至下遞歸地生成子節(jié)點，直到數(shù)據(jù)集不可分則決策樹停止生長。 （3）剪枝：決策樹容易過擬合，一般都需要剪枝，縮小樹結(jié)構(gòu)規(guī)模、緩解過擬合。3.2.5 決策樹算法原理of56143.2 決策樹第三章 分類15151515 基于信息論的決策樹算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來。 CART和C4.5支持?jǐn)?shù)據(jù)特征為連續(xù)分布時的處理，主要通過使用二元切分來處理連續(xù)型變量，即求一個特定的值分裂值：特征值大于分裂值就走左子樹，或者就走右子樹。 ID3

11、算法建立在“奧卡姆剃刀”的基礎(chǔ)上，越是小型的決策樹越優(yōu)于大的決策樹。ID3算法中根據(jù)信息論的信息增益評估和選擇特征，每次選擇信息增益最大的特征來做判斷模塊。 C4.5是ID3的一個改進(jìn)算法，繼承了ID3算法的優(yōu)點。C4.5算法用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足，在樹構(gòu)造過程中進(jìn)行剪枝；能夠完成對連續(xù)屬性的離散化處理；能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。 CART算法采用的是基尼（Gini）指數(shù)（選Gini指數(shù)最小的特征s）作為分裂標(biāo)準(zhǔn)，同時它也是包含后剪枝操作。of56153.2 決策樹第三章 分類16161616 2. ID3算法 1）ID3算法的信息論基礎(chǔ)

12、（1）信息熵 信息熵：在概率論中，信息熵給了一種度量不確定性的方式，是用來衡量隨機變量不確定性的，熵就是信息的期望值。若待分類的事物可能劃分在N類中，分別是x1，x2，,xn，每一種取到的概率分別是p1，p2，,pn，那么X的熵就定義為： 從定義中可知： 當(dāng)隨機變量只取兩個值時，即X的分布 則熵為：of56163.2 決策樹第三章 分類171717171717 （2）條件熵 假設(shè)有隨機變量（X,Y）,其聯(lián)合概率分布為：P(X=xi,Y=yi)=pij,i=1,2,n;j=1,2,m。則條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性，其定義為X在給定條件下Y的條件概率分布的熵

13、對X的數(shù)學(xué)期望： 若是樣本的特征只有兩個值(X1=0，X2=1),對應(yīng)(出現(xiàn)，不出現(xiàn))，如文本分類中某一個單詞的出現(xiàn)與否。那么對于特征二值的情況，用T代表特征，用t代表T出現(xiàn)， 表示該特征不出現(xiàn)。那么： 與前面的公式對比一下，P(t)就是T出現(xiàn)的概率，P( )就是T不出現(xiàn)的概率，結(jié)合信息熵的計算公式，可得：of56173.2 決策樹第三章 分類1818181818 （3）信息增益 信息增益（Information Gain）表示得知特征X的信息后，而使得Y的不確定性減少的程度。定義為： 信息增益是針對一個一個的特征而言的，就是看一個特征X，系統(tǒng)有它和沒它的時候信息量各是多少，兩者的差值就是這個

14、特征給系統(tǒng)帶來的信息增益。 對于特征取值為二值的情況，特征T給系統(tǒng)帶來的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差：of56183.2 決策樹第三章 分類191919191919 3. C4.5算法 C4.5算法同樣以“信息熵”作為核心，是ID3基礎(chǔ)上的優(yōu)化改進(jìn)，同時，也保持了分類準(zhǔn)確率高、速度快的特點。 1）基本思想 信息增益C4.5算法挑選具有最高信息增益率的屬性為測試屬性。對樣本集T，假設(shè)變量a有k個屬性，屬性取值a1，a2，,an，對應(yīng)a取值為ai的樣本個數(shù)分別為ni，若n是樣本的總數(shù)，則應(yīng)有n1+n2+nk=n, Quinlan利用屬性a的熵值H(X,a),來定義為了獲

15、取樣本關(guān)于屬性a的信息所需要付出的代價，即： 信息增益率定義為平均互信息與獲取a信息所付出代價的比值，即：of56193.2 決策樹第三章 分類20202020202020 4. CART 算法 CART算法生成的是一棵二叉樹。它采用的是一種二分遞歸分割技術(shù)，每次都將當(dāng)前的數(shù)據(jù)集分為兩個互不相交子集，使得所有非葉子節(jié)點都只有兩個分支。 1）分裂屬性的選擇標(biāo)準(zhǔn) CART算法分裂屬性的選擇標(biāo)準(zhǔn)為Gini指數(shù)。CART算法選擇具有最小Gini指數(shù)的屬性為當(dāng)前數(shù)據(jù)集的分裂屬性。Gini指標(biāo)分類方法適用于具有連續(xù)性或離散性屬性的數(shù)據(jù)集。 設(shè)S為具有s個樣本的數(shù)據(jù)集，所有樣本總共包含m個不同的類別Ci，i

16、1,2,m ，那么Gini指標(biāo)為： 其中Pi為樣本屬性類別Ci的概率。of56203.2 決策樹第三章 分類2121212121212121 根據(jù)CART算法構(gòu)造的是一棵二叉樹，所以在CART算法中是用Gini指標(biāo)進(jìn)行二元劃分，對于數(shù)據(jù)集S的任何一個屬性A的任何一種取值a，可以將數(shù)據(jù)集S劃分成S1和S2兩個子集，對應(yīng)屬性A，Gini指標(biāo)的計算公式如下： 其中|S|表示數(shù)據(jù)集S的個數(shù)。當(dāng)GiniA(S)最小時，屬性A就為數(shù)據(jù)集S的最佳分裂屬性，S1和S2就是按屬性A的取值a對數(shù)據(jù)集S的劃分。 2）CART算法建樹過程 CART算法建樹過程見數(shù)據(jù)挖掘一書的第46頁。of56213.2 決策樹第三章

17、 分類22223.3貝葉斯分類第三章分類3.1基本概念3.2決策樹3.5實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)習(xí)題3.4支持向量機of5622高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用2323 貝葉斯分類是一類分類算法的總稱，這類算法均以貝葉斯定理（Bayes theorem）為基礎(chǔ)，采用了概率推理方法。3.3.1 貝葉斯定理of56233.3 貝葉斯分類第三章 分類 條件概率：表示事件B已經(jīng)發(fā)生的前提下，事件A發(fā)生的概率，稱為事件B發(fā)生下事件A的條件概率。其基本求解公式為： 貝葉斯定理之所以有用，是因為在生活中經(jīng)常遇到這種情況：可以很容易直接得出P(A|B),P(B|A)則很難直接得出，但

18、人們往往更關(guān)心P(B|A),貝葉斯定理打通了從P(A|B)獲得P(B|A)的道路。 貝葉斯定理：242424 樸素貝葉斯分類是貝葉斯分類的一種，樸素貝葉斯分類與貝葉斯分類相比，后者需要花很大的時間和空間復(fù)雜度去計算類條件概率。 1. 樸素貝葉斯分類原理 樸素貝葉斯的思想基礎(chǔ)是這樣的：對于給出的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，哪個最大，就認(rèn)為此待分類項屬于哪個類別。 樸素貝葉斯分類的正式定義如下： （1）設(shè)x=a1,a2,am,為一個待分類項，而每個a為x的一個特征屬性。 （2）有類別集合C=y1,y2,yn。 （3）計算P(y1|x),P(y2|x),P(yn|x)。 （4

19、）如果P(yk|x)=maxP(y1|x),P(y2|x),P(yn|x),則xyk。of56243.3 貝葉斯分類第三章 分類3.3.2 樸素貝葉斯分類原理與流程25252525 2.樸素貝葉斯分類流程 整個樸素貝葉斯分類可分為三個階段： 第一階段是準(zhǔn)備工作階段，這個階段的任務(wù)是為樸素貝葉斯分類做必要的準(zhǔn)備，主要工作是根據(jù)具體情況確定特征屬性，并對每個特征屬性進(jìn)行適當(dāng)劃分，然后由人工對一部分待分類項進(jìn)行分類，形成訓(xùn)練樣本集合。 第二階段是分類器訓(xùn)練階段，這個階段的任務(wù)就是生成分類器，主要工作是計算每個類別在訓(xùn)練樣本中的出現(xiàn)頻率及每個特征屬性劃分對每個類別的條件概率估計，并將結(jié)果進(jìn)行記錄。 第

20、三階段是應(yīng)用階段。 這個階段的任務(wù)是使用分類器對分類項進(jìn)行分類，其輸入是分類器和待分類項，輸出是待分類項與類別的映射關(guān)系。of56253.3 貝葉斯分類第三章 分類2626262626 樸素貝葉斯分類的流程圖如下圖。of56263.3 貝葉斯分類第三章 分類2727272727 貝葉斯分析中的三要素（即貝葉斯統(tǒng)計三要素，一要素是先驗概率P(A),二要素是條件概率P(A|B),最終得到三要素即后驗概率P(B|A)。 理解貝葉斯分析最好的方法即圖像法，如圖所示。A為紅圈，B為藍(lán)圈，AB為紫圈。這里的A（紅圈的面積即先驗，后驗是陰影占藍(lán)圈（B）的百分比。of56273.3 貝葉斯分類第三章 分類3.

21、3.3 貝葉斯分析282828282828 貝葉斯決策主要包含四個部分：數(shù)據(jù)（D）、假設(shè)（W）、目標(biāo)（O）和決策（S）。 貝葉斯決策步驟： 1.理清因果鏈條，確定哪個是假設(shè)，哪個是證據(jù)。 2.給出所有可能假設(shè)，即假設(shè)空。 3.假設(shè)，即假設(shè)空間。 4.根據(jù)貝葉斯概率公式求解后驗概率，得到假設(shè)空間的后驗概率分布。 5.利用后驗概率求解條件期望，得到條件期望最大值對應(yīng)的行為。 貝葉斯決策如果一旦變成自動化的計算機算法，它就是機器學(xué)習(xí)。用貝葉斯決策詮釋一個最簡單的機器學(xué)習(xí)分類算法，那就是樸素貝葉斯。of56283.3 貝葉斯分類第三章 分類3.3.4 貝葉斯決策2929293.4支持向量機第三章分類3

22、.1基本概念3.2決策樹3.5實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)習(xí)題3.3貝葉斯分類of5629高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用303030 支持向量機（SVM）是根據(jù)統(tǒng)計學(xué)習(xí)理論中的結(jié)構(gòu)風(fēng)險最小化原則提出的一種經(jīng)典的機器學(xué)習(xí)方法，現(xiàn)已發(fā)展為機器學(xué)習(xí)領(lǐng)域的一個重要分支。3.4.1 支持向量機主要思想of56303.4 支持向量機第三章 分類 SVM主要思想是針對兩類分類問題的，尋找一個超平面作為兩類訓(xùn)練樣本點的分割，以保證最小的分類錯誤率。在線性可分的情況下，存在一個或多個超平面使得訓(xùn)練樣本完全分開，SVM的目標(biāo)是找到其中的最優(yōu)超平面，最優(yōu)超平面是使得每一類數(shù)據(jù)與超平面距離最近

23、的向量與超平面之間的距離最大的平面；對于線性不可分的情況，可使用非線性核函數(shù)將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分。3.4.2 支持向量機基礎(chǔ)理論 支持向量機的理論有三個要點，即： （1）最大化間隔。 （2）核函數(shù)。 （3）對偶理論。31313131 1. 最大化間隔 在樣本線性可分的情況下，可行的分類超平面可能會有很多，如下圖中的L1、L2和L3。 從圖中可以直觀看出，L2比另外兩條分界線要更好，這是因為L2離樣本的距離更遠(yuǎn)一些，讓人覺得確信度更高。 SVM正是基于這種直觀思路來確定最佳分類超平面的：通過選取能夠最大化類間間隔的超平面，得到一個具有高確信度和泛化能力的分

24、類器，即最大間隔分類器。of56313.4 支持向量機第三章 分類3232323232 2. 核函數(shù) 核函數(shù)的定義： 設(shè)s是輸入空間（歐氏空間或離散集合），H為特征空間（希爾伯特空間），如果存在一個從s到H的映射 。 使得對所有的x，zs,函數(shù) ,則稱K(x,z),為核函數(shù)。 為映射函數(shù)， 為x，z映射到特征空間上的內(nèi)積。 常用的核函數(shù)主要有以下幾種： （1）線性核函數(shù)（Liner）。 （2）多項式核函數(shù)（Polynomial）。 （3）高斯（Gaussian）核函數(shù)(又稱徑向基函數(shù)，RBF)。 （4）指數(shù)型徑向基核函數(shù)。 （5）Sigmoid（或2層感知機）。 （6）傅立葉（Fourier）

25、核函數(shù)。of56323.4 支持向量機第三章 分類333333333333 3. 對偶理論（Duality Theory） 1947年由美籍匈牙利數(shù)學(xué)家馮諾依曼創(chuàng)立對偶理論。 對偶理論就是研究線性規(guī)劃中原始問題與對偶問題之間關(guān)系的理論。對偶問題有許多重要的特征，它的變量能提供關(guān)于原始問題最優(yōu)解的許多重要資料，有助于原始問題的求解和分析。對偶問題與原始問題之間存在著具體關(guān)系，見下表。of56333.4 支持向量機第三章 分類343434343434 原對偶優(yōu)化方法： 1）凸優(yōu)化問題 凸優(yōu)化問題是線性規(guī)劃中一種重要的特殊情形，它具有很好的性質(zhì)。如果凸規(guī)劃的目標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，又存在極小點，那么它

26、的極小點是唯一的，局部極小點就是全局極小點。 2）原對偶算法 原對偶算法作為一種解決復(fù)雜調(diào)度和整數(shù)規(guī)劃問題的有效方法，已經(jīng)被成功應(yīng)用于網(wǎng)絡(luò)調(diào)度問題。 應(yīng)用原對偶算法的前提條件是待求解優(yōu)化問題必須是嚴(yán)格的凸優(yōu)化問題。其核心思想是設(shè)計算法通過求解原優(yōu)化問題的對偶問題，來得到原問題的最優(yōu)解。of56343.4 支持向量機第三章 分類35353535353535 4. 幾種常用的損失函數(shù) 1）lp損失函數(shù) 2）-不靈敏損失函數(shù) 3）logistic損失函數(shù) 5. 結(jié)構(gòu)風(fēng)險最小化 結(jié)構(gòu)風(fēng)險最小化思想：首先，把函數(shù)集分解為一個函數(shù)子集序列，使各個子集能夠按照復(fù)雜性大小排列，也就是按照VC維大小排列，這樣在

27、同一個子集中置信范圍就相同；其次，在每個子集中尋找最小經(jīng)驗風(fēng)險，通常它隨著子集復(fù)雜度的增加而減少。最后，選擇最小經(jīng)驗風(fēng)險與置信范圍之和最小的子集，就可以達(dá)到期望風(fēng)險的最小，這個子集中使經(jīng)驗風(fēng)險最小的函數(shù)就是要求的最優(yōu)函數(shù)。 支持向量機是一種比較好的實現(xiàn)了結(jié)構(gòu)風(fēng)險最小化思想的方法。of56353.4 支持向量機第三章 分類363636363.4.3 支持向量機原理of56363.4 支持向量機第三章 分類 1. 支持向量機（SVM） 支持向量機（SVM）是一種分類算法，通過尋求結(jié)構(gòu)化風(fēng)險最小來提高學(xué)習(xí)機泛化能力，實現(xiàn)經(jīng)驗風(fēng)險和置信范圍的最小化，從而達(dá)到在統(tǒng)計樣本量較少的情況下，亦能獲得良好統(tǒng)計規(guī)

28、律的目的。SVM主要有以下3種情況： 1）線性可分情況。 右圖為線性可分情況。 圖中的圈和叉代表待分類的兩類樣本，H就是要求的最優(yōu)分類超平面，H1和H2是與最優(yōu)分類面平行的直線且分別通過這兩類樣本里距離H最近的樣本點。3737373737of56373.4 支持向量機第三章 分類 2）線性不可分情況 線性可分就是在樣本存在的空間中，可以找到可能正確劃分訓(xùn)練樣本的最優(yōu)分類超平面。但在現(xiàn)實中無法找到一個使得所有訓(xùn)練樣本關(guān)于分類超平面的間隔都是正值的分類超平面。必須適當(dāng)軟化條件。 對于那些需要軟化的條件，將它們分為兩類：一類是雖不滿足KKT條件但是可以被正確劃分的點；另外一類是不滿足KKT條件也不能

29、被正確劃分的點。 遇到線性不可分時，常用做法是把樣例特征映射到高維空間中去，如下圖所示。3838383838383838 線性不可分映射到高維空間，可能會導(dǎo)致維度大小高到可怕的程度，導(dǎo)致計算復(fù)雜。核函數(shù)的價值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)事先在低維上進(jìn)行計算，而將實質(zhì)上的分類效果表現(xiàn)在了高維上，也就避免了直接在高維空間中的復(fù)雜計算。 3）非線性可分情況 即便是引入了松弛變量，用直線劃分有些問題還是存在很大誤差，即輸入空間中不存在該問題的線性分類超平面，這種問題叫非線性可分問題。處理這類問題時，通過某種映射使得訓(xùn)練樣本線性可分，即將輸入空間映射到高維空間中后，通過訓(xùn)練支持向

30、量機得到該問題在高維空間中的最優(yōu)分類超平面，解決該類分類問題。 2支持向量機（SVM）的優(yōu)點 SVM學(xué)習(xí)問題可以表示為凸優(yōu)化問題，因此可以利用已知的有效算法發(fā)現(xiàn)目標(biāo)函數(shù)的全局最小值。而其他分類方法都采用一種基于貪心學(xué)習(xí)的策略來搜索假設(shè)空間，這種方法一般只能獲得局部最優(yōu)解。of56383.4 支持向量機第三章 分類393939393.5實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)第三章分類3.1基本概念3.2決策樹3.4支持向量機習(xí)題3.3貝葉斯分類of5639高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用4040 在Weka Explorer下方依次有6個不同標(biāo)簽顯示了Weka中六個不同的功能（不同的

31、軟件版本可能有著不同的標(biāo)簽），分別對應(yīng)著： （1）Preprocess（預(yù)處理）：在此項標(biāo)簽中通過“Open File”載入數(shù)據(jù)集，對數(shù)據(jù)集做預(yù)處理工作，同時也可使用Filter功能。 （2）Classify（分類）：對數(shù)據(jù)集進(jìn)行分類操作，并做出預(yù)測評估。 （3）Cluster（聚類）：學(xué)習(xí)數(shù)據(jù)集的聚類，并且測量對應(yīng)訓(xùn)練數(shù)據(jù)的聚類的對數(shù)似然，一般來說，對數(shù)似然越大就說明模型和數(shù)據(jù)擬合越好。 （4）Associate（關(guān)聯(lián)規(guī)則）：學(xué)習(xí)數(shù)據(jù)的關(guān)聯(lián)規(guī)則并對其進(jìn)行評估，此面板相對于Classify和Cluster來說更為簡單，只有3種算法來確定規(guī)則，但卻還沒有評估這些規(guī)則的手段。 （5）Select

32、attributes（選擇屬性）：通過此標(biāo)簽可以確定之前載入的數(shù)據(jù)集中相關(guān)的屬性。這里有幾種屬性選擇的方法可以通過此按鈕來實現(xiàn)，并且可以通過右鍵單擊歷史列表中的條目來將對應(yīng)的數(shù)據(jù)集可視化。 （6）Visualize（可視化）：查看不同的二維數(shù)據(jù)點圖并與其互動，并且?guī)椭脩艨梢暬粋€數(shù)據(jù)集，但它并不是指某個分類或聚類模型的結(jié)果，而指的是數(shù)據(jù)集的本身。3.5.1 Weka探索者圖形用戶界面of56403.5 實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)第三章 分類414141 通過Weka Explorer上的Classify面板，可以選擇學(xué)習(xí)算法，Weka中的分類器包括貝葉斯（Bayes）分類器、決策樹（

33、Trees）、規(guī)則（Rules）等。 weather nominal數(shù)據(jù)如下表所示。3.5.2 決策樹算法在Weka中的具體實現(xiàn)of56413.5 實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)第三章 分類42424242 從“Open file”讀取該訓(xùn)練集，在Attribute一欄中會顯示出該數(shù)據(jù)集的各個屬性，同時列出屬性的統(tǒng)計特性，并以直方圖的方式顯示出來。weather nominal訓(xùn)練集的五個屬性分別對應(yīng)表中的屬性，并以直方圖統(tǒng)計的方式顯示。 通過處理后的決策樹規(guī)則為：= Classifier model (full training set) = J48 pruned tree-outloo

34、k = sunny| humidity = high: no (3.0)| humidity = normal: yes (2.0)outlook = overcast: yes (4.0)outlook = rainy| windy = TRUE: no (2.0)| windy = FALSE: yes (3.0)Number of Leaves: 5Size of the tree: 8 從以上文本信息可以得出：若outlook = sunny且humidity = high，則play的分類結(jié)果就是no，結(jié)果數(shù)為3個；若outlook = sunny且humidity = normal

35、，那么play就為yes，結(jié)果數(shù)為2個。另外由最后兩行可以看出該樹共有節(jié)點8個，其中葉子節(jié)點為5個。of56423.5 實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)第三章 分類4343434343根據(jù)weather nominal訓(xùn)練集J48（C4.5）算法生成的決策樹如下圖所示。of56433.5 實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)第三章 分類3.5.3 使用中的具體實例 以某高校計算機科學(xué)與技術(shù)專業(yè)的C語言程序設(shè)計課程成績?yōu)槔唧w數(shù)據(jù)見下表，有上機時間、課本知識掌握程度、上課學(xué)習(xí)情況以及平時成績等因素。4444444444學(xué)生成績綜合判定數(shù)據(jù)集如下： 表中共含有167條記錄，其中包含111個正例和56個反例，用J48（C4.5）算法對該數(shù)據(jù)進(jìn)行分類處理并在Weka中實現(xiàn)。of56443.5 實戰(zhàn)：決策樹算法在Weka中的實現(xiàn)第三章 分類454545454545 通過處理后的決策樹規(guī)則為：= Classifier model (full training set) = J48 pruned tree-score = good | study = a:yes| study = b:yes | study = c |