聚类算法是在没有给定标签和样本值的前提下进行数据划分，是典型的无监督学习(unsupervised learning)算法。聚类试图将数据集中的样本划分成若干个不相交的子集，称为“簇”，或“类”。一个好的样本划分肯定是簇内的样本相似度高，而簇与簇之间的样本相似度低。

基于原型的聚类

簇是对象的集合，其中每个对象到定义该簇的原型的距离比其他簇的原型距离更近，例如在下面的k-means算法中，原型就是簇的质心。

1.k-means算法

k-means算法把数据集划分为k个簇，划分依据是簇的每一个样本点到质心（均值）的最小化平方误差和，即欧氏距离。欧氏距离越小，则代表这一个簇的紧密程度越大，簇内的样本相似度越高。

给定样本集$D=\{x_{1},x_{2},...,x_{m}\}$，k-means算法得到的簇划分$C=\{C_{1},C_{2},...,C_{k}\}$最小化平方误差

$$ E=\sum_{i=1}^{k}\sum_{x\in C_{i}}||x-\mu_{i}||_{2}^{2} $$

其中$\mu_{i}=\frac{1}{|C_{i}|}\sum_{x\in C_{i}}x$ 为簇$C_{i}$的均值向量
但直接求解欧氏距离最小值并不容易，因此采用迭代求解的方法。

1.首先随机选取k个质心，遍历每一个样本点，把样本点归入距它最近的质心所代表的簇中。
2.重新计算质心位置，即当前簇中的样本点的均值。
3.重复以上两步，直到算法收敛（更新不再产生划分变动），或者达到停止条件。

k值需要预先指定，而很多情况下k值难以确定，这是k-means的一个缺陷。

k-means的迭代过程本质上是坐标上升的过程。k-means是必定会收敛的，但是和梯度下降一样，只能保证收敛到局部最优，而不能保证收敛到到全局最优。因此初始质心的选择对算法的结果影响十分巨大。

坐标上升法每次通过更新函数中的一维，把其他维的参数看成常量，迭代直到当前维度收敛，再通过多次的迭代计算其他维度以达到优化函数的目的。

因为k-means算法是求均方误差，因此对于一些偏差较大的噪声点非常敏感，因此在k-means基础上可以做适当优化。

K-medoids算法就是一种优化算法，它和k-means唯一不同之处是：k-medoids算法用类中最靠近中心的一个样本点来代表该聚类，而k-means算法用质心来代表聚类。可以减少噪声点带来的影响。

二分K均值法也是一种优化算法，二分K均值法初始时将所有点看成一个簇，在簇的数量小于K的时候进行迭代，算法的核心是选择一个簇一分为二，这里一分为二的方法还是K均值法，只不过K变成了2。二分K均值依次计算每个簇一分为二后新的总平方误差，选择划分后总体平方误差最小的簇进行划分。这样就尽可能避免了k-means落入局部最优的情况。

2.学习向量量化（Learning Vector Quantization）

学习向量量化（LVQ）也是试图找到一组原型来刻画聚类结构，但与k-means不同的是，LVQ的样本带有类别标记。

给定样本集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})\}$,每个样本$x_{j}$是一个n维向量，$y_{j}$是类别标记，LVQ的目标是学得一组n维原型量$\{p_{1},p_{2},...,p_{q}\}$,每一个原型向量代表一个簇的原型。原型向量的簇标记为$t_{i}\in \gamma$
同样，LVQ也是采用迭代求解的方法。

1.随机选取一个有标记的样本点，找出距它最近的原型向量，根据两者标记是否一致进行更新
2.若样本$x_{j}$与原型向量$p_{i}$标记相同，则令$p_{i}$向$x_{j}$靠拢，反之则远离$x_{j}$
相同：

$$ {p}'=p_{i}+\eta(x_{j}-p_{i}) $$

不同：

$$ {p}'=p_{i}-\eta(x_{j}-p_{i}) $$

其中$\eta\in (0,1)$是学习率
3.重复直到满足停止条件

LVQ和k-means一样都可以在簇与簇之间画出分界线，称为簇划分。

3.高斯混合聚类

高斯混合聚类采用概率模型来表达聚类原型。
对于一个服从高斯分布（n维正态分布）的向量$x$，则

$$ p(x)=\frac{1}{(2\pi)^{\frac{2}{n}}|\Sigma|^{\frac{1}{2}}}e^{-\frac{1}{2}(x-\mu)^{T}\Sigma^{-1}(x-\mu)} $$

其中$\mu$是n维均值向量，$\Sigma$是协方差矩阵，次分布的完全由这两个参数确定。因此，记概率密度函数为$p(x|\mu,\Sigma)$
则高斯混合分布：

$$ p_{M}(x)=\sum_{i=1}^{k}\alpha_{i}p(x|\mu_{i},\Sigma_{i}) $$

\
其中$\sum_{i=1}^{k}\alpha_{i}=1$
若训练集由高斯混合分布生成，对于样本$z_{j}\in \{1,2,...,k\}$，样本属于某一个高斯分布的概率为$p(z_{j}=i)=\alpha_{i}$,为先验概率。根据贝叶斯定理，其后验分布为：

$$ p_{M}(z_{j}=i|x_{j})=\frac{p(z_{j}=i)p_{M}(x_{j}|z_{j}=i)}{p_{M}(x_{j})} $$

$$ =\frac{\alpha_{i}p(x_{j}|\mu_{i},\Sigma_{i})}{\sum_{l=1}^{k}\alpha_{l}p(x_{j}|\mu_{l},\Sigma_{l})}=\gamma_{ji}(i=1,2,...,k) $$

这就把样本来自每个高斯分布的概率（某一个高斯分布被选中的概率）转化成了由每个高斯分布生成的概率。
用似然函数求解最大似然估计：

$$ lnL(D)=ln\left(\prod p_{M}(x_{j})\right)=\sum_{j=1}{k}ln\left(\sum_{i=1}^{k}\alpha_{i}p(x_{j}|\mu_{i},\Sigma_{i})\right) $$

求解得：

$$ \mu_{i}=\frac{\sum_{j=1}^{m}\gamma_{ji}x_{j}}{\sum_{j=1}^{m}\gamma_{ji}} $$

$$ \Sigma_{i}=\frac{\sum_{j=1}^{m}\gamma_{ji}(x_{j}-\mu_{i})(x_{j}-\mu_{i})^{T}}{\sum_{j=1}^{m}\gamma_{ji}} $$

可以求得$\alpha_{i}=\frac{1}{m}\sum_{i=1}^{m}\gamma_{ji}$
同样采用迭代法：

1.假设$\mu,\Sigma$已知，求出$\gamma$的值
2.更新$\mu,\Sigma$参数
3.重复1,2,直到算法收敛或者停止

参考-周志华《机器学习》