聚类分析以及有关系数.ppt

《聚类分析以及有关系数.ppt》由会员分享，可在线阅读，更多相关《聚类分析以及有关系数.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一节 距离和相似系数,在对样本（或变量）进行分类时，样品（或 变量）之间的相似性度量工具距离和相似 系数。前者常用来度量样本之间的相似性，后 者常用来度量变量之间的 相似性。样本之间的 距离和相似系数有着各种不同的定义，而这些 定义与变量的类型有非常密切的关系。,第六章 聚类分析,（1）间隔尺度变量： 变量有连续的量来表示， 如长度，重量，速度，温度等。,（2）有序尺度变量：变量度量时不用明确的 数量表示，而是用等级来表示，如某产品分 为一等品，二等品，三等品等有次序关系。,（3）名义尺度变量：变量用一些类表示，这 些类之间既无等级关系也无数量关系。如性别， 职业，产品的型号等。,通常变量按

2、测量尺度的不同可以分为以下三类：,表6.1.1 数据矩阵,一、距离,设 为第 个样品的第 个指标，数据矩 阵列于表6.1.1,在表6.1.1中，每个样品有 个变量，故 每个样品都可以看成是 中的一个点， 个 样品就是 中的 个点。在 中需定义某 种距离，第 个样品与第 个样品之间的距 离记为 ，在聚类过程中，相距较近的点 倾向于归为一类，相距较远的点应归属不同 的类。,距离 的定义一般满足如下四个条件：,第 个样品与第 个样品间的明考夫斯基距离 （简称明氏距离）定义为 这里 为某一自然数。明氏距离有以下三种特 殊形式：,常用的距离有如下几种：,1.明考夫斯基（Minkowski）距离,其中 为

3、第 个变量的样本均值， 为第 个变量的样本方差。,当各变量的单位不同或测量值范围相差很大时，不应直接采用明氏距离，而应先对各变量的数据作标准化处理，然后用标准化后的数据计算距离。最常用的标准化处理是，令,当 时， 可以定义第 个样品与第 个样品间的兰氏 距离为,2.兰氏（Lance和Williams）距离,其中 为样本协方差矩阵。使用马氏距离的好处是 考虑到了各变量之间 的 相关性，并且与各 变量的单位无关。但马氏距离有一个很大的 缺陷，就是马氏距离公式中的 难以确定。,3.马氏（Mahalanobis）距离,第 个样品与第 个样品之间的马氏距离为,其中 是变量 与变量 间的相关系数。当 个变

4、量互不相关时， ，即斜 交空间距离退化为欧氏距离（除相差一个常数 倍外）。,4.斜交空间距离,第 个样品与第 个样品间的斜交空间距离定义为,例6.2.1 某高校举办一个培训班，从学员的资 料中得到这样六个变量：性别 ，取值为男 和女；外语语种 ，取值为英，日和俄；专 业 ，取值为统计，会计和金融；职业 ， 取值为教师和非教师；居住处 ，取值为校 内和校外；学历 ，取值为本科和本科以下。,现有两名学员：,这两名学员的第二个变量都取值“英”，称为 配合的，第一个变量一个取值为“男”，另一 个取值为“女”，称为不配合的。一般的，若 记配合的变量数为 ，不配合的变量数 为 ，则它们之间的距离可定义为,

5、故按此定义本例中 与 之间的距离为 。,二 相似系数,变量 与 的相似系数用 来表示，它一 般应满足如下三个条件：,最常用的相似系数有如下两种,1.夹角余弦,变量 与 的夹角余弦定义为,它是 中变量 的观察向量 与变量 的观察向量 之间的夹角 的余弦函数，即 。,变量 与 的相关系数为,2.相关系数,常量之间常常借助于相似系数来定义距离， 如令,第二节 系统聚类法,系统聚类法（hierarchical clustering method）的基本思想是：开始将 个样本各自作为一类，并规定样本之间距离和类与类之间的距离，然后将距离最近的合并成一个新类，计算新类与其他类的距离；重复进行两个最近类的合

