數(shù)據(jù)挖掘原理、算法及應(yīng)用第4章分類和預(yù)測(cè)課件

1、第4章 分 類 和 預(yù) 測(cè)4.1 分類和預(yù)測(cè)的基本概念和步驟4.2 基于相似性的分類算法4.3 決策樹分類算法4.4 貝葉斯分類算法4.5 人工神經(jīng)網(wǎng)絡(luò)(ANN)4.6 支持向量機(jī)4.7 預(yù)測(cè)4.8 預(yù)測(cè)和分類中的準(zhǔn)確率、誤差的度量4.9 評(píng)估分類器或預(yù)測(cè)器的準(zhǔn)確率4.10 小結(jié) 4.1 分類和預(yù)測(cè)的基本概念和步驟銀行貸款員需要分析數(shù)據(jù)，搞清楚哪些貸款申請(qǐng)者是“安全的”，銀行的“風(fēng)險(xiǎn)”是什么。AllElectronics的市場(chǎng)經(jīng)理需要數(shù)據(jù)分析，以便幫助他猜測(cè)具有某些特征的顧客是否會(huì)購(gòu)買一臺(tái)新的計(jì)算機(jī)。醫(yī)學(xué)研究者希望分析乳腺癌數(shù)據(jù)，預(yù)測(cè)病人應(yīng)當(dāng)接受三種具體治療方案中的哪一種。 數(shù)據(jù)分類是一個(gè)兩步

2、過程，如圖4-1所示的貸款應(yīng)用數(shù)據(jù)，第一步，建立描述預(yù)先定義的數(shù)據(jù)類或概念集的分類器。 圖4-1 數(shù)據(jù)分類過程由于提供了每個(gè)訓(xùn)練元組的類標(biāo)號(hào)，這一步也稱做監(jiān)督學(xué)習(xí)(Supervised Learning)，即分類器的學(xué)習(xí)在被告知每個(gè)訓(xùn)練元組屬于哪個(gè)類的“監(jiān)督”下進(jìn)行。它不同于無監(jiān)督學(xué)習(xí)(Unsupervised Learning)(或稱聚類)，每個(gè)訓(xùn)練元組的類標(biāo)號(hào)是未知的，并且要學(xué)習(xí)的類的個(gè)數(shù)或集合也可能事先不知道。 在第二步(如圖4-1(b)所示)，使用模型進(jìn)行分類。首先評(píng)估分類器的預(yù)測(cè)準(zhǔn)確率。如果使用訓(xùn)練集來測(cè)量分類器的準(zhǔn)確率，則評(píng)估可能是樂觀的，因?yàn)榉诸惼髭呄蛴谶^分?jǐn)M合(overfit)

3、該數(shù)據(jù)(即在學(xué)習(xí)期間，它可能并入了訓(xùn)練數(shù)據(jù)中的某些特殊的異常點(diǎn)，這些異常點(diǎn)不在一般數(shù)據(jù)集中出現(xiàn))。 4.2 基于相似性的分類算法基于相似性的分類算法的思路比較簡(jiǎn)單直觀。假定數(shù)據(jù)庫(kù)中的每個(gè)元組ti為數(shù)值向量，每個(gè)類用一個(gè)典型數(shù)值向量來表示，則能通過分配每個(gè)元組到它最相似的類來實(shí)現(xiàn)分類。定義4.1 給定一個(gè)數(shù)據(jù)庫(kù)D=t1，t2，tn和一組類C=C1，C2，Cm。對(duì)于任意的元組ti=ti1，ti2，tik如果存在一個(gè)CiC，使得： (4.1)則ti被分配到類Ci中，其中sim(ti，Ci)稱為相似性度量函數(shù)。 算法4.1 基于相似性的分類算法(每個(gè)類Ci對(duì)應(yīng)一個(gè)中心點(diǎn))。輸入：每個(gè)類的中心C1, C

4、2, , Cm；待分類的元組t。輸出：輸出類別c。 算法4.2 基于相似性的分類算法(每個(gè)類Ci對(duì)應(yīng)多個(gè)中心點(diǎn))。輸入：訓(xùn)練樣本數(shù)據(jù)D=t1，t2，tn和訓(xùn)練樣本對(duì)應(yīng)類屬性值C=C1，C2，Cm；待分類的元組t。輸出：輸出類別c。算法4.3 k-最臨近算法。輸入：訓(xùn)練數(shù)據(jù)T；最臨近數(shù)目k；待分類的元組t輸出：輸出類別c 4.3 決策樹分類算法從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法是生成一個(gè)決策樹(Decision Tree)。決策樹表示方法是應(yīng)用最廣泛的邏輯方法之一，它從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值

5、的比較，根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分支，在決策樹的葉結(jié)點(diǎn)得到結(jié)論。所以，從決策樹的根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整棵決策樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。圖4-2 buys_computer的決策樹示意圖4.3.1 決策樹基本算法概述 1. 決策樹生成算法決策樹生成算法的輸入是一組帶有類別標(biāo)記的例子，決策樹是一棵二叉樹或多叉樹。二叉樹的內(nèi)部結(jié)點(diǎn)(非葉子結(jié)點(diǎn))一般表示為一個(gè)邏輯判斷，如形式為(ai=vi)的邏輯判斷，其中ai是屬性，vi是該屬性的某個(gè)屬性值。樹的邊是邏輯判斷的分支結(jié)果。多叉樹的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹的葉子結(jié)點(diǎn)都是類別標(biāo)記

6、。算法4.4 Generate_decision_tree(決策樹生成算法)。輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹(由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹)。(1) 創(chuàng)建結(jié)點(diǎn)N；(2) IF samples 都在同一個(gè)類C THEN 返回N作為葉結(jié)點(diǎn)，以類C標(biāo)記，并且Return；(3) IF attribute_list為空 THEN 返回N作為葉結(jié)點(diǎn)，標(biāo)記為samples中最普通的類,并且Return；/多數(shù)表決(4) 選擇attribute_list中具有最高信息增益的屬性test_attribute；(5) 標(biāo)記結(jié)點(diǎn)N為t

