几种常见模式识别算法整理和总结

几种常见模式识别算法整理和总结

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

这学期选了门模式识别的课。发现最常见的一种情况就是,书上写的老师ppt上写的都看不懂,然后绕了一大圈去自己查资料理解,回头看看发现,Ah-ha,原来本质的原理那么简单,自己一開始仅仅只是被那些看似formidable的细节吓到了。所以在这里把自己所学的一些点记录下来,供备忘,也供參考。

 

 

1. K-Nearest Neighbor

K-NN能够说是一种最直接的用来分类未知数据的方法。基本通过以下这张图跟文字说明就能够明确K-NN是干什么的

 

knn

简单来说,K-NN能够看成:有那么一堆你已经知道分类的数据,然后当一个新数据进入的时候,就開始跟训练数据里的每一个点求距离,然后挑离这个训练数据近期的K个点看看这几个点属于什么类型,然后用少数服从多数的原则,给新数据归类。一个比較好的介绍k-NN的课件能够见以下链接,图文并茂,我当时一看就懂了

http://courses.cs.tamu.edu/rgutier/cs790_w02/l8.pdf

 

实际上K-NN本身的运算量是相当大的,由于数据的维数往往不止2维,并且训练数据库越大,所求的样本间距离就越多。就拿我们course project的人脸检測来说,输入向量的维数是1024维(32×32的图,当然我认为这样的方法比較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先验概率,这个求起来非常easy,就是一大堆数据中求某一类数据占的百分比就能够了,比方300个一堆的数据中A类数据占100个,那么A的先验概率就是1/3。第二个就是likelihood,likelihood能够这么理解:对于每一类的训练数据,我们都用一个multivariate正态分布来拟合它们(即通过求得某一分类训练数据的平均值和协方差矩阵来拟合出一个正态分布),然后当进入一个新的測试数据之后,就分别求取这个数据点在每一个类别的正态分布中的大小,然后用这个值乘以原先的prior便是所要求得的后验概率post了。
贝叶斯公式中另一个evidence,对于刚開始学习的人来说,可能会一下没法理解为什么在实际运算中它不见了。实则上,evidence仅仅是一个让最后post归一化的东西,而在模式分类中,我们仅仅须要比較不同类别间post的大小,归一化反而添加�了它的运算量。当然,在有的地方,这个evidence绝对不能省,比方后文提到的GMM中,须要用到EM迭代,这时候假设不用evidence将post归一化,后果就会非常可怕。

Bayes方法一个不错的參考网页可见以下链接:

3. Principle Component Analysis
PCA,译为主元分析或者主成份分析,是一种非常好的简化数据的方法,也是PR中常见到不能再常见的算法之中的一个。CSDN上有一篇非常不错的中文博客介绍PCA,《主元分析(PCA)理论分析及应用》,能够见以下链接:
对于我而言,主元分析最大的意义就是让我明确了线性代数中特征值跟特征向量到底代表什么,从而让我进一步感受到了线性代数的博大精深魅力无穷。- -|||

PCA简而言之就是依据输入数据的分布给输入数据又一次找到更能描写叙述这组数据的正交的坐标轴,比方以下一幅图,对于那个椭圆状的分布,最方便表示这个分布的坐标轴肯定是椭圆的长轴短轴而不是原来的x y。
PCA
那么怎样求出这个长轴和短轴呢?于是线性代数就来了:我们求出这堆数据的协方差矩阵(关于什么是协方差矩阵,详见本节最后附的链接),然后再求出这个协方差矩阵的特征值和特征向量,相应最大特征值的那个特征向量的方向就是长轴(也就是主元)的方向,次大特征值的就是第二主元的方向,以此类推。

关于PCA,推荐两个不错的tutorial:
(1) A tutorial on Principle Component Analysis从最主要的数学原理到应用都有,让我在被老师的讲课弄晕之后瞬间开悟的tutorial:
(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的样例简单看出

lda

图的左边是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等带下标的符号表示的是矩阵里的元素,而非代表整个矩阵,当年在这个上面绕了好久。。

nmf

当然上面所提的方法仅仅是当中一种而已,在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个1×10标志向量,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

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118896.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Mybatis的多表关联查询(多对多)「建议收藏」

    Mybatis的多表关联查询(多对多)「建议收藏」Mybatis的多表关联查询(多对多)项目目录结构实现Role到User多对多业务要求用户与角色的关系模型编写角色实体类编写Role持久层接口实现的SQL语句编写映射文件测试代码实现User到Role的多对多业务要求编写用户实体类编写User持久层接口实现的SQL语句编写映射文件测试代码mybatis中的多表查询: 示例:用户和角色 一个用户可以有多个角色 一个角色可以赋予多个用户 步骤: 1、建立两张表:用户表,角色表 让用户表和角色表具有多对多的关

  • mac navicat 激活码(注册激活)

    (mac navicat 激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

  • RTSP协议解析_RTP协议

    RTSP协议解析_RTP协议RTSP被用于建立的控制媒体流的传输,它为多媒体服务扮演“网络远程控制”的角色。尽管有时可以把RTSP控制信息和媒体数据流交织在一起传送,但一般情况RTSP本身并不用于转送媒体流数据。媒体数据的传送可通过RTP/RTCP等协议来完成。一次基本的RTSP操作过程是:首先,客户端连接到流服务器并发送一个RTSP描述命令(DESCRIBE)。流服务器通过一个SDP描述来进行反馈,反馈信息包括流数

  • h3c路由器远程管理_h3c无线路由器怎么设置

    h3c路由器远程管理_h3c无线路由器怎么设置H3C路由器telnet进去以后重启的命令是什么啊?在用户模式下输入,reboot建议在重启之前进行设备配置的保存。避免丢失最近的配置操作。保存设备配置命令为:在用户模式下输入,save输入以上两种命令时,均会自动弹出提示信息,要求管理员确认是否进行重启或保存配置操作,弹出提示信息后输入Y即可。Y代表确认(yes)。H3C路由交换机清除所有配置的命令是?H3C路由交换机清除所有配置的命令是:re…

    2022年10月17日
  • 慧荣SM2246EN开卡Toggle 8贴东芝闪存SSD失败解决方法[通俗易懂]

    慧荣SM2246EN开卡Toggle 8贴东芝闪存SSD失败解决方法[通俗易懂]如果你的固态硬盘是慧荣SM2246EN主控的,且闪存为8贴9D2H9E2H9DDJ9EDJ9EFK9DFK9DFL9EFL9CDJ等8Die4CE的,那么遇到开卡失败的话,可以尝试下面的方法来解决:打开慧荣SM2246EN量产工具文件夹中的FlashDB文件夹,找到里面的Flash.SET(闪存参数配置)文件,用记事本打开此文件后,把对应的闪存参数第46项数值(十六进制)适当降低1-6(十六进制)即可解决。比如下面以9DDJ为例:减少后,再次去开卡,应该就能过了,如果你也遇到

  • AVC1与H264的差别

    AVC1与H264的差别

    2021年11月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号