機(jī)器學(xué)習(xí)基礎(chǔ)教程課件：分類與聚類學(xué)習(xí)算法

分類與聚類學(xué)習(xí)算法緒論5.1分類學(xué)習(xí)算法5.1.1線性分類算法5.1.2非線性分類算法5.1.3核方法與支持向量機(jī)5.2聚類學(xué)習(xí)方法5.2.1K均值聚類算法

5.2.2其他聚類算法

分類（classification）和聚類（clustering）是機(jī)器學(xué)習(xí)的基本問題。

分類是一種監(jiān)督學(xué)習(xí)方法，必須事先明確地知道各類別的信息，且所有待分類樣本都有一個(gè)類別與之對(duì)應(yīng)。很多時(shí)候無法滿足上述條件，如處理海量數(shù)據(jù)時(shí)候，這時(shí)候可以考慮聚類分析。

聚類是將數(shù)據(jù)集劃分為多個(gè)簇的過程，每個(gè)簇由若干樣本構(gòu)成，并滿足某種度量為標(biāo)準(zhǔn)的相似性。這種相似性在同一聚類之間最小，而在不同聚類之間最大。5.1分類學(xué)習(xí)算法

分類學(xué)習(xí)算法在實(shí)際中有大量的應(yīng)用，也是眾多復(fù)雜算法的基礎(chǔ)。分類學(xué)習(xí)算法有線性與非線性之分。線性分類就是用一個(gè)“超平面”將正、負(fù)樣本隔離開，如用一條直線對(duì)二維平面上的正、負(fù)樣本進(jìn)行分類，用一個(gè)平面對(duì)三維空間內(nèi)的正、負(fù)樣本進(jìn)行分類，用一個(gè)超平面對(duì)N維空間內(nèi)的正、負(fù)樣本進(jìn)行分類。相反，非線性分類則是用一個(gè)“超曲面”或多個(gè)超平（曲）面的組合將正、負(fù)樣本隔離開，如用一條曲線或折線對(duì)二維平面上的正、負(fù)樣本進(jìn)行分類，用一個(gè)曲面或者折面對(duì)三維空間內(nèi)的正、負(fù)樣本進(jìn)行分類，用一個(gè)超曲面對(duì)N維空間內(nèi)的正、負(fù)樣本進(jìn)行分類。5.1.1線性分類算法

一個(gè)分類問題是否屬于線性可分，取決于是否有可能找到一個(gè)點(diǎn)、直線、平面或超平面來分離開兩個(gè)相鄰的類別。如果每個(gè)類別的分布范圍本身是全連通的單一凸集，且互不重疊，則這兩個(gè)類別一定是線性可分的，如圖5.1所示。線性分類算法主要有線性回歸、邏輯回歸分類、單層感知器等。圖5.1線性可分情況1.線性擬合（回歸）分類方法線性擬合分類方法是求解直線（或超平面）問題求解的常見算法。這種方法可以用來進(jìn)行數(shù)據(jù)分類：如圖5.1所示，可以擬合一條直線（或超平面）作為兩種類別的“分界線（面）”，通過對(duì)數(shù)據(jù)與分類面之間的關(guān)系可以對(duì)兩類數(shù)據(jù)進(jìn)行分類和區(qū)別。線性擬合的目標(biāo)是找到一個(gè)函數(shù)，能將輸入屬性x映射到輸出（目標(biāo)）屬性y，在機(jī)器學(xué)習(xí)領(lǐng)域可將該映射模型記為上述模型還需要一個(gè)參數(shù)集合（常以符號(hào)θ表示），機(jī)器學(xué)習(xí)的任務(wù)就是從給定的數(shù)據(jù)集（訓(xùn)練集）中“學(xué)習(xí)”到擬合參數(shù)集θ。因此，式（5.1）常寫作如下形式

假設(shè)二元分類問題的正、負(fù)樣本分別用1和0表示。這樣，用線性擬合方法求解分類問題時(shí)，可設(shè)定一個(gè)閾值t（如t=0.5），使時(shí)預(yù)測(cè)，使時(shí)預(yù)測(cè)0。假設(shè)，產(chǎn)品的重量決定產(chǎn)品是否合格，將該方法用于某產(chǎn)品質(zhì)量檢測(cè)時(shí)方案如圖5.2所示，其中“○”表示合格、“?”表示不合格。用線性擬合得到的正好是一條直線，正好能夠?qū)a(chǎn)品質(zhì)量合格和不合格分開。圖5.2線性回歸算法求解分類問題

