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

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

2、醫(yī)療診斷、人臉檢測(cè)、故障診斷和故障預(yù)警 第三章分類3 of 56高級(jí)大數(shù)據(jù)人才培養(yǎng)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用3 . 13 . 23 . 3基本概念決策樹(shù)貝葉斯分類3.4 支持向量機(jī)3 . 5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題第三章分類4 of 563.1基本概念第三章 分類3.1.1 分類的基本概念分類（Classification）是一種重要的數(shù)據(jù)分析形式，它提取刻畫(huà)重要數(shù)據(jù)類的模型。這種模型稱為分類器，預(yù)測(cè)分類的（離散的、無(wú)序的）類標(biāo)號(hào)。這些類別可以用離散值表示，其中值之間的次序沒(méi)有意義。分類也可定義為：分類的任務(wù)就是通過(guò)學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)(Target Function) ，把每

3、個(gè)屬性集x映射到一個(gè)預(yù)先定義的類標(biāo)號(hào)y 。5 of 563.1基本概念第三章 分類3.1.2 分類的過(guò)程數(shù)據(jù)分類過(guò)程有兩階段：（1） 學(xué)習(xí)階段（構(gòu)建分類模型）。（2） 分類階段（使用模型預(yù)測(cè)給定數(shù)據(jù)的類標(biāo)號(hào)）。訓(xùn)練集歸納模型測(cè)試集推論建立分類模型的一般方法Tid屬性1屬性2屬性3類1112131415No Yes Yes No NoSmall Medium Large Small Large55K80K110K95K67K？應(yīng)用模型學(xué)習(xí)模型學(xué)習(xí)算法Tid屬性1屬性2屬性3類12345678910Yes No No Yes No No Yes No No NoLarge Medium Small

4、 Medium Large Medium Large Small Medium Small125K100K70K120K95K60K220K85K75K90KNo No No No Yes No No Yes No Yes6 of 563.1基本概念第三章 分類3.1.3 分類器性能的評(píng)估方法分類器的性能和所選擇的訓(xùn)練集和測(cè)試集有著直接關(guān)系。一般情況下，先用一部分?jǐn)?shù)據(jù)建立模型，然后再用剩下的數(shù)據(jù)來(lái)測(cè)試和驗(yàn)證這個(gè)得到的模型。如果使用相同的訓(xùn)練集和測(cè)試集，那么模型的準(zhǔn)確度就很難使人信服。保持法和交叉驗(yàn)證是兩種基于給定數(shù)據(jù)隨機(jī)選樣劃分的，是常用的評(píng)估分類方法準(zhǔn)確率的技術(shù)。7 of 567高級(jí)大數(shù)據(jù)人

5、才培養(yǎng)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用3 . 13.2 3 . 3基本概念決策樹(shù)貝葉斯分類3 . 4支持向量機(jī)3 . 5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題第三章分類8 of 5683.2決策樹(shù)第三章 分類決策樹(shù)是數(shù)據(jù)挖掘的有力工具之一，決策樹(shù)學(xué)習(xí)算法是從一組樣本數(shù)據(jù)集（一個(gè)樣本數(shù)據(jù)也可以稱為實(shí)例）為基礎(chǔ)的一種歸納學(xué)習(xí)算法，它著眼于從一組無(wú)次序、無(wú)規(guī)則的樣本數(shù)據(jù)（概念）中推理出決策樹(shù)表示形式的分類規(guī)則。3.2.1 決策樹(shù)概述決策樹(shù)（Decision Tree）是一種類似于流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)（非樹(shù)葉節(jié)點(diǎn)）表示在屬性上的測(cè)試，每個(gè)分支表示該測(cè)試上的一個(gè)輸出，而每個(gè)樹(shù)葉節(jié)點(diǎn)存放一個(gè)類標(biāo)號(hào)

