六章聚类分析.ppt

《六章聚类分析.ppt》由会员分享，可在线阅读，更多相关《六章聚类分析.ppt（83页珍藏版）》请在三一文库上搜索。

1、第六章 聚类分析 v6.1 引言 v6.2 距离和相似系数 v6.3 系统聚类法 v6.4 动态聚类法 1 6.1 引言 v聚类分析：将分类对象分成若干类，相似的归为同 一类，不相似的归为不同的类。 v聚类分析和判别归类有着不同的分类目的，彼此之 间既有区别又有联系。 v聚类分析分为Q型（分类对象为样品）和R型（分类 对象为变量）两种。 2 相似性的不同定义 3 6.2 距离和相似系数 v相似性度量：距离和相似系数。 v样品之间的距离和相似系数有着各种不同的定义，而这些定 义与变量的类型有着非常密切的关系。 v变量的测量尺度：间隔、有序和名义尺度。 间隔变量：变量用连续的量来表示，如长度、重量

2、、速度、 温度等。 有序变量：变量度量时不用明确的数量表示，而是用等级来 表示，如某产品分为一等品、二等品、三等品等有次序关 系。 名义变量：变量用一些类表示，这些类之间既无等级关系也 无数量关系，如性别、职业、产品的型号等。 4 v对于间隔变量，距离常用来度量样品之间的相似性 ，相似系数常用来度量变量之间的相似性。 v本章主要讨论具有间隔尺度变量的样品聚类分析方 法。 v一、距离 v二、相似系数 5 一、距离 v设x =(x1,x2,xp) 和y =(y1,y2,yp)为两个样品，则所 定义的距离一般应满足如下三个条件： (i)非负性：d(x, y)0，d(x, y)=0当且仅当x=y； (

3、ii)对称性：d(x, y) = d(y, x)； (iii)三角不等式：d(x, y)d(x,z) + d(z, y)。 6 常用的距离 v1.明考夫斯基（Minkowski）距离 v2.兰氏（Lance和Williams）距离 v3.马氏距离 v4.斜交空间距离 7 1.明考夫斯基距离 v明考夫斯基距离（简称明氏距离）： 这里q0。 v明氏距离的三种特殊形式： v(i)当q=1时， ，称为绝对值距离，常被 形象地称作“城市街区”距离； v(ii)当q=2时， ， 这是欧氏距离，它是聚类分析中最常用的一个距离； v(iii)当q=时， ，称为切比雪夫距离。 8 绝对值距离图示 9 对各变量的

4、数据作标准化处理 v当各变量的单位不同或测量值范围相差很大时，应 先对各变量的数据作标准化处理。最常用的标准化 处理是，令 其中 和sii分别为xi的样本均值和样本方差。 10 2.兰氏距离 v当所有的数据皆为正时，可以定义x与y之间的兰氏 距离为 v该距离与各变量的单位无关，且适用于高度偏斜或 含异常值的数据。 11 3.马氏距离 vx和y之间的马氏距离为 其中S为样本协差阵。 12 4.斜交空间距离 vx和y之间的斜交空间距离定义为 其中rij是第i个变量与第j个变量间的相关系数。 v当p个变量互不相关时，该距离即为欧氏距离的1/p 倍。 13 名义尺度变量的一种距离定义 v例6.2.1

5、某高校举办一个培训班，从学员的资料中得到这样 六个变量：性别(x1)，取值为男和女；外语语种(x2)，取值为 英、日和俄；专业(x3)，取值为统计、会计和金融；职业(x4) ，取值为教师和非教师；居住处(x5)，取值为校内和校外； 学历(x6)，取值为本科和本科以下。 现有两名学员： x=(男，英，统计，非教师，校外，本科) y=(女，英，金融，教师，校外，本科以下) 一般地，若记配合的变量数为m1，不配合的变量数为m2，则 它们之间的距离可定义为 故按此定义，本例中x 与y 之间的距离为2/3。 14 二、相似系数 v变量之间的相似性度量，在一些应用中要看相似系 数的大小，而在另一些应用中要