7、est_attribute；(6) FOR each test_attribute中的已知值ai，由結(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai的分枝；(7) 設(shè)si是samples 中test_attribute =ai的樣本的集合；/一個(gè)劃分(8) IF si 為空 THEN 加上一個(gè)樹葉，標(biāo)記為samples中最普通的類；(9) ELSE 加上一個(gè)由Generate_decision_tree(si，attribute_listtest_attribute)返回的結(jié)點(diǎn)。2. 決策樹修剪算法現(xiàn)實(shí)世界的數(shù)據(jù)一般不可能是完美的，可能某些屬性字段上缺值(Missing Values)；

8、可能缺少必須的數(shù)據(jù)而造成數(shù)據(jù)不完整；可能數(shù)據(jù)不準(zhǔn)確、含有噪聲甚至是錯(cuò)誤的。 有兩種基本的剪枝策略：(1) 預(yù)先剪枝(Pre-Pruning)：在生成樹的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。(2) 后剪枝(Post-Pruning)：一種擬合-化簡(jiǎn)(Fitting-and-simplifying)的兩階段方法。首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合(Tuning Set或Adjusting Set)，如果存在某個(gè)葉子剪去后測(cè)試集上的準(zhǔn)確度或其他測(cè)度不降低(不變得更壞)，則剪去該葉子；否則停機(jī)。4.3.2 ID3算

9、法1. 信息論簡(jiǎn)介1948年Shannon提出并發(fā)展了信息論，以數(shù)學(xué)的方法度量并研究信息，通過通信后對(duì)信源中各種符號(hào)出現(xiàn)的不確定程度的消除來度量信息量的大小。他提出了自信息量、信息熵、條件熵及平均互信息量等一系列概念。條件熵及平均互信息量等一系列概念。(1) 自信息量。在收到ai之前，收信者對(duì)信源發(fā)出ai的不確定性定義為信息符號(hào)ai的自信息量I(ai)，即I(ai)=-lbp(ai)，其中p(ai)為信源發(fā)出ai的概率。(2) 信息熵。自信息量只能反映符號(hào)的不確定性，而信息熵可以用來度量整個(gè)信源X整體的不確定性，定義如下： (4.2)(3) 條件熵。如果信源X與隨機(jī)變量Y不是相互獨(dú)立的，收信者

10、收到信息Y，那么，用條件熵H(XY)來度量收信者在收到隨機(jī)變量Y之后，對(duì)隨機(jī)變量X仍然存在的不確定性。設(shè)X對(duì)應(yīng)信源符號(hào)ai，Y對(duì)應(yīng)信源符號(hào)bj，p(ai|bj)為當(dāng)Y為bj時(shí)，X為ai的概率，則有： (4.3)(4) 平均互信息量。平均互信息量表示信號(hào)Y所能提供的關(guān)于X的信息量的大小，用I(X,Y)表示： (4.4) 2. 信息增益計(jì)算在學(xué)習(xí)開始的時(shí)候只有一棵空的決策樹，并不知道如何根據(jù)屬性將實(shí)例進(jìn)行分類，所要做的就是根據(jù)訓(xùn)練實(shí)例集構(gòu)造決策樹來預(yù)測(cè)如何根據(jù)屬性對(duì)整個(gè)實(shí)例空間進(jìn)行劃分。設(shè)此時(shí)訓(xùn)練實(shí)例集為X，目的是將訓(xùn)練實(shí)例分為n類。設(shè)屬于第i類的訓(xùn)練實(shí)例為Ci，X中總的訓(xùn)練實(shí)例個(gè)數(shù)為|X|，若記

11、一個(gè)實(shí)例屬于第i類的概率為P(Ci)，則： (4.5) 此時(shí)，決策樹對(duì)劃分C的不確定程度為 (4.6) 以后在無混淆的情況下將H(X，C)簡(jiǎn)記為H(X)。(4.7) 決策樹學(xué)習(xí)過程就是使得決策樹對(duì)劃分的不確定程度逐漸減小的過程。若選擇測(cè)試屬性a進(jìn)行測(cè)試，在得知a=aj的情況下屬于第i類的實(shí)例為Cij。記 (4.8)即p(Ci；a=aj)為在測(cè)試屬性a的取值為aj時(shí)，它屬于第i類的概率。此時(shí)，決策樹對(duì)分類的不確定程度就是訓(xùn)練實(shí)例集對(duì)屬性X的條件熵。 (4.9)又因?yàn)樵谶x擇測(cè)試屬性a后伸出的每個(gè)a=aj分支Xj對(duì)于分類信息的信息熵為(4.10)屬性a對(duì)于分類提供的信息增益I(X；a)為： (4.1

12、1)3. ITD3算法算法4.5 ID3算法。4. ID3算法應(yīng)用舉例【例4.1】 表4-1給出了一個(gè)可能帶有噪音的數(shù)據(jù)集合。它有四個(gè)屬性：Outlook、Temperature、H umidity和Windy。它被分為No和Yes兩類。通過ID3算法構(gòu)造決策樹將數(shù)據(jù)進(jìn)行分類。因?yàn)槌跏紩r(shí)刻屬于P類和N類的實(shí)例個(gè)數(shù)均為12個(gè)，所以初始時(shí)刻的熵值為如果選取Outlook屬性作為測(cè)試屬性，根據(jù)式(4.10)，此時(shí)的條件熵為如果選取Temperature屬性作為測(cè)試屬性，則有:如果選取Humidity屬性作為測(cè)試屬性，則有:如果選取Windy屬性作為測(cè)試屬性，則有:可以看出H(X|Outlook)最小

13、，即有關(guān)Outlook的信息對(duì)于分類有最大的幫助，提供最大的信息量，即I(X，Outlook)最大。所以應(yīng)該選擇Outlook屬性作為測(cè)試屬性。還可以看出H(X)=H(X|Windy)，即I(X,Windy)=0，有關(guān)Windy的信息不能提供任何分類信息。選擇Outlook作為測(cè)試屬性之后將訓(xùn)練實(shí)例集分為三個(gè)子集，生成三個(gè)葉結(jié)點(diǎn)，對(duì)每個(gè)葉結(jié)點(diǎn)依次利用上面過程則生成如圖4-3所示的決策樹。圖4-3 表4-1所訓(xùn)練生成的決策樹5. ID3算法性能分析ID3算法可以描述成從一個(gè)假設(shè)空間中搜索一個(gè)擬合訓(xùn)練樣例的假設(shè)。被ID3算法搜索的假設(shè)空間就是可能的決策樹的集合。ID3算法以一種從簡(jiǎn)單到復(fù)雜的爬山算

14、法遍歷這個(gè)假設(shè)空間，從空的樹開始，然后逐步考慮更加復(fù)雜的假設(shè)，目的是搜索到一個(gè)正確分類訓(xùn)練數(shù)據(jù)的決策樹。引導(dǎo)這種爬山搜索的評(píng)估函數(shù)是信息增益度量。有幾種途徑可被用來避免決策樹學(xué)習(xí)中的過度擬合，它們分為兩類：(1) 預(yù)先剪枝，及早停止樹增長(zhǎng)，在ID3算法完美分類訓(xùn)練數(shù)據(jù)之前就停止樹增長(zhǎng)。(2) 后剪枝，即允許樹過度擬合數(shù)據(jù)，然后對(duì)這個(gè)樹進(jìn)行后修剪。 無論是通過及早停止還是后剪枝來得到正確規(guī)模的樹，一個(gè)關(guān)鍵的問題是使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模。解決這個(gè)問題的方法包括：(1) 使用與訓(xùn)練樣例截然不同的一套分離的樣例來評(píng)估后修剪的決策樹的分類效果。(2) 使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)

15、測(cè)試來估計(jì)擴(kuò)展(或修剪)一個(gè)特定的結(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。例如，Quinlan(1986)使用一種卡方法(Chi_square)測(cè)試來估計(jì)進(jìn)一步擴(kuò)展結(jié)點(diǎn)是否能改善在整個(gè)實(shí)例分布上的性能，還是僅僅改善了當(dāng)前的訓(xùn)練數(shù)據(jù)上的性能。4.3.3 C4.5算法C4.5克服了ID3在應(yīng)用中存在的不足，主要體現(xiàn)在以下幾個(gè)方面：(1) 用信息增益率來選擇屬性，它克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足。(2) 在樹構(gòu)造過程中或者構(gòu)造完成之后，進(jìn)行剪枝。(3) 能夠完成對(duì)連續(xù)屬性的離散化處理。(4) 能夠?qū)τ诓煌暾麛?shù)據(jù)進(jìn)行處理，例如能對(duì)未知的屬性值進(jìn)行處理。(5) C4.5采用的

16、知識(shí)表示形式為決策樹，并最終可以形成產(chǎn)生式規(guī)則。1. 構(gòu)造決策樹設(shè)T為數(shù)據(jù)集，類別集合為C1，C2，Ck，選擇一個(gè)屬性V把T分為多個(gè)子集。設(shè)V有互不重合的n個(gè)取值v1，v2，vn，則T被分為n個(gè)子集T1，T2，Tn，這里Ti中的所有實(shí)例的取值均為vi。令|T|為數(shù)據(jù)集T的例子數(shù)，|Ti|為V=vi的例子數(shù)，|Cj|=freq(Cj，T)為Cj類的例子數(shù)，|Cjv|是V=vi例子中，具有Cj類別例子數(shù)。則有: 類別Cj發(fā)生概率為 (4.12) 屬性V=vi的發(fā)生概率為 (4.13) 屬性V=vi的例子中，具有類別Cj的條件概率為 (4.14) Quinlan在ID3中使用信息論中的信息增益(ga

17、in)來選擇屬性，而C4.5采用屬性的信息增益率(gainratio)來選擇屬性。1) 類別的信息熵 (4.15)2) 類別條件熵按照屬性V把集合T分割，分割后的類別條件熵為 (4.16)3) 信息增益(gain)信息增益，即互信息?？杀硎緸?(4.17)4) 屬性V的信息熵 (4.18)5) 信息增益率 (4.19) 2. 連續(xù)屬性的處理在ID3中沒有處理連續(xù)屬性的功能。在C4.5中，設(shè)在集合T中，連續(xù)屬性A的取值為v1，v2，vm，則任何在vi和vi+1之間的任意取值都可以把實(shí)例集合分為兩部分，即 (4.20)可以看到一共有m1種分割情況。對(duì)屬性A的m1種分割的任意一種情況，作為該屬性的兩

