本文關(guān)鍵詞：模式識(shí)別，由筆耕文化傳播整理發(fā)布。

這學(xué)期選了門模式識(shí)別的課。發(fā)現(xiàn)最常見(jiàn)的一種情況就是，書上寫的老師ppt上寫的都看不懂，，然后繞了一大圈去自己查資料理解，回頭看看發(fā)現(xiàn)，Ah-ha，原來(lái)本質(zhì)的原理那么簡(jiǎn)單，自己一開(kāi)始只不過(guò)被那些看似formidable的細(xì)節(jié)嚇到了。所以在這里把自己所學(xué)的一些點(diǎn)記錄下來(lái)，供備忘，也供參考。

1. K-Nearest Neighbor

K-NN可以說(shuō)是一種最直接的用來(lái)分類未知數(shù)據(jù)的方法�；就ㄟ^(guò)下面這張圖跟文字說(shuō)明就可以明白K-NN是干什么的

簡(jiǎn)單來(lái)說(shuō)，K-NN可以看成：有那么一堆你已經(jīng)知道分類的數(shù)據(jù)，然后當(dāng)一個(gè)新數(shù)據(jù)進(jìn)入的時(shí)候，就開(kāi)始跟訓(xùn)練數(shù)據(jù)里的每個(gè)點(diǎn)求距離，然后挑離這個(gè)訓(xùn)練數(shù)據(jù)最近的K個(gè)點(diǎn)看看這幾個(gè)點(diǎn)屬于什么類型，然后用少數(shù)服從多數(shù)的原則，給新數(shù)據(jù)歸類。一個(gè)比較好的介紹k-NN的課件可以見(jiàn)下面鏈接，圖文并茂，我當(dāng)時(shí)一看就懂了

實(shí)際上K-NN本身的運(yùn)算量是相當(dāng)大的，因?yàn)閿?shù)據(jù)的維數(shù)往往不止2維，而且訓(xùn)練數(shù)據(jù)庫(kù)越大，所求的樣本間距離就越多。就拿我們course project的人臉檢測(cè)來(lái)說(shuō)，輸入向量的維數(shù)是1024維(32x32的圖，當(dāng)然我覺(jué)得這種方法比較silly)，訓(xùn)練數(shù)據(jù)有上千個(gè)，所以每次求距離(這里用的是歐式距離，就是我們最常用的平方和開(kāi)根號(hào)求距法) 這樣每個(gè)點(diǎn)的歸類都要花上上百萬(wàn)次的計(jì)算。所以現(xiàn)在比較常用的一種方法就是kd-tree。也就是把整個(gè)輸入空間劃分成很多很多小子區(qū)域，然后根據(jù)臨近的原則把它們組織為樹(shù)形結(jié)構(gòu)。然后搜索最近K個(gè)點(diǎn)的時(shí)候就不用全盤比較而只要比較臨近幾個(gè)子區(qū)域的訓(xùn)練數(shù)據(jù)就行了。kd-tree的一個(gè)比較好的課件可以見(jiàn)下面鏈接：

當(dāng)然，kd-tree有一個(gè)問(wèn)題就是當(dāng)輸入維數(shù)跟訓(xùn)練數(shù)據(jù)數(shù)量很接近時(shí)就很難優(yōu)化了。所以用PCA(稍后會(huì)介紹)降維大多數(shù)情況下是很有必要的

2. Bayes Classifier

貝葉斯方法一篇比較科普的中文介紹可以見(jiàn)pongba的平凡而神奇的貝葉斯方法: ，實(shí)際實(shí)現(xiàn)一個(gè)貝葉斯分類器之后再回頭看這篇文章，感覺(jué)就很不一樣。

在模式識(shí)別的實(shí)際應(yīng)用中，貝葉斯方法絕非就是post正比于prior*likelihood這個(gè)公式這么簡(jiǎn)單，一般而言我們都會(huì)用正態(tài)分布擬合likelihood來(lái)實(shí)現(xiàn)。

用正態(tài)分布擬合是什么意思呢？貝葉斯方法式子的右邊有兩個(gè)量，一個(gè)是prior先驗(yàn)概率，這個(gè)求起來(lái)很簡(jiǎn)單，就是一大堆數(shù)據(jù)中求某一類數(shù)據(jù)占的百分比就可以了，比如300個(gè)一堆的數(shù)據(jù)中A類數(shù)據(jù)占100個(gè)，那么A的先驗(yàn)概率就是1/3。第二個(gè)就是likelihood，likelihood可以這么理解：對(duì)于每一類的訓(xùn)練數(shù)據(jù)，我們都用一個(gè)multivariate正態(tài)分布來(lái)擬合它們(即通過(guò)求得某一分類訓(xùn)練數(shù)據(jù)的平均值和協(xié)方差矩陣來(lái)擬合出一個(gè)正態(tài)分布)，然后當(dāng)進(jìn)入一個(gè)新的測(cè)試數(shù)據(jù)之后，就分別求取這個(gè)數(shù)據(jù)點(diǎn)在每個(gè)類別的正態(tài)分布中的大小，然后用這個(gè)值乘以原先的prior便是所要求得的后驗(yàn)概率post了。

貝葉斯公式中還有一個(gè)evidence，對(duì)于初學(xué)者來(lái)說(shuō)，可能會(huì)一下沒(méi)法理解為什么在實(shí)際運(yùn)算中它不見(jiàn)了。實(shí)則上，evidence只是一個(gè)讓最后post歸一化的東西，而在模式分類中，我們只需要比較不同類別間post的大小，歸一化反而增加了它的運(yùn)算量。當(dāng)然，在有的地方，這個(gè)evidence絕對(duì)不能省，比如后文提到的GMM中，需要用到EM迭代，這時(shí)候如果不用evidence將post歸一化，后果就會(huì)很可怕。