6、看相似系数绝对值 的大小。 v相似系数（或其绝对值）越大，认为变量之间的相 似性程度就越高；反之，则越低。 v聚类时，比较相似的变量倾向于归为一类，不太相 似的变量归属不同的类。 15 相似系数一般需满足的条件 v(1)cij=1，当且仅当xi=axj+b，a(0) 和b是常数； (2)|cij|1，对一切i,j； (3)cij=cji，对一切i,j。 16 两个向量的夹角余弦 17 1.夹角余弦 v变量xi与xj的夹角余弦定义为 它是Rn中变量xi的观测向量(x1i,x2i,xni)与变量xj的观 测向量(x1j,x2j,xnj)之间夹角ij的余弦函数，即 cij(1)=cosij。 18

7、2.相关系数 v变量xi与xj的相关系数为 v如果变量xi与xj是已标准化了的，则它们间的夹角余 弦就是相关系数。 19 v相似系数除常用来度量变量之间的相似性外有时也 用来度量样品之间的相似性，同样，距离有时也用 来度量变量之间的相似性。 v由距离来构造相似系数总是可能的，如令 这里dij为第i个样品与第j个样品的距离，显然cij满足 定义相似系数的三个条件，故可作为相似系数。 v距离必须满足定义距离的三个条件，所以不是总能 由相似系数构造。高尔（Gower）证明，当相似系 数矩阵(cij)为非负定时，如令 则dij满足距离定义的三个条件。 20 6.3 系统聚类法 v系统聚类法（或层次聚类

8、法，hierarchical clustering method）是通过一系列相继的合并或相继的分割来 进行的，分为聚集的（agglomerative）和分割的（ divisive）两种，适用于样品数目n不是很大的情形 。 v聚集系统法的基本思想是：开始时将n个样品各自作 为一类，并规定样品之间的距离和类与类之间的距 离，然后将距离最近的两类合并成一个新类，计算 新类与其他类的距离；重复进行两个最近类的合并 ，每次减少一类，直至所有的样品合并为一类。 21 一开始每个样品各自作为一类 22 v分割系统法的聚类步骤与聚集系统法正相反。由n个 样品组成一类开始，按某种最优准则将它分割成两 个尽可能

9、远离的子类，再用同样准则将每一子类进 一步地分割成两类，从中选一个分割最优的子类， 这样类数将由两类增加到三类。如此下去，直至所 有n个样品各自为一类或采用某种停止规则。 v聚集系统法最为常用，本节集中介绍其中常用的八 种方法，所有这些聚类方法的区别在于类与类之间 距离的定义不同。 23 6.3 系统聚类法 v一、最短距离法 v二、最长距离法 v三、类平均法 v四、重心法 v*五、中间距离法 v六、离差平方和法（Ward方法） v七、系统聚类法的统一 v八、类的个数 24 一、最短距离法 v定义类与类之间的距离为两类最近样品间的距离， 即 25 图6.3.1 最短距离法：DKL=d23 最短距

10、离法的聚类步骤 v(1)规定样品之间的距离，计算n个样品的距离矩阵 D(0)，它是一个对称矩阵。 v(2)选择D(0)中的最小元素，设为DKL，则将GK和GL合 并成一个新类，记为GM，即GM= GKGL。 v(3)计算新类GM与任一类GJ之间距离的递推公式为 26 递推公式的图示理解 27 最短距离法的聚类步骤 在D(0)中，GK和GL所在的行和列合并成一个新行新 列，对应GM ，该行列上的新距离值由上述递推公式 求得，其余行列上的距离值不变，这样就得到新的 距离矩阵，记作D(1) 。 v(4)对D(1)重复上述对D(0)的两步得D(2) ，如此下去直 至所有元素合并成一类为止。 28 v如

