樸素貝葉斯分類算法課件

1、第3章 分類與回歸3.1 概述3.2 決策樹分類方法3.3 貝葉斯分類方法3.4 K-最近鄰分類方法3.5 神經(jīng)網(wǎng)絡(luò)分類方法3.6 支持向量機(jī)3.7 組合學(xué)習(xí)方法3.8 不平衡數(shù)據(jù)分類問題3.9 分類模型的評(píng)價(jià)3.10 回歸方法3.1 概述分類的定義分類是數(shù)據(jù)挖掘中的一種主要分析手段分類的任務(wù)是對(duì)數(shù)據(jù)集進(jìn)行學(xué)習(xí)并構(gòu)造一個(gè)擁有預(yù)測(cè)功能的分類模型，用于預(yù)測(cè)未知樣本的類標(biāo)號(hào)，如：根據(jù)電子郵件的標(biāo)題和內(nèi)容檢查出垃圾郵件根據(jù)核磁共振的結(jié)果區(qū)分腫瘤是惡性還是良性的根據(jù)星系的形狀對(duì)它們進(jìn)行分類劃分出交易是合法或欺詐將新聞分類金融、天氣、娛樂體育等分類與回歸的區(qū)別分類和回歸都有預(yù)測(cè)的功能，但是：分類預(yù)測(cè)的輸出

2、為離散或標(biāo)稱的屬性；回歸預(yù)測(cè)的輸出為連續(xù)屬性值；分類與回歸的例子：預(yù)測(cè)未來某銀行客戶會(huì)流失或不流失，這是分類任務(wù)；預(yù)測(cè)某商場(chǎng)未來一年的總營(yíng)業(yè)額，這是回歸任務(wù)。分類的步驟分類的過程描述如下：1)首先將數(shù)據(jù)集劃分為2部分：訓(xùn)練集和測(cè)試集。2) 第一步：對(duì)訓(xùn)練集學(xué)習(xí)，構(gòu)建分類模型。模型可以是決策樹或分類規(guī)則等形式。3) 第二步：用建好的分類模型對(duì)測(cè)試集分類評(píng)估該分類模型的分類準(zhǔn)確度及其它性能。4)最后，使用分類準(zhǔn)確度高的分類模型對(duì)類標(biāo)號(hào)未知的未來樣本數(shù)據(jù)進(jìn)行分類。分類與聚類的區(qū)別分類因?yàn)槭褂昧祟悩?biāo)號(hào)屬性，屬于有監(jiān)督的學(xué)習(xí)方法聚類，事先沒有使用任何類標(biāo)號(hào)信息，屬于無(wú)監(jiān)督的學(xué)習(xí)方法分類的應(yīng)用目前分類與回

3、歸方法已被廣泛應(yīng)用于各行各業(yè)，如：股票預(yù)測(cè)信用評(píng)估醫(yī)療診斷市場(chǎng)營(yíng)銷圖像分類等數(shù)據(jù)挖掘中分類算法歸類分類模型的學(xué)習(xí)方法大體上主要有以下幾類 基于決策樹的分類方法貝葉斯分類方法 K-最近鄰分類方法 神經(jīng)網(wǎng)絡(luò)方法 支持向量機(jī)方法集成學(xué)習(xí)方法回歸分析回歸分析可以對(duì)預(yù)測(cè)變量和響應(yīng)變量之間的聯(lián)系建模。在數(shù)據(jù)挖掘環(huán)境下，預(yù)測(cè)變量是描述樣本的感興趣的屬性，一般預(yù)測(cè)變量的值是已知的，響應(yīng)變量的值是我們要預(yù)測(cè)的。當(dāng)響應(yīng)變量和所有預(yù)測(cè)變量都是連續(xù)值時(shí)，回歸分析是一個(gè)好的選擇?；貧w分析包括：線性回歸、非線性回歸以及邏輯回歸等。3.2 決策樹分類方法3.2.1 決策樹的基本概念3.2.1 決策樹的基本概念決策樹(Dec

4、ision Tree)是一種樹型結(jié)構(gòu)，包括：決策節(jié)點(diǎn)(內(nèi)部節(jié)點(diǎn))、分支和葉節(jié)點(diǎn)三個(gè)部分。其中：決策節(jié)點(diǎn)代表某個(gè)測(cè)試，通常對(duì)應(yīng)于待分類對(duì)象的某個(gè)屬性，在該屬性上的不同測(cè)試結(jié)果對(duì)應(yīng)一個(gè)分支。葉節(jié)點(diǎn)存放某個(gè)類標(biāo)號(hào)值，表示一種可能的分類結(jié)果。分支表示某個(gè)決策節(jié)點(diǎn)的不同取值。決策樹可以用來對(duì)未知樣本進(jìn)行分類，分類過程如下：從決策樹的根節(jié)點(diǎn)開始，從上往下沿著某個(gè)分支往下搜索，直到葉結(jié)點(diǎn)，以葉結(jié)點(diǎn)的類標(biāo)號(hào)值作為該未知樣本所屬類標(biāo)號(hào)。 典型決策樹決策樹分類例題演示1某銀行訓(xùn)練數(shù)據(jù)下表， 請(qǐng)利用決策樹分類方法預(yù)測(cè)類標(biāo)號(hào)未知的新樣本“是”,“500010000”,“10是不流失否20000300002不是流失首先

5、，建立決策樹然后，使用決策樹對(duì)未知新樣本分類：未知樣本：“是”,“500010000”,“2”,“是”,？決策樹分類例題演示2categoricalcategoricalcontinuousclass訓(xùn)練數(shù)據(jù)集決策樹模型有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorced 80K應(yīng)用模型測(cè)試數(shù)據(jù)有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)Start from the root of tree.有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorc

6、ed 80K測(cè)試數(shù)據(jù)應(yīng)用模型測(cè)試數(shù)據(jù)有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorced 80K應(yīng)用模型測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorced 80K應(yīng)用模型測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorced 80K應(yīng)用模型測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)有房者婚姻狀態(tài)年收入YESNONONOYesNoMarried Single, Divorced 80K分配拖欠房款屬性為： “No”應(yīng)用模型測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)3.2.2 決策樹的構(gòu)

7、建決策樹在構(gòu)建過程中需重點(diǎn)解決2個(gè)問題：(1)如何選擇合適的屬性作為決策樹的節(jié)點(diǎn)去劃分訓(xùn)練樣本；(2)如何在適當(dāng)位置停止劃分過程，從而得到大小合適的決策樹。1.決策樹的屬性選擇雖然可以采用任何一個(gè)屬性對(duì)數(shù)據(jù)集進(jìn)行劃分，但最后形成的決策樹會(huì)差異很大。需要尋找合適的屬性選擇方法。屬性選擇是決策樹算法中重要的步驟，常見的屬性選擇標(biāo)準(zhǔn)包括信息增益(information gain)和Gini系數(shù)。信息增益是決策樹常用的分枝準(zhǔn)則,在樹的每個(gè)結(jié)點(diǎn)上選擇具有最高信息增益的屬性作為當(dāng)前結(jié)點(diǎn)的劃分屬性。Gini系數(shù)是一種不純度函數(shù)，用來度量數(shù)據(jù)集的數(shù)據(jù)關(guān)于類的純度。2.獲得大小合適的樹決策樹學(xué)習(xí)的目的是希望生成

