几种常见模式识别方法总结.docx-资料库

weixin_42202345-10676496-4744300845392886304.docx.pdf-第1页.png

第1页 / 共5页

weixin_42202345-10676496-4744300845392886304.docx.pdf-第2页.png

第2页 / 共5页

weixin_42202345-10676496-4744300845392886304.docx.pdf-第3页.png

第3页 / 共5页

weixin_42202345-10676496-4744300845392886304.docx.pdf-第4页.png

第4页 / 共5页

weixin_42202345-10676496-4744300845392886304.docx.pdf-第5页.png

第5页 / 共5页

几种常见模式识别算法整理和总结 1. K-Nearest Neighbor： K-NN 可以说是一种最直接的用来分类未知数据的方法。基本通过下面这张图跟文字说明就可以明白 K-NN 是干什么的：简单来说，K-NN 可以看成：有那么一堆你已经知道分类的数据，然后当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑离这个训练数据最近的 K 个点看看这几个点属于什么类型，然后用少数服从多数的原则，给新数据归类。实际上 K-NN 本身的运算量是相当大的，因为数据的维数往往不止 2 维，而且训练数据库越大，所求的样本间距离就越多。就拿我们 course project 的人脸检测来说，输入向量的维数是 1024 维(32x32 的图，当然我觉得这种方法比较 silly)，训练数据有上千个，所以每次求距离(这里用的是欧式距离，就是我们最常用的平方和开根号求距法) 这样每个点的归类都要花上上百万次的计算。所以现在比较常用的一种方法就是 kd-tree。也就是把整个输入空间划分成很多很多小子区域，然后根据临近的原则把它们组织为树形结构。然后搜索最近 K 个点的时候就不用全盘比较而只要比较临近几个子区域的训练数据就行了。kd-tree 的一个比较好的课件可以见下面链接： http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf 当然，kd-tree 有一个问题就是当输入维数跟训练数据数量很接近时就很难优化了。所以用 PCA(稍后会介绍)降维大多数情况下是很有必要的 2. Bayes Classifier 贝叶斯方法一篇比较科普的中文介绍可以见 pongba 的平凡而神奇的贝叶斯方法: http://mindhacks.cn/2008/09/21/the-magical-bayesian-method/，实际实现一个贝叶斯分类器之后再回头看这篇文章，感觉就很不一样。

在模式识别的实际应用中，贝叶斯方法绝非就是 post 正比于 prior*likelihood 这个公式这么简单，一般而言我们都会用正态分布拟合 likelihood 来实现。用正态分布拟合是什么意思呢？贝叶斯方法式子的右边有两个量，一个是 prior 先验概率，这个求起来很简单，就是一大堆数据中求某一类数据占的百分比就可以了，比如 300 个一堆的数据中 A 类数据占 100 个，那么 A 的先验概率就是 1/3。第二个就是 likelihood，likelihood 可以这么理解：对于每一类的训练数据，我们都用一个 multivariate 正态分布来拟合它们(即通过求得某一分类训练数据的平均值和协方差矩阵来拟合出一个正态分布)，然后当进入一个新的测试数据之后，就分别求取这个数据点在每个类别的正态分布中的大小，然后用这个值乘以原先的 prior 便是所要求得的后验概率 post 了。贝叶斯公式中还有一个 evidence，对于初学者来说，可能会一下没法理解为什么在实际运算中它不见了。实则上，evidence 只是一个让最后 post 归一化的东西，而在模式分类中，我们只需要比较不同类别间 post 的大小，归一化反而增加了它的运算量。当然，在有的地方，这个 evidence 绝对不能省，比如后文提到的 GMM 中，需要用到 EM 迭代，这时候如果不用 evidence 将 post 归一化，后果就会很可怕。 3. Principle Component Analysis PCA，译为主元分析或者主成份分析，是一种很好的简化数据的方法，也是 PR 中常见到不能再常见的算法之一。CSDN 上有一篇很不错的中文博客介绍 PCA，《主元分析(PCA) 理论分析及应用》，可以见下面链接： http://blog.csdn.net/ayw_hehe/archive/2010/07/16/5736659.aspx 对于我而言，主元分析最大的意义就是让我明白了线性代数中特征值跟特征向量究竟代表什么，从而让我进一步感受到了线性代数的博大精深魅力无穷。PCA 简而言之就是根据输入数据的分布给输入数据重新找到更能描述这组数据的正交的坐标轴。 4. Linear Discriminant Analysis LDA，基本和 PCA 是一对双生子，它们之间的区别就是 PCA 是一种 unsupervised 的映射方法而 LDA 是一种 supervised 映射方法，这一点可以从下图中一个 2D 的例子简单看出

图的左边是 PCA，它所作的只是将整组数据整体映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据内部的分类信息。因此，虽然做了 PCA 后，整组数据在表示上更加方便(降低了维数并将信息损失降到最低)，但在分类上也许会变得更加困难；图的右边是 LDA，可以明显看出，在增加了分类信息之后，两组输入映射到了另外一个坐标轴上，有了这样一个映射，两组数据之间的就变得更易区分了(在低维上就可以区分，减少了很大的运算量)。 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

资料库

几种常见模式识别方法总结.docx

相关推荐

人工智能

热门标签

最新资料