經(jīng)典的機(jī)器學(xué)習(xí)算法匯總

濃縮就是精華。想要把書(shū)寫(xiě)厚很容易，想要寫(xiě)薄卻非常難。現(xiàn)在已經(jīng)有這么多經(jīng)典的機(jī)器學(xué)習(xí)算法，如果能抓住它們的核心本質(zhì)，無(wú)論是對(duì)于理解還是對(duì)于記憶都有很大的幫助，還能讓你更可能通過(guò)面試。在本文中，SIGAI將用一句話來(lái)總結(jié)每種典型的機(jī)器學(xué)習(xí)算法，幫你抓住問(wèn)題的本質(zhì)，強(qiáng)化理解和記憶。下面我們就開(kāi)始了。

貝葉斯分類(lèi)器

核心：將樣本判定為后驗(yàn)概率最大的類(lèi)

貝葉斯分類(lèi)器直接用貝葉斯公式解決分類(lèi)問(wèn)題。假設(shè)樣本的特征向量為x，類(lèi)別標(biāo)簽為y，根據(jù)貝葉斯公式，樣本屬于每個(gè)類(lèi)的條件概率（后驗(yàn)概率）為：

分母p(x)對(duì)所有類(lèi)都是相同的，分類(lèi)的規(guī)則是將樣本歸到后驗(yàn)概率最大的那個(gè)類(lèi)，不需要計(jì)算準(zhǔn)確的概率值，只需要知道屬于哪個(gè)類(lèi)的概率最大即可，這樣可以忽略掉分母。分類(lèi)器的判別函數(shù)為：

在實(shí)現(xiàn)貝葉斯分類(lèi)器時(shí)，需要知道每個(gè)類(lèi)的條件概率分布p(x|y)即先驗(yàn)概率。一般假設(shè)樣本服從正態(tài)分布。訓(xùn)練時(shí)確定先驗(yàn)概率分布的參數(shù)，一般用最大似然估計(jì)，即最大化對(duì)數(shù)似然函數(shù)。

貝葉斯分分類(lèi)器是一種生成模型，可以處理多分類(lèi)問(wèn)題，是一種非線性模型。

決策樹(shù)

核心：一組嵌套的判定規(guī)則

決策樹(shù)在本質(zhì)上是一組嵌套的if-else判定規(guī)則，從數(shù)學(xué)上看是分段常數(shù)函數(shù)，對(duì)應(yīng)于用平行于坐標(biāo)軸的平面對(duì)空間的劃分。判定規(guī)則是人類(lèi)處理很多問(wèn)題時(shí)的常用方法，這些規(guī)則是我們通過(guò)經(jīng)驗(yàn)總結(jié)出來(lái)的，而決策樹(shù)的這些規(guī)則是通過(guò)訓(xùn)練樣本自動(dòng)學(xué)習(xí)得到的。下面是一棵簡(jiǎn)單的決策樹(shù)以及它對(duì)空間的劃分結(jié)果：

訓(xùn)練時(shí)，通過(guò)最大化Gini或者其他指標(biāo)來(lái)尋找最佳分裂。決策樹(shù)可以輸特征向量每個(gè)分量的重要性。

決策樹(shù)是一種判別模型，既支持分類(lèi)問(wèn)題，也支持回歸問(wèn)題，是一種非線性模型（分段線性函數(shù)不是線性的）。它天然的支持多分類(lèi)問(wèn)題。

kNN算法

核心：模板匹配，將樣本分到離它最相似的樣本所屬的類(lèi)

kNN算法本質(zhì)上使用了模板匹配的思想。要確定一個(gè)樣本的類(lèi)別，可以計(jì)算它與所有訓(xùn)練樣本的距離，然后找出和該樣本最接近的k個(gè)樣本，統(tǒng)計(jì)這些樣本的類(lèi)別進(jìn)行投票，票數(shù)最多的那個(gè)類(lèi)就是分類(lèi)結(jié)果。下圖是kNN算法的示意圖：

在上圖中有紅色和綠色兩類(lèi)樣本。對(duì)于待分類(lèi)樣本即圖中的黑色點(diǎn)，尋找離該樣本最近的一部分訓(xùn)練樣本，在圖中是以這個(gè)矩形樣本為圓心的某一圓范圍內(nèi)的所有樣本。然后統(tǒng)計(jì)這些樣本所屬的類(lèi)別，在這里紅色點(diǎn)有12個(gè)，圓形有2個(gè)，因此把這個(gè)樣本判定為紅色這一類(lèi)。

