1、引言

簡單說，算法就是：解決問題的手段，并且是批量化解決問題的手段。

比如你想要木頭桌子，那么制造桌子的工廠就是“一套算法”。提供（輸入）木頭，就會(huì)得到（輸出）桌子。

關(guān)于算法，有3點(diǎn)需要注意：

• 解決不同的問題可能會(huì)用到不同的算法，也可能用相同的算法。沒有某種算法是萬能的，只是適用的范圍不同而已。
• 算法沒有高級(jí)和低級(jí)之分，快速便宜的解決問題才是目的，一味追求復(fù)雜的算法（例如：深度學(xué)習(xí)），相當(dāng)于“用大炮打蚊子”
• 有時(shí)候有多種算法可以解決同一個(gè)問題，用最低的成本和最短的時(shí)間解決問題才是目的。根據(jù)不同環(huán)境選擇合適的算法很重要。

機(jī)器學(xué)習(xí)算法有很多種，歸本溯源來概括，就是建立映射關(guān)系 Y = f(X) ，針對(duì)新的 X 預(yù)測(cè)出對(duì)應(yīng)的 Y，這稱為預(yù)測(cè)建模或預(yù)測(cè)分析。

2、決策樹算法

決策樹是一種解決分類問題的算法，決策樹算法采用樹形結(jié)構(gòu)，使用層層推理來實(shí)現(xiàn)最終的分類。

決策樹由下面幾種元素構(gòu)成：

• 根節(jié)點(diǎn)：包含樣本的全集
• 內(nèi)部節(jié)點(diǎn)：對(duì)應(yīng)特征屬性測(cè)試
• 葉節(jié)點(diǎn)：代表決策的結(jié)果

預(yù)測(cè)時(shí)，在樹的內(nèi)部節(jié)點(diǎn)處用某一屬性值進(jìn)行判斷，根據(jù)判斷結(jié)果決定進(jìn)入哪個(gè)分支節(jié)點(diǎn)，直到到達(dá)葉節(jié)點(diǎn)處，得到分類結(jié)果。

這是一種基于 if-then-else 規(guī)則的有監(jiān)督學(xué)習(xí)算法，決策樹的這些規(guī)則通過訓(xùn)練得到，而不是人工制定的。

決策樹是最簡單的機(jī)器學(xué)習(xí)算法，它易于實(shí)現(xiàn)，可解釋性強(qiáng)，完全符合人類的直觀思維，有著廣泛的應(yīng)用。

下面來看一個(gè)實(shí)際的例子。

銀行要用機(jī)器學(xué)習(xí)算法來確定是否給客戶發(fā)放貸款，為此需要考察客戶的年收入，是否有房產(chǎn)這兩個(gè)指標(biāo)。領(lǐng)導(dǎo)安排你實(shí)現(xiàn)這個(gè)算法，你想到了最簡單的線性模型，很快就完成了這個(gè)任務(wù)。

首先判斷客戶的年收入指標(biāo)。如果大于20萬，可以貸款；否則繼續(xù)判斷。然后判斷客戶是否有房產(chǎn)。如果有房產(chǎn)，可以貸款；否則不能貸款。

這個(gè)例子的決策樹如下圖所示：

2.1 特征值選擇

特征選擇決定了使用哪些特征來做判斷。在訓(xùn)練數(shù)據(jù)集中，每個(gè)樣本的屬性可能有很多個(gè)，不同屬性的作用有大有小。因而特征選擇的作用就是篩選出跟分類結(jié)果相關(guān)性較高的特征，也就是分類能力較強(qiáng)的特征。

在特征選擇中通常使用的準(zhǔn)則是：信息增益。

2.2 決策樹生成

選擇好特征后，就從根節(jié)點(diǎn)觸發(fā)，對(duì)節(jié)點(diǎn)計(jì)算所有特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)特征，根據(jù)該特征的不同取值建立子節(jié)點(diǎn)；對(duì)每個(gè)子節(jié)點(diǎn)使用相同的方式生成新的子節(jié)點(diǎn)，直到信息增益很小或者沒有特征可以選擇為止。

2.3 決策樹剪枝

剪枝的主要目的是對(duì)抗過擬合，通過主動(dòng)去掉部分分支來降低過擬合的風(fēng)險(xiǎn)。

3、線性回歸算法

3.1 什么是回歸

回歸的目的是為了預(yù)測(cè)，比如預(yù)測(cè)明天的天氣溫度，預(yù)測(cè)股票的走勢(shì)…

回歸之所以能預(yù)測(cè)是因?yàn)樗ㄟ^歷史數(shù)據(jù)，摸透了“套路”，然后通過這個(gè)套路來預(yù)測(cè)未來的結(jié)果。

3.2 什么是線性

“越…，越…”符合這種說法的就可能是線性個(gè)關(guān)系：

• “房子”越大，“租金”就越高
• “漢堡”買的越多，花的“錢”就越多
• 杯子里的“水”越多，“重量”就越大
• ……

但是并非所有“越…，越…”都是線性的，比如“充電越久，電量越高”，就類似下面的非線性曲線：

線性關(guān)系不僅僅只能存在 2 個(gè)變量（二維平面）。3 個(gè)變量時(shí)（三維空間），線性關(guān)系就是一個(gè)平面，4 個(gè)變量時(shí)（四維空間），線性關(guān)系就是一個(gè)體。

3.3 什么是線性回歸

線性回歸本來是是統(tǒng)計(jì)學(xué)里的概念，現(xiàn)在經(jīng)常被用在機(jī)器學(xué)習(xí)中。