線性擬合算法試圖用一條直線去擬合只有兩種取值的離散樣本，通常并不適合分類問題：①線性回歸算法用于分類問題的預(yù)測(cè)值是連續(xù)的數(shù)值型，可能會(huì)超出[0,1]范圍，不利于類別解釋；②當(dāng)類別不平衡（正、負(fù)樣本數(shù)量上差別非常大）或者少數(shù)樣本點(diǎn)較為遠(yuǎn)離時(shí)，常造成模型偏向某個(gè)類別以至形成錯(cuò)誤分類。如圖5.3所示，有的樣本遠(yuǎn)離，造成錯(cuò)誤分類現(xiàn)象。圖5.3線性回歸算法錯(cuò)誤分類例子

假設(shè)由兩個(gè)類別：和，它們屬于同一個(gè)樣本空間Ω，在類別中的數(shù)據(jù)概率密度函數(shù)為，在類別中的數(shù)據(jù)概率密度函數(shù)為。如果將中的數(shù)據(jù)錯(cuò)分到中，則其條件概率為：而將中的數(shù)據(jù)錯(cuò)分到中，則其條件概率為：

其中，。若令為類別的先驗(yàn)概率，為類別的先驗(yàn)概率，則有。則分類情況應(yīng)為先驗(yàn)概率與條件概率的乘積，可以用表5.1表示。關(guān)于錯(cuò)誤分類的情況可以形象地用圖5.4來說明。

數(shù)據(jù)實(shí)際屬于類別π1數(shù)據(jù)實(shí)際屬于類別π2分類操作結(jié)果屬于類別π1分類操作結(jié)果屬于類別π2表5.1分類情況表圖5.4錯(cuò)誤分類概率情況圖

分類情況的好壞可以使用錯(cuò)誤分類代價(jià)（簡(jiǎn)稱錯(cuò)分代價(jià)）來進(jìn)行衡量。由于正確分類沒有出現(xiàn)錯(cuò)誤，因此正確分類的錯(cuò)分代價(jià)為0。而將本來屬于類別的數(shù)據(jù)錯(cuò)分為類別的錯(cuò)分代價(jià)為；同樣的，將本來屬于類別的數(shù)據(jù)錯(cuò)分為類別的錯(cuò)分代價(jià)為。在兩分類的情況下，綜合所有的因素，可以使用期望錯(cuò)分代價(jià)（ECM）來進(jìn)行評(píng)價(jià)：優(yōu)良的分類結(jié)果應(yīng)該式（5.5）的錯(cuò)分代價(jià)最小。對(duì)于圖5.4所示的兩個(gè)分類區(qū)域，應(yīng)該有：對(duì)于R2有：對(duì)于有：對(duì)于有：

對(duì)于兩個(gè)同屬于正態(tài)分布的數(shù)據(jù)集，其聯(lián)合概率密度函數(shù)為：

（5.8）

其中，為兩個(gè)正態(tài)總體的期望，

為其方差，而且這兩個(gè)方差預(yù)設(shè)為相等，則分類后的最小ECM為：

（5.9）

（5.10）上兩式中，指數(shù)函數(shù)的自變量有：

（5.11）

于是式（5.9）和式（5.10）取對(duì)數(shù)，變成：

（5.12）

（5.13）

在實(shí)際處理過程中，可以將均值代替期望

，樣本協(xié)方差陣代陣代替

。分類函數(shù)的形式由式（5.2）給出，對(duì)于兩重分類的分類函數(shù)應(yīng)該有：

（5.14）

式中，為兩類數(shù)據(jù)的均值（期望），S為兩類數(shù)據(jù)相同的協(xié)方差陣。對(duì)式（5.14）有：

(5.15)

可得線性分類函數(shù)為：

(5.16)

對(duì)于兩類方差不同的總體，其分類域變?yōu)椋?5.17)

(5.18)

式中，(5.19)

可見，當(dāng)兩個(gè)總體的方差相同時(shí),將其代入式（5.19）。式（5.17）、（5.18）就退化為式（5.12）、（5.13）。

