em算法代码

① 急求如何用MATLab实现EM算法

最大期望算法（Expectation Maximization Algorithm，又译期望最大化算法），是一种迭代算法，用于含有隐变量（hidden variable）的概率参数模型的最大似然估计或极大后验概率估计。
实现代码如下：
02 Jul 2015 hui cheng
06 May 2015 Mei Dong
very good job！

12 Nov 2014 Jobaer
please, sir , send me a source code on image segmentation. I want to segement weeds from soil.My email address is [email protected] .

18 Jan 2014 HuangJunFeng HuangJunFeng
16 Dec 2013 widdy
19 Feb 2013 Tong Chu
01 Jan 2013 manas nag
sir
after executing this it is declaring that k is undefined

04 Dec 2012 Jason Rebello
Some people want to know how to view the segmented image. For example suppose you have two classes ie k=2; us the following code to view it
[row col] = size(ima);
final_img = zeros(row,col);
for i=1:row
for j=1:col
if mask(i,j)==1
final_img(i,j)=1;
else
final_img(i,j)=255;
end
end
end
imshow(final_img/255);
This is a naive way of viewing it .. you may have to change somethings if k>2. Anywayz hope it helps. The mask basically stores the segmented image.

16 Nov 2011 surya
great job.i am using the same algorithm in my project for x-ray images.can u please tell how to view the segmented image

Comment only

18 Feb 2010 prashanth
Sir, I am starting my project on the same subject. i was unable to find the algorithm psuedocode for em algorithm. kindly send me one at [email protected]. Also can u just tell me the explanation for the source code..

Comment only

21 Dec 2009 maria
Hi, could you please explain how I can use "mask" to see result of segmentation??

Comment only

17 Mar 2009 Patrick
Greetings Prof., Very nice .. could you please let me know what exactly does the mask variable store ? As what i see it classifies each pixel that falls within each class . Am i correct in that assumption?
Thanks

24 May 2008 darko brajicic
great job!

27 Apr 2008 Bilo Bilo
Thanks

15 Aug 2007 smiled fisher
06 Nov 2006 Karthik Raja T
HI, Greetings,can it for my color image segmentation ?

04 Sep 2006 Mikel Rodriguez
12 Jul 2006 carlos mas
03 May 2006 Mohamed Sami
look when u make a code u must show us the output to see it then u read ur code .. try to explain that with output we can see bye

② pattern recognition and machine learning这本书怎么看

作者：Richardmore
这本书可以说是机器学习的经典学习之作。以前在上机器学习这么课的时候，很多细节还没联系到，结果在读论文中就显得捉襟见肘。本文打算理清楚这本书的脉络，也顺便为学习机器学习的人打下一个学习路线图。

1. 排除两块内容

现排除第五章的内容神经网络，之所以把神经网络先单列出来，原因一是一个比较独立的研究脉络，二是因为这部分因为深度学习的原因太热了，所以我认为在学习机器学习中把神经网络单列出来学习，在交大的研究生课程安排中，神经网络是机器学习的后续课程。
对于第6，7章，也不在下面的学习路线中，因为这部分是关于核技巧方面的，主要是就是高斯过程回归，高斯过程分类以及SVM等内容。
2. 一个概率图框架为中心视角

排除了上面几章的内容，PRML书中可以用下面的学习路线图覆盖，通过这个图可以理清楚了各个内容的不同角色。
<img src="https://pic3.mg.com/_b.png" data-rawwidth="1888" data-rawheight="412" class="origin_image zh-lightbox-thumb" width="1888" data-original="https://pic3.mg.com/_r.png">

说明：
（1）一般模型中都会有隐变量因此，，因此对于P（X）的采用MLE学习的另一个技巧,便是第九章 EM算法。条件是在M步时，Q要可以被analytically computed。
（2）至于为什么近似，Exact Inference is hard we resort to approximation
3. 隐变量技巧

下面我们看看另外一个视角：隐变量技巧。隐变量不仅可以使得模型的表达能力丰富起来，而且通常对于隐变量往往富有一定的实际意义。