6、并，每次减少一类，直至所有的样品合并为一类。,用 表示第 个样品与第 个样品的距离， 表示类， 表示 与 的距离。 本节介绍的系统聚类方法中，所有的方法一开 始每个样品自成一类，类与类之间的距离与样 本之间的距离相同（除离差平方和法之外）， 即 ，所以起初距离矩阵全部相同， 记为,一 最短距离法,类与类之间的距离为两类最近样 本之间的距离，即 称这种系统聚类法为最短距离法（single linkage method）。,（一）定义,（二）最短距离法的聚类步骤如下；,（1）规定样本之间的距离，计算 个样本 距离矩阵 ，它是一个对称矩阵。,（2）选定 中的最小元素，设为 ，则将 和 合并成一个新类

7、，记为 ，即 。,（3）计算新类 与任一类 之间距离的递推公式,在 中， 和 所在的行与列合并成一个新行新列，对应 ，该行列上的 新距离值由（6.3.2）式求得，其余行列上的距离值不变，这样就得到新的距离矩阵，记为 。,（4）对 重复上述对 的两步得 ，如此下去直至所有元素合并成一类为止。,如果某一步 中最小的元素不止一个，则称此现象为结（tie），对应这些最小元素的类可以任选一类合并或同时合并。,（1）样品间采用绝对值距离（这时它与 其它明氏距离完全相同），计算样品间的距 离矩阵 ，列于表6.2.1。,例6.2.1 设有五个样品，每个只测量了一 个指标，分别是1，2，6，8，11，试用最 短

8、距离法将它们分类。,表 6.2.1,（2） 中最小元素是 ，于是将 和 合并成 ，并利用（6.3.2）式计算 与其他类的距离，列于表6.2.2,表6.2.2,（3） 的最小元素是 ，合并 和 成 ， 与其他类之间的距离计算为 表6.2.3,表6.2.3,（4） 中的最小元素是 ，将 和 合并为 ，新的距离矩阵列于表6.2.4,表6.2.4,（5）最后将 和 合并为 ，这时所有五 个样品聚为一类，过程终止。,将上述聚类过程画成一张树形图（或称谱系图，dendrogram），如图6.2.1 所示。,图6.2.1 最短距离法树形图,类与类之间的距离定义为两类最远样品间的距离，即 称这种系统聚类法为最

9、长距离法（complete linkage method）。,二 最长距离法,最长距离法与最短距离法并类步骤完全相同， 只是类间距离的递推公式有所不同。设某步 将类 和 合并成新类 ，则 与任 一类 的距离为,对例6.2.1 采用最长距离法，其树形图如图6.2.2所示,例 6.2.2 对305 名女中学生测量八个体型指标：,相关矩阵列于表6.2.5，我们用相似系数 来度量各变量之间的相似性。,表6.2.5 各变量之间的相关系数,图6.2.3 八个体型变量的最长距离法树形图,类与类之间的距离既不取两类最近样品间 的距离，也不取两类最远距离间的距离，而是 取介于两者之间的距离，称为中间距离法 （m

10、edian method）。,中间距离法,设某一步将 和 合并为 ，对于任一 类 ，考虑由 为边长组成的 三角形（如图6.2.4所示），取 边的中线 作为 ，由初等平面几何可知， 的计算 公式为,中间距离法可推广为更一般的情形，将 (6.2.5)式三项的系数依赖于某个参数 ，即 这里 ，这种方法称为可变法。,其中 和 分别为类 和 的样品个数， 为 中的样品 与 中的样品 之间的距离。,类平均法,类平均法(gverage linkage method)有两种 定义，一种定义方法是类与类之间距离定义 为所有样品对之间的平均距离，即定义 和 之间的距离为,递推公式为：,另一种定义方法是定义类与类之

