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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、知識表示形式為決策樹，并最終可以形成產(chǎn)生式規(guī)則。1. 構(gòu)造決策樹設(shè)T為數(shù)據(jù)集，類別集合為C1，C2，Ck，選擇一個屬性V把T分為多個子集。設(shè)V有互不重合的n個取值v1，v2，vn，則T被分為n個子集T1，T2，Tn，這里Ti中的所有實例的取值均為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之間的任意取值都可以把實例集合分為兩部分，即 (4.20)可以看到一共有m1種分割情況。對屬性A的m1種分割的任意一種情況，作為該屬性的兩

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

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

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

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

22、Ci時數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設(shè)Ci稱為最大似然假設(shè)。否則，需要最大化P(X|Ci)P(Ci)。注意，假設(shè)不是等概率，那么類的先驗概率可以用P(Ci)=si/s計算，其中si是類Ci中的訓(xùn)練樣本數(shù)，而s是訓(xùn)練樣本總數(shù)。(4) 給定具有許多屬性的數(shù)據(jù)集，計算P(X|Ci)的開銷可能非常大。為降低計算P(X|Ci)的開銷，可以做類條件獨立的樸素假定。給定樣本的類標(biāo)號，假定屬性值相互條件獨立，即在屬性間不存在依賴關(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】 對于表4-2給出的訓(xùn)練數(shù)據(jù)，使用樸素貝葉斯方法進(jìn)行分類學(xué)習(xí)。解 數(shù)據(jù)樣本用屬性age，income,student和credit_rating描述。類標(biāo)號屬性buys_computer具有兩個不同值(即yes，no)。設(shè)C1對應(yīng)于類buys_computer=“Yes”，而C2對應(yīng)于類buys_computer=“No”。希望分類的未知樣本為X=(age=“ 30”,income=“medium”,student =“Yes”,credit_rating=“fair”)。需要最大化P(X|Ci)P(Ci)，i=1，2。每個

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

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

26、4.4.3 貝葉斯信念網(wǎng)1. 模型表示貝葉斯信念網(wǎng)絡(luò)(Bayesian Belief Networks，BBN)，簡稱貝葉斯網(wǎng)絡(luò)，用圖形表示一組隨機(jī)變量之間的概率關(guān)系。貝葉斯網(wǎng)絡(luò)有兩個主要成分：(1) 一個有向無環(huán)圖(dag)，表示變量之間的依賴關(guān)系。(2) 一個概率表，把各結(jié)點和它的直接父結(jié)點關(guān)聯(lián)起來。貝葉斯網(wǎng)絡(luò)的重要性質(zhì)表述如下：性質(zhì)1 條件獨立 貝葉斯網(wǎng)絡(luò)中的一個結(jié)點，如果它的父母結(jié)點已知，則它條件獨立于它的所有非后代結(jié)點。圖4-6(b)中，給定C，A條件獨立于B和D，因為B和D都是A的非后代結(jié)點。樸素貝葉斯分類器中的條件獨立假設(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ò)的一個例子，對心臟病或心口痛患者建模。假設(shè)圖中每個變量都是二值的。心臟病結(jié)點(HD)的父母結(jié)點對應(yīng)于影響該疾病的危險因素，例如鍛煉(E)和飲食(D)等。心臟病結(jié)點的子結(jié)點對應(yīng)于該病的癥狀，如胸痛(CP)和高血壓(BP)等。如圖4-7所示，心口痛(Hb)可能源于不健康的飲食，同時又可能導(dǎo)致胸痛。圖4-7 發(fā)現(xiàn)心臟病和心口痛病人的貝葉斯網(wǎng)影響疾病的危險因素對應(yīng)的結(jié)點只包含先驗概率，而心臟病、心口痛以及它們的相應(yīng)癥狀所對應(yīng)的結(jié)點都包含條件概率。為了節(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ò)的建模包括兩個步驟：創(chuàng)建網(wǎng)絡(luò)結(jié)構(gòu)；估計每一個結(jié)點的概率表中的概率值。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以通過對主觀的領(lǐng)域?qū)＜抑R編碼獲得。算法4.5給出了歸納貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一個系統(tǒng)的過程。算法4.5 貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的生成算法。例4.3 考慮圖4-7中的變量。執(zhí)行步驟1后，設(shè)變量次序為(E，D，HD，Hb，CP，BP)。從變量D開始，經(jīng)過步驟

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

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

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

32、性信息累計超出某一值時，神經(jīng)元被激活并傳遞出一個信息給其他神經(jīng)元，這個值稱為閾值(Threshold)。這種傳遞信息的神經(jīng)元為“興奮”性的。第二種情況是神經(jīng)元雖然接收到其他神經(jīng)元傳遞的信息，但沒有向外傳遞信息，此時，稱這個神經(jīng)元為“抑制”性的。圖4-9 McCulloch-Pitts認(rèn)知網(wǎng)絡(luò)在圖4-9中，wi為關(guān)聯(lián)權(quán)，表示神經(jīng)元對第i個晶枝接收到信息的感知能力。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é)為三個步驟： (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ù)。 (4.30) 識別和歸類問題中，如果采用階躍函數(shù)，當(dāng)輸出值為1時，可以肯定地說出輸入的歸類。階躍函數(shù)的缺點是數(shù)學(xué)性質(zhì)較差，如在x0點不光滑。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ò)去解決實際問題的過程稱為工作。圖4-11是前向型人工神經(jīng)網(wǎng)絡(luò)的計算流程。 圖4-11 前向型人工神經(jīng)網(wǎng)絡(luò)的計算流4.5.2 感知器考慮圖4-12中的圖和表。圖(a)所示的表顯示一個數(shù)據(jù)集，包含三個布爾變量(x1，x2，x3)和一個輸出變量y，當(dāng)三個輸入中至少有兩個是0時，y取1，而至少有兩個

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

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

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