對(duì)于多個(gè)正態(tài)總體的數(shù)據(jù)集進(jìn)行分類，可以將兩類數(shù)據(jù)的分類方法進(jìn)行推廣。對(duì)于期望錯(cuò)分代價(jià)函數(shù)來講，如果有n類數(shù)據(jù)，且將第一類數(shù)據(jù)錯(cuò)分為各個(gè)n-1類的數(shù)據(jù)，則借鑒兩個(gè)總體期望錯(cuò)分代價(jià)函數(shù)的情況，有：

以此類推，可得到總的期望錯(cuò)分代價(jià)函數(shù)為：式中，為各類數(shù)據(jù)的先驗(yàn)概率。

對(duì)于多重分類的線性分類函數(shù)，有：

（5.21）式中，為組間交叉乘積和，為組內(nèi)樣本矩陣。線性組合

為樣本數(shù)據(jù)第一判別量，依次可以得到第k判別量。2.邏輯斯蒂（Logistic）回歸分類（1）決策邊界與決策區(qū)域

邏輯斯蒂（Logistic）回歸分類是應(yīng)用最為廣泛的分類學(xué)習(xí)算法。其“回歸”并不是真正意義上的回歸或擬合，其目標(biāo)屬性不是連續(xù)的數(shù)值型，而是離散的標(biāo)稱型。邏輯斯蒂（Logistic）回歸算法使用Sigmoid函數(shù)（簡(jiǎn)稱S函數(shù)）作為分類問題的假設(shè)函數(shù)，滿足分類問題預(yù)測(cè)值在[0,1]區(qū)間這一性質(zhì)。Sigmoid函數(shù)表達(dá)式如下

（5.22）Sigmoid函數(shù)很好地近似了階躍函數(shù)，且連續(xù)光滑，嚴(yán)格單調(diào)遞增，并以（0,0.5）中心點(diǎn)對(duì)稱，即當(dāng)輸入大于0時(shí)輸出趨于1，當(dāng)輸入小于0時(shí)輸出趨于0，當(dāng)輸入等于0時(shí)輸出正好為0.5，如圖5.4所示。此外，Sigmoid函數(shù)容易求導(dǎo)，其導(dǎo)數(shù)為

（5.23）圖5.5Sigmoid函數(shù)曲線

這樣，可通過Sigmoid函數(shù)對(duì)進(jìn)行變換，使其取值壓縮在“[0,1]”范圍，即顯然，當(dāng)時(shí)，預(yù)測(cè)樣本x為正例；當(dāng)，預(yù)測(cè)樣本x為負(fù)例；當(dāng)時(shí)，，稱為樣本分類的決策邊界。如圖5.6展示了二維數(shù)據(jù)的決策邊界圖5.6決策邊界為直線

這樣，特征空間被決策邊界劃分成不同的區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)類別，稱為決策區(qū)域。當(dāng)我們判定待識(shí)別的樣本位于某個(gè)決策區(qū)域時(shí)，就判決它可以劃歸到對(duì)應(yīng)的類別中。需要注意的是，決策區(qū)域包含類別中樣本的分布區(qū)域，但不等于類別的真實(shí)分布范圍。

這樣，準(zhǔn)則函數(shù)可以表達(dá)成N個(gè)樣本的負(fù)對(duì)數(shù)似然代價(jià)均值式中，和分別表示第k個(gè)樣本的輸入和輸出；N為樣本總個(gè)數(shù)。使用梯度下降法可以求解出使取極值最小的最優(yōu)參數(shù)。梯度下降基本思想是，隨機(jī)選取一組參數(shù)初值，計(jì)算代價(jià)，然后尋找能讓代價(jià)在數(shù)值上下降最多的另一組參數(shù)，反復(fù)迭代直到達(dá)到一個(gè)局部最優(yōu)。梯度下降參數(shù)更新公式如下求導(dǎo)得

代入得，上式就是邏輯斯蒂回歸算法的核心遞推公式。通過不斷更新參數(shù)集，直到達(dá)到收斂，此時(shí)得到的參數(shù)即為。圖5.6所得決策邊界即采用邏輯回歸算法所得，其準(zhǔn)則函數(shù)隨迭代次數(shù)變化如圖5.7所示，可見最終準(zhǔn)則函數(shù)趨于0。3.單層感知器

感知器模型如第四章圖4.2所示，是一種神經(jīng)元模型，沒有反饋和內(nèi)部狀態(tài)，是對(duì)多個(gè)輸入量加權(quán)求和后確定輸出的值。顯然，感知器是一個(gè)多輸入單輸出的非線性系統(tǒng)。