8、能夠揭示數(shù)據(jù)集結(jié)構(gòu)并且預(yù)測(cè)能力強(qiáng)的一棵樹，在樹完全生長(zhǎng)的時(shí)候有可能預(yù)測(cè)能力反而降低，為此通常需要獲得大小合適的樹。一般來說有兩種獲取方法:一種為定義樹的停止生長(zhǎng)條件,常見條件包括最小劃分實(shí)例數(shù)、劃分閾值和最大樹深度等。另一種方法是對(duì)完全生長(zhǎng)決策樹進(jìn)行剪枝，方法是對(duì)決策樹的子樹進(jìn)行評(píng)估，若去掉該子樹后整個(gè)決策樹表現(xiàn)更好，則該子樹將被剪枝。3.決策樹構(gòu)建的經(jīng)典算法Hunt算法是許多經(jīng)典決策樹算法如ID3、C4.5的基礎(chǔ)Hunt算法對(duì)決策樹的建立過程描述如下，假定Dt是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集，C=C1,C2,Cm是類標(biāo)號(hào)，Hunt算法的遞歸定義如下：(1)如果Dt中所有記錄都屬于同一個(gè)類Ci(1

9、im),那么t是葉結(jié)點(diǎn)，用類標(biāo)號(hào)Ci進(jìn)行標(biāo)記。(2)如果Dt包含屬于多個(gè)類的記錄,則選擇一個(gè)屬性測(cè)試條件，將記錄劃分為更小的子集。對(duì)于測(cè)試條件的每個(gè)輸出，創(chuàng)建一個(gè)子女節(jié)點(diǎn)，并根據(jù)測(cè)試結(jié)果將Dt中的記錄分布到子女節(jié)點(diǎn)中，然后對(duì)每個(gè)子女節(jié)點(diǎn)遞歸調(diào)用該算法。3.2.3 ID3分類算法DI3分類算法概述ID3分類算法由Quinlan于1986年提出它使用信息增益(information gain)作為屬性的選擇標(biāo)準(zhǔn)。首先檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一個(gè)類別的數(shù)據(jù)為止。最后得到一

10、棵決策樹，它可以用來對(duì)新的樣本進(jìn)行分類?；靖拍钆cID3分類算法相關(guān)的基本概念包括：信息熵信息增益信息熵熵(entropy,也稱信息熵)用來度量一個(gè)屬性的信息量。假定S為訓(xùn)練集，S的目標(biāo)屬性C具有m個(gè)可能的類標(biāo)號(hào)值，C=C1,C2,Cm，假定訓(xùn)練集S中，Ci在所有樣本中出現(xiàn)的頻率為 (i=1,2,3,m)，則該訓(xùn)練集S所包含的信息熵定義為：熵越小表示樣本對(duì)目標(biāo)屬性的分布越純，反之熵越大表示樣本對(duì)目標(biāo)屬性分布越混亂。 信息熵例題演示考慮數(shù)據(jù)集weather如下, 求weather數(shù)據(jù)集關(guān)于目標(biāo)屬性play ball的熵。outlooktemperaturehumiditywindplay bal

11、lsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormal weakyesraincoolnormal strongnoovercastcoolnormal strongyessunnymildhighweaknosunnycoolnormal weakyesrain mildnormal weakyes sunnymildnormal strongyesovercastmildhighstrongyesovercasthotnormal weakyesrainmi

12、ldhighstrongno信息熵例題演示(續(xù))解答：令weather數(shù)據(jù)集為S，其中有14個(gè)樣本,目標(biāo)屬性play ball有2個(gè)值C1=yes, C2=no。14個(gè)樣本的分布為：9個(gè)樣本的類標(biāo)號(hào)取值為yes，5個(gè)樣本的類標(biāo)號(hào)取值為No。C1=yes在所有樣本S中出現(xiàn)的概率為9/14，C2=no在所有樣本S中出現(xiàn)的概率為5/14。因此數(shù)據(jù)集S的熵為：信息增益信息增益是劃分前樣本數(shù)據(jù)集的不純程度(熵)和劃分后樣本數(shù)據(jù)集的不純程度(熵)的差值。假設(shè)劃分前樣本數(shù)據(jù)集為S,并用屬性A來劃分樣本集S，則按屬性A劃分S的信息增益Gain(S,A)為樣本集S的熵減去按屬性A劃分S后的樣本子集的熵：按屬性A

13、劃分S后的樣本子集的熵定義如下：假定屬性A有k個(gè)不同的取值，從而將S劃分為k個(gè)樣本子集S1,S2,Sk，則按屬性A劃分S后的樣本子集的信息熵為:其中|Si|(i,=1,2,k)為樣本子集Si中包含的樣本數(shù)，|S|為樣本集S中包含的樣本數(shù)。信息增益越大，說明使用屬性A劃分后的樣本子集越純，越有利于分類。信息增益例題演示以數(shù)據(jù)集weather為例，設(shè)該數(shù)據(jù)集為S，假定用屬性wind來劃分S，求S對(duì)屬性wind的信息增益。 outlooktemperaturehumiditywindplay ballsunnyhothighweaknosunnyhothighstrongnoovercasthoth

14、ighweakyesrainmildhighweakyesraincoolnormal weakyesraincoolnormal strongnoovercastcoolnormal strongyessunnymildhighweaknosunnycoolnormal weakyesrain mildnormal weakyes sunnymildnormal strongyesovercastmildhighstrongyesovercasthotnormal weakyesrainmildhighstrongno信息增益例題演示(續(xù))解答：(1)首先由前例計(jì)算得到數(shù)據(jù)集S的熵值為0.9

15、4；(2)屬性wind有2個(gè)可能的取值weak,strong，它將S劃分為2個(gè)子集：S1,S2,S1為wind屬性取值為weak的樣本子集，共有8個(gè)樣本；S2為wind屬性取值為strong的樣本子集，共有6個(gè)樣本；下面分別計(jì)算樣本子集S1和S2的熵。信息增益例題演示(續(xù))對(duì)樣本子集S1，play ball=yes的有6個(gè)樣本，play ball=no的有2個(gè)樣本，則：對(duì)樣本子集S2，play ball=yes的有3個(gè)樣本，play ball=no的有3個(gè)樣本，則：信息增益例題演示(續(xù))利用屬性wind劃分S后的熵為：按屬性wind劃分?jǐn)?shù)據(jù)集S所得的信息增益值為：ID3算法偽代碼函數(shù)：DT(S

16、,F)輸入：訓(xùn)練集數(shù)據(jù)S，訓(xùn)練集數(shù)據(jù)屬性集合F輸出：ID3決策樹(1)if 樣本S全部屬于同一個(gè)類別C then(2) 創(chuàng)建一個(gè)葉結(jié)點(diǎn)，并標(biāo)記類標(biāo)號(hào)為C；(3) return；(4)else(5) 計(jì)算屬性集F中每一個(gè)屬性的信息增益，假定增益值最大的屬性為A；(6) 創(chuàng)建結(jié)點(diǎn)，取屬性A為該結(jié)點(diǎn)的決策屬性；(7) for 結(jié)點(diǎn)屬性A的每個(gè)可能的取值V do(8) 為該結(jié)點(diǎn)添加一個(gè)新的分支，假設(shè)SV為屬性A取值為V的樣本子集；(9) if 樣本SV全部屬于同一個(gè)類別C then(10) 為該分支添加一個(gè)葉結(jié)點(diǎn)，并標(biāo)記類標(biāo)號(hào)為C；(11) else(12) 遞歸調(diào)用DT(SV, F-A)，為該分支創(chuàng)

