1、聚类分析聚类分析洪金益洪金益中南大学地学院中南大学地学院地质数据处理基础11第十一章 聚类分析1 引言2 距离和相似系数3 系统聚类法4 动态聚类法 1 引言 判别分析和聚类分析是两种不同目的的分类方法，它们所起的作用是不同的。 判别分析方法假定组（或类）已事先分好，判别新样品应归属哪一组，对组的事先划分有时也可以通过聚类分析得到。 聚类分析：将分类对象分成若干类，相似的归为同一类，不相似的归为不同的类。 聚类分析分为Q型（分类对象为样品）和R型（分类对象为变量）两种。相似性的不同定义2 距离和相似系数 相似性度量：距离和相似系数。 距离常用来度量样品之间的相似性，相似系数常用来度量变量之间的
2、相似性。 样品之间的距离和相似系数有着各种不同的定义，而这些定义与变量的类型有着非常密切的关系。变量的测量尺度 通常变量按测量尺度的不同可以分为间隔、有序和名义尺度变量三类。间隔尺度变量：变量用连续的量来表示，如长度、重量、速度、温度等。有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如某产品分为一等品、二等品、三等品等有次序关系。名义尺度变量：变量用一些类表示，这些类之间既无等级关系也无数量关系，如性别、职业、产品的型号等。一、距离 设xij为第i个样品的第j个指标，数据矩阵列于表。变 量x1x2xp样 品1x11x12x1p2x21x22x2pnxn1xn2xnp 数 据 矩
3、 阵距离dij一般应满足的四个条件 (i) dij0，对一切i,j； (ii) dij=0，当且仅当第i个样品与第j个样品的各变量值相同； (iii) dij=dji，对一切i,j； (iv) dijdik+dkj，对一切i,j,k。常用的距离 1.明考夫斯基(Minkowski)距离 2.兰氏(Lance和Williams)距离 3.马氏(Mahalanobis)距离 4.斜交空间距离1.明考夫斯基距离 第i个样品与第j个样品间的明考夫斯基距离（简称明氏距离）定义为这里q为某一自然数。明氏距离有以下三种特殊形式： （i）当q=1时， ，称为绝对值距离，常被形象地称作“城市街区”距离； （ii
4、）当q=2时， ，称为欧氏距离，这是聚类分析中最常用的一个距离； （iii）当q=时， ，称为切比雪夫距离。 11qpqijikjkkdqxx 11pijikjkkdxx 1 2212pijikjkkdxx 1maxijikjkkpdxx 绝对值距离图示对各变量的数据作标准化处理 当各变量的单位不同或测量值范围相差很大时，应先对各变量的数据作标准化处理。最常用的标准化处理是，令 其中 和 分别为第j个变量的样本均值和样本方差。*,1,2, ,1,2,ijjijjjxxxinjps11njijixxn2111njjijjisxxn2.兰氏距离 当xji0，j=1,2, ,n，i=1,2, ,p时
5、，可以定义第i个样品与第j个样品间的兰氏距离为 这个距离与各变量的单位无关。由于它对大的异常值不敏感，故适用于高度偏斜的数据。 明氏距离和兰氏距离都没有考虑变量间的相关性，因此这两种距离更适合各变量之间互不相关的情形。 1pikjkijkikjkxxdLxx3.马氏距离 第i个样品与第j个样品间的马氏距离为其中xi=(xi1,xi2, ,xip)，xj=(xj1,xj2, ,xjp)，S为样本协方差矩阵。 使用马氏距离的好处是考虑到了各变量之间的相关性，并且与各变量的单位无关。但马氏距离有一个很大的缺陷，就是马氏距离公式中的S难以确定。没有关于不同类的先验知识，S就无法计算。因此，在实际聚类分
6、析中，马氏距离不是理想的距离。1i jijijdMxxSxx名义尺度变量的一种距离定义 例 某高校从学员的资料中得到这样六个变量：性别(x1)，取值为男和女；外语语种(x2)，取值为英、日和俄；专业(x3)，取值为统计、会计和金融；职业(x4)，取值为教师和非教师；居住处(x5)，取值为校内和校外；学历(x6)，取值为本科和本科以下。 现有两名学员：x1=（男，英，统计，非教师，校外，本科）x2=（女，英，金融，教师，校外，本科以下） 这两名学员的第二个变量都取值“英”，称为配合的，第一个变量一个取值为“男”，另一个取值为“女”，称为不配合的。一般地，若记配合的变量数为m1，不配合的变量数为m
7、2，则它们之间的距离可定义为 故按此定义本例中x1 与x2 之间的距离为2/3。21212mdmm二、相似系数 聚类分析方法不仅用来对样品进行分类，而且可用来对变量进行分类，在对变量进行分类时，常常采用相似系数来度量变量之间的相似性。 变量之间的这种相似性度量，在一些应用中要看相似系数的大小，而在另一些应用中要看相似系数绝对值的大小。 相似系数（或其绝对值）越大，认为变量之间的相似性程度就越高；反之，则越低。 聚类时，比较相似的变量倾向于归为一类，不太相似的变量归属不同的类。 相似系数一般需满足的条件 (1)cij=1，当且仅当xi=axj+b，a(0) 和b是常数； (2)|cij|1，对一
8、切i,j； (3)cij=cji，对一切i,j。 两个向量的夹角余弦 cosx yx xy y1.夹角余弦 变量xi与xj的夹角余弦定义为它是Rn中变量xi的观测向量(x1i,x2i, ,xni)与变量xj的观测向量(x1j,x2j, ,xnj)之间夹角ij的余弦函数，即cij(1)=cosij。 11 222111nkikjkijnnkikjkkx xcxx2.相关系数 变量xi与xj的相关系数为 如果变量xi与xj是已标准化了的，则它们间的夹角余弦就是相关系数。 11 222112nkiikjjkijnnkiikjjkkxxxxcxxxx 相似系数除常用来度量变量之间的相似性外有时也用来度
9、量样品之间的相似性，同样，距离有时也用来度量变量之间的相似性。 由距离来构造相似系数总是可能的，如令 这里dij为第i个样品与第j个样品的距离，显然cij满足定义相似系数的三个条件，故可作为相似系数。 距离必须满足定义距离的四个条件，所以不是总能由相似系数构造。高尔（Gower）证明，当相似系数矩阵(cij)为非负定时，如令 则dij满足距离定义的四个条件。11ijijcd2 1ijijdc3 系统聚类法 系统聚类法(hierarchical clustering method)是聚类分析诸方法中用得最多的一种。 基本思想是：开始将n个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，
10、然后将距离最近的两类合并成一个新类，计算新类与其他类的距离；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并为一类。 本节介绍的八种系统聚类方法，其区别在于类与类之间距离的计算方法不同。一开始每个样品各自作为一类3 系统聚类法 一、最短距离法 二、最长距离法 三、中间距离法 四、类平均法 五、重心法 六、离差平方和法（Ward方法） 七、系统聚类法的统一 八、类的个数一、最短距离法 定义类与类之间的距离为两类最近样品间的距离，即,minKLKLiji Gj GDd 最短距离法：DKL=d23最短距离法的聚类步骤 (1)规定样品之间的距离，计算n个样品的距离矩阵D(0)，它是一个对称矩
11、阵。 (2)选择D(0)中的最小元素，设为DKL，则将GK和GL合并成一个新类，记为GM，即GM= GKGL。 (3)计算新类GM与任一类GJ之间距离的递推公式为,minminmin, minmin,MJKJLJMJijijiji Gj Gi Gj Gi Gj GKJLJDdddDD递推公式的图示理解最短距离法的聚类步骤 在D(0)中，GK和GL所在的行和列合并成一个新行新列，对应GM ，该行列上的新距离值由（6.3.2）式求得，其余行列上的距离值不变，这样就得到新的距离矩阵，记作D(1) 。 (4)对D(1)重复上述对D(0)的两步得D(2) ，如此下去直至所有元素合并成一类为止。 如果某一
12、步D(m)中最小的元素不止一个，则称此现象为结（tie），对应这些最小元素的类可以任选一对合并或同时合并。最短距离法最容易产生结。 由于最短距离法是用两类之间最近样本点的距离来聚的，因此该方法不适合对分离得很差的群体进行聚类例 设有五个样品，每个测量一个指标，分别是1，2，6，8，11，试用最短距离法将它们分类。记G1=1，G2=2，G3=6，G4=8，G5=11，样品间采用绝对值距离。G1G2G3G4G5G10G210G3540G47620G5109530D(0)D(1)G6G3G4G5G60G340G4620G59530其中G6= G1G2D(2)G6G7G5G60G740G5930其中G
13、7= G3G4D(3)G6G60G84其中G6= G1G2最短距离法树形图二、最长距离法 类与类之间的距离定义为两类最远样品间的距离，即,maxKLKLiji Gj GDd图 最长距离法： DKL=d15 最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。 递推公式：max,MJKJLJDDD 对采用最长距离法，其树形图如图6.3.4所示，它与上图有相似的形状，但并类的距离要比上图大一些，仍分成两类为宜。图 最长距离法树形图异常值的影响 最长距离法容易被异常值严重地扭曲，一个有效的方法是将这些异常值单独拿出来后再进行聚类。三、中间距离法 类与类之间的距离既不取两类最近样
14、品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离，称为中间距离法(median method)。 设某一步将GK和GL合并为GM，对于任一类GJ，考虑由DKJ、DLJ和DKL为边长组成的三角形(如下图所示)，取DKL边的中线作为DMJ。DMJ的计算公式为2222111222MJKJLJKLDDDD四、类平均法 类平均法(average linkage method)有两种定义，一种定义方法是把类与类之间的距离定义为所有样品对之间的平均距离，即定义GK和GL之间的距离为其中nK和nL分别为类GK和GL的样品个数，dij为GK中的样品i与GL中的样品j之间的距离，如图所示。容易得到
15、它的一个递推公式：,1KLKLiji Gj GKLDdn n,11MJKJLJMJijijiji Gj Gi Gj Gi Gj GMJMJKLKJLJMMDdddn nn nnnDDnn图 类平均法：DKL=(d13+d14+d15+d23+d24+d25)/ 6 另一种定义方法是定义类与类之间的平方距离为样品对之间平方距离的平均值，即 它的递推公式为 类平均法较好地利用了所有样品之间的信息，在很多情况下它被认为是一种比较好的系统聚类法。22,1KLKLiji Gj GKLDdn n222KLMJKJLJMMnnDDDnn对上例采用（使用平方距离的）类平均法进行聚类。一开始将D(0)的每个元素
16、都平方，并记作2(0)DG1G2G3G4G5G10G210G325160G4493640G51008125902(0)D2(1)DG6G3G4G5G60G320.50G442.540G590.52590G6G7G5G60G731.50G590.51702(2)D2(3)DG6G8G60G851.170类平均法树形图五、重心法 类与类之间的距离定义为它们的重心(均值)之间的欧氏距离。设GK和GL的重心分别为 ，则GK与GL之间的平方距离为 这种系统聚类法称为重心法(centroid hierarchical method)，如图。它的递推公式为KLxx和 22KLKLKLKLDdx xxxxx2
17、2222KLKLMJKJLJKLMMMnnn nDDDDnnn重心法：KLKLx xDd与其他系统聚类法相比，重心法在处理异常值方面更稳健，但是在别的方面一般不如类平均法或离差平方和法的效果好。六、离差平方和法(Ward方法) 类中各样品到类重心（均值）的平方欧氏距离之和称为（类内）离差平方和。设类GK和GL合并成新类GM，则GK,GL和GM的离差平方和分别是它们反映了各自类内样品的分散程度。 KLMKiKiKi GLiLiLi GMiMiMi GWWWxxxxxxxxxxxx类内离差平方和的几何解释 类内离差平方和WK是类GK内各点到类重心点 的直线距离之平方和。kx 定义GK和GL之间的平
18、方距离为这种系统聚类法称为离差平方和法或Ward方法(Wards minimum variance method)。 也可表达为 离差平方和法使得两个大的类倾向于有较大的距离，因而不易合并；相反，两个小的类却因倾向于有较小的距离而易于合并。这往往符合我们对聚类的实际要求。2KLMKLDWWW2KLD 2KLKLKLKLMn nDnxxxx图 离差平方和法与重心法的聚类比较 离差平方和法的平方距离递推公式为 对采用离差平方和法进行聚类。2222JKJLJMJKJLJKLJMJMJMnnnnnDDDDnnnnnnG1G2G3G4G5G10G20.50G312.580G424.51820G55040
19、.512.54.502(0)D2(1)DG6G3G4G5G60G313.50G428.1720G560.1712.54.502(2)DG6G7G5G60G730.250G560.1710.6702(3)DG6G8G60G856.030离差平方和法树形图 例 下表列出了全国31个省市区地球化学扫面的八个主要变量数据。x1、 x2 、 x3、 x4 、x5 、x6 、 x7 、 x8，试分别用最短距离法、重心法和Ward方法对各地区作聚类分析。为同等地对待每一变量，在作聚类前，先对各变量作标准化变换。表 地球化学扫面数据 单位：ppm地区x1x2x3x4x5x6x7x8北京2959.19730.7
20、9749.41513.34467.871141.82478.42457.64天津2459.77495.47697.33302.87284.19735.97570.84305.08河北1495.63515.9362.37285.32272.95540.58364.91188.63山西1406.33477.77290.15208.57201.5414.72281.84212.1内蒙古1303.97524.29254.83192.17249.81463.09287.87192.96辽宁1730.84553.9246.91279.81239.18445.2330.24163.86吉林1561.8649
21、2.42200.49218.36220.69459.62360.48147.76黑龙江1410.11510.71211.88277.11224.65376.82317.61152.85上海3712.31550.74893.37346.935271034.98720.33462.03江苏2207.58449.37572.4211.92302.09585.23429.77252.54浙江2629.16557.32689.73435.69514.66795.87575.76323.36安徽1844.78430.29271.28126.33250.56513.18314151.39福建2709.464
22、28.11334.12160.77405.14461.67535.13232.29江西1563.78303.65233.81107.9209.7393.99509.39160.12山东1675.75613.32550.71219.79272.59599.43371.62211.84河南1427.65431.79288.55208.14217337.76421.31165.32湖北1783.43511.88282.84201.01237.6617.74523.52182.52湖南1942.23512.27401.39206.06321.29697.22492.6226.45广东3055.1735
23、3.23564.56356.27811.88873.061082.82420.81广西2033.87300.82338.65157.78329.06621.74587.02218.27海南2057.86186.44202.72171.79329.65477.17312.93279.19重庆2303.29589.99516.21236.55403.92730.05438.41225.8四川1974.28507.76344.79203.21240.24575.1430.36223.46贵州1673.82437.75461.61153.32254.66445.59346.11191.48云南2194
24、.25537.01369.07249.54290.84561.91407.7330.95西藏2646.61839.7204.44209.11379.3371.04269.59389.33陕西1472.95390.89447.95259.51230.61490.9469.1191.34甘肃1525.57472.98328.9219.86206.65449.69249.66228.19青海1654.69437.77258.78303244.93479.53288.56236.51宁夏1375.46480.89273.84317.32251.08424.75228.73195.93新疆1608.82
25、536.05432.46235.82250.28541.3344.85214.4图 最短距离法图 重心法图 离差平方和法 从树形图来看，如Ward方法将31个地区分为以下三类： 第类：北京、浙江、上海和广东。第类：天津、江苏、云南、重庆、河北、新疆、山东、湖北、四川、湖南、福建、广西、海南和西藏。第类：山西、甘肃、内蒙古、辽宁、黑龙江、吉林、青海、宁夏、安徽、贵州、河南、陕西和江西。 如果分为五类，则广东和西藏将各自为一类。 ？问题：试从成矿带或大地构造单元的演化史来解释这几种分？问题：试从成矿带或大地构造单元的演化史来解释这几种分类的合理性？类的合理性？七、系统聚类法的统一 Lance和Wi
26、lliams于1967年将八种系统聚类法的递推公式统一为： 其中K, L, , 是参数，不同的系统聚类法，它们有不同的取值。下表列出了上述各种方法四个参数的取值。222222MJKKJLLJKLKJLJDDDDDD系统聚类法参数表单调性 令Di是系统聚类法中第i次并类时的距离，如果一种系统聚类法能满足D1D2D3 ，则称它具有单调性。这种单调性符合系统聚类法的思想，先合并较相似的类，后合并较疏远的类。 最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都具有单调性，但中间距离法和重心法不具有单调性。八、类的个数 如果能够分成若干个很分开的类，则类的个数就比较容易确定；反之，如
27、果无论怎样分都很难分成明显分开的若干类，则类个数的确定就比较困难了。 确定类个数的常用方法有： 1.给定一个阈值T。 2.观测样品的散点图。 3.使用统计量。1.给定一个阈值T 通过观测树形图，给出一个你认为合适的阈值T，要求类与类之间的距离要大于T，有些样品可能会因此而归不了类或只能自成一类。这种方法有较强的主观性，这是它的不足之处。2.观测样品的散点图 如果样品只有两个或三个变量，则可通过观测数据的散点图来确定类的个数。对于三个变量，可使用软件的交互式数据分析菜单系统通过旋转三维坐标轴从各个角度来观测散点图。 如果变量个数超过三个，则可对每一可能考虑的聚类结果分别使用费希尔判别法进行降维，
28、将所有样品的前两个或三个判别式得分制作成散点图，观测类之间是否分离得较好以决定分几类较为合适。 从散点图中进行主观聚类 观测散点图还有一个重要的用途，就是从直觉上来判断所采用的聚类方法是否合理，甚至有时直接从散点图中进行主观的分类，效果也许会好于正规的聚类方法，特别是在寻找“自然的”类方面。寻找“自然的”类3.使用统计量 （1）R2统计量。 （2）半偏R2统计量。 （3）伪F统计量。 （4）伪t统计量。4 动态聚类法 动态聚类法的基本思想是，选择一批凝聚点或给出一个初始的分类，让样品按某种原则向凝聚点凝聚，对凝聚点进行不断的修改或迭代，直至分类比较合理或迭代稳定为止。类的个数k可以事先指定，也
29、可以在聚类过程中确定。选择初始凝聚点（或给出初始分类）的一种简单方法是采用随机抽选（或随机分割）样品的方法。 动态聚类法有许多种方法，比较流行的动态聚类法k均值法。k均值法是由麦奎因（MacQueen,1967）提出并命名的一种算法。k均值法的基本步骤 (1)选择k个样品作为初始凝聚点，或者将所有样品分成k个初始类，然后将这k个类的重心（均值）作为初始凝聚点。 (2)对除凝聚点之外的所有样品逐个归类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点更新为这一类目前的均值，直至所有样品都归了类。 (3)重复步骤(2)，直至所有的样品都不能再分配为止。 最终的聚类结果在一定程
30、度上依赖于初始凝聚点或初始分类的选择。经验表明，聚类过程中的绝大多数重要变化均发生在第一次再分配中。 例 对上述5个样品采用k均值法聚类，指定k=2，具体步骤如下：(1) 随意将这些样品分成两类，则这两个初始类的均值分别是5和 。(2)计算1到两个类(均值)的欧氏距离(0)(0)121,6,82,11GG和162(0)1(0)21,154111,16522dGdG由于1到 的距离小于到 的距离，因此1不用重新分配，计算6到两个类的距离故6应重新分配到 中，修正后的两个类为 ，新的类均值分别为 。计算(0)1G(0)2G(0)1(0)26,651116,6622dGdG(0)2G(1)22,6,
31、11G和114623和(1)11,8G(1)1(1)2118,84322128,86133dGdG结果8重新分配到 中，两个新类为 ，其类均值分别为1和 。再计算重新分配2到 中，两个新类为 ，其类均值分别为 。 (3)再次计算每个样品到类均值的距离，结果列于表。 最终得到的两个类为1,2和6,8,11。(1)2G (2)11G364(2)1(2)22,211332,26444dGdG(2)1G(2)22,6,8,11G(3)11,2G,(3)26,8,11G111823和各样品到类均值的距离例 对地化扫面的例子使用k均值法进行聚类，聚类前对各变量作标准化变换，聚类结果如下： 第类：北京、上海和浙江。 第类：广东。 第类：天津、江苏、福建、山东、湖南、广西、 重庆、四川和云南。 第类：河北、山西、内蒙古、辽宁、吉林、黑龙 江、安徽、江西、河南、湖北、海南、贵 州、陕西、甘肃、青海、宁夏和新疆。 第类：西藏。结结 束束
