存档

‘模式识别’ 分类的存档
7月
16

粒子群优化(Particle Swarm Optimization, PSO)

今天突然开始发闲了,因为老板好像出差了,然后今天下午原计划是去另一个校区搞一些比较重要的事情的,但是我问那边老师下午在么?他在1点50分才回我短信说。。。2点之前他会在的。。。然后下午突然就觉得好空虚,没事干了。。

好吧,所以,今天继续上来补一篇比较简单的算法文吧,应该没什么人会看不懂的吧。。。估计。。。

RT所示,叫做粒子群优化,因为我一直管叫PSO,中文名在我脑海中的印象一直是“粒子XX算法”,我今天才突然意识到,原来有优化这两个字的,然后我就在想,这个叫做“优化”的算法都那么简单了,那么那个叫做“粒子算法”的东西是有多简单啊。。。然后查了一下,好吧,没有“粒子算法”这么一说,或者说,“粒子算法”就是“粒子群优化算法”本身。。。

可能有人听过蚁群算法,觉得粒子群算法会不会跟蚁群算法差不多,其实。。不是差得多不多的问题,完全就是两个东西,生态一点的说法,蚁群算法是模拟蚂蚁找回家的路这种最优路径问题,但是粒子群模拟的是鸟类找最适合栖息地的过程,虽说都是找最优解的问题,但是你敢说鸟类的做法可以放到蚂蚁身上?算了,过阵子我有空就再搞一篇蚁群算法的吧。。。这里姑且先开这个坑。。。 阅读全文...

6月
09

性别识别专题三——实例应用

好吧,专注填坑30年的我又回来了。。。

这次总算真的可以写一下性别识别这个东西了,因为性别识别是个目的,然后为了完成这个目的,需要多种算法手段来实现,所以这就是前面两个专题里面提到的PCA和线性分类器了。

好吧,不多说,直接开始介绍正题。【哦对了,这篇文章主要是写给对模式识别不怎么熟悉的人看的,所以大牛基本可以不要在这里浪费时间了。。反正就是PCA+LDA嘛,你们懂得~】 阅读全文...

5月
22

性别识别专题二——Fisher分类器

好吧,我又来填坑了。。。为啥呢?因为这周我的任务好像差不多了,硬件客观条件所限,要干活最快也要到周六,想象自己给自己挖了这么多坑,补天于心不安啊!!

说到坑这个东西,大家可能有所不知,在这个BLOG里,外表看上去我挖的坑不多(但也不是没有),但是殊不知我的draft里面躺了一大堆草稿,觉得这个可以写来玩玩,那个又想写来分享什么的,而且有些想法发现像个无底洞,所以就被永久雪藏了,比如之前搞的那个统计信号处理专题,出了1之后就在也没动过了。。。

填坑,是个良心活!!

闲话就说这么多吧。。。


线性判别式分析(Linear Discriminant Analysis, LDA),也叫做Fisher线性判别,也就是数模里面常见的Fisher分类器,之前讲到的那个PCA,经常和LDA一起出现,解决了无数的问题,看成模式识别界最平民化的模范COUPLE,平民化一是因为用的多,二是简单,粗暴,易懂。。 阅读全文...

5月
04

性别识别专题一——PCA

翻了一下之前Algorithm的最后一篇,居然是去年12月写的伪逆法,现在五月4号,也就是说我整整有半年没写关于算法的文章了,看了一下各个Category的数目,也属Algorithm最少,为了平衡这一问题,我决定出个长篇专题,里面涉及几个分布的小算法,最近就把这么几篇补上,这样就显得我不是没在搞算法的!!