17、建子樹；(13) end if(11) end for(12)end ifID3建樹算法演示以weather數(shù)據(jù)集為例，講解ID3的建立過程。outlooktemperaturehumiditywindplay ballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormal weakyesraincoolnormal strongnoovercastcoolnormal strongyessunnymildhighweaknosunnycoolnormal wea

18、kyesrain mildnormal weakyes sunnymildnormal strongyesovercastmildhighstrongyesovercasthotnormal weakyesrainmildhighstrongno數(shù)據(jù)集的構(gòu)成數(shù)據(jù)集具有屬性：outlook, temperature, humidity, wind. outlook = sunny, overcast, rain temperature = hot, mild, cool humidity = high, normal wind = weak, strong ID3建立決策樹首先計(jì)算總數(shù)據(jù)集S對(duì)所

19、有屬性的信息增益，尋找根節(jié)點(diǎn)的最佳分裂屬性:Gain(S, outlook) = 0.246Gain(S, temperature) = 0.029Gain(S, humidity) = 0.152Gain(S, wind) = 0.049 顯然，這里outlook屬性具有最高信息增益值，因此將它選為根結(jié)點(diǎn). ID3建立決策樹(續(xù))以outlook做為根結(jié)點(diǎn)，繼續(xù)往下：思想是，以outlook的可能取值建立分支，對(duì)每個(gè)分支遞歸建立子樹。因?yàn)閛utlook有3個(gè)可能值,因此對(duì)根結(jié)點(diǎn)建立3個(gè)分支sunny, overcast, rain.那么，哪個(gè)屬性用來最佳劃分根結(jié)點(diǎn)的Sunny分支？overc

20、ast分支？Rain分支？outlooksunnyovercastrain?ID3建立決策樹(續(xù))首先對(duì)outlook的sunny分支建立子樹。找出數(shù)據(jù)集中outlook = sunny的樣本子集Soutlook=sunny，然后依次計(jì)算剩下三個(gè)屬性對(duì)該樣本子集Ssunny劃分后的信息增益：Gain(Ssunny, humidity) = 0.971Gain(Ssunny, temperature) = 0.571Gain(Ssunny, wind) = 0.371顯然humidity具有最高信息增益值，因此它被選為outlook結(jié)點(diǎn)下sunny分支下的決策結(jié)點(diǎn)。outlooksunnyove

21、rcastrain?HumidityID3建立決策樹(續(xù))采用同樣的方法，依次對(duì)outlook的overcast分支、rain分支建立子樹，最后得到一棵可以預(yù)測(cè)類標(biāo)號(hào)未知的樣本的決策樹。ID3決策樹對(duì)未知樣本進(jìn)行預(yù)測(cè)下面利用決策樹對(duì)類標(biāo)號(hào)未知的樣本X進(jìn)行預(yù)測(cè)：X=rain, hot, normal, weak, ?ID3算法總結(jié)ID3算法是所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。ID3搜索的假設(shè)空間是可能的決策樹的集合，搜索目的是構(gòu)造與訓(xùn)練數(shù)據(jù)一致的一棵決策樹，搜索策略是爬山法，在構(gòu)造決策樹時(shí)從簡(jiǎn)單到復(fù)雜，用信息熵作為爬山法的評(píng)價(jià)函數(shù)。ID3算法的核心是在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性，

22、用信息增益作為屬性選擇的標(biāo)準(zhǔn)，使得在每個(gè)非葉節(jié)點(diǎn)進(jìn)行測(cè)試時(shí)能獲得關(guān)于被測(cè)數(shù)據(jù)最大的類別信息，使得該屬性將數(shù)據(jù)集分成子集后，系統(tǒng)的熵值最小。ID3算法優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：理論清晰，方法簡(jiǎn)單，學(xué)習(xí)能力較強(qiáng)。缺點(diǎn)：(1)算法只能處理分類屬性數(shù)據(jù)，無(wú)法處理連續(xù)型數(shù)據(jù)；(2)算法對(duì)測(cè)試屬性的每個(gè)取值相應(yīng)產(chǎn)生一個(gè)分支，且劃分相應(yīng)的數(shù)據(jù)樣本集,這樣的劃分會(huì)導(dǎo)致產(chǎn)生許多小的子集。隨著子集被劃分得越來越小，劃分過程將會(huì)由于子集規(guī)模過小所造成的統(tǒng)計(jì)特征不充分而停止；(3)ID3算法中使用信息增益作為決策樹節(jié)點(diǎn)屬性選擇的標(biāo)準(zhǔn)，由于信息增益在類別值多的屬性上計(jì)算結(jié)果大于類別值少的屬性上計(jì)算結(jié)果，這將導(dǎo)致決策樹算法偏向選擇

23、具有較多分枝的屬性，因而可能導(dǎo)致過度擬合。在極端的情況下，如果某個(gè)屬性對(duì)于訓(xùn)練集中的每個(gè)元組都有唯一的一個(gè)值，則認(rèn)為該屬性是最好的，這是因?yàn)閷?duì)于每個(gè)劃分都只有一個(gè)元組(因此也是一類)。3.2.4 C4.5分類算法基于ID3算法中存在的不足，Quinlan于1993年對(duì)其做出改進(jìn)，提出了改進(jìn)的決策樹分類算法C4.5，該算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾個(gè)方面對(duì)ID3算法進(jìn)行了改進(jìn)：(1)能夠處理連續(xù)型屬性數(shù)據(jù)和離散型屬性數(shù)據(jù)；(2)能夠處理具有缺失值的數(shù)據(jù)；(3)使用信息增益率作為決策樹的屬性選擇標(biāo)準(zhǔn)；(4)對(duì)生成的樹進(jìn)行剪枝處理，以獲取簡(jiǎn)略的決策樹；(5)從決策樹到規(guī)則的自動(dòng)產(chǎn)生。C4.5

24、算法的概念描述假定S為訓(xùn)練集，目標(biāo)屬性C具有m個(gè)可能的取值，C=C1,C2,Cm，即訓(xùn)練集S的目標(biāo)屬性具有m個(gè)類標(biāo)號(hào)值C1,C2,Cm，C4.5算法所涉及的概念描述如下：(1)假定訓(xùn)練集S中，Ci在所有樣本中出現(xiàn)的頻率為pi(i=1,2,3,m)，則該集合S所包含的信息熵為：C4.5算法的概念描述(續(xù))(2)設(shè)用屬性A來劃分S中的樣本,計(jì)算屬性A對(duì)集合S的劃分熵值EntropyA(S)定義如下:若屬性A為離散型數(shù)據(jù)，并具有k個(gè)不同的取值,則屬性A依據(jù)這k個(gè)不同取值將S劃分為k個(gè)子集S1,S2,Sk，屬性A劃分S的信息熵為：其中|Si|和|S|分別是Si和S中包含的樣本個(gè)數(shù)。C4.5算法的概念描

