系统聚类的方法解析

1、聚类分析 1 聚类分析 一聚类分析的定义 二系统聚类的基本思想 三八种系统聚类方法 四类间距离的统一性 一、聚类分析的定义 “ 物以类聚，人以群分”。对事物进行分类，是人们认 识事物的出发点，也是人们认识世界的一种重要方法。 因此，分类学已成为人们认识世界的一门基础科学。 聚类分析就是分析如何对样品（或变量）进行量化分 类的问题。通常聚类分析分为Q型聚类和R型聚类。Q 型聚类是对样品进行分类处理，R型聚类是对变量进行 分类处理。 二、系统聚类的基本思想二、系统聚类的基本思想 系统聚类的基本思想是：距离相近的样品（或变量）先聚成类， 距离相远的后聚成类，过程一直进行下去，每个样品（或变量） 总能

2、聚到合适的类中。 系统聚类法是诸聚类分析方法中使用最多的一种，按下列步骤 进行： ?计算n个样品两两之间的距离，构成距离矩阵 ?合并距离最近的两类为一新类 ?计算新类与当前各类的距离。再合并、计算，直至只有一 类为止 ?画聚类图，解释 ?将n个样品各作为一类 三、八种系统聚类方法 在进行系统聚类之前，我们首先要定义类与类之间的 距离，由类间距离定义的不同产生了不同的系统聚类法。 常用的类间距离定义有8种之多，与之相应的系统聚类法 也有8种，分别为最短距离法、最长距离法、中间距离法、 重心法、类平均法、可变类平均法、可变法和离差平方和 法。它们的归类步骤基本上是一致的，主要差异是类间距 离的计算

3、方法不同。以下用d ij表示样品Xi与Xj之间距离， 用Dij表示类Gi与Gj之间的距离。 1. 最短距离法最短距离法 定义类与之间的距离为两类最近样品的距离，即为 (1) 设类与合并成一个新类记为，则任一类与的距离为 (2) ij GXGX ij dD jjii ? ? , min , min ikjr krij XGXG Dd ? ? , minmin,min ikjpikjq ijij XGXGxGxG dd ? ? min, kpkq DD? ?最短距离法进行聚类分析的步骤如下： （1）定义样品之间距离，计算样品的两两距离，得一距离 阵记为D （0） ，开始每个样品自成一类，显然这时D

4、ij= d ij。 （2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个 新类，记为Gr，即Gr=Gp，Gq。 （3）按（5.12）计算新类与其它类的距离。 （4）重复（2）、（3）两步，直到所有元素。并成一类为 止。如果某一步距离最小的元素不止一个，则对应这些 最小元素的类可以同时合并。 1. 最短距离法最短距离法 ?【例1】设有六个样品，每个只测量一个指标，分别是1，2， 5，7，9，10 ，试用最短距离法将它们分类。 （1）样品采用绝对值距离，计算样品间的距离阵D （0） ，见 表1 G1 G2 G3 G4 G5 G6 G1 0 G2 1 0 G3 4 3 0 G4 6 5 2

5、0 G5 8 7 4 2 0 G6 9 8 5 3 1 0 表 1 1. 最短距离法 （2）D （0）中最小的元素是D12 D 56 1，于是将G1和G2合 并成G7，G5和G6合并成G8，并利用（5.12）式计算新类与其 它类的距离D （1） ，见表2 G7 G3 G4 G8 G7 0 G3 3 0 G4 5 2 0 G8 7 4 2 0 表 2 1. 最短距离法 （3）在D （1）中最小值是D34 D482，由于G4与G3合并， 又与G8合并，因此G3、G4、G8合并成一个新类G9，其与其 它类的距离D （2） ，见表 3 G 7 G 9 G7 0 G9 3 0 表 3 1. 最短距离法

6、（4）最后将G7和G9合并成G10，这时所有的六个样品聚为一 类，其过程终止。 上述聚类的可视化过程见图1所示，横坐标的刻度表示并类 的距离。这里我们应该注意，聚类的个数要以实际情况所定， 其详细内容将在后面讨论。 图1 最短距离聚类法的过程 1. 最短距离法 定义类 i G 与 j G 之间的距离为两类最远样品的距离，即 为 , max ipjq pqij XGXG Dd ? ? (3) 最长距离法与最短距离法的并类步骤完全一样，也是将 各样品先自成一类，然后将距离最小的两类合并。将类 p G 与 q G 合并为 r G ，则任一类 k G 与 r G 的类间距离公 式为 2.最长距离法 最

