04聚类分析.pdf

《04聚类分析.pdf》由会员分享，可在线阅读，更多相关《04聚类分析.pdf（16页珍藏版）》请在金锄头文库上搜索。

1、学 海 无 涯 聚类分析专题 6.1 引言引言 俗话说， “物以类聚，人以群分” ，在自然科学和社会科学等各领域中，存在着大量的 分类问题。分类学是人类认识世界的基础科学，在古老的分类学中，人们主要靠经验和专业 知识进行定性的分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分 类的要求越来越高， 以致有时仅凭经验和专业知识难以确切地进行分类， 于是人们逐渐地把 数学工具引用到了分类学中， 这便形成了数值分类学这一学科， 之后又将多元分析的技术引 入到数值分类学， 便又从数值分类学中分离出一个重要分支聚类分析。 与多元分析的其 它分析方法相比，聚类分析方法较为粗糙，理论上还不够完

2、善，正处于发展阶段。但是，由 于该方法应用方便，分类效果较好，因此越来越为人们所重视。这些年来聚类分析的方法发 展较快，内容越来越丰富。 判别分析与聚类分析都是研究事物分类的基本方法，它们有着不同的分类目的，彼此 之间既有区别又有联系。 各种判别分析方法都要求对类有事先的了解， 通常是每一类都有一 个样本，据此得出判别函数和规则，进而可对其它新的样品属于哪一类作出判断。对类的事 先了解和确定常常可以通过聚类分析得到。 聚类分析的目的是把分类对象按一定规则分成若 干类，这些类不是事先给定的，而是根据数据的特征确定的。在同一类里的这些对象在某种 意义上倾向于彼此相似， 而在不同类里的对象倾向于不相

3、似。 聚类分析能够用来概括数据而 不只是为了寻找“自然的”或“实在的”分类。例如，在选拔少年运动员时，对少年的身体 形态、身体素质、生理功能的各种指标进行测试，据此对少年进行分类，分在同一类里的少 年这些指标较为相近。类确定好之后，可以根据各类的样本数据得出选材的判别规则，作为 选材的依据。又如，根据啤酒中含有的酒精成分、纳成分、所含的热量“卡路里”数值，可 以对啤酒进行分类。 聚类分析根据分类对象不同分为Q型聚类分析和R型聚类分析。Q型聚类分析是指对 样品进行聚类，R型聚类分析是指对变量进行聚类。本章我们主要讨论Q型聚类。 6.2 距离和相似系数距离和相似系数 在对样品（或变量）进行分类时，

4、样品（或变量）之间的相似性是如何度量的呢？这 一节中， 我们介绍两个相似性度量距离和相似系数， 前者常用来度量样品之间的相似性。 后者常用来度量变量之间的相似性。 样品之间的距离和相似系数有着各种不同的定义， 而这 些定义与变量的类型有着非常密切的关系。通常变量按测量尺度的不同可以分为以下三类： （1） 间隔尺度变量：变量用连续的量来表示，如长度、重量、速度、温度等。 （2） 有序尺度变量：变量度量时不用明确的数量表示，而是用等级来表示，如某产品 分为一等品、二等品、三等品等有次序关系。 （3） 名义尺度变量：变量用一些类表示，这些类之间既无等级关系也无数量关系，如 性别、职业、产品的型号等。

5、 学 海 无 涯 我们这里主要讨论具有间隔尺度变量的样品聚类分析方法。 一、距离一、距离 设 ij x为第i个样品的第j个指标，数据矩阵列于表 6.1。每个样品有p个变量，故每个 样品都可以看成是 p R中的一个点，n个样品就是 p R中的n个点。 在 p R中需定义某种距离， 第i个样品与第j个样品之间的距离记为 ij d， 在聚类过程中， 距离较近的点倾向于归为一类， 距离较远的点应归属不同的类。所定义的距离 ij d一般应满足如下四个条件： （） 0 ij d，对一切ji,； （） 0= ij d，当且仅当第i个样品与第j个样品的各变量值相同； （） jiij dd=，对一切ji,； （

