數(shù)據(jù)挖掘（第2版） 課件 第3章 分類(lèi)

高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用數(shù)據(jù)挖掘（第二版）第三章分類(lèi)of562高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用

分類(lèi)是一種很重要的數(shù)據(jù)挖掘技術(shù)，也是數(shù)據(jù)挖掘研究的重點(diǎn)和熱點(diǎn)之一。分類(lèi)的目的是分析輸入數(shù)據(jù)，通過(guò)訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來(lái)的特性，為每一個(gè)類(lèi)找到一種準(zhǔn)確描述或者模型，這種描述常常用謂詞來(lái)表示。由此生成的類(lèi)描述用來(lái)對(duì)未來(lái)的測(cè)試數(shù)據(jù)進(jìn)行分類(lèi)。盡管這些未來(lái)測(cè)試數(shù)據(jù)的類(lèi)標(biāo)簽是未知的，仍可以由此預(yù)測(cè)這些新數(shù)據(jù)所屬的類(lèi)。也可以由此對(duì)數(shù)據(jù)中每一個(gè)類(lèi)有更好的理解。More應(yīng)用市場(chǎng)：醫(yī)療診斷、人臉檢測(cè)、故障診斷和故障預(yù)警······3.1分類(lèi)概述第三章分類(lèi)3.2

決策樹(shù)3.3

貝葉斯分類(lèi)3.5實(shí)戰(zhàn)：Python支持向量機(jī)分類(lèi)習(xí)題3.4

支持向量機(jī)of563高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用

分類(lèi)（Classification）是一種重要的數(shù)據(jù)分析形式，它提取刻畫(huà)重要數(shù)據(jù)類(lèi)的模型。這種模型稱(chēng)為分類(lèi)器，預(yù)測(cè)分類(lèi)的（離散的、無(wú)序的）類(lèi)標(biāo)號(hào)。這些類(lèi)別可以用離散值表示，其中值之間的次序沒(méi)有意義。3.1.1分類(lèi)的基本概念of5643.1分類(lèi)概述第三章分類(lèi)

分類(lèi)可描述如下：從訓(xùn)練數(shù)據(jù)中確定函數(shù)模型y=f(x1,x2,...,xd)，其中xi,i=1,...d為特征變量，y為分類(lèi)變量。當(dāng)y為離散變量時(shí)，即dom(y)={y1,y2,...,ym}，被稱(chēng)為分類(lèi)。

分類(lèi)也可定義為：分類(lèi)的任務(wù)就是通過(guò)學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)(TargetFunction)?，把每個(gè)屬性集x映射到一個(gè)預(yù)先定義的類(lèi)標(biāo)號(hào)y。

數(shù)據(jù)分類(lèi)過(guò)程有兩階段：

（1）學(xué)習(xí)階段（構(gòu)建分類(lèi)模型）。

（2）分類(lèi)階段（使用學(xué)習(xí)階段構(gòu)建的模型預(yù)測(cè)給定數(shù)據(jù)的類(lèi)標(biāo)號(hào)）。3.1.2分類(lèi)的過(guò)程of5653.1分類(lèi)概述第三章分類(lèi)建立分類(lèi)模型的一般方法3.1.2分類(lèi)的過(guò)程of5663.1分類(lèi)概述第三章分類(lèi)建立分類(lèi)模型的一般方法

訓(xùn)練集：用于訓(xùn)練模型，擬合參數(shù)，即模型擬合的數(shù)據(jù)樣本集合，如通過(guò)訓(xùn)練擬合一些參數(shù)來(lái)建立一個(gè)分類(lèi)器。

測(cè)試集：用來(lái)評(píng)估訓(xùn)練好的最終模型的性能如何，評(píng)價(jià)模型好壞，測(cè)試集沒(méi)有參于訓(xùn)練，主要是測(cè)試訓(xùn)練好的模型的準(zhǔn)確能力等，但不能作為調(diào)參、選擇特征等算法相關(guān)的選擇的依據(jù)。

訓(xùn)練數(shù)據(jù)中的數(shù)據(jù)不能再出現(xiàn)在驗(yàn)證數(shù)據(jù)以及測(cè)試數(shù)據(jù)中，驗(yàn)證數(shù)據(jù)最好也不要出現(xiàn)在測(cè)試數(shù)據(jù)中，這點(diǎn)在訓(xùn)練分類(lèi)器的時(shí)候一定要特別注意。

3.1.3分類(lèi)器性能的評(píng)估方法of5673.1分類(lèi)概述第三章分類(lèi)（1）評(píng)估分類(lèi)器性能的度量度量公式準(zhǔn)確率、識(shí)別率（TP+TN)/(P+N)錯(cuò)誤率、誤分類(lèi)率（FP+FN)/(P+N)敏感度、真正例率、召回率TP/P特效型、真負(fù)例率TN/N精度TP/(TP+FP)TP,TN,FP,FN,P,N分別表示真正例，真負(fù)例，假正例，假負(fù)例，正和負(fù)樣本數(shù)。

3.1.3分類(lèi)器性能的評(píng)估方法of5683.1分類(lèi)概述第三章分類(lèi)（2）比較分類(lèi)器的其他方面速度：這涉及產(chǎn)生和使用分類(lèi)器的計(jì)算開(kāi)銷(xiāo)。魯棒性：這是假的數(shù)據(jù)有噪聲或有缺失值時(shí)分類(lèi)器做出正確預(yù)測(cè)的能力。通常，魯棒性用噪聲和缺失值漸增的一系列合成數(shù)據(jù)集評(píng)估?？缮炜s性：這涉及給定大量數(shù)據(jù)，有效的構(gòu)造分類(lèi)器的能力。通常，可伸縮性用規(guī)模漸增的一系列數(shù)據(jù)集評(píng)估?？山忉屝裕哼@涉及分類(lèi)器或預(yù)測(cè)其提供的理解和洞察水平?？山忉屝允侵饔^的，因而很難評(píng)估。決策樹(shù)和分類(lèi)規(guī)則可能容易解釋?zhuān)S著它們變得更復(fù)雜，它們的可解釋性也隨著消失。

3.1.3分類(lèi)器性能的評(píng)估方法of5693.1分類(lèi)概述第三章分類(lèi)（3）如何獲得可靠的分類(lèi)器準(zhǔn)確率估計(jì)a.保持方法和隨機(jī)二次抽樣保持：給定數(shù)據(jù)隨機(jī)地劃分成兩個(gè)獨(dú)立的集合：訓(xùn)練集和檢驗(yàn)集。使用訓(xùn)練集導(dǎo)出模型，其準(zhǔn)確率用檢驗(yàn)集估計(jì)。估計(jì)是悲觀的，因?yàn)橹挥幸徊糠殖跏紨?shù)據(jù)用于導(dǎo)出模型。隨機(jī)二次抽樣：將保持方法重復(fù)次，總準(zhǔn)確率估計(jì)取每次迭代準(zhǔn)確率的平均值。b.交叉驗(yàn)證在k-折交叉驗(yàn)證（-foldcross-validation）中，初始數(shù)據(jù)隨機(jī)地劃分成k個(gè)互不相交的子集或“折”D1,D2,...,DK，每個(gè)折的大小大致相等。訓(xùn)練和檢驗(yàn)進(jìn)行k次。在第i次迭代，分區(qū)Di用做檢驗(yàn)集，其余的分區(qū)一起用做訓(xùn)練模型。c.自助法自助法從給定訓(xùn)練元組中有放回的均勻抽樣。103.2決策樹(shù)第三章分類(lèi)3.1

分類(lèi)概述3.3

貝葉斯分類(lèi)3.5實(shí)戰(zhàn)：Python支持向量機(jī)分類(lèi)習(xí)題3.4

支持向量機(jī)of5610高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用11of56113.2決策樹(shù)第三章分類(lèi)

3.2決策樹(shù)的實(shí)例

