第七章 聚类分析

1、1,第七章 聚类分析,分类与聚类的区别 分类：用已知类别的样本训练集来设计分类器（监督学习） 聚类（集群）：事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）,2,7.1 聚类的基本概念 7.2 模式相似性测度 7.3 类的定义与类间距离 7.4 聚类算法 启发式聚类：简单聚类 层次（分级）聚类（hierarchical clustering) : 分裂聚类、 合并聚类、 动态聚类。 其它聚类算法,3,3,7.1 聚类的基本概念,似圆度,7.1.1 聚类分析的基本思想 据相似程度聚类 无监督聚类（Unsupervised）,4,4,7.1.2 聚类准则对聚类结果的影响,羊,狗,

2、猫, 鲨鱼,蜥蜴,蛇,麻雀，海鸥,金鱼,青蛙,(a)繁衍后代的方式,金鱼,鲨鱼,羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙,(b) 肺的存在,金鱼,鲨鱼,羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙,(c) 生存环境,金鱼,蜥蜴,蛇,麻雀，海鸥,青蛙,(d)繁衍后代的方式和是否存在肺,鲨鱼,羊,狗,猫,7.1 聚类的基本概念,5,7.1.3 距离测度对聚类结果的影响,2.1 聚类的基本概念,5,数据的粗聚类是两类,细聚类为4类,6,6,7.2 模式相似性测度,7.2.1 距 离 测 度 7.2.2 相 似 测 度 7.2.3 匹 配 测 度,7,7,7.2.1 距离测度(差值测度),Distance (

3、or Dissimilarity) Measure 设特征矢量 和 的距离为 则 一般应满足如下公理,(1) (2) (3),(triangular inequality),8,距离测度(差值测度), 欧氏(Euclidean)距离, 绝对值距离(街坊距离或Manhattan距离),(3) 切氏(Chebyshev)距离,9,距离测度(差值测度),(4) 明氏(Minkowski)距离,(5) Cambera距离(Lance距离、Willims距离),该距离能克服量纲的影响， 但不能克服分量间的相关性。,10,距离测度(差值测度),(6)马氏(Mahalanobis)距离,其中,（协方差矩阵的

4、无偏估计）,（均值向量的估计）,性质：对一切非奇异线性变换都是不变的。即，具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。,11,马氏距离具有线性变换不变性,证明：设，有非奇异线性变换： 则,12,故,13,马氏距离的一般定义,设 、 是从期望矢量为 、协方差矩阵为的母体G中抽取的两个样本，则它们间的马氏距离定义为 当 和 是分别来自两个数据集中的样本时，设C是它们的互协方差阵，则它们间的马氏距离定义为,当、V、C为单位矩阵时，马氏距离欧氏距离。 对于正态分布，等概率密度点轨迹是到均值矢量的 马氏距离为常数的点所构成的超椭球面。,14,7.2.2 相 似 测 度,重

