系统聚类法及其应用研究*

田 兵

（包头师范学院《阴山学刊》编辑部，内蒙古包头 014030）

系统聚类法及其应用研究*

田 兵

（包头师范学院《阴山学刊》编辑部，内蒙古包头 014030）

本文介绍了系统聚类法的基本思想和常用方法以及优缺点，然后举例说明了其在具体问题中的应用。

聚类分析;系统聚类法;最短距离法、最长距离法、中间距离法、类平均法、重心法、离差平方和法

聚类分析是将样本进行分类的一种统计方法。它是根据样本数据计算样本之间的距离（相似程度），将距离较近的样本归为同一类，不同类别的样本距离相对较远。聚类分析的内容包含十分广泛，有系统聚类法、动态聚类法、分裂法、最优分割法、模糊聚类法、图论聚类法、聚类预报等多种方法。

系统聚类法也称层次聚类，是聚类分析许多方法中用的最多的一种，其基本思想是:开始将n个样本各自作为一类，并规定样本之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类与其他类的距离;重复进行两个最近类的合并，每次减少一类，直至所有的样本合并为一类。根据所定义的类与类的距离，系统聚类法可以分为最短距离法、最长距离法、中间距离法、类平均法、重心法、离差平方和法。

1 常用的系统聚类法

1.1 最短距离法

定义类与类之间的距离为两类最近样本间的距离，即

称这种系统聚类法为最短距离法。其中用dij.表示第i个样本与第j个样本的距离，G1，G2，…表示类，DKL表示Gk与GL的距离。

当某步骤类GK和GL合并为GM后，按最短距离法计算新类GM与其他类GJ的类间距离，其递推公式为:

1.2 最长距离法

定义类与类之间的距离为两类最远样本间的距离，即

称这种系统聚类法为最短距离法。

当某步骤类GK和GL合并为GM后，则GM与任一类GJ的距离为:

DMJ=max{DKL，DLJ}.

1.3 中间距离法

定义类与类之间的距离取介于上述最短距离和最长距离的中间距离。设某一步将GK和GL合并为GM，对于任一类 GJ考虑由 DKL，DLJ，DKJ为边长组成的三角形，取DKL边的中线作为DMJ，由初等平面几何可知，

称这种系统聚类法为中间距离法。

1.4 类平均法

类平均法有两种定义，一种定义方法是把类与类之间的距离定义为所有样本对之间的平均距离，即定义GK和GL之间的距离为

其中nK和nL分别为GK和GL的样本个数，dij为GK中样本i与GL中样本j之间的距离。它的递推公式为:

另一种定义方法是定义类与类之间的平方距离为样本对之间平方距离的平均值，即

它的递推公式为

类平均法较充分的利用了所有样本之间的信息，在很多情况下，它被认为是一种较好的系统聚类法。

1.5 重心法

类与类之间的距离定义为它们的重心之间的Euclid距离。设GK和GL的重心分别为¯xK和¯xL，则GK和GL之间的平方距离为

这种系统聚类方法称为重心法。它的递推公式为

重心法在处理异常值方面比其他系统类法更稳健，但是在别的方面一般不如类平均法或离差平方和法的效果好。

1.6 离差平方和法

离差平方和法是基于方差分析思想，如果类分得正确，则同类样本之间的离差平方和应当较小，不同类样本之间的离差平方和应当较大。

设类GK和GL合并为新的类GM，则GK、GL和GM的离差平方和分别是

这种系统聚类法称为离差平方和法。它的递推公式为

GK和GL之间的平方距离也可以写成

可见，这个距离公式与重心法的距离公式只相差一个常数。重心法的类间距与两类的样本数无关，而离差平方和法的类间距与两类的样本数有较大的关系，两个大类倾向于有较大的距离，因而不宜合并。这更符合聚类的实际要求。离差平方和法在许多场合下优于重心法，是一种比较好的系统聚类法，但它对异常值很敏感。

2 数据样本

选用2010年全国各省（自治区、直辖市）的预期寿命指数、教育指数、人类生产总值指数为样本数据（见表1）。对表1进行系统聚类分析:按照最短距离法、最长距离法、中间距离法、类平均法、重心法、离差平方和法将样本数据分为5类，得出每种分类法下的分类结果。我们通过R软件编写程序，可以得到具体的分 类情况。最短距离法:

表1:样本数据

图1:最短距离法下的分类情况

最长距离法:

图2:最长距离法下的分类情况

中间距离法:

图3:中间距离法下的分类情况

类平均法

图4:类平均法下的分类情况

重心法:

离差平方和法:

图6:离差平方和法下的分类情况

比较上述六种不同系统聚类方法下的分布情况， 可以得到表2。

表2:不同聚类方法结果的比较

从表2可以看出应用最短距离法和中间距离法的分类结果是一样的，应用类平均和重心法的分类结果是一样的。六种分类法都将天津、北京、上海归为一类。从表1中可以看出，澳门和香港的数据较接近，所以澳门和香港应归为一类。故最长距离法、类平均法、重心法和离差平方和法的分类质量较高。

3 系统聚类法的优缺点

系统聚类方法的优点是操作简单，能细致地看出小类聚为大类的过程，由合并时的距离水平可以看出样品间的亲疏程度。但是它的缺点也显而易见。一旦一组对象合并时，下一步将在新生成的类上进行。已做的处理不能被撤消，类之间不能交换对象。如果在某一步没有很好地选择合并的话，将会造成低质量的聚类结果。因为合并或分裂的决定需要检查和估算大量的对象或类。需计算大量的距离，需要花费大量的时间，所以算法不具有很好的可伸缩性。上述的每种聚类方法都有其缺陷。例如，最短距离法容易受链式结构的影响，从而导致蔓延较长的类。类平均连接方法、最长距离法则倾向于集中在内部集合上形成同种的紧密类（通常为球形）。重心聚类和中间距离聚类方法有可能导致逆增（当聚类规模增大时，对象与聚类之间的相异度反而减小），这就使得谱系图难以解释。

［1］赵东方.数学模型与计算［M］.北京:科学出版社，2007，2.

［2］刘顺忠.数理统计理论、方法、应用和软件计算［M］.武汉:华中科技大学，2005，9.

［3］薛 毅.陈立萍.统计建模与R软件［M］.北京:清华大学出版社，2007.

［4］王芳.传统聚类方法的分析及改进［D］长沙:中南大学，2007.

［5］杨小兵.聚类分析中若干关键技术的研究［D］.杭州:浙江大学，2005.

［6］戴涛.聚类分析算法研究［D］.清华大学2005.

［7］张惟皎，刘春煌，李芳玉.聚类质量的评价方法［J］.计算机工程，2005（20）.

Hierarchical Clustering Method and Its Research about Application

TIAN Bing
（Editor of Academic Journal，Baotou Teachers College;Baotou 014030）

The article introduces the basic thought of hierarchical clustering method，common method and strengths and weaknesses.Then its application of specific problems is elucidated.

cluster analysis;hierarchical clustering method;single linkage method;complete linkage method;median method;average linkage method;centroid hierarchical method;ward’s minimum variance method

O213

A

1004－1869（2014）02－0011－06

10.13388/j.cnki.ysajs.2014.02.003

2014－04－12

田兵（1982－），男，山西五台人，编辑，理学硕士，研究方向:数理统计。