18、個(gè)離散取值，重新構(gòu)造該屬性的離散值，再按照上述公式計(jì)算每種分割所對(duì)應(yīng)的信息增益率gain_ratio(vi)，在m1 種分割中，選擇最大增益率的分割作為屬性A的分枝，即 (4.21)圖4-4 連續(xù)屬性分割示意圖3. 決策樹剪枝由于噪聲和隨機(jī)因素的影響，決策樹一般會(huì)很復(fù)雜，因此需要進(jìn)行剪枝操作。1) 剪枝策略有兩種剪枝策略： 在樹生成過程中判斷是否還繼續(xù)擴(kuò)展決策樹，若停止擴(kuò)展，則相當(dāng)于剪去該結(jié)點(diǎn)以下的分枝； 對(duì)于生成好的樹剪去某些結(jié)點(diǎn)和分枝。2) 基于誤差的剪枝決策樹的剪枝通常是用葉結(jié)點(diǎn)替代一個(gè)或者多個(gè)子樹，然后選擇出現(xiàn)概率最高的類作為該結(jié)點(diǎn)的類別。在C4.5中，還允許用其中的樹枝來替代子樹。如

19、果使用葉結(jié)點(diǎn)或者樹枝代替原來的子樹之后，誤差率若能夠下降，則使用此葉結(jié)點(diǎn)或者樹枝代替原來的子樹。圖4-5所示為用一個(gè)葉子節(jié)點(diǎn)替換子樹示意圖。圖4-5 用一個(gè)葉子節(jié)點(diǎn)替換子樹示意圖3) 誤差率的判斷設(shè)一個(gè)葉結(jié)點(diǎn)覆蓋N個(gè)實(shí)例，其中E個(gè)為錯(cuò)誤的。對(duì)于具有信任CF的實(shí)例，計(jì)算一個(gè)二項(xiàng)分布UCF(E，N)，該二項(xiàng)分布即實(shí)例的誤判概率，那么N個(gè)實(shí)例判斷錯(cuò)誤的數(shù)目為NUCF(E，N)。子樹的錯(cuò)誤數(shù)目為所有葉結(jié)點(diǎn)的總和。例如：上例中：括號(hào)中為覆蓋的實(shí)例。設(shè)CF=0.25，則該子樹的實(shí)例判斷錯(cuò)誤數(shù)目為若以一個(gè)葉結(jié)點(diǎn)C1代替該子樹，則16個(gè)實(shí)例中有一個(gè)錯(cuò)誤(C3)，誤判實(shí)例數(shù)目為由于判斷錯(cuò)誤數(shù)目小于上述子樹，則以

20、該葉結(jié)點(diǎn)代替子樹。4.4 貝葉斯分類算法貝葉斯分類是統(tǒng)計(jì)分類方法。在貝葉斯學(xué)習(xí)方法中實(shí)用性很高的一種稱為樸素貝葉斯分類方法。在某些領(lǐng)域，其性能與神經(jīng)網(wǎng)絡(luò)、決策樹相當(dāng)。 4.4.1 貝葉斯定理定義4.2 設(shè)X是類標(biāo)號(hào)未知的數(shù)據(jù)樣本，設(shè)H為某種假定，如數(shù)據(jù)樣本X屬于某特定的類C。對(duì)于分類問題，希望確定P(H|X)，即給定觀測(cè)數(shù)據(jù)樣本X，假定H成立的概率。貝葉斯定理給出了如下計(jì)算P(H|X)的簡(jiǎn)單有效的方法：(4.22)4.4.2 樸素貝葉斯分類樸素貝葉斯分類的工作過程如下：(1) 每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量X=x1，x2，xn表示，分別描述具有n個(gè)屬性A1，A2，An的樣本的n個(gè)度量。(2)

21、假定有m個(gè)類C1，C2，Cm，給定一個(gè)未知的數(shù)據(jù)樣本X(即沒有類標(biāo)號(hào))，分類器將預(yù)測(cè)X屬于具有最高后驗(yàn)概率(條件X下)的類。也就是說，樸素貝葉斯分類將未知的樣本分配給類Ci(1im)，當(dāng)且僅當(dāng)P(Ci|X)P(Cj|X)，j=1，2，m，ji。這樣，最大的P(Ci|X)對(duì)應(yīng)的類Ci稱為最大后驗(yàn)假定，而P(Ci|X)可以根據(jù)下面的貝葉斯定理來確定： (4.23)(3) 由于P(X)對(duì)于所有類為常數(shù)，只需要P(X|Ci)P(Ci)最大即可。如果Ci類的先驗(yàn)概率未知，則通常假定這些類是等概率的，即P(C1)=P(C2)=P(Cm)，因此問題就轉(zhuǎn)換為對(duì)P(X|Ci)的最大化。P(X|Ci)常被稱為給定

22、Ci時(shí)數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設(shè)Ci稱為最大似然假設(shè)。否則，需要最大化P(X|Ci)P(Ci)。注意，假設(shè)不是等概率，那么類的先驗(yàn)概率可以用P(Ci)=si/s計(jì)算，其中si是類Ci中的訓(xùn)練樣本數(shù)，而s是訓(xùn)練樣本總數(shù)。(4) 給定具有許多屬性的數(shù)據(jù)集，計(jì)算P(X|Ci)的開銷可能非常大。為降低計(jì)算P(X|Ci)的開銷，可以做類條件獨(dú)立的樸素假定。給定樣本的類標(biāo)號(hào)，假定屬性值相互條件獨(dú)立，即在屬性間不存在依賴關(guān)系。這樣 (4.24)如果Ak是離散屬性，則P(xk|Ci)=sik/si，其中sik是在屬性Ak上具有值xk的類Ci的訓(xùn)練樣本數(shù)，而si是Ci中的訓(xùn)練樣本數(shù)。如果Ak是

23、連續(xù)值屬性，則通常假定該屬性服從高斯分布，即 (4.25)【例4.2】 對(duì)于表4-2給出的訓(xùn)練數(shù)據(jù)，使用樸素貝葉斯方法進(jìn)行分類學(xué)習(xí)。解 數(shù)據(jù)樣本用屬性age，income,student和credit_rating描述。類標(biāo)號(hào)屬性buys_computer具有兩個(gè)不同值(即yes，no)。設(shè)C1對(duì)應(yīng)于類buys_computer=“Yes”，而C2對(duì)應(yīng)于類buys_computer=“No”。希望分類的未知樣本為X=(age=“ 30”,income=“medium”,student =“Yes”,credit_rating=“fair”)。需要最大化P(X|Ci)P(Ci)，i=1，2。每個(gè)

