人臉識別中常用的幾種分類器

在人臉識別中有幾種常用的分類器，一是最鄰近分類器；二是線性分類器

（1）最鄰近分類器

最近鄰分類器是模式識別領域中最常用的分類方法之一，其直觀簡單，在通常的應用環境中非常有效。因此在人臉識別問題中有著廣泛的應用。最鄰近方法是這樣定義的：

假設訓練樣本（X,Y）={xi,yi | i=1,2,...n},這里xi 代表第i個樣本的特征向量，yi是該樣本的類別標簽。對于一個新的待分類樣本xi，最鄰近分類器預測該樣本的標簽的方法是，尋找與xi距離度量最近的訓練樣本，然后把該訓練樣本的標簽作為待測試樣本xi的標簽yi' ，即：

這里d(xi, xi) 代表樣本xi 與樣本xi 之間的距離度量。

最鄰近的算法非常直觀，也容易被實現，他通過距離測試樣本最近的訓練樣本的標簽來預測當前測試樣本的類別，可以適用于任何分布的數據，而且已有文獻證明，在樣本足夠多的情況下，最鄰近分類的錯誤率是比較理想的。

距離度量有很多種，一般采用的室歐氏距離。除此之外還有相關度，卡方，直方圖交，Bhattacharyya距離（又名巴氏距離）。

1）歐氏距離  ：是一個通常采用的距離定義，它是在m維空間中兩個點之間的真實距離。距離值越小，代表兩個直方圖距離越近，越相似，反之中則代表距離越遠。

2）相關度

兩直方圖之間的相關度定義如下

N等于直方圖中bin的個數，對于相關度而言，數值越大越匹配。完全匹配的數值為1，完全不匹配的是-1，值為0則表示無關聯，兩個直方圖是隨機組合。

3）卡方Chi-Square

對于卡方而言，匹配度越高，距離越小，則卡方值越低，相反，匹配值越低，距離越大，卡方值越高。完全匹配值為0，完全不匹配的值為無限值。

4）直方圖交

對于直方圖交，值越大越匹配，距離越小，越低分表示越不匹配。如果兩個直方圖都被歸一化，那么完全匹配的值為1，完全不匹配的值為0.

5）Bhattacharyya 距離

Bhattacharyya 距離又被稱之為巴氏距離。巴氏距離可用來對兩組特征直方圖的相關性進行測量，其常用來作為分類器算法。

定義如下：

對于巴氏距離數值越小表示越匹配，距離越近，而數值越大表示越不匹配，距離越遠。兩個直方圖完全匹配值為0，完全不匹配值為1.

（2）線性分類器

線性分類器(一定意義上,也可以叫做感知機) 是最簡單也很有效的分類器形式.在一個線性分類器中,可以看到SVM形成的思路,并接觸很多SVM的核心概念.用一個二維空間里僅有兩類樣本的分類問題來舉個小例子。如圖所示

C1和C2是要區分的兩個類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個分類函數，它可以將兩類樣本完全分開。一般的，如果一個線性函數能夠將樣本完全正確的分開，就稱這些數據是線性可分的，否則稱為非線性可分的。

LDA：

線性判別式分析(Linear Discriminant Analysis, LDA)，也叫做Fisher線性判別(Fisher Linear Discriminant ,FLD)，是模式識別的經典算法，它是在1996年由Belhumeur引入模式識別和人工智能領域的。性鑒別分析的基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達到抽取分類信息和壓縮特征空間維數的效果，投影后保證模式樣本在新的子空間有最大的類間距離和最小的類內距離，即模式在該空間中有最佳的可分離性。因此，它是一種有效的特征抽取方法。使用這種方法能夠使投影后模式樣本的類間散布矩陣最大，并且同時類內散布矩陣最小。就是說，它能夠保證投影后模式樣本在新的空間中有最小的類內距離和最大的類間距離，即模式在該空間中有最佳的可分離性。

