首先自我檢討一下，這篇拖得實在是太久了。主要是前一陣子回了趟國，去了趟阿拉斯加看大冰塊，還去了趟夏威夷潛水。正所謂業精於勤而荒於嬉，我得收收心啦。

在上一篇文章中在下淺顯地總結了一些流行的聚類（clustering）的演算法，在這篇以及下篇文章我們來聊一聊一些流行的分類（classification）演算法。分類演算法跟屬於unsupervised learning的聚類演算法不同，屬於supervised learning。用人話翻譯一下，分類演算法嘗試著給資料貼上標籤，而且這些標籤都是可以觀測到的。比如把人分成男人跟女人，把男人分成喜歡男人的跟喜歡女人的。

KNN(K Nearest Neighbours)

： 這個估計要算所有分類演算法中間最簡單了。它的內在邏輯我們老祖宗們已經參得很透了，就是所謂的“物以類聚，人以群分”。你跟什麼樣的人混在一起，你就是什麼樣的人。具體到這個演算法本身，就是對我們要分析的這個樣本，劃定一個它的鄰域，鄰域的大小由鄰居（neighbours）的多少來界定，這裡是K個鄰居，一般來說K是要奇數。然後根據鄰居們的標籤來投票，把得票最多的那個標籤貼到我們要分析的這個樣本上，奇數K是為了避免平票。

用數學表達起來就是：算了，還是不用數學表達了，一圖勝千言，我們貼張圖吧。

一些分類方法（Classification）的總結 I

一些分類方法（Classification）的總結 I

上圖中，綠色帶問號的圓點就是我們要分析的樣本，實線劃出來的圈是小鄰域，虛線畫出來的圈是大鄰域。小鄰域的K=3，問號綠色圓點應該貼上紅色三角標籤；大鄰域的K=5， 問號綠色圓點應該貼上藍色方塊標籤。這幅圖是極好的，它不但直觀地表述了KNN演算法是怎麼實現的，還一針見血地指出了其弱點。它的弱點主要有兩個，第一個是K的取值，第二個是對鄰域的劃分。K如果取小了，分類結果會對噪聲（noise）很敏感；K如果取大了，分類的邊界又變得不是那麼清晰。鄰域的劃分對KNN的分類結果也是至關重要的，上圖展示的二維空間中，兩個維度的權重一樣，所以鄰域是個圓形；如果兩個維度的權重不一樣，鄰域的形狀會發生變化，直接印象分類結果。所以KNN一般會在對資料樣本發一系列metric learning的連招之後使用。

Logistic regression

：

Logistic regression一般是用來做binary的分類的，不過它也可以被用到多中情況的分類，只要多用幾次就可以了。比如有五個類別，第一次判定是不是類別一，第二次從不是類別一的樣本中判別是不是類別二，以此類推，如下圖所示。

一些分類方法（Classification）的總結 I

一些分類方法（Classification）的總結 I

對於一個沒有明顯的推導規則的分類問題（0和1），單純地指出某樣本應該是0還是1是很困難的，Logistic regression幫助我們來估計樣本是0還是1的條件機率。分類0和1的假設給我們提供了很多的便利，因為我們可以很直接地得出

Pr(Y = 1) = \textbf{E}[Y], Y = 0 \ or\ 1

，同樣我們有

Pr(Y = 1 | X = x) = \textbf{E}[Y|X = x]

，其中Y是dependent variable， X是independent variable。

假設

Pr(Y = 1| X = x) = p(x;\theta)

，當給定

X = x

時，

Y= 1

的條件機率是一個關於

x

和

\theta

的函式，其中

x

是X的觀測值，

\theta

是一系列引數。再假設所有的樣本都是相互獨立的，於是我們如下conditional likelihood function：

L(\theta_0,\theta) = \prod_{i=1}^{n}Pr(Y = y_i|X = x_i) = \prod_{i=1}^{n}p(x_i;\theta_0, \theta)^{y_i}(1 - p(x_i;\theta_0, \theta)^{1-y_i})

，其中

y_i = 0 \ or \ 1

兩邊取log，得到：

l(\theta_0, \theta) = \sum_{i=1}^{n}{y_i \cdot log(p(x_i; \theta_0, \theta)) + (1-y_i) \cdot log(1 - p(x_i;\theta_0, \theta))} \\ = \sum_{i=1}^{n}{log(1-p(x_i;\theta_0, \theta)) + \sum_{i=1}^{n}{y_i\cdot log(\frac{p(x_i;\theta_0,\theta)}{1-p(x_i;\theta_0,\theta)} )}}