25、述(續(xù))如果屬性A為連續(xù)型數(shù)據(jù)，則按屬性A的取值遞增排序，將每對(duì)相鄰值的中點(diǎn)看作可能的分裂點(diǎn)，對(duì)每個(gè)可能的分裂點(diǎn)，計(jì)算：其中SL和SR分別對(duì)應(yīng)于該分裂點(diǎn)劃分的左右兩部分子集，選擇EntropyA(S)值最小的分裂點(diǎn)作為屬性A的最佳分裂點(diǎn)，并以該最佳分裂點(diǎn)按屬性A對(duì)集合S的劃分熵值作為屬性A劃分S的熵值。C4.5算法的概念描述(續(xù))(3) C4.5以信息增益率作為選擇標(biāo)準(zhǔn)，不僅考慮信息增益的大小程度，還兼顧為獲得信息增益所付出的“代價(jià)”：C4.5通過引入屬性的分裂信息來調(diào)節(jié)信息增益，分裂信息定義為信息增益率定義為這樣如果某個(gè)屬性有較多的分類取值，則它的信息熵會(huì)偏大，但信息增益率由于考慮了分裂信息

26、而降低，進(jìn)而消除了屬性取值數(shù)目所帶來的影響。 C4.5算法演示以weather數(shù)據(jù)集為例，演示C4.5算法對(duì)該數(shù)據(jù)集進(jìn)行訓(xùn)練，建立一棵決策樹的過程，對(duì)未知樣本進(jìn)行預(yù)測(cè)。Step1:計(jì)算所有屬性劃分?jǐn)?shù)據(jù)集S所得的信息增益分別為(參考ID3例題演示): Step2:計(jì)算各個(gè)屬性的分裂信息和信息增益率以outlook屬性為例，取值為overcast的樣本有4條，取值為rain的樣本有5條，取值為sunny的樣本有5條：同理依次計(jì)算其它屬性的信息增益率分別如下：Step3:取值信息增益率最大的那個(gè)屬性作為分裂結(jié)點(diǎn)，因此最初選擇outlook屬性作為決策樹的根結(jié)點(diǎn)，產(chǎn)生3個(gè)分支，如下：Step4:對(duì)根結(jié)

27、點(diǎn)的不同取值的分支，遞歸調(diào)用以上方法，求子樹，最后通過C4.5獲得的決策樹為：C4.5對(duì)缺失數(shù)據(jù)的處理由于決策樹中節(jié)點(diǎn)的測(cè)試輸出決定于單個(gè)屬性的不同取值，當(dāng)訓(xùn)練集或測(cè)試集中的某個(gè)樣本數(shù)據(jù)的測(cè)試屬性值未知，就無(wú)法得到當(dāng)前節(jié)點(diǎn)的測(cè)試輸出，因此ID3算法不允許訓(xùn)練集和測(cè)試集中存在缺失數(shù)據(jù)。對(duì)數(shù)據(jù)缺失值的處理，通常有兩種方法：方法一：拋棄數(shù)據(jù)集中具有缺失值的數(shù)據(jù)。當(dāng)數(shù)據(jù)集中只有少量缺失值數(shù)據(jù)的情況下，可以拋棄具有缺失值的數(shù)據(jù)，但是當(dāng)數(shù)據(jù)集中存在大量缺失值時(shí)不能采用這種方法。方法二：以某種方式填充缺失的數(shù)據(jù)。如以該屬性中最常見值或平均值替代該缺失值，或者以與缺失值樣本所對(duì)應(yīng)的類標(biāo)號(hào)屬性值相同的樣本中該缺

28、失值屬性的最常見值或平均值來代替。在C4.5算法中采用概率的方法，為缺失值的每個(gè)可能值賦予一個(gè)概率，而不是簡(jiǎn)單地將最常見的值替代該缺失值。C4.5算法偽代碼C4.5決策樹的建立過程可以分為兩個(gè)過程：首先使用訓(xùn)練集數(shù)據(jù)依據(jù)C4.5樹生長(zhǎng)算法構(gòu)建一棵完全生長(zhǎng)的決策樹然后對(duì)樹進(jìn)行剪枝，最后得到一棵最優(yōu)決策樹。C4.5決策樹的生長(zhǎng)階段算法偽代碼 函數(shù)名：CDT(S,F)輸入：訓(xùn)練集數(shù)據(jù)S，訓(xùn)練集數(shù)據(jù)屬性集合F輸出：一棵未剪枝的C4.5決策樹(1)if 樣本S全部屬于同一個(gè)類別C then(2) 創(chuàng)建一個(gè)葉結(jié)點(diǎn)，并標(biāo)記類標(biāo)號(hào)為C；(3) return；(4)else(5) 計(jì)算屬性集F中每一個(gè)屬性的信息

29、增益率，假定增益率值最大的屬性為A；(6) 創(chuàng)建結(jié)點(diǎn)，取屬性A為該結(jié)點(diǎn)的決策屬性；(7) for 結(jié)點(diǎn)屬性A的每個(gè)可能的取值V do(8) 為該結(jié)點(diǎn)添加一個(gè)新的分支, 假設(shè)SV為屬性A取值為V的樣本子集；(9) if 樣本SV全部屬于同一個(gè)類別C then(10) 為該分支添加一個(gè)葉結(jié)點(diǎn)，并標(biāo)記為類標(biāo)號(hào)為C；(11) else(12) 則遞歸調(diào)用CDT(SV ,F-A)，為該分支創(chuàng)建子樹；(13) end if(14) end for(15)end ifC4.5決策樹的剪枝處理階段算法偽代碼函數(shù)名：Prune(node)輸入：待剪枝子樹node輸出：剪枝后的子樹 (1)計(jì)算待剪子樹node中葉

30、節(jié)點(diǎn)的加權(quán)估計(jì)誤差leafError；(2)if 待剪子樹node是一個(gè)葉節(jié)點(diǎn) then(3) return 葉節(jié)點(diǎn)誤差；(4)else(5) 計(jì)算node的子樹誤差subtreeError；(6) 計(jì)算node的分支誤差branchError為該節(jié)點(diǎn)中頻率最大一個(gè)分支誤差(7) if leafError小于branchError和subtreeError then(8) 剪枝，設(shè)置該節(jié)點(diǎn)為葉節(jié)點(diǎn)；(9) error=leafError；(10) else if branchError小于leafError和subtreeError then(11) 剪枝，以該節(jié)點(diǎn)中頻率最大那個(gè)分支替換該節(jié)點(diǎn)

31、；(12) error=branchError;(13) else(14) 不剪枝(15) error=subtreeError;(16) return error;(17) end if(18)end ifC4.5算法的優(yōu)缺點(diǎn)與其它分類算法相比，C4.5分類算法具有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留與內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。為適應(yīng)大規(guī)模數(shù)據(jù)集，在C4.5后出現(xiàn)有SLIQ和SPRINT等算法。 3.4.5 CART算法CART(Clas

32、sification and Regression Tree)算法，由美國(guó)斯坦福大學(xué)和加州大學(xué)伯克利分校的Breiman等人于1984年提出。CART決策樹采用的是二元遞歸劃分方法，能夠處理連續(xù)屬性數(shù)據(jù)和標(biāo)稱屬性作為預(yù)測(cè)變量和目標(biāo)變量下的分類，當(dāng)輸出變量是標(biāo)稱屬性數(shù)據(jù)時(shí)，所建立的決策樹稱為分類樹(classification tree)，用于分類的預(yù)測(cè)。當(dāng)輸出變量為數(shù)值型變量時(shí)，所建立的決策樹稱為回歸樹(regression tree)，用于數(shù)值的預(yù)測(cè)。3.4.5 CART算法與C4.5相比，CART算法的主要差別體現(xiàn)在：(1)CART為二叉樹，而C4.5可以為多叉樹。(2)CART中的輸入變