24、類的先驗(yàn)概P(Ci)可以根據(jù)訓(xùn)練樣本計(jì)算： P(buys_computer=“Yes”)=9/14= 0.643。 P(buys_computer=“No”)=5/1 4=0.357。 為計(jì)算P(P(X|Ci)，i=1、2，計(jì)算下面的條件概率假設(shè)條件獨(dú)立性，使用以上概率，得到：因此，對(duì)于樣本X，樸素貝葉斯分類預(yù)測(cè)buys_computer=“yes”。至此，通過在全部時(shí)間基礎(chǔ)上觀察某事件出現(xiàn)的比例來估計(jì)概率。例如，在上例中，估計(jì)P(age30| buys_computer=“yes”)使用的是比值行nc/n，其中n=9為所有buys_computer=“yes”的訓(xùn)練樣本數(shù)目，而nc=2是在其

25、中age30的數(shù)目。顯然，在多數(shù)情況下，觀察到的比例是對(duì)概率的一個(gè)良好估計(jì)，但當(dāng)nc很小時(shí)估計(jì)較差。設(shè)想P(age30| buys_computer=“yes”)的值為0.08，而樣本中只有9個(gè)樣本為buys_computer=“yes”，那么對(duì)于nc最有可能的值只有0。這產(chǎn)生了兩個(gè)難題：(1) nc/n產(chǎn)生了一個(gè)有偏的過低估計(jì)(Underestimate)概率。(2) 當(dāng)此概率估計(jì)為0時(shí)，如果將來的查詢包括age30，此概率項(xiàng)會(huì)在貝葉斯分類器中占有統(tǒng)治地位。原因在于，其他概率項(xiàng)乘以0值后得到的最終結(jié)果為0。為避免這些難題，可以采用一種估計(jì)概率的貝葉斯方法，即如下定義的m-估計(jì)： (4.26)

26、4.4.3 貝葉斯信念網(wǎng)1. 模型表示貝葉斯信念網(wǎng)絡(luò)(Bayesian Belief Networks，BBN)，簡(jiǎn)稱貝葉斯網(wǎng)絡(luò)，用圖形表示一組隨機(jī)變量之間的概率關(guān)系。貝葉斯網(wǎng)絡(luò)有兩個(gè)主要成分：(1) 一個(gè)有向無環(huán)圖(dag)，表示變量之間的依賴關(guān)系。(2) 一個(gè)概率表，把各結(jié)點(diǎn)和它的直接父結(jié)點(diǎn)關(guān)聯(lián)起來。貝葉斯網(wǎng)絡(luò)的重要性質(zhì)表述如下：性質(zhì)1 條件獨(dú)立 貝葉斯網(wǎng)絡(luò)中的一個(gè)結(jié)點(diǎn)，如果它的父母結(jié)點(diǎn)已知，則它條件獨(dú)立于它的所有非后代結(jié)點(diǎn)。圖4-6(b)中，給定C，A條件獨(dú)立于B和D，因?yàn)锽和D都是A的非后代結(jié)點(diǎn)。樸素貝葉斯分類器中的條件獨(dú)立假設(shè)也可以用貝葉斯網(wǎng)絡(luò)來表示。如圖4-5(c)所示，其中y是目

27、標(biāo)類，X1，X2，Xd是屬性集。圖4-6 使用有向無環(huán)圖表示概率關(guān)系圖4-7所示是貝葉斯網(wǎng)絡(luò)的一個(gè)例子，對(duì)心臟病或心口痛患者建模。假設(shè)圖中每個(gè)變量都是二值的。心臟病結(jié)點(diǎn)(HD)的父母結(jié)點(diǎn)對(duì)應(yīng)于影響該疾病的危險(xiǎn)因素，例如鍛煉(E)和飲食(D)等。心臟病結(jié)點(diǎn)的子結(jié)點(diǎn)對(duì)應(yīng)于該病的癥狀，如胸痛(CP)和高血壓(BP)等。如圖4-7所示，心口痛(Hb)可能源于不健康的飲食，同時(shí)又可能導(dǎo)致胸痛。圖4-7 發(fā)現(xiàn)心臟病和心口痛病人的貝葉斯網(wǎng)影響疾病的危險(xiǎn)因素對(duì)應(yīng)的結(jié)點(diǎn)只包含先驗(yàn)概率，而心臟病、心口痛以及它們的相應(yīng)癥狀所對(duì)應(yīng)的結(jié)點(diǎn)都包含條件概率。為了節(jié)省空間，圖中省略了一些概率。注意P(X= x )=1P(X=

28、x)，P(X= x |Y)=1P(X=x|Y)，其中 x 表示與x相反的結(jié)果。因此，省略的概率可以很易求得。例如，條件概率：P(心臟病=No|鍛煉=No,飲食=健康) =1-P(心臟病=Yes|鍛煉=No,飲食=健康) =10.55 =0.452. 建立模型貝葉斯網(wǎng)絡(luò)的建模包括兩個(gè)步驟：創(chuàng)建網(wǎng)絡(luò)結(jié)構(gòu)；估計(jì)每一個(gè)結(jié)點(diǎn)的概率表中的概率值。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以通過對(duì)主觀的領(lǐng)域?qū)＜抑R(shí)編碼獲得。算法4.5給出了歸納貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一個(gè)系統(tǒng)的過程。算法4.5 貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生成算法。例4.3 考慮圖4-7中的變量。執(zhí)行步驟1后，設(shè)變量次序?yàn)?E，D，HD，Hb，CP，BP)。從變量D開始，經(jīng)過步驟

29、2到7，得到如下條件概率：3. 使用BBN進(jìn)行推理舉例情況一：沒有先驗(yàn)信息。在沒有任何先驗(yàn)信息的情況下，可以通過計(jì)算先驗(yàn)概率P(HD=Yes)和P(HD=No)來確定一個(gè)病人是否可能患心臟病。為了表述方便，設(shè)Yes，No表示鍛煉的兩個(gè)值，健康，不健康表示飲食的兩個(gè)值。情況二：高血壓。如果一個(gè)人有高血壓，可以通過比較后驗(yàn)概率P(HD=Yes|BP=高)和P(HD=No|BP=高)來診斷他是否患有心臟病。為此，必須先計(jì)算P(BP=高)：其中Yes，No。因此，此人患心臟病的后驗(yàn)概率是：情況三：高血壓、飲食健康、經(jīng)常鍛煉身體。假設(shè)得知此人經(jīng)常鍛煉身體并且飲食健康。加上這些新信息，此人患心臟病的后驗(yàn)概

30、率為而此人不患心臟病的概率是：因此模型暗示健康的飲食和有規(guī)律的體育鍛煉可以降低患心臟病的危險(xiǎn)。4. BBN的特點(diǎn)下面是BBN模型的一般特點(diǎn)：(1) BBN提供了一種用圖形模型來捕獲特定領(lǐng)域的先驗(yàn)知識(shí)的方法。網(wǎng)絡(luò)還可以用來對(duì)變量間的因果依賴關(guān)系進(jìn)行編碼。(2) 構(gòu)造網(wǎng)絡(luò)可能既費(fèi)時(shí)又費(fèi)力。然而，一旦網(wǎng)絡(luò)結(jié)構(gòu)確定下來，添加新變量就十分容易。(3) 貝葉斯網(wǎng)絡(luò)很適合處理不完整的數(shù)據(jù)。對(duì)有屬性遺漏的實(shí)例可以通過對(duì)該屬性的所有可能取值的概率求和或求積分來加以處理。(4) 因?yàn)閿?shù)據(jù)和先驗(yàn)知識(shí)以概率的方式結(jié)合起來了，所以該方法對(duì)模型的過分?jǐn)M合問題是非常魯棒的。4.5 人工神經(jīng)網(wǎng)絡(luò)(ANN)4.5.1 人工神經(jīng)

31、網(wǎng)絡(luò)的基本概念大腦的一個(gè)重要成分是神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)由相互關(guān)聯(lián)的神經(jīng)元組成。每一個(gè)神經(jīng)元由內(nèi)核(Body)、軸突(Axon)和晶枝(Dendrite)組成。晶枝形成一個(gè)非常精密的“毛刷”環(huán)繞在內(nèi)核周圍。軸突可以想象為一根又長(zhǎng)又細(xì)的管道，其終點(diǎn)分為眾多細(xì)小分支，將內(nèi)核的信息傳遞給其他內(nèi)核的晶枝。這些細(xì)小分支的頭，即那些又長(zhǎng)又細(xì)管道的終點(diǎn)，稱為突觸(synapse)，它們的主要功能是接觸其他內(nèi)核的晶枝。圖4-8 生物學(xué)中神經(jīng)網(wǎng)絡(luò)的簡(jiǎn)圖一個(gè)神經(jīng)元根據(jù)晶枝接收到的信息，通過內(nèi)核進(jìn)行信息處理，再通過它所控制的突觸送給其他的神經(jīng)元。神經(jīng)元可分為兩種：“抑制”性的或“興奮”性的。當(dāng)一個(gè)神經(jīng)元的晶枝接收的興奮