如果 2 個(gè)或者多個(gè)變量之間存在“線性關(guān)系”，那么我們就可以通過歷史數(shù)據(jù)，摸清變量之間的“套路”，建立一個(gè)有效的模型，來預(yù)測(cè)未來的變量結(jié)果。

簡單的說，是通過求出一條直線y=w*x+b，盡可能的擬合樣本點(diǎn)。

如何擬合出一條直線最佳匹配我所有的數(shù)據(jù)？一般使用“最小二乘法”來求解。

“最小二乘法”的思想是這樣的，假設(shè)我們擬合出的直線代表數(shù)據(jù)的真實(shí)值，而觀測(cè)到的數(shù)據(jù)代表擁有誤差的值。為了盡可能減小誤差的影響，需要求解一條直線使所有誤差的平方和最小。最小二乘法將最優(yōu)問題轉(zhuǎn)化為求函數(shù)極值問題。函數(shù)極值在數(shù)學(xué)上我們一般會(huì)采用求導(dǎo)數(shù)為0的方法。但這種做法并不適合計(jì)算機(jī)，可能求解不出來，也可能計(jì)算量太大。

計(jì)算機(jī)科學(xué)界專門有一個(gè)學(xué)科叫“數(shù)值計(jì)算”，專門用來提升計(jì)算機(jī)進(jìn)行各類計(jì)算時(shí)的準(zhǔn)確性和效率問題。例如，著名的“梯度下降”以及“牛頓法”就是數(shù)值計(jì)算中的經(jīng)典算法，也非常適合來處理求解函數(shù)極值的問題。梯度下降法是解決回歸模型中最簡單且有效的方法之一?！　?br> 　　
為什么在深度學(xué)習(xí)大殺四方的今天還使用線性回歸呢？

一方面，線性回歸所能夠模擬的關(guān)系其實(shí)遠(yuǎn)不止線性關(guān)系。線性回歸中的“線性”指的是系數(shù)的線性，而通過對(duì)特征的非線性變換，以及廣義線性模型的推廣，輸出和特征之間的函數(shù)關(guān)系可以是高度非線性的。另一方面，也是更為重要的一點(diǎn)，線性模型的易解釋性使得它在物理學(xué)、經(jīng)濟(jì)學(xué)、商學(xué)等領(lǐng)域中占據(jù)了難以取代的地位。

4、邏輯回歸算法

邏輯回歸是一種與線性回歸非常類似的算法，但是，從本質(zhì)上講，線型回歸處理的問題類型與邏輯回歸不一致。線性回歸處理的是數(shù)值問題，也就是最后預(yù)測(cè)出的結(jié)果是數(shù)字，例如房價(jià)。而邏輯回歸處理的是分類問題，也就是說，邏輯回歸預(yù)測(cè)結(jié)果是離散的分類，例如判斷這封郵件是否是垃圾郵件，以及用戶是否會(huì)點(diǎn)擊此廣告等等。

例如，當(dāng)預(yù)測(cè)目標(biāo)是0到1之間的概率，這個(gè)時(shí)候單純的線性模型是做不到的，因?yàn)樵诙x域不在某個(gè)范圍之內(nèi)時(shí)，值域也超出了規(guī)定區(qū)間。

所以此時(shí)需要這樣的形狀的模型會(huì)比較好：

那么怎么得到這樣的模型呢？

可以對(duì)線性回歸的計(jì)算結(jié)果加上了一個(gè)Sigmoid函數(shù)，將數(shù)值結(jié)果轉(zhuǎn)化為了0到1之間的概率(你只需要理解對(duì)數(shù)值越大，函數(shù)越逼近1，數(shù)值越小，函數(shù)越逼近0)，接著我們根據(jù)這個(gè)概率可以做預(yù)測(cè)，例如概率大于0.5，則這封郵件就是垃圾郵件等等。從直觀上來說，邏輯回歸是畫出了一條分類線，見下圖。

4.1 線性回歸 VS 邏輯回歸

線性回歸和邏輯回歸是 2 種經(jīng)典的算法。經(jīng)常被拿來做比較，下面整理了一些兩者的區(qū)別：

• 線性回歸只能用于回歸問題，邏輯回歸雖然名字叫回歸，但是更多用于分類問題。
• 線性回歸要求因變量是連續(xù)性數(shù)值變量，而邏輯回歸要求因變量是離散的變量
• 線性回歸要求自變量和因變量呈線性關(guān)系，而邏輯回歸不要求自變量和因變量呈線性關(guān)系
• 線性回歸可以直觀的表達(dá)自變量和因變量之間的關(guān)系，邏輯回歸則無法表達(dá)變量之間的關(guān)系

5、樸素貝葉斯算法

5.1 貝葉斯定理

在概率論與統(tǒng)計(jì)學(xué)中，貝葉斯定理描述了一個(gè)事件發(fā)生的可能性，這個(gè)可能性是基于事先掌握了一些與該事件相關(guān)的情況從而推測(cè)的。也就是說，貝葉斯理論是指根據(jù)一個(gè)已發(fā)生事件的概率，計(jì)算另一個(gè)事件的發(fā)生概率。

從數(shù)學(xué)上貝葉斯理論可以表示為：

• P(B)表示發(fā)生B事件的概率；
• P(A)表示發(fā)生A事件的概率；
• P(B|A)表示在A事件已經(jīng)發(fā)生的情況下B事件會(huì)發(fā)生的概率；
• P(A|B)表示在B事件已經(jīng)發(fā)生的情況下A事件會(huì)發(fā)生的概率；