假設(shè)有一個(gè)公司想要招聘一個(gè)機(jī)器學(xué)習(xí)的算法工程師，公司在招聘的時(shí)候會(huì)有一定的流程對(duì)應(yīng)聘者進(jìn)行篩選。公司要對(duì)“是否錄用應(yīng)聘者？”這樣的問(wèn)題進(jìn)行決策時(shí)，會(huì)進(jìn)行一系列的判斷：首先看應(yīng)聘者“是否發(fā)表過(guò)頂會(huì)論文？”。如果是“發(fā)表過(guò)”，則直接錄用；如果是“沒(méi)有發(fā)表”，則再看“是否是研究生？”。如果“不是研究生”，則再看“是否為年級(jí)前十？”；如果“是研究生”，則再看“是否有機(jī)器學(xué)習(xí)項(xiàng)目的相關(guān)經(jīng)驗(yàn)？”。如果是“年級(jí)前十”，則直接錄用。如果有“機(jī)器學(xué)習(xí)相關(guān)項(xiàng)目經(jīng)驗(yàn)”，則直接錄取。圖3-2展示了招聘算法工程師的決策樹(shù)。12

決策樹(shù)（DecisionTree）是一種類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)（非樹(shù)葉節(jié)點(diǎn)）表示在屬性上的測(cè)試，每個(gè)分支表示該測(cè)試上的一個(gè)輸出，而每個(gè)樹(shù)葉節(jié)點(diǎn)存放一個(gè)類(lèi)標(biāo)號(hào)，樹(shù)的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。決策樹(shù)生成方式一般情況下都是由上而下的。每次不同的事件或決策都有可能引發(fā)至少兩個(gè)以上的事件，形成不同的結(jié)果，這種決策方法用圖形表示出來(lái)很像一棵樹(shù)，所以稱(chēng)之為決策樹(shù)。決策樹(shù)是一種簡(jiǎn)單且廣泛使用的分類(lèi)器。通過(guò)訓(xùn)練數(shù)據(jù)來(lái)構(gòu)建決策樹(shù)，可高效地對(duì)未知的數(shù)據(jù)進(jìn)行分類(lèi)。3.2.1決策樹(shù)概述of56123.2決策樹(shù)第三章分類(lèi)

決策樹(shù)是數(shù)據(jù)挖掘的有力工具之一，決策樹(shù)學(xué)習(xí)算法是從一組樣本數(shù)據(jù)集（一個(gè)樣本數(shù)據(jù)也可以稱(chēng)為實(shí)例）為基礎(chǔ)的一種歸納學(xué)習(xí)算法，它著眼于從一組無(wú)次序、無(wú)規(guī)則的樣本數(shù)據(jù)（概念）中推理出決策樹(shù)表示形式的分類(lèi)規(guī)則。決策樹(shù)的兩大優(yōu)點(diǎn)：（1）決策樹(shù)模型可讀性好且具有描述性，有助于人工分析。（2）效率高，決策樹(shù)只需一次構(gòu)建就可反復(fù)使用，每次預(yù)測(cè)的最大計(jì)算次數(shù)不超過(guò)決策樹(shù)的深度。13

基于決策樹(shù)的決策算法是屬于實(shí)用性很好的總結(jié)預(yù)測(cè)算法之一，是一個(gè)趨近于非連續(xù)型函數(shù)值的算法。決策樹(shù)在各行各業(yè)有著非常多的廣泛應(yīng)用，如在醫(yī)院的臨床決策、人臉檢測(cè)、故障診斷、故障預(yù)警、醫(yī)療數(shù)據(jù)挖掘、案例分析、分類(lèi)預(yù)測(cè)的軟件系統(tǒng)等方面都有很大的用處。決策樹(shù)是數(shù)據(jù)挖掘的有力工具之一。決策樹(shù)的最佳用途是圖解說(shuō)明如何領(lǐng)會(huì)決策與相關(guān)事件的相互作用。

決策樹(shù)的最佳用途是圖解說(shuō)明如何領(lǐng)會(huì)決策與相關(guān)事件的相互作用。

3.2.2決策樹(shù)的用途和特性of56133.2決策樹(shù)第三章分類(lèi)

決策樹(shù)的特性是能夠直觀的體現(xiàn)數(shù)據(jù)，一般通過(guò)簡(jiǎn)單分析都能理解決策樹(shù)表達(dá)的含義。決策樹(shù)對(duì)于數(shù)據(jù)要求不是很高，數(shù)據(jù)的表達(dá)形式一般很簡(jiǎn)單。另外，決策樹(shù)能夠在短時(shí)間內(nèi)對(duì)大型的數(shù)據(jù)源做出有效且可行的分析結(jié)果。14

決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類(lèi)的過(guò)程。它提供一種在什么條件下會(huì)得到什么值的類(lèi)似規(guī)則的方法。決策樹(shù)分為分類(lèi)樹(shù)和回歸樹(shù)兩種，分類(lèi)樹(shù)對(duì)離散變量做決策樹(shù)，回歸樹(shù)對(duì)連續(xù)變量做決策樹(shù)。

直觀看，決策樹(shù)分類(lèi)器就像判斷模塊和終止塊組成的流程圖，終止塊表示分類(lèi)結(jié)果（也就是樹(shù)的葉子）。判斷模塊表示對(duì)一個(gè)特征取值的判斷（該特征有幾個(gè)值，判斷模塊就有幾個(gè)分支）。3.2.3決策樹(shù)工作原理of56143.2決策樹(shù)第三章分類(lèi)買(mǎi)電腦的決策樹(shù)1515上圖表示了一個(gè)關(guān)心電子產(chǎn)品的用戶(hù)是否會(huì)購(gòu)買(mǎi)電腦，用它可以預(yù)測(cè)某條記錄（某個(gè)人）的購(gòu)買(mǎi)意向。樹(shù)中包含了三種節(jié)點(diǎn)：根節(jié)點(diǎn)（rootrode），它沒(méi)有入邊，但有兩條或多條出邊。子節(jié)點(diǎn)（childnode），恰有一條入邊和兩條或多條出邊。葉節(jié)點(diǎn)（leafnode）或終節(jié)點(diǎn)（terminalnode），恰有一條入邊，但沒(méi)有出邊。

在決策樹(shù)中，每個(gè)葉節(jié)點(diǎn)都賦予一個(gè)類(lèi)標(biāo)號(hào)。非終節(jié)點(diǎn)（包括根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)）包含屬性測(cè)試條件，用以分開(kāi)具有不同特性的記錄。這棵決策樹(shù)對(duì)銷(xiāo)售記錄進(jìn)行分類(lèi)，指出一個(gè)電子產(chǎn)品消費(fèi)者是否會(huì)購(gòu)買(mǎi)一臺(tái)計(jì)算機(jī)。每個(gè)內(nèi)部節(jié)點(diǎn)（方形框）代表對(duì)某個(gè)屬性的一次檢測(cè)。每個(gè)葉節(jié)點(diǎn)（橢圓框）代表一個(gè)類(lèi)。of56153.2決策樹(shù)第三章分類(lèi)3.2.3決策樹(shù)工作原理1616of56163.2決策樹(shù)第三章分類(lèi)

了解不難發(fā)現(xiàn)，樣本所有特征中有一些特征在分類(lèi)時(shí)起到了決定性作用，決策樹(shù)的構(gòu)造過(guò)程就是找到這些具有決定性作用的特征，根據(jù)其決定性程度來(lái)構(gòu)造一個(gè)倒立的樹(shù)，決定性作用最大的那個(gè)特征作為根節(jié)點(diǎn)，然后遞歸找到各分支下子數(shù)據(jù)集中次大的決定性特征，直至子數(shù)據(jù)集中所有數(shù)據(jù)都屬于同一類(lèi)[6]。所以，構(gòu)造決策樹(shù)的過(guò)程本質(zhì)上就是根據(jù)數(shù)據(jù)特征將數(shù)據(jù)集分類(lèi)的遞歸過(guò)程，需要解決的第一個(gè)問(wèn)題就是，當(dāng)前數(shù)據(jù)集上哪個(gè)特征在劃分?jǐn)?shù)據(jù)分類(lèi)時(shí)起決定性作用。圖3-3給出了一個(gè)商業(yè)上使用的決策樹(shù)的例子。3.2.3決策樹(shù)工作原理1717

決策樹(shù)分類(lèi)算法應(yīng)用的完整流程應(yīng)包含建樹(shù)和應(yīng)用。建樹(shù)是從經(jīng)驗(yàn)數(shù)據(jù)中獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)，建立模型或者構(gòu)造分類(lèi)器，是決策樹(shù)算法的工作重點(diǎn)，通常又將其分為建樹(shù)和剪枝兩個(gè)部分。而應(yīng)用則比較簡(jiǎn)單，利用建好的決策樹(shù)模型分類(lèi)或者預(yù)測(cè)新數(shù)據(jù)即可。

