一、 K近鄰

KNN算法的基本思想就是在訓(xùn)練集中數(shù)據(jù)和標(biāo)簽已知的情況下，輸入測(cè)試數(shù)據(jù)，將測(cè)試數(shù)據(jù)的特征與訓(xùn)練集中對(duì)應(yīng)的特征進(jìn)行相互比較，找到訓(xùn)練集中與之最為相似的前K個(gè)數(shù)據(jù)，則該測(cè)試數(shù)據(jù)對(duì)應(yīng)的類別就是K個(gè)數(shù)據(jù)中出現(xiàn)次數(shù)最多的那個(gè)分類，其算法的描述為：

1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；

2）按照距離的遞增關(guān)系進(jìn)行排序；

3）選取距離最小的K個(gè)點(diǎn)；

4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；

5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。

其中在計(jì)算距離時(shí)采用歐氏距離或曼哈頓距離：

k值的選擇：當(dāng)k值較小時(shí)，預(yù)測(cè)結(jié)果對(duì)近鄰的實(shí)例點(diǎn)非常敏感，容易發(fā)生過擬合；如果k值過大模型會(huì)傾向大類，容易欠擬合；通常k是不大于20的整數(shù)

優(yōu)點(diǎn)：精度高，對(duì)異常值不敏感

缺點(diǎn)：k值敏感，空間復(fù)雜度高（需要保存全部數(shù)據(jù)）,時(shí)間復(fù)雜度高（平均O(logM)，M是訓(xùn)練集樣本數(shù)）

二、感知機(jī)

PLA全稱是Perceptron Linear Algorithm，即線性感知機(jī)算法，屬于一種最簡單的感知機(jī)（Perceptron）模型。它是支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)。感知機(jī)模型是機(jī)器學(xué)習(xí)二分類問題中的一個(gè)非常簡單的模型。它的基本結(jié)構(gòu)如下圖所示：

假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的，感知機(jī)學(xué)習(xí)的目標(biāo)是求得一個(gè)能夠?qū)⒂?xùn)練數(shù)據(jù)集正實(shí)例點(diǎn)和負(fù)實(shí)例點(diǎn)完全正確分開的分離超平面。如果是非線性可分的數(shù)據(jù)，則最后無法獲得超平面。所以感知機(jī)的目標(biāo)函數(shù)為一條直線或者一個(gè)超平面，其輸出為：

其中wx+b表示空間中的一點(diǎn)的坐標(biāo)，我們的目標(biāo)取找到合適的w和b，使得f（x）和真實(shí)的y值相符合，當(dāng)然不可能達(dá)到完全符合，所以應(yīng)當(dāng)是盡可能多的點(diǎn)被正確分類。換句話說就是讓那些分錯(cuò)類的點(diǎn)越接近邊界線越好。這時(shí)我們就可以用距離來定義損失函數(shù)了：損失值=錯(cuò)誤的點(diǎn)到邊界的距離的總和。優(yōu)化的對(duì)象便是讓這個(gè)距離之和最小。

由點(diǎn)到平面的距離公式我們可以得到任意一點(diǎn)距離我們上面定義的模型的距離為：

有了計(jì)算距離的方式，我們來看看損失函數(shù)究竟怎么定義。這里需要注意的是我們的目標(biāo)是那些分錯(cuò)類的點(diǎn)，而不是所有點(diǎn)，因此不能直接將距離作為損失函數(shù)，所以我們需要找出那些分錯(cuò)類的點(diǎn)，建立他們的損失函數(shù)。這里正好可以利用絕對(duì)值來進(jìn)行區(qū)分正確點(diǎn)和錯(cuò)誤點(diǎn)。對(duì)于模型來說，在分類錯(cuò)誤的情況下，若w?xi+b>0，去掉絕對(duì)值不變,則實(shí)際的yi應(yīng)該是等于-1,為了使原式保持正值，則添加一個(gè)負(fù)號(hào)。而當(dāng)w?xi+b<0時(shí)，去掉絕對(duì)值加負(fù)號(hào)，此時(shí)yi等于1,上式為正值。因此由這個(gè)特性我們可以去掉上面的絕對(duì)值符號(hào)，將公式轉(zhuǎn)化為:

去掉||w||后得到最終的損失函數(shù)為:

