（计算机应用技术专业论文）动态聚类法研究.pdf

西南大学计算机与信息科学学院2 0 0 3 级硕士学位论文 动态聚类法研究 计算机应用技术专业硕士研究生徐艺萍 指导教师邓辉文教授 摘要 聚类分析是认识事物的基本途径之一。通过聚类分析，可以更清楚地认识事物的本质特 征。目前的各种聚类分析方法中，动态聚类法是最为普遍的一种。本文主要从静态样本和动 态样本两方面对动态聚类法进行了研究。 一般的动态聚类算法都是针对静态样本数据的，其聚类结果不仅依赖初始分类，而且易 陷入局部极小。而最近邻聚类算法正好能弥补该类聚类算法的不足。但现有的最近邻聚类算 法的聚类半径一般都是随机选择或是根据经验确定的，且没有相应的有效性函数对聚类结果 进行评价。基于以上原因，本文提出了针对静态样本进行聚类的一种新的最近邻聚类算法， 并给出了相应的实验分析。 另外，在现有的诸多领域，如数据挖掘、大型数据库和互联网信息处理等，其数据都是 动态的。a r t 2 神经网络虽能很好地实现这类动态数据的聚类，但a r t 2 网络本身存在的问题 又限制了它在这方面的应用。鉴于此，本文又提出了一种改进的a r t 2 网络学习算法来实现动 态样本的聚类，同时给出了该方法的实验仿真结果。 关键词：静态样本动态样本动态聚类最近邻聚类算法a r t 2 神经网络 西南大学计算机与信息科学学院2 0 0 3 级硕上学位论文 a b s t r a c t c l u s t e r i n ga n a l y s i si so n eo f t h eb a s i cw a y st ou n d e r s t a n dt h i n g s t h ee s s e n t i a l c h a r a c t e r so f t h i n g sc a nb ec l e a r l yr e c o g n i z e db yc l u s t e r i n ga n a l y s i s u pt on o w , d y n a m i cc l u s t e r i n gm e t h o di st h em o s tp r e v a l e n to n ei na l ls o r t so fc l u s t e r i n ga n a l y s i s m e t h o d s s ot h ep a p e rr e s e a r c h e so nd y n a m i cc l u s t e r i n gm e t h o dm o s t l yf r o mt w o a s p e c t s 一s t a t i cs a m p l e sa n dd y n a m i cs a m p l e s t h e g e n e r a ld y n a m i cc l u s t e r i n ga l g o r i t h m sa r eu s e db ys t a t i cs a m p l e s t h er e s u l t s o f c l u s t e r i n gn o to n l yr e l yo nt h eo r i g i n a lc l a s s i f i c a t i o n ，b u te a s i l yg e ti n t ol o c a l o p t i m u m a n dt h en e a r e s tn e i g h b o rc l u s t e r i n ga l g o r i t h mc a n j u s tm a k eu pt h e s e d i s a d v a n t a g e so f d y n a m i cc l u s t e r i n ga l g o r i t h m s h o w e v e r , t h ec l u s t e r i n gr a d i u so f t h e p r e s e n t n e a r e s tn e i g h b o rc l u s t e r i n ga l g o r i t h mi ss e l e c t e dr a n d o m l yo rc o n f i r m e db y e x p e r i e n c e ，a n dt h e r ei sn oc o r r e s p o n d e n tc l u s t e rv a l i d i t yf u n c t i o nt oe s t i m a t et h e r a t i o n a l i t yo f c l u s t e r i n gr e s u l t s b a s e do nt h e s er e a s o n sa b o v e ，an e wn e a r e s tn e i g h b o r c l u s t e r i n ga l g o r i t h mi sp r o p o s e di nt h i sp a p e r , a n dc o r r e s p o n d e n te x p e r i m e n t a la n a l y s e s a r ea l s og i v e no u t i na d d i t i o n , t h ed a t ai sd y n a m i ci na g o o dm a n ye x i s t i n ga r e a s ，s u c ha sd a t am i n i n g ， l a r g ed a t a b a s ea n di n t e m e ti n f o r m a t i o np r o c e s s i n g ，e t c a l t h o u g ha r t 2n e u r a ln e t w o r k c a nw e l lr e a l i z et h ec l u s t e r i n go fd y n a m i cs a m p l e s ，t h ep r o b l e m sa r i s i n gf r o ma r t 2 n e u r a 1n e t w o r ki t s e l fr e s t r i c t e di t sa p p l i c a t i o n w h e r e a s ，a ni m p r o v e da r t 2n e u r a l n e t w o r kc l u s t e r i n ga l g o r i t h mi sp r o p o s e dt or e a l i z et h ec l u s t e r i n go fd y n a m i cs a m p l e s ， a n dt h es i m u l a t i o nr e s u l t sa r eg i v e no u t 砒t h es a m et i m e k e yw o r d s ：s t a t i cs a m p l e s ，d y n a m i cs a m p l e s ，d y n a m i cc l u s t e r i n g ，n e a r e s t n e i g h b o rc l u s t e r i n ga l g o r i t h m ，a r t 2n e u r a ln e t w o r k l i 独创性声明 学位论文题目：盘查鐾娄洼珏巍 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西南大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者：偌。气薄 签字日期：j 一一年涉月j 【日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名：练也阵 签字日期：印口i 年争月话日 学位论文作者毕业后去向： 导师签名：识采狰。 签字日期：碑q - 月彬日 工作单位：酉直登垫太堂电话：( q 81 ! q g ! 5 通讯地址：堕刖鲞绫豳壹亘直盘拉太堂堡堂瞳邮编：i ! ! ! ! ! 第一章绪论 1 1 引言 第一章绪论 聚类分析( c l u s t e ra n a l y s i s ，c a ) 是多元统计分析的一个重要分支它是把一个没有类别 标记的样本集按某种相似性准则划分成若干个子集( 类) ，使每一类中的样本点尽可能相似， 而不同类中的样本点之间时差异尽可能大，其实质是寻找隐藏在数据中不同的数据模型。目 前，聚类分析在我国地质、考古、天气预报、工农业、医学等领域均有广泛的应用。由于学 科问的相互渗透，新边缘学科的兴起，数学与电子计算机的应用日益广泛，已使得聚类分析 方法逐步成为了科学研究中不可缺少的手段。 目前，常用的聚类分析方法有系统聚类法、动态聚类法和神经网络聚类法，其中动态聚 类法在各个领域中都得到了广泛应用，显示了其独特的优越性。但是现有的动态聚类方法( 如： f c m ，k 一均值聚类算法等) 仍然存在着诸多问题。如何来解决动态聚类方法存在的问题，使动 态聚类法应用更为广泛，将是一个值得深入研究的课题。 1 2 动态聚类法存在的问题 动态聚类法是基于样本问相似性度量的间接聚类方法。该方法按照样本问的相似性把样 本集划分成若干个子集，每个子集即为一类。与系统聚类法相比，动态聚类法具有以下两个 优点： ( 1 ) 在聚类过程中，样品的属类可以发生改变。 ( 2 ) 当样品数较大时，计算量较小，占用的内存空间较少。 尽管如此，在对某些样品分类时动态聚类法却经常出现不尽人意的结果。以著名的h a l d 水泥样品释热实验数据吲为例，从文献【8 】中可以看到，当k = 2 时，分类结果 g 1 = ( 1 ，2 ，4 ，8 ，1 1 ，g 2 = 3 ，5 ，6 ，7 ，9 ，1 0 ，1 2 ，1 3 j 是完全合理的但是当k = 3 时，却有 g i = 1 ，2 ，4 ，8 ，g 2 ：5 ，1 0 ，11 ，g 3 = 3 ，6 ，7 ，9 ，1 2 ，1 3 ) 。虽然从总体上说这样分类可咀， 但是从水泥样品释热量y 的大小显见发生了交叉分类现象，这在实际工作中( 如工厂产品等 级、城镇土地级别划分) 是不允许出现的。可见，现有的动态聚类法也存在着不足。归纳起来， 主要存在以下不足： 第一章绪论 ( 1 ) 在分类前需随机给定一个初始分类聚类模型的类中心和分类数，即选择儿个“凝 聚点”，让样品向最近的凝聚点凝聚。这样由点凝聚成类，得到的就是初始分类。“凝 聚点”一旦确定，不管合不台理，在聚类过程中都不会改变。可见，初始分类对最终 聚类结果有着很大的影响。 ( 2 ) 容易陷入局部最优。因为现有的动态聚类算法( 如爬山法、k 一均值聚类算法等) 几乎都 要涉及到对目标函数取最小值，而目标函数又是非凸的。 ( 3 ) 分类前所有的样本点都必须己知( 本文称此为静态样本，对这种数据聚类称基于静态 样本的聚类分析) ，这种静态样本聚类分析在实际工程应用中受到许多限制，因为许 多工程的运行性态观测都是时效性极强的动态过程，它们的样本数据都是实时产生的 ( 本文称此为动态样本，对这种数据聚类称基于动态样本的聚类分析) 。 ( 4 ) 易出现模式交混现象。 1 3 最近邻聚类算法的主要思想及存在的问题 最近邻聚类算法是一种最简单、最基本的聚类算法，它的主要思想是首先把第一个数据 作为第一组的聚类中心。接下来，若某个数据距该聚类中心的距离d 小于预期值尺( 即聚类半 径) ，就把这个数据放到此组中：否则，把该数据设为新一组的聚类中心，直到把所有的数据 归类为止。 该算法在聚类前不需要给定初始分类，聚类过程中也不涉及到对目标函数求导f 即可以避 免陷入局部最优) 。可见，它能有效解决动态聚类算法中存在的前两个问题，是一种非常适合 静态样本聚类的算法。但是该算法中聚类半径的选择是当前的一大难题，并且也没有一个有 效性函数来对聚类结果进行评价。基于此，本文提出了一种新的最近邻聚类算法对静态样本 进行动态聚类。 1 4a r t 神经网络的产生、发展及存在的问题 自适应共振网络( 简称a r t ) 是由美m b o s t o n 自适应系统中心的g r o s s b e f g 和 c a r p e n t e r - t - 1 9 8 7 年3 月提出的，是一类比较适合用于模式聚类的神经网络。它的发展主要经历 t r 4 阶段：a r t l l 9 i ，a r t 2 1 1 q 和a r t 3 t “i ，它们在功能和实现方面形成了一个不断完善的系 列。a r t i 是最基本的，它只能处理离散数据特征；a r t 2 既可以处理离散数据特征，也可以处 理模拟数据特征：a r t 3 结构最复杂，它将人脑模型中的神经元突触生物化学运行机理应用于 神经网络。其中a r t 2 型神经网络使用最为广泛，本文主要研究a r t 2 型神经网络。 2 第一章 绪论 a r t 2 网络用于聚类分析具有在学习新的模式时不破坏己存储的模式的优点，既可以快速 识别己存储的模式，又能迅速适应未学习过的新对象，快速实现动态聚类。同时，它还可以 通过调整警戒参数p 来协调网络的稳定性和可塑性，在实际应用中可以适应不同程度的分类 要求。因此，r t 2 算法是一种非常适合动态样本聚类的算法。但是传统的a r t 2 网络存在权值 的初始化方法和参数d 的选择不尽合理，存在模式漂移现象和在处理数据过程中丢失了幅度 信息等缺点。鉴于此，本文提出了一种改进的a r t 2 网络学习算法对动态样本进行聚类。 1 5 内容安排 全文共分六章。 第一章绪论 概要介绍了聚类分析的重要性和目前的动态聚类法存在的问题。简单介绍了适合动态聚 类的最近邻聚类算法和川n 神经网络学习算法存在的问题。指出全文的研究重点是对最近邻聚 类算法和a r t 2 神经网络学习算法的改进及其在聚类分析中的应用。 第二章聚类分析 本章主要阐述一些聚类分析的相关知识和概念。包括数据预处理、聚类统计量、类的定 义和特征、类间距离、常用聚类方法、聚类结果分析等内容。通过本章可以对模式聚类有比 较全面的了解。 第三章a r t 2 神经网络的结构和原理 a r t 2 网络是a 础r 网络中的一种，可以用于处理连续信号模式，非常适用于模式聚类分析 问题。本章从a 瑚r 网络的一般结构开始，详细讲述了传统a k r 2 网络的结构、原理和工作步骤。 以便于进一步提出对它的改进。 第四章基于静态样本的动态聚类算法 本章首先介绍了动态聚类法和最近邻聚类法的研究现状在此基础上提出了一种新的最 近邻聚类算法。详细阐述了这一新算法中初始聚类半径的确定方法，聚类过程中半径的修改 方法，并提出了一有效性函数对聚类结果进行评价。虽后通过实例分析证明了采用该方法对 静态样本进行聚类不仅能加快聚类的速度、提高聚类的精度和有效地跳出局部最优，而且特 别适合大样本聚类。 第五章基于动态样本的聚类算法 本章首先分析了传统a r t 2 网络存在的问题，在此基础上提出了一种改进的a 瑚眩网络学 习算法。详细阐述了改进的a r t 2 网络学习算法中参数的选取方法、权值的初始化方法、权值 3 第一章绪论 的修正方法和如何恢复幅度信息以及该算法的工作步骤。最后通过实例分析证明了采用该算法 对动态样本进行聚类不仅能有效解决模式漂移问题、充分利用幅度信息和提高聚类速度，而且 还能减少或避免模式交混现象。 第六章总结与展望 对全文的内容进行总结，并指出今后的研究方向。 1 6 本章小结 本章首先概要介绍了聚类分析的重要性和目前的动态聚类法存在的问题。然后介绍了适 合动态聚类的最近邻聚类算法和a 】册神经网络学习算法存在的问题。最后给出了全文的内容组 织安排。 4 第= 章聚类分析 第二章聚类分析 “聚类”顾名思义就是将性质相同或相近的对象聚成一类，并按照这些对象的定性或 定量特征数值将其分组归类。为此，需要确切地描述和度量有关属性，并从中比较对象间 的相似程度，把最接近的对象归并成类。在聚类分析中常把事物称为样品或样本，把他们 的属性称为变量或指标，变量的描述可以是定性的或定量的。若用连续的定性量测定，则 称为间隔尺度；用有序的等级表示，称为有序尺度；也可用一些只有名字，而无等级和数 量关系的类比来描述，称为名义尺度。 根据对象的不同，聚类分析有两种类型：针对样品的为样品聚类，亦称q 型群分析；针 对变量的为变量聚类，亦称r 群分析i ”】。 2 1 数据预处理 设聚类问题中有, 个样品：x ( f - l ，2 ，月) - 对每个样品选择了p 个变量，用问隔 常称此为样本数据矩阵。其中每一行向量表示第f 个样品p 个变量的观测值： x = ( h ，x j2 , - - , x , p )( 2 2 ) 而每一列向量表示第，个变量在n 个样品中的观测值： x ；= ( x j j , t j ，h ) ( 2 3 ) 由于各变量表示样品的各种性质，往往使用不同的度量单位，观测值也可能相差十分悬 殊。这样，绝对值大的变量其影响可能会盖住绝对值小的变量使后者应有的作用得不到反 映。为了确保各变量在分析中的地位相同，需要对观测数据进行预处理。预处理的对象可以 是x 中的每一列向量，即对每一个变量做变换；也可以是x 中的每一行向量，即对每一个样 品做变换。对每一变量的变换有中心化和标准化，对每一样品的变换有归一化。 第二章聚类分析 2 1 1中心化 中心化是要使各个变量的观测值都有相同的基点，通常是在观测值上减去相应变量的平 均值。记第j 个变量的平均值为： 一x j = 1 n 智n x ， - ，= l ，2 ，p 对第个变量的r 1 个数据做中心化变换则为 = 一x ， i = l ，2 ，。一，n ( 2 4 ) ( 2 5 ) 经此变换后各个变量的均值都为0 ，即各变量的取值基点相同都为0 。也可以做如下变换 2 一m 。i 。n ( x ，) ，= 1 ，2 ，p 它将使各变量的最小值为0 ，称此变换为正规化。 2 1 2 标准化 ( 2 6 ) 标准化是在中心化的基础上再作变换，它使各变量的变化范围相等。当用不同的方法衡 量变化范围时，就有不同的标准化变换方法。常用的有： ( 1 ) 标准差标准化 记第j 个变量的标准差为： 墨= 对第个变量的竹个数据做标准差标准化为 - = 1 ，2 ，p x ；2 孚h ，z ，门 经此变换后各变量的均值都为0 ，标准差都为1 。 ( 2 ) 极差标准化 记第_ ，个变量的极差为： r ，2m 。a ；x 。( x i ，) 一罂，鎏( x 口) ，= 1 ，2 ，p 对第，个变量的n 个数据做极差标准化为： x ：。字 渊，2 ，n 6 ( 2 7 ) ( 2 8 ) ( 2 1 0 ) 第= 章 聚类分析 经此变换后各变量的均值都为0 ，极差都为l 。 ( 3 ) 极差正规化 对第，个变量的n 个数据做极差正规化为： i = 1 ，2 ，一，”( 2 1 1 ) 经此变换后各变量的最小值都为0 ，极差都为1 。 经标准化变换后，各变量基点相同，变化范围也相同了。 2 1 3 归一化 每一个样品可以视为p 维空间中的一个向量，也可以看作p 维空间中的一个样品点。 这些样品点到原点的距离可能各不相同，亦即每个向量的长度各不相同。有时候为了便于分 析问题，要将这些样品点变换到同一个单位圆或者高维球面上，也就是使各向量的长度( 模) 相等。这就需要对样本数据进行归一化处理。通常对向量进行归一化就是使它们的模变为1 。 向量x 的模为： l - 以f 再可 ( z 1 2 ) 对向量x 进行归一化，即： x ，：_ 三l 1 n l ，l 三堕_ 、忆l l ，l l x 1 经此变换后各向量的模都为1 ，各样品点均位于同一球面上。 2 2 聚类统计量 f 2 1 3 ) 聚类统计量有很多种，其中常用的有距离、相似系数和关联系数。距离和相似系数都是 用于度量分类对象之间相似程度的统计量，适用于可用连续数量来表示的变量。它们的定义 与聚类分析的类型有关。通常相似系数的取值范围都在 - 1 ，l l z i e ，而距离可以是【o ，一】。 关联系数则是用于描述定性数据之间的关联强度的统计量。 距离和相似系数的使用范围各不相同。在有的情况下只能使用距离来度量对象之问的 相似程度，比如图2 1 所示的例子。 图2 1 表示在病理分析时发现的肺癌患者的头发中微量元素的含量关系。如果以c r ，c d ， a s 含量的一个函数作为变量x i ：x l = f ( c r ，c d ，a s ) ；以s e 、z n 含量的另一个函数作 掣 第二章 聚类分析 为变量x2 ：x ! = g ( s e ，z n ) 。以x2 为横坐标，x l 为纵坐标，每个检查者按这些微量 元素的含量在坐标平面中表示为一个样品点。现要对所有样品按照初期患者、后期患者和健 康人分为三类，在这种情况f ，就只能采用距离来度量每个样品之间的相似程度。 图2 1 肺癌患者与微量元素 患者 x 2 在有的情况下，则只能使用相似系数来度量对象之间的相似程度。比如浓度配方问题。 有h 个溶液样品，给出了每个样品中所含溶质和溶剂的质量以溶质质量为纵坐标，溶剂 质量为横坐标，所有样品点位于二维坐标平面上，如图2 2 所示。 溶质质量 图2 2 溶液浓度配方 量 现要将所有溶液样品按浓度进行分类，浓度接近的认为是同一类。显然，这时候样品 点之间的距离是没有意义的，只能采用相似系数来度量样品的相似程度。 还有一些情况下，用距离和相似系数皆可度量对象之间的相似程度。 2 2 1 距离 距离是q 型聚类分析常用的分类统计量，在r 型聚类分析中应用较少。对于有p 个变量 8 第二章聚类分析 的样品来说，n 个样品可以表示成p 维空间中的n 个点，当然可以用点问距离度量样品问 的接近程度。常用d 。表示样品i 与样品，之问的距离。两个样品间的距离在。一o 。之间 距离越小，两个样品越接近。在聚类分析中，最常用的距离定义有以下几种 ( 1 ) 明氏( m i n k o w s k i ) 距离 明氏距离适用于一般的欧氏空问。 当g = 1 时，明氏距离即为绝对值距离 当q = 2 时，即为欧氏( e u c l i d ) 距离 d ( 2 ) = ( ( x 扩x 肛) 2 ) “2 当q = o o 时，即为切比雪夫距离 q 0 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) d 口( 。) = m 一a xl x n x p i ( 2 1 7 ) ( 2 ) 马氏距离( m a h a l a n o b i ) 考虑到样品各变量的观测值往往为随机变量，因此第i 个样品的p 个变量的观测值 x ，= ( x n ，x j 2 ，x p ) 7 应是p 维的随机向量。由于随机向量有一定的分布规律，各个 分量之间又可能相关，因此两个样品作为两个随机向量的个体用马氏距离更为合适： d u ( m ) = ( x ，一x 1 ( x ，一x ，) ( 2 _ 1 8 ) 其中是随机向量的协方差矩阵。 ( 3 ) 兰氏距离( c a n b e r r a ) 州驴吉毫剿 2 2 2 相似系数 对于p 维空间中的两个向量，可以用相似系数来度量它们之间的相似度。设表示第 9 r ， ( 一一 )g( u d t x ， = ) i ( d 第二章聚类分析 i 个和第，个向量问的相似系数，则日。应满足以f 条件 绝对值不大于1 ，即对所有的f 、- ，恒有i 口u i 1 。同时，当且仅当两个向量存在 线性关系，即x ，= c x j ( c 为不等于。的任一常数) 时ti 口u i _ 1 才成立； 对称性，即对所有的i 、_ 恒有口u = 口_ 。 两个对象间的相似系数也有多种定义形式，常见的有以下几种： ( i ) 夹角余弦 夹角余弦是经常使用的一种相似系数，对q 型聚类和r 型聚类均适用。其取值范围为 一1 1 】。 q 型聚类 在q 型聚类分析中，样品作为p 维空间中的向量，它们的相似系数可用两个向量之问 的夹角余弦来表示，样品i 和样品_ ，的夹角余弦可记为： x 且 q 口= c o s ( o ) = 以向量点积的形式可以表示为 i ，_ = 1 ，2 ，n( 2 2 1 ) r 型聚类 在r 型聚类分析中，分类对象为变量，每一变量可以看作一维空间中的向量，第_ ，个变 量可以表示成式( 2 3 ) 的向量。变量间的接近程度可用夹角余弦表示。可记为： z u q = c o s ( 8 口) = i ，= 1 ，2 ，p ( 2 2 2 ) 以向量点积的形式可以表示为式( 2 2 1 ) 的形式，只是i ，j = 1 ，2 ，p 。 ( 2 ) 相关系数 相关系数经常用于r 型聚类分析，在q 型聚类分析中应用较少。在r 型聚类分析中，第i 个变量和第，个变量之间的相关系数可表示为： 1 0 、，一i 王o ，一iii k 一 “一埘 d x d i = v g 第二章聚类分析 ( x 。，一x ，) ( x u ( 2 2 3 ) 其“，i 为媳；= 吉喜- ，。1 智 x 。 若将观测值视为随机变量，则每个变量为n 维随机向量。式( 2 2 3 ) 实际上就是两个”维 随机向量之间的相关系数的估计值。 ( 3 ) 算术平均最小法 0 = m i n ( x x 业) 二! 一 妻兰( z 。+ 工且) = l f 2 2 4 ) ( 4 ) 其它相似系数表示法 除了夹角余弦和相关系数以外系数。在一些特定场合，还会用到其它形式的相似系数。 比如在a r t 2 神经网络中，计算两个模式x l 和x 2 的相似度有时会用到以下方法： 称，为x t 和x 2 的三角相似度，其取值范围为【o ，l 】。三角相似度的原理如图2 3 所示。 图2 3 三角相似度 图2 3 中两模式x l 和x 2 按照向量运算的平行四边形法则相加，其和向量为x l + x 2 。x i 、 x ：和x ，+ x ：三个向量构成一三角形式c z 笛，又可化为：，= 世 隶焉，可见，三角 第二章聚粪分析 相似度的几何意义就是三角形的一边与另两边之和的比值。显然，如果x 。和x2 方向越接 近，二者之间的夹角越小，值就越大。当x i 和x 2 方向相同时，r 取最大值1 ；当x l 和x ，方向相反时，取最小值0 。因此r 的大小反映了两模式的相似程度。 2 2 3 关联系数 距离和相似系数都适用于可用连续数量来表示的变量，但还有一些变量只可定性的加以 描述，这时就要用到关联系数。关联性的广义含义是用来描述定性数据之间的关系，而关联 系数就是关联强度的一个指标。 关联系数有几十种甚至上百种。多态变量之间的关联常用列联表来表示，列联表在气象 分析中经常用到。列联表如表2 1 。 表2 1 列联表 多态定性变量的关联系数主要有以下几种 ( 1 ) 与z2 有关的关联系数 z 2 = 九s s 毫凳n ，。n ，i o 。”一 z2 本身就是一种关联系数，可记为： 吲驴心陲击一 1 2 ( 2 2 7 ) 第二章聚类分析 ( 2 ) 最优预测系数 为了说明两个变量的关联性，还可以从另一个角度来考虑，即利用一个变量来预测另一 个变量的能力大小作为关联强弱的一个标志。 当a 变量的状态未知，要预测b 变量，就利用表2 1 中边和虽人作为b 状态的预测， 并记为： n s b = m a x n 5 。，”5 。：，一一，n s 町，- 一，r l s b q ( 2 2 8 ) 如果a 的状态己知为f ，要预测占变量，就利用表2 1 中第i 列中最大的作为b 状态 的预钡4 ，并记为： n 。= i l l a xf 一，。，”，：，疗。， 这样虽优预测系数三为 ， 口 九m + n p n s 6 一 s 。 = 上l 上l 一 2 n s s n 5 6 一一5 口 ( 3 ) 与信息有关的关联系数 r 2 2 9 ) 已知信息的嫡h = 一p fl o g2p j ，单位为比特，可咀用信息比作为两个变量关联 f = i 程度的标志，信息比为j 只： 2 3 类 2 3 1 类的定义 关于类的定义有很多种，在不同的应用中有不同的定义。 ( 2 3 1 ) 设g 为元素的集合，它共有m 个元素，记为g ，：i = 1 ，2 ，m 。另外给定一个阈 值t 0 。则常用的类定义有以下几种，可以适用于不同的场合。 若g 中任意两个元素g ，g 之间的距离不大于阂值，即d 口 t ，则称g 为 拳 鲨一伍 以一p 上， 二 第= 章聚类分析 一个类。也就是说如果一个样品集中的任意两样品问的距离都不夫于某一个取定 的实数r ，则说g 构成一个类。 若g 中任意一个元素g ，它与其它元素间的距离均值不大于闽值，即 击，萎。蟠丁删称g 为一愤 对g 中的任意一个元素g ，总存在另一个元素g ，它们的距离不大于阈值， 即d i tt 则称g 为一个类。 这几种类定义方式均是通过限制元素间的距离来定义类，只是限制的方法有所不 同。其中的要求最高，只要满足它的条件，一定满足其它定义的条件。 2 3 2 类的特征 若将类g 的元素g 。视为随机向量x ，则可用以下几种特征来描述类。 ( 1 ) 类的重心 即为各元素的均向量： i c = 上m 妻i = l x 。 ( z 3 2 ) ( 2 ) 类的样本离差矩阵与样本协方差矩阵 样本离差矩阵： a 6 = ( x ，一_ g ) ( x 一五) 7 ( 2 3 3 ) 样本协方差矩阵： s 。= 击彳。 c ：“， ( 3 ) 类的直径 类的直径也有多种定义，比较简单的有： d g21 蛩a x ( d ) ( 2 3 5 ) 或： d g = ( x 。一i x 。) ( x ，一i x 。) 7t r ( a g ) ( 2 3 6 ) 1 4 第二章聚类分析 式( 2 3 5 ) 将类中元素间的最长距离定义为类直径，其量纲与距离相同；式( 2 3 6 ) 为类中各 元素至类重心的欧氏距离之和，也可理解为类中各元素指标的离差( 变差) 平方和的总和，其 量纲为距离的平方。类直径反映了类的规模和范围，以及类中各元素间的差异。 2 3 3 类间距离 类问距离可以描述两类闻的关系，其前提是取自不同类的两个元素间的距离是可定义 的。类间距离也有多种定义形式。 设有两个类g 。和g 6 ，它们分别有m 和i , 1 个元素，它们的重心分别为x 。和。6 。又 设元素g g 。，元素g ，g 6 ，这两个元素问的距离为d u 。将类间距离记为d ( a ，6 ) 。 则类间距离有以下几种定义形式。 最短距离法 它定义两类中晟靠近的两个元素间的距离为类间距离，即： d s ( 日，6 ) = r a i n d ig ，g o , g ，g 。) ( 2 3 7 ) 最长距离法 它定义两类中最远的两个元素闻的距离为类间距离，即： d t ( 口，6 ) = m a x d 口ig ，g a , g ，g 。) ( 2 3 8 ) 重心法 它定义两类的两个重心问的距离为类间距离，记为d c ( 口，b ) 。 d 。( 口，6 ) = l x 。一x 。l ( 2 _ 3 9 ) 类平均法 它定义弼类中任意两个元素间距离的平均值为类问距离，即： 蹦如，2 去磊。磊。d 。 离差平方和法 由式( 2 3 6 ) 得到的两类g 。与g 6 的直径分别为d 。与d 6 。设类g 。+ = g 。ug 6 其直径为g ：+ 6t 则可定义类间距离为： d ( 口，b ) = d a + b d 。一d 6 ( 2 4 1 ) 第= 章聚类分析 如果用欧氏距离作为元素间的距离，则有： d 。( d ，b ) = ( 2 a 2 ) 这表明离差平方和法定义的类间距离d w ( a ，b ) 与重心法定义的类间距离d c ( 口，b ) 只差 一个常数因子，该因子与两个类的元素数目有关。 2 4 常用聚类方法 聚类分析的方法有很多种，例如系统聚类法、动态聚类法、最近邻聚类法、有序样品 的最优分割、模糊聚类法、神经网络聚类法等。 2 4 1 系统聚类法 系统聚类法先将”个样本看成r 个类，每个类有一个样本。然后将特性最接近的两类 归为一个新的类。这样就有了h l 类。再从”一l 类中找出特性最相近的两类又归并为一 类，这样就有了”一2 如此归类下去，母后所有样本归为一类。据此过程，可以作出聚 类图( 又称分群囤、谱系图) ，从聚类图中确定类构个数和每类的样本。系统聚类法的工作 原理可以归纳为以下几步( 用距离度量样品间或类间的相似程度) ： 计算全部一个样品两两问的距离以并构成 维距离系数矩阵d 。由于以= 0 以及距离的对称性，实际上只需要计算矩阵主对角线以下或以上的各个元素，共有! ! q ；1 2 个： 将每个样品作为一类，共构成n 类。上述的n 维矩阵d 即为类间的距离系数矩阵： 由系数矩阵找出并合并距离最近的类为一新类，于是总的类数将至少减少1 。记下 参加合并的类的序号与距离： 若只剩下一类了，转至第步：否则计算新类与当前其它各类的距离，调整系数矩 阵d ，然后返回第 步： 根据第步中记录的序号和距离，画出聚类图； 确定类的个数，最后得到所聚成的各类。 在第步计算类间距离的时候，可以采用多种算法，因此就有多种系统聚类法。 ( 1 ) 晟短距离法与最长距离法 在计算类间距离时，如果采用式( 2 3 7 ) ，则为最短距离法；如果采用式( 2 3 8 ) ，则为最长 1 6 辱 第= 章聚类分析 距离法。设在某步将类q 与g ，合并为g mt 则新类瓯与其它类g 的距离可以由以下递推 公式计算： 最短距离法： 最长距离法 d 。m ，= m i n d s ( f ，尼) ，d 。( _ ，i ) d 。( m ，七) = m a x d 。( j ，) ，d 。( _ ，) ) f 2 4 3 ) r 2 4 4 ) ( 2 ) 中阎距离法 最短距离法和最长距离法在决定g 。与其它类g i 的距离时，实际上是在两个距离 d ( i ，k ) 和d ( j ，k ) 中分别取最小值或最大值。而中间距离法在这二者之间取中间值，其递推 公式为： 蹦m ，炉序丽曩瓦丽面 这相当于在类g j ，q 和g ：的距离三角形中不选两边d ( i ，七) ，d ( j ，) 中的任何一边， 而选取第三边d ( i ，) 的中线作为新类瓯与q 的距离。如图2 4 所示。 图2 4 三角形中线作为类间距离 ( 3 ) 重心法和类平均法 采用重心法和类平均法计算类间距离的系统聚类法即为重心法和类平均法。设类g ；与 q 合并为g 。，它们各有的样品数目分别为怫，吩，( = 吩+ ) 。又设样品间采用欧氏 距离，递推公式为： 重心法： 第= 章聚类分析 d c ( m ，k ) = 类平均法： j 。曩丐n j 事n ( 2 4 6 ) d g ( ，忌) = ! l d 6 ( f ，七) + n jd g i j ，七) ( 2 4 7 ) 肛m h m ( 4 ) 离差平方和法 即采用离差平方和计算类间距离： d ( m ，k )二玉兰d 毒( f ，| ) + 二尘兰d ；( _ ，七) 一士d o ( f ，) v 门4 - n km - 4 - 订 n m + f k ( 2 4 8 ) 以上几种系统聚类法的工作步骤完全相同只是计算类间距离的递推公式不一样。为了 便于计算机程序的编制，1 9 7 6 年l a n c e 和w i l l i a m s 提出来一个统一公式： o ( m ，炉厄而丽i 万瓦可面雨而可而万写可习 ( 2 4 9 ) 其中，口，均为参数，对于不同的系统聚类法，它们取不同的值。如表2 2 所示。 表2 2 系统聚类法的参数取值表 y 最短距离法 最长距离法 中间距离法 重心法 类平均法 1 ，2 l ，2 1 ，2 吩n m n i f n 。 1 2 1 2 1 2 n i h 。 n j n o 0 1 4 一a p i 0 离差平方和法 ( _ + 仇) ( + ( n j + n k ) l ( n m + n k )一心( + n k ) 0 一般来说，各种系统聚类法的效果不尽相同。最短距离法比较适合于条形的类，可以有 1 8 北 北 o o o 第= 章聚娄分析 所弯曲。蛀k 距离泫、重心法、类平均法和离差平方和法等比较适台于椭球形的类。 对于具体问题j _ ； j 哪一种方法好，较为复杂。为此需要研究系统聚类法的性质，最优化性 质为其中之一。对丁= 月个样品，要求分为k 类，并将一分类法 g 1 ，g 2 , - - - , g 女 记为6 ( ，t ) 。 为了比较分类的合理性，可以定义一个分类函数上( 6 ( ”，t ) ) ，它的取值越小，分类方法越合 理。如果方法b + ( 1 7 ，k ) 能够满足： 上( 6 ( ”，七) ) 2 。职：，l ( 。) ) ( 2 5 0 ) 其中是所有b ( n ，k ) 的集合，则在分类函数l ( b ( n ，女) ) 的意义下，6 + ( ，k ) 为最优分类 方法。也称分类函数l ( b ( n ，i c ) ) 为损失函数或目标函数。损失函数的定义有很多种，应视具 体问题的需要而定。 系统聚类法虽然可以找到比较好的聚类结果，但是由于需要建立类问距离矩阵、类直径 矩阵、损失函数值矩阵等，还需要进行全面的两两比较，运行效率太低。当样品总数n 比较 大时，数据的存储量和操作量都十分巨大，以致难以进行下去。 2 4 2 动态聚类法 为了克服系统聚类法效率太低的缺点，就得避开全面的计算和比较，在局部分析的基础 上，作出较为粗略的分类，然后再按某种最优的准则进行修正，直至分类比较合理为止。基 于这种思想产生了动态聚类法，又称逐步聚类法。其工作原理如图2 5 所示。 完成 圈25 动态聚类法的工作原理 1 9 第二章聚粪分析 图中的“凝聚点”是欲形成类的中心。刚开始时，选若干有代表性的样品作为凝聚点， 相当于把这些样品单独作为类。然后按一定的原则( 比如选择晟近的凝聚点) 使其它样品向 凝聚点聚集，合并于已有的类中，从而实现了分类。这样，比较的范围局限于仅与凝聚点比， ：1 ：作量大大减少。此后需判别这样的分类是否合理，若不合理，则应作修改，然后再进行分 类直至分类合理为止。 凝聚点的好坏直接决定了初始分类，对最终分类结果也有较大影响，因此在选择凝聚 点时应慎重。凝聚点的选择常用如下方法： 人为地选择：当对所研究的问题有了一定的了解，对一批样品怎样分类，分成几 类，大体能心中有数，这时可选择一批有代表性的样品作为凝聚点。 重心法：人为地确定一个常数女，将样品分成七类，计算每一类的重心( 均值) ， 取这些重心为凝聚点。 密度法：先人为地取二个正数西和吐，以每个样品作为球心，以吐为半径，落 在这个球内的样品数( 不包括作为球心的样品) 就叫做该样品的密度。首先选择具有最大密 度的样品点作为第一凝聚点；然后选择次大密度的样品点，若它和第一凝聚点的距离大于 或等于以，取该点作为第二凝聚点，否则不取其为凝聚点。再选密度次于它的样品，用这 种方法依样品的密度由大到小的选下去，当每一次所选样品和己定的所有凝聚点的距离都 大于吐( 或等于吐) ，则选该点为新凝聚点，否则该点不作为凝聚点。再选密度仅次于它 的样品来考察。凝聚点的个数应与欲分类的类数相同a4 一般应大于4 ，常取吐= 2 嗣。 产生初始分类的常用的方法如下： 人为地分类，即凭经验将样品进行初步的分类。 选择一批凝聚点，每个样品按虽近凝聚点归类。 用某种聚类分析的方法得到一个分类，将这个分类结果作为初始分类。 动态聚类算法可以分为以下几步( 假设共有h 个样品) ： 确定分类个数七，一般取前七个样品作为凝聚点，也可以随机选取七个样品作为凝 聚点每个凝聚点样品自成一类： 按距离最近原则，将其余一t 个样品逐个并入晟近凝聚点所代表的类。每并入一 个样品，立即重新计算该类的重心，并用此重心替代原来的凝聚点。待”个样品都 被分类后，计算用来评价动态聚类分析效果的准则函数的值。 第= 章聚类分析 以最后形成的每个凝聚点代表一类，将全部 个样品重新聚娄，逐个并入最近的凝 聚点所属的类。与第步相同，每并八一样品，就重新计算重心，并以此重心代替原来的凝 聚点。 个样品被重新分类后，计算准则函数的值，如果新的准测函数的值比前一次分类的 准则函数的值效果更好，就重复第步：否则聚类完成。 动态聚类法速度快，聚类结果较好，但目前理论尚不完善还存在初始分类确定难的问 题。 2 4 3 最近邻聚类法 最近邻聚类算法是一种最简单、最基本的聚类算法，该算法的主要思想是首先把第一个 数据作为第一个聚类中心，接下来，检测其它数据点到