顯然，感知器沒有反饋和內(nèi)部狀態(tài)，是多輸入單輸出的非線性系統(tǒng)。其輸入與輸出滿足如下關(guān)系：(5.30)

感知器算法的具體步驟可表達(dá)如下：1）設(shè)定初始參數(shù)集，s=0;2)對(duì)訓(xùn)練樣本集的所有規(guī)范化增廣特征向量進(jìn)行分類，將分類錯(cuò)誤的樣本（即不滿足的樣本）放入集合中；3）利用公式（5.35）更新參數(shù)集；4）返回步驟2），直至所有的樣本都被正確分類為止。此時(shí)參數(shù)集即為求得的最優(yōu)值。顯然，感知器算法中遞推步長(zhǎng)決定了每次對(duì)參數(shù)集修正的幅度，其大小直接影響迭代速度和精度。一般，遞推步長(zhǎng)選擇有如下方式：1）固定值。即選擇固定的非負(fù)數(shù)；

2）絕對(duì)修正。在單樣本修正算法中，為保證分類錯(cuò)誤的樣本在對(duì)參數(shù)集合進(jìn)行一次修正后能正確分類，需要滿足，代入遞推修正公式（5.35）得解得，3）部分修正。若滿足式（5.38）則稱部分修正。4）變步長(zhǎng)法。可以取按照某種規(guī)律逐步減小的，使得算法開始時(shí)收斂較快，接近最優(yōu)解時(shí)收斂速度變慢，以提高求解的精度。比較常用的變步長(zhǎng)法是取5）最優(yōu)步長(zhǎng)法。在每一次迭代時(shí)，通過求準(zhǔn)則函數(shù)對(duì)于不同的的最小值，來確定最優(yōu)的。該方法會(huì)帶來更大的計(jì)算量。5.1.2非線性分類算法

線性分類器可以實(shí)現(xiàn)線性可分的類別之間的分類決策，其形式簡(jiǎn)單，分類決策快速。但在許多實(shí)際分類問題中，兩個(gè)類別的樣本之間并沒有明確的分類決策邊界，線性分類器無法完成分類任務(wù)。線性不可分情況典型如下：①分布范圍是凹的類別的凸包與另一類別分布范圍重疊（如圖5.8a所示）；②類別的分布范圍由兩個(gè)以上不連通區(qū)域構(gòu)成，如異或（XOR）問題（如圖5.8b所示）。（a）凹集凸包與凸集重疊（b）異或問題圖5.8線性不可分情況1.多項(xiàng)式邏輯回歸算法

大多數(shù)情況，無法用一條直線將不同的類別分開（如圖5.9所示）。圖5.9決策邊界復(fù)雜情況圖5.10多項(xiàng)式邏輯回歸的決策邊界2.貝葉斯分類器

貝葉斯分類器是一種基于統(tǒng)計(jì)的分類器，原理如下：確定某樣本的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率（該樣本屬于某一類的概率），選擇具有最大后驗(yàn)概率的類別作為樣本的所屬類別。（1）貝葉斯理論改寫成（2）樸素貝葉斯分類算法例5.1人的心情受活動(dòng)、天氣、地點(diǎn)、是否獨(dú)處等環(huán)境條件影響。近段時(shí)間來，小明情緒波動(dòng)較大，其中心情愉悅情況10次，心情欠佳情況5次。為此，他將當(dāng)時(shí)的活動(dòng)、天氣、地點(diǎn)、是否獨(dú)處等情況做了詳細(xì)的記錄，并統(tǒng)計(jì)如下表

請(qǐng)預(yù)測(cè)某天天氣晴、小明一個(gè)人在校外看電影時(shí)他的心情。環(huán)境心情環(huán)境心情愉悅欠佳愉悅欠佳活動(dòng)看電影31天氣晴天52逛街42雨天20考試32陰天33地點(diǎn)學(xué)校53是否獨(dú)處獨(dú)處32校外52有伴73解：將“天氣晴、小明一個(gè)人在校外看電影”記為事件X。首先，分別計(jì)算心情愉悅和心情欠佳的先驗(yàn)概率：，然后，分別計(jì)算心情愉悅和心情欠佳的類條件概率：