11、果某一步D(m)中最小的元素不止一个，则称此现象为结（ tie），对应这些最小元素的类可以任选一对合并或同时合 并。最短距离法最容易产生结，且有一种挑选长链状聚类的 倾向，称为链接（chaining）倾向。 v由于最短距离法是用两类之间最近样本点的距离来聚的，因 此该方法不适合对分离得很差的群体进行聚类。 29 v例6.3.1 设有五个样品，每个只测量了一个指标， 分别是1，2，6，8，11，试用最短距离法将它们分 类。 记G1=1，G2=2，G3=6，G4=8，G5=11， 样品间采用绝对值距离。 G1G2G3G4G5 G10 G210 G3540 G47620 G5109530 表6.3.

12、1 D(0) 30 其中G6= G1G2 其中G7= G3G4 G6G3G4G5 G60 G340 G4620 G59530 表6.3.2 D(1) 表6.3.3 D(2) G6G7G5 G60 G740 G5930 31 其中G6= G1G2 表6.3.4 D(3) G6G8 G60 G840 32 图6.3.2 最短距离法树形图 二、最长距离法 v类与类之间的距离定义为两类最远样品间的距离， 即 33 图6.3.3 最长距离法：DKL=d15 v最长距离法与最短距离法的并类步骤完全相同，只 是类间距离的递推公式有所不同。 v递推公式： 34 v对例6.3.1采用最长距离法，其树形图如图6.

13、3.4所示 ，它与图6.3.2有相似的形状，但并类的距离要比图 6.3.2大一些，仍分成两类为宜。 35 图6.3.4 最长距离法树形图 异常值的影响 v最长距离法容易被异常值严重地扭曲。 36 v例6.3.2 对305名女中学生测量八个体型指标： x1：身高x5：体重 x2：手臂长x6：颈围 x3：上肢长x7：胸围 x4：下肢长x8：胸宽 37 表6.3.5各对变量之间的相关系数 x1x2x3x4 x5x6x7x8 x11.000 x20.8461.000 x30.8050.8811.000 x40.8590.8260.8011.000 x50.4730.3760.3800.436 1.00

14、0 x60.3980.3260.3190.329 0.7621.000 x70.3010.2770.2370.327 0.7300.5831.000 x80.3820.4150.3450.365 0.6290.5770.5391.000 38 图6.3.5 八个体型变量的最长距离法树形图 三、类平均法 v有两种定义。一种定义方法是把类与类之间的距离定义为所 有样品对之间的平均距离，即定义GK和GL之间的距离为 39 图6.3.6 类平均法 v递推公式： 40 v另一种定义方法是定义类与类之间的平方距离为样 品对之间平方距离的平均值，即 v它的递推公式为 v类平均法较好地利用了所有样品之间的信息

15、，在很 多情况下它被认为是一种比较好的系统聚类法。 41 v对例6.3.1采用（使用平方距离的）类平均法进行聚 类。一开始将D(0)的每个元素都平方，并记作 。 G1G2G3G4G5 G10 G210 G325160 G4493640 G5100812590 表6.3.6 42 G6G3G4G5 G60 G320.50 G442.540 G590.52590 表6.3.7 G6G7G5 G60 G731.50 G590.5170 表6.3.8 43 G6G8 G60 G851.170 G6G8 G60 G851.170 表6.3.9 44 图6.3.7 类平均法树形图 四、重心法 v类与类之间

16、的距离定义为它们的重心(均值)之间的 欧氏距离。设GK和GL的重心分别为 ，则GK与 GL之间的平方距离为 45 图6.3.8 重心法 v合并GK和GL之后的新类GM的重心是 其中nM=nK+nL为GM的样品个数。 v重心法的递推公式为 v与其他系统聚类法相比，重心法在处理异常值方面 更稳健，但是在别的方面一般不如类平均法或离差 平方和法的效果好。 46 *五、中间距离法 v设某一步将GK和GL合并为GM，对于任一类GJ，考虑由DKJ， DLJ和DKL为边长组成的三角形，取DKL边的中线作为DMJ。 DMJ的计算公式为 47 图6.3.9 中间距离法的几何表示 六、离差平方和法(Ward方法)

