1 K-means 与 EM 的联系
给定 
维空间中一个包含 
个点的数据集 %5ET)
, 以及期望其聚成 
簇：
, 我们可以定义每个簇的中心点为
其中 
表示簇 
的点的个数。这样，K-means 算法的目标函数 (平方差和) 为：
%20%3D%20%5Cdisplaystyle%20%5Csum_%7Bi%3D1%7D%5Ek%20%5Csum_%7Bx_j%20%5Cin%20C_i%7D%20%7C%7Cx_j%20-%20%5Cmu_i%7C%7C%5E2)
1.1 EM 算法的基本原理和步骤
假设每一个簇 都由一个多元正态分布刻画，即
%20%3D%20f(x%7CC_i%3B%5Cmu_i%2C%5CSigma_i)%20%3D%20%5Cfrac%7B1%7D%7B(2%5Cpi)%5E%7B%5Cfrac%7Bn%7D%7B2%7D%7D%7C%5CSigma_i%7C%5E%7B%5Cfrac%7B1%7D%7B2%7D%7D%7D%20%5Cexp%5C%7B-%20%5Cfrac%7B(x-%5Cmu_i)%5ET%5CSigma_i%5E%7B-1%7D(x-%5Cmu_i)%7D%7B2%7D%5C%7D)
其中，簇均值 
及协方差矩阵 
均是未知参数。)
是 
属性属于簇 的概率密度。令 
表示对应 
的第 
维度的随机变量，记 %5ET)
代表对应于 
个维度的随机向量。假设 
的概率密度函数是在所有 个簇之上的高斯混合模型，定义为
%20%3D%20%5Cdisplaystyle%20%5Csum_%7Bi%3D1%7D%5Ek%20f_i(x)P(C_i)%20%3D%20%5Csum_%7Bi%3D1%7D%5Ek%20f_i(x%7CC_i%3B%5Cmu_i%2C%5CSigma_i)P(C_i))
其中先验概率 )
, 满足
%20%3D%201)
我们将簇 的参数简记作
%5C%7D)
则 
的似然为
%20%3D%20%5Cprod_%7Bj%3D1%7D%5Em%20f(x_j))
则 MLE (极大似然估计) 为
))
由贝叶斯公式可知
%20%3D%20%5Cfrac%7BP(x_j%7CC_i)P(C_i)%7D%7B%5Csum_%7Bt%7D%5EkP(x_j%7C%20C_t)P(C_t)%7D)
由于每个簇都建模为一个多元正态分布，故而
%20%5Capprox%202%5Cepsilon%20%5Ccdot%20f_i(x_j))
因而，)
可以看作是点 
在簇 中的权值或贡献。
- 初始化：
, 对于每一个簇 , 均值 
使用均匀分布随机地初始化 且 
, %20%5Cleftarrow%20%5Cfrac%7B1%7D%7Bk%7D)
.
- E 步：计算
)
, 且记 %5ET)
表示簇 在所有 个点上的权向量。
- M 步：重新估计
)
, 即
(x_j%20-%20%5Cmu_i)%5ET%7D%7Bw_i%5ET%5Cmathbf%7B1%7D%7D%5C%5C%20%26P%5Et(C_i)%20%5Cleftarrow%20%5Cfrac%7Bw_i%5ET%5Cmathbf%7B1%7D%7D%7Bm%7D%20%5Cend%7Baligned%7D)
- 不断地依次重复操作
步和 
步，直到
.
其他