kNN算法是一種判別模型，即支持分類(lèi)問(wèn)題，也支持回歸問(wèn)題，是一種非線性模型。它天然的支持多分類(lèi)問(wèn)題。kNN算法沒(méi)有訓(xùn)練過(guò)程，是一種基于實(shí)例的算法。

PCA

核心：向重構(gòu)誤差最小（方差最大）的方向做線性投影

PCA是一種數(shù)據(jù)降維和去除相關(guān)性的方法，它通過(guò)線性變換將向量投影到低維空間。對(duì)向量進(jìn)行投影就是讓向量左乘一個(gè)矩陣得到結(jié)果向量，這是線性代數(shù)中講述的線性變換：

y = Wx

降維要確保的是在低維空間中的投影能很好的近似表達(dá)原始向量，即重構(gòu)誤差最小化。下圖是主分量投影示意圖：

在上圖中樣本用紅色的點(diǎn)表示，傾斜的直線是它們的主要變化方向。將數(shù)據(jù)投影到這條直線上即完成數(shù)據(jù)的降維，把數(shù)據(jù)從2維降為1維。計(jì)算最佳投影方向時(shí)求解的最優(yōu)化問(wèn)題為：

最后歸結(jié)為求協(xié)方差矩陣的特征值和特征向量：

PCA是一種無(wú)監(jiān)督的學(xué)習(xí)算法，它是線性模型，不能直接用于分類(lèi)和回歸問(wèn)題。

LDA

核心：向最大化類(lèi)間差異、最小化類(lèi)內(nèi)差異的方向線性投影

線性鑒別分析的基本思想是通過(guò)線性投影來(lái)最小化同類(lèi)樣本間的差異，最大化不同類(lèi)樣本間的差異。具體做法是尋找一個(gè)向低維空間的投影矩陣W，樣本的特征向量x經(jīng)過(guò)投影之后得到的新向量：

y = Wx

同一類(lèi)樣投影后的結(jié)果向量差異盡可能小，不同類(lèi)的樣本差異盡可能大。直觀來(lái)看，就是經(jīng)過(guò)這個(gè)投影之后同一類(lèi)的樣本進(jìn)來(lái)聚集在一起，不同類(lèi)的樣本盡可能離得遠(yuǎn)。下圖是這種投影的示意圖：

上圖中特征向量是二維的，我們向一維空間即直線投影，投影后這些點(diǎn)位于直線上。在上面的圖中有兩類(lèi)樣本，通過(guò)向右上方的直線投影，兩類(lèi)樣本被有效的分開(kāi)了。綠色的樣本投影之后位于直線的下半部分，紅色的樣本投影之后位于直線的上半部分。

訓(xùn)練時(shí)的優(yōu)化目標(biāo)是類(lèi)間差異與類(lèi)內(nèi)差異的比值：

最后歸結(jié)于求解矩陣的特征值與特征向量：

LDA是有監(jiān)督的機(jī)器學(xué)習(xí)算法，在計(jì)算過(guò)程中利用了樣本標(biāo)簽值。這是一種判別模型，也是線性模型。LDA也不能直接用于分類(lèi)和回歸問(wèn)題，要對(duì)降維后的向量進(jìn)行分類(lèi)還需要借助其他算法，如kNN。

LLE（流形學(xué)習(xí)）

核心：用一個(gè)樣本點(diǎn)的鄰居的線性組合近似重構(gòu)這個(gè)樣本，將樣本投影到低維空間中后依然保持這種線性組合關(guān)系

局部線性嵌入（簡(jiǎn)稱(chēng)LLE）將高維數(shù)據(jù)投影到低維空間中，并保持?jǐn)?shù)據(jù)點(diǎn)之間的局部線性關(guān)系。其核心思想是每個(gè)點(diǎn)都可以由與它相近的多個(gè)點(diǎn)的線性組合來(lái)近似，投影到低維空間之后要保持這種線性重構(gòu)關(guān)系，并且有相同的重構(gòu)系數(shù)。

算法的第一步是求解重構(gòu)系數(shù)，每個(gè)樣本點(diǎn)xi可以由它的鄰居線性表示，即如下最優(yōu)化問(wèn)題：

這樣可以得到每個(gè)樣本點(diǎn)與它鄰居節(jié)點(diǎn)之間的線性組合系數(shù)。接下來(lái)將這個(gè)組合系數(shù)當(dāng)做已知量，求解下面的最優(yōu)化問(wèn)題完成向量投影：