17、 v（类内）离差平方和：类中各样品到类重心（均值）的平方 欧氏距离之和。 v设类GK和GL合并成新类GM，则GK, GL和GM的离差平方和分 别是 对固定的类内样品数，它们反映了各自类内样品的分散程 度。 48 类内离差平方和的几何解释 v类内离差平方和WK是类GK内各点到类重心点 的直 线距离之平方和。 49 v定义GK和GL之间的平方距离为 v 也可表达为 v离差平方和法使得两个大的类倾向于有较大的距离 ，因而不易合并；相反，两个小的类却因倾向于有 较小的距离而易于合并。这往往符合我们对聚类的 实际要求。 50 51 图6.3.10 离差平方和法与重心法的聚类比较 v离差平方和法的平方距离

18、递推公式为 v对例6.3.1采用离差平方和法进行聚类。 52 图6.3.11 离差平方和法树形图 v最短距离法、最长距离法和类平均法都属于连接方法，它们 既可以用于样品的聚类，也能够用于变量的聚类。本章介绍 的其他聚类方法都将只能用于样品的聚类。 v例6.3.3 表6.3.10列出了1999年全国31个省、直辖市和自治 区的城镇居民家庭平均每人全年消费性支出的八个主要变量 数据。这八个变量是 x1：食品x5：交通和通讯 x2：衣着x6：娱乐教育文化服务 x3：家庭设备用品及服务x7：居住 x4：医疗保健x8：杂项商品和服务 分别用最短距离法、重心法和Ward方法对各地区作聚类分析 。为同等地对

19、待每一变量，在作聚类前，先对各变量作标准 化变换。 53 表6.3.10 消费性支出数据 单位：元 地区x1x2x3x4x5x6x7x8 北京2959.19730.79749.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

20、.17249.81463.09287.87192.96 辽宁1730.84553.9246.91279.81239.18445.2330.24163.86 吉林1561.86492.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.326

21、89.73435.69514.66795.87575.76323.36 安徽1844.78430.29271.28126.33250.56513.18314151.39 福建2709.46428.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 54 河南1427.65431.79288.55208.14217337.76421.31165.32 湖北1783.43

22、511.88282.84201.01237.6617.74523.52182.52 湖南1942.23512.27401.39206.06321.29697.22492.6226.45 广东3055.17353.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

23、 四川1974.28507.76344.79203.21240.24575.1430.36223.46 贵州1673.82437.75461.61153.32254.66445.59346.11191.48 云南2194.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.662

24、28.19 青海1654.69437.77258.78303244.93479.53288.56236.51 宁夏1375.46480.89273.84317.32251.08424.75228.73195.93 新疆1608.82536.05432.46235.82250.28541.3344.85214.4 55 图6.3.12 最短距离法 56 图6.3.13 重心法 57 图6.3.14 离差平方和法 58 从这三个树形图来看，只有Ward方法较好地符合了 我们的实际聚类要求，它将31个地区分为以下三类 ： 第类：北京、浙江、上海和广东。这些都是我国经 济最发达、城镇居民消费水平最高的

25、沿海地区。 第类：天津、江苏、云南、重庆、河北、新疆、 山东、湖北、四川、湖南、福建、广西、海南和西 藏。这些地区在我国基本上属于经济发展水平和城 镇居民消费水平中等的地区。 第类：山西、甘肃、内蒙古、辽宁、黑龙江、吉 林、青海、宁夏、安徽、贵州、河南、陕西和江 西。这些地区在我国基本上属于经济较落后地区， 城镇居民的消费水平也是较低的。 v如果分为五类，则广东和西藏将各自为一类。 59 60 图6.3.15 离差平方和法所分三类的平行图 七、系统聚类法的统一 vLance和Williams于1967年将（书中介绍的）八种系 统聚类法的递推公式统一为： 其中K, L, , 是参数，不同的系统聚

