這次介紹一下數(shù)模國(guó)賽常用的分類方法，以下這方法也是現(xiàn)在應(yīng)用比較廣泛的分類方法：K-近鄰算法（k-Nearest Neighbors，KNN）和支持向量機(jī)（Support Vector Machine, SVM）。

?

K-近鄰算法

K-近鄰算法的基本思想是：如果一個(gè)樣本在特征空間中的K個(gè)最相似（即特征空間中最鄰近）的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。以空間中k個(gè)點(diǎn)為中心進(jìn)行聚類，對(duì)最靠近他們的對(duì)象歸類。

KNN方法思路簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無需計(jì)算參數(shù)；不足之處是計(jì)算量較大，需要計(jì)算每一個(gè)待分類的樣本點(diǎn)它到全體已知樣本的距離，才能求得它的K個(gè)最鄰近點(diǎn)。目前也要改進(jìn)策略，如采用其它距離比如更接近于實(shí)際的距離函數(shù)而不是歐氏距離來度量長(zhǎng)度，建立更高效的索引機(jī)制，等等。

?

值得一提的是，需要把KNN與另外一個(gè)名字相似的算法——K-均值聚類（K-means，全稱為k-means clustering algorithm）區(qū)分開來，均值聚類是一種無監(jiān)督學(xué)習(xí)的算法，通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。聚類結(jié)束條件可以為：1)沒有（或最小數(shù)目）對(duì)象被重新分配給不同的聚類。2)沒有（或最小數(shù)目）聚類中心再發(fā)生變化。3)誤差平方和局部最小。

下面給出兩種算法的示意圖，方便理解并區(qū)分，KNN在上，K-means在下。

KNN

?

K-means

?

支持向量機(jī)

支持向量機(jī)是一種二分類所給樣本點(diǎn)分成算法，基本目的是尋找一個(gè)可以把樣本點(diǎn)分成兩類的直線(對(duì)于二維平面而言)。維基百科上的定義是這樣的：

支持向量機(jī)（英語：support vector machine，常簡(jiǎn)稱為SVM，又名支持向量網(wǎng)絡(luò)）是在分類與回歸分析中分析數(shù)據(jù)的監(jiān)督式學(xué)習(xí)模型與相關(guān)的學(xué)習(xí)算法。給定一組訓(xùn)練實(shí)例，每個(gè)訓(xùn)練實(shí)例被標(biāo)記為屬于兩個(gè)類別中的一個(gè)或另一個(gè)，SVM訓(xùn)練算法創(chuàng)建一個(gè)將新的實(shí)例分配給兩個(gè)類別之一的模型，使其成為非概率二元線性分類器。SVM模型是將實(shí)例表示為空間中的點(diǎn)，這樣映射就使得單獨(dú)類別的實(shí)例被盡可能寬的明顯的間隔分開。然后，將新的實(shí)例映射到同一空間，并基于它們落在間隔的哪一側(cè)來預(yù)測(cè)所屬類別。

支持向量機(jī)是一種比較經(jīng)典的算法，不過目前應(yīng)用還是神經(jīng)網(wǎng)絡(luò)決策樹比較多。下面我們由簡(jiǎn)至繁來了解一下模型以及算法。首先是對(duì)樣本情況的分類討論。

a.樣本完全線性可分

線性可分通俗來講即為存在一條可以把樣本完全分開的直線：

?

鑒于嚴(yán)謹(jǐn)起見，樣本可能為n>3維的向量，我們把這條“直線”延伸開來，將其稱為“超平面”。而我們要在所有符合條件的超平面中尋找到這兩類點(diǎn)距離最大的那個(gè)超平面：

?

?

顯然，符合條件的超平面到兩類樣本點(diǎn)的距離是相同的。樣本中距離超平面最近的一些點(diǎn)，我們給它一個(gè)定義叫做支持向量，如上圖中標(biāo)記為紅色的點(diǎn)。上圖中2/|w|這一段距離我們把它叫做間隔。

當(dāng)訓(xùn)練集線性可分時(shí)，通過硬間隔學(xué)習(xí)得到一個(gè)線性分類器，即硬間隔SVM。

?

b.樣本不完全線性可分

不是所有的情況都存在一個(gè)超平面將兩類樣本點(diǎn)完全分開來的，比如下面這種情況：

這個(gè)時(shí)候我們?cè)S個(gè)別允點(diǎn)落在超平面內(nèi)部，或落入決策邊界的錯(cuò)誤一側(cè)。這個(gè)時(shí)候的間隔我們稱做軟間隔。

當(dāng)訓(xùn)練數(shù)據(jù)不能線性可分但是可以近似線性可分時(shí)，通過軟間隔最大化也可以學(xué)習(xí)到一個(gè)線性分類器，即軟間隔SVM。

c.樣本線性不可分

更有些時(shí)候，不是依靠一給超平面就能把兩類樣本點(diǎn)分開來的，比如下面這種情況：

這種時(shí)候就需要把樣本點(diǎn)投射到高維空間，方可區(qū)分：

?

當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時(shí)，通過使用核技巧和軟間隔最大化，可以學(xué)習(xí)到一個(gè)非線性SVM。

以上就是本次介紹的常用模型了，KNN和SVM，有問題的小伙伴可以隨時(shí)提問喔～

不是所有的情況都存在一個(gè)超平面將兩類樣本點(diǎn)完全分開來的，比如下面這種情況：

這個(gè)時(shí)候我們?cè)S個(gè)別允點(diǎn)落在超平面內(nèi)部，或落入決策邊界的錯(cuò)誤一側(cè)。這個(gè)時(shí)候的間隔我們稱做軟間隔。

當(dāng)訓(xùn)練數(shù)據(jù)不能線性可分但是可以近似線性可分時(shí)，通過軟間隔最大化也可以學(xué)習(xí)到一個(gè)線性分類器，即軟間隔SVM。

?

c.樣本線性不可分

更有些時(shí)候，不是依靠一給超平面就能把兩類樣本點(diǎn)分開來的，比如下面這種情況：

?

?

這種時(shí)候就需要把樣本點(diǎn)投射到高維空間，方可區(qū)分：

?

當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時(shí)，通過使用核技巧和軟間隔最大化，可以學(xué)習(xí)到一個(gè)非線性SVM。

以上就是本次介紹的常用模型了，KNN和SVM，有問題的小伙伴可以隨時(shí)提問喔～

總結(jié)

以上是生活随笔為你收集整理的【数学建模常用模型】分类专题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。