<img src="https://pic1.mg.com/_b.png" data-rawwidth="1764" data-rawheight="422" class="origin_image zh-lightbox-thumb" width="1764" data-original="https://pic1.mg.com/_r.png">

说明：
（1）这里所谓的结合模型中，在PRML中最后一章仅仅提到了以加法的方式进行模型集合，也就是mixture of experts，在论文Hinton G E. Training procts of experts by minimizing contrastive divergence[J]. Neural computation, 2002, 14(8): 1771-1800. 提出了proct of experts 模型，也就是以乘法的方式进行结合，RBM就是一种特殊的proct of experts 模型，而高斯混合模型便是加法模型的代表。
（2）隐变量的技巧是机器学习中一种重要的技巧，隐变量的加入不仅仅增加了模型的表达能力，而且，隐变量还可以被赋予某种特殊的意义，比如RBM模型中隐变量h被当成显变量v的特征抽象。这当然归根结底是因为隐变量模型确实是现实世界真实存在的情况，unobserved but important variables do exist! 当然隐变量的引入也为模型的推断带来了新的挑战，有很多比较好的隐变量模型往往找不到很高效的方法，而被限制着。
4. 例子说明

下面分别从上面两个视角来分析RBM模型，贝叶斯线性回归和序列模型。
4.1 RBM模型
RBM模型是一个无向2层对称的图模型，从隐变量的视角来看，它是一个以乘法方式结合的distributed models。当然隐变量的引入增加了模型的复杂性和表达能力，但是也为学习，推断带来了问题。对于RBM的参数学习，因为是无向图，所以采用MLE最大化P（X），但是由于此时P（X，Z）难以评估，所以
<img src="https://pic2.mg.com/v2-_b.png" data-rawwidth="834" data-rawheight="94" class="origin_image zh-lightbox-thumb" width="834" data-original="https://pic2.mg.com/v2-_r.png">
很难计算，没有在RBM的学习中不能像高斯混合模型那样可以采取EM算法。因此只能采取最为标准的做法，求取P（X）的梯度，结果梯度公式如下：
<img src="https://pic2.mg.com/v2-_b.png" data-rawwidth="800" data-rawheight="90" class="origin_image zh-lightbox-thumb" width="800" data-original="https://pic2.mg.com/v2-_r.png">

然而对于计算后面的model部分的积分需要知道模型的概率分布，评估模型的概率分布需要计算一个标准化的分母，难以计算。因此就需要依赖近似，由于p（v｜h），p（h｜v）都是可以分析公式表达，因此采用Gibbs sampler来数值逼近积分。当然后来Hinton G E. Training procts of experts by minimizing contrastive divergence[J].发现对于这一部分，Gibbs sampler 不需要多部的迭代，一次迭代就可以了，从而使的训练RBM的时间代价大大降低了，后来（A fast learning algorithm for deep belief nets，2006）提出了贪婪式的训练多层DBN（stacked RBM），每层都是训练RBM，从而使的深度学习焕发新的活力（Recing the dimensionality of data with neural networks，2006）。

4.2 贝叶斯线性回归Bayesian Linear Regression BLR

这个模型是最为基础的，这个模型在PRML中，利用直接推断，变分法推断，MCMC采样都是可以做的；因此便于比较不同算法得到的结果。之前，本来打算在这里以LDA主题模型来举例，虽然LDA的EM算法， 变分法，以及Gibbs sampling 都是可以做的，但是模型太复杂，所以果断放弃了，以BLR模型作为例子说明。
BLR是一个有向图模型，是一个典型的贝叶斯网络（虽然简单一点）。如果以一个贝叶斯的视角来看，其中的隐变量便是线性参数w，以及各种超参数α,β.....，在贝叶斯的处理视角之下，这些都会赋予一个先验分布。当然，有些模型书中也提到，有不同层次上的贝叶斯网络。有的是仅仅对参数w赋予一个先验分布，而对于其他的参数（hyperparameter）仅仅是作为模型参数，就是假设是一个渡固定的数值，然后再通过learn evidence function，其实说白了就是MLE，来寻找最佳的超参数α,β....。相比于把线性参数w，以及各种超参数α,β.....全部作为放入到贝叶斯网络中，这样的做法显然简化了模型，降低了贝叶斯网络的复杂性。这个技巧也在多处的论文中出现。
从隐变量的角度来看，由于BLR模型相对简单，其中并没有随机隐变量，仅仅是一些参数w，以及各种超参数α,β..的环境隐变量。
4.3 序列模型：隐马尔可夫链HMM与条件随机CRF

