机器学习笔记（五）聚类

聚类：“聚类是指将数据集划分为若干类，聚类的本质即将数据集中相似的样本进行分组的过程，每个组称为一个簇，每个簇的样本对应一个潜在的类别，使得各个簇之内的数据最为相似，而各个簇之间的数据相似度差别尽可能的大。聚类分析就是以相似性为基础，在一个聚类中的模式之间比不在同一个聚类中的模式之间具有更多的相似性。对数据集进行聚类划分，样本没有类别标签，一种典型的无监督学习方法。
聚类方法：层次聚类、K-Means、谱聚类等

K-Means模型
K-Means最初起源于信号处理，是一种比较流行的聚类方法，基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。K-Means算法的特点是类别的个数是人为给定的，数据之间的相似度可以使用欧氏距离度量 。

优化目标：最小化所有样本点到所有簇中心的距离平方和。

优化算法：
交替迭代法：基本思想是將多變量問題轉化爲單變量問題的求解，即，在一步計算時，保持其他的變量固定不變，只求解一個變量的問題，下一步時，再固定個變量，並尋找另一個變量求解，如此進行下去，直到得到問題的解。基本思想是将多变量问题转化为单变量问题的求解，在一步计算时，保持其他的变量固定不变，只求解一个变量的问题，下一步时，再固定一个变量，并寻找另一个变量求解，如此进行下去，知道得到问题的解。

算法流程
随机选择k个点作为初始中心
repeat：
将每个样本指派到最近的中心，形成k个类
重新计算每个类的中心为该类样本均值
直到中心不发生变化

高斯混合模型（GMM）
混合模型是一个可以用来表示在总体分布（distribution）中含有 K 个子分布的概率模型，换句话说，混合模型表示了观测数据在总体中的概率分布，它是一个由 K 个子分布组成的混合分布。混合模型不要求观测数据提供关于子分布的信息，来计算观测数据在总体分布中的概率。
高斯混合模型可以看作是由 K 个单高斯模型组合而成的模型，这 K 个子模型是混合模型的隐变量（Hidden variable）。一般来说，一个混合模型可以使用任何概率分布，这里使用高斯混合模型是因为高斯分布具备很好的数学性质以及良好的计算性能。
k-means和GMM的关系
在特定条件下，k-means和GMM方法可以互相用对方的思想来表达。在k-means中根据距离每个点最接近的类中心来标记该点的类别，这里存在的假设是每个类簇的尺度接近且特征的分布不存在不均匀性。这也解释了为什么在使用k-means前对数据进行归一会有效果。高斯混合模型则不会受到这个约束，因为它对每个类簇分别考察特征的协方差模型。
K-means算法可以被视为高斯混合模型（GMM）的一种特殊形式。整体上看，高斯混合模型能提供更强的描述能力，因为聚类时数据点的从属关系不仅与近邻相关，还会依赖于类簇的形状。n维高斯分布的形状由每个类簇的协方差来决定。在协方差矩阵上添加特定的约束条件后，可能会通过GMM和k-means得到相同的结果。
在k-means方法中使用EM来训练高斯混合模型时对初始值的设置非常敏感。而对比k-means，GMM方法有更多的初始条件要设置。实践中不仅初始类中心要指定，而且协方差矩阵和混合权重也要设置。可以运行k-means来生成类中心，并以此作为高斯混合模型的初始条件。由此可见并两个算法有相似的处理过程，主要区别在于模型的复杂度不同。

EM算法：是一种迭代算法，1977 年由 Dempster 等人总结提出，用于含有隐变量（Hidden variable）的概率模型参数的最大似然估计。
每次迭代包含两个步骤：
第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

k-means与EM关系
k-means是两个步骤交替进行，可以分别看成E步和M步；
E步中将每个点分给中心距它最近的类（硬分配），可以看成是EM算法中E步（软分配）的近似。当方差无限小 的时候，EM相当于k-means。
M步中将每类的中心更新为分给该类各点的均值，可以认为是在「各类分布均为单位方差的高斯分布」的假设 下，最大化似然值；