樸素貝葉斯分類算法課件

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

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

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

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

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

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

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

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

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

10、棵決策樹，它可以用來對新的樣本進行分類。基本概念與ID3分類算法相關(guān)的基本概念包括：信息熵信息增益信息熵熵(entropy,也稱信息熵)用來度量一個屬性的信息量。假定S為訓(xùn)練集，S的目標(biāo)屬性C具有m個可能的類標(biāo)號值，C=C1,C2,Cm，假定訓(xùn)練集S中，Ci在所有樣本中出現(xiàn)的頻率為 (i=1,2,3,m)，則該訓(xùn)練集S所包含的信息熵定義為：熵越小表示樣本對目標(biāo)屬性的分布越純，反之熵越大表示樣本對目標(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個樣本,目標(biāo)屬性play ball有2個值C1=yes, C2=no。14個樣本的分布為：9個樣本的類標(biāo)號取值為yes，5個樣本的類標(biā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個不同的取值，從而將S劃分為k個樣本子集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對屬性wind的信息增益。 outlooktemperaturehumiditywindplay ballsunnyhothighweaknosunnyhothighstrongnoovercasthoth

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

15、4；(2)屬性wind有2個可能的取值weak,strong，它將S劃分為2個子集：S1,S2,S1為wind屬性取值為weak的樣本子集，共有8個樣本；S2為wind屬性取值為strong的樣本子集，共有6個樣本；下面分別計算樣本子集S1和S2的熵。信息增益例題演示(續(xù))對樣本子集S1，play ball=yes的有6個樣本，play ball=no的有2個樣本，則：對樣本子集S2，play ball=yes的有3個樣本，play ball=no的有3個樣本，則：信息增益例題演示(續(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全部屬于同一個類別C then(2) 創(chuàng)建一個葉結(jié)點，并標(biāo)記類標(biāo)號為C；(3) return；(4)else(5) 計算屬性集F中每一個屬性的信息增益，假定增益值最大的屬性為A；(6) 創(chuàng)建結(jié)點，取屬性A為該結(jié)點的決策屬性；(7) for 結(jié)點屬性A的每個可能的取值V do(8) 為該結(jié)點添加一個新的分支，假設(shè)SV為屬性A取值為V的樣本子集；(9) if 樣本SV全部屬于同一個類別C then(10) 為該分支添加一個葉結(jié)點，并標(biāo)記類標(biā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建立決策樹首先計算總數(shù)據(jù)集S對所

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

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

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

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

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

24、算法的概念描述假定S為訓(xùn)練集，目標(biāo)屬性C具有m個可能的取值，C=C1,C2,Cm，即訓(xùn)練集S的目標(biāo)屬性具有m個類標(biā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中的樣本,計算屬性A對集合S的劃分熵值EntropyA(S)定義如下:若屬性A為離散型數(shù)據(jù)，并具有k個不同的取值,則屬性A依據(jù)這k個不同取值將S劃分為k個子集S1,S2,Sk，屬性A劃分S的信息熵為：其中|Si|和|S|分別是Si和S中包含的樣本個數(shù)。C4.5算法的概念描

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

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

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

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

29、增益率，假定增益率值最大的屬性為A；(6) 創(chuàng)建結(jié)點，取屬性A為該結(jié)點的決策屬性；(7) for 結(jié)點屬性A的每個可能的取值V do(8) 為該結(jié)點添加一個新的分支, 假設(shè)SV為屬性A取值為V的樣本子集；(9) if 樣本SV全部屬于同一個類別C then(10) 為該分支添加一個葉結(jié)點，并標(biāo)記為類標(biā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)計算待剪子樹node中葉

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

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

32、sification and Regression Tree)算法，由美國斯坦福大學(xué)和加州大學(xué)伯克利分校的Breiman等人于1984年提出。CART決策樹采用的是二元遞歸劃分方法，能夠處理連續(xù)屬性數(shù)據(jù)和標(biāo)稱屬性作為預(yù)測變量和目標(biāo)變量下的分類，當(dāng)輸出變量是標(biāo)稱屬性數(shù)據(jù)時，所建立的決策樹稱為分類樹(classification tree)，用于分類的預(yù)測。當(dāng)輸出變量為數(shù)值型變量時，所建立的決策樹稱為回歸樹(regression tree)，用于數(shù)值的預(yù)測。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)稱的，并且具有兩個以上的類別，則CART可能考慮將目標(biāo)類別合并成兩個超類別。(5)如果目標(biāo)變量是連續(xù)的，則CART算法找出一組基于樹的回歸方程來預(yù)測目標(biāo)變量。(6)對于缺失值的處理方法不同，CART采用代理測試(surrogate)來估計測試的輸出值，而C4.5直接將其分配到該分支中概率最大的分類。 (7)對決策樹的剪枝方法不同。CART算法的基本概念分類回歸樹的建樹過程是對訓(xùn)練集的反復(fù)劃分的過程，涉及如何從多個屬性中選擇當(dāng)

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

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

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

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

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

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

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

41、%是在主場。如果下一場比賽在B對的主場進行，請預(yù)測哪支球隊最有可能勝出？解答：根據(jù)貝葉斯定理,假定隨機變量X代表東道主，X取值范圍為A,B隨機變量Y代表比賽的勝利者，取值范圍為A,B。已知：A對取勝的概率為0.65，表示為：P(Y=A)=0.65，B對取勝的概率為0.35 ，表示為：P(Y=B)=0.35，B對取勝時作為東道主的概率是0.75，表示為：P(X=B|Y=B) = 0.75,A對取勝時B對作為東道主的概率是0.3,表示為:P(X=B|Y=A) = 0.3,計算：下一場比賽在B對主場，同時A對勝出的概率表示為：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下一場比賽在B對主場，同時B對勝出的概率表示為：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ù)計算結(jié)果，可以推斷出，下一場最有可能是B對勝出。 P(X=B)的計算 ：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ù)測一個未知類別的樣本屬于各個類別的可能性，選擇其中可能性最大的一個類別作為該樣本的最終類別。樸素貝葉斯分類算法(續(xù))設(shè)數(shù)據(jù)集為D，對應(yīng)屬性集：A1,A2,An, CA1,A2,An是樣本的屬性變量，C是有m個取值C1,C2,.,Cm的類標(biāo)號屬性變量。數(shù)據(jù)集D中的每個樣本X可以表示為X=x1,x2,xn,Ci樸素貝葉斯分類算法的概念描述如下：1)假定樸素貝葉斯分類器將未知樣本X分配給類Ci，則： 根據(jù)貝葉斯定理:由于P(X)對所有類為常數(shù)

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

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

46、斯分類算法演示對weather數(shù)據(jù)集使用樸素貝葉斯算法預(yù)測未知樣本X=rainy,hot,normal,false,?的play ball類標(biāo)號屬性的值。該問題描述如下：樣本X=rainy, hot, normal, false, ?類標(biāo)號play ball有2個取值yes, no題目即求:樣本X在play為yes的概率P(play=yes|X)和樣本在play為no的概率P(play=no|X)樣本X將被預(yù)測為概率值大的那個類。解：根據(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 同樣方法計算：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ù)計算結(jié)果：P(play=yes|X) P(play=no|X)所以：樣本X=rainy,hot,normal,false,?的play類標(biāo)號值應(yīng)為yes.樸素貝葉斯分類算法在計算概率的時候存在概率為0及概率值可能很小的情況，因此在某些情況下需要考慮條件概率的Laplace估計以及解決小概率相乘溢出問題。1. 條件概率的Laplace估計在后驗概率的計算過程中，當(dāng)有一個屬性的條件概率等于0，則整個類的后驗概率就等于0，簡單地使用記錄比例來估計類條件概率的方法顯得太脆弱，尤其是當(dāng)訓(xùn)練樣本很少而屬性數(shù)目很大的情況下。一種更極端的情況是，當(dāng)訓(xùn)練樣例不能覆蓋那么多

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

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

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

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

54、進行分類，實現(xiàn)方法是通過投票進行多數(shù)表決得到最終類標(biāo)號 ，其中：其中 為類標(biāo)號的所有可能取值， 是測試樣本z的一個最近鄰類標(biāo)號， 是指示函數(shù)，如果其參數(shù)為真，則返回1，否則返回0。 kNN算法演示 對weather數(shù)據(jù)集，利用KNN算法，測試樣本X=(rain, hot, normal, weak，?)的類標(biāo)號屬性，其中k取3。Step1:首先計算樣本X到14個記錄的距離(取定義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最近的三個近鄰p5,p10,p13Step3:因為三個最近鄰對應(yīng)的類標(biāo)號都為yes,因此樣本X的類標(biāo)號被預(yù)測為yes。 kNN算法演示(續(xù))KNN算法優(yōu)缺點優(yōu)點：算法思想簡單，易于實現(xiàn)。缺點：最近鄰分類對每個屬性指定相同的權(quán)重。而數(shù)據(jù)集中的不同屬性可能需要賦予不同的權(quán)值；由于K

56、-NN存放所有的訓(xùn)練樣本，直到有新的樣本需要分類時才建立分類，因此當(dāng)訓(xùn)練樣本數(shù)量很大時，該學(xué)習(xí)算法的時間復(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)元之間相互連接的形式拓撲結(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機網(wǎng)絡(luò)等。感知器模型感知器神經(jīng)網(wǎng)絡(luò)是一個具有單層計算神經(jīng)元的神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的傳遞函數(shù)是線性閾值單元。原始的感知器神經(jīng)網(wǎng)絡(luò)只有一個神經(jīng)元，因此只能輸出兩個值，適合簡單的模式分類問題。感知器模型圖如下：單層感知器可將外部輸入分為兩類。當(dāng)感知器的輸出為+1時，輸入屬于L1類，當(dāng)感知器的輸出為-1時，輸入屬于L2類，從而實現(xiàn)兩類目標(biāo)的識別。感知器模型(續(xù))在多維空間，單層感知器進行模式識別的判決超平面由下式?jīng)Q定：對于只有兩個輸入的判別邊界是直線,選擇合適的學(xué)

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

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

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