好吧,就闲话到这,这次说的是PCA算法,PCA的全称是主成分分析法(Principal Component Analysis),它一般是用于模式识别等算法中的预处理模块,做什么用的呢,一般两个方面,一个是对数据进行降噪处理,另一个就是在模式识别中对数据进行降维。什么意思?比如说吧,我这个专题是性别识别,用的是不同性别的人脸图像,图像的像素数就是原始的信息数据,假设一幅图像时640*480,那么相当于一幅图像的特征向量是640*480=307200维,这个维数显然是很可怕的,所以需要降维,怎么将呢?就是找出这些维数里面可以作为区分的那些维,把他们提取出来,剩下的扔掉就可以了。 阅读全文...

12月
02

伪逆法

分类器,是一切模式识别的基础,不管你想识别多么复杂的东西,待识别对象有多少类,你都必须要用上分类器,而不管分类器多么的复杂,归根结底,都是二分类的分类器,而二分类问题,最基础的就是线性分类器。。

虽然线性分类器在实用中不会被用上,但是许多研究的基础都是从线性分类器开始的,以前说的那个Adaboost,一个分类器可以由n多个线性分类器加权级联起来,SVM即便引进了核函数,通过把低维映射到高维空间使之线性可分,但是其研究基础还是线性分类器【过阵子良心发现了就补一篇SVM的吧。。】,神经网络每个神经元是什么?还是线性分类器。

以前被Adaboost和神经网络的那种思维模式误导了,比如说,在Adaboost算法中寻找来级联的弱线性分类器是怎么找的,扫面整个分类器集合找到目前为止最好用的一个弱分类器。神经网络中的神经元的权值是怎么算的?还不是要训练,修正?以至于我决定的,线性二分类问题找到的一个最简单的分类器必须要迭代训练【这里不是说要找最优分类器】。

最近上课老师提到了一个伪逆法,由于我睡过去了,没听清楚,回来上网查了一下,发现这个东西好像还挺好用的~至少思想值得学习!!

伪逆法思想是基于最小二乘的,假如说我们有一堆数据,数据量为N,每个数据向量为m维的,表示如下: 阅读全文...

11月
21

动态时间规整DTW

好吧,最近耳机坏了,日剧计划暂停一下,好好更新一下学术方面的东西吧。。。

今天介绍的是动态时间规整算法(Dynamic Time Warping),我对这个算法有着非常深的感情,嗯,你知道为什么吗?今年上半年还是大四的我,显然是到了要做毕设的时候了,然后指导老师在2月20才交代给我要做什么,然后我就盲目的乱弄了一个多月,因为是算法设计的类型问题,想不出算法你就别指望可以写得出什么东西来,比起那些只有工作量没有太多思维量的毕设题目,我对我的前景堪忧啊,多少个晚上躺在床上,突然突发奇想想到一个东西,然后就下床开电脑验证一下,再然后,就是失望地回去睡觉了。。直到那一天,我遇到了你,DTW,是你拯救了我!!让我产生了一个神奇的灵感,然后花没几天就把毕设给做完了。。。不仅出了不错的结果,还拿了个校级优秀论文。。

我。。。好像又TM扯远了。。。 阅读全文...

9月
10

K-Means++

之前在这里讲AP聚类算法的时候顺带提到了K-Means算法,但是就提到了K-Means算法有两个比较麻烦的弊端,一个是聚类的数目不能自动设置,而要人工设定。另外一个就是对迭代的初始点很敏感,初始点选的不好很容易得出错误的聚类结果来。

然后呢,前阵子无意中看到了K-Means算法的加强版,叫做K-Means++算法【维基请猛戳这里←】,这个算法解决了初始点敏感问题,额。。一定程度上把。。

根据维基上的说法,K-Means++这个算法步骤大概如下:

  1. 在已有的所有点中随机选取一个点,将其加入初始点。
  2. 对于所有的点,计算出他们的D值,D值就是每个点到距离他们最近的初始点的距离的平方。
  3. 对所有点选取下一个点加入初始点的集合,每个点被选取的概率正比于他们的D值。
  4. 如果初始点集合数目没有达到预定的数目,回到2,否则到5。
  5. 执行K-Means算法