32、性信息累計(jì)超出某一值時(shí)，神經(jīng)元被激活并傳遞出一個(gè)信息給其他神經(jīng)元，這個(gè)值稱為閾值(Threshold)。這種傳遞信息的神經(jīng)元為“興奮”性的。第二種情況是神經(jīng)元雖然接收到其他神經(jīng)元傳遞的信息，但沒有向外傳遞信息，此時(shí)，稱這個(gè)神經(jīng)元為“抑制”性的。圖4-9 McCulloch-Pitts認(rèn)知網(wǎng)絡(luò)在圖4-9中，wi為關(guān)聯(lián)權(quán)，表示神經(jīng)元對(duì)第i個(gè)晶枝接收到信息的感知能力。f稱為輸出函數(shù)或激活函數(shù)(Activation Function)，y=f(z)為輸出神經(jīng)元的輸出值。McCulloch-Pitts 輸出函數(shù)定義為(4.27)其中， (4.28)人工神經(jīng)網(wǎng)絡(luò)的建立和應(yīng)用可以歸結(jié)為三個(gè)步驟： (1) 網(wǎng)

33、絡(luò)結(jié)構(gòu)的確定。激活函數(shù)的類型比較多，主要有線性函數(shù)(式(4.29)和Sigmoid函數(shù)(式(4.30)。 f(x)=ax+b(4.29)其中，a和b是實(shí)常數(shù)。 (4.30) 識(shí)別和歸類問題中，如果采用階躍函數(shù)，當(dāng)輸出值為1時(shí)，可以肯定地說出輸入的歸類。階躍函數(shù)的缺點(diǎn)是數(shù)學(xué)性質(zhì)較差，如在x0點(diǎn)不光滑。Sigmoid函數(shù)彌補(bǔ)了這一方面的不足，使得函數(shù)值在(0，1)區(qū)間連續(xù)變化。Sigmoid函數(shù)又稱S形函數(shù)，如圖4-10所示。圖4-10 Sigmoid函數(shù)(2) 關(guān)聯(lián)權(quán)和的確定。關(guān)聯(lián)權(quán)和是通過學(xué)習(xí)(訓(xùn)練，train)得到的，學(xué)習(xí)分為有指導(dǎo)學(xué)習(xí)和無指導(dǎo)學(xué)習(xí)兩類。在一組正確的輸入輸出結(jié)果的條件下，人工

34、神經(jīng)網(wǎng)絡(luò)依據(jù)這些數(shù)據(jù)，調(diào)整并確定權(quán)數(shù)wi和，使得網(wǎng)絡(luò)輸出同理想輸出偏差盡量小的方法稱為有指導(dǎo)學(xué)習(xí)。在只有輸入數(shù)據(jù)而不知輸出結(jié)果的前提下，確定權(quán)數(shù)wi和的方法稱無指導(dǎo)學(xué)習(xí)。在學(xué)習(xí)過程中，不同的目標(biāo)函數(shù)得到不同的學(xué)習(xí)規(guī)則。 (3) 工作階段(Simulate)。在權(quán)數(shù)wi和確定的基礎(chǔ)上，用帶有確定權(quán)數(shù)的神經(jīng)網(wǎng)絡(luò)去解決實(shí)際問題的過程稱為工作。圖4-11是前向型人工神經(jīng)網(wǎng)絡(luò)的計(jì)算流程。 圖4-11 前向型人工神經(jīng)網(wǎng)絡(luò)的計(jì)算流4.5.2 感知器考慮圖4-12中的圖和表。圖(a)所示的表顯示一個(gè)數(shù)據(jù)集，包含三個(gè)布爾變量(x1，x2，x3)和一個(gè)輸出變量y，當(dāng)三個(gè)輸入中至少有兩個(gè)是0時(shí)，y取1，而至少有兩個(gè)

35、大于0時(shí)，y取1。圖4-12 使用感知器模擬一個(gè)布爾函數(shù)模型的輸出計(jì)算公式如下： (4.31) 注意感知器的輸入結(jié)點(diǎn)和輸出結(jié)點(diǎn)之間的區(qū)別。輸入結(jié)點(diǎn)簡(jiǎn)單地把接收到的值傳送給輸出鏈，而不作任何轉(zhuǎn)換。輸出結(jié)點(diǎn)則是一個(gè)數(shù)學(xué)裝置，計(jì)算輸入的加權(quán)和，減去偏置項(xiàng)，然后根據(jù)結(jié)果的符號(hào)產(chǎn)生輸出。更具體地，感知器模型的輸出可以用如下數(shù)學(xué)方式表示：(4.32)其中，w1，w2，wd是輸入鏈的權(quán)值，而x1， x2， xd是輸入屬性值。符號(hào)函數(shù)作為輸出神經(jīng)元的激活函數(shù)(Activation Function)，當(dāng)參數(shù)為正時(shí)輸出+1，參數(shù)為負(fù)時(shí)輸出1。感知器模型可以寫成下面更簡(jiǎn)潔的形式： (4.33)算法4.6 感知器學(xué)

36、習(xí)算法。(10) until 滿足終止條件算法的主要計(jì)算是第(7)步中的權(quán)值更新公式：(4.34)其中，wj(k)是第k次循環(huán)后第i個(gè)輸入鏈上的權(quán)值，參數(shù)為學(xué)習(xí)率(Learning Rate)，xij是訓(xùn)練樣本xi的第j個(gè)屬性值。從公式(4.34)可以看出，新權(quán)值W(k+1)等于舊權(quán)值W(k)加上一個(gè)正比于預(yù)測(cè)誤差(y )的項(xiàng)。如果預(yù)測(cè)正確，那么權(quán)值保持不變。否則，按照如下方法更新：(1) 如果y=+1， =1，那么預(yù)測(cè)誤差(y )=2。為了補(bǔ)償這個(gè)誤差，需要通過提高所有正輸入鏈的權(quán)值、降低所有負(fù)輸入鏈的權(quán)值來提高預(yù)測(cè)輸出值。(2) 如果y=1， =+1，那么預(yù)測(cè)誤差(y )=2。為了補(bǔ)償這個(gè)

37、誤差，需要通過降低所有正輸入鏈的權(quán)值、提高所有負(fù)輸入鏈的權(quán)值來減少預(yù)測(cè)輸出值。圖4-13 圖4-12中的數(shù)據(jù)的感知器決策邊界圖4-14 XOR4.5.3 多層人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)比感知器模型更復(fù)雜。這些額外的復(fù)雜性來源于多個(gè)方面：(1) 網(wǎng)絡(luò)的輸入層和輸出層之間可能包含多個(gè)中間層，這些中間層叫做隱藏層(Hidden Layer)，隱藏層中的結(jié)點(diǎn)稱為隱藏結(jié)點(diǎn)(Hidden Node)。這種結(jié)構(gòu)稱為多層神經(jīng)網(wǎng)絡(luò)(見圖4-15)。 圖4-15 多層前饋人工神經(jīng)網(wǎng)絡(luò)(ANN)舉例(2) 除了符號(hào)函數(shù)外，網(wǎng)絡(luò)還可以使用其他激活函數(shù)，如圖4-16所示的線性函數(shù)、S型(邏輯斯締)函數(shù)、雙曲正切函數(shù)等

38、。這些激活函數(shù)允許隱藏結(jié)點(diǎn)和輸出結(jié)點(diǎn)的輸出值與輸入?yún)?shù)呈非線性關(guān)系。圖4-16 人工神經(jīng)網(wǎng)絡(luò)激活函數(shù)的類型這些附加的復(fù)雜性使得多層神經(jīng)網(wǎng)絡(luò)可以對(duì)輸入和輸出變量間更復(fù)雜的關(guān)系建模。例如，考慮上一節(jié)中描述的XOR問題。實(shí)例可以用兩個(gè)超平面進(jìn)行分類，這兩個(gè)超平面把輸入空間劃分到各自的類，如圖4-17(a)所示。因?yàn)楦兄髦荒軜?gòu)造一個(gè)超平面，所以它無法找到最優(yōu)解。該問題可以使用兩層前饋神經(jīng)網(wǎng)絡(luò)加以解決，見圖4-17(b)。 圖4-17 XOR問題的兩層前饋神經(jīng)網(wǎng)絡(luò)1. 學(xué)習(xí)ANN模型ANN學(xué)習(xí)算法的目的是確定一組權(quán)值W，最小化誤差的平方和： (4.35) 圖4-18 兩個(gè)參數(shù)模型的誤差曲面E(W1，W

39、2)大多數(shù)情況下，由于激活函數(shù)的選擇(如S型或雙曲正切函數(shù))，ANN的輸出是參數(shù)的非線性函數(shù)。這樣，推導(dǎo)出W的全局最優(yōu)解變得不那么直接了。像基于梯度下降的方法等貪心算法可以很有效地求解優(yōu)化問題。梯度下降方法使用的權(quán)值更新公式可以寫成：(4.36)2. ANN學(xué)習(xí)中的設(shè)計(jì)問題在訓(xùn)練神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)分類任務(wù)之前，應(yīng)該先考慮以下設(shè)計(jì)問題：(1) 確定輸入層的結(jié)點(diǎn)數(shù)目。 (2) 確定輸出層的結(jié)點(diǎn)數(shù)目。 (3) 選擇網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，例如，隱藏層數(shù)和隱藏結(jié)點(diǎn)數(shù)，前饋還是遞歸網(wǎng)絡(luò)結(jié)構(gòu)。 (4) 初始化權(quán)值和偏置。隨機(jī)賦值常常是可取的。(5) 去掉有遺漏值的訓(xùn)練樣例，或者用最合理的值來代替。3. 人工神經(jīng)網(wǎng)絡(luò)的特