這樣可以得到向量y，這就是投影之后的向量。

LLE是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法，它是一種非線性降維算法，不能直接用于分類(lèi)或者回歸問(wèn)題。

等距映射（流形學(xué)習(xí)）

核心：將樣本投影到低維空間之后依然保持相對(duì)距離關(guān)系

等距映射使用了微分幾何中測(cè)地線的思想，它希望數(shù)據(jù)在向低維空間映射之后能夠保持流形上的測(cè)地線距離。所謂測(cè)地線，就是在地球表面上兩點(diǎn)之間的最短距離對(duì)應(yīng)的那條弧線。直觀來(lái)看，就是投影到低維空間之后，還要保持相對(duì)距離關(guān)系，即投影之前距離遠(yuǎn)的點(diǎn)，投影之后還要遠(yuǎn)，投影之前相距近的點(diǎn)，投影之后還要近。

我們可以用將地球儀的三維球面地圖投影為二維的平面地圖來(lái)理解：

投影成平面地圖后為：

在投影之前的地球儀上，美國(guó)距離中國(guó)遠(yuǎn)，泰國(guó)距離中國(guó)近，投影成平面地圖之后，還要保持這種相對(duì)遠(yuǎn)近關(guān)系。

等距映射是一種無(wú)監(jiān)督學(xué)習(xí)算法，是一種非線性降維算法。

人工神經(jīng)網(wǎng)絡(luò)

核心：一個(gè)多層的復(fù)合函數(shù)

人工神經(jīng)網(wǎng)絡(luò)在本質(zhì)上是一個(gè)多層的復(fù)合函數(shù)：

它實(shí)現(xiàn)了從向量x到向量y的映射。由于使用了非線性的激活函數(shù)f，這個(gè)函數(shù)是一個(gè)非線性函數(shù)。

神經(jīng)網(wǎng)絡(luò)訓(xùn)練時(shí)求解的問(wèn)題不是凸優(yōu)化問(wèn)題。反向傳播算法由多元復(fù)合函數(shù)求導(dǎo)的鏈?zhǔn)椒▌t導(dǎo)出。

標(biāo)準(zhǔn)的神經(jīng)網(wǎng)絡(luò)是一種有監(jiān)督的學(xué)習(xí)算法，是一種非線性模型，它既可以用于分類(lèi)問(wèn)題，也可以用于回歸問(wèn)題，天然的支持多分類(lèi)問(wèn)題。

支持向量機(jī)

核心：最大化分類(lèi)間隔的線性分類(lèi)器（不考慮核函數(shù)）

支持向量機(jī)的目標(biāo)是尋找一個(gè)分類(lèi)超平面，它不僅能正確的分類(lèi)每一個(gè)樣本，并且要使得每一類(lèi)樣本中距離超平面最近的樣本到超平面的距離盡可能遠(yuǎn)。

訓(xùn)練時(shí)求解的原問(wèn)題為：

對(duì)偶問(wèn)題為：

對(duì)于分類(lèi)問(wèn)題，預(yù)測(cè)函數(shù)為：

如果不使用非線性核函數(shù)，SVM是一個(gè)線性模型。使用核函數(shù)之后，SVM訓(xùn)練時(shí)求解的對(duì)偶問(wèn)題為：

對(duì)于分類(lèi)問(wèn)題，預(yù)測(cè)函數(shù)為：

如果使用非線性核，SVM是一個(gè)非線性模型。

訓(xùn)練時(shí)求解的問(wèn)題是凸優(yōu)化問(wèn)題，求解采用了SMO算法，這是一種分治法，每次挑選出兩個(gè)變量進(jìn)行優(yōu)化，其他變量保持不動(dòng)。選擇優(yōu)化變量的依據(jù)是KKT條件，對(duì)這兩個(gè)變量的優(yōu)化是一個(gè)二次函數(shù)極值問(wèn)題，可以直接得到公式解。

SVM是一種判別模型。它既可以用于分類(lèi)問(wèn)題，也可以用于回歸問(wèn)題。標(biāo)準(zhǔn)的SVM只能支持二分類(lèi)問(wèn)題，使用多個(gè)分類(lèi)器的組合，可以解決多分類(lèi)問(wèn)題。

logistic回歸

核心：直接從樣本估計(jì)出它屬于正負(fù)樣本的概率

