这学期选了门模式识别课。 最常见的是，我不知道书上老师的ppt上写的是什么，然后绕道自己查资料了解。 回想起来，Ah-ha的本质原理那么简单，自己最初只是对看起来像公式的细节感到吃惊。 所以，请在这里记录下自己学到的东西，不要忘记，作为参考。
1. K-Nearest Neighbor
可以说K-NN是最直接地将未知数据分类的方法。 基本上用下图和文字说明的话，就知道K-NN在做什么了
简单来说，中小学已经有很多知道分类的数据了。 然后，新数据进来后，开始从训练数据的各点求出距离。 然后，选择与该训练数据最接近的k个点，看这些点属于什么类型，按照少数服从多数原则对新数据进行分类。 介绍中小学的比较好的教材请参考以下链接。 文字和文章排列着，我很快就明白了
3358 courses.cs.tamu.edu/rgu tier/cs 790 _ w02/l8.pdf
实际上，K-NN本身的运算量相当大。 这是因为数据的维数大多在2维以上，训练数据库越大，所要求的样本间距离越多。 在我们course project的人脸检测中，输入向量的维数为1024维(32x32的图)。 当然，我认为这种方法比较了silly。 ) )，所以训练数据成千上万，所以每次求距离) )这里使用的是欧式距离。 是我们最常用的平方和开根号距离法。 ) )那样，必须对每个点的分类进行数百万次的计算。 所以现在常用的方法之一是kd-tree。 也就是说，将整个输入空间分割为多个儿童区域，根据邻近原则将它们组织成树形结构。 然后，检索最近的k个点时，不是全面比较，而是比较与几个子区域相邻的训练数据即可。 kd-tree的好课件请参考以下链接：
3358 www.INF.ed.AC.uk/teaching/courses/inf2b/learn notes/inf2b-learn 06-LEC.pdf
当然，kd-tree中存在输入维数接近训练数据数时难以优化的问题。 所以用PCA (后述)降维往往是必要的
2. Bayes Classifier贝叶斯方法(比较科学的中文介绍pongba平凡而不可思议的贝叶斯方法33603358 mind hacks.cn/2008/09/21/the-magical-Bayesian-) 并不是与likelihood这一公式成比例的简单，一般用正态分布拟合likelihood来实现。 用正态分布拟合是什么意思？ 贝叶斯方法公式的右边有两个量。 一个是prior先验概率。 求这个很简单，只要从很多数据中求出某种数据所占的比例就可以了。 例如，如果300个数据中有100个a类数据，则a的先验概率为1/3。 第二个是likelihood。 likelihood利用多元正态分布对各级训练数据进行拟合，即通过求出某一分类训练数据的平均值和协方差矩阵来拟合正态分布，进入新的测试数据后，再对其进行拟合对于初学者来说，你可能无法理解为什么在实际运算中那个消失了。 实际上，evidence是最后一个post的规范化，但模式分类只需要比较不同类之间的post大小，规范化反而增加了运算量。 当然，在某些地方，绝对不能省略这个证据。 例如，在后述的GMM中，需要使用EM迭代。 此时，如果不通过evidence对开机自检进行标准化，就会产生可怕的结果。 Bayes方法的好参考页面包含以下链接： http://www.cs.mcgill.ca/~ mcleish/644/main.html 3358 www.Sina.com/3358 www.Sina.com.csdn有PCA，《主元分析(PCA)理论分析及应用》1111011101010101010101010101010101010101010101010101010 请参阅以下链接。 http://blog.csdn.net/ayw _ hehe/archive/2010/07/16/5736659.aspx对我来说，主元-|| http://www.Sina.com/ppx 例如，下图相对于其椭圆状分布，最容易表示该分布的坐下
标轴肯定是椭圆的长轴短轴而不是原来的x y。 那么如何求出这个长轴和短轴呢？于是线性代数就来了：我们求出这堆数据的协方差矩阵(关于什么是协方差矩阵，详见本节最后附的链接)，然后再求出这个协方差矩阵的特征值和特征向量，对应最大特征值的那个特征向量的方向就是长轴(也就是主元)的方向，次大特征值的就是第二主元的方向，以此类推。关于PCA，推荐两个不错的tutorial: (1) A tutorial on Principle Component Analysis从最基本的数学原理到应用都有，让我在被老师的讲课弄晕之后瞬间开悟的tutorial: http://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf (2) 里面有一个很生动的实现PCA的例子，还有告诉你PCA跟SVD是什么关系的，对编程实现的帮助很大(当然大多数情况下都不用自己编了):
http://www.math.ucsd.edu/~gptesler/283/pca_07-handout.pdf
4. Linear Discriminant Analysis
LDA，基本和PCA是一对双生子，它们之间的区别就是PCA是一种unsupervised的映射方法而LDA是一种supervised映射方法，这一点可以从下图中一个2D的例子简单看出
图的左边是PCA，它所作的只是将整组数据整体映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据内部的分类信息。因此，虽然做了PCA后，整组数据在表示上更加方便(降低了维数并将信息损失降到最低)，但在分类上也许会变得更加困难；图的右边是LDA，可以明显看出，在增加了分类信息之后，两组输入映射到了另外一个坐标轴上，有了这样一个映射，两组数据之间的就变得更易区分了(在低维上就可以区分，减少了很大的运算量)。
在实际应用中，最常用的一种LDA方法叫作Fisher Linear Discriminant，其简要原理就是求取一个线性变换，是的样本数据中“between classes scatter matrix”(不同类数据间的协方差矩阵)和“within classes scatter matrix”(同一类数据内部的各个数据间协方差矩阵)之比的达到最大。关于Fisher LDA更具体的内容可以见下面课件，写的很不错~
http://www.csd.uwo.ca/~olga/Courses//CS434a_541a//Lecture8.pdf
5. Non-negative Matrix Factorization
NMF，中文译为非负矩阵分解。一篇比较不错的NMF中文介绍文可以见下面一篇博文的链接，《非负矩阵分解：数学的奇妙力量》
http://chnfyn.blog.163.com/blog/static/26954632200751625243295/
这篇博文很大概地介绍了一下NMF的来龙去脉(当然里面那幅图是错的。。。)，当然如果你想更深入地了解NMF的话，可以参考Lee和Seung当年发表在Nature上面的NMF原文，"Learning the parts of objects by non-negative matrix factorization"
http://www.seas.upenn.edu/~ddlee/Papers/nmf.pdf
读了这篇论文，基本其他任何介绍NMF基本方法的材料都是浮云了。
NMF，简而言之，就是给定一个非负矩阵V，我们寻找另外两个非负矩阵W和H来分解它，使得后W和H的乘积是V。论文中所提到的最简单的方法，就是根据最小化||V-WH||的要求，通过Gradient Discent推导出一个update rule，然后再对其中的每个元素进行迭代，最后得到最小值，具体的update rule见下图，注意其中Wia等带下标的符号表示的是矩阵里的元素，而非代表整个矩阵，当年在这个上面绕了好久。。
当然上面所提的方法只是其中一种而已，在http://spinner.cofc.edu/~langvillea/NISS-NMF.pdf中有更多详细方法的介绍。
相比于PCA、LDA，NMF有个明显的好处就是它的非负，因为为在很多情况下带有负号的运算算起来都不这么方便，但是它也有一个问题就是NMF分解出来的结果不像PCA和LDA一样是恒定的。
6. Gaussian Mixture Model
GMM体贴的宝贝混合模型粗看上去跟上文所提的贝叶斯分类器有点类似，但两者的方法有很大的不同。在贝叶斯分类器中，我们已经事先知道了训练数据(training set)的分类信息，因此只要根据对应的均值和协方差矩阵拟合一个体贴的宝贝分布即可。而在GMM中，我们除了数据的信息，对数据的分类一无所知，因此，在运算时我们不仅需要估算每个数据的分类，还要估算这些估算后数据分类的均值和协方差矩阵。。。也就是说如果有1000个训练数据10租分类的话，需要求的未知数是1000+10+10(用未知数表示未必确切，确切的说是1000个1x10标志向量,10个与训练数据同维的平均向量，10个与训练数据同维的方阵)。。。反正想想都是很头大的事情。。。那么这个问题是怎么解决的呢？
这里用的是一种叫EM迭代的方法。
具体使用方法可以参考http://neural.cs.nthu.edu.tw/jang/books/dcpr/doc/08gmm.pdf 这份台湾清华大学的课件，写的真是相当的赞，实现代码的话可以参考：
1. 倩倩的博客http://www.cnblogs.com/jill_new/archive/2010/12/01/1893851.html 和
2. http://www.cs.ru.nl/~ali/EM.m
当然 Matlab里一般也会自带GMM工具箱，其用法可以参考下面链接：
http://www.mathworks.com/help/toolbox/stats/gmdistribution.fit.html