先來(lái)介紹一下建樹(shù)。建樹(shù)也就是決策樹(shù)分類(lèi)算法建模的主體過(guò)程，或者說(shuō)，建樹(shù)便是主要規(guī)則的產(chǎn)生過(guò)程。3.2.4決策樹(shù)構(gòu)建步驟of56173.2決策樹(shù)第三章分類(lèi)1818

決策樹(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í)行2～3步，直到每個(gè)節(jié)點(diǎn)足夠“純”為止。（“純”的含義是要么全部是“是”，要么全部是“否”）。3.2.4決策樹(shù)構(gòu)建步驟of56183.2決策樹(shù)第三章分類(lèi)1919

決策樹(shù)的變量可以有兩種：數(shù)字型（Numeric）和名稱(chēng)型（Nominal）。（1）數(shù)字型：變量類(lèi)型是整數(shù)或浮點(diǎn)數(shù)，如前面例子中的“年齡”。用“>”，“<”等作為分割條件（排序后，利用已有的分割情況，可以?xún)?yōu)化分割算法的時(shí)間復(fù)雜度）。（2）名稱(chēng)型：類(lèi)似編程語(yǔ)言中的枚舉類(lèi)型，變量只能從有限的選項(xiàng)中選取。3.2.4決策樹(shù)構(gòu)建步驟of56193.2決策樹(shù)第三章分類(lèi)

如何評(píng)估分割點(diǎn)的好壞？如果一個(gè)分割點(diǎn)可以將當(dāng)前的所有節(jié)點(diǎn)分為兩類(lèi)，使得每一類(lèi)都很“純”，也就是同一類(lèi)的記錄較多，那么就是一個(gè)好分割點(diǎn)。20203.2.4決策樹(shù)構(gòu)建步驟of56203.2決策樹(shù)第三章分類(lèi)數(shù)字型名稱(chēng)型212121

樹(shù)的主體建好后，接下來(lái)便是對(duì)其剪枝。

決策樹(shù)的剪枝一般通過(guò)極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(shù)來(lái)實(shí)現(xiàn)。

決策樹(shù)剪枝常用的方法有兩種：預(yù)剪枝和后剪枝。

of56213.2決策樹(shù)第三章分類(lèi)3.2.4決策樹(shù)構(gòu)建步驟222222of56223.2決策樹(shù)第三章分類(lèi)

預(yù)剪枝的核心問(wèn)題是，如何事先指定樹(shù)的最大深度，如果設(shè)置的最大深度不恰當(dāng)，那么將會(huì)導(dǎo)致過(guò)于限制樹(shù)的生長(zhǎng)，使決策樹(shù)的表達(dá)式規(guī)則趨于一般，不能更好地對(duì)新數(shù)據(jù)集進(jìn)行分類(lèi)和預(yù)測(cè)。

預(yù)剪枝是根據(jù)一些原則盡早停止樹(shù)的增長(zhǎng)，如樹(shù)的深度達(dá)到用戶(hù)所要的深度、節(jié)點(diǎn)中樣本個(gè)數(shù)少于用戶(hù)指定個(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)。3.2.4決策樹(shù)構(gòu)建步驟預(yù)剪枝

還有另外一個(gè)方法來(lái)實(shí)現(xiàn)預(yù)剪枝操作，那就是，采用檢驗(yàn)技術(shù)對(duì)當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的樣本集合進(jìn)行檢驗(yàn)，如果該樣本集合的樣本數(shù)量已小于事先指定的最小允許值，那么停止該結(jié)點(diǎn)的繼續(xù)生長(zhǎng)，并將該結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)，否則可以繼續(xù)擴(kuò)展該結(jié)點(diǎn)。232323of56233.2決策樹(shù)第三章分類(lèi)3.2.4決策樹(shù)構(gòu)建步驟后剪枝

后剪枝是通過(guò)在完全生長(zhǎng)的樹(shù)上剪去分枝實(shí)現(xiàn)的，通過(guò)刪除節(jié)點(diǎn)的分支來(lái)剪去樹(shù)節(jié)點(diǎn)，可以使用的后剪枝方法有多種，比如：錯(cuò)誤率降低修剪（Reduced-errorpruning）、規(guī)則后修剪（Rulepost-pruning）、最小錯(cuò)誤剪枝（MinimumErrorpruning，MEP）和最小描述長(zhǎng)度（MinimumDescriptionLength，MDL）算法等等。

后剪枝操作是一個(gè)邊修剪邊檢驗(yàn)的過(guò)程，一般規(guī)則標(biāo)準(zhǔn)是，在決策樹(shù)的不斷剪枝操作過(guò)程中，將原樣本集合或新數(shù)據(jù)集合作為測(cè)試數(shù)據(jù)，檢驗(yàn)決策樹(shù)可測(cè)試數(shù)據(jù)的預(yù)測(cè)精度，并計(jì)算出相應(yīng)的錯(cuò)誤率，如果剪掉某個(gè)子樹(shù)后的決策樹(shù)對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度或其他測(cè)度不降低，那么就剪掉該子樹(shù)。2424241.認(rèn)識(shí)決策樹(shù)

1）決策樹(shù)的生成過(guò)程

一棵決策樹(shù)的生成過(guò)程主要分為以下3個(gè)部分：

（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ò)擬合。3.2.5決策樹(shù)算法原理of56243.2決策樹(shù)第三章分類(lèi)252525

3.2.5決策樹(shù)算法原理of56253.2決策樹(shù)第三章分類(lèi)決策樹(shù)的優(yōu)點(diǎn)如下：

（1）適用于數(shù)值型和標(biāo)稱(chēng)型（離散型數(shù)據(jù)，變量的結(jié)果只在有限目標(biāo)集中取值），能夠讀取數(shù)據(jù)集合，提取一些列數(shù)據(jù)中蘊(yùn)含的規(guī)則。

（2）實(shí)現(xiàn)難度小，效率較高，可以在短時(shí)間內(nèi)高效處理大規(guī)模數(shù)據(jù)集，也更容易讓人理解。

（3）對(duì)于數(shù)據(jù)集的完備性要求不高，即使缺失部分?jǐn)?shù)據(jù)也可以對(duì)數(shù)據(jù)進(jìn)行處理，對(duì)于特征相關(guān)性較低的數(shù)據(jù)集進(jìn)行處理時(shí)能夠達(dá)到良好的效果。

（4）決策樹(shù)模型具有更高的魯棒性和靈活度，使其應(yīng)用范圍得到了拓寬。決策樹(shù)模型也有一些缺點(diǎn)，比如處理缺失數(shù)據(jù)時(shí)的困難、過(guò)度擬合以及忽略數(shù)據(jù)集中屬性之間的相關(guān)性等等。26262626

基于信息論的決策樹(shù)算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來(lái)。CART和C4.5支持?jǐn)?shù)據(jù)特征為連續(xù)分布時(shí)的處理，主要通過(guò)使用二元切分來(lái)處理連續(xù)型變量，即求一個(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í)它也是包含后剪枝操作。of56263.2決策樹(shù)第三章分類(lèi)3.2.5決策樹(shù)算法原理27272727

2.ID3算法

1）ID3算法的信息論基礎(chǔ)

（1）信息熵

信息熵：在概率論中，信息熵給了一種度量不確定性的方式，是用來(lái)衡量隨機(jī)變量不確定性的，熵就是信息的期望值。若待分類(lèi)的事物可能劃分在N類(lèi)中，分別是x1，x2，…,xn，每一種取到的概率分別是p1，p2，…,pn，那么X的熵就定義為：

從定義中可知：

當(dāng)隨機(jī)變量只取兩個(gè)值時(shí)，即X的分布

則熵為：of56273.2決策樹(shù)第三章分類(lèi)28282828

2.ID3算法

of56283.2決策樹(shù)第三章分類(lèi)

熵值越高，則數(shù)據(jù)混合的種類(lèi)越高，其蘊(yùn)含的含義是一個(gè)變量可能的變化越多（反而跟變量具體的取值沒(méi)有任何關(guān)系，只和值的種類(lèi)多少以及發(fā)生概率有關(guān)），它攜帶的信息量就越大。熵在信息論中是一個(gè)非常重要的概念，很多機(jī)器學(xué)習(xí)的算法都會(huì)利用到這個(gè)概念。292929292929

（2）條件熵

假設(shè)有隨機(jī)變量（X,Y）,其聯(lián)合概率分布為：P(X=xi,Y=yi)=pij,i=1,2,…,n;j=1,2,…,m。則條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性，其定義為X在給定條件下Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望：