6、，樹(shù)的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。決策樹(shù)生成方式一般情況下都是由上而下的。每次不同的或決策都有可能引發(fā)至少兩個(gè)以上的，形成不同的結(jié)果，這種決策方法用圖形表示出來(lái)很像一棵樹(shù)，所以稱之為決策樹(shù)。決策樹(shù)是一種簡(jiǎn)單且廣泛使用的分類器。通過(guò)訓(xùn)練數(shù)據(jù)來(lái)構(gòu)建決策樹(shù)，可高效地對(duì)未知的數(shù)據(jù)進(jìn)行分類。9 of 5693.2決策樹(shù)第三章 分類3.2.2 決策樹(shù)的用途和特性基于決策樹(shù)的決策算法是屬于實(shí)用性很好的總結(jié)預(yù)測(cè)算法之一，是一個(gè)趨近于非連續(xù)型函數(shù)值的算法。決策樹(shù)在各行各業(yè)有著非常多的廣泛應(yīng)用，如在醫(yī)院的臨床決策、人臉檢測(cè)、故障診斷、故障預(yù)警、醫(yī)療數(shù)據(jù)挖掘、案例分析、分類預(yù)測(cè)的軟件系統(tǒng)等方面都有很大的用處。決策樹(shù)的最佳用

7、途是圖解說(shuō)明如何領(lǐng)會(huì)決策與相關(guān)的相互作用。10 of 56103.2決策樹(shù)第三章 分類3.2.3 決策樹(shù)工作原理決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。它提供一種在什么條件下會(huì)得到什么值的類似規(guī)則的方法。決策樹(shù)分為分類樹(shù)和回歸樹(shù)兩種，分類樹(shù)對(duì)離散變量做決策樹(shù)，回歸樹(shù)對(duì)連續(xù)變量做決策樹(shù)。直觀看，決策樹(shù)分類器就像判斷模塊和終止塊組成的流程圖，終止塊表示分類結(jié)果（也就是樹(shù)的葉子）。判斷模塊表示對(duì)一個(gè)特征取值的判斷（該特征有幾個(gè)值，判斷模塊就有幾個(gè)分支）。45買是不是優(yōu)秀一般不買買不買買買電腦的決策樹(shù)信用評(píng)級(jí)?學(xué)生 ?年齡 ?30.4511 of 5611113.2決策樹(shù)第三章 分類上圖表示了一個(gè)

8、關(guān)心電子產(chǎn)品的用戶是否會(huì)購(gòu)買電腦，用它可以預(yù)測(cè)某條記錄（某個(gè)人）的購(gòu)買意向。樹(shù)中包含了三種節(jié)點(diǎn)：根節(jié)點(diǎn)（root rode），它沒(méi)有入邊，但有兩條或多條出邊。子節(jié)點(diǎn)（child node），恰有一條入邊和兩條或多條出邊。葉節(jié)點(diǎn)（leaf node ）或終節(jié)點(diǎn)（terminal node），恰有一條入邊，但沒(méi)有出邊。在決策樹(shù)中，每個(gè)葉節(jié)點(diǎn)都賦予一個(gè)類標(biāo)號(hào)。非終節(jié)點(diǎn)（包括根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)） 包含屬性測(cè)試條件，用以分開(kāi)具有不同特性的記錄。這棵決策樹(shù)對(duì)銷售記錄進(jìn)行分類， 指出一個(gè)電子產(chǎn)品消費(fèi)者是否會(huì)購(gòu)買一臺(tái)計(jì)算機(jī)。每個(gè)內(nèi)部節(jié)點(diǎn)（方形框）代表對(duì)某個(gè)屬性的一次檢測(cè)。每個(gè)葉節(jié)點(diǎn)（橢圓框）代表一個(gè)類。12 o

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

10、類樹(shù)的主體建好后，接下來(lái)便是對(duì)其剪枝。決策樹(shù)的剪枝一般通過(guò)極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(shù)來(lái)實(shí)現(xiàn)。決策樹(shù)剪枝常用的方法有兩種：預(yù)剪枝和后剪枝。預(yù)剪枝是根據(jù)一些原則盡早停止樹(shù)的增長(zhǎng)，如樹(shù)的深度達(dá)到用戶所要的深度、節(jié)點(diǎn)中樣本個(gè)數(shù)少于用戶指定個(gè)數(shù)等。預(yù)剪枝在建立樹(shù)的過(guò)程中決定是否需要繼續(xù)劃分或分裂訓(xùn)練樣本來(lái)實(shí)現(xiàn)提前停止樹(shù)的構(gòu)造，一旦決定停止分枝，就將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)。后剪枝是通過(guò)在完全生長(zhǎng)的樹(shù)上剪去分枝實(shí)現(xiàn)的，通過(guò)刪除節(jié)點(diǎn)的分支來(lái)剪去樹(shù)節(jié)點(diǎn)。14 of 561414143.2決策樹(shù)第三章 分類3.2.5 決策樹(shù)算法原理1. 認(rèn)識(shí)決策樹(shù)1）決策樹(shù)的生成過(guò)程一棵決策樹(shù)的生成過(guò)程主要分為以下3個(gè)部