這時(shí)候我們?cè)賮砜簇惾~斯定理，這個(gè)公式說明了兩個(gè)互換的條件概率之間的關(guān)系，它們通過聯(lián)合概率關(guān)聯(lián)起來。在這種情況下，若知道P(A|B) 的值，就能夠計(jì)算P(B|A)的值。因此貝葉斯公式實(shí)際上闡述了這么一個(gè)事情，如下圖所示：

就像是上圖中，已知黑點(diǎn)已經(jīng)落入A區(qū)域了，由于A區(qū)域大部分區(qū)域與B區(qū)域相交，因此推斷黑點(diǎn)也在B區(qū)域的概率會(huì)變大。我們想獲得的結(jié)果其實(shí)是P(B|A)，即我們想知道，在考慮了一些現(xiàn)有的因素后，這個(gè)隨機(jī)事件會(huì)以多大概率出現(xiàn)。參考這個(gè)概率結(jié)果，在很多事情上我們可以有針對(duì)性地作出決策。

5.2 樸素貝葉斯

在機(jī)器學(xué)習(xí)領(lǐng)域主要使用的是樸素貝葉斯算法，有方法簡單、分類準(zhǔn)確率高、速度快的特點(diǎn)。

樸素貝葉斯法（Naive Bayes）是基于貝葉斯定理與特征條件獨(dú)立假設(shè)的分類方法，其分類原理就是利用貝葉斯公式根據(jù)某特征的先驗(yàn)概率計(jì)算出其后驗(yàn)概率，然后選擇具有最大后驗(yàn)概率的類作為該特征所屬的類。

之所以稱之為“樸素”，是因?yàn)樨惾~斯分類只做最原始、最簡單的假設(shè)：所有的特征之間都是相互獨(dú)立的。

來看一個(gè)經(jīng)典的文章分類例子：輸入一篇未知文檔X，判斷該文檔屬于科技類別還是娛樂類別。

根據(jù)貝葉斯理論，只需要判斷P(科技|文檔X)和P(娛樂|文檔X)的大小。而文檔其實(shí)就是一個(gè)個(gè)關(guān)鍵詞，所以我們需要計(jì)算的是P(科技|詞1，詞2，詞3......)和P(娛樂|詞1，詞2，詞3.....)。所以可得：

P(科技|詞1，詞2，詞3)=P(詞1，詞2，詞3|科技)*P(科技)/P(詞1，詞2，詞3)
P(娛樂|詞1，詞2，詞3)=P(詞1，詞2，詞3|娛樂)*P(娛樂)/P(詞1，詞2，詞3)

上式中因?yàn)榉帜付加?code>P(詞1，詞2，詞3)，故可以消去。只需要比較P(詞1，詞2，詞3|科技)*P(科技)和P(詞1，詞2，詞3|娛樂)*P(娛樂)即可。

下圖中的訓(xùn)練集中一共有30篇科技文章，60篇娛樂文章，共計(jì)90篇文章。這些文章中提取出重要的詞語分別有商場、影院、支付寶和云計(jì)算，并統(tǒng)計(jì)了在不同類別文章中出現(xiàn)的次數(shù)。

現(xiàn)在有一個(gè)將要被預(yù)測(cè)的文章，該文章中出現(xiàn)重要的詞為：影院，商場與支付寶，則計(jì)算該文章屬于科技、娛樂的概率分別是多少？

那么我們可以直接帶入式子中進(jìn)行計(jì)算：

P(科技|影院，商場，支付寶)=P(影院，商場，支付寶|科技)*P(科技)=(8/100)(9/100)(20/100)(30/90)=0.00048
P(娛樂|影院，商場，支付寶)=P(影院，商場，支付寶|娛樂)*P(娛樂)=(56/121)(51/121)(15/121)(60/90)=0.01612

可見，該文章屬于娛樂類別的概率要大于屬于科技類別的概率。

6、K-鄰近算法

K-鄰近算法(K Nearest Neighbor)又叫KNN算法，即給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例，這K個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分類到這個(gè)類中。這就類似于現(xiàn)實(shí)生活中少數(shù)服從多數(shù)的思想。

KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。

如上圖所示，有兩類不同的樣本數(shù)據(jù)，分別用藍(lán)色的小正方形和紅色的小三角形表示，而圖正中間的那個(gè)綠色的圓所標(biāo)示的數(shù)據(jù)則是待分類的數(shù)據(jù)。

下面我們根據(jù)k近鄰的思想來給綠色圓點(diǎn)進(jìn)行分類：

• 如果K=3，綠色圓點(diǎn)的最鄰近的3個(gè)點(diǎn)是2個(gè)紅色小三角形和1個(gè)藍(lán)色小正方形，少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類點(diǎn)屬于紅色的三角形一類。
• 如果K=5，綠色圓點(diǎn)的最鄰近的5個(gè)鄰居是2個(gè)紅色三角形和3個(gè)藍(lán)色的正方形，還是少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類點(diǎn)屬于藍(lán)色的正方形一類。

從上面例子我們可以看出，K-近鄰算法的思想非常簡單，也非常容易理解。但是要想應(yīng)用于實(shí)際問題，還有很多細(xì)節(jié)要考慮，比如k怎么確定，取值多少時(shí)效果最好？所謂的最近鄰又是如何來判斷給定呢？

6.1 k值的選取