若是樣本的特征只有兩個(gè)值(X1=0，X2=1),對(duì)應(yīng)(出現(xiàn)，不出現(xiàn))，如文本分類(lèi)中某一個(gè)單詞的出現(xiàn)與否。那么對(duì)于特征二值的情況，用T代表特征，用t代表T出現(xiàn)，

表示該特征不出現(xiàn)。那么：

與前面的公式對(duì)比一下，P(t)就是T出現(xiàn)的概率，P()就是T不出現(xiàn)的概率，結(jié)合信息熵的計(jì)算公式，可得：of56173.2決策樹(shù)第三章分類(lèi)3030303030

（3）信息增益

信息增益（InformationGain）表示得知特征X的信息后，而使得Y的不確定性減少的程度。定義為：

信息增益是針對(duì)一個(gè)一個(gè)的特征而言的，就是看一個(gè)特征X，系統(tǒng)有它和沒(méi)它的時(shí)候信息量各是多少，兩者的差值就是這個(gè)特征給系統(tǒng)帶來(lái)的信息增益。

對(duì)于特征取值為二值的情況，特征T給系統(tǒng)帶來(lái)的信息增益就可以寫(xiě)成系統(tǒng)原本的熵與固定特征T后的條件熵之差：of56303.2決策樹(shù)第三章分類(lèi)31313131312）ID3算法生成決策樹(shù)的過(guò)程

of56313.2決策樹(shù)第三章分類(lèi)算法3-1[14]輸入：訓(xùn)練集，特征集，分類(lèi)集輸出：決策規(guī)則集1.創(chuàng)建一個(gè)節(jié)點(diǎn)N2.ifA為空then3.以C中多數(shù)類(lèi)c來(lái)標(biāo)記N為葉子節(jié)點(diǎn)4.elseifS為空then5.以父節(jié)點(diǎn)中的多數(shù)類(lèi)c來(lái)標(biāo)記N為葉子節(jié)點(diǎn)6.elseif決策樹(shù)深度已經(jīng)達(dá)到了設(shè)置的最大值then7.以父節(jié)點(diǎn)中的多數(shù)c類(lèi)來(lái)標(biāo)記N為葉子節(jié)點(diǎn)8.elseifS屬于同一類(lèi)別cthen9.以該類(lèi)別c標(biāo)記N為葉子節(jié)點(diǎn)10.else計(jì)算并選擇A中具有最大增益的屬性a來(lái)標(biāo)記N11.endif12.根據(jù)屬性a的取值，將訓(xùn)練集S分割成個(gè)子集13.遞歸調(diào)用遞歸劃分停止的條件：（1）沒(méi)有條件屬性可以繼續(xù)劃分。（2）給定的分支的數(shù)據(jù)集為空。（3）數(shù)據(jù)集屬于同一類(lèi)。（4）決策樹(shù)已經(jīng)達(dá)到設(shè)置的最大值。3232323232

3）ID3算法使用實(shí)例

of56323.2決策樹(shù)第三章分類(lèi)

表3-4所示為某學(xué)院學(xué)生成績(jī)數(shù)據(jù)庫(kù)（訓(xùn)練樣本集合），訓(xùn)練樣本包含四個(gè)屬性，它們分別為成績(jī)、任課教師、A課程的修習(xí)類(lèi)別、是否修過(guò)B課程。樣本集合的類(lèi)別屬性為C課程是否合格，該屬性有2個(gè)取值，即為合格和不合格。序號(hào)成績(jī)?nèi)握n教師A課程的課程修習(xí)是否修過(guò)B課程C課程是否合格1>80甲核心無(wú)不合格2<60乙核心無(wú)不合格360--80丙核心無(wú)合格4>80甲專(zhuān)業(yè)選修無(wú)合格5<60丁非限定選修有不合格6>80甲非限定選修有不合格760--80丙非限定選修有合格8<60乙專(zhuān)業(yè)選修無(wú)合格9<60乙非限定選修有不合格10>80丁專(zhuān)業(yè)選修無(wú)不合格3333333333

3）ID3算法使用實(shí)例

of56333.2決策樹(shù)第三章分類(lèi)

成績(jī)屬性：“>80”有4個(gè)（這4個(gè)中C課程1個(gè)合格，3個(gè)不合格），“<60”有4個(gè)（這4個(gè)中C課程1個(gè)合格，3個(gè)不合格），“60--80”有2個(gè)（這2個(gè)C課程都是合格）。所以利用

可以計(jì)算H(成績(jī)):利用信息增益公式計(jì)算成績(jī)的信息增益：g(成績(jī))=H(X)-H=0.97-0.65=0.323434343434

3）ID3算法使用實(shí)例

of56343.2決策樹(shù)第三章分類(lèi)

任課教師屬性：甲3個(gè)（這3個(gè)中C課程1個(gè)合格，2個(gè)不合格），乙3個(gè)（這3個(gè)中C課程1個(gè)合格，2個(gè)不合格），丙2個(gè)（這2個(gè)C課程都是合格），丁2個(gè)（這2個(gè)C課程都是不合格）?？梢杂?jì)算H(任課教師)。

所以，任課教師的信息增益：g（任課教師）=H(X)-H(任課教師）=0.97-0.551=0.419。3535353535

3）ID3算法使用實(shí)例

of56353.2決策樹(shù)第三章分類(lèi)

A課程作為哪類(lèi)課程修習(xí)這個(gè)屬性，作為核心課程的為3個(gè)（這3個(gè)中C課程1個(gè)合格，2個(gè)不合格），作為專(zhuān)業(yè)選修的為3個(gè)（這3個(gè)中C課程2個(gè)合格，1個(gè)不合格），作為非限定選修的為4個(gè)（這4個(gè)中C課程1個(gè)合格，3個(gè)不合格）。利用公式可以計(jì)算H（A的修習(xí)類(lèi)別）。

所以，A的修習(xí)類(lèi)別信息增益：g(A的修習(xí)類(lèi)別)=H(X)-H(A的修習(xí)類(lèi)別)=0.97-0.876=0.0943636363636

3）ID3算法使用實(shí)例

of56363.2決策樹(shù)第三章分類(lèi)

是否修過(guò)B課程這個(gè)屬性，有修過(guò)的4個(gè)（這4個(gè)中C課程1個(gè)合格，3個(gè)不合格），無(wú)修過(guò)的6個(gè)（這6個(gè)中C課程3個(gè)合格，3個(gè)不合格）。利用公式可以計(jì)算H（是否修過(guò)B）。

所以，是否修過(guò)B的信息增益：g(是否修過(guò)B)=0.97-0.925=0.0453737373737

3）ID3算法使用實(shí)例

of56373.2決策樹(shù)第三章分類(lèi)

從上面對(duì)各屬性的信息增益計(jì)算，并根據(jù)ID3算法選擇分裂屬性的標(biāo)準(zhǔn)可知，第一個(gè)選擇的分裂屬性為成績(jī)。通過(guò)成績(jī)屬性的分裂，將樣本訓(xùn)練集分為四個(gè)分枝，其中丙教師任課分枝樣本全部通過(guò)C課程，丁教師任課分枝樣本全部屬于不通過(guò)C課程，所以這兩枝停止分裂。而甲任課和乙任課的樣本還包括合格與不合格類(lèi)，并且屬性集中還有三個(gè)屬性，因而需要進(jìn)一步計(jì)算屬性的信息增益，進(jìn)而選擇分裂屬性。通過(guò)計(jì)算，并根據(jù)ID3算法原理建立的完整決策樹(shù)如圖所示。3838383838

3）ID3算法優(yōu)缺點(diǎn)

of56383.2決策樹(shù)第三章分類(lèi)

ID3算法建樹(shù)過(guò)程簡(jiǎn)單且易懂。但是ID3存在多值偏向問(wèn)題，在選擇分裂屬性時(shí)，會(huì)優(yōu)先選擇取值較多的屬性，而在某一些情況下，這些屬性并不是最優(yōu)屬性；對(duì)于連續(xù)型屬性，傳統(tǒng)的ID3算法不能直接進(jìn)行處理；其次，屬性間的關(guān)聯(lián)性不強(qiáng)，但它正是ID3算法可以在Hadoop平臺(tái)上并行化的前提；再者，ID3算法對(duì)噪聲數(shù)據(jù)很敏感；最后，結(jié)果會(huì)隨著訓(xùn)練集規(guī)模的不同而不同。393939393939

3.C4.5算法

C4.5算法同樣以“信息熵”作為核心，是ID3基礎(chǔ)上的優(yōu)化改進(jìn)，同時(shí)，也保持了分類(lèi)準(zhǔn)確率高、速度快的特點(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à)，即：

信息增益率定義為平均互信息與獲取a信息所付出代價(jià)的比值，即：of56393.2決策樹(shù)第三章分類(lèi)404040404040

3.C4.5算法

of56403.2決策樹(shù)第三章分類(lèi)以ID3算法思想為核心，C4.5在此基礎(chǔ)上重點(diǎn)從以下幾個(gè)方面進(jìn)行了改進(jìn)：（1）利用信息增益比率作為新的屬性判別能力度量，較好解決了ID3算法優(yōu)先選擇具有較多值，而不是最優(yōu)屬性可能導(dǎo)致過(guò)擬合的現(xiàn)象。使用信息增益率能解決問(wèn)題，也產(chǎn)生一個(gè)新的問(wèn)題：既然是比率，就不能避免分母為0或者非常?。ó?dāng)某個(gè)接近時(shí)出現(xiàn)）的情況，出現(xiàn)這種情況的后果就是要么比率非常大，要么就未定義。為了避免這種情況的出現(xiàn)，可以將信息增益率計(jì)算分兩步走來(lái)解決：首先是計(jì)算所有屬性的信息增益，忽略掉結(jié)果低于平均值的屬性，僅對(duì)高于平均值的屬性進(jìn)一步計(jì)算信息增益率，從中擇優(yōu)選取分裂屬性。（2）缺失數(shù)據(jù)的處理思路。在面對(duì)缺失數(shù)據(jù)這一點(diǎn)上，C4.5針對(duì)不一樣的情況，采取不一樣的解決方法。方法如下：①若某一屬性在計(jì)算信息增益或者增益率過(guò)程中，出現(xiàn)某些樣本沒(méi)有屬性的情況，C4.5的處理方式：一是直接忽略掉這些樣本；二是根據(jù)缺失樣本占總樣本的比例，對(duì)屬性的增益或增益率進(jìn)行相應(yīng)“打折”；三是將屬性的一個(gè)均值或者最常見(jiàn)的值賦給這些缺失樣本；四是總結(jié)分析其他未知屬性的規(guī)律，補(bǔ)全這些缺失樣本。414141414141

