一.系统聚类法

1.基本思想

将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。

算法：

第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类， $G_{1}^{(0)},G_{2}^{(0)},...,G_{n}^{(0)}$ 。计算各类之间的距离（初始时即为各样本间的距离），得到一个N*N维的距离矩阵D⁽⁰⁾。这里，标号(0)表示聚类开始运算前的状态。

第二步：假设前一步聚类运算中已求得距离矩阵D⁽ⁿ⁾，n为逐次聚类合并的次数，则求D⁽ⁿ⁾中的最小元素。如果它是G_i⁽ⁿ⁾和G_j⁽ⁿ⁾两类之间的距离，则将G_i⁽ⁿ⁾和G_j⁽ⁿ⁾两类合并为一类 $G_{ij}^{(n+1)}$ ，由此建立新的分类： $G_{1}^{(n+1)},G_{2}^{(n+1)},...,G_{l}^{(n+1)}$ 。

第三步：计算合并后新类别之间的距离，得D⁽ⁿ⁺¹⁾。

计算 $G_{ij}^{(n+1)}$ 与其它没有发生合并的 $G_{1}^{(n+1)},G_{2}^{(n+1)},...,G_{l}^{(n+1)}$ 之间的距离，可采用多种不同的距离计算准则进行计算。

第四步：返回第二步，重复计算及合并，直到得到满意的分类结果。（如：达到所需的聚类数目，或D⁽ⁿ⁾中的最小分量超过给定阈值D等。）

2.距离计算准则

那么什么是距离计算准则呢？

进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。

主要的距离计算准则：

–最短距离法

–最长距离法

–中间距离法

–重心法

–类平均距离法

聚类准则函数：

（1）最短距离法：设H和K是两个聚类，则两类间的最短距离定义为：

$D_{HK}=min(d_{uv}),u\in H,v\in K$

其中，d_u,v表示H类中的样本x_u和K类中的样本x_v之间的距离，D_H,K表示H类中的所有样本和K类中的所有样本之间的最小距离。

递推运算：假若K类是由I和J两类合并而成，则

$\left.\begin{matrix} D_{HI}=min(d_{mn})&,m\in H &,n\in I \\ D_{HJ}=min(d_{mn})&,m\in H &,n\in J \end{matrix}\right\}\Rightarrow D_{HK}=min(D_{HI},D_{HJ})$

（2）最长距离法：设H和K是两个聚类，则两类间的最长距离定义为：

$D_{HK}=max(d_{uv}),u\in H,v\in K$

其中d_u,v的含义与上面相同。

递推运算：假若K类是由I和J两类合并而成，则

$\left.\begin{matrix} D_{HI}=max(d_{mn})&,m\in H &,n\in I \\ D_{HJ}=max(d_{mn})&,m\in H &,n\in J \end{matrix}\right\}\Rightarrow D_{HK}=max(D_{HI},D_{HJ})$

（3）中间距离法：设K类是由I和J两类合并而成，则H和K类之间的距离为：

$D_{HK}=\sqrt{\frac{1}{2}D_{HI}^{2}+\frac{1}{2}D_{HJ}^{2}-\frac{1}{4}D_{IJ}^{2}}$

它介于最长距离和最短距离之间。

（4）重心法：假设I类中有n_I个样本，J类中有n_J个样本，则I和J合并后共有n_I+n_J个样本。用n_I/(n_I+n_J)和n_J/(n_I+n_J)代替中间距离法中的系数，得到重心法的类间距离计算公式：

$D_{HK}=\sqrt{\frac{n_{i}}{n_{i}+n_{j}}D_{HI}^{2}+\frac{n_{j}}{n_{i}+n_{j}}D_{HJ}^{2}-\frac{n_{i}n_{j}}{(n_{i}+n_{j})^{2}}D_{IJ}^{2}}$

（5）类平均距离法：若采用样本间所有距离的平均距离，则有：

$D_{HK}=\sqrt{\frac{1}{n_{H}+n_{K}}\sum_{ _{j\in K}^{i\in H}}^{ }d_{ij}^{2} }$

递推运算公式：

$D_{HK}=\sqrt{\frac{n_{i}}{n_{i}+n_{j}}D_{HI}^{2}+\frac{n_{j}}{n_{i}+n_{j}}D_{HJ}^{2}}$

二. k均值算法

1.算法思想及基本步骤

将给定的样本划分为K类，K预先指定。

算法基本思想：基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。

算法步骤：

1.为每个聚类确定一个初始聚类中心，这样，就有K个初始聚类中心。

2.将样本集中的样本Xi按照最小距离原则分配到最邻近聚类Zj

$d_{ij}=min(\left \| x_{i}-z_{j} \right \|),x_{i}\in S,z_{j}\in Z$

3.使用每个聚类中的样本均值作为新的聚类中心。

4.重复步骤2.3直到聚类中心不再变化。

5.结束，得到K个聚类。

2.算法的优化目标

K均值算法的聚类准则函数为：

$J=\sum_{j=1}^{k}\sum_{i=1}^{n}\left \|x_{i}^{(j)}-z_{j} \right \|^{2}$

在算法中我们需要计算K个聚类的样本均值，算法名称由此得来。

我们要寻找聚类准则函数J的最小值作为算法优化的目标，当J最小的时候，函数对于每个聚类中心的偏导数为0：

$\frac{\partial J }{\partial z_{j}}=-2\sum_{i=1}^{n}(x_{i}^{(j)}-z_{j})=-2\sum_{i=1}^{n}x_{i}^{(j)}+2|S_{j}|z_{j}=0$

得到 $z_{j}=\frac{1}{|S_{j}|}\sum_{i=1}^{n}x_{i}^{(j)}$ 。这说明取类内样本均值为聚类中心可以使得聚类准则函数达到最小。

3.初始聚类中心的选取

初始聚类中心的选取决定着计算的迭代次数，甚至决定着最终的解是否为全局最优，所以选择一个好的初始聚类中心是很有必要的。

首先选择第一个样本点作为第一个聚类中心。

然后选取距离第一个点最远的点作为第二个聚类中心。

……

第j个聚类中心要远离第1~j-1个聚类中心。

或者可以多次随机取初始聚类中心，得到聚类结果，取平均值。

三.聚类结果的评价

迅速评价聚类结果，在上述迭代运算中是很重要的，特别是具有高维特征向量的模式，不能直接看清聚类效果，因此，可考虑用以下几个指标来评价聚类效果：

–聚类中心之间的距离

距离值大，通常可考虑分为不同类

–聚类域中的样本数目

样本数目少且聚类中心距离远，可考虑是否为噪声

–聚类域内样本的距离方差

方差过大的样本可考虑是否属于这一类

模式聚类目前还没有一种通用的放之四海而皆准的准则，往往需要根据实际应用来选择合适的方法。

秒客网

数据挖掘——学习笔记（系统聚类法和K均值聚类法）