隐马尔可夫链HMM这个模型是一个有向图模型，典型的贝叶斯网络，只不过这个网络是一个线性链（linear chains），因此可以进行分析上推断，要知道对于一般网络，并不存在通用的实用的inference算法。因为HMM是一个有向图模型。但是（1）在PRML书中，以及李航《统计学习》中并没有把其当作一个贝叶斯网络来进行处理，对所有的参数比如发射概率，转移矩阵概率都是模型的参数，而不是通过赋予一个先验分布，从而纳入到贝叶斯网络框架之中。因此对于模型而言，关键的便是通过MLE最大化P（X）来学习模型的参数，因为这里的有隐变量，因此在PRML，以及《统计学习》中都是通过EM算法做的。（2）其实，HMM是一个典型的线性链式的贝叶斯网络，因此对于通过对其参数赋予先验分布，进而从贝叶斯的角度，来对模型进行推断是一个非常自然的想法。我在论文Sharon Goldwater， Thomas L Griffiths 论文 A Fully Bayesian Approach to Unsupervised Part-of-Speech Tagging，中作者采用了Bayesian HMM 重新做了POS任务。作者在文中还详细罗列了Bayesian HMM 相比普通的HMM的优点：（a）可以使用先验知识，例如在POS中语言的认知可以加入到先验分布之中，而且（b）贝叶斯的推断，是通过一个后验分布推断参数，相比MLE点估计，会更加准确。对于贝叶斯的推断，作者在文中使用了Gibbs sample抽样实现了数值采样推断模型。最后作者比较了Gibbs sample＋Bayesian HMM和普通的HMM ＋EM，在POS任务效果更加好。另外，对于本论文的作者Thomas L Griffiths，第一次接触这个学者，是在读Gibbs sample in LDA这篇文章，作者推导了LDA的各种的条件分布，然后基于Gibbs sample 进行采样，记得Github上有Java版的实现代码，其推导十分严谨，并且有代码辅助，是学习LDA的一个捷径。在近似推断方面可以看出Thomas L Griffiths是一个坚定的数值采样学派，而LDA的开山之作《Latent Dirichlet Allocation 》的作者David M. Blei，看了作者部分文章以后，发现这个人是在近似推断方面是一个变分法的坚定学派，在《Latent Dirichlet Allocation 》之中，便是通过变分法进行推断了，David M. Blei还写了一个关于变分法的入门讲义pdf，网上可以搜到。所以回看我们概率图视角，做机器学习推断是不可避免的，有的是变分法近似，有的是数值采样近似，也有的是EM算法试一试。至于选择哪一种，就看你的问题哪一个比较简单了。但是好像有的人对这些方面各有偏爱。
再说一下条件随机场CRF，相比与HMM，这也是一个序列模型，在很多的NLP任务中，CRF都是state of art 的算法，毕竟人家可以方便的特征工程嘛。但是这种日子被深度学习取代了，在NLP方面，RNN（递归神经网络）要比CRF表现更好，见我之前博文基于RNN做语义理解和词向量。先不说这么远，CRF的模型架构上是一个典型的无向的链式概率图模型，因此，（回看我们概率图的视角），CRF的关键问题便是如何进行学习了P（X），好在求其该模型直接求其梯度并没有太大的困难，具体可以参见李航的《统计学习》。
5 结束语

这篇文章，从概率图，隐变量两个视角对PRML中各个章节进行了串联，并以RBM，BLR，序列模型（HMM&CRF）具体说明这种串联。

③ 会用C语言画图的(圆)Bresenham算法的高手帮忙看下！

