EM算法与高斯混合分布

作为机器学习的十大算法之一，EM算法可谓是风头出尽，尤其是EM算法在聚类等方面的优越表现，让EM算法备受瞩目，这个星期对EM算法进行了一番了解，说实话EM算法光从教科书上的那些公式说导我觉得很难理解，在七月算法的一节关于EM算法的公开课上慢慢的对EM算法有了算是入门的了解，今天就来说说EM算法与其典型的应用：高斯混合分布

 

首先简略介绍一个高斯混合分布：

 

在一个随机分布里面，可能存在着很多的分布类型，我们假设每个类的分布都符合高斯混合模型，那么一个随机值集合里面就会有多个高斯分布，举个简单的例子，在一群男女生中，我们统计每个人的身高数据，因为男女生的身高存在差异，我们显然不能讲两者的身高都做一样的处理，那么对于这个身高数据而言，男生的身高符合一个高斯分布，女生的身高符合一个高斯分布，这就是一个数据集里面的两个高斯分布，高斯分布的数学描述是：

                       

其中phi表示一个高斯分布，alpha表示该高斯分布占的比例

 

回到男女身高问题本身，现在的问题是如何求解男女身高的均值和方差(标准差)

 

当然我们可以使用极大似然估计来求解，但这只是理论上可行，实际并不可行

因此我们需要使用一种新的办法来求解，当然，这里自然指的是：EM算法

 

EM算法该如何理解，这是一个问题，七月算法的公开课讲的非常给力，这里给出链接地址 http://www.julyedu.com/video/play/?id=79&course=18

 

这里我不准备对EM进行理论推导，对于上述的男女身高问题这里仅给出一个结论，然后我们使用python将这个问题解决，当然，具体的推导过程见附件的pdf文件

 

每次迭代过程的公式是：

 

最后我们使用python代码来实现以下男女身高问题的求解过程，我给出了一个男生占50人女生占70人的数据集，其中男生均值为175，标准差为2，女生均值是160，方标准差为2，并加以0~1的随机噪声，然后通过代码求解EM算法运算的准确性

 

# -*- coding: cp936 -*-
"""
EM算法与混合高斯分布
author:luchi
date:2015/12/6

description：假如有一堆人，包括男的和女的，现在不知道
其比例只能统计身高信息，现在要求男的和女的的身高的均值
方差已经在人群中占得比例，使用EM算法的混合高斯模型可以
解决
"""
from numpy import *
from random import *
import math

#计算高斯值
def calcGauss(x,mu,sigma):
    return exp(-1*(x-mu)**2/2/(sigma**2))/sigma/sqrt(2*math.pi)
    
#计算均值
def averageHeight(height,gamma,n):
    sumHeight=0.0
    for i in range(len(height)):
        sumHeight+=height[i]*gamma[i]
    return float(sumHeight)/n
#计算标准差
def varianceHeight(height,gamma,mu,n):
    sumVariance=0.0
    for i in range(len(height)):
        sumVariance+=gamma[i]*(height[i]-mu)**2
    return sqrt(float(sumVariance)/n)

#终止条件gp,bp,gmu,gsigma,bmu,bsigma
def isEqual(cur,now):
    cur=mat(cur).T
    now=mat(now).T
    temp=cur-now
    if temp.T*temp<0.001:
        return True
    return False
    
#计算的主要函数，height为人群的身高分布
def calcEM(height):
    N=len(height)
    gp=0.5  #女孩的初始比例
    bp=0.5  #男孩的初始比例
    gmu,gsigma=min(height),1  #初始值的女孩身高均值和标准差
    bmu,bsigma=max(height),1  #初始值的男孩身高均值和标准差
    
    ggamma=range(N)  #计算女孩在迭代过程中的gamma值
    bgamma=range(N)  #计算女孩在迭代过程中的gamma值
    
    cur=[gp,bp,gmu,gsigma,bmu,bsigma] #初始的方差矩阵
    now=[]
    
    times=0  #迭代次数
    while times<100:
        i=0
        for x in height:
           ggamma[i]= gp*calcGauss(x,gmu,gsigma)
           bgamma[i]= bp*calcGauss(x,bmu,bsigma)
           s= ggamma[i]+bgamma[i]
           ggamma[i]/=s
           bgamma[i]/=s
           i+=1
        
        gn=sum(ggamma)  #计算比例
        gp=float(gn)/float(N)
        bn=sum(bgamma)
        bp=float(bn)/float(N)
        gmu=averageHeight(height,ggamma,gn)
        gsigma=varianceHeight(height,ggamma,gmu,gn)
        bmu=averageHeight(height,bgamma,bn)
        bsigma=varianceHeight(height,bgamma,bmu,bn)

        now=[gp,bp,gmu,gsigma,bmu,bsigma]
        if isEqual(cur,now):
            break
        cur=now

        print "迭代次数是：\t",times
        print "女孩的身高平均值和标准差是:\t",gmu,gsigma
        print "男孩的身高平均值和标准差是:\t",bmu,bsigma
        print "男孩女孩的比例是：\t",bn,gn,bn+gn
        times+=1
    return now

def test():
    #产生随机测试集
    height=[]
    #产生男生的身高数据
    for i in range(50):
        height.append(gauss(175,2)+5*random()*pow(-1,i))
    for i in range(70):
        height.append(gauss(160,2)+5*random()*pow(-1,i))
    
    calcEM(height)

if __name__=='__main__':
    test()
    
        




        

  计算结果如下：

 

 

迭代次数是：	2
女孩的身高平均值和标准差是:	160.368555386 3.56047601722
男孩的身高平均值和标准差是:	174.782518706 3.52040845881
男孩女孩的比例是：	52.5771905209 67.4228094791 120.0

 

 需要说明的是，EM算法对初值很敏感，而且EM算法是局部最优解，而不是全局最优解，但是在选定的初值偏差不是太大的情况下，EM算法还是有很好的准确度