11、分：（1） 特征選擇：特征選擇是指從訓(xùn)練數(shù)據(jù)眾多的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn) 的分裂標(biāo)準(zhǔn)，如何選擇特征有著很多不同量化評(píng)估標(biāo)準(zhǔn)，從而衍生出不同的決策樹(shù)算法。（2） 決策樹(shù)生成：根據(jù)選擇的特征評(píng)估標(biāo)準(zhǔn)，從上至下遞歸地生成子節(jié)點(diǎn)，直到數(shù)據(jù)集不可分則決策樹(shù)停止生長(zhǎng)。（3） 剪枝：決策樹(shù)容易過(guò)擬合，一般都需要剪枝，縮小樹(shù)結(jié)構(gòu)規(guī)模、緩解過(guò)擬合。15 of 56151515153.2決策樹(shù)第三章 分類基于信息論的決策樹(shù)算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來(lái)。CART和C4.5支持?jǐn)?shù)據(jù)特征為連續(xù)分布時(shí)的處理，主要通過(guò)使用二元切分來(lái)處理連續(xù)型變量，即求

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

13、2決策樹(shù)第三章 分類2. ID3算法1）ID3算法的信息論基礎(chǔ)（1）信息熵信息熵：在概率論中，信息熵給了一種度量不確定性的方式，是用來(lái)衡量隨確定性的，熵就是信息的期望值。若待分類的事物可能劃分在N類中，分別是x1，x2，,xn，每一種取到的概率分別是p1，p2，,pn，那么X的熵就定義為：H ( X ) = -pi log pii =1從定義中可知：0 H ( X ) log(n)量不nP ( X = 1) = p, P ( X = 0) = 1 - p, 0 p 1當(dāng)隨量只取兩個(gè)值時(shí)，即X的分布則熵為：H ( X ) = - p log2 ( p) - (1 - p)log2 (1 - p)

14、17 of 561717171717173.2決策樹(shù)第三章 分類（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的條件概率分布的熵對(duì)X的數(shù)學(xué)期望：nH (Y | X ) = pi H (Y | X = xi )i=1若是樣本的特征只有兩個(gè)值(X1=0，X2=1),對(duì)應(yīng)(出現(xiàn)，不出現(xiàn))，如文本分類中某一個(gè)單詞的出現(xiàn)與否。那么對(duì)于特征二值的情況，用T代表特征，用t代表T出現(xiàn)，t 表示該特征不出現(xiàn)。那么：H (C|T ) = P (t ) H (

15、C|t ) + P (t )H (C|t )與前面的公式對(duì)比一下，P(t)就是T出現(xiàn)的概率，P( t)就是T不出現(xiàn)的概率，結(jié)合信息熵的計(jì)算公式，可得：H (C|t ) = -P (Ci|t )log2 P (Ci|t )i=1nH C|t=-P (C |t )logP (C |t )()ni2ii=118 of 5618181818183.2決策樹(shù)第三章 分類（3）信息增益信息增益（Information Gain）表示得知特征X的信息后，而使得Y的不確定性減少的程度。定義為：g (D, A) = H (D) - H (D | A)信息增益是針對(duì)一個(gè)一個(gè)的特征而言的，就是看一個(gè)特征X，系統(tǒng)有它

16、和沒(méi)它的時(shí)候信息量各是多少，兩者的差值就是這個(gè)特征給系統(tǒng)帶來(lái)的信息增益。對(duì)于特征取值為二值的情況，特征T給系統(tǒng)帶來(lái)的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差：g (C,T ) = H (C ) - H (C|T )= -P (C )logP (C ) + P (t )P (C |t )logP (C |t ) + P (t )P (C |t )log P (C |t )nnni2ii2ii2ii=1i=1i=119 of 561919191919193.2決策樹(shù)第三章 分類3. C4.5算法C4.5算法同樣以“信息熵”作為核心，是ID3基礎(chǔ)上的優(yōu)化改進(jìn)，同時(shí)，也保持了分類準(zhǔn)確率