假設(shè)我們有訓(xùn)練數(shù)據(jù)和待分類點(diǎn)如下圖：

上圖中有倆類，一個(gè)是黑色的圓點(diǎn)，一個(gè)是藍(lán)色的長方形，現(xiàn)在我們的待分類點(diǎn)是紅色的五邊形。

假設(shè)我們選取k=1這個(gè)極端情況，由圖中可以看到，五邊形離黑色的圓點(diǎn)最近，k又等于1，最終判定待分類點(diǎn)是黑色的圓點(diǎn)。很明顯，判別結(jié)果并不正確。

可見，如果我們選取較小的k值，容易發(fā)生過擬合，即很容易學(xué)習(xí)到噪聲，也就非常容易判定為噪聲類別。

所謂的過擬合就是在訓(xùn)練集上準(zhǔn)確率非常高，而在測(cè)試集上準(zhǔn)確率低，經(jīng)過上例，我們可以得到k太小會(huì)導(dǎo)致過擬合，很容易將一些噪聲（如上圖離五邊形很近的黑色圓點(diǎn)）學(xué)習(xí)到模型中，而忽略了數(shù)據(jù)真實(shí)的分布。

如果將k調(diào)大一點(diǎn)，使k等于8，把長方形都包括進(jìn)來，很容易得到正確的分類應(yīng)該是藍(lán)色的長方形。如下圖：

但是，K值并不是越大越好。

如果果我們選取較大的k值，就相當(dāng)于用較大鄰域中的訓(xùn)練數(shù)據(jù)進(jìn)行預(yù)測(cè)，這時(shí)與輸入實(shí)例較遠(yuǎn)的（不相似）訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用，使預(yù)測(cè)發(fā)生錯(cuò)誤。

試想，如果k=N（N為訓(xùn)練樣本的個(gè)數(shù)）,那么無論輸入實(shí)例是什么，都將簡單地預(yù)測(cè)它屬于在訓(xùn)練實(shí)例中最多的類。這時(shí)相當(dāng)于就沒有訓(xùn)練模型，直接拿訓(xùn)練數(shù)據(jù)統(tǒng)計(jì)了一下各個(gè)數(shù)據(jù)的類別，找最大的而已。如下圖所示：

我們統(tǒng)計(jì)了黑色圓形是8個(gè)，長方形個(gè)數(shù)是7個(gè)，如果k=N，得出結(jié)論是：紅色五邊形是屬于黑色圓形。很明顯，判別結(jié)果也是不對(duì)的。

所以，k值既不能過大，也不能過小，在上面的例子中，k值選擇在下圖紅色圓邊界之間這個(gè)范圍是最好的：

真實(shí)例子中不可能只有兩個(gè)特征，但是原理是一樣的。我們一般選取一個(gè)較小的數(shù)值，通常采取交叉驗(yàn)證法來選取最優(yōu)的k值。

也就是說，選取k值很重要的關(guān)鍵是實(shí)驗(yàn)調(diào)參，類似于神經(jīng)網(wǎng)絡(luò)選取多少層這種，通過調(diào)整超參數(shù)來得到一個(gè)較好的結(jié)果。

6.2 距離的度量

有兩種計(jì)算距離的方法：歐氏距離（歐幾里得距離）和曼哈頓距離。

歐氏距離就是我們生活中所說的兩點(diǎn)之間的最短距離，而曼哈頓距離就是兩點(diǎn)之間每個(gè)維度的距離之和，我們用一張圖來解釋更明白：

如圖，在二維坐標(biāo)中，兩個(gè)黑點(diǎn)之間綠色的線就是歐氏距離；而紅色、藍(lán)色、黃色的折線都是等長的，就是曼哈頓距離。用到多維坐標(biāo)中也是如此。

7、K-means聚類算法

K-means 是我們最常用的基于歐式距離的聚類算法，其認(rèn)為兩個(gè)目標(biāo)的距離越近，相似度越大。

日常生活中，從人臉識(shí)別、語音識(shí)別到搜索引擎，我們看到越來越多人工智能領(lǐng)域的算法逐漸走向落地。盡管全球每日新增數(shù)據(jù)量以PB或EB級(jí)別增長，但是大部分?jǐn)?shù)據(jù)屬于無標(biāo)注甚至非結(jié)構(gòu)化。所以相對(duì)于監(jiān)督學(xué)習(xí)，不需要標(biāo)注的無監(jiān)督學(xué)習(xí)蘊(yùn)含了巨大的潛力與價(jià)值。

K-Means是無監(jiān)督學(xué)習(xí)的杰出代表之一，常用于數(shù)據(jù)探索或挖掘前期，沒有先驗(yàn)經(jīng)驗(yàn)的前提下做探索性分析。

7.1 工作原理

K-means 有一個(gè)著名的模型——牧師—村民模型：

有四個(gè)牧師去郊區(qū)布道，一開始牧師們隨意選了幾個(gè)布道點(diǎn)，并且把這幾個(gè)布道點(diǎn)的情況公告給了郊區(qū)所有的村民，于是每個(gè)村民到離自己家最近的布道點(diǎn)去聽課。
聽課之后，大家覺得距離太遠(yuǎn)了，于是每個(gè)牧師統(tǒng)計(jì)了一下自己的課上所有的村民的地址，搬到了所有地址的中心地帶，并且在海報(bào)上更新了自己的布道點(diǎn)的位置。
牧師每一次移動(dòng)不可能離所有人都更近，有的人發(fā)現(xiàn)A牧師移動(dòng)以后自己還不如去B牧師處聽課更近，于是每個(gè)村民又去了離自己最近的布道點(diǎn)……
就這樣，牧師每個(gè)禮拜更新自己的位置，村民根據(jù)自己的情況選擇布道點(diǎn)，最終穩(wěn)定了下來。