6、） kjikij ddd+，对一切kji,。 表 6.1 数据矩阵 变量 样品 1 x 2 x p x 1 11 x 12 x p x1 2 21 x 22 x p x2 n 1n x 2n x np x 常用的距离有如下几种： 1明考夫斯基(Minkowski)距离 第i个样品与第j个样品间的明考夫斯基距离定义为 q p k q jkikij xxqd 1 1 )( = = （6.2.1） 这里q为某一自然数，这是一个最常用最直观的距离。 当1=q时， = = p k jkikij xxd 1 ) 1 (，称为绝对值距离； 当2=q时，()() = = = p k jkik p k jkik

7、ij xxxxd 1 2 2 1 1 2 )2(，称为欧氏距离； 当=q时， jkik pk ij xxd= 1 max)(，称为切比雪夫距离。 当各变量的单位不同或虽单位相同但各变量的测量值相差很大时，不应直接采用明考 夫斯基距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常 用的标准化处理是，令 学 海 无 涯 jj j ij ij s xx x = * ，ni, 2 , 1=，pj, 2 , 1= 其中， = = n i ij jx n x 1 1 为第j个变量的样本均值， = = n i j ijjj xx n s 1 2 )( 1 1 为第j个变量的 样本方差

8、。 2马氏(Mahalanobis)距离 第i个样品与第j个样品间的马氏距离为 )()()( 12 jijiij xxSxxMd= （6.2.2） 其中),( 21 = ipiii xxxx，S为样本协方差矩阵。使用马氏距离的好处是考虑到了各变量 之间的相关性，并且与各变量的单位无关。不足之处是对马氏距离公式中的S，若始终不 变，则往往显得不妥；若要随聚类过程而不断变化，则会有许多不便。 3兰氏(Lance 和 Williams)距离 当0 ij x，ni, 2 , 1=，pj, 2 , 1=时，则可以定义第i个样品与第j个样品间的 兰氏距离为 = + = p k jkik jkik ij x

9、x xx Ld 1 )( （6.2.3） 这个距离与各变量单位无关，但没有考虑变量间的相关性。由于它对大的异常值不敏感，故 适用于高度偏斜的数据。 4斜交空间距离 由于样品的各个变量之间往往存在不同程度的相关关系，因此有时采用欧氏距离显得 不够理想，有人建议采用斜交空间距离。第i个样品与第j个样品间的斜交空间距离定义为 2 1 11 2 * )( 1 = = p k p l kljliljkikij rxxxx p d 其中 kl r是变量 k x与变量 l x间的相关系数。当p个变量互不相关时，)2( 1 * ijij d p d=，即斜 交空间距离退化为欧氏距离（除相差一个常数倍外） 。

10、以上几种距离的定义均要求变量是间隔尺度的，如果使用的变量是有序尺度或名义尺 度的，则有相应的一些定义距离的方法。下例是对名义尺度变量的一种距离定义。 例例 6.2.1 设有五个变量均为名义尺度变量， 1 x取值V和I， 2 x取值M和Q， 3 x取值S 和A， 4 x取值B、T和F， 5 x取值D和K。现有两个样品 ),( 1 =KTSQVx，),( 2 =KFSMVx 这两个样品的第一个变量都取值V，称为配合的，第二个变量一个取Q，一个取M，称为 学 海 无 涯 不配合的。记配合的变量数为 1 m，不配合的变量数为 2 m，定义它们之间的距离为 21 2 12 mm m d + = （6.2

11、.5） 因此 1 x与 2 x之间的距离为 5 2 。 二、相似系数二、相似系数 聚类分析方法不仅用来对样品进行分类，而且可以用来对变量进行分类，在对变量进 行分类时，常常采用相似系数来度量变量之间的相似性。变量之间的关系越是密切，其相似 系数越接近于 1（或-1） ；反之，它们的关系越是疏远，其相似系数越是接近于 0。聚类时， 比较相似的变量倾向于归为一类，不怎么相似的变量归属不同的类。变量 i x与 j x的相似系 数用 ij C来表示，它一般应满足以下三个条件： （）1= ij C，当且仅当baxx ji +=，a)0( a和b为常数； （）1 ij C，对一切ji,； （） jiij

12、CC =，对一切ji,。 最常用的相似系数有如下两种： 1夹角余弦 变量 i x与 j x的夹角余弦定义为 2 1 1 2 1 2 1 ) 1 ( = = = n k kj n k ki n k kjki ij xx xx C （6.2.6） 它 是 n R中 变 量 i x的 观 测 向 量),( 21 = niiii xxxx与 变 量 j x的 观 测 向 量 ),( 21 = njjjj xxxx之间夹角 ij 的余弦函数，即 ijij Ccos) 1 (=。 2相关系数 变量 i x与 j x的相关系数定义为 ()() ()() 2 1 1 2 1 2 1 )2( = = = n k

13、 j kj n k i ki n k j ki i ki ij xxxx xxxx C （6.2.7） 相关系数我们曾用 ij r来表示，这里表示为)2( ij C是为了与其它相似系数的符号一致。如果 学 海 无 涯 变量 i x与 j x是已标准化了的，则它们间的夹角余弦就是原变量的相关系数。 变量之间常借助于相似系数来定义距离，如令 22 1 ijij Cd= （6.2.8） 样品之间有时也用相似系数来度量样品间的相似性程度。 一般来说，同一批数据采用不同的相似性度量，会得到不同的分类结果。在进行聚类 分析的过程中，应根据实际情况选取好合适的相似性度量。如在经济变量分析中，常采用相 关系数

14、来描述变量间的相似性程度。 一般情况下， 相关系数比其它的相似系数有更强的可变 性，但分辨力要弱一些。 6.3 系统聚类法系统聚类法 系统聚类法是聚类分析诸方法中用得最多的一种， 其基本思想是： 开始将n个样品各自 作为一类， 并规定样品之间的距离和类与类之间的距离， 然后将距离最近的两类合并成一个 新类，计算新类 与其它类的距离（注：未合并的类之间的距离不用重新计算） ；重复进行两 个最近类的合并，每次减少一类，直至所有的样品合并为一类。本节介绍常用的八种系统聚 类方法，所有这些聚类方法的区别在于类与类之间距离的计算方法不同。 以下我们用 ij d表示第i个样品与第j个样品的距离， 1 G，

15、 2 G， 表示类， KL D表示 K G 与 L G的距离。本节介绍的系统聚类法中，除离差平方和法之外，其余所有的方法因一开始 每个样品自成一类，类与类之间的距离与样品之间的距离相同，即 KLKL dD=，所以起初 的距离矩阵全部相同，记为)( )0(ij dD=。 一、最短距离法一、最短距离法 定义类与类之间的距离为两类最近的样品间的距离，即 ( ) ij GjGi KL dD LK = , min （6.3.1） 称这种系统聚类法为最短距离法。用最短距离法的聚类步骤如下： （1）规定样品之间的距离，计算n个样品的距离矩阵 )0( D，它是一个对称矩阵。 （2）选择 )0( D中的最小元素，设为 KL D，则将 K G与 L G合并成一个新类，记为 M G， 即 LKM GGG,=。 （3）计算新类与任一类 J G之间的距离为 ( )( )( ) LJKJij GjGi ij GjGi ij GjGi MJ DDdddD JLJKJ