17、高、速度快的特點(diǎn)。1）基本思想信息增益C4.5算法挑選具有最高信息增益率的屬性為測(cè)試屬性。對(duì)樣本集T，假設(shè)變量a有k個(gè)屬性，屬性取值a1，a2，,an，對(duì)應(yīng)a取值為ai的樣本個(gè)數(shù)分別為ni，若n是樣本的總數(shù)，則應(yīng)有n1+n2+nk=n, Quinlan利用屬性a的熵值H(X,a),來(lái)定義為了獲取樣本關(guān)于屬性a的信息所需要付出的代價(jià)，即： g ( X，a)E ( X，a) =H ( X，a)信息增益率定義為平均互信息與獲取a信息所付出代價(jià)的比值，即：kkni nni nHX，a) = -P (ai )log2 P a -()i=1logi2i=120 of 56202020202020203.2

18、決策樹(shù)第三章 分類4. CART 算法CART算法生成的是一棵二叉樹(shù)。它采用的是一種二分遞歸分割技術(shù)，每次都將當(dāng)前的數(shù)據(jù)集分為兩個(gè)互不相交子集，使得所有非葉子節(jié)點(diǎn)都只有兩個(gè)分支。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個(gè)樣本的數(shù)據(jù)集，所有樣本總共包含m個(gè)不同的類別Ci，i1,2,m ， 那么Gini指標(biāo)為：mGini(S ) = 1 -2Pi i =1其中Pi為樣本屬性類別Ci的概率。21 of 562121212121212121

19、3.2決策樹(shù)第三章 分類根據(jù)CART算法構(gòu)造的是一棵二叉樹(shù)，所以在CART算法中是用Gini指標(biāo)進(jìn)行二元?jiǎng)澐?，?duì)于數(shù)據(jù)集S的任何一個(gè)屬性A的任何一種取值a，可以將數(shù)據(jù)集S劃分成S1和S2兩個(gè)子集，對(duì)應(yīng)屬性A，Gini指標(biāo)的計(jì)算公式如下：S1 SGiniA(S ) =Gini(S ) +Gini(S)12S其中|S|表示數(shù)據(jù)集S的個(gè)數(shù)。當(dāng)GiniA(S)最小時(shí)，屬性A就為數(shù)據(jù)集S的最佳分裂屬性，S1和S2就是按屬性A的取值a對(duì)數(shù)據(jù)集S的劃分。2）CART算法建樹(shù)過(guò)程CART算法建樹(shù)過(guò)程見(jiàn)數(shù)據(jù)挖掘一書(shū)的第46頁(yè)。S222 of 562222高級(jí)大數(shù)據(jù)人才培養(yǎng)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用3 . 13

20、. 23 . 3基本概念決策樹(shù)貝葉斯分類3 . 4支持向量機(jī)3 . 5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題第三章分類23 of 5623233.3貝葉斯分類第三章 分類貝葉斯分類是一類分類算法的總稱，這類算法均以貝葉斯定理（Bayes theorem） 為基礎(chǔ)，采用了概率推理方法。3.3.1 貝葉斯定理P ( AB) P (B)P ( A|B) =貝葉斯定理之所以有用，是因?yàn)樵谏钪薪?jīng)常遇到這種情況：可以很容易直接得出P(A|B),P(B|A)則很難直接得出，但人們往往更關(guān)心P(B|A),貝葉斯定理打通了從P(A|B)獲得P(B|A)的道路。貝葉斯定理：P ( A|B) P (B) P (

21、 A)P (B|A) =24 of 562424243.3貝葉斯分類第三章 分類3.3.2 樸素貝葉斯分類原理與流程樸素貝葉斯分類是貝葉斯分類的一種，樸素貝葉斯分類與貝葉斯分類相比，后者需要花很大的時(shí)間和空間復(fù)雜度去計(jì)算類條件概率。1. 樸素貝葉斯分類原理樸素貝葉斯的思想基礎(chǔ)是這樣的：對(duì)于給出的待分類項(xiàng)，求解在此項(xiàng)出現(xiàn)的條件下各個(gè)類別出現(xiàn)的概率，哪個(gè)最大，就認(rèn)為此待分類項(xiàng)屬于哪個(gè)類別。樸素貝葉斯分類的正式定義如下：（1） 設(shè)x=a1,a2,am,為一個(gè)待分類項(xiàng)，而每個(gè)a為x的一個(gè)特征屬性。（2） 有類別集合C=y1,y2,yn。（3）計(jì)算P(y1|x),P(y2|x),P(yn|x)。（4）如

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