11、间的平方距 离为样品对之间的平方距离的平均值，即,它的递推公式类似于(6.2.8)式，即,在递推公式(6.2.10)式中， 的影响没有被反 映出来，为此可将该递推公式进一步推广为,其中 ，称这种系统聚类方法为可变类 平均法。,对例6.2.1采用(6.2.9)式的类平均法进行聚类。对 的每个元素都平方，则使用递推公式会比较方便。,(1) 计算 ，见表 6.2.6。,表6.2.6,(2)找 中的最小元素，它是 ，将 和 合并为 ，计算 与 的距离。这时 ， 由(6.2.9) 式计算得,同样可算得 和 ，列于表6.2.7。,表6.2.7,(3)对 重复上述步骤 ，将 和 并为 ， 得平方距离矩阵 (

12、见表6.2.8)，再将 和 合并成 得 (见表6.2.9)，最后将 和 合并为 ，聚类过程终止。,表6.2.9,表6.2.8,树形图如图6.2.5所示。,类与类之间的距离定义为它们的重心（均值） 之间的欧氏距离。设 和 之间的重心分 别为 和 ，则 与 之间的平均距离为 这种系统聚类法成为重心法。,五 重心法,它的推递公式为,类中各样品到类重心（均值）的平方欧氏距 离之和称为（类内）离差平方和。设 和 合并成新类 ，则 和 的离差平 方和分别是,离差平方和法（Ward方法）,如果 和 这两类相距较近，则合并后 所增加的离差平方和 应较小； 否则应较大。于是 和 之间 的平 方距离定义为 这种系

13、统聚类法称为离差平方和法或Ward 法（Wards minimun variance method）。,也可以表达为,离差平方和法的平方距离推导公式为,对例6.2.1采用离差平方和法进行聚类，聚类过 程中的平方距离矩阵列于表6.2.10至表6.2.13， 树形图如图6.2.6所示。并类的次序为 和 合并成 ， 和 合并成 ， 和 合 并成 ，最后 和 合并成 。,表6.2.10,表6.2.11,表6.2.12,表6.2.13,例6.2.3 表6.2.14 列出了1999年全国31个省、 市和自治区的城镇居民家庭平均每人全年消费 性支出的八个主要变量依据。这八个变量是,表6.2.14 消费性支出