第三，分別計(jì)算心情愉悅和心情欠佳的后驗(yàn)概率最后，事件X導(dǎo)致小明心情愉悅和心情欠佳概率分別為，（3）特殊問題

下面，我們討論樸素貝葉斯分類算法遇到的兩類特殊問題。

①如果訓(xùn)練樣本集中有的屬性值一次都沒有出現(xiàn)（如表5.2中，在心情欠佳時(shí)，天氣為雨天的樣本一次也沒有出現(xiàn)），即其條件屬性概率為0。這時(shí)，計(jì)算該屬性的類條件概率時(shí)，各項(xiàng)屬性都需乘以該0值，導(dǎo)致不管其他數(shù)值的概率有多大，最終乘積都為0。顯然這是不合理的，不能因?yàn)闆]有觀察到某事件，就認(rèn)為該事件發(fā)生的概率為0。當(dāng)這種屬性值一次都沒有出現(xiàn)的情況出現(xiàn)較多時(shí)，在歸一化后求取最終的條件概率時(shí)，甚至?xí)l(fā)生0除以0的現(xiàn)象。

對(duì)于這種情況，通常采用拉普拉斯平滑進(jìn)行處理。以例5.1中心情欠佳時(shí)的天氣情況概率為例。根據(jù)表5.2，當(dāng)心情欠佳時(shí)天氣晴天、雨天和陰天的概率分別為2/5、0/5、3/5。

此時(shí)，選擇一個(gè)很小的常數(shù)，按如下形式進(jìn)行平滑理：、、。其中，、、需滿足。②有的訓(xùn)練樣本集不僅有離散的標(biāo)稱屬性，還有連續(xù)的數(shù)值屬性，如例5.1，若小明在記錄的時(shí)候?qū)?dāng)時(shí)的溫度、濕度用數(shù)值記錄下來，這就變成了混合問題。對(duì)混合問題，樸素貝葉斯分類算法有兩種處理方法：一種方法是將數(shù)值屬性離散化，轉(zhuǎn)換為常規(guī)的離散標(biāo)稱屬性；另一種方法是假設(shè)數(shù)值屬性符號(hào)正態(tài)分布，根據(jù)訓(xùn)練樣本計(jì)算出正太分布的參數(shù)，然后再計(jì)算測(cè)試樣本某個(gè)數(shù)值屬性出現(xiàn)的概率，并以該概率作為條件概率代入式（5.31）和（5.32）中求解。下面通過例5.2演示如何解決上述兩類特殊問題。例5.2

小明喜歡戶外“驢行”，表5.3是近來小明“驢行”的情況統(tǒng)計(jì)。其中，“天氣”和“空氣質(zhì)量”等離散型屬性為統(tǒng)計(jì)次數(shù)；“溫度”、“濕度”等連續(xù)數(shù)值型屬性為數(shù)值，單位分別為“℃”和“%”。

請(qǐng)預(yù)測(cè)某天下雨、氣溫20℃、濕度90%、空氣重度污染時(shí)小明是否外出“驢行”。天氣“驢行”溫度“驢行”濕度“驢行”空氣質(zhì)量“驢行”是否是否是否是否晴天83

2535

8590良好92雨天01

1822

7560輕度污染12陰天21

2319

6065重度污染01

1930

7095

3110

5585

22

90

16

80

30

75

26

80

17

90

表5.3小明“驢行”與否與條件情況統(tǒng)計(jì)解：將“天氣晴、小明一個(gè)人在校外看電影”記為事件X。首先，分別計(jì)算“驢行”=“是”和“驢行”=“否”的先驗(yàn)概率。根據(jù)上表統(tǒng)計(jì)，“驢行”=“是”的次數(shù)為10次，“驢行”=“否”的次數(shù)為5次，故，然后，分別計(jì)算“驢行”=“是”和“驢行”=“否”條件下各項(xiàng)屬性的類條件概率。①在計(jì)算和時(shí)，會(huì)遇到第1類問題，即為該屬性值的樣本一次也沒出現(xiàn)。此時(shí)，進(jìn)行拉普拉斯平滑處理，則：