23、類項(xiàng)進(jìn)行分類，其輸入是分類器和待分類項(xiàng)，輸出是待分類項(xiàng)與類別的映射關(guān)系。26 of 5626262626263.3貝葉斯分類第三章 分類樸素貝葉斯分類的流程圖如下圖。準(zhǔn)備工作階段確定特征屬性獲取訓(xùn)練樣本分類器訓(xùn)練階段應(yīng)用階段以P(x|yi)P(yi)最大項(xiàng)作為x所屬類別對(duì)每個(gè)類別計(jì)算P(x|yi)P(yi)對(duì)每個(gè)類別計(jì)算P(yi)對(duì)每個(gè)特征屬性計(jì)算所有劃分的條件概率27 of 5627272727273.3貝葉斯分類第三章 分類3.3.3貝葉斯分析貝葉斯分析中的三要素（即貝葉斯統(tǒng)計(jì)三要素，一要素是先驗(yàn)概率P(A),二要素是條件概率P(A|B),最終得到三要素即后驗(yàn)概率P(B|A)。理解貝葉斯分

24、析最好的方法即圖像法，如圖所示。A為紅圈，B為藍(lán)圈，AB為紫圈。這里的A（紅圈的面積即先驗(yàn)，后驗(yàn)是陰影占藍(lán)圈（B）的百分比。28 of 562828282828283.3貝葉斯分類第三章 分類3.3.4 貝葉斯決策貝葉斯決策主要包含四個(gè)部分：數(shù)據(jù)（D）、假設(shè)（W）、目標(biāo)（O）和決策（S）。貝葉斯決策步驟：1. 理清因果鏈條，確定哪個(gè)是假設(shè)，哪個(gè)是證據(jù)。2. 給出所有可能假設(shè)，即假設(shè)空。3. 假設(shè)，即假設(shè)空間。4. 根據(jù)貝葉斯概率公式求解后驗(yàn)概率，得到假設(shè)空間的后驗(yàn)概率分布。5. 利用后驗(yàn)概率求解條件期望，得到條件期望最大值對(duì)應(yīng)的行為。貝葉斯決策如果一旦變成自動(dòng)化的計(jì)算機(jī)算法，它就是機(jī)器學(xué)習(xí)。用

25、貝葉斯決策詮釋一個(gè)最簡(jiǎn)單的機(jī)器學(xué)習(xí)分類算法，那就是樸素貝葉斯。29 of 56292929高級(jí)大數(shù)據(jù)人才培養(yǎng)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用3 . 13 . 2基本概念決策樹(shù)3 . 3貝葉斯分類3 . 43 . 5支持向量機(jī)實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題第三章分類30 of 563030303.4支持向量機(jī)第三章 分類支持向量機(jī)（SVM）是根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論中的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則提出的一種經(jīng)典的機(jī)器學(xué)習(xí)方法，現(xiàn)已發(fā)展為機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)重要分支。3.4.1 支持向量機(jī)主要思想SVM主要思想是針對(duì)兩類分類問(wèn)題的，尋找一個(gè)超平面作為兩類訓(xùn)練樣本點(diǎn)的分割， 以保證最小的分類錯(cuò)誤率。在線性可分的情況

26、下，存在一個(gè)或多個(gè)超平面使得訓(xùn)練樣本完全分開(kāi)，SVM的目標(biāo)是找到其中的最優(yōu)超平面，最優(yōu)超平面是使得每一類數(shù)據(jù)與超 平面距離最近的向量與超平面之間的距離最大的平面；對(duì)于線性不可分的情況，可使用非線性核函數(shù)將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分。3.4.2 支持向量機(jī)基礎(chǔ)理論支持向量機(jī)的理論有三個(gè)要點(diǎn)，即：（1） 最大化間隔。（2） 核函數(shù)。（3） 對(duì)偶理論。31 of 56313131313.4支持向量機(jī)第三章 分類1. 最大化間隔在樣本線性可分的情況下，可行的分類超平面可能會(huì)有很多，如下圖中的L1、L2和L3。從圖中可以直觀看出，L2比另外兩條分界線要更好，這是因?yàn)長(zhǎng)2離