我們可以看到，牧師的目的是為了讓每個(gè)村民到其最近中心點(diǎn)的距離和最小。

在實(shí)踐中，其工作原理如下：

（1）K-means 算法首先將所有坐標(biāo)初始化為“K”集群中心。

（2）每經(jīng)過一次算法，每個(gè)點(diǎn)都會(huì)分配給其最近的集群中心。

（3）然后，集群中心會(huì)被更新為在該經(jīng)過中分配給其的所有點(diǎn)的“中心”。這是通過重新計(jì)算集群中心作為各自集群中點(diǎn)的平均值來實(shí)現(xiàn)的。

（4）算法會(huì)重復(fù)執(zhí)行，直到上次迭代的集群中心發(fā)生最小變化。

如果集群呈現(xiàn)一致的球形形狀，說明 K-means 在捕獲結(jié)構(gòu)和進(jìn)行數(shù)據(jù)推理方面非常有效。但是，如果集群呈現(xiàn)更復(fù)雜的幾何形狀，那就說明算法在數(shù)據(jù)聚類方面做得不好。

K-means 的另一個(gè)缺點(diǎn)是，該算法不允許彼此距離較遠(yuǎn)的數(shù)據(jù)點(diǎn)共享同一集群，而不管它們是否屬于該集群。K-means 本身不會(huì)從數(shù)據(jù)中了解到集群數(shù)量，而是必須預(yù)先定義信息。最后，當(dāng)集群之間出現(xiàn)重疊時(shí)，K-means 無法確定如何分配重疊位置的數(shù)據(jù)點(diǎn)。

8、SVM 算法

支持向量機(jī)，Support Vector Machine，簡稱SVM，是誕生于統(tǒng)計(jì)學(xué)習(xí)界，同時(shí)在機(jī)器學(xué)習(xí)界大放光彩的經(jīng)典算法。

8.1 線性可分

對(duì)于一個(gè)數(shù)據(jù)集合可以畫一條直線將兩組數(shù)據(jù)點(diǎn)分開，這樣的數(shù)據(jù)成為線性可分。見下圖：

將上述數(shù)據(jù)集分隔開來的直線成為分隔超平面。對(duì)于二維平面來說，分隔超平面就是一條直線。對(duì)于三維及三維以上的數(shù)據(jù)來說，分隔數(shù)據(jù)的是個(gè)平面，稱為超平面，也就是分類的決策邊界。

點(diǎn)到分割面的距離，稱為點(diǎn)相對(duì)于分割面的間隔。

數(shù)據(jù)集所有點(diǎn)到分隔面的最小間隔的，稱為分類器或數(shù)據(jù)集的間隔。SVM分類器就是要找最大的數(shù)據(jù)集間隔。

支持向量機(jī)的核心思想： 最大間隔化，最不受到噪聲的干擾。如上圖所示，分類器A比分類器B的間隔（藍(lán)色陰影）大。

8.2 線性不可分

如果沒有核函數(shù)技術(shù)，支持向量機(jī)算法最多算是一種更好的線性分類技術(shù)。但是，通過跟高斯“核”的結(jié)合，支持向量機(jī)可以表達(dá)出非常復(fù)雜的分類界線，從而達(dá)成很好的的分類效果?！昂恕笔聦?shí)上就是一種特殊的函數(shù)，最典型的特征就是可以將低維的空間映射到高維的空間。

如下圖所示的兩類數(shù)據(jù)，分別分布為兩個(gè)圓圈的形狀，這樣的數(shù)據(jù)本身就是線性不可分的，此時(shí)該如何將兩類數(shù)據(jù)分開？

上圖所述的這個(gè)數(shù)據(jù)集，是用兩個(gè)半徑不同的圓圈加上了少量的噪音生成得到的，所以，一個(gè)理想的分界應(yīng)該是一個(gè)“圓圈”而不是一條線（超平面）。

我們?nèi)绾卧诙S平面劃分出一個(gè)圓形的分類界線？在二維平面可能會(huì)很困難，但是通過“核”可以將二維空間映射到三維空間，然后使用一個(gè)線性平面就可以達(dá)成類似效果。也就是說，二維平面劃分出的非線性分類界線可以等價(jià)于三維平面的線性分類界線。于是，我們可以通過在三維空間中進(jìn)行簡單的線性劃分就可以達(dá)到在二維平面中的非線性劃分效果。

9、協(xié)同過濾算法

協(xié)同過濾（Collaborative Filtering, 簡稱CF）是推薦系統(tǒng)最重要的思想之一。在早期，協(xié)同過濾幾乎等同于推薦系統(tǒng)。

協(xié)同過濾這個(gè)算法，目的就是找相似，可以是找相似的人，也可以是找相似的物，還可以更復(fù)雜，同時(shí)找相似的人與物。相應(yīng)的，進(jìn)化出三種常見的子類：

