系统聚类

1. 模型背景

聚类分析是研究如何将对象按照多个方面的特征进行综合分类的一种统计方法。然而在以往的分类学中，人们主要靠经验和专业知识作定性分类处理，许多分类不可避免地带有主观性和任意性，不能揭示客观事物内在的本质差别和联系；或者人们只根据事物单方面的特征进行分类，这些分类虽然可以反映事物某些方面的区别，但却往往难以反映各类事物之间的综合差异。聚类分析方法有效地解决了科学研究中多因素、多指标的分类问题。

在目前的实际应用中，系统聚类法（Hierarchical clustering methods，也称分层聚类法）由于类与类之间的距离计算方法灵活多样，使其适应不同的要求。该方法是目前实践中使用最多的。例如，考虑手写字符识别。手写字符识别样本集可以先划分成一般的组群，其中每个组群对应于一个唯一的字符，某些组群可以进一步划分成子组群，因为一个字符可能有多种显著不同的写法。另外，使用系统聚类方法可以在进化研究中按动物的生物学特征对它们分组，发现进化路径，得出物种的分层结构。

2. 模型原理

系统聚类，也称分层聚类或凝聚的层次聚类方法，使用自底向上的策略，属聚类分析的一种方法，系统聚类法是国内外使用得最多的一种聚类方法，这种方法是先将聚类的样本或变量各自看成一群，然后确定类与类间的相似统计量，并选择最接近的两类或若干个类合并成一个新类，计算新类与其他各类间的相似性统计量，再选择最接近的两群或若干群合并成一个新类，直到所有的样本或变量都合并成一类为止。

常用的系统聚类法是以距离为相似统计量时，确定新类与其他各类之间距离的方法，如最短距离法、最长距离法、中间距离法、重心法、群平均法、离差平方和法、欧氏距离等。

首先将几个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类与其他类的距离；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并成一类。

3. 实施分析步骤

以n个样本的聚类分析为例，系统聚类法的步骤如下：

• 定义以变量或指标的个数为维度的空间里的一种距离；
• 计算n个样本两两之间的距离；
• 将每个样本归为一类，根据计算出的样本间的距离合并距离最近的两类为一个新类；
• 再计算新类与其他各类的距离，同样再根据计算出的距离合并距离最近的两类为一个新类；
• 循环以上过程直至类别个数为1；
• 画出各阶段的聚类图并决定类别的个数。
• 对于变量聚类分析，只需要将距离替换为相似系数，然后将相似系数较大的变量分别聚类即可。

常用的空间距离有：绝对值距离、欧氏距离、切比雪夫距离、马氏距离和兰氏距离等。

确定了距离和相似系数后就要进行分类。分类有许多种方法，最常用的一种方法是在样品距离的基础上定义类与类之间的距离。首先将n个样品分成n类，每个样品自成一类，然后每次将具有最小距离的两类合并，合并后重新计算类与类之间的距离，这个过程一直持续到将所有的样品归为一类为止，并把这个过程画成一张聚类图，参照聚类图可方便地进行分类。因为聚类图很像一张系统图，所以这种方法就叫系统聚类法。系统聚类法是在实际中使用最多的一种方法，从上面的分析可以看出，虽然我们已给了计算样品之间距离的方法，但在实际计算过程中还要定义类与类之间的距离。定义类与类之间的距离也有许多方法，不同的方法就产生了不同的系统聚类方法，常用的有如下六种：

• 最短距离法：类与类之间的距离等于两类最近样品之间的距离；
• 最长距离法：类与类之间的距离等于两类最远样品之间的距离：
• 类平均法：类与类之问的距离等于各类元素两两之间的平方距离的平均；
• 重心法：类与类之间的距离定义为对应这两类重心之间的距离对样品分类来说，每一类的类重心就是该类样品的均值；
• 中间距离法：最长距离法夸大了类间距离，最短距离法低估了类间距离介于两者问的距离法即为中间距离法，类与类之问的距离既不采用两类之间最近距离。也不采用最远距离，而是采用介于最远和最近之间的距离；
• 离差平方和法(Ward法)：基于方差分析的思想，如果分类正确，同类样品之间的离差平方和应当较小，类与类之间的离差平方和应当较大。

4. 输入输出参数设置

系统聚类方法的核心问题在于度量两个类之间的距离，其中每个类一般是一个对象集。

系统聚类常用算法代表为AGNES算法，具体步骤主要分为：

输入：定义样本数据样本数包含m个无标记样本，相似性度量函数s，聚类簇数k

输出：k类样本

• 初始化每个样本为一个簇，，
• 计算样本两两之间的距离为，
• 通过相似性度量函数s，根据下面的式子来计算距离，找出最相似的两个簇合并

最小距离：

最大距离：

平均距离：

• 直到簇数为k，否则循环2）。

显然，最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，而平均距离则由两个簇的所有样本共同决定，当聚类簇距离由三种方式计算时，AGNES算法被相应的称为“单链接”（single-linkage），“全链接”（complete-linkage），“均链接”（average-linkage）算法。

5. 运行效果评价

系统聚类的优点在于距离与规则的相似度容易定义，不需要预先制定聚类数并且可以发现类的层次关系；但该方法的缺陷在于一旦合并步骤完成就不会被撤销，这种技术将不能更正错误的决定，同时奇异值对系统聚类影响过大，该方法不具有很好的可伸缩性，因为每次的合并决定都需考察评估多个对象和类。

6. 模型应用

如下图所示，将八个序号所示对象按系统聚类方法进行聚类：

第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2两个点合并为一个簇；

 第2步：对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后3，4点成为一簇；

 第3步：重复第2步的工作，5，6点成为一簇；

      第4步：重复第2步的工作，7，8点成为一簇；

      第5步：合并{1，2}，{3，4}成为一个包含四个点的簇；

      第6步：合并{5，6}，{7，8}，由于合并后的簇的数目已经达到了用户输入的终止条件，程序终止。

       具体步骤如表所示，最终聚为两类{1，2，3，4}、{5，6，7，8}结束

表1 系统聚类步骤