這樣，對(duì)于“驢行”=“是”和“驢行”=“否”條件下的“天氣”和“空氣質(zhì)量”各屬性的類條件概率匯總?cè)缦卤恚孩趯?duì)于含數(shù)值屬性的“溫度”和“濕度”，假設(shè)均符合正態(tài)分布。這樣，對(duì)于“溫度”和“濕度”屬性，為“是”類別的樣本均為10個(gè)，為“否”類別的樣本均為5個(gè)。按下式分別計(jì)算各組數(shù)據(jù)的均值和標(biāo)準(zhǔn)差。匯總?cè)缦卤恚哼@樣，對(duì)于屬性值為“x”的樣本，均值和標(biāo)準(zhǔn)差均已知，其正態(tài)分布的概率密度函數(shù)可按下式計(jì)算：對(duì)于“氣溫20℃”、“濕度90%”按上式計(jì)算得：

第三，以概率密度代替概率值，分別計(jì)算在事件X條件下“驢行”=“是”和“驢行”=“否”的后驗(yàn)概率：

最后，事件X導(dǎo)致小明外出“驢行”和不外出“驢行”概率分別為貝葉斯分類器給出的下雨、氣溫20℃、濕度90%、空氣重度污染時(shí)，小明不外出“驢行”概率達(dá)99.9936%。故，小明不會(huì)外出“驢行”。5.1.3核方法與支持向量機(jī)

核方法的基本思想是，將原始數(shù)據(jù)通過某種非線性映射到高維空間，再利用線性方法分析和處理數(shù)據(jù)。支持向量機(jī)（SupportVectorMachine，SVM）是一種由監(jiān)督學(xué)習(xí)，其基本思想是將樣本向量映射到高維空間中，尋求一個(gè)最優(yōu)區(qū)分兩類數(shù)據(jù)的超平面，使各分類到超平面的距離最大，亦稱大間距分隔機(jī)。顯然，SVM使用了核方法，使用不同的核函數(shù)形成了不同的SVM算法。1.核方法核方法認(rèn)為，將低維空間中不可線性分割的數(shù)據(jù)集，映射到高維空間中時(shí)，很可能變成線性可分的。例如，對(duì)于一維特征空間中線性不可分問題（如圖5.11a），可設(shè)定判別函數(shù)J(x)=(x-a)(x-b)(5.52)（a）一維線性不可分問題（b）二維線性可分問題圖5.11將一維線性不可分問題轉(zhuǎn)化為二維線性可分問題

則可通過的正負(fù)來判別x的類別：當(dāng)時(shí)，x屬于類別1，當(dāng)，x屬于類別2。

進(jìn)一步，令，，則原始一維特征空間就映射到二維特征空間即，上述一維線性問題涉及的數(shù)據(jù)在二維特征空間映射為一條拋物線。其判別函數(shù)（式（5.52））轉(zhuǎn)換為其決策邊界在二維特征空間為一條直線。這樣，決策邊界將拋物線分割為兩部分，實(shí)現(xiàn)了線性分割。其中，在決策邊界下部（）為類別1，在決策邊界上部（）為類別2。

設(shè)原始數(shù)據(jù)集（輸入變量x）在低維空間X中，通過變換將映射到目標(biāo)高維空間H中。若存在，使得則稱為核函數(shù)。對(duì)于目標(biāo)高維空間H，一般維數(shù)比較高，難以求其內(nèi)積。通過核技巧可巧妙地解決該問題，即不顯式定義和計(jì)算映射函數(shù)，而是通過低維空間點(diǎn)的核函數(shù)計(jì)算高維空間向量的內(nèi)積。這樣，就只涉及映射后特征向量的內(nèi)積計(jì)算，而不直接計(jì)算的值，可以有效避免維度禍根（curseofdimension）問題，也減少了計(jì)算量。下面，以二階多項(xiàng)式變換進(jìn)一步說明核方法。設(shè)對(duì)n維數(shù)據(jù)的二階多項(xiàng)式映射函數(shù)為

則，高維特征向量的內(nèi)積（核函數(shù)）可表示為

即，將映射函數(shù)和內(nèi)積運(yùn)算巧妙地轉(zhuǎn)換成原始特征的內(nèi)積運(yùn)算，可有效地加快運(yùn)算速度。