Bayes方法一個(gè)不錯(cuò)的參考網(wǎng)頁(yè)可見(jiàn)下面鏈接：

~mcleish/644/main.html

3. Principle Component Analysis

PCA，譯為主元分析或者主成份分析，是一種很好的簡(jiǎn)化數(shù)據(jù)的方法，也是PR中常見(jiàn)到不能再常見(jiàn)的算法之一。CSDN上有一篇很不錯(cuò)的中文博客介紹PCA，《主元分析(PCA)理論分析及應(yīng)用》，可以見(jiàn)下面鏈接：

對(duì)于我而言，主元分析最大的意義就是讓我明白了線性代數(shù)中特征值跟特征向量究竟代表什么，從而讓我進(jìn)一步感受到了線性代數(shù)的博大精深魅力無(wú)窮。- -|||

PCA簡(jiǎn)而言之就是根據(jù)輸入數(shù)據(jù)的分布給輸入數(shù)據(jù)重新找到更能描述這組數(shù)據(jù)的正交的坐標(biāo)軸，比如下面一幅圖，對(duì)于那個(gè)橢圓狀的分布，最方便表示這個(gè)分布的坐標(biāo)軸肯定是橢圓的長(zhǎng)軸短軸而不是原來(lái)的x y。

那么如何求出這個(gè)長(zhǎng)軸和短軸呢？于是線性代數(shù)就來(lái)了：我們求出這堆數(shù)據(jù)的協(xié)方差矩陣(關(guān)于什么是協(xié)方差矩陣，詳見(jiàn)本節(jié)最后附的鏈接)，然后再求出這個(gè)協(xié)方差矩陣的特征值和特征向量，對(duì)應(yīng)最大特征值的那個(gè)特征向量的方向就是長(zhǎng)軸(也就是主元)的方向，次大特征值的就是第二主元的方向，以此類推。

關(guān)于PCA，推薦兩個(gè)不錯(cuò)的tutorial:

(1) A tutorial on Principle Component Analysis從最基本的數(shù)學(xué)原理到應(yīng)用都有，讓我在被老師的講課弄暈之后瞬間開(kāi)悟的tutorial:

(2) 里面有一個(gè)很生動(dòng)的實(shí)現(xiàn)PCA的例子，還有告訴你PCA跟SVD是什么關(guān)系的，對(duì)編程實(shí)現(xiàn)的幫助很大(當(dāng)然大多數(shù)情況下都不用自己編了):

 ~gptesler/283/pca_07-handout.pdf

4. Linear Discriminant Analysis

LDA，基本和PCA是一對(duì)雙生子，它們之間的區(qū)別就是PCA是一種unsupervised的映射方法而LDA是一種supervised映射方法，這一點(diǎn)可以從下圖中一個(gè)2D的例子簡(jiǎn)單看出

。

~olga/Courses//CS434a_541a//Lecture8.pdf 

5. Non-negative Matrix Factorization

NMF，中文譯為非負(fù)矩陣分解。一篇比較不錯(cuò)的NMF中文介紹文可以見(jiàn)下面一篇博文的鏈接，《非負(fù)矩陣分解：數(shù)學(xué)的奇妙力量》

這篇博文很大概地介紹了一下NMF的來(lái)龍去脈(當(dāng)然里面那幅圖是錯(cuò)的。。。)，當(dāng)然如果你想更深入地了解NMF的話，可以參考Lee和Seung當(dāng)年發(fā)表在Nature上面的NMF原文，"Learning the parts of objects by non-negative matrix factorization"

~ddlee/Papers/nmf.pdf

讀了這篇論文，基本其他任何介紹NMF基本方法的材料都是浮云了。

NMF，簡(jiǎn)而言之，就是給定一個(gè)非負(fù)矩陣V，我們尋找另外兩個(gè)非負(fù)矩陣W和H來(lái)分解它，使得后W和H的乘積是V。論文中所提到的最簡(jiǎn)單的方法，就是根據(jù)最小化||V-WH||的要求，通過(guò)Gradient Discent推導(dǎo)出一個(gè)update rule，然后再對(duì)其中的每個(gè)元素進(jìn)行迭代，最后得到最小值，具體的update rule見(jiàn)下圖，注意其中Wia等帶下標(biāo)的符號(hào)表示的是矩陣?yán)锏脑�，而非代表整個(gè)矩陣，當(dāng)年在這個(gè)上面繞了好久。。

當(dāng)然上面所提的方法只是其中一種而已，在~langvillea/NISS-NMF.pdf中有更多詳細(xì)方法的介紹。

相比于PCA、LDA，NMF有個(gè)明顯的好處就是它的非負(fù)，因?yàn)闉樵诤芏嗲闆r下帶有負(fù)號(hào)的運(yùn)算算起來(lái)都不這么方便，但是它也有一個(gè)問(wèn)題就是NMF分解出來(lái)的結(jié)果不像PCA和LDA一樣是恒定的。

6. Gaussian Mixture Model

這里用的是一種叫EM迭代的方法。

1. 倩倩的博客 和

2. ~ali/EM.m

當(dāng)然 Matlab里一般也會(huì)自帶GMM工具箱，其用法可以參考下面鏈接：

  本文關(guān)鍵詞：模式識(shí)別，由筆耕文化傳播整理發(fā)布。