27、樣本的 距離更遠(yuǎn)一些，讓人覺(jué)得確信度更高。SVM正是基于這種直觀思路來(lái)確定最佳分類超平面的：通過(guò)選取能夠最大化類間間隔的超平面，得到一個(gè)具有高確信度和泛化能力的分類器，即最大間隔分類器。32 of 5632323232323.4支持向量機(jī)第三章 分類2. 核函數(shù)核函數(shù)的定義：設(shè)s是輸入空間（歐氏空間或離散集合），H為特征空間（希爾伯特空間），如果存在一個(gè)從s到H的映射 j (x) : s H。使得對(duì)所有的x，zs,函數(shù) ( x, z ) = ( x) ( z ),則稱K(x,z),為核函數(shù)。 ( x) 為映射函數(shù)，( x) ( z )為x，z映射到特征空間上的內(nèi)積。常用的核函數(shù)主要有以下幾種：

28、（1） 線性核函數(shù)（Liner）。（2） 多項(xiàng)式核函數(shù)（Polynomial）。（3） 高斯（Gaussian）核函數(shù)(又稱徑向基函數(shù)，RBF)。（4） 指數(shù)型徑向基核函數(shù)。（5） Sigmoid（或2層感知機(jī)）。（6） 傅立葉（Fourier）核函數(shù)。33 of 563333333333333.4支持向量機(jī)第三章 分類3. 對(duì)偶理論（Duality Theory）1947年由美籍匈牙利數(shù)學(xué)家馮諾依曼創(chuàng)立對(duì)偶理論。對(duì)偶理論就是研究線性規(guī)劃中原始問(wèn)題與對(duì)偶問(wèn)題之間關(guān)系的理論。對(duì)偶問(wèn)題有許多重要的特征，它的變量能提供關(guān)于原始問(wèn)題最優(yōu)解的許多重要資料，有助于原始問(wèn)題的求解和分析。對(duì)偶問(wèn)題與原始問(wèn)題之

29、間存在著具體關(guān)系，見(jiàn)下表。34 of 563434343434343.4支持向量機(jī)第三章 分類原對(duì)偶優(yōu)化方法：1） 凸優(yōu)化問(wèn)題凸優(yōu)化問(wèn)題是線性規(guī)劃中一種重要的特殊情形，它具有很好的性質(zhì)。如果凸規(guī)劃的目標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，又存在極小點(diǎn)，那么它的極小點(diǎn)是唯一的，局部極小點(diǎn)就是全局極小點(diǎn)。2） 原對(duì)偶算法原對(duì)偶算法作為一種解決復(fù)雜調(diào)度和整數(shù)規(guī)劃問(wèn)題的有效方法，已經(jīng)被成功應(yīng)用于網(wǎng)絡(luò)調(diào)度問(wèn)題。應(yīng)用原對(duì)偶算法的前提條件是待求解優(yōu)化問(wèn)題必須是嚴(yán)格的凸優(yōu)化問(wèn)題。其核心思想是設(shè)計(jì)算法通過(guò)求解原優(yōu)化問(wèn)題的對(duì)偶問(wèn)題，來(lái)得到原問(wèn)題的最優(yōu)解。35 of 56353535353535353.4支持向量機(jī)第三章 分類4.

30、幾種常用的損失函數(shù)1） lp損失函數(shù)2） -不靈敏損失函數(shù)3）logistic損失函數(shù)5. 結(jié)構(gòu)風(fēng)險(xiǎn)最小化結(jié)構(gòu)風(fēng)險(xiǎn)最小化思想：首先，把函數(shù)集分解為一個(gè)函數(shù)子集序列，使各個(gè)子集能夠按照復(fù)雜性大小排列，也就是按照VC維大小排列，這樣在同一個(gè)子集中置信范圍就相同；其次，在每個(gè)子集中尋找最小經(jīng)驗(yàn)風(fēng)險(xiǎn)，通常它隨著子集復(fù)雜度的增加而減少。最后，選擇最小經(jīng)驗(yàn)風(fēng)險(xiǎn)與置信范圍之和最小的子集，就可以達(dá)到期望風(fēng)險(xiǎn)的最小，這個(gè)子集中使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的函數(shù)就是要求的最優(yōu)函數(shù)。支持向量機(jī)是一種比較好的實(shí)現(xiàn)了結(jié)構(gòu)風(fēng)險(xiǎn)最小化思想的方法。36 of 56363636363.4支持向量機(jī)第三章 分類3.4.3 支持向量機(jī)原理1.