一般，核函數(shù)K(x,y)都是由經(jīng)驗(yàn)選定，然后通過實(shí)驗(yàn)驗(yàn)證該選擇的有效性。常用的核函數(shù)有如下幾類：（1）線性核函數(shù)，式中，c為可選常數(shù)。（2）多項(xiàng)式核函數(shù)，式中，c為可選常數(shù)；d為最高次項(xiàng)次數(shù)。（3）高斯核函數(shù)，式中，為高斯核帶寬。越大，高斯核函數(shù)越平滑，泛化能力越差；越小，高斯核函數(shù)變化越劇烈，泛化能力越強(qiáng)。（4）拉普拉斯核函數(shù)，式中，為參數(shù)。（5）Sigmoid核函數(shù)，式中，，tanh為雙曲正切函數(shù)；c為可選常數(shù)，一般為數(shù)據(jù)維數(shù)的倒數(shù)。此外，核函數(shù)的組合亦是核函數(shù)。設(shè)和是核函數(shù)，則（1）其線性組合是核函數(shù)，式中，、為任意正數(shù)。（2）其直積是核函數(shù)（3）組合亦是核函數(shù)式中，為任意函數(shù)。2.SVM問題數(shù)學(xué)描述對(duì)線性可分的二元分類問題，其分類決策邊界是高維特征空間中的超平面，其解有無窮多個(gè)（如圖5.12所示）。顯然，可以在一定范圍內(nèi)平移分類決策邊界（超平面），只要該決策邊界不達(dá)到或跨過各類別中距其最近的樣本，均可正確地實(shí)現(xiàn)線性分類。通常，將上述平移裕量d稱為分類間隔。圖5.12超平面、分類間隔與支持向量

設(shè)最優(yōu)決策邊界方程為注意式（5.64）與式（5.2）以及邏輯回歸中的的表達(dá)是一致的，區(qū)別在于將原來的改寫為c，并不再使用恒為1的。因此，采用SVM進(jìn)行二元分類時(shí)，可以通過符號(hào)函數(shù)將映射到不同的類別（設(shè)類別標(biāo)簽y分別為“-1”和“1”）上，則這樣，如果能確定和c，對(duì)于任意樣本，可以根據(jù)的正負(fù)號(hào)很快地確定其類別即。

由于只有1和-1兩種取值，上式實(shí)質(zhì)為因此，要使分類間隔最大，即要使樣本盡量遠(yuǎn)離決策邊界，使足夠大。而對(duì)于樣本數(shù)為N的整個(gè)訓(xùn)練集來說，其離決策邊界的最大距離由離該邊界最近的樣本決定。因此，要使訓(xùn)練集的分類間隔最大，應(yīng)使最近樣本的分類間隔盡可能的大，即應(yīng)盡可能的大。由幾何知識(shí)可知，樣本距決策邊界的距離為式中，表示參數(shù)向量的2-范式，即。

設(shè)訓(xùn)練集的分類間隔為d。由于訓(xùn)練集分類間隔由最近樣本決定，且決策邊界居中平分分類間隔。因此，有SVM的目標(biāo)是，尋找一個(gè)離決策邊界（超平面）最近的數(shù)據(jù)點(diǎn)的最大間隔，即要求d盡可能的大。因此，SVM分類問題的數(shù)學(xué)描述為將上兩式轉(zhuǎn)化為

為使式（5.71）的解有唯一確定值，常令。這樣，訓(xùn)練集的分類間隔為d重新定義為SVM分類問題的數(shù)學(xué)描述變?yōu)樯鲜骄褪荢VM的基本形式。3.線性支持向量機(jī)SVM的基本形式是一個(gè)標(biāo)準(zhǔn)的二次規(guī)劃問題，可直接利用現(xiàn)成的優(yōu)化計(jì)算包求解，但求解效率慢。一般，通過對(duì)每條約束引入拉格朗日乘子，將SVM問題轉(zhuǎn)換為更易求解的“對(duì)偶問題”進(jìn)行求解。在拉格朗日乘子法轉(zhuǎn)換過程中還可引入核函數(shù)，便于將SVM算法推廣到非線性分類問題。這樣，式（5.73）的拉格朗日函數(shù)表達(dá)如下其對(duì)偶形式為求的極小值。對(duì)求偏導(dǎo)，有

聯(lián)立，得其對(duì)偶問題為上式是一個(gè)二次規(guī)劃問題，總能為二次規(guī)劃問題找到全局極大值點(diǎn)（即支持向量）及對(duì)應(yīng)的，并由計(jì)算得到。然后，將代入任意支持向量，得

