EM算法的改进

EM算法的改进3.1 算法介绍3.1.1 算法起步EM方法是在十九世纪七十年代被提出的求因子极大似然估算的一种方法，这个方法适应于大多数情况，主要是从不完整数据集中对参数进行一种估算。这种方法可以很好地实施到解决存有缺陷的数据中。我们有一种很形象的描述来讲解这个算法。比如两个人盛一锅不多的米饭，他们都希望两个人盛的一样多，因为他们谁都不想吃亏，这样显然也没必要找一个称来称精确的两份，可行的方法是先给每个人碗里随意盛一些，然后再观察哪个人碗里的米饭多盛出来一些给另一个人，然后再观察，不断的将米饭多的那个人碗里的米饭盛出来给少的那个人，这个过程不断地持续下去，用计算机语言描述就是迭代过程，直到大家看不出两个人碗里的米饭在分量上有什么差别为止。 EM算法的过程如下：如果我们猜想得到A和B两个数据因子，这个时候我们并不知道他们的任何信息，但是他们又是相互关联的，知道A就可以推出B，相反也是一样的。这个时候我们给定一个数字为A的值，这样我们就可以计算出来B的值，就这样不停地循环计算一直到A和B的值相差一个给定数为止。3.1.2算法介绍EM算法在数据挖掘中称得上是一种著名的算法，主要有以下两个过程： E步骤：eatimate the expected values M步骤：re-estimate parameters这个方法的一个重要作用是在于对数据因子的估算上。可是因为算法的运算素的相当慢，也就没有被很多人运用。EM算法和K-means方法相结合，主要是希望找到一个极大似然估计，通过当前的设想估算来找到未知参数的期望。另外，可以通过未知参数的期望值反过来得到极大似然估计值。下面的图很好的介绍了最大似然算法的原理： 图3.1 正态分布生成数据这里的计算步骤如下：Step 1：计算隐藏变量的期望值，并且我们假定；这里代表了参数是通过第j个分布生成的数据： （6）Step 2：我们可以计算其余的一个极大似然估计，如果能够假定由隐藏变量取得的值是第一部计算得到的，那么我们用新的假设来代替以前的假设，重复的进行迭代。那么我们得到极大似然估计是： （7）这个表达式和（6）的样本均值有些类似，它是针对于单个正态分布的。现有的式子计算了加权之后的因子数据的均值，权重是根据前面的计算。3.1.3代码描述这里我写出了主程序算法代码：%演示EM训练算法的实现过程 dim,Num=size(data); max_iter=10;%最大迭代次数 min_improve=1e-4; Ngauss=3;%混合高斯函数个数 Pw=zeros(1,Ngauss);%保存权重 mu= zeros(dim,Ngauss);%保存每个高斯分类的均值 sigma= zeros(dim,dim,Ngauss);%保存协方差矩阵 fprintf(对各个高斯分量进行初始化n); ctcm,cv,cc,cs,mp = qv_ft(data, Ngs); mu=cm;%均值初始化 for j=1:Ngauss gauss_labels=find(map=j);%找出每个类对应的标签 Pw(j)= length(gsls)/length(mp);%分类后是1的样本数的个数 sigma(:,:,j) = diag(std(data(:,gslbs),0,2); %求行向量的方差 end last_loglik = -Inf;%上次的概率 if Ngauss=1,%一个高斯函数不需要用EM进行估计 sa(:,:,1) = sqrtm(cov(data,1); mu(:,1) = mean(data,2); else Sa_j = se(sa(:,:,:); ir= 0; for iter = 1:max_iter %求样本对应函数的输出及每个高斯分量的输出 sigma_old=sigma_i; for i=1:Ngauss P(:,i)= Pw(i) * p_se(data, se(mu(:,i), squeeze(sigma_i(:,:,i);%每一个样本对应每一个高斯分量的输出 end s=sum(P,2);% for j=1:Num P(j,:)=P(j,:)/s(j); end Pw(1:Ngauss) = 1/Num*sum(P);%权重的估计 %均值的估计 for i=1:Ngauss sum1=0; for j=1:Num sum1=sum1+P(j,i).*data(:,j); end mu(:,i)=sum1./sum(P(:,i); end %方差估计按照公式类似 if(sum(sum(sum(abs(s_j- sa_d) ce);/如果函数未达到要求，那么接着这个步骤； /若收敛，则退出循环 用以上程序可进行自动划分分割区域，以下是通过EM算法实现图像分割的实例： 图3.4 自动划分图像图像区域（转） 其中左边的是原图，右边的是当M=2时的分割图像。当然对于不同的M值会产生不同的划分。这些都是EM算法在很多领域中的应用，因此说EM算法具有很好的操作性，进一步研究EM算法并提高它的算法效率是必要的。3.3 改进算法3.3.1 改进动机 传统的EM算法是基于最大似然函数的迭代过程，它的优点就是简单稳定，但是简单相对的就是算法迭代的次数多，速度慢，这就造成了时间复杂度的增大，对于很多问题来说都不具有吸引力，其他的就是方法会得到部分最好解，这对精度要求稍高的问题来说也不太现实。因此很多人选择使用K-均值算法。本文希望引入cs算法解决这些问题，因为Levy飞行具有跳跃性强，不会陷入局部最优的特点，cs搜索模型速度快，可以克服EM模型的几个缺点。因此有很大的可行性。3.3.2 算法改进我们将cs搜索算法应用到EM中，以下是改进算法的步骤：Step 1:最大似然的参数有多种取值，我们给定一个很大范围，参数在此范围内取得，将这一取值范围看成是cs算法中的不同的区域坐标，因此引入cs算法;Step 2： 从m个范围值中选择参数，选择参数的过程依据cs算法的过程：第t次迭代的第i个参数，通过Levy飞行，产生下一次迭代的初始参数，有 （18）其中是点对点乘法，就是一个步长大小服从Levy分布的随机游走，可以表示为 （19）此处，具体的步长大小是利用Mantegna法则来实现的。Step 3: 设置一个限度迭代次数，用每次选定的参数进行重复期望的计算，到达指定迭代次数算法如果还未收敛，利用cs搜索算法进行下一次参数搜索；Step 4:循环上面过程，利用Step 1的过程继续产生不同的参数，接着进行Step 2，不断的迭代计算参数，当我们最后计算的似然函数参数差距小于我们给定的值，停止迭代，进入Step 5；Step 5：在计算完成后，得到了我们需要的解。3.3.3 改进算法程序importJAVA.clusterers.EM;importJAVA.core;importJAVA.core.converters.*;importJAVA.clusterers.*;importjava.io.*;publicclassEMpubliclEM()publicvoidMain()throwsExceptionEMm_cluster=newEM();FileinputFile=newFile(MyJAVA);ArffLoaderarf=newArffLoader();arf.setFile(inputFile);InstancesinstancesTrain=arf.getDataSet();inle=newFile(JAVA);arf.setFile(inputFile);Inesinst=arf.get();m_cluster.ber(insTn);System.out.println(Thenumberofcluster:+m_cl.nOCl();intnum=m_cluster.numberOfClusters();System.out.println();System.out.println(m_cluster.toString();System.out.println();doublepredict=m_cluster.clusterPriors();for(inti=0;inum;i+)System.out.println(+i+种分类的先验概率为：+pti);publicstaticvoidmain(Stringargs)throwsExceptionlEMa=newEM();a.Main(); 3.3.4 改进算法的优点（1） 由于cs算法有不会陷入局部最优的特点，因此算法参数可以不断地跳出局部最优限制，EM方法这样就不易得到部分最好的解；（2） 改进后的算法提高了参数计算的准确性，改善了