31、支持向量機(jī)（SVM）支持向量機(jī)（SVM）是一種分類算法，通過(guò)尋求結(jié)構(gòu)化風(fēng)險(xiǎn)最小來(lái)提高學(xué)習(xí)機(jī)泛化能力，實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍的最小化，從而達(dá)到在統(tǒng)計(jì)樣本量較少的情況下，亦能獲得良好統(tǒng)計(jì)規(guī)律的目的。SVM主要有以下3種情況： 1）線性可分情況。右圖為線性可分情況。圖中的圈和叉代表待分類的兩類樣本，H就是要求的最優(yōu)分類超平面， H1和H2是與最優(yōu)分類面平行的直線且分別通過(guò)這兩類樣本里距離H最近的樣本點(diǎn)。37 of 5637373737373.4支持向量機(jī)第三章 分類2）線性不可分情況線性可分就是在樣本存在的空間中，可以找到可能正確劃分訓(xùn)練樣本的最優(yōu)分類超平面。但在現(xiàn)實(shí)中無(wú)法找到一個(gè)使得所有訓(xùn)練樣本關(guān)

32、于分類超平面的間隔都是正值的分類超平面。必須適當(dāng)軟化條件。對(duì)于那些需要軟化的條件，將它們分為兩類：一類是雖不滿足KKT條件但是可以被正確劃分的點(diǎn)；另外一類是不滿足KKT條件也不能被正確劃分的點(diǎn)。遇到線性不可分時(shí)，常用做法是把樣例特征映射到高維空間中去，如下圖所示。特征地圖分離超平面復(fù)雜的低維度簡(jiǎn)單的高維度在更高維上分離可能更容易38 of 5638383838383838383.4支持向量機(jī)第三章 分類線性不可分映射到高維空間，可能會(huì)導(dǎo)致維度大小高到可怕的程度，導(dǎo)致計(jì)算復(fù)雜。核函數(shù)的價(jià)值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)事先在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類效果表現(xiàn)在了高維上

33、，也就避免了直接在高維空間中的復(fù)雜計(jì)算。3）非線性可分情況即便是引入了松弛變量，用直線劃分有些問(wèn)題還是存在很大誤差，即輸入空間中不存在該問(wèn)題的線性分類超平面，這種問(wèn)題叫非線性可分問(wèn)題。處理這類問(wèn)題時(shí)，通過(guò)某種映射使得訓(xùn)練樣本線性可分，即將輸入空間映射到高維空間中后，通過(guò)訓(xùn)練支持向量機(jī)得到該問(wèn)題在高維空間中的最優(yōu)分類超平面，解決該類分類問(wèn)題。2支持向量機(jī)（SVM）的優(yōu)點(diǎn)SVM學(xué)習(xí)問(wèn)題可以表示為凸優(yōu)化問(wèn)題，因此可以利用已知的有效算法發(fā)現(xiàn)目標(biāo)函數(shù)的全局最小值。而其他分類方法都采用一種基于貪心學(xué)習(xí)的策略來(lái)搜索假設(shè)空間，這種方法一般只能獲得局部最優(yōu)解。39 of 5639393939高級(jí)大數(shù)據(jù)人才培養(yǎng)之

34、一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用3 . 13 . 2基本概念決策樹(shù)3 . 3貝葉斯分類3 . 43 . 5支持向量機(jī)實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題第三章分類40 of 5640403.5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)第三章 分類3.5.1 Weka探索者圖形用戶界面在Weka Explorer下方依次有6個(gè)不同標(biāo)簽顯示了Weka中六個(gè)不同的功能（不同的軟件版本可能有著不同的標(biāo)簽），分別對(duì)應(yīng)著：（1） Preprocess（預(yù)處理）：在此項(xiàng)標(biāo)簽中通過(guò)“Open File”載入數(shù)據(jù)集，對(duì)數(shù)據(jù)集做預(yù)處理工作，同時(shí)也可使用Filter功能。（2） Classify（分類）：對(duì)數(shù)據(jù)集進(jìn)行分類操作