5、点考虑两矢量的方向是否相近，而忽略矢量长度。,(1) 角度相似系数(夹角余弦）矢量之间的相似性可用它们的夹角余弦来度量,(2) 相关系数数据中心化后的矢量夹角余弦,性质：相关系数具有坐标系平移、旋转、比例不变性。,15,15,性质：不受量纲变化的影响。,(3) 指数相关系数,这里假设 和 的维数 n 相同、概率分布相同。 是第 i 个分量的方差。,16,7.2.3 匹 配 测 度,若特征只有两个状态：,0 = 有此特征；1 = 无此特征。称之为二值特征。 对于给定的二值特征矢量x和y中的某两个相对应的分量xi与yj若xi=1, yj=1 ，则称 xi与yj (1-1)匹配；若xi=1, yj=

6、0 ，则称 (1-0)匹配；若xi=0, yj=1 ，则称 (0-1)匹配；若xi=0, yj=0 ，则称 (0-0)匹配。 对于二值n维特征矢量可定义如下相似性测度：,17,匹 配 测 度,(1) Tanimoto测度,(1-1)匹配的特征数目 (0-1)匹配的特征数目 (1-0)匹配的特征数目 (0-0)匹配的特征数目,令,注意，这里只考虑（1-1）匹配，而不考虑（0-0）匹配。,18,匹 配 测 度,(2) Rao测度 (3) 简单匹配系数 (4) Dice系数 (5) Kulzinsky系数,（1-1）匹配特征数目与特征总数之比,（1-1）匹配+（0-0）匹配/特征总数,只对（1-1）

7、匹配加权,（1-1）匹配/ （1-0）匹配+（0-1）匹配,19,19,例 1,设 (1) Tanimoto测度 (2) Rao测度 (3) 简单匹配测度 (4) Dice系数 (5) Kulzinsky系数,则,20,7.3 类的定义与类间距离,21,7.3.2 类间距离测度方法, 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法,22,22,k,p,q,23,（二）最远距离 递推公式,k,p,q,24,（三）中间距离 递推公式,25,（四）重心距离递推公式 式中 ， 和 分别是i和j的重心， i, j=k, l, p, q 。,26,（五） 平均距离 两类p和q间的

8、距离平方定义为这两类元素两两之间的平均平方距离，即设l =p q ，类平均距离的递推公式为,27,27,（六） 离差平方和法 设类t 的重心是 ， t 的类内离差平方和定义为 设l =p q ，则sl要变大。把两类合并所增加的离差平方和定义为两类平方距离，即 ，可以证明 k与l =p q的离差平方和的递推公式,28,29,7.3.3 聚类准则函数,评估分类过程或分类结果优劣的准则函数 （一）类内距离准则（误差平方和准则）,式中，nj是j中的样本个数，,适用于各类模式呈团状分布的情况。,30,2.3.3 聚类准则函数,（二）类间距离准则,式中， 是总的样本均值矢量，,加权类间距离准则,对于两类问

9、题 ，可以定义,31,（三）基于类内类间距离的准则函数,构造能同时使Jwmin和JBmax的准则函数 类内离差矩阵（Scatter Matrix）,总的类内离差矩阵,总的离差矩阵,类间离差矩阵,32,32,ST = SW + SB,证明：,33,（三）基于类内类间距离的准则函数,聚类的基本目标是使 JWB=TrSBmax和JWW =TrSWmin 因此可定义如下聚类准则函数,Jimax，(i=1, 2, 3, 4) 即，类内越“紧”，类间越“开”，聚类效果越好。,34,74 聚类算法,(1) 简单聚类方法,(2) 分裂聚类法,(4) 动态聚类法,(3) 合并聚类法,35,74 简单聚类方法,根

10、据相似性阈值和最小距离原则, 条件及约定 设待分类的模式为 , 选定类内距离门限 。 算法思想 计算模式特征矢量到聚类中心的距离,并和门限 比较，决定归属该类或作为新的一类中心。这种算法通常选择欧氏距离。,36, 算法原理步骤 取任意一个模式特征矢量作为第一个聚类中心。例 如，令 类的中心 。 计算下一个模式特征矢量 到 的距离 。若 ，则建立新的一类 ,其中心 。若 ，则 。,37, 假设已有聚类中心 ，计算尚未确定类别的模式特征矢量 到各聚类中心 的距离 。如果 , 则 作为新的一类 的中心， ； 否则，如果 ,则指判 。检查是否所有的模式都分划完类别，如果都分划完了则结束；否则返到。,3

11、8,这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。 从算法的过程可以看出，该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑设置不同的T和选择不同的次序，最后选择较好的结果进行比较。,简单聚类算法特点:,39,简单聚类图例,40,例7.4.1：初始条件不同的简单聚类结果,初始中心不同,样本顺序不同,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,10 9 8,10 9 8,8 7 6,8 7 6,11 6 7,11 6 7,9 1

12、0 11,9 10 11,41,74 分裂聚类(Divisive algorithm),分裂聚类：把全部样本作为一类，然后根据相似性、相邻性分解。 目标函数: 两类均值方差,N：总样本数， 为1类样本数 为2类样本数，,42,分裂聚类框图：,43,用下例说明分裂聚类算法 例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：,44,解：第一次分类时计算所有样本，分别划到,（即划分为另一类）时的最大E值。 1、开始时,45,2、分别计算当 依次划入,时的E值,把 划入,时有,仅有x1一个样本,46,然后再把 依次划入 ， 计算对应的E值，找出一个最大的E值。 通过计算知 把 划为 的E值最

13、大。 ,E(1)=56.6,再继续进行第二、第三次迭代 计算出 E(2) , E(3) , ,47,次数 E值 1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8 176.15 9 195.26 10 213.07 11 212.01,48,第10次迭代 划入 时，E最大。于是分成以下两类： ,每次分类后要重新计算 的值。可用以下递推公式：,49,50,作业： 样本 1 2 3 4 5 6 7 8 0 2 1 5 6 5 6 7 0 2 1 3 3 4 4 5 用对分法编程上机，分成两类画出图形。,51, 条件及约定 设待分

14、类的模式特征矢量为 ， 表示第 次合并时的第 类。 算法思想 首先将 N 个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。,按最小距离原则不断进行两类合并,74 合并聚类法(agglomerative algorithm),52,53, 找出前一步求得的矩阵 中的最小元素，设它 是 和 间的距离，将 和 两类合并 成一类，于是产生新的聚类 令 检查类的个数。如果类数 大于2，转至；否则，停止。,54,例7.4.3：如下图所示 1、设全部样本分为6类， 2、作距离矩阵D(0) 3

15、、求最小元素： 4、把1,3合并7=(1,3) 4,6合并8=(4,6) 5、合并的类数没有达到要求 作距离矩阵D(1),D(0),55,例7.4.3：如下图所示 7、作距离矩阵D(1) 8、求最小元素： 9、把2,5，8合并 9=（2,5,4,6） 10、合并的类数达到要求， 停止。,D(1),56,57,7-4 动态聚类 兼顾分裂聚类和合并聚类,动态聚类的方法概要 先选定某种距离作为样本间的相似性度量; 确定评价聚类结果的准则函数; 给出某种初始分类，用迭代法找出使准则函数取极值的最好聚类结果。,58,动态聚类框图,59,代表点的选取方法： 代表点就是初始分类的聚类中心数C 凭经验选代表点

16、，根据问题的性质、数据分布，从直观上选出较合理的代表点; 将全部样本随机分成C类，计算每类重心，把这些重心作为每类的代表点。,60, 按密度大小选代表点： 以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该点的密度，并按密度大小排序。 首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。 d1太小，代表点太多，d1太大，代表点太少，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。

17、用前C个样本点作为代表点。,61,初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。 E 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。 E 直接用样本进行初始分类，先规定距离d，把第一个样本作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第

18、二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。,62,最佳初始分类。 如图所示，随着初始分类C的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。,C,63, 条件及约定 设待分类的模式特征矢量集为 ，类的数目C是事先设定的。 算法思想 该方法取定 C个类别和选取 C个初始聚类中心，按最小距离原则将各模式分配到 C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。,C-均值法,64, 算法原理步骤,C-均值法,65,(4) 如果 ,则结束,否则 ,转至(2)。,

19、(3) 计算重新分类后的各类心 式中 为类 中所含模式的个数。,C-均值法,66,例7.4.3：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C均值法实现样本分类（C=2）。,第一步：令C=2，选初始聚类中心为,67,68,69,第三步：根据新分成的两类建立新的聚类中心,第四步： 转第二步进行第二次叠代。 第二步（第二次叠代）：重新计算 到z1(2） , z2(2） 的距离，把它们归为最近聚类中心，重新分为两类，,70,第三步（第二次叠代），更新聚类中心,71,第四步， 第二步（第三次叠代）， 第三步（第三次叠代），更新聚类中心,进行第三次叠代,72,73,(0,0.5),74,(

20、1.25,1.13),(7.67,7.33),75,ISODATA算法,(Iterative Self-Organizing Data Analysis Techniques Algorithm 迭代自组织数据分析),特点：启发性推理、分析监督、控制聚类结构及人机交互。 条件及约定： 设待分类的模式特征矢量为 ，算法运行前需设定7个初始参数。 算法思想： 在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。,76,ISODATA算法原理步骤

21、, 预置 设定聚类分析控制参数： =预期的类数， =初始聚类中心个数(可以不等于c)， =每一类中允许的最少模式数目， =类内各分量分布的距离标准差上界， =两类中心间的最小距离下界， =在每次迭代中可以合并的最大聚类对数， =允许的最多迭代次数。 将待分类的模式特征矢量 读入。 选定初始聚类中心，可从待分类的模式特征矢量集 中任选 个模式特征矢量作为初始聚类中心。,77,ISODATA算法原理步骤, 按最小距离原则将模式集 中每个模式分到某一类中，即,如果 则判 式中 表示 和类 的中心 之间的距离。 依据 判断合并。如果类 中样本数 ，则取消该类的中心 ， ，转至。,78,ISODATA算

22、法原理步骤, 计算各类的中心 计算各类中模式到类心的平均距离 计算各个模式到其类内中心的总体平均距离, 计算分类后的参数:各类中心、类内平均距离及总体平均距离。,79,ISODATA算法原理步骤, 依据 、 判断停止、分裂或合并。, 若迭代次数 已达 ，则置 转到；否则转下。 若 则转到(将一些类分裂)；否则转下。 若 ,(则跳过分裂处理)转至,否则转下。 若 ，当迭代次数 是奇数时转至(分裂处理)；迭代次数 是偶数时转至(合并处理)。,80,ISODATA算法原理步骤, 计算各类类内距离的标准差矢量,式中， 为分量编号， 为类的编号， 为矢量维数，是 的第 个分量， 是 的第 个分量。,81

23、, 对每一聚类，求出类内距离标准差矢量 中的最大分量 在 中，对任一 ，若有 ，同时又满足下面两个条件之一： 和 则将该类 分裂为两个聚类，且令 。这两个新类的中心 和 是这样构成的： 和 只是在 中相应于 的分量分别加上和减去 ，而其它分量不变，其中 ， 的选取应使 和 仍在 的类域空间中且其它类 的模式到 和 距离较远，而原 类中的模式和它们距离较小。分裂后， ，转至； 否则，转下。,ISODATA算法原理步骤,82, 计算各对聚类中心间的距离 依据 判断合并。将 与 比较，并将小于 的那些 按递增次序排列，取前L个， 。从最小的 开始，将相应的两类合并。若原来的两个类心为 和 ，则合并后的聚类中心为 （已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。,ISODATA算法原理步骤,83, 如果迭代次数 已达 次或过程收敛，则结束。否则， ，若需要调整参数，则转至；若不改变参数，则转至。,ISODATA算法原理步骤,84,我们将ISODATA算法的合并和分裂的条件归纳如下： 合并的条件： (类内样本数 )(类的数目 )(两类