这个算法为什么可以很好的解决K-Means算法的初值选择问题呢??我们考虑二维点集的聚类问题,K-Means算法是随便选择初始点,那么就会有一定的概率在一个Cluster内部出现两个或者更多的初始点,还有一种可能就是初始点出现在两个Cluster的正中间这种,反正就是会导致算法不是很有效,一个最常见的失败的聚类经常就是在某些地方把两类聚为一类,然后在另外一些地方把一类分为两类。但是呢,K-Means++算法可以很有效的避免这种状况,比如我在某一Cluster中间已经出现了一个初始点了,那么这个Cluster的点到这个初始点的距离就很小,平方后D值就更小了,所以这里面的点被选为下一个Cluster的概率就会很小。大部分情况下,K-Means++初始化完成之后每个Cluster就会有一个初始化点,这种时候我们就知道里聚类完成也差不多了。所以呢,K-Means++算法也可以很好地降低K-Means算法的迭代次数,换言之,就是算法的时间消耗。 阅读全文...

8月
12

HMM

隐马尔科夫模型(Hidden Markov Model,HMM)是机器学习中一个极其重要又有效的方法,说到隐马尔科夫模型,就要先说一下马尔科夫过程,马尔科夫过程指的是一个东西,它有N种状态,而在时刻T的状态只与前面的k个状态有关,k≥1,称之为k阶马尔科夫模型,我们一般讨论的都是k=1的情况。这里要说明的是,假设k=1,下一个状态只与上一个状态有关,但是并不是上一个状态确定了,下一个状态就确定了,而是下一个状态有多种情况,而具体出现哪一种情况是一个概率事件,这个概率决定于上一个状态是什么。比如说天气问题,假设第二天的天气只跟前一天的天气有关,但是今天下雨,明天的天气可以是90%下雨,10%晴天,而今天晴天,明天可能20%下雨,80%晴天这样。

我们可以知道,一个一阶马尔科夫模型主要由初始状态概率分布π,状态转移矩阵A和状态数目N组成。初始概率分布就是t=0的时候各个状态出现的概率,状态转移矩阵就是每个状态下之间转换的概率矩阵,状态数目就是有几个状态。

那什么是HMM呢?一个很经典的例子,我们有很多个不同的盒子,每个盒子了里面都有很多不同颜色的小球,这些盒子我们称之为状态,每次我们只能选定一个盒子,t=0的时候每个盒子都有一定概率被选中,假设随机选了某一个盒子,然后我们就从盒子里面随机挑出一个小球,然后我们根据盒子的状态概率转移矩阵挑选出下一个盒子,然后在下一个盒子里面再随机挑出一个小球,然后不断重复,隐马尔科夫模型研究的就是这么一个过程。只是啊,在这个过程中我们只能看到每次被挑出来的小球的颜色,而不能知道小球每次具体是从哪个盒子里面挑出来的,盒子(状态)之间的转换过程是隐藏的!! 阅读全文...

7月
29

近邻传播聚类Affinity Propagation

机器学习中一个很重要的方面就是聚类算法。聚类算法说白了就是给你一大堆点的坐标(维度可以是很高的),然后给你一个距离度量的准则(比如欧拉距离,马氏距离什么的),然后你要自动把相近的点放在一个集合里面,归为一类。

继续科普:一个比较传统的聚类算法就是k-Means聚类,算法很简单,哦,说起这件事,我刚刚在整理东西时就发现了一篇讲到k-Means的论文,里面又是一大堆看不懂的符号,我说你们真的有必要那么装逼么?? 阅读全文...

7月
28

Ababoost

毕设时曾经有个模式识别的东西想用Adaboost算法来实现,然后自己就傻不溜秋的用matlab写了一个API,也是为了方便将来用,后来不但没用上这个算法,而且指导老师跟我说,你难道不知道有个软件叫weka么??让后我就SB了。。。

不管怎么样,好歹是学过且用过的。

Adaboost的算法思想就是把许许多多的弱分类器合并起来,变成一个强分类器。

阅读全文...