GMM 的EM 实现

算法逻辑在这里：

http://www.cnblogs.com/Azhu/p/4131733.html

贴之前先说下，本来呢是打算自己写一个的，在matlab 上，不过，实在是写不出来那么高效和健壮的，网上有很多实现的代码，例如上面参考里面的，那个代码明显有问题阿，然后因为那里面的代码与逻辑分析是一致的，那在其基础上修改看看，结果发现代码健壮性实在太差了，我的数据集是 70-by-2000 的矩阵，70个样本2000维，结果协方差的逆根本算不出来，全部是inf，那去前50维，还是算不出来，这个虽然逻辑是对的，但是这软件的局限阿。

那只能用其他方法了，有一个写的很好的，下面会贴出来，不过都是矩阵运算，看是能看懂的，不过数学计算实在写不出来，按这么来的也只是跟着其敲了一遍，敲之前还看了半天才懂其的数学计算，matlab 的内置函数也不算熟，这里就顺便写下来好了。

主函数：

12-26 行是初始化类标号和其他参数，12行调用了初始标号的参数，实际上初始化的是R。
R 是一个n-by-k 矩阵，每项表示一个i-th 样本在 j-th GM 中的概率值，就是p(x|k)。
因为是初始化，所以14行获取了当前类标号label。
27 - 40 是迭代部分，通过判断是否收敛和迭代次数循环
29 是m-step，这跟我写的算法逻辑有点不同，不过不影响。
29 m-step是假设知道了标号，训练GMM 模型参数，获得的是model。
30 是 e-step，假设训练好了GMM ，计算样本的分配情况，其中loglikehood 是在e-step 中计算了。
剩下的是收敛判断

 function [label, model, llh] = emgm(X, init)

 % Perform EM algorithm for fitting the Gaussian mixture model.

 %   X: d x n data matrix

 %   init: k ( x ) or label ( x n, <=label(i)<=k) or center (d x k)

 % Written by Michael Chen ([email protected]).

 %% initialization

 % fprintf('EM for Gaussian mixture: running ... \n');

 % load('final_initlize');

 % X = dataset().x';

 % init = dataset().y';

 % R n-by-k 矩阵，表示i-th 样本属于j-th 个类的概率，初始化时候为1、，迭代后变是权重化了。

 R = initialization(X,init);

 % label 表示n 个样本的类标号。

 [~,label(,:)] = max(R,[],);

 % 这句是为了处理类标号不连续的情况

 R = R(:,unique(label));

 %pect = zeros(size(label));

 % tol 是阀值控制

 tol = 1e-;

 maxiter = ;

 % loglikehood

 llh = -inf(,maxiter);

 converged = false;

 % 当前迭代的标号

 t = ;

 while ~converged && t < maxiter

     t = t+;

     model = maximization(X,R);

     [R, llh(t)] = expectation(X,model);

     [~,label(:)] = max(R,[],);

     u = unique(label);   % non-empty components

     if size(R,) ~= size(u,)

         R = R(:,u);   % remove empty components

     else

         converged = llh(t)-llh(t-) < tol*abs(llh(t));

     end

 end

 llh = llh(:t);

 % if converged

 %     fprintf('Converged in %d steps.\n',t-);

 %     llh  = t-;

 % else

 %     fprintf('Not converged in %d steps.\n',maxiter);

 %     llh = maxiter;

 % end

初始化函数：