40、點(diǎn)人工神經(jīng)網(wǎng)絡(luò)的一般特點(diǎn)概括如下：(1) 至少含有一個(gè)隱藏層的多層神經(jīng)網(wǎng)絡(luò)是一種普適近似(Universal Approximator)，即可以用來近似任何目標(biāo)函數(shù)。由于ANN具有豐富的假設(shè)空間，因此對(duì)于給定的問題，選擇合適的拓?fù)浣Y(jié)構(gòu)來防止模型的過分?jǐn)M合是很重要的。(2) ANN可以處理冗余特征，因?yàn)闄?quán)值在訓(xùn)練過程中自動(dòng)學(xué)習(xí)。冗余特征的權(quán)值非常小。(3) 神經(jīng)網(wǎng)絡(luò)對(duì)訓(xùn)練數(shù)據(jù)中的噪聲非常敏感。處理噪聲問題的一種方法是使用確認(rèn)集來確定模型的泛化誤差；另一種方法是每次迭代把權(quán)值減少一個(gè)因子。(4) ANN權(quán)值學(xué)習(xí)使用的梯度下降方法經(jīng)常會(huì)收斂到局部最小值。避免局部最小值的方法是式中加上一個(gè)動(dòng)量項(xiàng)(Mo

41、mentum Term)。(5) 訓(xùn)練ANN是一個(gè)很耗時(shí)的過程，特別是當(dāng)隱藏結(jié)點(diǎn)數(shù)量很大時(shí)。然而，測(cè)試樣例分類時(shí)非常快。4.6 支 持 向 量 機(jī)支持向量機(jī)(Support Vector Machine，SVM)已經(jīng)成為一種備受關(guān)注的分類技術(shù)。這種技術(shù)具有堅(jiān)實(shí)的統(tǒng)計(jì)學(xué)理論基礎(chǔ)，并在許多實(shí)際應(yīng)用(如手寫數(shù)字的識(shí)別、文本分類等)中展示了大有可為的實(shí)踐效用。此外，SVM可以很好地應(yīng)用于高維數(shù)據(jù)，避免了維災(zāi)難問題。這種方法具有一個(gè)獨(dú)特的特點(diǎn)：它使用訓(xùn)練實(shí)例的一個(gè)子集來表示決策邊界。該子集稱做支持向量(Support Vector)。4.6.1 最大邊緣超平面圖4-19顯示了一個(gè)數(shù)據(jù)集，包含屬于兩個(gè)不同

42、類的樣本，分別用方塊和圓圈表示。 圖4-19 一個(gè)線性可分?jǐn)?shù)據(jù)集上的可能決策邊界為了更好地理解不同的超平面對(duì)泛化誤差的影響，考慮兩個(gè)決策邊界B1和B2，如圖4-20所示。 圖4-20 決策邊界的邊緣統(tǒng)計(jì)學(xué)習(xí)理論給出了線性分類器邊緣與其泛化誤差之間關(guān)系的形式化解釋，稱這種理論為結(jié)構(gòu)風(fēng)險(xiǎn)最小化(Structural Risk Minimization，SRM)理論。該理論根據(jù)分類器的訓(xùn)練誤差Re、訓(xùn)練樣本數(shù)N和模型的復(fù)雜度(即它的能力(Capacity)h，給出了分類器的泛化誤差的一個(gè)上界R。更明確地，在概率1-下，分類器的泛化誤差j在最壞情況下滿足下列公式： (4.37)4.6.2 線性支持向量

43、機(jī)：可分情況一個(gè)線性SVM是這樣一個(gè)分類器，它尋找具有最大邊緣的超平面，因此它也經(jīng)常被稱為最大邊緣分類器(Maximal Margin Classifier)。 1. 線性決策邊界考慮一個(gè)包含N個(gè)訓(xùn)練樣本的二元分類問題。每個(gè)樣本表示為一個(gè)二元組(xi，yi)(i=1，2，N)，其中xi=(xi1，xi2，xid)T，對(duì)應(yīng)于第i個(gè)樣本的屬性集。為方便計(jì)，令yi1，1表示它的類標(biāo)號(hào)。一個(gè)線性分類器的決策邊界可以寫成如下形式： (4.38)圖4-21顯示了包含圓圈和方塊的二維訓(xùn)練集。圖中的實(shí)線表示決策邊界，它將訓(xùn)練樣本一分為二，劃入各自的類中。任何位于決策邊界上的樣本都必須滿足公式(4.37)。例如

44、，如果xa和xb是兩個(gè)位于決策邊界上的點(diǎn)，則兩個(gè)方程相減便得到：圖4-21 SVM的決策邊界和邊緣對(duì)于任何位于決策邊界上方的方塊xs，可以證明：xs+b=k(4.39)其中，k0。類似地，對(duì)于任何位于決策邊界下方的圓圈xc，可以證明：xc+b=k(4.40)其中，k0。如果標(biāo)記所有的方塊的類標(biāo)號(hào)為+1，標(biāo)記所有的圓圈的類標(biāo)號(hào)為1，則可以用以下的方式預(yù)測(cè)任何測(cè)試樣本z的類標(biāo)號(hào)y： (4.41)2. 線性分類器的邊緣考慮那些離決策邊界最近的方塊和圓圈。由于該方塊位于決策邊界的上方，因此對(duì)于某個(gè)正值k，它必然滿足公式(4.38)；而對(duì)于某個(gè)負(fù)值k，圓圈必須滿足公式(4.40)。調(diào)整決策邊界的參數(shù)和b

45、，兩個(gè)平行的超平面bi1和bi2可以表示如下：bi1：x+b=+1(4.42)bi2：x+b=1(4.43) 決策邊界的邊緣由這兩個(gè)超平面之間的距離給定。為了計(jì)算邊緣，令x1是bi1上的一個(gè)數(shù)據(jù)點(diǎn)，x2是bi2上的一個(gè)數(shù)據(jù)點(diǎn)，如圖4-21所示。將x1和x2分別代入公式(4.42)和(4.43)中，則邊緣d可以通過兩式相減得到： (4.44)3. 學(xué)習(xí)線性SVM模型SVM的訓(xùn)練階段包括從訓(xùn)練數(shù)據(jù)中估計(jì)決策邊界的參數(shù)和b。選擇的參數(shù)必須滿足下面兩個(gè)條件： (4.45)這些條件要求所有類標(biāo)號(hào)為1的訓(xùn)練實(shí)例(即方塊)都必須位于超平面x+b=+1上或位于它的上方，而那些類標(biāo)號(hào)為1的訓(xùn)練實(shí)例(即圓圈)都必

46、須位于超平面x+b=1上或位于它的下方。這兩個(gè)不等式可以概括為如下更緊湊的形式： (4.46) 盡管前面的條件也可以用于其他線性分類器(包括感知器)，但是SVM增加了一個(gè)要求：其決策邊界的邊緣必須是最大的。然而，最大化邊緣等價(jià)于最小化下面的目標(biāo)函數(shù)： (4.47) 定義4.3 線性SVM(可分情況)：SVM的學(xué)習(xí)任務(wù)可以形式化地描述為以下被約束的優(yōu)化問題：首先，必須改寫目標(biāo)函數(shù)，考慮施加在解上的約束。新目標(biāo)函數(shù)稱為該優(yōu)化問題的拉格朗日算子：(4.48)為了最小化拉格朗日算子，必須對(duì)Lp關(guān)于和b求偏導(dǎo)，并令它們等于零： (4.49) (4.50) 處理不等式約束的一種方法就是把它變換成一組等式約

47、束。只要限制拉格朗日乘子非負(fù)，這種變換便是可行的。這種變換導(dǎo)致如下拉格朗日乘子約束，稱做Karuch-Kuhn-Tucher(KKT)條件： (4.51) (4.52) 對(duì)前面的優(yōu)化問題求解仍是一項(xiàng)十分棘手的任務(wù)，因?yàn)樗婕按罅繀?shù)：、b和i。通過將拉格朗日算子變換成僅包含拉格朗日乘子的函數(shù)(稱做對(duì)偶問題)，可以簡(jiǎn)化該問題。為了變換成對(duì)偶問題，首先將公式(4.49)和(4.50)代入到公式(4.48)中。這將導(dǎo)致該優(yōu)化問題的如下對(duì)偶公式：(4.53) 對(duì)偶拉格朗日算子和原拉格朗日算子的主要區(qū)別如下：(1) 對(duì)偶拉格朗日算子僅涉及拉格朗日乘子和訓(xùn)練數(shù)據(jù)，而原拉格朗日算子除涉及拉格朗日乘子外，還涉

