存档

‘Algorithm’ 分类的存档
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的时候每个盒子都有一定概率被选中,假设随机选了某一个盒子,然后我们就从盒子里面随机挑出一个小球,然后我们根据盒子的状态概率转移矩阵挑选出下一个盒子,然后在下一个盒子里面再随机挑出一个小球,然后不断重复,隐马尔科夫模型研究的就是这么一个过程。只是啊,在这个过程中我们只能看到每次被挑出来的小球的颜色,而不能知道小球每次具体是从哪个盒子里面挑出来的,盒子(状态)之间的转换过程是隐藏的!! 阅读全文…

8月
02

傅里叶变化与频率那些事儿

学数字信号处理的时候都会接触到的三个东西就是数字频率,模拟频率,采样频率,这三个东西其实挺好懂得,但是一旦涉及到编程那些东西好像很容易出错,而且一般都是比较难查的。然后一旦到了数字滤波器那些东西,又来什么归一化频率的,就更乱了,加上数字福利叶变换后频率就变成-π到π了,然后又有人搞不懂了。。

趁我现在脑子清新,概念还比较清晰,这里整理一下,也方便将来我又分不清东南西北的时候可以回来复习复习,如果有找不着北的孩子看到这个,希望对你有帮助。

首先我们解释模拟频率,数字频率和采样频率。

假设我们有一小段正弦信号sin(2 π f t),不要考虑任何数字化的东西,这个f就叫做模拟频率。假设f=100,那么我们高中知识知道这个正弦信号的周期是1/f,也就是0.01,也就是说0.01的时间t里面正弦信号变化的一周,我们就知道从0到1里面变化了100次,也就是f次,所以我们才把f叫做频率的。 阅读全文…

7月
30

匹配滤波器

学数字通信原理的时候就会学到,如果一个信号,传输过程中加了白噪声,然后我们接收到这个信号后,需要对这个信号进行采样,我们想要的结果是想要在时刻Ts对这个加了噪的信号进行采样,使得在Ts时刻采样点的信噪比最大;通信原理课本告诉我们如果要达到这个目的,那么就要在采样前先把信号通过一个匹配滤波器,然后再在Ts时刻采样,匹配滤波器可以让你的信噪比达到最大。

匹配滤波器通过使滤波器和信号取得某种一致性,使得在Ts时刻信号出现某一尖峰,这样来实现抑制噪声。额。。匹配滤波器的推导这里就不说了,因为什么地方都可以查得到,反正就是假设信号是x(t),那么匹配滤波器的系统响应函数就是: 阅读全文…

7月
29

近邻传播聚类Affinity Propagation

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

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

7月
28

Ababoost

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

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

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

阅读全文…

7月
28

Camshift跟踪算法

基于图像处理的人机交互算法中,Camshift是一个很入门很基本的目标跟踪算法,不过当年学得很窝火,因为一开始不知道在网络上找,所以就研究论文里面这个算法的详情,结果看了好久也没看懂,因为那些狗屎论文个个都在装逼,明明一个很简单的算法,非要用数学封装起来,你数学就算了,非要把一个过程用连续的积分表示出来,好吧,我原谅你积分,你为了得到一个更为一般的表达式,给我他喵的抽象出一个变换核出来!!然后引进一大堆▽,∂什么的,你知道对于一个刚学习图像处理的孩子来说,这要多伤人心!! 阅读全文…

6月
29

通用图搜索算法A*基类

这个是很早很早之前写的了。看人工智能的书的时候看到了启发式图搜索算法,完全不难理解,书上使用它来实现排序拼图的路径搜索,看完挺想自己实现一个,但是又觉得没啥难度,然后就想啊,能不能写个通用的抽象基类,要用这个方法解决什么问题时,就继承这个Class,然后写把与问题相关的几个函数写一下,就可以直接用了,这样的话以后想用暴力搜索解决一些临时问题,就可以随便写一写就可以了。

阅读全文…

分类: 模式识别 标签: , ,