33、量和輸出變量可以是分類型也可以是數(shù)值型，而C4.5的輸出變量只能是分類型。(3)CART使用Gini系數(shù)作為變量的不純度量，而C4.5使用信息增益率。(4)如果目標(biāo)變量是標(biāo)稱的，并且具有兩個(gè)以上的類別，則CART可能考慮將目標(biāo)類別合并成兩個(gè)超類別。(5)如果目標(biāo)變量是連續(xù)的，則CART算法找出一組基于樹的回歸方程來預(yù)測(cè)目標(biāo)變量。(6)對(duì)于缺失值的處理方法不同，CART采用代理測(cè)試(surrogate)來估計(jì)測(cè)試的輸出值，而C4.5直接將其分配到該分支中概率最大的分類。 (7)對(duì)決策樹的剪枝方法不同。CART算法的基本概念分類回歸樹的建樹過程是對(duì)訓(xùn)練集的反復(fù)劃分的過程，涉及如何從多個(gè)屬性中選擇當(dāng)

34、前最佳劃分屬性的問題。另外針對(duì)CART的分類樹和回歸樹，它們的計(jì)算方法有所不同，數(shù)值型和分類型屬性變量的計(jì)算法方法也存在差異。下面介紹CART算法的兩個(gè)基本概念：屬性選擇標(biāo)準(zhǔn)分類樹與回歸樹的屬性選擇屬性選擇標(biāo)準(zhǔn)ID3使用信息增益作為屬性選擇標(biāo)準(zhǔn)，C4.5使用信息增益率作為屬性選擇標(biāo)準(zhǔn)。CART算法使用Gini系數(shù)來度量對(duì)某個(gè)屬性變量測(cè)試輸出的兩組取值的差異性，理想的分組應(yīng)該盡量使兩組中樣本輸出變量取值的差異性總和達(dá)到最小，即“純度”最大，也就是使兩組輸出變量取值的差異性下降最快，“純度”增加最快。設(shè)t為分類回歸樹中的某個(gè)節(jié)點(diǎn)，稱函數(shù)：為Gini系數(shù),k為當(dāng)前屬性下測(cè)試輸出的類別數(shù)，p(j|t)

35、為節(jié)點(diǎn)t中樣本測(cè)試輸出取類別j的概率。 屬性選擇標(biāo)準(zhǔn)(續(xù))設(shè)t為一個(gè)節(jié)點(diǎn)，為該節(jié)點(diǎn)的一個(gè)屬性分枝條件，該分枝條件將節(jié)點(diǎn)t中樣本分別分到左分支SL和右分支SR中，稱： 為在分枝條件下節(jié)點(diǎn)t的差異性損失。其中，G(t)為劃分前測(cè)試輸出的Gini系數(shù)，|SR|和|SL|分別表示劃分后左右分枝的樣本個(gè)數(shù)。為使節(jié)點(diǎn)t盡可能的純，我們需選擇某個(gè)屬性分枝條件使該節(jié)點(diǎn)的差異性損失盡可能大。用(t)表示所考慮的分枝條件的全體，則選擇分枝條件應(yīng)為：屬性選擇分類樹的屬性選擇對(duì)于CART分類樹的屬性選擇，針對(duì)屬性類型為分類型和數(shù)值型，方法有所不同。對(duì)于分類型屬性，由于CART只能建立二叉樹，對(duì)于取多個(gè)值的屬性變量，需

36、要將多類別合并成兩個(gè)類別，形成“超類”，然后計(jì)算兩“超類”下樣本測(cè)試輸出取值的差異性。對(duì)于數(shù)值型屬性，方法是將數(shù)據(jù)按升序排序，然后從小到大依次以相鄰數(shù)值的中間值作為分隔，將樣本分為兩組，并計(jì)算所得組中樣本測(cè)試輸出取值的差異性。理想的分組是使兩組中樣本測(cè)試輸出取值的差異性總和達(dá)到最小，即“純度”最大，也就是使兩組輸出變量取值的差異性下降最快，“純度”增加最快。屬性選擇回歸樹的屬性選擇回歸樹確定當(dāng)前最佳分組變量的策略與分類樹相同，主要不同在于度量節(jié)點(diǎn)測(cè)試輸出值差異性的指標(biāo)有所不同，采用方差作為指標(biāo)，其定義為：其中，t為節(jié)點(diǎn)，N為節(jié)點(diǎn)t所含的樣本個(gè)數(shù)，yi(t)為節(jié)點(diǎn)t中測(cè)試輸出變量值， 為節(jié)點(diǎn)t中

37、測(cè)試輸出變量的平均值。于是，差異性損失的度量指標(biāo)為方差的減少量，其定義為：其中，R(t)和N分別為分組前輸出變量的方差和樣本個(gè)數(shù)，R(tR)、NR和R(tL)、NL分別為分組后右子樹的方差和樣本量以及左子樹的方差和樣本量。使達(dá)到最大的屬性變量為當(dāng)前最佳劃分屬性變量。CART算法描述函數(shù)名：CART(S,F)輸入：樣本集數(shù)據(jù)S，訓(xùn)練集數(shù)據(jù)屬性集合F輸出：CART樹(1)if 樣本S全部屬于同一個(gè)類別C，then(2) 創(chuàng)建一個(gè)葉結(jié)點(diǎn)，并標(biāo)記類標(biāo)號(hào)為C；(3) return;(4)else(4) 計(jì)算屬性集F中每一個(gè)屬性劃分的差異性損失，假定差異性損失最大的屬性為A；(5) 創(chuàng)建結(jié)點(diǎn)，取屬性A為該

38、結(jié)點(diǎn)的決策屬性；(6) 以屬性A劃分S得到S1和S2兩個(gè)子集； (7) 遞歸調(diào)用CART(S1 ,F)；(8) 遞歸調(diào)用CART(S2 ,F)；(9)end 3.3 貝葉斯分類方法貝葉斯分類方法是一種基于統(tǒng)計(jì)的學(xué)習(xí)方法。是一種利用概率統(tǒng)計(jì)知識(shí)進(jìn)行學(xué)習(xí)分類的方法。如：預(yù)測(cè)一個(gè)數(shù)據(jù)對(duì)象屬于某個(gè)類別的概率。如：計(jì)算郵件是垃圾郵件或合法郵件的概率，取概率大的為預(yù)測(cè)結(jié)果主要算法有：樸素貝葉斯分類算法貝葉斯信念網(wǎng)絡(luò)分類算法等。樸素貝葉斯分類算法和貝葉斯信念網(wǎng)絡(luò)分類算法都是建立在貝葉斯定理基礎(chǔ)上的算法假定X為類標(biāo)號(hào)未知的一個(gè)數(shù)據(jù)樣本，H為樣本X屬于類別C的一個(gè)假設(shè)分類問題就是計(jì)算概率P(H|X) 的問題，即