通過(guò)先將向量進(jìn)行線性加權(quán)，然后計(jì)算logistic函數(shù)，可以得到[0,1]之間的概率值，它表示樣本x屬于正樣本的概率：

正樣本標(biāo)簽值為1，負(fù)樣本為0。訓(xùn)練時(shí)，求解的的是對(duì)數(shù)似然函數(shù)：

這是一個(gè)凸優(yōu)化問(wèn)題，求解時(shí)可以用梯度下降法，也可以用牛頓法。

logistic回歸是一種判別模型，需要注意的是它是一種線性模型，用于二分類(lèi)問(wèn)題。

隨機(jī)森林

核心：用有放回采樣的樣本訓(xùn)練多棵決策樹(shù)，訓(xùn)練決策樹(shù)的每個(gè)節(jié)點(diǎn)是只用了無(wú)放回抽樣的部分特征，預(yù)測(cè)時(shí)用這些樹(shù)的預(yù)測(cè)結(jié)果進(jìn)行投票

隨機(jī)森林是一種集成學(xué)習(xí)算法，它由多棵決策樹(shù)組成。這些決策樹(shù)用對(duì)訓(xùn)練樣本集隨機(jī)抽樣構(gòu)造出樣本集訓(xùn)練得到。隨機(jī)森林不僅對(duì)訓(xùn)練樣本進(jìn)行抽樣，還對(duì)特征向量的分量隨機(jī)抽樣，在訓(xùn)練決策樹(shù)時(shí)，每次分裂時(shí)只使用一部分抽樣的特征分量作為候選特征進(jìn)行分裂。

對(duì)于分類(lèi)問(wèn)題，一個(gè)測(cè)試樣本會(huì)送到每一棵決策樹(shù)中進(jìn)行預(yù)測(cè)，然后投票，得票最多的類(lèi)為最終分類(lèi)結(jié)果。對(duì)于回歸問(wèn)題隨機(jī)森林的預(yù)測(cè)輸出是所有決策樹(shù)輸出的均值。

假設(shè)有n個(gè)訓(xùn)練樣本。訓(xùn)練每一棵樹(shù)時(shí)，從樣本集中有放回的抽取n個(gè)樣本，每個(gè)樣本可能會(huì)被抽中多次，也可能一次都沒(méi)抽中。用這個(gè)抽樣的樣本集訓(xùn)練一棵決策樹(shù)，訓(xùn)練時(shí)，每次尋找最佳分裂時(shí)，還要對(duì)特征向量的分量采樣，即只考慮部分特征分量。

隨機(jī)森林是一種判別模型，既支持分類(lèi)問(wèn)題，也支持回歸問(wèn)題，并且支持多分類(lèi)問(wèn)題。這是一種非線性模型。

AdaBoost算法

核心：用多個(gè)分類(lèi)器的線性組合來(lái)預(yù)測(cè)，訓(xùn)練時(shí)重點(diǎn)關(guān)注錯(cuò)分的樣本，準(zhǔn)確率高的弱分類(lèi)器權(quán)重大

AdaBoost算法的全稱(chēng)是自適應(yīng)boosting（Adaptive Boosting），是一種用于二分類(lèi)問(wèn)題的算法，它用弱分類(lèi)器的線性組合來(lái)構(gòu)造強(qiáng)分類(lèi)器。弱分類(lèi)器的性能不用太好，僅比隨機(jī)猜測(cè)強(qiáng)，依靠它們可以構(gòu)造出一個(gè)非常準(zhǔn)確的強(qiáng)分類(lèi)器。強(qiáng)分類(lèi)器的計(jì)算公式為：

其中x是輸入向量，F(xiàn)(x)是強(qiáng)分類(lèi)器，ft(x)是弱分類(lèi)器，at是弱分類(lèi)器的權(quán)重，T為弱分類(lèi)器的數(shù)量，弱分類(lèi)器的輸出值為+1或-1，分別對(duì)應(yīng)正樣本和負(fù)樣本。分類(lèi)時(shí)的判定規(guī)則為：

sgn(F(x))

強(qiáng)分類(lèi)器的輸出值也為+1或-1，同樣對(duì)應(yīng)于正樣本和負(fù)樣本。