3.C4.5算法

of56413.2決策樹(shù)第三章分類(lèi)以ID3算法思想為核心，C4.5在此基礎(chǔ)上重點(diǎn)從以下幾個(gè)方面進(jìn)行了改進(jìn)：②若屬性已被選為分裂屬性，分支過(guò)程中出現(xiàn)樣本缺失屬性的情況，C4.5的處理方式：一是直接忽略這些樣本；二是用一個(gè)出現(xiàn)頻率最高的值或者均值賦給這些樣本屬性；三是直接將這些缺失屬性的樣本依據(jù)規(guī)定的比例分配到所有子集中去；四是將所有缺失樣本歸為一類(lèi)，全部劃分到一個(gè)子集中；五是總結(jié)分析其他樣本，相應(yīng)的分配一個(gè)值給缺失屬性的樣本。③若某個(gè)樣本缺失了屬性，又未被分配到子集中去，面對(duì)這種情況，C4.5的處理方法是：一是若存在單獨(dú)的缺失分支，直接分配到該分支；二是將其直接賦予一個(gè)最常見(jiàn)的屬性的值，然后進(jìn)行正常的劃分；三是綜合分析屬性已存在的所有分支，按照一定的概率將其直接分到其中某一類(lèi)；四是根據(jù)其他屬性來(lái)進(jìn)行分支處理；五是所有待分類(lèi)樣本在屬性結(jié)點(diǎn)處都終止分類(lèi)，然后依據(jù)當(dāng)前結(jié)點(diǎn)所覆蓋的葉子結(jié)點(diǎn)類(lèi)別，為其直接分配一個(gè)概率最高的類(lèi)。424242424242

3.C4.5算法

of56423.2決策樹(shù)第三章分類(lèi)以ID3算法思想為核心，C4.5在此基礎(chǔ)上重點(diǎn)從以下幾個(gè)方面進(jìn)行了改進(jìn)：（3）連續(xù)屬性的處理思路面對(duì)連續(xù)屬性的情況，C4.5算法的思路是將連續(xù)屬性離散化，分成不同的區(qū)間段，再進(jìn)行相應(yīng)的處理。具體處理過(guò)程如下：一是按照一定的順序排列連續(xù)屬性；二是選取相鄰兩個(gè)屬性值的中點(diǎn)作為潛在劃分點(diǎn)，計(jì)算其信息增益；三是修正劃分點(diǎn)計(jì)算后的信息增益；四是在修正后的劃分點(diǎn)中作出選擇，小于均值的劃分點(diǎn)可以直接忽略；五是計(jì)算最大信息增益率；六是選擇信息增益率最大的劃分點(diǎn)作為分裂點(diǎn)。（4）剪枝策略C4.5有兩種基本剪枝策略：子樹(shù)替代法和子樹(shù)上升法。前者的思路是：從樹(shù)的底部向樹(shù)根方向，若某個(gè)葉結(jié)點(diǎn)替代子樹(shù)后，誤差率與原始樹(shù)很接近，便可用這個(gè)葉結(jié)點(diǎn)取代整棵子樹(shù)；后者則是誤差率在一定合理范圍時(shí)，將一棵子樹(shù)中出現(xiàn)頻率最高的子樹(shù)用以替代整棵子樹(shù)，使其上升到較高結(jié)點(diǎn)處。C4.5算法雖說(shuō)突破了ID3算法很多方面的瓶頸，產(chǎn)生的分類(lèi)規(guī)則準(zhǔn)確率也比較高、易于理解，但是在核心的思想上還是保持在“信息熵”的范疇，最終仍生成多叉樹(shù)。同時(shí)，缺點(diǎn)也較為明顯：建造樹(shù)時(shí)，訓(xùn)練集要進(jìn)行多次排序和掃描，所以效率不高。此外，C4.5算法只能處理駐留于內(nèi)存的數(shù)據(jù)集，若訓(xùn)練集過(guò)大，超過(guò)內(nèi)存容量時(shí)，算法便無(wú)能為力了。434343434343

3.C4.5算法

of56433.2決策樹(shù)第三章分類(lèi)2）C4.5算法建樹(shù)過(guò)程算法3-2[14]輸入：訓(xùn)練集，特征集輸出：決策規(guī)則集1.創(chuàng)建一個(gè)節(jié)點(diǎn)N2.ifA為空then3.以C中多數(shù)類(lèi)c來(lái)標(biāo)記N為葉子節(jié)點(diǎn)4.elseifS為空then5.以父節(jié)點(diǎn)中的多數(shù)類(lèi)c來(lái)標(biāo)記N為葉子節(jié)點(diǎn)6.elseif決策樹(shù)深度已經(jīng)達(dá)到了設(shè)置的最大值then7.以父節(jié)點(diǎn)中的多數(shù)c類(lèi)來(lái)標(biāo)記N為葉子節(jié)點(diǎn)8.elseifS同屬一個(gè)類(lèi)別cthen9.以c標(biāo)記N為葉子節(jié)點(diǎn)10.else計(jì)算并選擇A中具有最大信息增益率的屬性a來(lái)標(biāo)記N；如果A中具有連續(xù)性的屬性，則還需要對(duì)其先離散化11.根據(jù)屬性的取值，將訓(xùn)練集橫向分割成n個(gè)子集12.遞歸調(diào)用遞歸劃分停止的條件：（1）沒(méi)有條件屬性可以繼續(xù)劃分。（2）給定的分支的數(shù)據(jù)集為空。（3）數(shù)據(jù)集屬于同一類(lèi)。（4）決策樹(shù)已經(jīng)達(dá)到設(shè)置的最大值。444444444444

3.C4.5算法

of56443.2決策樹(shù)第三章分類(lèi)3）C4.5算法應(yīng)用實(shí)例天氣溫度濕度風(fēng)速活動(dòng)晴炎熱高弱取消晴炎熱高強(qiáng)取消陰炎熱高弱進(jìn)行雨適中高弱進(jìn)行雨寒冷正常弱進(jìn)行雨寒冷正常強(qiáng)取消陰寒冷正常強(qiáng)進(jìn)行晴適中高弱進(jìn)行晴寒冷正常弱進(jìn)行雨適中正常弱進(jìn)行晴適中正常強(qiáng)進(jìn)行陰適中高強(qiáng)進(jìn)行陰炎熱正常弱進(jìn)行雨適中高強(qiáng)取消