• 物品協(xié)同過濾（ItemCF）：相似的物品可能被同個(gè)用戶喜歡。這個(gè)就是著名的世界杯期間沃爾瑪尿布和啤酒的故事了。這里因?yàn)槭澜绫陂g，奶爸要喝啤酒看球，又要帶娃，啤酒和尿布同時(shí)被奶爸所需要，也就是相似商品，可以放在一起銷售。
• 用戶協(xié)同過濾（UserCF）：相似的用戶可能喜歡相同物品。如加了好友的兩個(gè)用戶，或者點(diǎn)擊行為類似的用戶被視為相似用戶。如你和你的同學(xué)互加了抖音好友，他們兩人各自喜歡的視頻，可能會(huì)產(chǎn)生互相推薦。
• 模型協(xié)同過濾：使用矩陣分解模型來學(xué)習(xí)用戶和物品的協(xié)同過濾信息。一般這種協(xié)同過濾模型有：SVD，SVD++等。

9.1 物品協(xié)同過濾

以圖書銷售推薦為例，解釋物品協(xié)同過濾的過程。為了簡單化，假設(shè)某圖書銷售平臺(tái)總共有6本書銷售，有6個(gè)用戶購買。

前面說到ItemCF的定義是，相似的物品可能被同個(gè)用戶喜歡。反過來講，就是被同個(gè)用戶喜歡的物品是相似商品。如上圖中，圖書1和圖書2兩本書，被用戶A同時(shí)喜歡，這兩本書具有相似性。而圖書5和圖書6，沒有被同個(gè)用戶同時(shí)喜歡，不具有相似性。

如果用余弦相似度計(jì)算圖書1和圖書2的相似度，也叫做cosine距離，計(jì)算過程為：

回想中學(xué)的數(shù)學(xué)知識(shí)我們就可以知道，上面的similarity計(jì)算公式，實(shí)際上就是計(jì)算書籍1的評(píng)分向量（4,5,4,0,0,0）和書籍2的評(píng)分向量（3,0,3,3,4,0）的 cos 夾角。

用同樣的方式，可以算出圖書1跟其他五本圖書相似度分別為0.27, 0 .79，0.32,0.99和0。對(duì)每兩本書計(jì)算完這個(gè)相似度后，就可以獲得全部圖書的相似矩陣。

一個(gè)平臺(tái)不僅僅有6本圖書6個(gè)用戶，我們?cè)贁U(kuò)展到一般的情況。計(jì)算物品的相似度，實(shí)際是計(jì)算每兩個(gè)物品評(píng)分向量的cosine距離，評(píng)分向量的每一維，代表了一個(gè)用戶，下圖中，表格的第一行代表了所有用戶對(duì)物品A的評(píng)分。當(dāng)有100萬個(gè)用戶時(shí)，也就是計(jì)算每兩個(gè)100萬維向量的距離。這樣就導(dǎo)致計(jì)算量很大，而且很多平臺(tái)不僅僅只有100萬用戶，因而這個(gè)低效的計(jì)算方式需要改進(jìn)。

有了評(píng)分矩陣之后，預(yù)測(cè)決策一般有兩種場景。

一種是根據(jù)相似度排序推薦最近鄰物品。類似于“看了還看”，“買了還買”場景。在這里的例子中，我們知道圖書1和其他圖書的相似度排序分別是圖書5，圖書3，圖書4和圖書2。當(dāng)用戶點(diǎn)擊了圖書1時(shí)，就可以按照相似順序從高到低推薦。

第二種是根據(jù)相似度預(yù)測(cè)評(píng)分推薦物品。如何決策要不要給用戶B推薦圖書2，圖書4和圖書6呢？如下圖，通過用戶B對(duì)圖書1的評(píng)分 * 未知圖書與圖書1的相似度來預(yù)測(cè)用戶B對(duì)剩下圖書的評(píng)分。如圖書2的預(yù)測(cè)評(píng)分 = 圖書1的評(píng)分5分 * 圖書1和圖書2的相似度0.27 ，從而用戶B對(duì)圖書2的評(píng)分是：5*0.27=1.35。同樣方式計(jì)算出其他圖書的評(píng)分預(yù)測(cè)。

上面的結(jié)果來看，用戶B對(duì)其他圖書評(píng)分比較低，這幾本圖書推薦的可能性大大減少。

9.2 用戶協(xié)同過濾

用戶協(xié)同過濾（UserCF）的計(jì)算方式跟物品協(xié)同過濾（ItemCF）的計(jì)算方式類似。不同的是由計(jì)算兩兩物品的相似度，轉(zhuǎn)換成計(jì)算兩兩用戶的相似度。如下圖所示：

評(píng)分了相同圖書的用戶為相似用戶，他們的相似度同樣也用cosine相似度公式來計(jì)算。計(jì)算完相似度后，就可以根據(jù)用戶間的相似性，預(yù)測(cè)用戶對(duì)未評(píng)分圖書進(jìn)行評(píng)分預(yù)測(cè)。

但是在電商平臺(tái)上，由于用戶評(píng)分的稀疏性（很多用戶壓根不評(píng)分），沒有評(píng)分的用戶無法跟其他用戶計(jì)算相似性，從而導(dǎo)致很多用戶之間沒有相似度。

時(shí)間到了移動(dòng)互聯(lián)網(wǎng)的今天，我們更多是用點(diǎn)擊數(shù)據(jù)，用戶好友關(guān)系，通訊錄或者甚至是同一個(gè)WIFI地址來計(jì)算用戶協(xié)同過濾，數(shù)據(jù)稀疏性得到一定程度上的解決?，F(xiàn)在，用戶的協(xié)同過濾在信息流內(nèi)容推薦，社交性的推薦系統(tǒng)有著很好的利用。比如抖音，因?yàn)閮?nèi)容更新頻繁，用戶協(xié)同過濾可以作為很好的召回手段，所以也就會(huì)出現(xiàn)老公點(diǎn)贊的視頻會(huì)被推薦給他老婆的情景。