35、，并做出預(yù)測(cè)評(píng)估。（3） Cluster（聚類）：學(xué)習(xí)數(shù)據(jù)集的聚類，并且測(cè)量對(duì)應(yīng)訓(xùn)練數(shù)據(jù)的聚類的對(duì)數(shù)似然，一般來(lái)說(shuō)，對(duì)數(shù)似然越大就說(shuō)明模型和數(shù)據(jù)擬合越好。（4） Associate（關(guān)聯(lián)規(guī)則）：學(xué)習(xí)數(shù)據(jù)的關(guān)聯(lián)規(guī)則并對(duì)其進(jìn)行評(píng)估，此面板相對(duì)于Classify和Cluster來(lái)說(shuō)更為簡(jiǎn)單，只有3種算法來(lái)確定規(guī)則，但卻還沒(méi)有評(píng)估這些規(guī)則的手段。（5） Select attributes（選擇屬性）：通過(guò)此標(biāo)簽可以確定之前載入的數(shù)據(jù)集中相關(guān)的屬性。這里有幾種屬性選擇的方法可以通過(guò)此按鈕來(lái)實(shí)現(xiàn)，并且可以通過(guò)右鍵單擊歷史列表中的條目來(lái)將對(duì)應(yīng)的數(shù)據(jù)集可視化。（6） Visualize（可視化）：查看不同的二

36、維數(shù)據(jù)點(diǎn)圖并與其互動(dòng)，并且?guī)椭脩艨梢暬粋€(gè)數(shù)據(jù)集，但它并不是指某個(gè)分類或聚類模型的結(jié)果，而指的是數(shù)據(jù)集的本身。41 of 564141413.5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)第三章 分類3.5.2 決策樹(shù)算法在Weka中的具體實(shí)現(xiàn)通過(guò)Weka Explorer上的Classify面板，可以選擇學(xué)習(xí)算法，Weka中的分類器包括貝葉斯（Bayes）分類器、決策樹(shù)（Trees）、規(guī)則（Rules）等。 weather nominal 數(shù)據(jù)如下表所示。42 of 56424242423.5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)第三章 分類從“Open file”讀取該訓(xùn)練集，在Attribute

37、一欄中會(huì)顯示出該數(shù)據(jù)集的各個(gè)屬性， 同時(shí)列出屬性的統(tǒng)計(jì)特性，并以直方圖的方式顯示出來(lái)。weather nominal訓(xùn)練集的五個(gè)屬性分別對(duì)應(yīng)表中的屬性，并以直方圖統(tǒng)計(jì)的方式顯示。通過(guò)處理后的決策樹(shù)規(guī)則為：= Classifier model (full training set) = J48 pruned treeoutlook = sunny|humidity = high: no (3.0)|humidity = normal: yes (2.0)outlook = overcast: yes (4.0) outlook = rainy|windy = TRUE: no (2.0)|win

38、dy = FALSE: yes (3.0) Number of Leaves: 5Size of the tree: 8從以上文本信息可以得出：若outlook = sunny且humidity = high，則play的分類結(jié)果就是no，結(jié)果數(shù)為3個(gè)；若outlook = sunny且humidity = normal，那么play就為yes，結(jié)果數(shù)為2個(gè)。另外由最后兩行可以看出該樹(shù)共有節(jié)點(diǎn)8個(gè)，其中葉子節(jié)點(diǎn)為5 個(gè)。43 of 5643434343433.5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)第三章 分類根據(jù)weather nominal訓(xùn)練集J48（C4.5）算法生成的決策樹(shù)如下圖所示。

39、3.5.3 使用中的具體實(shí)例以某高校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的C語(yǔ)言程序設(shè)計(jì)課程成績(jī)?yōu)槔?，具體數(shù)據(jù)見(jiàn)下表，有上機(jī)時(shí)間、課本知識(shí)掌握程度、上課學(xué)習(xí)情況以及平時(shí)成績(jī)等因素。44 of 5644444444443.5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)第三章 分類學(xué)生成績(jī)綜合判定數(shù)據(jù)集如下：表含有167條記錄，其中包含111個(gè)正例和56個(gè)反例，用J48（C4.5）算法對(duì)該數(shù)據(jù)進(jìn)行分類處理并在Weka中實(shí)現(xiàn)。45 of 564545454545453.5實(shí)戰(zhàn)： 決策樹(shù)算法在Weka中的實(shí)現(xiàn)第三章 分類通過(guò)處理后的決策樹(shù)規(guī)則為：= Classifier model (full training set) = J48 pruned treescore = good|study = a:yes|study = b:yes study = c