38、。這些激活函數(shù)允許隱藏結(jié)點和輸出結(jié)點的輸出值與輸入?yún)?shù)呈非線性關(guān)系。圖4-16 人工神經(jīng)網(wǎng)絡(luò)激活函數(shù)的類型這些附加的復(fù)雜性使得多層神經(jīng)網(wǎng)絡(luò)可以對輸入和輸出變量間更復(fù)雜的關(guān)系建模。例如，考慮上一節(jié)中描述的XOR問題。實例可以用兩個超平面進(jìn)行分類，這兩個超平面把輸入空間劃分到各自的類，如圖4-17(a)所示。因為感知器只能構(gòu)造一個超平面，所以它無法找到最優(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 兩個參數(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è)計問題在訓(xùn)練神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)分類任務(wù)之前，應(yīng)該先考慮以下設(shè)計問題：(1) 確定輸入層的結(jié)點數(shù)目。 (2) 確定輸出層的結(jié)點數(shù)目。 (3) 選擇網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，例如，隱藏層數(shù)和隱藏結(jié)點數(shù)，前饋還是遞歸網(wǎng)絡(luò)結(jié)構(gòu)。 (4) 初始化權(quán)值和偏置。隨機(jī)賦值常常是可取的。(5) 去掉有遺漏值的訓(xùn)練樣例，或者用最合理的值來代替。3. 人工神經(jīng)網(wǎng)絡(luò)的特

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

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

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

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

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

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

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

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

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

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

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

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

52、弛變量相關(guān)的不等式約束，而最后一項是要求當(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)代入拉格朗日算子中，得到如下的對偶拉格朗日算子： (4.63) 4.6.4 非線性支持向量機(jī)1. 屬性變換為了說明怎樣進(jìn)行屬性變換可以導(dǎo)致一個線性的決策邊界，考察圖4-26(a)給出的二維數(shù)據(jù)集，它包含方塊(類標(biāo)號y=1)和圓圈(類標(biāo)號y=1)。數(shù)據(jù)

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

54、能的選擇是把數(shù)據(jù)變換到無限維空間中，但是這樣的高維空間可能很難處理。其次，即使知道合適的映射函數(shù)，在高維特征空間中解決被約束的優(yōu)化問題仍然是計算代價很高的任務(wù)。為了解釋這些問題并考察處理它們的方法，假定存在一個合適的函數(shù)(x)來變換給定的數(shù)據(jù)集。變換后，需要構(gòu)建一個線性的決策邊界，把樣本劃分到它們各自所屬的類中。在變換空間中，線性決策邊界具有以下形式(x)+b=0 定義4.4 非線性SVM 一個非線性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)化問題的對偶拉格朗日算子： (4.66)使用二次規(guī)劃技術(shù)得到i后，就可以通過下面的方程導(dǎo)出參數(shù)和b： (4.67) (4.68) 這類似于公式(4.49)和(4.50)的線性SVM。最后，可以通過下式對檢驗實例z進(jìn)行分類： (4.69)3. 核技術(shù)點積經(jīng)常用來度量兩個輸入向量間的相似度。例如，余弦相似度可以定義為規(guī)范化后具有單位長度的兩個向量間的點積。類似地，點積(x)(x)可以看做兩個實例xi和xj在變換空間中的相似性度量。核技術(shù)是一種使用原屬性集計算變換空間中的相似度的方法?？紤]公式(4.65)中的映射函數(shù)。兩個輸入向量

56、u和v在變換空間中的點積可以寫成如下形式：(4.70) 該分析表明，變換空間中的點積可以用原空間中的相似度函數(shù)表示： (4.71) 圖4-27顯示了一個非線性決策邊界，它是通過使用公式(4.71)給出的多項式核函數(shù)的SVM獲得的。檢驗實例z可以通過下式分類： (4.72)圖4-27 具有多項式核的非線性SVM產(chǎn)生的決策邊界4. Mercer定理定理4.1 Mercer定理 核函數(shù)k可以表示為：當(dāng)且僅當(dāng)對于任意滿足的函數(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é)一下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ù)類型、為了引入松弛變量所需的代價函數(shù)C等。(3) 通過對數(shù)據(jù)中每個分類屬性值引入一個啞變量，SVM可以應(yīng)用于分類數(shù)據(jù)。例如，如果婚姻狀況有三個值單身，已婚，離異，可以對每

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

59、相關(guān)聯(lián)的響應(yīng)變量y的值組成。訓(xùn)練集包含|D|個形如(x1,y1)，(x2,y2)，(x|D|, y|D|)的數(shù)據(jù)點。回歸系數(shù)可以用下式估計： (4.78) (4.79)例4.5 使用最小二乘法的直線回歸。表4-3給出了一組成對的數(shù)據(jù)。其中x表示大學(xué)畢業(yè)后工作的年數(shù)，而y是對應(yīng)的年薪。這些二維數(shù)據(jù)可以用散布圖，如圖4-28所示。該圖暗示兩個變量x和y之間存在線性關(guān)系。用方程y=w0+w1x對年薪和工作年數(shù)之間的關(guān)系建模。圖4-28 例4.5中的表4-2的數(shù)據(jù)圖示多元線性回歸是直線回歸的擴(kuò)展，涉及多個預(yù)測變量。它允許響應(yīng)變量y用描述元組X的n個預(yù)測變量或?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)變量值。一個基于兩個預(yù)測屬性或變量A1和A2的多元線性回歸模型的例子是：y=w0+w1x1+w2x2 (4.80)4.7.2 非線性回歸【例4.6】 多項式回歸模型到線性回歸模型的變換。考慮下式給出的三次多項式關(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 其他