9.3 模型協(xié)同過濾

SVD算法的誕生，跟美國Netflix公司有關(guān)。這家公司中文名叫網(wǎng)飛，拍了大家熟悉的網(wǎng)劇《紙牌屋》。

時(shí)間來到2006年，Netflix發(fā)起一個(gè)推薦系統(tǒng)的懸賞競賽。他們公開了自己網(wǎng)站的用戶數(shù)據(jù)評(píng)分?jǐn)?shù)據(jù)包，并放出100萬美元懸賞優(yōu)化推薦算法。凡是能在Netflix現(xiàn)有的推薦系統(tǒng)基礎(chǔ)上，把均方根誤差降低10%的人，都能參與瓜分這100萬美元。消息一放出，引來了無數(shù)高手參加。這場比賽中，最佳算法就是SVD。

背景介紹完了，接下來直接介紹SVD是怎么計(jì)算的。

還是跟前面那樣，簡單化問題：假設(shè)一個(gè)平臺(tái)只有4個(gè)用戶和4本圖書。

根據(jù)線性代數(shù)我們知道，一個(gè)矩陣可以分解為多個(gè)矩陣的乘積。SVD英文全稱叫做Singular Value Decomposition，這個(gè)算法是個(gè)矩陣分解的通用名稱，在不同領(lǐng)域有不同的形式。在推薦系統(tǒng)領(lǐng)域，可以簡單的認(rèn)為，SVD就是將一個(gè)矩陣，在一定的精度損失下，將一個(gè)矩陣分解成兩個(gè)矩陣。運(yùn)用這個(gè)算法，我們可以將上圖的矩陣做以下的近似分解：

其中，用戶矩陣部分代表著每個(gè)用戶的偏好在一個(gè)二維隱語義空間上的映射。同樣地，物品矩陣代表著每本圖書的特性在一個(gè)二維隱語義空間上的映射。這兩個(gè)矩陣也就是模型的結(jié)果。這樣，我們訓(xùn)練模型的時(shí)候，就只需要訓(xùn)練用戶矩陣中的8個(gè)參數(shù)和物品矩陣中的8個(gè)參數(shù)即可。大大減少了計(jì)算量。

模型訓(xùn)練的過程，簡單地說，就是通過最小二乘法，不斷將用戶評(píng)分?jǐn)?shù)據(jù)迭代入矩陣中計(jì)算，直到把均方誤差優(yōu)化到最小。

通過模型訓(xùn)練，我們得到用戶矩陣Q和物品矩陣P后，全部用戶對(duì)全部圖書的評(píng)分預(yù)測(cè)可以通過R = PQ來獲得。如上圖中，用戶A的向量(1.40,-1.18)乘以物品2的向量（2.19,0.73）則可得用戶A對(duì)物品1的評(píng)分預(yù)測(cè)為：1.40×(-1.18)+2.19×0.73=2.21。

對(duì)所有的用戶和物品都執(zhí)行相同操作，可以得到全部用戶對(duì)全部物品的評(píng)分。如下圖右側(cè)矩陣：

得到全部的評(píng)分預(yù)測(cè)后，我們就可以對(duì)每本圖書進(jìn)行擇優(yōu)推薦。需要注意的是，用戶矩陣和物品矩陣的乘積，得到的評(píng)分預(yù)估值，與用戶的實(shí)際評(píng)分不是全等關(guān)系，而是近似相等的關(guān)系。如上圖中兩個(gè)矩陣綠色部分，用戶實(shí)際評(píng)分和預(yù)估評(píng)分都是近似的，有一定的誤差。

在現(xiàn)在的實(shí)際應(yīng)用中，SVD一般作為協(xié)同過濾的離線召回使用。一般地，將需要給用戶推薦的物品提前離線計(jì)算好，存在HBASE中，在用戶有請(qǐng)求的時(shí)候，直接讀取推薦的結(jié)果，放入初排階段的召回集中。

10、神經(jīng)網(wǎng)絡(luò)算法

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

人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Networks，ANN)算法是80年代機(jī)器學(xué)習(xí)界非常流行的算法，不過在90年代中途衰落?，F(xiàn)在，攜著“深度學(xué)習(xí)”之勢(shì)，神經(jīng)網(wǎng)絡(luò)重裝歸來，重新成為最強(qiáng)大的機(jī)器學(xué)習(xí)算法之一。

神經(jīng)網(wǎng)絡(luò)的誕生起源于對(duì)大腦工作機(jī)理的研究。早期生物界學(xué)者們使用神經(jīng)網(wǎng)絡(luò)來模擬大腦。機(jī)器學(xué)習(xí)的學(xué)者們使用神經(jīng)網(wǎng)絡(luò)進(jìn)行機(jī)器學(xué)習(xí)的實(shí)驗(yàn)，發(fā)現(xiàn)在視覺與語音的識(shí)別上效果都相當(dāng)好。在BP算法(加速神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程的數(shù)值算法)誕生以后，神經(jīng)網(wǎng)絡(luò)的發(fā)展進(jìn)入了一個(gè)熱潮。

簡單來說，神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)機(jī)理就是分解與整合。在著名的Hubel-Wiesel試驗(yàn)中，學(xué)者們研究貓的視覺分析機(jī)理是這樣的。