二. 原理簡述：

LDA的原理是，將帶上標簽的數據（點），通過投影的方法投影到維度更低的空間中，使得投影后的點形成按類別區分的情形，即相同類別的點，在投影后的空間中距離較近，不同類別的點，在投影后的空間中距離較遠。

要說明LDA，首先得弄明白線性分類器(Linear Classifier)：因為LDA是一種線性分類器。對于K-分類的一個分類問題，會有K個線性函數：

當滿足條件：對于所有的j，都有Yk > Yj,的時候，我們就說x屬于類別k。對于每一個分類，都會用一個公式去計算一個得分值，所有公式的結果中得分最高的那個類別，就是所屬的分類了。

上式實際上就是一種投影，是將一個高維的點投影到一條高維的直線上，LDA最求的目標是，給出一個標注了類別的數據集，投影到了一條直線之后，能夠使得點盡量的按類別區分開，當k=2即二分類問題的時候，如下圖所示：

紅色的方形的點為0類的原始點、藍色的方形點為1類的原始點，經過原點的那條線就是投影的直線，從圖上可以清楚的看到，紅色的點和藍色的點被原點明顯的分開了，這個數據只是隨便畫的，如果在高維的情況下，看起來會更好一點。下面我來推導一下二分類LDA問題的公式：

假設用來區分二分類的直線（投影函數)為：

LDA分類的一個目標是使得不同類別之間的距離越遠越好，同一類別之中的距離越近越好，所以我們需要定義幾個關鍵的值。

類別i的原始中心點為：（Di表示屬于類別i的點)

類別i投影后的中心點為：

衡量類別i投影后，類別點之間的分散程度（方差）為：

最終我們可以得到一個下面的公式，表示LDA投影到w后的損失函數：

我們分類的目標是，使得類別內的點距離越近越好（集中），類別間的點越遠越好。分母表示每一個類別內的方差之和，方差越大表示一個類別內的點越分散，分子為兩個類別各自的中心點的距離的平方，我們最大化J(w)就可以求出最優的w了。想要求出最優的w，可以使用拉格朗日乘子法，但是現在我們得到的J(w)里面，w是不能被單獨提出來的，我們就得想辦法將w單獨提出來。

我們定義一個投影前的各類別分散程度的矩陣，這個矩陣的意思是，如果某一個輸入點集Di里面的點距離這個分類的中心點mi越近，則Si里面元素的值就越小，如果分類的點都緊緊地圍繞著mi，則Si里面的元素值越更接近0.

帶入Si，將J(w)分母化為：

同樣的將J(w)分子化為：

這樣損失函數可以化成下面的形式，我們的目標是求取它的最大值：

這樣就可以用拉格朗日乘子法了，但是還有一個問題，如果分子、分母是都可以取任意值的，那就會使得有無窮解，我們將分母限制為長度為1（這是用拉格朗日乘子法一個很重要的技巧），并作為拉格朗日乘子法的限制條件，帶入得到：

求導公式如下：

這樣的式子就是一個求特征值的問題了。

對于N(N>2)分類的問題，我就直接寫出下面的結論了：

又因為w=[w1,w2...wd]，所以得到：

把損失函數分解可知，我們要求的是:

最佳投影矩陣的列向量即為的d個最大的特征值所對應的特征向量(矩陣的特征向量)，且最優投影軸的個數d<=c-1(c表示類的個數).

這里想多談談特征值，特征值在純數學、量子力學、固體力學、計算機等等領域都有廣泛的應用，特征值表示的是矩陣的性質，當我們取到矩陣的前N個最大的特征值的時候，我們可以說提取到的矩陣主要的成分（這個和之后的PCA相關，但是不是完全一樣的概念）。在機器學習領域，不少的地方都要用到特征值的計算，比如說圖像識別、pagerank、LDA、還有之后將會提到的PCA等等。

Fisher線性判別是PCA+LDA。