26、类法，它们有 不同的取值。表6.3.11列出了上述八种方法四个参 数的取值。 v1.单调性 v2.空间的浓缩与扩张 61 表6.3.11 系统聚类法参数表 62 1.单调性 v令Di是系统聚类法中第i次并类时的距离，如果一种 系统聚类法能满足D1D2D3 ，则称它具有单调 性。这种单调性符合系统聚类法的思想，先合并较 相似的类，后合并较疏远的类。 v最短距离法、最长距离法、可变法、类平均法、可 变类平均法和离差平方和法都具有单调性，但中间 距离法和重心法不具有单调性。 63 2.空间的浓缩与扩张 v设A=(aij)和B=(bij)是两个元素非负的同阶矩阵，若aijbij(对一 切i, j)，则

27、记作AB。该记号仅在本节中使用。 v设有两种系统聚类法，它们在第i步的距离矩阵分别为Ai和Bi ，i=0,1,n1，若AiBi，i=1,n1，则称第一种方法比第二 种方法使空间扩张，或第二种方法比第一种方法使空间浓缩 。 v以类平均法为基准，有如下一些结论： (1) D(短)D(平)，D(重)D(平)。 (2) D(长)D(平)。 (3) 当01时,D(变平)D(平)；当0时,D(变平)D(平)。 64 例6.3.4 （最短距离法的链接倾向） 65 v(1)采用最短距离法。可以算得，当聚成两类时，C1 和C11组成一类，其余所有的点组成另一类，这里出 现了链接现象；当聚成三类时，C1和C11组

28、成第类 ，其余的C点组成第类，所有的A点和B点组成第 类。 v(2)采用类平均法。经算得，当聚成两类时，一类由 所有C点构成，另一类由所有A点和所有B点构成； 当聚成三类时，A点群、B点群和C点群各自作为一 类。 66 从直观的图形中进行主观聚类 v当p=2时，可通过目测散点图从直觉上来判断所采用的正规 聚类方法是否合理。我们甚至可以直接在散点图上进行主观 的聚类，其效果未必逊于正规的聚类方法，特别是在寻找“ 自然的”类和符合我们实际需要的类方面。 v当p=3时，我们可使用SAS软件的交互式数据分析菜单系统 产生三维旋转图，通过旋转三维坐标轴从各个角度来观测散 点图，以直观评估所作聚类的效果如

29、何，不过观测效果一般 明显不如平面散点图清楚。 v当p3时，有时我们可采用主成分分析（见第七章）或因子 分析（见第八章）的技术将维数降至2或3维，然后再生成散 点图或旋转图，从直觉上进行主观的聚类。 67 寻找“自然的”类 68 八、类的个数 v如果能够分成若干个很分开的类，则类的个数就比 较容易确定；反之，如果无论怎样分都很难分成明 显分开的若干类，则类个数的确定就比较困难了。 v确定类个数的常用方法有： 1.给定一个阈值T。 2.观测样品的散点图。 3.使用统计量。 69 1.给定一个阈值T v通过观测树形图，给出一个你认为合适的阈值T， 要求类与类之间的距离要大于T，有些样品可能会 因此

30、而归不了类或只能自成一类。这种方法有较强 的主观性，这是它的不足之处。 70 2.观测样品的散点图 v如果样品只有两个（或三个）变量，则可通过观测 数据的散点图（或旋转图）来主观确定类的个数。 v如果变量个数超过三个，则可对每一可能考虑的聚 类结果，将所有样品的前两个（或三个）费希尔判 别函数得分制作成散点图（或旋转图），目测类之 间是否分离得较好。该图既能帮助我们评估聚类效 果的好坏，也能帮助我们判断所定的类数目是否恰 当。 71 72 图6.3.17 按图6.3.14分三类的两个判别函数得分的散点图 73 图6.3.18 按图6.3.14分五类的两个判别函数得分的散点图 3.使用统计量 v