39、給定觀察樣本X下假設(shè)H成立的概率有多大。這里：P(H)表示假設(shè)H的先驗(yàn)概率(prior probability)。P(X)表示樣本數(shù)據(jù)X的先驗(yàn)概率。P(H|X)表示在條件X下，假設(shè)H的后驗(yàn)概率(posterior probability)。P(X|H)表示在給定假設(shè)H的前提條件下，樣本X的后驗(yàn)概率3.3.1 貝葉斯定理例:假設(shè)數(shù)據(jù)集由三個(gè)屬性構(gòu)成：年齡、收入、是否購(gòu)買計(jì)算機(jī)樣本X為：35, 4000, ?假設(shè)H為：顧客將購(gòu)買計(jì)算機(jī)。則：P(H)表示任意給定的顧客將購(gòu)買計(jì)算機(jī)的概率，而不考慮年齡、收入其它信息。P(X)表示數(shù)據(jù)集中，樣本年齡為35，工資為4000的概率。P(H|X)表示已知顧客的

40、年齡和收入分別為35和4000，顧客購(gòu)買計(jì)算機(jī)的概率。P(X|H)表示已知顧客購(gòu)買計(jì)算機(jī)，顧客年齡和收入屬性值為35和4000的概率。 貝葉斯定理(續(xù))假設(shè)X,Y是一對(duì)隨機(jī)變量，它們的：聯(lián)合概率P（X=x,Y=y）是指X取值x且Y取值y的概率條件概率是指一隨機(jī)變量在另一隨機(jī)變量取值已知的情況下取某一個(gè)特定值的概率。例如P(Y=y|X=x）是指在變量X取值x的情況下，變量Y取值y的概率)。貝葉斯定理是指X和Y的聯(lián)合概率和條件概率滿足如下關(guān)系：例：考慮A和B兩隊(duì)之間的足球比賽：假設(shè)過去的比賽中，65%的比賽A對(duì)取勝，35%的比賽B對(duì)取勝。A對(duì)勝的比賽中只有30%是在B對(duì)的主場(chǎng)，B對(duì)取勝的比賽中75

41、%是在主場(chǎng)。如果下一場(chǎng)比賽在B對(duì)的主場(chǎng)進(jìn)行，請(qǐng)預(yù)測(cè)哪支球隊(duì)最有可能勝出？解答：根據(jù)貝葉斯定理,假定隨機(jī)變量X代表東道主，X取值范圍為A,B隨機(jī)變量Y代表比賽的勝利者，取值范圍為A,B。已知：A對(duì)取勝的概率為0.65，表示為：P(Y=A)=0.65，B對(duì)取勝的概率為0.35 ，表示為：P(Y=B)=0.35，B對(duì)取勝時(shí)作為東道主的概率是0.75，表示為：P(X=B|Y=B) = 0.75,A對(duì)取勝時(shí)B對(duì)作為東道主的概率是0.3,表示為:P(X=B|Y=A) = 0.3,計(jì)算：下一場(chǎng)比賽在B對(duì)主場(chǎng)，同時(shí)A對(duì)勝出的概率表示為：P(Y=A|X=B)P(Y=A|X=B) = P(X=B|Y=A)*P(Y

42、=A)/P(X=B) = (0.3*0.65)/0.4575=0.4262下一場(chǎng)比賽在B對(duì)主場(chǎng)，同時(shí)B對(duì)勝出的概率表示為：P(Y=B|X=B)P(Y=B|X=B)=P(X=B|Y=B)*P(Y=B)/P(X=B) =(0.75*0.35)/0.4575=0.5737根據(jù)計(jì)算結(jié)果，可以推斷出，下一場(chǎng)最有可能是B對(duì)勝出。 P(X=B)的計(jì)算 ：P(X=B)= P(X=B,Y=A)+P(X=B,Y=B) = P(Y=A|X=B)*P(X=B) + P(Y=B|X=B)*P(X=B) = P(X=B|Y=A)*P(Y=A) + P(X=B|Y=B)*P(Y=B) = 0.3*0.65+0.75*0.3

43、5=0.195+0.2625 = 0.4575 3.3.2 樸素貝葉斯分類算法樸素貝葉斯分類算法，即：Nave Bayes 樸素貝葉斯分類算法利用貝葉斯定理來預(yù)測(cè)一個(gè)未知類別的樣本屬于各個(gè)類別的可能性，選擇其中可能性最大的一個(gè)類別作為該樣本的最終類別。樸素貝葉斯分類算法(續(xù))設(shè)數(shù)據(jù)集為D，對(duì)應(yīng)屬性集：A1,A2,An, CA1,A2,An是樣本的屬性變量，C是有m個(gè)取值C1,C2,.,Cm的類標(biāo)號(hào)屬性變量。數(shù)據(jù)集D中的每個(gè)樣本X可以表示為X=x1,x2,xn,Ci樸素貝葉斯分類算法的概念描述如下：1)假定樸素貝葉斯分類器將未知樣本X分配給類Ci，則： 根據(jù)貝葉斯定理:由于P(X)對(duì)所有類為常數(shù)

44、，最大化后驗(yàn)概率P(Ci|X)可轉(zhuǎn)化為最大化先驗(yàn)概率P(X|Ci)P(Ci)。類的先驗(yàn)概率P(Ci)可以用si/s來估計(jì)，其中si是數(shù)據(jù)集D中屬于類Ci的樣本個(gè)數(shù)，s是數(shù)據(jù)集D的樣本總數(shù)樸素貝葉斯假定一個(gè)屬性值對(duì)給定類的影響?yīng)毩⒂谄渌麑傩灾?，屬性之間不存在依賴關(guān)系,這樣： 從數(shù)據(jù)集中求概率這里xk表示樣本X在屬性Ak下的取值。對(duì)于每個(gè)屬性，考察該屬性是分類的還是連續(xù)的。如果屬性Ak是分類屬性，則：P(xk|Ci)=sik/si，其中sik是D中屬性Ak的值為xk的Ci類的樣本個(gè)數(shù)，si是D中屬于Ci類的樣本個(gè)數(shù)。如果屬性Ak是連續(xù)值屬性，則通常假定該連續(xù)值屬性服從高斯分布，因而類別Ci下屬性x

45、k的類條件概率近似為：即 的最大值點(diǎn)等價(jià)于 的最大值點(diǎn)：這里的 和 分別是數(shù)據(jù)集中屬于Ci類的樣本屬性Ak的值的平均值和標(biāo)準(zhǔn)差。為對(duì)未知樣本X分類，對(duì)每個(gè)類Ci，計(jì)算P(X|Ci)，樣本X被指派到類別Ci中，當(dāng)且僅當(dāng): 即X被指派到最大的類別中樸素貝葉斯分類算法的基本描述函數(shù)名：NaiveBayes輸入：類標(biāo)號(hào)未知的樣本X=x1,x2,xn輸出：未知樣本X所屬類別號(hào)(1) for j=1 to m (2) 計(jì)算X屬于每一個(gè)類別Cj的概率；(3) 計(jì)算訓(xùn)練集中每個(gè)類別Cj的概率P(Cj)；(4) 計(jì)算概率值；(5) end for(6) 選擇計(jì)算概率值最大的Ci(1im)作為類別輸出。 樸素貝葉