接下來是關鍵性的一步啦！我們假設：

log\frac{p(x;\theta_0,\theta)}{1-p(x;\theta_0,\theta)} = \theta_0+x\cdot\theta

所以

p(x;\theta_0,\theta) = \frac{1}{1+e^{-(\theta_0+x\cdot\theta)}}

所以

l(\theta_0,\theta) = \sum_{i=1}^{n}{-log1+e^{\theta_0+x_i \cdot \theta}}+\sum_{i=1}^{n}{y_i(\theta_0+x_i\cdot\theta)}

求

\theta_0^*,\theta^*

使得

l(\theta_0,\theta)

最小，從而獲得最優引數。

這個方法的牛逼之處在於用死sigmoid函式，把一個【0，1】之間的變數轉化到實數域上來，從而克服了OLS linear regression可能給出【0，1】之外的機率值的缺點。

讀者答疑：

姓顏色的小學生

邏輯迴歸可以直接進行多分類吧，把伯努利分佈改成multinoulli分佈

這是一個非常好的問題！我之前並沒有考慮到，今天早上我在健身房的時候想了一下，現在嘗試著回答一下。首先我擅自把multinoulli理解成multinomial分佈，如果理解有錯誤還請@姓顏色的小學生 糾正哈！其實用multinomial跟用好幾次Binary Logistic Regression解決的是兩個問題，而在某些特殊情況下，這兩種方法的結果是一樣的。用multinomial的話，算出來的機率是一個unconditional probability，也就是

P(X=k)

，其中k是指第k中分類。而用多次binary算出來的是一個conditional probably，也就是

P(X=k | X \notin \{1,2,3, ... k-1\})

。用Multinomial的話有一個條件，各個分類之間必須是相互獨立的；而用多次Binary的話不需要這個條件（都算條件機率，必然不需要independency）。而當這個獨立性條件滿足的時候，兩種方法算出來的結果應該是一樣的。用比較淺顯地話來說，multinomial可以用來解決男人女人不男不女（假設既男又女不存在）的問題，但是不能解決喜歡男人的人和男人女人不男不女的問題。希望我把問題說清楚了，如果有什麼不清楚的地方還請接著提問哈！

SVM

：

Support Vector Machine，這個我特地查了一下中文，叫做“支援向量學習機”，翻譯得非常直白。這是一個supervised learning model，一般用於classification或者regression。這裡我們主要講classification的情況。SVM的中心思想就是尋找一根hyperplane來把兩個不同class分開來。理論上來說，我們可以找到無數跟這樣的hyperplane，所以我們要再加一個限定條件，我們要找一根能使margin最大的hyperplane。一圖勝千言，下面我們貼張圖：

一些分類方法（Classification）的總結 I

一些分類方法（Classification）的總結 I

我們稱那個Gap叫做margin，也就是那兩條虛線之間的距離。我們稱這兩條虛線叫做support plane，Support vectors就是在綠線上面的點。如圖可見，當中那條紅線是使margin最大的那條hyperplane。

從intuition上面來理解，貌似SVM還是蠻簡單的，接下來我們就來嚴謹地用數學來表達一遍吧！在開始寫公式之前，我們還是先來看張圖吧：

一些分類方法（Classification）的總結 I

一些分類方法（Classification）的總結 I

這張圖的意思就是經過一系列的normalization，我們可以把中間那條紅線用如下等式來表示：

\overrightarrow{w}\cdot\overrightarrow{x} + b = 0

而與它對應的兩條support plane分別可以用以下等式來表示：

\overrightarrow{w}\cdot\overrightarrow{x}+b=1

\overrightarrow{w}\cdot\overrightarrow{x}+b=-1

假設在虛線上的紅點中的一個是向量

\overrightarrow{x_1}

，在虛線上面的星星是

\overrightarrow{x_2}

，所以我們有

\overrightarrow{w}\cdot (\overrightarrow{x_1} - \overrightarrow{x_2})=2

Normalize一下後，兩個support plane之間的margin D：

D = 2 / ||\overrightarrow{w}||

我們要最大化D，其實也就是相當於最小化

\frac{1}{2}||\overrightarrow{w}||^2