48、及決策邊界的參數(shù)。盡管如此，這兩個(gè)優(yōu)化問題的解是等價(jià)的。(2) 公式(4.53)中的二次項(xiàng)前有個(gè)負(fù)號(hào)，這說明原來涉及拉格朗日算子LP的最小化問題已經(jīng)變換成了涉及對(duì)偶拉格朗日算子LD的最大化問題。對(duì)于大型數(shù)據(jù)集，對(duì)偶優(yōu)化問題可以使用數(shù)值計(jì)算技術(shù)來求解，如使用二次規(guī)劃。一旦找到一組i就可以通過公式(4.49)和(4.52)來求得和b的可行解。決策邊界可以表示成：(4.54) 【例4.4】 考慮圖4-22給出的二維數(shù)據(jù)集，它包含8個(gè)訓(xùn)練實(shí)例。使用二次規(guī)劃方法，可以求解公式(4.53)給出的優(yōu)化問題，得到每一個(gè)訓(xùn)練實(shí)例的拉格朗日乘子i，如圖4-22(a)的表的最后一列所示。圖4-22 一個(gè)線性可分?jǐn)?shù)據(jù)

49、集的例子令=(1，2)，b為決策邊界的參數(shù)。使用公式(4.48)，可以按如下方法求解1和2： 偏倚項(xiàng)b可以使用公式(4.51)對(duì)每個(gè)支持向量進(jìn)行計(jì)算：對(duì)b取平均值，得到b=7.93。對(duì)應(yīng)于這些參數(shù)的決策邊界顯示在圖4-22中。一旦確定了決策邊界的參數(shù)，檢驗(yàn)實(shí)例z可以按以下的公式來分類：如果f(z)=1，則檢驗(yàn)實(shí)例被分為到正類，否則分到負(fù)類。4.6.3 線性支持向量機(jī)：不可分情況圖4-23給出了一個(gè)和圖4-20相似的數(shù)據(jù)集，不同處在于它包含了兩個(gè)新樣本P和Q。盡管決策邊界B1誤分類了新樣本，而B2正確分類了它們，但是這并不意味著B2是一個(gè)比B1好的決策邊界，因?yàn)檫@些新樣本可能只是訓(xùn)練數(shù)據(jù)集中的噪

50、聲。B1可能仍然比B2更可取，因?yàn)樗哂休^寬的邊緣，從而對(duì)過分?jǐn)M合不太敏感。然而，上一節(jié)給出的SVM公式只能構(gòu)造沒有錯(cuò)誤的決策邊界。 圖4-23 不可分情況下SVW的決策邊界盡管公式(4.46)給定的原目標(biāo)函數(shù)仍然是可用的，但是決策邊界B1不再滿足公式(4.45)給定的所有約束。因此，必須放松不等式約束，以適應(yīng)非線性可分?jǐn)?shù)據(jù)，可以通過在優(yōu)化問題的約束中引入正值的松弛變量(Slack Variable)實(shí)現(xiàn)，如下式所示： (4.55)圖4-24可以幫助理解松弛變量i的意義。圓圈P是一個(gè)實(shí)例，它違反公式(4.45)給定的約束。設(shè)x+b=+1是一條經(jīng)過點(diǎn)P，且平行于決策邊界的直線?？梢宰C明它與超平面

51、x+b=+1之間的距離為多/|。因此，提供了決策邊界在訓(xùn)練樣本P上的誤差估計(jì)。圖4-24 不可分離數(shù)據(jù)的松弛變量理論上，可以使用和前面相同的目標(biāo)函數(shù)，然后加上公式(4.55)給定的約束來確定決策邊界。然而，由于在決策邊界誤分樣本的數(shù)量上沒有限制，學(xué)習(xí)算法可能會(huì)找到這樣的決策邊界：它的邊緣很寬，但是誤分了許多訓(xùn)練實(shí)例，如圖4-25所示。為了避免這個(gè)問題，必須修改目標(biāo)函數(shù)，以懲罰那些松弛變量值很大的決策邊界。修改后的目標(biāo)函數(shù)如下：圖4-25 一個(gè)具有寬邊緣但訓(xùn)練誤差很高的決策邊界由此，被約束的優(yōu)化問題的拉格朗日算子可以記作如下形式： (4.56)其中，前面兩項(xiàng)是需要最小化的目標(biāo)函數(shù)，第三項(xiàng)表示與松

52、弛變量相關(guān)的不等式約束，而最后一項(xiàng)是要求當(dāng)i的值非負(fù)的結(jié)果。此外，利用如下的KKT條件，可以將不等式約束變換成等式約束：i0， i0， i0(4.57)i(yi(xi+b)1+i)(4.58)ii=0(4.59) 令L關(guān)于、b和的一階導(dǎo)數(shù)為零，就得到如下公式： (4.60) (4.61) (4.62) 將公式(4.60)、(4.61)和(4.62)代入拉格朗日算子中，得到如下的對(duì)偶拉格朗日算子： (4.63) 4.6.4 非線性支持向量機(jī)1. 屬性變換為了說明怎樣進(jìn)行屬性變換可以導(dǎo)致一個(gè)線性的決策邊界，考察圖4-26(a)給出的二維數(shù)據(jù)集，它包含方塊(類標(biāo)號(hào)y=1)和圓圈(類標(biāo)號(hào)y=1)。數(shù)據(jù)

53、集是這樣生成的：所有的圓圈都聚集在圖的中心附近，而所有的方塊都分布在離中心較遠(yuǎn)的地方?？梢允褂孟旅娴墓綄?duì)數(shù)據(jù)集中的實(shí)例分類： (4.64) 因此，數(shù)據(jù)集的決策邊界可以表示如下：這可以進(jìn)一步簡(jiǎn)化為下面的二次方程： 需要一個(gè)非線性變換將數(shù)據(jù)從原先的特征空間映射到一個(gè)新的空間，決策邊界在這個(gè)空間下成為線性的。假定選擇下面的變換： (4.65) 在變換空間中，找到參數(shù)=(1，2，3，4，5)，使得：圖4-26 分類具有非線性決策邊界的數(shù)據(jù)2. 學(xué)習(xí)非線性SVM模型盡管屬性變換方法看上去大有可為，但是存在一些實(shí)現(xiàn)問題。首先，不清楚應(yīng)當(dāng)使用什么類型的映射函數(shù)，確?？梢栽谧儞Q后空間構(gòu)建線性決策邊界。一種可