//包含头文件这个不用我说了吧
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<graphics.h>
//交换a,b的值函数
void Swap(int *a,int *b);
//Bresenhen画园函数,圆心坐标(centerx,centery)半径radius线条颜色color
void BresenhemCircle(int centerx, int centery, int radius, int color, int type);
void initgr(void) /* BGI初始化 */
{
int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */
registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
initgraph(&gd, &gm, "");//初始化图形,必须写的
setbkcolor(WHITE);//设置背景颜色
}

int main(void)
{
int centerx,centery,radius,color,type;//变量定义总该知道的吧
printf("centerx,centery\n");//输出提示信息，这个总该知道的吧
scanf("%d",¢erx);//输入中心坐标横坐标
scanf("%d",¢ery);//
printf("radius\n");
scanf("%d",&radius);
printf("color,type\n");
scanf("%d",&color);
scanf("%d",&type);
initgr(); /*BGI初始化 */
BresenhemCircle(centerx,centery,radius,color,type);//重点理解这个函数
/*setcolor(RED);
circle(centerx, centery,radius);*/
/*Swap(&xs,&xe);
printf("%d,%d",xs,xe); */
getch();
closegraph();
}

void BresenhemCircle(int centerx, int centery, int radius, int color, int type)
{
int x =type= 0;//这些赋值语句应该能够看懂的吧
int y = radius;
int delta = 2*(1-radius);
int direction;
while (y >= 0) {//循环，如果y>=0就继续执行{}里面的语句
if (!type) { //!type表示如果type=0就执行{}里面的语句
putpixel(centerx+x, centery+y, color);
//前面两个参数是坐标，后面一个是颜色值，在(centerx+x, centery+y)画一个点
putpixel(centerx-x, centery+y, color);
putpixel(centerx-x, centery-y, color);
putpixel(centerx+x, centery-y, color);
}
else {//如果type=1就执行下面的
line(centerx+x, centery+y, centerx+x, centery-y);
line(centerx-x, centery+y, centerx-x, centery-y);
}
if (delta < 0) {//这个类似上面的，只不过这个嵌套了一层if-else if-else
if ((2*(delta+y)-1) < 0) {
direction = 1;
}
else {
direction = 2;
}
}
else if(delta > 0) {
if ((2*(delta-x)-1) <= 0) {
direction = 2;
}
else {
direction = 3;
}
}
else {
direction=2;
}

switch(direction) {//选择如果direction=1执行case 1:到case 2:直接的语句，如果没有break那么case 2:下面的语句也会被执行
case 1:
x++;
delta += (2*x+1);
break;
case 2:
x++;
y--;
delta += 2*(x-y+1);
break;
case 3:
y--;
delta += (-2*y+1);
break;
}

}
}

④ 如何正确选择聚类算法

作者 | Josh Thompson

来源 | 数据派THU

Choosing the Right Clustering Algorithm for your Dataset - KDnuggets

聚类算法十分容易上手，但是选择恰当的聚类算法并不是一件容易的事。

数据聚类是搭建一个正确数据模型的重要步骤。数据分析应当根据数据的共同点整理信息。然而主要问题是，什么通用性参数可以给出最佳结果，以及什么才能称为“最佳”。

本文适用于菜鸟数据科学家或想提升聚类算法能力的专家。下文包括最广泛使用的聚类算法及其概况。根据每种方法的特殊性，本文针对其应用提出了建议。

四种基本算法以及如何选择

聚类模型可以分为四种常见的算法类别。尽管零零散散的聚类算法不少于100种，但是其中大部分的流行程度以及应用领域相对有限。

基于整个数据集对象间距离计算的聚类方法，称为基于连通性的聚类（connectivity-based）或层次聚类。根据算法的“方向”，它可以组合或反过来分解信息——聚集和分解的名称正是源于这种方向的区别。最流行和合理的类型是聚集型，你可以从输入所有数据开始，然后将这些数据点组合成越来越大的簇，直到达到极限。

层次聚类的一个典型案例是植物的分类。数据集的“树”从具体物种开始，以一些植物王国结束，每个植物王国都由更小的簇组成（门、类、阶等）。

