重心到三个顶点距离

系统聚类法（hierarchical clustering method）是最常用的、也是比较成熟的一种聚类分析方法，又称谱系聚类法或者层次聚类法.系统聚类法的基本思想是：设有n个事物.开始时，将每个事物各看成一类，因此一共有n类，这时类与类之间的距离也就是事物之间的距离.然后找出距离最小的两类，将它们合并为一类.这时的类可能已包含多个事物，因此需要规定类与类之间的距离，以衡量各类之间的差别.计算各类之间的距离，并找出距离最小的两类，将它们合并为一类.再找出距离最小的两类，将它们合并为一个新的类.……这样一直下去，每次都会使类别的个数减少1，一直到将所有的事物合并为一类为止.或者合并到类的数目满足聚类的要求为止.

图24.1　聚类图示例

聚类分析的结果，可以用一个图形象地表示出来，这种图像一棵树，称为聚类图.

图24.1就是一个聚类图.如果我们想知道分成2类的聚类结果，只要在与2条竖线相交的位置画一条水平线l1，就可以看出分成的2类是：

﹛1，2，3﹜，﹛4，5，6﹜.

如果我们想知道分成3类的聚类结果，只要在与3条竖线相交的位置画一条水平线l2，就可以看出分成的3类是：

﹛1﹜，﹛2，3﹜，﹛4，5，6﹜.

在系统聚类分析的每一步中，都要寻找距离最小的两类，因此必须对类与类之间的距离作出规定，可以采用不同的方法规定类与类之间的距离.当然，随着这种规定的不同，所得到的聚类分析的结果也就可能不一样.这一点将在下面的例题分析中进一步加以说明.

例2　足球是人们最喜爱的运动之一.每届足球世界杯赛都是全世界尤其是青少年狂欢的节目.2002年足球世界杯赛，最后有16支球队进入前16名，这些球队在进入前16名以前的分组赛中的进球数和失球数统计如表24.3所示.

表24.3　2002年足球世界杯赛分组赛进球、失球数统计

以进球数x为横坐标，以失球数y为纵坐标，每个足球队可以用坐标平面上的一个点来表示，由此可以作出这16支球队的散点图，如图24.2所示.

下面对这16支足球队进行系统聚类分析.我们采用通常平面上点的距离表示对应的球队之间的差别.

（1）最短距离法.将两个类中各点之间的最短距离规定为这两个类的类间距离.

图24.2　足球队散点图

参见图24.2，开始时，16个点就是16个类.由于1号点、10号点、15号点为同一点，它们之间的距离为0.因此首先将1号点与10号点合并为一类，再与15号点合并为一类，记为G1.11号点与14号点也是同一点，因此也可合并为一类，记为G2.

接着计算每两个类之间的距离，可得目前两个类间的最短距离为1.6号点与G1类间的距离为1，因此将6号点与G1类合并为新的类，记为G3.4号点与8号点的距离也为1，因此可合并为一类，记为G4.

再计算目前每两类之间的距离，可得最短距离为1.G3类含有点1、10、15、6.2号点与G3中的6号点的距离最短且为1，因此2号点与G3的距离为1，于是将2号点与G3合并成一个新的类.16号点与G4中的4号点的距离为1，即16号点与G4的距离为1，于是将16号点与G4合并成一类.

如此继续下去，直至聚合成一类为止，得到聚类图，如图24.3所示.

从这张聚类图可以看出，如果将球队分成3类，只要在与3条竖线相交的位置画一条水平线，就可看出聚类结果为

第1类：﹛9.德国，5.巴西﹜；

第2类：﹛3.西班牙﹜；

第3类：﹛12.英格兰，16.比利时，8.美国，4.巴拉圭，7.韩国，13.墨西哥，14.意大利，11.瑞典，2.塞内加尔，6.土耳其，15.日本，10.爱尔兰，1.丹麦﹜.

图24.3　最短距离法聚类图

（2）最长距离法.将两个类中各点之间的最长距离规定为这两类的类间距离.

在例2中，仿照上面的方法，可得到聚类图，如图24.4所示.

图24.4　最长距离法聚类图

如果将球队分成3类，由聚类图可得到下列分类结果：

第1类：﹛9.德国，5.巴西，3.西班牙﹜；

第2类：﹛8.美国，4.巴拉圭，16.比利时，2.塞内加尔﹜；

第3类：﹛12.英格兰，13.墨西哥，7.韩国，14.意大利，11.瑞典，6.土耳其，15.日本，10.爱尔兰，1.丹麦﹜.

（3）重心法.将两类的重心之间的距离规定为这两类的类间距离.

一个类的重心就是属于这一类的所有样品的平均值.设Gp＝﹛x1，x2，…，xn﹜，则Gp的重心为

显然，如果一个类中只有一个样品，则重心就是这个样品.如果将Gp，Gq两类合并，则合并后的类Gr的重心为

其中np，nq是Gp，Gq中的样品数，nr＝np＋nq是Gr中的样品数.

在例2中，设G1＝﹛1.丹麦，10.爱尔兰，15.日本，6.土耳其﹜，G2＝﹛7.韩国，13.墨西哥﹜，于是，G1的重心的坐标为

因此G1的重心为（5，2.25）.

G2的重心的坐标为

因此G2的重心为（4，1.5）.

所以G1与G2两类之间的距离为

按照上述规定的类间距离计算方法，经过逐步合并，可以得到聚类图，如图24.5所示.

图24.5　重心法聚类图

从此聚类图可以看出，如果将球队分成3类，聚类结果如下：

第1类：﹛9.德国，5.巴西，3.西班牙﹜；

第2类：﹛16.比利时，8.美国，4.巴拉圭，2.塞内加尔﹜；

第3类：﹛12.英格兰，14.意大利，11.瑞典，13.墨西哥，7.韩国，6.土耳其，15.日本，10.爱尔兰，1.丹麦﹜.

通过对例2的分析我们知道，可以采用不同的方法规定两个类之间的距离.当类间距离的规定不同时，可能会得到不一样的聚类分析结果.除了上述3种规定类间距离的方法，还有多种其他方法.

通过上面的例子可以看出，所谓聚类就是将数据划分成不同的类的一个过程，要求处于同一类中的对象具有很大的相似性，而处于不同类的对象之间则具有很大的相异性.从统计学观点看来，聚类分析是通过数据建模简化数据的一种科学方法.当今世界已进入“大数据时代”.根据科学家推算，如果将2013年全世界的数据存储在光盘上，并且将这些光盘分成5堆，每一堆都可以从地球堆到月球.人们对于海量数据的挖掘和运用，将给人类生活、工作和思维产生巨大的影响，而聚类分析正是对大数据进行挖掘的重要工具之一.