54、能的選擇是把數(shù)據(jù)變換到無限維空間中，但是這樣的高維空間可能很難處理。其次，即使知道合適的映射函數(shù)，在高維特征空間中解決被約束的優(yōu)化問題仍然是計(jì)算代價(jià)很高的任務(wù)。為了解釋這些問題并考察處理它們的方法，假定存在一個(gè)合適的函數(shù)(x)來變換給定的數(shù)據(jù)集。變換后，需要構(gòu)建一個(gè)線性的決策邊界，把樣本劃分到它們各自所屬的類中。在變換空間中，線性決策邊界具有以下形式(x)+b=0 定義4.4 非線性SVM 一個(gè)非線性SVM的學(xué)習(xí)任務(wù)可以形式化表達(dá)為以下的優(yōu)化問題：注意，非線性SVM的學(xué)習(xí)任務(wù)和線性SVM(參見定義4.3)很相似。主要的區(qū)別在于，學(xué)習(xí)任務(wù)是在變換后的屬性(x)，而不是在原屬性x上執(zhí)行的。采用4.

55、6.2和4.6.3節(jié)介紹的線性SVM所使用的方法，可以得到該受約束的優(yōu)化問題的對(duì)偶拉格朗日算子： (4.66)使用二次規(guī)劃技術(shù)得到i后，就可以通過下面的方程導(dǎo)出參數(shù)和b： (4.67) (4.68) 這類似于公式(4.49)和(4.50)的線性SVM。最后，可以通過下式對(duì)檢驗(yàn)實(shí)例z進(jìn)行分類： (4.69)3. 核技術(shù)點(diǎn)積經(jīng)常用來度量?jī)蓚€(gè)輸入向量間的相似度。例如，余弦相似度可以定義為規(guī)范化后具有單位長(zhǎng)度的兩個(gè)向量間的點(diǎn)積。類似地，點(diǎn)積(x)(x)可以看做兩個(gè)實(shí)例xi和xj在變換空間中的相似性度量。核技術(shù)是一種使用原屬性集計(jì)算變換空間中的相似度的方法。考慮公式(4.65)中的映射函數(shù)。兩個(gè)輸入向量

56、u和v在變換空間中的點(diǎn)積可以寫成如下形式：(4.70) 該分析表明，變換空間中的點(diǎn)積可以用原空間中的相似度函數(shù)表示： (4.71) 圖4-27顯示了一個(gè)非線性決策邊界，它是通過使用公式(4.71)給出的多項(xiàng)式核函數(shù)的SVM獲得的。檢驗(yàn)實(shí)例z可以通過下式分類： (4.72)圖4-27 具有多項(xiàng)式核的非線性SVM產(chǎn)生的決策邊界4. Mercer定理定理4.1 Mercer定理 核函數(shù)k可以表示為：當(dāng)且僅當(dāng)對(duì)于任意滿足的函數(shù)g(x)， 則滿足定理4.1的核函數(shù)稱為正定(Positive Definite)核函數(shù)。下面給出一些這種函數(shù)的例子： (4.73) (4.74) (4.75)4.6.5 支持向

57、量機(jī)的特征SVM具有許多很好的性質(zhì)，已經(jīng)成為最廣泛使用的分類算法之一。下面簡(jiǎn)要總結(jié)一下SVM的一般特征：(1) SVM學(xué)習(xí)問題可以表示為凸優(yōu)化問題，因此可以利用已知的有效算法發(fā)現(xiàn)目標(biāo)函數(shù)的全局最小值，而其他的分類方法(如基于規(guī)則的分類器和人工神經(jīng)網(wǎng)絡(luò))都采用一種基于貪心學(xué)習(xí)的策略來搜索假設(shè)空間，這種方法一般只能獲得局部最優(yōu)解。(2) SVM通過最大化決策邊界的邊緣來控制模型的能力。盡管如此，用戶必須提供其他參數(shù)，如使用的核函數(shù)類型、為了引入松弛變量所需的代價(jià)函數(shù)C等。(3) 通過對(duì)數(shù)據(jù)中每個(gè)分類屬性值引入一個(gè)啞變量，SVM可以應(yīng)用于分類數(shù)據(jù)。例如，如果婚姻狀況有三個(gè)值單身，已婚，離異，可以對(duì)每

58、一個(gè)屬性值引入一個(gè)二元變量。(4) 本節(jié)所給出的SVM公式表述是針對(duì)二類問題的，SVM可擴(kuò)展到多類問題。4.7 預(yù) 測(cè)數(shù)值預(yù)測(cè)是對(duì)于給定的輸入預(yù)測(cè)連續(xù)值或有序值。 4.7.1 線性回歸直線回歸分析涉及一個(gè)響應(yīng)變量y和一個(gè)預(yù)測(cè)變量x。它是最簡(jiǎn)單的回歸形式，并用x的線性函數(shù)對(duì)y建模，即 y=b+wx (4.76)其中，y的方差假定為常數(shù)，b和w是回歸系數(shù)，分別表示直線的Y軸截距和斜率?；貧w系數(shù)b和w也可以看作權(quán)重，可以等價(jià)地記作 y=w0+w1x (4.77) 這些系數(shù)可以用最小二乘方法求解，它將最佳擬合直線估計(jì)為最小化實(shí)際數(shù)據(jù)與直線的估計(jì)值之間的誤差的直線。設(shè)D是訓(xùn)練集，由預(yù)測(cè)變量x的值和與它們

59、相關(guān)聯(lián)的響應(yīng)變量y的值組成。訓(xùn)練集包含|D|個(gè)形如(x1,y1)，(x2,y2)，(x|D|, y|D|)的數(shù)據(jù)點(diǎn)。回歸系數(shù)可以用下式估計(jì)： (4.78) (4.79)例4.5 使用最小二乘法的直線回歸。表4-3給出了一組成對(duì)的數(shù)據(jù)。其中x表示大學(xué)畢業(yè)后工作的年數(shù)，而y是對(duì)應(yīng)的年薪。這些二維數(shù)據(jù)可以用散布圖，如圖4-28所示。該圖暗示兩個(gè)變量x和y之間存在線性關(guān)系。用方程y=w0+w1x對(duì)年薪和工作年數(shù)之間的關(guān)系建模。圖4-28 例4.5中的表4-2的數(shù)據(jù)圖示多元線性回歸是直線回歸的擴(kuò)展，涉及多個(gè)預(yù)測(cè)變量。它允許響應(yīng)變量y用描述元組X的n個(gè)預(yù)測(cè)變量或?qū)傩訟1，A2，An的線性函數(shù)建模，其中X=

60、(x1，x2，xn)。訓(xùn)練數(shù)據(jù)集D包含形如(X1,y1)，(X2,y2)，(X|D|,y|D|)的數(shù)據(jù)，其中Xi是n維訓(xùn)練元組，yi是與Xi相關(guān)聯(lián)的響應(yīng)變量值。一個(gè)基于兩個(gè)預(yù)測(cè)屬性或變量A1和A2的多元線性回歸模型的例子是：y=w0+w1x1+w2x2 (4.80)4.7.2 非線性回歸【例4.6】 多項(xiàng)式回歸模型到線性回歸模型的變換?？紤]下式給出的三次多項(xiàng)式關(guān)系： y=w0+w1x+w2x2+w3x3 (4.81) 為了將該方程轉(zhuǎn)換成線性的，定義如下新變量：x1=x， x2=x2， x3=x3 方程(4.81)可以轉(zhuǎn)換成線性形式，結(jié)果為y=w0+w1x1+w2x2+w3x3 4.7.3 其他