46、斯分類算法演示對(duì)weather數(shù)據(jù)集使用樸素貝葉斯算法預(yù)測(cè)未知樣本X=rainy,hot,normal,false,?的play ball類標(biāo)號(hào)屬性的值。該問題描述如下：樣本X=rainy, hot, normal, false, ?類標(biāo)號(hào)play ball有2個(gè)取值yes, no題目即求:樣本X在play為yes的概率P(play=yes|X)和樣本在play為no的概率P(play=no|X)樣本X將被預(yù)測(cè)為概率值大的那個(gè)類。解：根據(jù)樸素貝葉斯定理：P(play=yes|X)=P(X|play=yes)*P(play=yes) =P(x1|play=yes)*P(x2|play=yes)*

47、P(x3|play=yes)*P(x4|play=yes)*P(play=yes)其中：P(x1|play=yes)=P(outlook=rainy|play=yes)=3/9P(x2|play=yes)=P(temperature=hot|play=yes)=2/9P(x3|play=yes)=P(humidity=normal|play=yes)=6/9P(x4|play=yes)=P(windy=false|play=yes)=6/9P(play=yes)=9/14因此：P(play=yes|X)=1/32/92/32/39/14=0.0211 同樣方法計(jì)算：P(play=no|X)=P

48、(X|play=no)*P(play=no) =P(x1|play=no)*P(x2|play=no)*P(x3|play=no)*P(x4|play=no)*P(play=no)其中：P(x1|play=no)=P(outlook=rainy|play=no)=2/5P(x2|play=no)=P(temperature=hot|play=no)=2/5P(x3|play=no)=P(humidity=normal|play=no)=1/5P(x4|play=no)=P(windy=false|play=no)=2/5P(play=no)=9/14因此：P(play=no|X)=2/52/5

49、1/52/59/14=0.0082 根據(jù)計(jì)算結(jié)果：P(play=yes|X) P(play=no|X)所以：樣本X=rainy,hot,normal,false,?的play類標(biāo)號(hào)值應(yīng)為yes.樸素貝葉斯分類算法在計(jì)算概率的時(shí)候存在概率為0及概率值可能很小的情況，因此在某些情況下需要考慮條件概率的Laplace估計(jì)以及解決小概率相乘溢出問題。1. 條件概率的Laplace估計(jì)在后驗(yàn)概率的計(jì)算過程中，當(dāng)有一個(gè)屬性的條件概率等于0，則整個(gè)類的后驗(yàn)概率就等于0，簡(jiǎn)單地使用記錄比例來估計(jì)類條件概率的方法顯得太脆弱，尤其是當(dāng)訓(xùn)練樣本很少而屬性數(shù)目很大的情況下。一種更極端的情況是，當(dāng)訓(xùn)練樣例不能覆蓋那么多

50、的屬性值時(shí)，我們可能無(wú)法分類某些測(cè)試記錄。例如：若P(outlook=overcast |play=no)為0而不是1/7,則具有屬性集X=(outlook=overcast，temperature=hot，humidity=normal，wind=weak)的記錄的類條件概率如下： 此時(shí)將導(dǎo)致無(wú)法計(jì)算獲取記錄X的類標(biāo)號(hào)信息。1. 條件概率的Laplace估計(jì)(續(xù))為避免這一問題，條件概率為零時(shí)一般采用Laplace估計(jì)來解決這個(gè)問題，Laplace估計(jì)定義如下：其中n是類Yj中的實(shí)例總數(shù)，nc是類Yj的訓(xùn)練樣例中取值為Xi的樣例數(shù)，l是稱為等價(jià)樣本大小的參數(shù)，而p是用戶指定的參數(shù)。如果沒有訓(xùn)

51、練集(即n=0)，則P(Xi|Yj)=p。因此p可以看作是在類Yj的記錄中觀察屬性值Xi的先驗(yàn)概率。等價(jià)樣本大小l決定先驗(yàn)概率p和觀測(cè)概率nc/n之間的概率。在前面的例子中，條件概率 P(outlook=overcast |play=no)=0.使用Laplace估計(jì)方法，l=5,p=1/5,則條件概率不再是0，而是P(outlook=overcast |play=no)=(0+51/5)/(5+5)=0.1。2. 解決溢出問題對(duì)于概率值 ，即使每一個(gè)乘積因子都不為零，但當(dāng)n較大時(shí)也可能幾乎為零，此時(shí)將難以區(qū)分不同類別。注意到以下兩個(gè)表達(dá)式取極大值的條件相同：為解決這一問題，將乘積的計(jì)算問題轉(zhuǎn)

52、化為加法計(jì)算問題，可以避免“溢出”。樸素貝葉斯分類算法的優(yōu)缺點(diǎn)樸素貝葉斯分類算法的優(yōu)點(diǎn)在于：容易實(shí)現(xiàn)在大多數(shù)情況下所獲得的結(jié)果比較好。缺點(diǎn)：算法成立的前提是假設(shè)各屬性之間互相獨(dú)立。當(dāng)數(shù)據(jù)集滿足這種獨(dú)立性假設(shè)時(shí)，分類準(zhǔn)確度較高。而實(shí)際領(lǐng)域中，數(shù)據(jù)集可能并不完全滿足獨(dú)立性假設(shè)3.4 K-最近鄰分類方法K-最近鄰分類算法是一種基于實(shí)例的學(xué)習(xí)算法，它不需要先使用訓(xùn)練樣本進(jìn)行分類器的設(shè)計(jì)，而是直接用訓(xùn)練集對(duì)數(shù)據(jù)樣本進(jìn)行分類，確定其類別標(biāo)號(hào)。K-最近鄰分類方法概述基本思想:如果它走路象鴨子，叫聲象鴨子，則它可能是一個(gè)鴨子訓(xùn)練集測(cè)試集K-最近鄰算法的基本思想是：對(duì)于未知類標(biāo)號(hào)的樣本，按照歐幾里得距離找出它在

53、訓(xùn)練集中的k個(gè)最近鄰，將未知樣本賦予k最近鄰中出現(xiàn)次數(shù)最多的類別號(hào)。K-最近鄰分類算法的基本描述令D為訓(xùn)練集，Z為測(cè)試集，K為最近鄰數(shù)目，其中每個(gè)樣本可以表示為(x,y)的形式，即 ，其中 表示樣本的n個(gè)屬性，y表示樣本的類標(biāo)號(hào)，則KNN分類算法的基本描述如下算法名：KNN輸入：最近鄰數(shù)目K ，訓(xùn)練集D，測(cè)試集Z輸出：對(duì)測(cè)試集Z中所有測(cè)試樣本預(yù)測(cè)其類標(biāo)號(hào)值(1)for 每個(gè)測(cè)試樣本 do(2) 計(jì)算z和每個(gè)訓(xùn)練樣本 之間的距離(3) 選擇離z最近的k最近鄰集合(4) 返回 中樣本的多數(shù)類的類標(biāo)號(hào)(5)end for K-最近鄰分類算法的基本描述(續(xù))kNN算法根據(jù)得到的最近鄰列表中樣本的多數(shù)類

54、進(jìn)行分類，實(shí)現(xiàn)方法是通過投票進(jìn)行多數(shù)表決得到最終類標(biāo)號(hào) ，其中：其中 為類標(biāo)號(hào)的所有可能取值， 是測(cè)試樣本z的一個(gè)最近鄰類標(biāo)號(hào)， 是指示函數(shù)，如果其參數(shù)為真，則返回1，否則返回0。 kNN算法演示 對(duì)weather數(shù)據(jù)集，利用KNN算法，測(cè)試樣本X=(rain, hot, normal, weak，?)的類標(biāo)號(hào)屬性，其中k取3。Step1:首先計(jì)算樣本X到14個(gè)記錄的距離(取定義4-3的曼哈頓距離)分別為： Distance(X,p1)=2, Distance(X,p2)=3，Distance(X,p3)=2，Distance(X,p4)=2，Distance(X,p5)=1，Distance