14、数据 单位：元,图6.2.7和图6.2.8中的聚类距离是经正规化之后的距离(见附录6-1中的说明(5)和(8),图6.2.9中的聚类“距离”是半偏 (见(6.2.23)式)。从这三个树形图来看，Ward方法似乎更符合我们的聚类要求，它将31个地区分为以下三类： 第类：北京、浙江、上海和广东。这些都是我国经济最发达、城镇居民消费水平最高的沿海地区。 第类：天津、江苏、云南、重庆、河北、新疆、山东、湖北、四川、湖南、福建、广西、海南和西藏。这些地区在我国基本上属于经济发展水平和城镇居民消费水平中等的地区。 第类：山西、甘肃、内蒙古、辽宁、黑龙江、吉林、青海、宁夏、安徽、贵州、河南、陕西和江西。这些

15、地区在握国基本上属于经济较落后地区，城镇居民消费水平也是较低的。,如果分为五类，则广东和西藏各自为一类。,Lance和Williams与1967年将这些递推公式 统一为：,其中 、 、 和 是参数，不同的系 统聚类法，它们有不同的取值。表6.2.15列出 了上述八种方法和四个参数的取值。,七、系统聚类法的统一,表6.2.15 系统聚类法参数表,八 系统聚类法的两个性质。,（一）单调性,令 是系统聚类法中第 次并类时的距离， 如例6.3.1中，用最短距离法时，有 ，且有 。如 果一种系统聚类法能满足 ， 则称它具有单调性。,设 和 是两个元素非负的同 阶矩阵，若 ，则记作 。,(二）空间的浓缩与

16、扩张,设有两种系统聚类法，它们在第 步的 距离矩阵分别为 和 若 则称第一种方法比第 二种方法更使空间扩张，或第二种方法比第 一种方法更使空间浓缩。,以类平均法为基准，其他方法都与它作比较有如下一些结论：,即最短距离法和重心法比类平均法更使空间浓缩。,即最长距离法比类平均 法更使空间扩张。,即这时可变类平均法比类平均法更使空间浓缩；当 即此时可变类平均法比类平均法更使空间扩张。,九 类的个数,通过观察树型图，给出一个你认为适合的阈 值T，要求类与类之间的距离要大于T，有些 样品可能会因此而归不了类或只能自成一类。 这种方法有比较强的主观性，这是它的不足 之处。,（一）给定一个阈值T,如果样品只

17、有两个或三个变量，则可通过观 测这些数据的散点图来确认类的个数。对于 三个变量，可使用SAS软件通过旋转三维坐 标轴从各个角度来观测散点图。如果变量个 数超过三个，则可使原来变量综合成两个或 三个综合变量，然后再观测这些综合变量的 散点图。,(二）观察样品的散点图,设总样品数为 ，聚类时把所有样品合并 为 个类 ，类 的样品数和重心 分别是 和 ，则 ， 所有样品的总重心 ，令所有 样品的总离差平方和为,（三）使用统计量,1 统计量,类 中样品的类内离差平方和为,个类的类内离差平方和之和为,可作如下分解,再令,值越小（即 越大），表明类内离差 平方和之和在总离差平方和中所占的比例越 小，也就说

18、明 个类分得越开。因此， 统 计量可用于评价合并成 个类时的聚类效果， 值越大，聚类效果越好。,2 半偏 统计量,其中 ，半偏 值是上一 步 值与该步 值之间差，因此半偏 值 越大，说明上一次聚类的效果越好。,3 伪F统计量,（6.2.23）式也可写成,与 的作用一样，它也随分类个数 的减少而变小。 可看作一个调整系数， 能够使得伪F值不随 的减少而变小，并且 可以直接根据伪F值的大小作出分几类为合适 的判断。伪F值越大，表明此时的分类效果越 好。伪F统计量不具有F分布。,伪 值大表明 和 合并成新类 后，类 内离差平方和的增量 相对于原 和 两类的类内离差平方和是大的，这说明被合并 的两个类

19、 和 是很分开的，也即上一次聚 类的效果是好的。伪 统计量是确定类个数的 有用指标，但不具有象随机变量 那样的分布。,4 伪 统计量,第四节 动态聚类法,基本思想：选择一批凝聚点或给出初始的 分类，让样品按某种原则向凝聚点凝聚，对凝 聚点进行不断的修改和迭代，直至分类比较合 理或迭代比较稳定为止。类的个数k 可以事先 指定，也可以在聚类过程中确定。,（3）重复步骤（2），直至所有的样品都不能再分配为止。,k均值法是由麦奎因（MacQueen，1967）提出并命名的一种算法。其基本步骤为：,（1）选择k个样品作为初始凝聚点，或者将所 有样品分成k个初始类，然后将这k个类的重心（均值）作为初始凝聚

20、点。,（2）对除凝聚点之外的所有样品逐个分类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点更新为这一类目前的均值，直至所有的样品都归了类。,例 6.3.1 对例6.2.1采用k均值法聚类，指定 k=2，具体步骤如下：,（1）我们随意将这些样品分成 和 两类，则这两个初始类的均值分别是 和 。,（2）计算1到两个类（均值）的欧氏距离,由于1到 的距离小于到 的距离，因 此1不能重新分配，计算6到两个类的距离,故6应该分配到 中，修正后的两类为 ，新的类均值分别为 和 。,结果8 重新分配到 中，两个新类为 ，其类均值分别为 1 和 。,计算,再计算,重新分配 2 到 中，两个新类为 ,其类均值分别 为 和 。,（3）再次计算每个样品列类均值的距离，结 果列于表6.3.1。最终得到的两个类为 和 。,表6.3.1 各样品列类均值的距离,例6.3.2 对例6.2.3使用k均值法进行聚类，聚 类前对各变量作标准化变换，聚类结果如下：,第1类 ：北京、上海和浙江,第2类 ：广东,第3类 ：天津、江苏、福建、山东、湖南、 广西、重庆、四 川和云南,类均值之间的距离列于表6.3.2,第4类 ：河北、山西、内蒙古、辽宁、吉林、 黑龙江、安徽、江西、河南、湖北、海南、 贵州、陕西、甘肃、青海、宁夏和新疆,第5类 ：西藏,表6.3.2 类均值之间的距离,