表中有四個(gè)屬性，屬性集合A={天氣,溫度,濕度,風(fēng)速}，類(lèi)別標(biāo)簽有兩個(gè)，類(lèi)別集合L={進(jìn)行,取消}。454545454545

3.C4.5算法

of56453.2決策樹(shù)第三章分類(lèi)3）C4.5算法應(yīng)用實(shí)例①計(jì)算類(lèi)別信息熵類(lèi)別信息熵表示的是所有樣本中各種類(lèi)別出現(xiàn)的不確定性之和。根據(jù)熵的概念，熵越大，不確定性就越大，把事情搞清楚所需要的信息量就越多。464646464646

3.C4.5算法

of56463.2決策樹(shù)第三章分類(lèi)3）C4.5算法應(yīng)用實(shí)例②計(jì)算每個(gè)屬性的信息熵每個(gè)屬性的信息熵相當(dāng)于一種條件熵。他表示的是在某種屬性的條件下，各種類(lèi)別出現(xiàn)的不確定性之和。屬性的信息熵越大，表示這個(gè)屬性中擁有的樣本類(lèi)別越不“純”。474747474747

3.C4.5算法

of56473.2決策樹(shù)第三章分類(lèi)3）C4.5算法應(yīng)用實(shí)例③計(jì)算信息增益信息增益=熵-條件熵，在這里就是類(lèi)別信息熵-屬性信息熵，它表示的是信息不確定性減少的程度。如果一個(gè)屬性的信息增益越大，就表示用這個(gè)屬性進(jìn)行樣本劃分可以更好的減少劃分后樣本的不確定性，當(dāng)然，選擇該屬性就可以更快更好地完成我們的分類(lèi)目標(biāo)。信息增益就是ID3算法的特征選擇指標(biāo)。但是我們假設(shè)這樣的情況，每個(gè)屬性中每種類(lèi)別都只有一個(gè)樣本，那這樣屬性信息熵就等于零，根據(jù)信息增益就無(wú)法選擇出有效分類(lèi)特征。所以，C4.5選擇使用信息增益率對(duì)ID3進(jìn)行改進(jìn)。484848484848

3.C4.5算法

of56483.2決策樹(shù)第三章分類(lèi)3）C4.5算法應(yīng)用實(shí)例④計(jì)算屬性分裂信息度量用分裂信息度量來(lái)考慮某種屬性進(jìn)行分裂時(shí)分支的數(shù)量信息和尺寸信息，我們把這些信息稱(chēng)為屬性的內(nèi)在信息（instrisicinformation）。信息增益率用信息增益/內(nèi)在信息，會(huì)導(dǎo)致屬性的重要性隨著內(nèi)在信息的增大而減?。ㄒ簿褪钦f(shuō)，如果這個(gè)屬性本身不確定性就很大，那就越不傾向于選取它），這樣算是對(duì)單純用信息增益有所補(bǔ)償。494949494949

3.C4.5算法

of56493.2決策樹(shù)第三章分類(lèi)3）C4.5算法應(yīng)用實(shí)例⑤計(jì)算信息增益率

天氣的信息增益率最高，選擇天氣為分裂屬性。發(fā)現(xiàn)分裂了之后，天氣是“陰”的條件下，類(lèi)別是”純“的，所以把它定義為葉子節(jié)點(diǎn)，選擇不“純”的結(jié)點(diǎn)繼續(xù)分裂。在子結(jié)點(diǎn)當(dāng)中重復(fù)過(guò)程①~⑤。505050505050504.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)分類(lèi)方法適用于具有連續(xù)性或離散性屬性的數(shù)據(jù)集。

設(shè)S為具有s個(gè)樣本的數(shù)據(jù)集，所有樣本總共包含m個(gè)不同的類(lèi)別Ci，i?{1,2,…,m}，那么Gini指標(biāo)為：

其中Pi為樣本屬性類(lèi)別Ci的概率。of56503.2決策樹(shù)第三章分類(lèi)當(dāng)Gini(S)=0表示該節(jié)點(diǎn)包含的信息量最大；當(dāng)Gini(S)最大時(shí)，表示該節(jié)點(diǎn)包含的信息量最小。5151515151515151

根據(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ì)算公式如下：

其中|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ū)的第75頁(yè)。of56213.2決策樹(shù)第三章分類(lèi)52523.3

貝葉斯分類(lèi)第三章分類(lèi)3.1基本概念3.2決策樹(shù)3.5實(shí)戰(zhàn)：決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題3.4

支持向量機(jī)of5652高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用5353

貝葉斯分類(lèi)是一類(lèi)分類(lèi)算法的總稱(chēng)，這類(lèi)算法均以貝葉斯定理（Bayestheorem）為基礎(chǔ)，采用了概率推理方法。3.3.1貝葉斯定理of56533.3貝葉斯分類(lèi)第三章分類(lèi)

條件概率：表示事件B已經(jīng)發(fā)生的前提下，事件A發(fā)生的概率，稱(chēng)為事件B發(fā)生下事件A的條件概率。其基本求解公式為：

貝葉斯定理之所以有用，是因?yàn)樵谏钪薪?jīng)常遇到這種情況：可以很容易直接得出P(A|B),P(B|A)則很難直接得出，但人們往往更關(guān)心P(B|A),貝葉斯定理打通了從P(A|B)獲得P(B|A)的道路。

貝葉斯定理：545454

樸素貝葉斯分類(lèi)是貝葉斯分類(lèi)的一種，樸素貝葉斯分類(lèi)與貝葉斯分類(lèi)相比，后者需要花很大的時(shí)間和空間復(fù)雜度去計(jì)算類(lèi)條件概率。1.樸素貝葉斯分類(lèi)原理

樸素貝葉斯的思想基礎(chǔ)是這樣的：對(duì)于給出的待分類(lèi)項(xiàng)，求解在此項(xiàng)出現(xiàn)的條件下各個(gè)類(lèi)別出現(xiàn)的概率，哪個(gè)最大，就認(rèn)為此待分類(lèi)項(xiàng)屬于哪個(gè)類(lèi)別。

樸素貝葉斯分類(lèi)的正式定義如下：

（1）設(shè)x={a1,a2,…,am},為一個(gè)待分類(lèi)項(xiàng)，而每個(gè)a為x的一個(gè)特征屬性。

（2）有類(lèi)別集合C={y1,y2,…,yn}。

（3）計(jì)算P(y1|x),P(y2|x),…,P(yn|x)。

（4）如果P(yk|x)=max{P(y1|x),P(y2|x),…,P(yn|x)},則x?yk。of56543.3貝葉斯分類(lèi)第三章分類(lèi)3.3.2樸素貝葉斯分類(lèi)原理與流程555555552.樸素貝葉斯分類(lèi)流程

整個(gè)樸素貝葉斯分類(lèi)可分為三個(gè)階段：

第一階段是準(zhǔn)備工作階段，這個(gè)階段的任務(wù)是為樸素貝葉斯分類(lèi)做必要的準(zhǔn)備，主要工作是根據(jù)具體情況確定特征屬性，并對(duì)每個(gè)特征屬性進(jìn)行適當(dāng)劃分，然后由人工對(duì)一部分待分類(lèi)項(xiàng)進(jìn)行分類(lèi)，形成訓(xùn)練樣本集合。

第二階段是分類(lèi)器訓(xùn)練階段，這個(gè)階段的任務(wù)就是生成分類(lèi)器，主要工作是計(jì)算每個(gè)類(lèi)別在訓(xùn)練樣本中的出現(xiàn)頻率及每個(gè)特征屬性劃分對(duì)每個(gè)類(lèi)別的條件概率估計(jì)，并將結(jié)果進(jìn)行記錄。

第三階段是應(yīng)用階段。

這個(gè)階段的任務(wù)是使用分類(lèi)器對(duì)分類(lèi)項(xiàng)進(jìn)行分類(lèi)，其輸入是分類(lèi)器和待分類(lèi)項(xiàng)，輸出是待分類(lèi)項(xiàng)與類(lèi)別的映射關(guān)系。of56553.3貝葉斯分類(lèi)第三章分類(lèi)5656565656

