系统聚类法 |
您所在的位置：网站首页 › 系统聚类模型的特点 › 系统聚类法 |
系统聚类法
 （2017-04-17 银河统计）
聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计方法，也是数据挖掘技术的基本方法。所谓类，通俗地说，就是指相似元素的集合。聚类分析起源于分类学，在考古的分类学中，人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展，人类的认识不断加深，分类越来越细，要求也越来越高，有时光凭经验和专业知识是不能进行确切分类的，往往需要定性和定量分析结合起来去分类，于是数学工具逐渐被引进分类学中，形成了数值分类学。后来随着多元分析的引进，聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。 聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。这里介绍常用的系统聚类法。 正如样本之间的距离可以有不同的定义方法一样（欧氏距离、曼哈顿距离、马氏距离等），类与类之间的距离也有各种定义。例如可以定义类与类之间的距离为两类之间最近样本的距离，或者定义为两类之间最远样本的距离，也可以定义为两类重心之间的距离等等。类与类之间用不同的方法定义距离，就产生了不同的系统聚类方法。常用的八种系统聚类方法，即最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法、离差平方和法。系统聚类分析尽管方法很多，但归类的步骤基本上是一样的，所不同的仅是类与类之间的距离有不同的定义方法，从而得到不同的计算距离的公式。 一、系统聚类分析涉及的基本问题 现有10名学生六门课程成绩样本表（附表I）如下： 样本（学生）概率论统计学英语政治数据挖掘线性代数 $S_1$676373754491 $S_2$746966948155 $S_3$769393797127 $S_4$653885856145 $S_5$803948754152 $S_6$728070888643 $S_7$605091954264 $S_8$774969508955 $S_9$658950709985 $S_{10}$7841558971281、样本间距离及距离矩阵 以欧氏距离为例，样本\(S_1\)和\(S_3\)之间的距离\(D_{13}\)的距离为， \[D_{13}=\sqrt{(76-67)^2+(93-63)^2+(93-73)^2+(79-75)^2+(71-44)^2+(27-91)^2}\approx 78.88 \]样本\(S_i\)和\(S_j\)之间的距离\(D_{ij}\)的距离构成的矩阵表（附表II）为， $D_{ij}$$S_1$$S_2$$S_3$$S_4$$S_5$$S_6$$S_7$$S_8$$S_9$$S_{10}$ $S_1$056.2178.8857.2553.8567.5340.9365.2565.5476.31 $S_2$56.21049.1744.5456.8318.6052.7749.1750.3742.13 $S_3$78.8849.17060.5880.6135.7267.6466.8078.8465.22 $S_4$57.2544.5460.58046.3051.7332.0551.2884.2338.51 $S_5$53.8556.8380.6146.30067.1153.9959.0684.8941.58 $S_6$67.5318.6035.7251.7367.11062.5450.8352.7947.26 $S_7$40.9352.7767.6432.0553.9962.54071.3486.8562.24 $S_8$65.2549.1766.8051.2859.0650.8371.34059.2053.25 $S_9$65.5450.3778.8484.2384.8952.7986.8559.20083.02 $S_{10}$76.3142.1365.2238.5141.5847.2662.2453.2583.0202、按样本间距离矩阵最小距离聚类 样本间距离矩阵为对称矩阵，即\(D_{ij}=D_{ji}\)，并且对角线距离为0，即\(D_{ii}=0\)。所以，样本间距离矩阵最小距离只在下三角矩阵中寻找即可。表中\(D_{26}=18.60\)为最小距离，说明样本\(S_2\)和\(S_6\)相似性最大，可以首先归为同一类。把样本\(S_2\)和\(S_6\)做为新类，计算新类和其它类距离，然后在降维距离矩阵中选择最小距离、再归类，直至把所有样本归为一类。 3、类与类之间的距离 我们可以把每个样本看成一个类，也可以把具有某种共同特征的几个样本分为一类，如按距离最小将样本\(S_2\)和\(S_6\)归为一类。当按某种距离公式（如欧氏距离）计算出两两样本间距离矩阵后，在距离矩阵基础上，多个样本和一个样本、或多个样本和多个样本之间的距离称为类与类之间的距离。 如果把样本\(S_2\)和\(S_6\)分为一类、即\(C_1\{S_2,S_6\}\)，再把样本\(S_7\)、\(S_8\)和\(S_9\)分为一类、即\(C_2\{S_7,S_8,S_9\}\)。\(C_1\)和\(C_2\)之间的距离称为类间距离。 二、系统聚类方法 为了分析问题简便，将5名学生3门课程成绩样本（附表III）进行系统聚类分析。样本数据为， 样本（学生）概率论统计学英语 $S_1$676373 $S_2$746966 $S_3$769393 $S_4$653885 $S_5$803948样本\(S_i\)和\(S_j\)之间的距离\(D_{ij}\)的距离构成的矩阵表（附表IV）为， $D_{ij}$$S_1$$S_2$$S_3$$S_4$$S_5$ $S_1$ $S_2$56.21 $S_3$78.8849.17 $S_4$57.2544.5460.58 $S_5$53.8556.8380.6146.301、最短距离法 根据距离矩阵（附表IV），按距离最小（最小距离44.54）将样本\(S_2\)和\(S_4\)归为一类\(C_1\)。在矩阵表中将\(C_1\)设置为第1行第1列，划去\(S_2\)、\(S_4\)对应行列，并计算\(C_1\)和其它样本或类之间的最短距离，得矩阵表如下， $D_{ij}$$C_1(2,4)$$S_1$$S_3$$S_5$ $C_1(2,4)$ $S_1$56.21 $S_3$49.1778.88 $S_5$46.3053.8580.61表中类\(C_1\)和样本\(S_1\)之间的最短距离为，\(min\{D_{12},D_{14}\}=min\{56.21,57.25\}=56.21\)，\(C_1\)和其它样本之间的最短距离同理。 现在距离矩阵中\(C_1\)和\(S_5\)最小距离为46.30，将两样本聚类为\(C_2(2,4,5)\)，在矩阵表中将\(C_2\)设置为第1行第1列，划去\(C_1\)、\(S_5\)对应行列，并计算\(C_2\)和其它样本或类之间的最短距离，得矩阵表如下， $D_{ij}$$C_2(2,4,5)$$S_1$$S_3$ $C_2(2,4,5)$ $S_1$53.85 $S_3$49.1778.88表中\(C_2(2,4,5)\)和\(S_1\)最短距离为，\(min\{D_{12},D_{14},D_{15}\}=min\{56.21.57.25,53.85\}=53.85\)。 按最小距离49.17将\(C_2(2,4,5)\)、\(S_3\)聚类为\(C_3(2,3,4,5)\)， $D_{ij}$$C_3(2,3,4,5)$$S_1$ $C_3(2,3,4,5)$ $S_1$53.85表中\(C_3(2,3,4,5)\)和\(S_1\)最短距离为，\(min\{D_{12},D_{13},D_{14},D_{15}\}=min\{56.21,78.88,57.25,53.85\}=53.85\)。 最后，\(C_3(2,3,4,5)\)和\(S_1\)聚为一类。 上述并类过程可用下图表达, 
2、最长距离法 最长距离和最短距离方法的唯一区别是取类间各样本距离集合的最大值。例如，类\(C_1(S_2,S_6)\)和\(C_2(S_8,S_9,S_{10})\)之间的距离矩阵为， $D_{ij}$$S_8$$S_9$$S_{10}$ $S_2$49.1750.3742.13 $S_6$50.8352.7947.26距离矩阵中最大距离为52.79，最小距离为42.13。运用最短距离法取最短距离42.13，而用最长距离法则取最大距离52.79。 根据距离矩阵（附表IV），按距离最小（最小距离44.54）将样本\(S_2\)和\(S_4\)归为一类\(C_1\)。在矩阵表中将\(C_1\)设置为第1行第1列，划去\(S_2\)、\(S_4\)对应行列，并计算\(C_1\)和其它样本或类之间的最长距离，得矩阵表如下， $D_{ij}$$C_1(2,4)$$S_1$$S_3$$S_5$ $C_1(2,4)$ $S_1$57.25 $S_3$60.5878.88 $S_5$56.8353.8580.61类\(C_1\)和样本\(S_1\)之间的最长距离为，\(max\{D_{12},D_{14}\}=max\{56.21,57.25\}=57.25\)，\(C_1\)。其它样本之间的最长距离同理。 按最小距离53.85将\(S_1\)、\(S_5\)聚类为\(C_2(1,5)\)， $D_{ij}$$C_2(1,5)$$C_1(2,4)$$S_3$ $C_2(1,5)$ $C_1(2,4)$57.25 $S_3$80.6160.58类\(C_2\)和类\(C_1\)之间的最长距离为，\(max\{D_{12},D_{14},D_{52},D_{54}\}=max\{56.21,57.25,56.83,46.30\}=57.25\)。\(C_2\)和\(S_3\)最长距离为，\(max\{D_{31},D_{35}\}=max\{78.88,80.61\}=80.61\)。 按最小距离57.25将\(C_1\)、\(C_2\)聚类为\(C_3(1,2,4,5)\)， $D_{ij}$$C_3(1,2,4,5)$$S_3$ $C_3(1,2,4,5)$ $S_3$80.61上述并类过程可用下图表达, 
3、中间距离法 类间中间距离采用“二和一”方式逐渐包含不同数量样本的类合为一类（这里为类\(G_r\)）。如果在某一步将类\(G_p\)与类\(G_q\)合并为\(G_r\)，任一类\(G_k\)和\(G_r\)的中间距离公式为： \[D_{kr}=\sqrt{\frac{D_{kp}^2}{2}+\frac{D_{kq}^2}{2}+\beta\times D_{pq}^2}\hspace{1cm}-\frac{1}{4}\leq\beta\leq 0 \]例如，设\(\beta=-\frac{1}{4}\)，样本\(S_2\)和\(S_6\)为一类\(C_r\)，和样本\(S_7\)的中间距离为， \[D_{7r}=\sqrt{\frac{D_{27}^2}{2}+\frac{D_{67}^2}{2}-\frac{D_{26}^2}{4}}=\sqrt{\frac{52.77^2}{2}+\frac{62.54^2}{2}-\frac{18.60^2}{4}}=57.11 \]
当\(\beta=-\frac{1}{4}\)时，由初等几何知\(D_{kr}\)就是上面三角形的中线。由于中间距离公式中的量都是距离的平方，为了计算方便，可将距离矩阵（附表IV）各距离换算为平方。转换后距离矩阵如下， $D_{ij}$$S_1$$S_2$$S_3$$S_4$$S_5$ $S_1$ $S_2$3159.56 $S_3$6222.052417.69 $S_4$3277.561983.813669.94 $S_5$2899.823229.656497.972143.69按距离最小（最小距离平方为1983.81）将样本\(S_2\)和\(S_4\)归为一类\(C_r\)。在矩阵表中将\(C_r\)设置为第1行第1列，划去\(S_2\)、\(S_4\)对应行列，并计算\(C_r\)和其它样本或类之间的中间距离，得矩阵表如下， $D_{ij}$$C_r(2,4)$$S_1$$S_3$$S_5$ $C_r(2,4)$ $S_1$2722.61 $S_3$2547.866222.05 $S_5$2190.722899.826497.97表中，按中间距离公式， \[D_{1r}^2=\frac{D_{12}^2}{2}+\frac{D_{14}^2}{2}-\frac{D_{24}^2}{4}=\frac{3159.56}{2}+\frac{3277.56}{2}-\frac{1983.81}{4}=2722.61 \]\[D_{3r}^2=\frac{D_{32}^2}{2}+\frac{D_{34}^2}{2}-\frac{D_{24}^2}{4}=\frac{2417.69}{2}+\frac{3669.94}{2}-\frac{1983.81}{4}=2547.86 \]\[D_{5r}^2=\frac{D_{52}^2}{2}+\frac{D_{54}^2}{2}-\frac{D_{24}^2}{4}=\frac{3229.65}{2}+\frac{2143.69}{2}-\frac{1983.81}{4}=2190.72 \]按最小距离平方2190.72将\(C_r(2,4)\)、\(S_5\)聚类为\(C_s(2,4,5)\)， $D_{ij}$$C_s(2,4,5)$$S_1$$S_3$ $C_r(2,4,5)$ $S_1$2263.54 $S_3$3975.246222.05表中，按中间距离公式， \[D_{1s}^2=\frac{D_{1r}^2}{2}+\frac{D_{15}^2}{2}-\frac{D_{5r}^2}{4}=\frac{2722.61}{2}+\frac{2899.82}{2}-\frac{2190.72}{4}=2263.54 \]\[D_{3s}^2=\frac{D_{3r}^2}{2}+\frac{D_{35}^2}{2}-\frac{D_{5r}^2}{4}=\frac{2547.86}{2}+\frac{6497.97}{2}-\frac{2190.72}{4}=3975.24 \]按最小距离平方2263.54将\(C_s(2,4,5)\)、\(S_1\)聚类为\(C_t(1,2,4,5)\)， $D_{ij}$$C_t(1,2,4,5)$$S_3$ $C_t(1,2,4,5)$ $S_3$6222.05上述并类过程可用下图表达, 
4、重心法 根据（附表I）数据，利用重心法计算类\(C_1\{S_2,S_6\}\)和\(C_2\{S_8,S_9,S_{10}\}\)之间的距离，只需计算出各个类的重心坐标，然后计算重心坐标的欧氏距离或其它距离。 样本\(S_2(74,69,66,94,81,55)\)和\(S_6(72,80,70,88,86,43)\)的重心为， \[\overline{S}_r=(\frac{74+72}{2},\frac{69+80}{2},\frac{66+70}{2},\frac{94+88}{2},\frac{81+86}{2},\frac{55+43}{2})=(73,74.5,68,91,83.5,49) \]样本\(S_8(77,49,69,50,89,55)\)、\(S_9(65,89,50,70,99,85)\)和\(S_{10}(78,41,55,89,71,28)\)的重心为， \[\overline{S}_s=(\frac{77+65+78}{3},\frac{49+89+41}{3},\frac{69+50+55}{3},\frac{50+70+89}{3},\frac{89+99+71}{3},\frac{55+85+28}{3})=(73.33,59.67,58,69.67,83.33,56) \]两个重心之间的欧氏距离为， \[\small{\overline{D}_{rs}=\sqrt{(73-73.33)^2+(74.5-59.67)^2+(68-58)^2+(91-69.67)^2+(83.5-83.33)^2+(49-56)^2}=28.706} \]根据距离矩阵（附表IV），按距离最小（最小距离44.54）将样本\(S_2\)和\(S_4\)归为一类\(C_r\)。在矩阵表中将\(C_r\)设置为第1行第1列，划去\(S_2\)、\(S_4\)对应行列，并计算\(C_r\)和其它样本或类之间的重心距离，得矩阵表如下， $D_{ij}$$C_r(2,4)$$S_1$$S_3$$S_5$ $C_r(2,4)$ $S_1$10.14 $S_3$43.6978.88 $S_5$32.8153.8580.61表中，类\(C_r\)的重心坐标为， \[(\frac{74+65}{2},\frac{69+38}{2},\frac{66+85}{2})=(69.5,53.5,75.5) \]类\(C_r\)重心和样本\(S_1\)之间的欧氏距离为， \[\overline{D}_{1r}=\sqrt{(69.5-67)^2+(53.5-63)^2+(75.5-73)^2}=10.14 \]和其它样本之间的重心距离同理。 按最小距离10.14将\(C_r(2,4)\)、\(S_1\)聚类为\(C_s(1,2,4)\)， $D_{ij}$$C_s(1,2,4)$$S_3$$S_5$ $C_s(1,2,4)$ $S_3$41.35 $S_5$33.9480.61表中，类\(C_s\)的重心坐标为， \[(\frac{74+65+67}{3},\frac{69+38+63}{3},\frac{66+85+73}{3})=(68.67,56.67,74.67) \]类\(C_s\)和样本\(S_3\)、\(S_5\)之间重心的欧氏距离为， \[\overline{D}_{3s}=\sqrt{(68.67-76)^2+(56.67-93)^2+(74.67-93)^2}=41.35 \]\[\overline{D}_{5s}=\sqrt{(68.67-80)^2+(56.67-39)^2+(74.67-48)^2}=33.94 \]按最小距离33.94将\(C_s(1,2,4)\)、\(S_5\)聚类为\(C_t(1,2,4,5)\)， $D_{ij}$$C_t(1,2,4,5)$$S_3$ $C_t(1,2,4,5)$ $S_3$41.35上述并类过程可用下图表达, 
如果最初样品之间的距离采用欧氏距离，重心法聚类到某一步， 类\(G_p\)和\(G_q\)分别有样本\(n_{_p}\)和\(n_{_q}\)个，将\(G_p\)和\(G_q\)合并为\(G_r\)，则\(G_r\)内样本个数为\(n_{_r}=n_{_p}+n_{_q}\)，某一类\(n_{_k}\)与新类\(G_r\)的距离为， \[D_{kr}=\sqrt{\frac{n_{_p}}{n_{_r}}D_{kp}^2+\frac{n_{_q}}{n_{_r}}D_{kq}^2-\frac{n_{_p}}{n_{_r}}\frac{n_{_q}}{n_{_r}}D_{pq}^2} \]5、类平均法 当聚类到某一步时，类\(G_p\)和\(G_q\)分别有样本\(n_{_p}\)和\(n_{_q}\)个，将\(G_p\)和\(G_q\)合并为\(G_r\)，则\(G_r\)内样本个数为\(n_{_r}=n_{_p}+n_{_q}\)，某一类\(n_{_k}\)与新类\(G_r\)的类平均距离公式为， \[D_{kr}=\sqrt{\frac{n_{_p}}{n_{_r}}D_{kp}^2+\frac{n_{_q}}{n_{_r}}D_{kq}^2} \]根据距离矩阵（附表IV），按距离最小（最小距离44.54）将样本\(S_2\)和\(S_4\)归为一类\(C_r\)。在矩阵表中将\(C_r\)设置为第1行第1列，划去\(S_2\)、\(S_4\)对应行列，并计算\(C_r\)和其它样本或类之间的类平均距离，得矩阵表如下， $D_{ij}$$C_r(2,4)$$S_1$$S_3$$S_5$ $C_r(2,4)$ $S_1$56.73 $S_3$55.1578.88 $S_5$51.8353.8580.61表中，由类平均距离公式， \[D_{1r}=\sqrt{\frac{D_{12}^2}{2}+\frac{D_{14}^2}{2}}=\sqrt{\frac{56.21^2}{2}+\frac{57.25^2}{2}}=56.73 \]\[D_{3r}=\sqrt{\frac{D_{32}^2}{2}+\frac{D_{34}^2}{2}}=\sqrt{\frac{49.17^2}{2}+\frac{60.58^2}{2}}=55.15 \]\[D_{5r}=\sqrt{\frac{D_{52}^2}{2}+\frac{D_{54}^2}{2}}=\sqrt{\frac{56.83^2}{2}+\frac{46.30^2}{2}}=51.83 \]按最小距离51.83将\(C_r(2,4)\)、\(S_5\)聚类为\(C_s(2,4,5)\)， $D_{ij}$$C_s(2,4,5)$$S_1$$S_3$ $C_s(2,4,5)$ $S_1$55.79 $S_3$64.7678.88表中， \[D_{1s}=\sqrt{\frac{2D_{1r}^2}{3}+\frac{D_{15}^2}{3}}=\sqrt{2\times\frac{56.73^2}{3}+\frac{53.85^2}{3}}=55.79 \]\[D_{3s}=\sqrt{\frac{2D_{3r}^2}{3}+\frac{D_{35}^2}{3}}=\sqrt{2\times\frac{55.15^2}{3}+\frac{80.61^2}{3}}=64.76 \]按最小距离55.79将\(C_s(2,4,5)\)、\(S_1\)聚类为\(C_t(1,2,4,5)\)， $D_{ij}$$C_t(1,2,4,5)$$S_3$ $C_t(1,2,4,5)$ $S_3$78.88上述并类过程可用下图表达, 
6、可变类平均法 由于类平均法公式中没有反映\(G_p\)和\(G_q\)之间距离\(D_{pq}\)的影响，所以给出可变类平均法。此法定义两类之间的距离同上，只是将任一类\(G_k\)与新类\(G_r\)的距离改为如下形式： \[D_{kr}=\sqrt{\frac{n_{_p}}{n_{_r}}(1-\beta)D_{kp}^2+\frac{n_{_q}}{n_{_r}}(1-\beta)D_{kq}^2+\beta D_{pq}} \]其中\(\beta\)是可变的且\(\beta |
【本文地址】