比方說，一個(gè)正方形，分解為四個(gè)折線進(jìn)入視覺處理的下一層中。四個(gè)神經(jīng)元分別處理一個(gè)折線。每個(gè)折線再繼續(xù)被分解為兩條直線，每條直線再被分解為黑白兩個(gè)面。于是，一個(gè)復(fù)雜的圖像變成了大量的細(xì)節(jié)進(jìn)入神經(jīng)元，神經(jīng)元處理以后再進(jìn)行整合，最后得出了看到的是正方形的結(jié)論。這就是大腦視覺識(shí)別的機(jī)理，也是神經(jīng)網(wǎng)絡(luò)工作的機(jī)理。

讓我們看一個(gè)簡單的神經(jīng)網(wǎng)絡(luò)的邏輯架構(gòu)。

在這個(gè)網(wǎng)絡(luò)中，分成輸入層，隱藏層，和輸出層。輸入層負(fù)責(zé)接收信號(hào)，隱藏層負(fù)責(zé)對(duì)數(shù)據(jù)的分解與處理，最后的結(jié)果被整合到輸出層。每層中的一個(gè)圓代表一個(gè)處理單元，可以認(rèn)為是模擬了一個(gè)神經(jīng)元，若干個(gè)處理單元組成了一個(gè)層，若干個(gè)層再組成了一個(gè)網(wǎng)絡(luò)，也就是"神經(jīng)網(wǎng)絡(luò)"。

在神經(jīng)網(wǎng)絡(luò)中，每個(gè)處理單元事實(shí)上就是一個(gè)邏輯回歸模型，邏輯回歸模型接收上層的輸入，把模型的預(yù)測(cè)結(jié)果作為輸出傳輸?shù)较乱粋€(gè)層次。通過這樣的過程，神經(jīng)網(wǎng)絡(luò)可以完成非常復(fù)雜的非線性分類。

在實(shí)際應(yīng)用中，以ANN為基礎(chǔ)，演化出了三種更為復(fù)雜的子類：

• 文本分析或自然語言處理的遞歸神經(jīng)網(wǎng)絡(luò)(簡稱RNN)
• 常用于影像數(shù)據(jù)進(jìn)行分析處理的卷積神經(jīng)網(wǎng)絡(luò)(簡稱CNN)
• 常用于數(shù)據(jù)生成或非監(jiān)督式學(xué)習(xí)應(yīng)用的生成對(duì)抗網(wǎng)絡(luò)(簡稱GAN)

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

首先從架構(gòu)的角度來理解RNN和ANN之間的區(qū)別：

RNN在隱藏狀態(tài)上有一個(gè)循環(huán)連接。此循環(huán)可以從在輸入數(shù)據(jù)中捕獲順序信息，賦予網(wǎng)絡(luò)一定的記憶能力，可學(xué)習(xí)具有前后相關(guān)的數(shù)據(jù)類型。例如進(jìn)行語言翻譯或文本翻譯，一個(gè)句子中的前后詞匯通常會(huì)有一定的關(guān)系。

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

卷積神經(jīng)網(wǎng)絡(luò)（CNN）目前在深度學(xué)習(xí)領(lǐng)域非常流行，使我們能夠在計(jì)算機(jī)視覺中獲得超人的性能，它在2010年代早期達(dá)到了人類的精度，而且其精度仍在逐年提高。

CNN像滑動(dòng)窗口一樣掃描輸入并生成中間表征，然后在它到達(dá)末端的全連接層之前對(duì)其進(jìn)行逐層抽象。

CNN也已成功應(yīng)用于非圖像數(shù)據(jù)集。Facebook的研究小組發(fā)現(xiàn)了一個(gè)基于卷積神經(jīng)網(wǎng)絡(luò)的先進(jìn)自然語言處理系統(tǒng)，其卷積網(wǎng)絡(luò)優(yōu)于RNN，而后者被認(rèn)為是任何序列數(shù)據(jù)集的首選架構(gòu)。雖然一些神經(jīng)科學(xué)家和人工智能研究人員不喜歡CNN（因?yàn)樗麄冋J(rèn)為大腦不會(huì)像CNN那樣做），但基于CNN的網(wǎng)絡(luò)正在擊敗所有現(xiàn)有的網(wǎng)絡(luò)實(shí)現(xiàn)。

10.4 生成對(duì)抗網(wǎng)絡(luò)–GAN

生成對(duì)抗網(wǎng)絡(luò)（GAN, Generative Adversarial Networks ）是一種 深度學(xué)習(xí) 模型，是近年來復(fù)雜分布上無監(jiān)督學(xué)習(xí)最具前景的方法之一。

模型通過框架中（至少）兩個(gè)模塊： 生成模型G（Generative Model）和 判別模型D（Discriminative Model）的互相 博弈學(xué)習(xí)產(chǎn)生相當(dāng)好的輸出。因此被稱為“對(duì)抗”網(wǎng)絡(luò)，對(duì)抗是指“生成模型”與“判別模型”相互對(duì)抗，實(shí)際上他們不僅僅是對(duì)抗，而是相互合作，相互演進(jìn)，相互促進(jìn)。

一個(gè)真實(shí)的例子就是警察和造假者之間的斗爭：假設(shè)一個(gè)造假者試圖制造假幣，而警察試圖識(shí)破它。最初，造假者沒有足夠的知識(shí)來制造看起來真實(shí)的假幣。隨著時(shí)間的流逝，造假者越來越善于制造看起來更像真實(shí)貨幣的假幣。這時(shí)，警察起初未能識(shí)別假幣，但最終他們會(huì)再次成功識(shí)別。