樸素貝葉斯分類(lèi)的流程圖如下圖。of56263.3貝葉斯分類(lèi)第三章分類(lèi)5757575757

貝葉斯分析中的三要素（即貝葉斯統(tǒng)計(jì)三要素，一要素是先驗(yàn)概率P(A),二要素是條件概率P(A|B),最終得到三要素即后驗(yàn)概率P(B|A)。

理解貝葉斯分析最好的方法即圖像法，如圖所示。A為紅圈，B為藍(lán)圈，AB為紫圈。這里的A（紅圈的面積即先驗(yàn)，后驗(yàn)是陰影占藍(lán)圈（B）的百分比。of56573.3貝葉斯分類(lèi)第三章分類(lèi)3.3.3貝葉斯分析5858585858

of56583.3貝葉斯分類(lèi)第三章分類(lèi)3.3.3貝葉斯分析

貝葉斯分析可以瞬間理解一些常用的理論，如幸存者偏差，你發(fā)現(xiàn)一些沒(méi)讀過(guò)書(shū)的人很有錢(qián)，事實(shí)上是你發(fā)現(xiàn)就已經(jīng)是幸存者了（對(duì)應(yīng)圖3-6中白圈A），而死了的人（白圈外的大部分面積）你都沒(méi)見(jiàn)到啊。還有陰謀論，陰謀論的特點(diǎn)是條件很多很復(fù)雜，但是條件一旦成立，結(jié)論幾乎成立，你一旦考慮了先驗(yàn)，這些條件成立本身就很困難，陰謀論不攻自破了。

此處貝葉斯分析的框架也在教導(dǎo)我們?nèi)绾翁幚硖乩c一般常識(shí)的規(guī)律。如果你太注重特例（即完全不看先驗(yàn)概率），很有可能會(huì)誤把噪聲看做信號(hào)，而奮不顧身的跳下去。而如果恪守先驗(yàn)概率，就成為無(wú)視變化而墨守成規(guī)的人。

其實(shí)只有貝葉斯流的人生存率會(huì)更高，因?yàn)樗麄儠?huì)重視特例，但也不忘記書(shū)本的經(jīng)驗(yàn)，根據(jù)貝葉斯公式小心調(diào)整信心，甚至?xí)鲃?dòng)根據(jù)信號(hào)判斷假設(shè)來(lái)設(shè)計(jì)實(shí)驗(yàn)。595959595959

貝葉斯決策主要包含四個(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í)。用貝葉斯決策詮釋一個(gè)最簡(jiǎn)單的機(jī)器學(xué)習(xí)分類(lèi)算法，那就是樸素貝葉斯。of56593.3貝葉斯分類(lèi)第三章分類(lèi)3.3.4貝葉斯決策606060606060of56603.3貝葉斯分類(lèi)第三章分類(lèi)3.3.4貝葉斯估計(jì)

貝葉斯估計(jì)假定是服從某一分布的隨機(jī)變量，但貝葉斯估計(jì)并不是直接估計(jì)出的某個(gè)特定值，而是估計(jì)的分布，進(jìn)而用來(lái)估計(jì)新數(shù)據(jù)出現(xiàn)的概率。在貝葉斯估計(jì)中，先驗(yàn)分布是不可忽略的。在已知的情況下，描述的分布即描述后驗(yàn)概率分布，然后求出的期望值，將這個(gè)期望值作為其最優(yōu)值。假設(shè)X=(x1,x2,...,xn)是滿(mǎn)足獨(dú)立同分布的一組抽樣數(shù)據(jù)樣本，其對(duì)應(yīng)的參數(shù)是隨機(jī)的，根據(jù)貝葉斯公式可以求得的后驗(yàn)概率其中，p(X)的概率是不確定的，可由得到，因此，上式變?yōu)?16161616161of56613.3貝葉斯分類(lèi)第三章分類(lèi)3.3.4貝葉斯估計(jì)總結(jié)貝葉斯估計(jì)的求解步驟為：（1）確定所求參數(shù)的似然函數(shù)；（2）確定所求參數(shù)的先驗(yàn)分布函數(shù)；（3）確定所求參數(shù)的后驗(yàn)分布函數(shù)；（4）根據(jù)貝葉斯公式求解參數(shù)的后驗(yàn)分布。6262623.4支持向量機(jī)第三章分類(lèi)3.1基本概念3.2決策樹(shù)3.5實(shí)戰(zhàn)：決策樹(shù)算法在Weka中的實(shí)現(xiàn)習(xí)題3.3貝葉斯分類(lèi)of5662高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用636363

支持向量機(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ī)主要思想of56633.4支持向量機(jī)第三章分類(lèi)SVM主要思想是針對(duì)兩類(lèi)分類(lèi)問(wèn)題的，尋找一個(gè)超平面作為兩類(lèi)訓(xùn)練樣本點(diǎn)的分割，以保證最小的分類(lèi)錯(cuò)誤率。在線性可分的情況下，存在一個(gè)或多個(gè)超平面使得訓(xùn)練樣本完全分開(kāi)，SVM的目標(biāo)是找到其中的最優(yōu)超平面，最優(yōu)超平面是使得每一類(lèi)數(shù)據(jù)與超平面距離最近的向量與超平面之間的距離最大的平面；對(duì)于線性不可分的情況，可使用非線性核函數(shù)將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分。3.4.2支持向量機(jī)基礎(chǔ)理論

支持向量機(jī)的理論有三個(gè)要點(diǎn)，即：

（1）最大化間隔。

（2）核函數(shù)。

（3）對(duì)偶理論。64646464

1.最大化間隔

在樣本線性可分的情況下，可行的分類(lèi)超平面可能會(huì)有很多，如下圖中的L1、L2和L3。

從圖中可以直觀看出，L2比另外兩條分界線要更好，這是因?yàn)長(zhǎng)2離樣本的距離更遠(yuǎn)一些，讓人覺(jué)得確信度更高。SVM正是基于這種直觀思路來(lái)確定最佳分類(lèi)超平面的：通過(guò)選取能夠最大化類(lèi)間間隔的超平面，得到一個(gè)具有高確信度和泛化能力的分類(lèi)器，即最大間隔分類(lèi)器。of56643.4支持向量機(jī)第三章分類(lèi)65656565

1.最大化間隔

of56653.4支持向量機(jī)第三章分類(lèi)(1)間隔

既然SVM的目標(biāo)是最大化間隔，便要先對(duì)“間隔”進(jìn)行定義。所謂間隔，就是分類(lèi)超平面與所有樣本距離的最小值，表示為：

其中l(wèi)表示分類(lèi)超平面，N為樣本個(gè)數(shù)，為第個(gè)樣本。接下來(lái)還需要定義樣本到超平面的“距離”dist(l,x)。

可以得到：所以，分類(lèi)超平面1和N個(gè)樣本xi的間隔表達(dá)式為：66666666

1.最大化間隔

of56663.4支持向量機(jī)第三章分類(lèi)(2)最大化

有了上述定義的間隔，接下來(lái)的事情就很直接了——求解能使間隔最大化的參數(shù)和，即求解以下優(yōu)化函數(shù)：上述優(yōu)化函數(shù)也可以寫(xiě)成如下等價(jià)的形式s.t.其中的約束條件是為了滿(mǎn)足對(duì)“間隔”的定義。67676767672.核函數(shù)

核函數(shù)的定義：

設(shè)s是輸入空間（歐氏空間或離散集合），H為特征空間（希爾伯特空間），如果存在一個(gè)從s到H的映射

。

使得對(duì)所有的x，z?s,函數(shù),則稱(chēng)K(x,z),為核函數(shù)。為映射函數(shù)，

為x，z映射到特征空間上的內(nèi)積。

常用的核函數(shù)主要有以下幾種：

（1）線性核函數(shù)（Liner）。

（2）多項(xiàng)式核函數(shù)（Polynomial）。（3）高斯（Gaussian）核函數(shù)(又稱(chēng)徑向基函數(shù)，RBF)。

of56673.4支持向量機(jī)第三章分類(lèi)68686868682.核函數(shù)

（4）指數(shù)型徑向基核函數(shù)。

（5）Sigmoid（或2層感知機(jī)）。

（6）傅立葉（Fourier）核函數(shù)。of56683.4支持向量機(jī)第三章分類(lèi)此外，條件正定核函數(shù)(CPD核函數(shù))6969696969693.對(duì)偶理論（DualityTheory）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)題之間存在著具體關(guān)系，見(jiàn)下表。of56333.4支持向量機(jī)第三章分類(lèi)707070707070