7、长距离法 ?再找距离最小两类并类，直至所有的样品全归为一类为止。 可以看出最长距离法与最短距离法只有两点不同： 一是类与类之间的距离定义不同； 另一是计算新类与其它类的距离所用的公式不同。 , max ikjr krij XGXG Dd ? ? , maxmax,max ikjpjikjq ijij XGXGxGxG dd ? ? max, kpkq DD? （4 ） 2.最长距离法 最短、最长距离定义表示都是极端情况，我们定义类间距离 可以既不采用两类之间最近的距离也不采用两类之间最远的 距离，而是采用介于两者之间的距离，称为中间距离法。 中间距离将类G p与Gq类合并为类Gr，则任意的类G

8、k和Gr的距 离公式为 (?14 ? 0) (5) 设DkqDkp，如果采用最短距离法，则Dkr=Dkp，如果采用 最长距离法，则Dkr= Dkq。如图2所示，(5)式就是取它们 （最长距离与最短距离）的中间一点作为计算Dkr的根据。 2222 2 1 2 1 pqkqkpkr DDDD? 3.中间距离法 中间距离法 ?特别当?= ? 14，它表示取中间点算距离，公式为 (6) 222 4 1 2 1 2 1 pqkpkpkr DDDD? 图2 中间距离法 3.中间距离法 4. 重心法重心法 重心法定义类间距离为两类重心（各类样品的均值）的距 离。重心指标对类有很好的代表性，但利用各样本的信息