31、（1）R2统计量。 v（2）半偏R2统计量。 v（3）伪F统计量。 v（4）伪t统计量。 74 6.4 动态聚类法 v在系统聚类法中，对于那些先前已被“错误”分类的 样品不再提供重新分类的机会，而动态聚类法（或 称逐步聚类法）却允许样品从一个类移动到另一个 类中。 v动态聚类法的计算量要比建立在距离矩阵基础上的 系统聚类法小得多。因此，使用动态聚类法计算机 所能承受的样品数目n要远远超过使用系统聚类法所 能承受的n。 75 v动态聚类法的基本思想是，选择一批凝聚点或给出一个初始 的分类，让样品按某种原则向凝聚点凝聚，对凝聚点进行不 断的修改或迭代，直至分类比较合理或迭代稳定为止。类的 个数k需

32、先指定一个。 v选择初始凝聚点（或给出初始分类）的一种简单方法是采用 随机抽选（或随机分割）样品的方法，可以要求凝聚点之间 至少应间隔某个距离值。 v动态聚类法只能用于对样品的聚类，而不能用于对变量的聚 类。 v动态聚类法有许多种方法，在这一节中，我们将讨论一种比 较流行的动态聚类法k均值法。它是由麦奎因（ MacQueen，1967）提出并命名的一种算法。 76 k均值法的基本步骤 v(1)选择k个样品作为初始凝聚点，或者将所有样品 分成k个初始类，然后将这k个类的重心（均值）作 为初始凝聚点。 v(2)对除凝聚点之外的所有样品逐个归类，将每个样 品归入凝聚点离它最近的那个类（通常采用欧氏距

33、 离），该类的凝聚点更新为这一类目前的均值，直 至所有样品都归了类。 v(3)重复步骤(2)，直至所有的样品都不能再分配为 止。 77 v最终的聚类结果在一定程度上依赖于初始凝聚点或 初始分类的选择。经验表明，聚类过程中的绝大多 数重要变化均发生在第一次再分配中。 v例6.4.1 对例6.3.1采用k均值法聚类，指定k=2，具 体步骤如下： (1) 随意将这些样品分成 两类，则这两个初始类的均值分别是5和 。 (2)计算1到两个类(均值)的欧氏距离 78 1不用重新分配，计算6到两个类的距离 故6应重新分配到 中，修正后的两个类为 ，新的类均值分别为 。计算 79 结果8重新分配到 中，两个新

34、类为 ， ，其类均值分别为1和 。再计算 重新分配2到 中，两个新类为 ，其类均值分别为 。 (3)再次计算每个样品到类均值的距离，结果列于表 6.4.1。 最终得到的两个类为1,2和6,8,11。 80 表6.4.1 各样品到类均值的距离 81 v例6.4.2 对例6.3.3使用k均值法进行聚类，聚类前对 各变量作标准化变换，聚类结果如下： 第类：北京、上海和浙江。 第类：广东。 第类：天津、江苏、福建、山东、湖南、广西、 重庆、四川和云南。 第类：河北、山西、内蒙古、辽宁、吉林、黑龙 江、安徽、江西、河南、湖北、海南、贵 州、陕西、甘肃、青海、宁夏和新疆。 第类：西藏。 82 v由于k均值法对凝聚点的初始选择有一定敏感性，故 再试一下其他初始的凝聚点也许是个不错的想法。 如果不同初始凝聚点的选择产生明显不同的最终聚 类结果，或者迭代的收敛是极缓慢的，那么可能表 明没有自然的类可以形成。 vk均值法有时也可用来改进系统聚类的结果，例如， 先用类平均法聚类，然后将其各类的重心作为k均值 法的初始凝聚点重新聚类，这可使得系统聚类时错 分的样品能有机会获得重新的分类。不过，k均值法 能否有效地改善系统聚类，我们不能一概而论，还 应视聚类的最终结果而定。 83