六章聚类分析.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离差平方和法的平方距离
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 聚类分析
链接地址:https://www.31doc.com/p-2594490.html