层次聚类算法将返回树状图数据，该树状图展示了信息的结构，而不是集群上的具体分类。这样的特点既有好处，也有一些问题：算法会变得很复杂，且不适用于几乎没有层次的数据集。这种算法的性能也较差：由于存在大量的迭代，因此整个处理过程浪费了很多不必要的时间。最重要的是，这种分层算法并不能得到精确的结构。

同时，从预设的类别一直分解到所有的数据点，类别的个数不会对最终结果产生实质性影响，也不会影响预设的距离度量，该距离度量粗略测量和近似估计得到的。

根据我的经验，由于简单易操作，基于质心的聚类（Centroid-based）是最常出现的模型。 该模型旨在将数据集的每个对象划分为特定的类别。 簇数（k）是随机选择的，这可能是该方法的最大问题。 由于与k最近邻居（kNN）相似，该k均值算法在机器学习中特别受欢迎。

计算过程包括多个步骤。首先，输入数据集的目标类别数。聚类的中心应当尽可能分散，这有助于提高结果的准确性。

其次，该算法找到数据集的每个对象与每个聚类中心之间的距离。最小坐标距离（若使用图形表示）确定了将对象移动到哪个群集。

之后，将根据类别中所有点的坐标平均值重新计算聚类的中心。重复算法的上一步，但是计算中要使用簇的新中心点。除非达到某些条件，否则此类迭代将继续。例如，当簇的中心距上次迭代没有移动或移动不明显时，聚类将结束。

尽管数学和代码都很简单，但k均值仍有一些缺点，因此我们无法在所有情景中使用它。缺点包括：

相比之下，期望最大化算法可以避免那些复杂情况，同时提供更高的准确性。简而言之，它计算每个数据集点与我们指定的所有聚类的关联概率。用于该聚类模型的主要工具是高斯混合模型（GMM）–假设数据集的点服从高斯分布。

k-means算法可以算是EM原理的简化版本。它们都需要手动输入簇数，这是此类方法要面对的主要问题。除此之外，计算原理（对于GMM或k均值）很简单：簇的近似范围是在每次新迭代中逐渐更新的。

与基于质心的模型不同，EM算法允许对两个或多个聚类的点进行分类-它仅展示每个事件的可能性，你可以使用该事件进行进一步的分析。更重要的是，每个聚类的边界组成了不同度量的椭球体。这与k均值聚类不同，k均值聚类方法用圆形表示。但是，该算法对于不服从高斯分布的数据集根本不起作用。这也是该方法的主要缺点：它更适用于理论问题，而不是实际的测量或观察。

最后，基于数据密度的聚类成为数据科学家心中的最爱。

这个名字已经包括了模型的要点——将数据集划分为聚类，计数器会输入ε参数，即“邻居”距离。因此，如果目标点位于半径为ε的圆（球）内，则它属于该集群。

具有噪声的基于密度的聚类方法（DBSCAN）将逐步检查每个对象，将其状态更改为“已查看”，将其划分到具体的类别或噪声中，直到最终处理整个数据集。用DBSCAN确定的簇可以具有任意形状，因此非常精确。此外，该算法无需人为地设定簇数 —— 算法可以自动决定。

尽管如此，DBSCAN也有一些缺点。如果数据集由可变密度簇组成，则该方法的结果较差；如果对象的位置太近，并且无法轻易估算出ε参数，那么这也不是一个很好的选择。

总而言之，我们并不能说选择了错误的算法，只能说其中有些算法会更适合特定的数据集结构。为了采用最佳的（看起来更恰当的）算法，你需要全面了解它们的优缺点。

例如，如果某些算法不符合数据集规范，则可以从一开始就将其排除在外。为避免繁琐的工作，你可以花一些时间来记住这些信息，而无需反复试验并从自己的错误中学习。

我们希望本文能帮助你在初始阶段选择最好的算法。继续这了不起的工作吧！

⑤ matlab实现EM算法

1. EM算法程序：
http://www.mathworks.com/matlabcentral/fileexchange/3713-em-algorithm-for-clustering-emfc-m

2. EM image segmentation：
http://www.mathworks.com/matlabcentral/fileexchange/10956-em-image-segmentation

3. 贝叶斯图像分割程序：(Bayseian image segmentation)
没有找到合适的程序代码 :-(