这个函数很简单，没什么好解释的。

 %% init

 function R = initialization(X, init)

 % 初始化一共用4中方式，一种是给定GMM 模型的参数初始值，一种是给定k 的个数，一种是给各sample 的标号，一种是给出类的中心点

 [d,n] = size(X);

 if isstruct(init)  % initialize with a model

     R  = expectation(X,init);

 elseif length(init) ==   % random initialization

     k = init;

     idx = randsample(n,k);

     m = X(:,idx);

     [~,label] = max(bsxfun(@minus,m'*X,dot(m,m,1)'/),[],);

     [u,~,label] = unique(label);

     while k ~= length(u)

         idx = randsample(n,k);

         m = X(:,idx);

         [~,label] = max(bsxfun(@minus,m'*X,dot(m,m,1)'/),[],);

         [u,~,label] = unique(label);

     end

     R = full(sparse(:n,label,,n,k,n));

 elseif size(init,) ==  && size(init,) == n  % initialize with labels

     label = init;

     k = max(label);

     R = full(sparse(:n,label,,n,k,n));

 elseif size(init,) == d  %initialize with only centers

     k = size(init,);

     m = init;

     [~,label] = max(bsxfun(@minus,m'*X,dot(m,m,1)'/),[],);

     R = full(sparse(:n,label,,n,k,n));

 else

     error('ERROR: init is not valid.');

 end

m-step函数：

输入参数 R解释参考上面。
7 计算各类的sample 个数和，一个1-by-k matrix。
8 7中的值除以样本总数就是 GM 的权重，同样是1-by-k matrix。
9 计算GM 样本均值，mu 是个d-by-k matrix，每列表示 k-th GM 的样本均值。
19 计算sqrtR 是为了 15-17行的计算中结果刚好是R。
15-17 sigma
18行应该是为了避免sigma 不能逆。

 %% m-step

 function model = maximization(X, R)

 [d,n] = size(X);

 % k 为类个数

 k = size(R,);

 % 各类的sample个数

 nk = sum(R,);

 w = nk/n;

 mu = bsxfun(@times, X*R, ./nk);

 Sigma = zeros(d,d,k);

 % 这个值是为了下面计算时候得到R，

 sqrtR = sqrt(R);

 for i = :k

     Xo = bsxfun(@minus,X,mu(:,i));

     Xo = bsxfun(@times,Xo,sqrtR(:,i)');

     Sigma(:,:,i) = Xo*Xo'/nk(i);

     Sigma(:,:,i) = Sigma(:,:,i)+eye(d)*(1e-); % add a prior for numerical stability

 end

 model.mu = mu;

 model.Sigma = Sigma;

 model.weight = w;

e-step:

e step 需要解释很多阿。
9 logRho，首先我们知道R 是每项表示一个i-th 样本在 j-th GM 中的概率值，计算公式如下，公式中x是d-by-1 的sample，也就是gamma 中的N()
%Gaussian posterior probability
%N(x|pMiu,pSigma) = 1/((2pi)^(D/2))*(1/(abs(sigma))^0.5)*exp(-1/2*(x-pMiu)'pSigma^(-1)*(x-pMiu))
问题是上面公式不一定能按步求出来阿，例如 sigma^-1，不一定解得出来阿，所以对上面得N()log 一下，后计算，同时避开计算sigma^-1，这个矩阵就是logRho
20-31 便是12 行的函数调用，其中涉及了一堆矩阵转换，验证过没有错，计算的就是log 后的 N()
14 上面公式 gamma 的分子部分。
15-16 是计算当前的loglikehood。
17 计算R 矩阵的log 形式。
18 反计算R。

 %% e-step

 function [R, llh] = expectation(X, model)

 mu = model.mu;

 Sigma = model.Sigma;

 w = model.weight;

 n = size(X,);

 k = size(mu,);

 logRho = zeros(n,k);

 for i = :k

     logRho(:,i) = loggausspdf(X,mu(:,i),Sigma(:,:,i));

 end

 logRho = bsxfun(@plus,logRho,log(w));

 T = logsumexp(logRho,);

 llh = sum(T)/n; % loglikelihood

 logR = bsxfun(@minus,logRho,T);

 R = exp(logR);

 %% log pdf

 function y = loggausspdf(X, mu, Sigma)

 d = size(X,);

 X = bsxfun(@minus,X,mu);

 [U,p]= chol(Sigma);

 if p ~=

     error('ERROR: Sigma is not PD.');

 end

 Q = U'\X;

 q = dot(Q,Q,);  % quadratic term (M distance)

 c = d*log(*pi)+*sum(log(diag(U)));   % normalization constant

 y = -(c+q)/;