這里求最小值采用的是隨機(jī)梯度下降算法，因?yàn)槲覀兠看稳∫粋€(gè)點(diǎn)來判斷他是不是錯(cuò)誤點(diǎn)，然后才能帶入優(yōu)化。

三、支持向量機(jī)SVM

支持向量機(jī)與感知機(jī)相似。他的目的也是取尋找一條直線或一個(gè)超平面將數(shù)據(jù)進(jìn)行二分類。只不過感知機(jī)的原理是到邊界的距離最小，而SVM的原理則是“間隔最大化”。

從上圖可以看出，如果數(shù)據(jù)集線性可分，那么這樣的直線又無數(shù)條，但是我們的目標(biāo)是找到一條容忍度最好的直線，即黃色的那條。

為什么要間隔最大呢？

一般來說，一個(gè)點(diǎn)距離分離超平面的遠(yuǎn)近可以表示分類預(yù)測(cè)的確信度，如圖中的A B兩個(gè)樣本點(diǎn)，B點(diǎn)被預(yù)測(cè)為正類的確信度要大于A點(diǎn)，所以SVM的目標(biāo)是尋找一個(gè)超平面，使得離超平面較近的異類點(diǎn)之間能有更大的間隔，即不必考慮所有樣本點(diǎn)，只需讓求得的超平面使得離它近的點(diǎn)間隔最大

2. 怎么計(jì)算間隔

f(x)=wTx+b 表示空間中一點(diǎn)的坐標(biāo)。當(dāng)f(x) 等于0的時(shí)候，x便是位于超平面上的點(diǎn)，而f(x) 大于0的點(diǎn)對(duì)應(yīng) y=1 的數(shù)據(jù)點(diǎn)，f(x)小于0的點(diǎn)對(duì)應(yīng)y=-1的點(diǎn)。這里的y=1和-1都是可以隨意指定的，相當(dāng)于兩種label，為了方便計(jì)算就取1和-1了。

根據(jù)上述原理我們可以總結(jié)為一個(gè)表達(dá)式：

實(shí)際上該公式等價(jià)于yi(WTxi+b)≥ +1。這就是最大間隔假設(shè)

3. 什么是支持向量

距離超平面最近的這幾個(gè)樣本點(diǎn)滿足yi(WTxi+b)=1，它們被稱為“支持向量”。虛線稱為邊界，兩條虛線間的距離稱為間隔（margin）。所謂的支持向量，就是使得上式等號(hào)成立，即最靠近兩條虛邊界線的向量。如果WTxi+b>1，那就說明更加支持了。

所以我們?cè)谟?jì)算最大間隔的時(shí)候，其實(shí)關(guān)注的是支持向量到超平面的距離。

由上述兩式聯(lián)立可得

對(duì)于支持向量，WTxi+b=1或-1，所以最大間隔變?yōu)?#xff1a;

這樣我們們便確定了目標(biāo)函數(shù)

等價(jià)于：

SVM函數(shù)的求解屬于凸二次規(guī)劃問題，采用拉格朗日乘數(shù)法求解。添加拉格朗日乘子 αi≥0，則整個(gè)拉格朗日函數(shù)可寫成：

4. 非線性支持向量機(jī)與核函數(shù)技

對(duì)于非線性分類問題，顯然無法用一個(gè)線性分離超平面來把不同的類別的數(shù)據(jù)點(diǎn)分開，那么可以用以下思路解決這個(gè)問題：

• 首先使用一個(gè)變換 z=?(x)將非線性特征空間x映射到新的線性特征空間z
• 在新的z特征空間里使用線性SVM學(xué)習(xí)分類的方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型

但是，這里有一個(gè)問題: ?(xi)??(xj)計(jì)算起來要分兩步，先映射x到z空間，然后在z空間（一般是較高維度）作高維度的內(nèi)積zi?zj。

為了簡化這個(gè)運(yùn)算過程，如果我們找到一個(gè)核函數(shù)K(xi,xj), 即K是關(guān)于x的函數(shù)，其運(yùn)算在低維空間上進(jìn)行，然后使得K(xi,xj)=?(xi)??(xj)，那么只需要計(jì)算一個(gè)比較好計(jì)算的核函數(shù)K(xi,xj)，就可以避免先映射，再在高維空間內(nèi)積的復(fù)雜運(yùn)算。

