聚类，混合模型，和EM算法
无监督学习任务：聚类（Clustering）
K-均值（K-mean）
混合高斯模型（Gaussian Mixture Models, GMM）
EM算法（Expectation-Maximization Algorithm）
评价指标（Evaluation Metrics）
（本文参考朱军老师的《概率机器学习》）
聚类（Clustering）
在有监督的分类问题中，训练数据由若干数据点及他们所属的类别组成，学习的目标是预测新数据应该分到其中哪一类。但对于无标签的数据（尤其是现在大数据时代的大多数数据），可以直接依据其特征本身的分布或特点进行分类（分簇，cluster），这就是聚类作为最开始的一大无监督学习任务（聚类和降维）的核心思想。
更具体的，为了将数据集分为不同的等价类，可以基于数据的 \(L_2\) 欧式空间距离（\(L_1\) 曼哈顿距离、\(L_\infty\) 切比雪夫距离、余弦距离、马氏距离），也可以基于如数据之间的其他相似性作为等价类。
类别之间除了同级关系，还可以是嵌套的层级关系（层级聚类，hierarchical clustering）。分类除了硬性的将每个数据点仅划分到一类，也可以软性的划分到多类。
从另一个角度来看，聚类还可以划分为：
- 基于连接（层次聚类）
- 基于中心点（K-均值）
- 基于概率分布（高斯混合模型）
- 基于密度
- 基于图
等。
K-均值（K-mean）
K-均值假设数据可以根据欧氏距离划分为不同的类，并且每个类有一个质心（centroid）。
于是，根据这个想法，为了找出真实质心，可以进行一下流程：
- 初始化：随机选择 \(K\) 个质心。
- 分配 (Assignment)：计算每个点到质心的距离，归入最近的簇。
- 更新 (Update)：重新计算每个簇的平均值作为新质心。
- 重复步骤2-3，直到质心不再变化或达到最大迭代次数。
可以看到，此算法收敛当且仅当簇内平方误差和收敛到最小： \[ J \gets \sum_{k=1}^K \sum_{i \in C_k} ||x_i - \mu_k||^2 \] 这是个非凸优化问题（也是为什么算法要用迭代的形式）。
由于目标函数的非凸性，算法会收敛到局部最优，为此，可以选取不同的初始质心 \(\{\mu_k\}\) 进行迭代，选的越多接近全局最优的概率越大。
当然，有规律的选初始质心比完全随机肯定更好。 Gonzales 在 1985 年提出了直接选数据点作为质心，并用贪心算法选与上一个质心距离最远的数据点作为下一个中心。Authur 和 Vassilvitskii 在 2007 年提出的改进算法保证了收敛步数不超过 \(O(\log K)\)。
可以看到K-均值十分简单有效，但最大的问题是其欧氏距离的假设限制了类分布的形状 - 无法处理畸形或者不规则的非圆类内分布。
混合高斯模型
K-均值作为硬性分类聚类，无法处理软性分类任务（如划分生物信息到计算机和生物两个分类）。为此，可以扩展质心的“点”为更加概率化的分布。
常见的概率分布峰数固定，无法作为任意数量的类别（峰）的概率密度函数。为此，假设有 \(K\) 个不同的概率分布及其概率密度函数 \(p_k(x)\)，混合分布是这些分布的线性组合： \[ p(x)=\sum_{k=1}^K \pi_k p_k(x) \] 混合高斯模型就是假设分布都是正态的 \(p_k(x)\sim\mathcal{N}(\mu_k,\Sigma_k)\)。混合高斯模型在扩展点为概率分布的同时，还扩展了类内形状，从仅支持圆变为支持椭圆。
更具体的，假设数据分布为 \(K\) 个高斯（正态）分布的和，其中每个高斯分布的权重（混合系数）是 \(\pi_k\)，均值是 \(\mu_k\)，协方差矩阵是 \(\Sigma_k\)。概率密度函数可以看到是： \[ p(x) = \sum_{k=1}^K \pi_k \mathcal{N}(x | \mu_k, \Sigma_k) \] 为了学习最优的混合高斯（分布）模型，考虑用最大似然估计： $$
$$
隐变量
可以看到上述概率密度函数过于耦合，并且关于 \(x\) 具体属于哪个类别的信息 \(p(x)\) 难以提供。于是，可以通过引进（类别作为）隐变量 \(Z\) 来给模型提供更多信息： \[ p(X, Z)=p(Z)p(X|Z) \]
EM 算法
期望最大化（Expectation maximization，EM）算法是一种迭代式求解隐变量概率分布模型参数估计的方法，想法和K-均值的算法类似。