。這裡的1/2是為了之後求導數方便的。所以SMV的Objectie Function是：

\min \frac{1}{2} ||\overrightarrow{w}||^2 \\ s.t. \quad (\overrightarrow{w} \cdot \overrightarrow{x_i} +b) \geq 1, \quad if \ y_i = 1 \\ (\overrightarrow{w} \cdot \overrightarrow{x_i} +b) \leq -1, \quad if \ y_i = -1

那兩個約束條件可以合併成一個：

y_i (\overrightarrow{w} \cdot \overrightarrow{x_i} + b) \geq 1

Non-separable Case：

看上去蠻簡單的對不對？但是如果我們仔細來想一想，萬一找不到一條hyperplane把兩坨點分開來怎麼辦？也就是說萬一出現了下圖這樣的情況怎麼辦？

一些分類方法（Classification）的總結 I

一些分類方法（Classification）的總結 I

我們需要加一個penalty term，於是Objective Function就可以寫成這樣：

\min \frac{1}{2}||\overrightarrow{w}||^2 + C \sum_{i=1}^{m} \xi_i \\ s.t. \quad y_i(\overrightarrow{w} \cdot \overrightarrow{x_i} +b) \geq 1-\xi_i, \quad \xi_i \geq 0

把上面這個最佳化問題寫成QP的形式：

\frac{1}{m} \sum_{i=1}^{m} l(\overrightarrow{w} \cdot \overrightarrow{x_i} + b, y_i) + \frac{1}{2} ||\overrightarrow{w}||^2

where

l

is no longer the zero-one loss， but is called the “hinge-loss”：

l(y, \hat{y}) = \max (0, 1 - y\hat{y})

。

Non-linear Case：

如果線性的hyperplane不足以解釋資料複雜性，我們可以把資料對映到一個高維的空間，然後找到一個線性的hyperplane來解釋資料的複雜性。寫成公式就是：

\overrightarrow{x} \mapsto \Phi(\overrightarrow{x})

and then learn the map from

\Phi(\overrightarrow{x})

to

y

：

f(\overrightarrow{x}) = \overrightarrow{w} \cdot \Phi(\overrightarrow{x}) + b

舉一個Polynomial Mapping的例子：

\Phi: R^2 \mapsto R^2 \\ (x_1,x_2) \mapsto (z_1, z_2, z_3) := \left(x_1^2, \sqrt{2}x_1x_2, x_2^2\right)

Choosing a good mapping

\Phi(\cdot)

（encoding prior knowledge + getting right complexity of function class） for your porblem imporves results。

The Kernel Trick：

有時候

\Phi(\overrightarrow{x})

會很大，使得解這個QP問題的難度大大增加。 The Representer theorem （Kimeldorf & Wahba， 1971） shows that （for SVMs as a special case）：

\overrightarrow{w}=\sum_{i=1}^{m} \alpha_i \Phi(\overrightarrow{x_i})

for some variables

\alpha

， instead of optimizing

\overrightarrow{w}

directly we can thus optimize

\alpha

。 The decision rule is now：

f(x) = \sum_{i=1}^{m} \alpha_i \Phi(\overrightarrow{x_i}) \cdot \Phi(\overrightarrow{x}) + b

We call

K(x_i, x) = \Phi(x_i)\cdot \Phi(x)

the

kernel function。

We can rewrite all the SVM equations we saw before， but with the

\overrightarrow{w}=\sum_{i=1}^{m}\alpha_i\Phi(\overrightarrow{x_i})

equation。

Decision function：

f(x)=\sum_{i=1}^{m}\alpha_i \Phi(\overrightarrow{x_i}) \cdot \Phi(\overrightarrow{x}) + b \\ = \sum_{m=1}^{m}\alpha_i K(\overrightarrow{x_i}, \overrightarrow{x})+b

Dual formulation：

\min P(\overrightarrow{w}, b) = \frac{1}{2} ||\sum_{i=1}^{m}\alpha_i \Phi(\overrightarrow{x_i})||^2 + C\sum_{i=1}^{m}H_1(y_if(\overrightarrow{x_i}))\\ H_1(z) = \max(0,1-z)

優點：因為SVM是QP問題，所以訓練它比較容易，在高維資料上的表現也不錯。

缺點：Kernel Function的選擇很重要！

下篇預告：

Neural network

decision trees

Random forests

Naive Bayesian