常見的核函數(shù)有：二次多項(xiàng)式核、高斯核

5. 軟間隔

我們一直假設(shè)訓(xùn)練樣本在樣本空間或特征空間食線性可分的，即存在一個(gè)超平面能將不同類的樣本完全劃分開。然而，在現(xiàn)實(shí)任務(wù)中往往很難確定合適的核函數(shù)使得訓(xùn)練樣本在特征空間中線性可分；退一步說，即便恰好找到了某個(gè)核函數(shù)使訓(xùn)練樣本在特征空間中線性可分，也很難斷定這個(gè)貌似線性可分的結(jié)果不是由于過擬合造成的。緩解該問題的一個(gè)方法是允許支持向量機(jī)在一些樣本上出錯(cuò)，為此要引入“軟間隔”的概念。當(dāng)然我們還要限制這些分錯(cuò)的樣本個(gè)數(shù)應(yīng)當(dāng)越少越好

之前做了一個(gè)最大間隔的假設(shè)，即所有樣本都滿足：

也就是說所有的樣本都得被分對(duì)，這稱之為“硬間隔”，而軟間隔則允許某些樣本不滿足約束條件，于是，目標(biāo)函數(shù)可寫為

其中C是常數(shù)，L0/1是0/1的損失函數(shù)：

當(dāng)C越大，模型的容忍程度就越小，邊界越瘦，C越小，邊界越胖，越多的樣本被分錯(cuò)，所以C為無窮大時(shí)迫使所有樣本都得滿足約束

直接使用0/1的損失函數(shù)求解不好求，一般都是將其變?yōu)閔inge損失函數(shù)：

此時(shí)，我們的優(yōu)化目標(biāo)函數(shù)也就變成了：

引入一個(gè)變量ξn=1? yi(Wx+b)，我們成為“松弛因子”，如果yi(Wx+b)<1，帶入hinge損失中，損失值大于0，說明樣本被分錯(cuò)，因此ξn代表犯了多少錯(cuò)。優(yōu)化的目標(biāo)函數(shù)最終變?yōu)?#xff1a;

5. LR和SVM不同點(diǎn)

• LR采用log損失，SVM采用合頁(hinge)損失

邏輯回歸方法基于概率理論，假設(shè)樣本為1的概率可以用sigmoid函數(shù)來表示，然后通過極大似然估計(jì)的方法估計(jì)出參數(shù)的值(基于統(tǒng)計(jì)的,其損失函數(shù)是人為設(shè)定的凸函數(shù)) 。支持向量機(jī)基于幾何間隔最大化原理，認(rèn)為存在最大幾何間隔的分類面為最優(yōu)分類面.(有嚴(yán)格的推導(dǎo))

• LR對(duì)異常值敏感，SVM對(duì)異常值不敏感

支持向量機(jī)只考慮局部的邊界線附近的點(diǎn)，而邏輯回歸考慮全局（遠(yuǎn)離的點(diǎn)對(duì)邊界線的確定也起作用，雖然作用會(huì)相對(duì)小一些）。LR模型找到的那個(gè)超平面，是盡量讓所有點(diǎn)都遠(yuǎn)離他，而SVM尋找的那個(gè)超平面，是只讓最靠近中間分割線的那些點(diǎn)盡量遠(yuǎn)離，即只用到那些支持向量的樣本。

• 對(duì)非線性問題的處理方式不同

LR主要靠特征構(gòu)造，必須組合交叉特征，特征離散化。SVM也可以這樣，還可以通過kernel(因?yàn)橹挥兄С窒蛄繀⑴c核計(jì)算,計(jì)算復(fù)雜度不高)。(由于可以利用核函數(shù),。SVM則可以通過對(duì)偶求解高效處理。LR則在特征空間維度很高時(shí)，表現(xiàn)較差。)

• 正則化不同

SVM的損失函數(shù)就自帶正則（損失函數(shù)中的1/2||w||^2項(xiàng)），這就是為什么SVM是結(jié)構(gòu)風(fēng)險(xiǎn)最小化算法的原因，而LR必須另外在損失函數(shù)上添加正則項(xiàng)

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的svm算法原理_机器学习——分类算法（1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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