這樣，當(dāng)使用已經(jīng)訓(xùn)練好的模型進(jìn)行測(cè)試時(shí)時(shí)，只需要支持向量而不需要顯示地計(jì)算參數(shù)集。設(shè)測(cè)試樣本為，則式中，為支持向量。4.非線性支持向量機(jī)將SVM算法應(yīng)用于非線性分類問題，需引入核方法將原特征向量映射到高維空間中，使非線性問題轉(zhuǎn)化為線性問題，再使用求解線性問題的方法，尋找變換后特征向量與目標(biāo)之間的模型。設(shè)原特征向量為x，特征映射函數(shù)為，則映射到高維空間形成新的特征向量。則用支持向量機(jī)方法在高維特征空間劃分超平面所對(duì)應(yīng)的模型可表達(dá)為則有其對(duì)偶問題為

改寫為求解后即可得超平面為截距項(xiàng)通過核函數(shù)求解得。設(shè)任一支持向量，則

這樣，對(duì)任意未知的測(cè)試樣本為，則式中，為支持量。5.2聚類學(xué)習(xí)算法聚類是一種無監(jiān)督的學(xué)習(xí)算法，追求的是簇內(nèi)個(gè)體間距小，而簇間間距大。其數(shù)學(xué)定義如下：對(duì)特征空間H中的n個(gè)樣本，按照樣本間的相似程度，將H劃分為K個(gè)特征區(qū)域

，且使得各樣本均能歸入其中一個(gè)特征區(qū)域，且不會(huì)同時(shí)歸入兩個(gè)或多個(gè)特征區(qū)域，即則稱該過程為聚類。聚類具有如下特點(diǎn)：1、聚類是對(duì)整個(gè)樣本集的劃分，而不是對(duì)單個(gè)樣本的識(shí)別。因此，K等于1或者樣本數(shù)目是毫無意義的。2、聚類的依據(jù)是“樣本間的相似程度”，即滿足“緊致性”要求：簇內(nèi)樣本間的相似程度要遠(yuǎn)大于簇間的相似程度。一般用各種距離函數(shù)表征這種相似程度，常見的有曼哈頓距離、歐式距離、名考夫斯基距離、切比雪夫距離等。樣本間相似程度的度量標(biāo)準(zhǔn)不同，可能造成不同的聚類結(jié)果。3、每個(gè)樣本均確定性地屬于某一簇，不會(huì)同時(shí)屬于兩個(gè)或多個(gè)簇。由于聚類是數(shù)據(jù)驅(qū)動(dòng)的無監(jiān)督學(xué)習(xí)算法，常有多種聚類結(jié)果出現(xiàn)。一個(gè)良好的聚類算法應(yīng)該具有如下特征：1、良好的可伸縮性。既對(duì)數(shù)據(jù)量小、維度少的數(shù)據(jù)集有良好的聚類結(jié)果，又對(duì)數(shù)據(jù)量大、維度多的數(shù)據(jù)集有良好性能。2、具有處理不同類型數(shù)據(jù)的能力。包括數(shù)值、圖像、文本、序列等各種數(shù)據(jù)類型以及它們的混合形式。3、處理噪聲數(shù)據(jù)能力。能有效降低噪聲對(duì)聚類結(jié)果的影響，在低質(zhì)量的數(shù)據(jù)集中也能獲得不錯(cuò)的聚類結(jié)果。4、對(duì)樣本順序不敏感。不受輸入樣本順序影響，任意順序的相同數(shù)據(jù)集能得到相同的聚類結(jié)果。5、在約束條件下，能夠得到更高質(zhì)量的聚類結(jié)果。6、易解釋性和易使用性。即聚類的結(jié)果易于解釋并為大家所接受，且方便使用。5.2.1K均值聚類算法K均值是一種基于劃分的聚類算法，其優(yōu)點(diǎn)是計(jì)算速度快、易于理解，是最常用的一種聚類算法。

在K均值聚類中，若樣本的距離越近，則說明其相似度越高。通常以距離的倒數(shù)表征相似程度，常見的距離計(jì)算方法有歐式距離（如式（5.90）所示）和曼哈頓距離（如式（5.91）所示）。式中，x,y均為n維樣本。

為保證算法的收斂性，K均值聚類算法常用平方誤差函數(shù)度量：式中，表示第i個(gè)樣本；表示第2個(gè)樣本所屬簇的聚類中心（Ce