訓(xùn)練時(shí)，依次訓(xùn)練每一個(gè)若分類(lèi)器，并得到它們的權(quán)重值。在這里，訓(xùn)練樣本帶有權(quán)重值，初始時(shí)所有樣本的權(quán)重相等，在訓(xùn)練過(guò)程中，被前面的弱分類(lèi)器錯(cuò)分的樣本會(huì)加大權(quán)重，反之會(huì)減小權(quán)重，這樣接下來(lái)的弱分類(lèi)器會(huì)更加關(guān)注這些難分的樣本。弱分類(lèi)器的權(quán)重值根據(jù)它的準(zhǔn)確率構(gòu)造，精度越高的弱分類(lèi)器權(quán)重越大。

AdaBoost算法從廣義加法模型導(dǎo)出，訓(xùn)練時(shí)求解的是指數(shù)損失函數(shù)的極小值：

L(y, F(x)) = exp(-yF(x))

求解時(shí)采用了分階段優(yōu)化，先得到弱分類(lèi)器，然后確定弱分類(lèi)器的權(quán)重值。

標(biāo)準(zhǔn)的AdaBoost算法是一種判別模型，只能支持二分類(lèi)問(wèn)題。它的改進(jìn)型可以處理多分類(lèi)問(wèn)題。

卷積神經(jīng)網(wǎng)絡(luò)

核心：一個(gè)共享權(quán)重的多層復(fù)合函數(shù)

卷積神經(jīng)網(wǎng)絡(luò)在本質(zhì)上也是一個(gè)多層復(fù)合函數(shù)，但和普通神經(jīng)網(wǎng)絡(luò)不同的是它的某些權(quán)重參數(shù)是共享的，另外一個(gè)特點(diǎn)是它使用了池化層。訓(xùn)練時(shí)依然采用了反向傳播算法，求解的問(wèn)題不是凸優(yōu)化問(wèn)題。

和全連接神經(jīng)網(wǎng)絡(luò)一樣，卷積神經(jīng)網(wǎng)絡(luò)是一個(gè)判別模型，它既可以用于分類(lèi)問(wèn)題，也可以用用于回歸問(wèn)題，并且支持多分類(lèi)問(wèn)題。

循環(huán)神經(jīng)網(wǎng)絡(luò)

核心：綜合了復(fù)合函數(shù)和遞推數(shù)列的一個(gè)函數(shù)

和普通神經(jīng)網(wǎng)絡(luò)最大的不同在于，循環(huán)神經(jīng)網(wǎng)絡(luò)是一個(gè)遞推的數(shù)列，因此具有了記憶功能。回憶我們高中時(shí)所學(xué)的等差數(shù)列：

一旦數(shù)列的首項(xiàng)a0以及公差d已經(jīng)確定，則后面的各項(xiàng)也確定了，這樣后面各項(xiàng)完全沒(méi)有機(jī)會(huì)改變自己的命運(yùn)。循環(huán)神經(jīng)網(wǎng)絡(luò)也是這樣一個(gè)遞推數(shù)列，后一項(xiàng)由前一項(xiàng)的值決定，但除此之外還接受了一個(gè)次的輸入值，這樣本次的輸出值既和之前的數(shù)列值有關(guān)，由于當(dāng)前時(shí)刻的輸入值有關(guān)，有機(jī)會(huì)通過(guò)當(dāng)前輸入值改變自己的命運(yùn)：

和其他類(lèi)型的神經(jīng)網(wǎng)絡(luò)一樣，循環(huán)神經(jīng)網(wǎng)絡(luò)是一個(gè)判別模型，既支持分類(lèi)問(wèn)題，也支持回歸問(wèn)題，并且支持多分類(lèi)問(wèn)題。

K均值算法

核心：把樣本分配到離它最近的類(lèi)中心所屬的類(lèi)，類(lèi)中心由屬于這個(gè)類(lèi)的所有樣本確定

k均值算法是一種無(wú)監(jiān)督的聚類(lèi)算法。算法將每個(gè)樣本分配到離它最近的那個(gè)類(lèi)中心所代表的類(lèi)，而類(lèi)中心的確定又依賴(lài)于樣本的分配方案。這是一個(gè)先有雞還是先有蛋的問(wèn)題。

在實(shí)現(xiàn)時(shí)，先隨機(jī)初始化每個(gè)類(lèi)的類(lèi)中心，然后計(jì)算樣本與每個(gè)類(lèi)的中心的距離，將其分配到最近的那個(gè)類(lèi)，然后根據(jù)這種分配方案重新計(jì)算每個(gè)類(lèi)的中心。這也是一種分階段優(yōu)化的策略。

k均值算法要求解的問(wèn)題是一個(gè)NPC問(wèn)題，只能近似求解，有陷入局部極小值的風(fēng)險(xiǎn)。