原—對(duì)偶優(yōu)化方法：1）凸優(yōu)化問(wèn)題

minf(x)

對(duì)于如上線性?xún)?yōu)化問(wèn)題，若f(x)，w(x)是凸函數(shù)，可行解集合是可行域F上的凸集，則稱(chēng)這類(lèi)優(yōu)化問(wèn)題為凸優(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)。

of56703.4支持向量機(jī)第三章分類(lèi)s.t.717171717171

原—對(duì)偶優(yōu)化方法：

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)解。of56713.4支持向量機(jī)第三章分類(lèi)

采用子梯度算法來(lái)求解對(duì)偶問(wèn)題，現(xiàn)對(duì)算法基本流程表述如下：(1)首先，用拉格朗日松弛法對(duì)造成原問(wèn)題不易解決的約束條件進(jìn)行松弛，并使得目標(biāo)函數(shù)仍保持線性，令為拉格朗日乘子，其中要求滿(mǎn)足≥0，則對(duì)原問(wèn)題松弛后的拉格朗日函數(shù)如下：727272727272of56723.4支持向量機(jī)第三章分類(lèi)（2）其次，求原問(wèn)題的對(duì)偶問(wèn)題，并推知，

對(duì)偶問(wèn)題為：s.t.（3）最后，子梯度法求解對(duì)偶問(wèn)題

和其它數(shù)學(xué)優(yōu)化方法相比，原-對(duì)偶法具有一些不可比擬的優(yōu)點(diǎn)。最突出的特點(diǎn)是通過(guò)使用拉格朗日乘法原則放松了原數(shù)學(xué)模型中的約束條件，這樣可以把原問(wèn)題中耦合在一起的原變量分離，把復(fù)雜的原問(wèn)題分成幾個(gè)獨(dú)立且易解決的子問(wèn)題進(jìn)行求解，降低了算法的復(fù)雜度，能夠?qū)崿F(xiàn)分布式計(jì)算。737373737373734.幾種常用的損失函數(shù)1）lp損失函數(shù)其中≥1，p表示范數(shù)。顯然常用的平方損失和絕對(duì)值損失是損失函數(shù)的特例。在回歸問(wèn)題中，平方損失由于其光滑性有著廣泛的應(yīng)用(最小二乘估計(jì))。而近年來(lái)，由于計(jì)算能力的改進(jìn)，絕對(duì)值損失也因其良好的穩(wěn)健性而逐漸成為熱點(diǎn)(最小一乘估計(jì))。2）?-不靈敏損失函數(shù)

支撐向量機(jī)(SVM)就是采用上述損失函數(shù)的一種處理高維問(wèn)題的學(xué)習(xí)算法。3）logistic損失函數(shù)

logistic損失函數(shù)多應(yīng)用于分類(lèi)問(wèn)題的研究。近期研究發(fā)現(xiàn)AdaBoost可以看成采用上述損失函數(shù)的函數(shù)空間的梯度下降算法.of56733.4支持向量機(jī)第三章分類(lèi)74747474747474

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ù)。

結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則為我們提供了一種不同于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的更科學(xué)的學(xué)習(xí)機(jī)器設(shè)計(jì)原則。但是，實(shí)施這一原則卻非常困難，關(guān)鍵是如何構(gòu)造函數(shù)子集結(jié)構(gòu)。遺憾的是，目前尚無(wú)關(guān)于如何構(gòu)造預(yù)測(cè)函數(shù)子集結(jié)構(gòu)的一般性理論。支持向量機(jī)是一種比較好的實(shí)現(xiàn)了結(jié)構(gòu)風(fēng)險(xiǎn)最小化思想的方法。of56743.4支持向量機(jī)第三章分類(lèi)757575753.4.3支持向量機(jī)原理of56753.4支持向量機(jī)第三章分類(lèi)

1.支持向量機(jī)（SVM）

支持向量機(jī)（SVM）是一種分類(lèi)算法，通過(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）線性可分情況。右圖為線性可分情況。

圖中的圈和叉代表待分類(lèi)的兩類(lèi)樣本，H就是要求的最優(yōu)分類(lèi)超平面，H1和H2是與最優(yōu)分類(lèi)面平行的直線且分別通過(guò)這兩類(lèi)樣本里距離H最近的樣本點(diǎn)。此時(shí)的分類(lèi)函數(shù)為：7676767676of56763.4支持向量機(jī)第三章分類(lèi)2）線性不可分情況

線性可分就是在樣本存在的空間中，可以找到可能正確劃分訓(xùn)練樣本的最優(yōu)分類(lèi)超平面。但在現(xiàn)實(shí)中無(wú)法找到一個(gè)使得所有訓(xùn)練樣本關(guān)于分類(lèi)超平面的間隔都是正值的分類(lèi)超平面。必須適當(dāng)軟化條件。

對(duì)于那些需要軟化的條件，將它們分為兩類(lèi)：一類(lèi)是雖不滿(mǎn)足KKT條件但是可以被正確劃分的點(diǎn)；另外一類(lèi)是不滿(mǎn)足KKT條件也不能被正確劃分的點(diǎn)。

遇到線性不可分時(shí)，常用做法是把樣例特征映射到高維空間中去，如下圖所示。7777777777777777

線性不可分映射到高維空間，可能會(huì)導(dǎo)致維度大小高到可怕的程度，導(dǎo)致計(jì)算復(fù)雜。核函數(shù)的價(jià)值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)事先在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類(lèi)效果表現(xiàn)在了高維上，也就避免了直接在高維空間中的復(fù)雜計(jì)算。

此時(shí)的分類(lèi)函數(shù)為：3）非線性可分情況

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

SVM剛開(kāi)始主要是用于分類(lèi)問(wèn)題，后來(lái)V.Vapnik等人通過(guò)引入不敏感損失函數(shù)，將SVM推廣到回歸估計(jì)，建立了支持向量機(jī)回歸。其基本思想是將原始輸入空間轉(zhuǎn)化為高維特征空間，然后再高維特征空間中尋找輸入和輸出變量間的線性關(guān)系。即給定數(shù)據(jù)樣本集合S={(xi,yi),...,(xm,ym)}，其中，xi屬于Rn,yi屬于Rn,i=1,2,3,...,m。在Rn上尋找函數(shù)f(x),使y=f(x)。SVR分為線性回歸和非線性回歸兩種情況。（1）線性回歸線性回歸函數(shù)可以寫(xiě)為：(2)非線性回歸797979793.5實(shí)戰(zhàn)：Python支持向量機(jī)分類(lèi)第三章分類(lèi)3.1基本概念3.2決策樹(shù)3.4支持向量機(jī)習(xí)題3.3貝葉斯分類(lèi)of5679高級(jí)大數(shù)據(jù)人才培養(yǎng)叢書(shū)之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用8080of56803.5實(shí)戰(zhàn)：Python支持向量機(jī)分類(lèi)第三章分類(lèi)

因?yàn)镻ython中的scikit-learn庫(kù)集成了SVM算法，使用方法較為便捷，因此本次實(shí)驗(yàn)選擇在Python中使用支持向量機(jī)做分類(lèi)。本文用的數(shù)據(jù)集為鳶尾花（Iris）數(shù)據(jù)集，這是統(tǒng)計(jì)學(xué)中一個(gè)經(jīng)典的數(shù)據(jù)集，其中包含了150條鳶尾花相關(guān)數(shù)據(jù)。它包含在scikit-learn的datasets模塊中。因此我們調(diào)用load_iris函數(shù)來(lái)加載數(shù)據(jù)：#載入鳶尾花數(shù)據(jù)集fromsklearnimportdatasetsiris=datasets.load_iris()818181of56813.5實(shí)戰(zhàn)：Python支持向量機(jī)分類(lèi)第三章分類(lèi)

Iris.data的部分?jǐn)?shù)據(jù)如圖所示：共5列，前4列為樣本特征，第5列為類(lèi)別，分別有三種類(lèi)別Iris-setosa，Iris-versicolor，Iris-virginica。SepalLengthSepalWidthPetalLengthPetalWidthClass5.13.51.40.2Iris-setosa4.93.01.40.2Iris-setosa4.73.21.30.2Iris-setosa4.63.11.50.2Iris-setosa5.03.61.40.2Iris-setosa5.43.91.70.4Ir