55、(X,p6)=2，Distance(X,p7)=3，Distance(X,p8)=3，Distance(X,p9)=2，Distance(X,p10)=1，Distance(X,p11)=3，Distance(X,p12)=1，Distance(X,p13)=1，Distance(X,p14)=3；Step2:取離樣本X最近的三個(gè)近鄰p5,p10,p13Step3:因?yàn)槿齻€(gè)最近鄰對(duì)應(yīng)的類標(biāo)號(hào)都為yes,因此樣本X的類標(biāo)號(hào)被預(yù)測(cè)為yes。 kNN算法演示(續(xù))KNN算法優(yōu)缺點(diǎn)優(yōu)點(diǎn)：算法思想簡(jiǎn)單，易于實(shí)現(xiàn)。缺點(diǎn)：最近鄰分類對(duì)每個(gè)屬性指定相同的權(quán)重。而數(shù)據(jù)集中的不同屬性可能需要賦予不同的權(quán)值；由于K

56、-NN存放所有的訓(xùn)練樣本，直到有新的樣本需要分類時(shí)才建立分類，因此當(dāng)訓(xùn)練樣本數(shù)量很大時(shí)，該學(xué)習(xí)算法的時(shí)間復(fù)雜度為n2。3.5 神經(jīng)網(wǎng)絡(luò)分類方法神經(jīng)網(wǎng)絡(luò)(Neural Network)是模擬人腦思維方式的數(shù)學(xué)模型，它是在現(xiàn)代生物學(xué)研究人腦組織成果的基礎(chǔ)上提出的，用來模擬人類大腦神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和行為。神經(jīng)網(wǎng)絡(luò)反映了人腦功能的基本特征，如并行信息處理、學(xué)習(xí)、聯(lián)想、模式分類、記憶等。典型神經(jīng)網(wǎng)絡(luò)模型神經(jīng)網(wǎng)絡(luò)模型性能主要由以下因素決定：(1)神經(jīng)元(信息處理單元)的特性；(2)神經(jīng)元之間相互連接的形式拓?fù)浣Y(jié)構(gòu)；(3)為適應(yīng)環(huán)境而改善性能的學(xué)習(xí)規(guī)則。目前神經(jīng)網(wǎng)絡(luò)模型的種類相當(dāng)豐富，已有40余種神經(jīng)網(wǎng)絡(luò)模型

57、。典型的有感知器模型、多層前向傳播網(wǎng)絡(luò)、BP模型、Hopfield網(wǎng)絡(luò)、ART網(wǎng)絡(luò)、SOM自組織網(wǎng)絡(luò)、學(xué)習(xí)矢量量化(LVQ)網(wǎng)絡(luò)、Blotzman機(jī)網(wǎng)絡(luò)等。感知器模型感知器神經(jīng)網(wǎng)絡(luò)是一個(gè)具有單層計(jì)算神經(jīng)元的神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的傳遞函數(shù)是線性閾值單元。原始的感知器神經(jīng)網(wǎng)絡(luò)只有一個(gè)神經(jīng)元，因此只能輸出兩個(gè)值，適合簡(jiǎn)單的模式分類問題。感知器模型圖如下：?jiǎn)螌痈兄骺蓪⑼獠枯斎敕譃閮深?。?dāng)感知器的輸出為+1時(shí)，輸入屬于L1類，當(dāng)感知器的輸出為-1時(shí)，輸入屬于L2類，從而實(shí)現(xiàn)兩類目標(biāo)的識(shí)別。感知器模型(續(xù))在多維空間，單層感知器進(jìn)行模式識(shí)別的判決超平面由下式?jīng)Q定：對(duì)于只有兩個(gè)輸入的判別邊界是直線,選擇合適的學(xué)

58、習(xí)算法可訓(xùn)練出滿意的 w1和w2，當(dāng)它用于兩類模式的分類時(shí)，相當(dāng)于在高維樣本空間中，用一個(gè)超平面將兩類樣本分開，即：w1x1+w2x2 +b=0 BP模型BP模型也稱反向傳播模型，是一種用于前向多層的反向傳播學(xué)習(xí)算法。學(xué)習(xí)方法：可以對(duì)組成前向多層網(wǎng)絡(luò)的各人工神經(jīng)元之間的連接權(quán)值進(jìn)行不斷的修改，從而使該前向多層網(wǎng)絡(luò)能夠?qū)⑤斎胄畔⒆儞Q成所期望的輸出信息。反向?qū)W習(xí)算法：在修改各人工神經(jīng)元的連接權(quán)值時(shí)，所依據(jù)的是該網(wǎng)絡(luò)的實(shí)際輸出與其期望輸出之差，將這一差值反向一層一層地向回傳播，來決定連接權(quán)值的修改。BP網(wǎng)絡(luò)如圖：BP模型的基本描述1)選擇一組訓(xùn)練樣例，每一個(gè)樣例由輸入信息和期望的輸出結(jié)果兩部分組成;

59、2)從訓(xùn)練樣例集中取一樣例，把輸入信息輸入到網(wǎng)絡(luò)中;3)分別計(jì)算經(jīng)神經(jīng)元處理后的各層節(jié)點(diǎn)的輸出;4)計(jì)算網(wǎng)絡(luò)的實(shí)際輸出和期望輸出的誤差;5)從輸出層反向計(jì)算到第一個(gè)隱含層，并按照某種能使誤差向減小方向發(fā)展的原則，調(diào)整網(wǎng)絡(luò)中各神經(jīng)元的連接權(quán)值;6)對(duì)訓(xùn)練樣例集中的每一個(gè)樣例重復(fù)3-5的步驟，直到對(duì)整個(gè)訓(xùn)練樣例集的誤差達(dá)到要求時(shí)為止。BP模型優(yōu)缺點(diǎn)優(yōu)點(diǎn)：理論基礎(chǔ)牢固，推導(dǎo)過程嚴(yán)謹(jǐn)，物理概念清晰，通用性好等。所以，它是目前用來訓(xùn)練前向多層網(wǎng)絡(luò)較好的算法。缺點(diǎn)：1)學(xué)習(xí)算法的收斂速度慢；2)網(wǎng)絡(luò)中隱含節(jié)點(diǎn)個(gè)數(shù)的選取尚無(wú)理論上的指導(dǎo)；3)從數(shù)學(xué)角度看，BP算法是一種梯度最速下降法，這就可能出現(xiàn)局部極小的

60、問題。所以BP算法是不完備的。3.6 支持向量機(jī)支持向量機(jī)(Support Vector Machine)分類器的特點(diǎn)是能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)。因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。支持向量機(jī)將向量映射到一個(gè)更高維的空間，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。平行超平面間的距離或差距越大，分類器的總誤差越小。支持向量機(jī)面臨的問題目前，用SVM構(gòu)造分類器來處理海量數(shù)據(jù)面臨以下兩個(gè)困難：1)SVM算法對(duì)大規(guī)模訓(xùn)練樣本難以實(shí)施由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的計(jì)算(m為樣本的個(gè)數(shù))，當(dāng)m數(shù)目很大