9、 不充分。 设 p G与 q G分别有样品 p n ， q n 个， 其重心分别为 p X和 q X， 则 p G与 q G之间的距离定义为 p X和 q X之间的距离，这里 我们用欧氏距离来表示，即 2 () () pqpqpq DXXXX? (7) 设将设将 p G 和和 q G 合并为合并为 r G， 则则 r G内样品个数为内样品个数为 qpr nnn? ， 它的重心是它的重心是 )( 1 qqpp r r XnXn n X?，类 k G的重心是的重心是 k X ， 那么依据（那么依据（ 5.175.17）式它与新类）式它与新类 r G的距离为的距离为 2222 2 pqpq krkp

10、kqpq rrr nnn n DDDD nnn ? （8） 这里我们应该注意，这里我们应该注意， 实际上实际上（8） 式表示的类式表示的类 k G 与新类与新类 r G 的的 距离为： 2 () () krkrkr DXXXX? 11 ()() kppqqkppqq rr Xn Xn XXn Xn X nn ? 22 2 22 1 (2) pq kkkpkq rr ppppqpqqqq r nn X XX XX X nn n X Xn n X Xn X X n ? ? 利用利用 1 () kkpkkqkk r X Xn X Xn X X n ? 代入上式，有代入上式，有 2 (2) (2) (

11、2) p krkkkppp r q kkkqqq r pq pppqqq r n DX XX XX X n n X XX XX X n n n X XX XX X n ? ? ? 222 2 pqpq kpkqpq rrr nnn n DDD nnn ? （9） 类平均法定义类间距离平方为这两类元素两两之间距离平方的 平均数，即为 22 1 ipjj pqij XGXG pq Dd n n ? ? ? ? (10) 设聚类的某一步将 p G 和 q G 合并为 r G，则任一类类 k G与 r G的 距离为： 22 1 ikjr krij XG XG kr Dd nn ? ? ? ? 22 1

12、 () ikjpikjq ijij XG XGXG XG kr dd nn ? ? ? ? ? 22 pq kpkq rr nn DD nn ? （11） 类平均法的聚类过程与上述方法完全类似，这里就不在详述了。 5. 类平均法类平均法 6.可变类平均法 可变类平均法 由于类平均法中没有反映出Gp和Gq之间的距离Dpq的影响， 因此将类平均法进一步推广，如果将Gp和Gq合并为新类Gr， 类Gk与新并类Gr的距离公式为： （12） 其中?是可变的且? 1，称这种系统聚类法为可变类平均法。 2222 (1)() pq krkpkqpq rr nn DDDD nn ? 针对于中间法而言，如果将中间法

13、的前两项的系数也依赖 于?，那么，如果将 p G 和 q G 合并为新类 r G，类 k G 与新 并类 r G 的距离公式为： 2222 1 () 2 krkpkqpq DDDD ? ? ? ? （13） 其中?是可变的，且1?。显然在可变类平均法中取 1 2 pq rr nn nn ?， 即为可变法。可变类平均法与可变法的分类 效果与 ? 的选择关系很大，在实际应用中 ? 常取负值。 7.可变法 法 该方法是Ward提出来的，所以又称为Ward法。该方法的基 本思想来自于方差分析，如果分类正确，同类样品的离差平 方和应当较小，类与类的离差平方和较大。具体做法是先将 n个样品各自成一类，然后

14、每次缩小一类，每缩小一类，离 差平方和就要增大，选择使方差增加最小的两类合并，直到 所有的样品归为一类为止。 设将n个样品分成k类G1，G2，Gk，用Xit表示Gt中的第I 个样品，n t表示Gt中样品的个数， 是Gt的重心，则Gt的样品 离差平方和为 1 () () t n tittitt t SXXXX ? ? ? (14) t X 8.离差平方和法 离差平方和法 8.离差平方和法 离差平方和法 如果 p G 和 q G 合并为新类 r G 类内离差平方和分别为 1 () () p n pippipp i SXXXX ? ? ? 1 () () q n qiqqiqq i SXXXX ?

15、? ? 1 () () r n rirrirr i SXXXX ? ? ? 8.离差平方和法 ? ?这种系统聚类法称为离差平方和法或Ward方法。下面论证 离差平方和法的距离递推（16）式。 它们反映了各自类内样品的分散程度，如果 p G 和 q G 这两类 相距较近，则合并后所增加的离散平方和 rpq SSS? 应较 小；否则，应较大。于是定义 p G 和 q G 之间的平方距离为： 2 pqrpq DSSS? (15) 其中 rpq GGG? ，可以证明类间距离的递推公式为 2222 kpkq k krkpkqpq rkrkrk nnnn n DDDD nnnnnn ? ? ? (5.26

16、) 8.离差平方和法 离差平方和法 ?由于 1 () () r n rirrirr i SXXXX ? ? ? 1 () () r n irpprirppr i XXXXXXXX ? ? ? 11 11 () ()() () () ()() () rr rr nn irpirpirppr ii nn prirpprpr ii XXXXXXXX XXXXXXXX ? ? ? ? ? ? 11 1 () ()() () 2()()() () pq r nn ippippiqpiqp ii n prirprprpr i XXXXXXXX XXXXn XXXX ? ? ? ? ? ? 1 () ()

17、() () q n piqqqpiqqqp i rprpr SXXXXXXXX n XXXX ? ? ? ? 1 () ()() () () () q n piqqiqqqpqpq i ppqqppqq rpp rr SXXXXn XXXX n Xn Xn Xn X n XX nn ? ? ? ? ? 2 () ()() () p pqqpqpqpqpq r n SSn XXXXXXXX n ? () ()() () qp pqqpqpqpqpq r nn SSn XXXXXXXX n ? 8.离差平方和法 离差平方和法 ?从而，由（5.25）式知 2 ()() qp pqpqpq r nn

18、DXXXX n ? （5.27） 那么，由（5.27）式和（5.19）式，可以得到离差平方和法的平 方距离的递推公式为： 2 () () rk krrkrk rk nn DXXXX nn ? ? 2 () () () ()() () p rk kpkp rkr qpq kqkqpqpq rr n nn XXXX nnn nn n XXXXXXXX nn ? ? ? ? ? ? ? ? ? 8.离差平方和法 离差平方和法 () () () () () () kpkp kpkp rkpk kqkq kqkq rkqk pq k pqpq rkr nnn n XXXX nnnn nnn n XXXX nnnn n n n XXXX nnn ? ? ? ? ? ? ? ? 222 kp