聚类分析简单例子

一、系统聚类的基本思想系统聚类的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。系统聚类过程是：假设总共有n个样品（或变量），第一步将每个样品（或变量）独自聚成一类，共有n类；第二步根据所确定的样品（或变量）“距离”公式，把距离较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类，共聚成n1类；第三步将“距离”最近的两个类进一步聚成一类，共聚成n2类；……，以上步骤一直进行下去，最后将所有的样品（或变量）全聚成一类。为了直观地反映以上的系统聚类过程，可以把整个分类系统画成一张谱系图。所以有时系统聚类也称为谱系分析。除系统聚类法外，还有有序聚类法、动态聚类法、图论聚类法、模糊聚类法等，限于篇幅，我们只介绍系统聚类方法。二、类间距离与系统聚类法在进行系统聚类之前，我们首先要定义类与类之间的距离，由类间距离定义的不同产生了不同的系统聚类法。常用的类间距离定义有8种之多，与之相应的系统聚类法也有8种，分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法。它们的归类步骤基本上是一致的，主要差异是类间距离的计算方法不同。以下用dij表示样品Xi与Xj之间距离，用Dij表示类Gi与Gj之间的距离。1.最短距离法定义类Gi与Gj之间的距离为两类最近样品的距离，即为(5.11)设Gk类与合并成一个新类记为Gr，则任一类与的距离为(5.12)ijGXGXijdDjjii,min,minikjrkrijXGXGDd,,min{min,min}ikjpikjqijijXGXGxGxGddmin{,}kpkqDD最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离阵记为D（0），开始每个样品自成一类，显然这时Dij=dij。（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，即Gr=｛Gp，Gq｝。（3）按（5.12）计算新类与其它类的距离。（4）重复（2）、（3）两步，直到所有元素。并成一类为止。如果某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并。【例5.1】设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。（1）样品采用绝对值距离，计算样品间的距离阵D（0），见表5.1G1G2G3G4G5G6G10G210G3430G46520G587420G6985310表5.1（2）D（0）中最小的元素是D12＝D56＝1，于是将G1和G2合并成G7，G5和G6合并成G8，并利用（5.12）式计算新类与其它类的距离D（1），见表5.2G7G3G4G8G70G330G4520G87420表5.2（3）在D（1）中最小值是D34＝D48＝2，由于G4与G3合并，又与G8合并，因此G3、G4、G8合并成一个新类G9，其与其它类的距离D（2），见表5.3G7G9G70G930表5.3（4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程终止。上述聚类的可视化过程见图5.1所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。图5.1最短距离聚类法的过程2.最长距离法定义类iG与jG之间的距离为两类最远样品的距离，即为,maxipjqpqijXGXGDd(5.13)最长距离法与最短距离法的并类步骤完全一样，也是将各样品先自成一类，然后将距离最小的两类合并。将类pG与qG合并为rG，则任一类kG与rG的类间距离公式为再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；另一是计算新类与其它类的距离所用的公式不同。,maxikjrkrijXGXGDd,,max{max,max}ikjpjikjqijijXGXGxGxGddmax{,}kpkqDD（5.14）3.中间距离法最短、最长距离定义表示都是极端情况，我们定义类间距离可以既不采用两类之间最近的距离也不采用两类之间最远的距离，而是采用介于两者之间的距离，称为中间距离法。中间距离将类Gp与Gq类合并为类Gr，则任意的类Gk和Gr的距离公式为(1／40)(5.15)设Dkr＞Dkp，如果采用最短距离法，则Dkr=Dkp，如果采用最长距离法，则Dkr=Dkq。如图5.2所示，(5.15)式就是取它们（最长距离与最短距离）的中间一点作为计算Dkr的根据。22222121pqkqkpkrDDDD特别当=1／4，它表示取中间点算距离，公式为(5.16)222412121pqkpkpkrDDDD图5.2中间距离法4.重心法重心法定义类间距离为两类重心（各类样品的均值）的距离。重心指标对类有很好的代表性，但利用各样本的信息不充分。设pG与qG分别有样品pn，qn个，其重心分别为pX和qX，则pG与qG之间的距离定义为pX和qX之间的距离，这里我们用欧氏距离来表示，即2()()pqpqpqDXXXX(5.17)设将pG和qG合并为rG，则rG内样品个数为qprnnn，它的重心是)(1qqpprrXnXnnX，类kG的重心是kX，那么依据（5.17）式它与新类rG的距离为22222pqpqkrkpkqpqrrrnnnnDDDDnnn（5.18）这里我们应该注意，实际上（5.18）式表示的类kG与新类rG的距离为：2()()krkrkrDXXXX11[()][()]kppqqkppqqrrXnXnXXnXnXnn222221(2)pqkkkpkqrrppppqpqqqqrnnXXXXXXnnnXXnnXXnXXn利用1()kkpkkqkkrXXnXXnXXn代入上式，有2(2)(2)(2)pkrkkkppprqkkkqqqrpqpppqqqrnDXXXXXXnnXXXXXXnnnXXXXXXn2222pqpqkpkqpqrrrnnnnDDDnnn（5.19）【例5.2】针对例5.1的数据，试用重心法将它们聚类。（1）样品采用欧氏距离，计算样品间的平方距离阵D2（0），见表5.4所示。G1G2G3G4G5G6G10G210G31690G4362540G564491640G6816425910表5.4（2）D2（0）中最小的元素是D212＝D256＝1，于是将G1和G2合并成G7，G5和G6合并成G8，并利用（5.18）式计算新类与其它类的距离得到距离阵D2（1），见表5.5：其中，其它结果类似可以求得G7G4G4G8G70G312.250G430.2540G86420.256.250222237313212111122221111169112.252222DDDD（3）在D2（1）中最小值是D234＝4，那么G3与G4合并一个新类G9，其与与其它类的距离D2（2），见表5.6：G7G9G8G70G920.250G86412.50表5.6（4）在中最小值是＝12.5，那么与合并一个新类，其与与其它类的距离，见表5.7：G7G10G70G1039.06250表5.7（5）最后将G7和G10合并成G11，这时所有的六个样品聚为一类，其过程终止。上述重心法聚类的可视化过程见图5.3所示，横坐标的刻度表示并类的距离。图5.3重心聚类法的过程5．类平均法类平均法定义类间距离平方为这两类元素两两之间距离平方的平均数，即为221ipjjpqijXGXGpqDdnn(5.20)设聚类的某一步将pG和qG合并为rG，则任一类类kG与rG的距离为：221ikjrkrijXGXGkrDdnn221()ikjpikjqijijXGXGXGXGkrddnn22pqkpkqrrnnDDnn（5.21）类平均法的聚类过程与上述方法完全类似，这里就不在详述了。6.可变类平均法由于类平均法中没有反映出Gp和Gq之间的距离Dpq的影响，因此将类平均法进一步推广，如果将Gp和Gq合并为新类Gr，类Gk与新并类Gr的距离公式为：（5.22）其中是可变的且1，称这种系统聚类法为可变类平均法。2222(1)()pqkrkpkqpqrrnnDDDDnn7．可变法针对于中间法而言，如果将中间法的前两项的系数也依赖于，那么，如果将pG和qG合并为新类rG，类kG与新并类rG的距离公式为：22221()2krkpkqpqDDDD（5.23）其中是可变的，且1。显然在可变类平均法中取12pqrrnnnn，即为可变法。可变类平均法与可变法的分类效果与的选择关系很大，在实际应用中常取负值。8.离差平方和法该方法是Ward提出来的，所以又称为Ward法。该方法的基本思想来自于方差分析，如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。设将n个样品分成k类G1，G2，…，Gk，用Xit表示Gt中的第I个样品，nt表示Gt中样品的个数，是Gt的重心，则Gt的样品离差平方和为1()()tntittitttSXXXX(5.24)tX如果pG和qG合并为新类rG类内离差平方和分别为1()()pnpippippiSXXXX1()()qnqiqqiqqiSXXXX1()()rnrirrirriSXXXX这种系统聚类法称为离差平方和法或Ward方法。下面论证离差平方和法的距离递推（5.26）式。它们反映了各自类内样品的分散程度，如果pG和qG这两类相距较近，则合并后所增加的离散平方和rpqSSS应较小；否则，应较大。于是定义pG和qG之间的平方距离为：2pqrpqDSSS(5.25)其中rpqGGG，可以证明类间距离的递推公式为2222kpkqkkrkpkqpqrkrkrknnnnnDDDDnnnnnn(5.26)由于1()()rnrirrirriSXXXX1()()rnirpprirppriXXXXXXXX1111()()()()()()()()rrrrnnirpirpirppriinnprirpprpriiXXXXXXXXXXXXXXXX111()()()()2()()()()pqrnnippippiqpiqpiinprirprprpriXXXXXXXXXXXXnXXXX1()()()()qnpiqqqpiqqqpirprprSXXXXXXXXnXXXX1()()()()()()qnpiqqiqqqpqpqippqqppqqrpprrSXXXXnXXXXnXnXnXnXnXXnn2()()()()ppqqpqpqpqpqrnSSnXXXXXXXXn()()()()qppqqpqpqpqpqrnnSSnXXXXXXXXn从而，由（5.25）式知2()()qppqpqpqrnnDXXXXn（5.27）那么，由（5.27）式和（5.19）式，可以得到离差平方和法的平方距离的递推公式为：2()()rkkrrkrkrknnDXXXXnn2()()()()()()prkkpkprkrqpqkqkqpqpqrrnnnXXXXnnnnnnXXXXXXXXnn()()()()()()kp