程序员经验分享-hwhale

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

2023-11-15

这学期选了门模式识别的课。发现最常见的一种情况就是，书上写的老师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维(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归一化，后果就会很可怕。
Bayes方法一个不错的参考网页可见下面链接：
3. Principle Component Analysis
PCA，译为主元分析或者主成份分析，是一种很好的简化数据的方法，也是PR中常见到不能再常见的算法之一。CSDN上有一篇很不错的中文博客介绍PCA，《主元分析(PCA)理论分析及应用》，可以见下面链接：
对于我而言，主元分析最大的意义就是让我明白了线性代数中特征值跟特征向量究竟代表什么，从而让我进一步感受到了线性代数的博大精深魅力无穷。- -|||
PCA简而言之就是根据输入数据的分布给输入数据重新找到更能描述这组数据的正交的坐标轴，比如下面一幅图，对于那个椭圆状的分布，最方便表示这个分布的坐标轴肯定是椭圆的长轴短轴而不是原来的x y。
那么如何求出这个长轴和短轴呢？于是线性代数就来了：我们求出这堆数据的协方差矩阵(关于什么是协方差矩阵，详见本节最后附的链接)，然后再求出这个协方差矩阵的特征值和特征向量，对应最大特征值的那个特征向量的方向就是长轴(也就是主元)的方向，次大特征值的就是第二主元的方向，以此类推。
关于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个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

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

深度学习宝典

机器学习

模式识别常用算法

几种常见模式识别算法整理和总结 的相关文章

  • uses sdk:minSdkVersion 16 cannot be smaller than version 17 declared in library [:flutter_inappwebvi

    0 简述 1 报错信息 2 问题原因 3 解决方案 简述 今天用到flutter的一个第三方webview框架 但是无法正常编译 编译了两次都失败了 报错信息 uses sdk minSdkVersion 16 cannot be smal

  • Java面试题第八天

    一 Java面试题第八天 1 如何实现对象克隆 浅克隆 浅克隆就是我们可以通过实现Cloneable接口 重写clone 这种方式就叫浅克隆 浅克隆 引用类型的属性 是指向同一个内存地址 但是如果引用类型的属性也进行浅克隆就是深克隆 深克隆

  • 空调工作原理

    1 变频空调 工作原理 变频 采用了比较先进的技术 启动时电压较小 可在低电压和低温度条件下启动 这对于某些地区由于电压不稳定或冬天室内温度较低而空调难以启动的情况 有一定的改善作用 由于实现了压缩机的无级变速 它也可以适应更大面积的制冷制

随机推荐

  • 8、es---深入聚合数据分析

    一 bucket与metric 1 bucket相当于mysql的group by 2 metric 对一个数据分组执行的统计 比如说求平均值 求最大值 求最小值 二 实战 1 例1 查询参数及结果说明 GET tvs sales sear

  • 欧拉降幂（广义欧拉降幂）

    第一个要求a和p互质 第二个和第三个是广义欧拉降幂 不要求a和p互质 但要求b和的大小关系 A K A K m m mod m K gt m 1 证明如下 1 若 A m 1 根据欧拉定理 A m 1 mod m 即可轻易得证 2 若 A

  • Java基础之比较器

    文章目录 一 背景 二 Comparable 自然排序 三 Comparator 定制排序 一 背景 Java中的对象 正常情况下 只能进行比较 或 不能使用 gt 或 lt 的 但是在开发场景中 我们需要对多个对象进行排序 言外之意 就需

  • 斗地主练习（按照斗地主的规则，完成洗牌发牌的动作。）

    按照斗地主的规则 完成洗牌发牌的动作 具体规则 使用54张牌 打乱顺序 三个玩家参与游戏 三人交替摸牌 每人17张牌 最后三张留作底牌 手中的牌按从小到大的顺序排列 import java util ArrayList import jav

  • 记下对方的证据，抹掉自己的证据

    记下对方的证据 抹掉自己的证据 http blog vsharing com itdays A908824 html 原创 记下对方的证据 抹掉自己的证据 公司另一个部门让我告诉他们 我们的国外那家技术服务商的服务怎么样 正好被那家公司给折

  • 【有奖下载】IMG DXT GPU 让光线追踪触手可及

    继 IMG CXT GPU 之后 2023 年 1 月 Imagination 正式推出 IMG DXT GPU 这款开创性的光追 GPU 将为所有移动设备用户带来最先进的图形技术 从高端设备到主流设备 D 系列的首款产品 IMG DXT

  • this is biaoti

    富文本咯咯咯咯咯咯 早上好吃了吗

  • LVS/NAT双主 + keepalived负载均衡实现

    一 keepalived简介 keepalived是分布式部署解决系统高可用的软件 结合lvs LinuxVirtual Server 使用 解决单机宕机的问题 keepalived是一个基于VRRP协议来实现IPVS的高可用的解决方案 对

  • properties文件中用注释的方法

    很简单 用

  • DPDK-流分类与多队列

    1 前言 多队列与流分类技术基本被应用到所有DPDK网关类项目中 比如开源的DPVS 美团的四层网关等等 利用多队列及分流技术可以使得网卡更好地与多核处理器 多任务系统配合 从而达到更高效IO处理的目的 这章节以英特尔的网卡为例 介绍多队列

  • 百度翻译破解

    破解百度翻译 1 页面基本信息 打开对应页面 直接搜索 百度翻译 打开百度翻译如图 需求 获取某个单词或句子的翻译结果 键入要翻译的关键字后 页面局部刷新 依旧使用的是AJAX 2 数据抓包 进入XHP页面获取Ajax实际请求地址及相关参数

  • Sqli-labs靶场详细攻略Less 34-37

    Less 34 37 Less 34 POST Bypass AddSlashes 这一关还是进行宽字节注入 与上一关的区别在于使用了post方法进行传递 先试一下上一关的注入代码 因为这一关是登录 就使用之前的dumb账号 dumb df

  • onenote标注pdf笔记_使用OneNote做文献阅读笔记的正确打开方式

    又到了紧张赶毕业论文的时候了 写毕业论文的时候 文献阅读是一个必不可少的环节 但是 当需要阅读的文献越来越多 需要记录的阅读笔记也越来越多时 问题来了 有没有自动保存笔记的方法 文献阅读的笔记太多 如何快速找到想要的文献笔记 有没有方法可以

  • QGIS：生成网格的步骤

    第一步 打开工具箱中的 创建网格 第二步 按照自己的需求设置参数 特别说明 1 网格类型要选 矩形 默认是点 2 网格范围可以自己定义范围 右边倒三角点开第三个 3 间隔设置不能超过网格范围 单位跟选择的坐标参考系相关联 mercator坐

  • 贝叶斯优化 Bayesian Optimization

    贝叶斯优化算法 BOA 贝叶斯优化算法BOA 背景介绍 贝叶斯优化流程 形式化 算法流程 核心算法 Prior Function Acquisition Function 参考文献 背景介绍 当前的场景中 会面临很多设计选择问题 比如说在工

  • Uncaught DOMException: Failed to execute 'removeChild' on 'Node': The node ……

    解决办法是加一个等待时间即可解决问题 setTimeout function you code 5

  • 在一台电脑上用不同端口同步以太坊区块链节点

    首先要获取第一个节点的信息 在第一个节点的控制台中输入 gt admin nodeInfo enode 将输出的结果用鼠标操作复制 然后在第二个节点的JS控制台中添加第一个节点为静态节点 输入 gt admin addPeer 例如admi

  • AdminLTE3框架下的BootStrap Modal 模态框

    直接贴出栗子 里面有注解

  • 主机与VMware的Linux虚拟机之间共享交换文件

    搭建环境 主机系统 Windows7 Ultimate VM软件 VMware Workstation 7 1 3 虚拟机系统 Linux Ubuntu 10 10 操作步骤 1 在主机上新建一个共享路径 用于将来和虚拟机之间进行共享文件

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

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

热门标签