模式识别 第二章 聚类分析

《模式识别 第二章 聚类分析》由会员分享，可在线阅读，更多相关《模式识别 第二章 聚类分析（70页珍藏版）》请在金锄头文库上搜索。

1、模式识别 第二章 聚类分析,2.1 聚类的基本概念,2.1.1聚类分析的基本思想 Clustering Analysis 据相似程度分类 无监督分类（Unsupervised）,2.1 聚类的基本概念,2.1.2 特征量的类型 物理量：直接反映特征的实际物理意义 如:长度、重量、速度等。处理前需要离散化。 次序量：按某种规则确定的只反映特征的次序 关系或等级 如:产品的等级、病症的级或期。已是离散量。 名义量：反映样本的状态特征非数值的， 如男性与女性、事物的状态、种类等。需要数值化。这些特征的数值指标既无数量含义，也无次序关系，只是用数字代表各种状态。,取决于分类算法和特征点分布情况的匹配。

2、,1.特征选取不当使分类无效。,2.1 聚类的基本概念,2.1.3 方法的有效性,2.特征选取不足可能使不同类别的模式判为一类。,取决于分类算法和特征点分布情况的匹配。,2.1 聚类的基本概念,2.1.3 方法的有效性,3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。,4.量纲选取不当。,2.1.4聚类准则对聚类结果的影响,2.1 聚类的基本概念,2.1.5 距离测度对聚类结果的影响,2.1 聚类的基本概念,数据的粗聚类是两类,细聚类为4类,2.2 模式相似性测度,2.2.1 距 离 测 度2.2.2 相 似 测 度2.2.3 匹 配 测 度,2.2.1 距离测度(差值测度),

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

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

5、的距离。解：由题设，可得从而马氏距离它们之比达 倍。若用欧氏距离，则算得的距离值相同：由分布函数知，A、B两点的概率密度分别为,已知一个二维正态母体G的分布为,2.2.2 相 似 测 度,重点考虑两矢量的方向是否相近，而忽略矢量长度。,(1) 角度相似系数(夹角余弦） 矢量之间的相似性可用它们的夹角余弦来度量,(2) 相关系数 数据中心化后的矢量夹角余弦,性质：相关系数具有坐标系平移、旋转、比例不变性。,相关系数具有坐标系平移、旋转、比例变换不变性,证明： （作业）,设，有旋转、平移变换： 其中，R是旋转变换矩阵（即正交矩阵）， 是平移矢量。 则有,性质：不受量纲变化的影响。,(3) 指数相关

6、系数,这里假设 和 的维数n相同、概率分布相同。是第i个分量的方差。,（三） 匹 配 测 度,若特征只有两个状态：,0 = 有此特征；1 = 无此特征。称之为二值特征。 对于给定的二值特征矢量x和y中的某两个相对应的分量xi与yj 若xi=1,yj=1 ，则称 xi与yj (1-1)匹配； 若xi=1,yj=0 ，则称 (1-0)匹配； 若xi=0,yj=1 ，则称 (0-1)匹配； 若xi=0,yj=0 ，则称 (0-0)匹配。 对于二值n维特征矢量可定义如下相似性测度：,（三） 匹 配 测 度,(1) Tanimoto测度,(1-1)匹配的特征数目 (0-1)匹配的特征数目 (1-0)匹配

7、的特征数目 (0-0)匹配的特征数目,令,注意，这里只考虑（1-1）匹配，而不考虑（0-0）匹配。,（三） 匹 配 测 度,(2) Rao测度 (3) 简单匹配系数 (4) Dice系数 (5) Kulzinsky系数,（1-1）匹配特征数目与特征总数之比,（1-1）匹配+（0-0）匹配/特征总数,只对（1-1）匹配加权,（1-1）匹配/ （1-0）匹配+（0-1）匹配,例 2.2,设(1) Tanimoto测度 (2) Rao测度 (3) 简单匹配测度 (4) Dice系数 (5) Kulzinsky系数,则,一、影响分类的因数 （1）分类准则；（2）特征量的选择；（3）量纲。 二、模式相似

8、性测度 （一） 距 离 测 度 (1) 欧氏距离 (2) 马氏距离 对坐标系平移、旋转、比例不变。 （二） 相 似 测 度 相关系数 （特征矢量的方向） 对坐标系平移、旋转、比例不变。 （三） 匹 配 测 度 （0-1）匹配系数,小结,2.3 类的定义与类间距离,2.3.1 类的定义 类的划分具有人为规定性，这反映在类的定义的选取及参数的选择上。 分类结果的优劣最后只能根据实际来评价。 定义1 设集合S中任意元素xi与xj间的距离dij有 dij h 其中h为给定的阈值，称S对于阈值h组成一类。,定义2 其中k为S中元素的个数。（类内平均距离）,定义5 若将集合S任意分成两类S1，S2，这两类

9、间的 距离D(S1,S2)h，则称S对于阈值h组成一类。,2.3.1 类的定义,定义3 设集合S中任意元素xi与xj间的距离dij有 其中k为S中元素的个数，称S对于阈值h,r组成一类。,定义4 xiS ，xjS，使dij h成立，则称S对于 阈值h组成一类。（最近距离）,2.3.2 类间距离测度,（一）最近距离 两个聚类k和l之间的最近距离定义为 式中， dij表示 xi k与xj l间的距离。 如果l由p和q两类合并而成，则有递推公式,2.3.2 类间距离测度,（二）最远距离递推公式,（三）中间距离 递推公式,2.3.2 类间距离测度,2.3.2 类间距离测度,（四）重心距离 递推公式式中

10、 ， 和 分别是i和j的重心， i,j=k,l,p,q 。,2.3.2 类间距离测度,（五） 平均距离 两类p和q间的距离平方定义为这两类元素两两之间的平均平方距离，即 设l =p q ，类平均距离的递推公式为,2.3.2 类间距离测度,（六） 离差平方和法 设类t的重心是 ， t的类内离差平方和定义为 设l =p q ，则sl要变大。把两类合并所增加的离差平方和定义为两类平方距离，即 ，可以证明k与l =p q的离差平方和的递推公式,类间距离递推公式,（其中l =p q ）,2.3.3 聚类准则函数,评估分类过程或分类结果优劣的准则函数 （一）类内距离准则（误差平方和准则）,式中，nj是j中

11、的样本个数，,适用于各类模式呈团状分布的情况。,2.3.3 聚类准则函数,（二）类间距离准则,式中， 是总的样本均值矢量，,加权类间距离准则,对于两类问题 ，可以定义,（三）基于类内类间距离的准则函数,构造能同时使Jwmin和JBmax的准则函数 类内离差矩阵（Scatter Matrix）,总的类内离差矩阵,总的离差矩阵,类间离差矩阵,ST = SW + SB （作业）,证明：,妈妈新开了个淘宝店，欢迎前来捧场 妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来出自己的一份力，帮忙宣传一下。 并

12、且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。 另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。欢迎大家来逛逛【扬州五亭龙玩具总动员】 ,个人小广告：,（三）基于类内类间距离的准则函数,聚类的基本目标是使 JWB=TrSBmax和JWW =TrSWmin 因此可定义如下聚类准则函数,Jimax，(i=1,2,3,4) 即，类内越“紧”，类间越“开”，聚类效果越好。,%该函数用于显示二维正态分布的函数图 clear; %X1和X2分别为两个向量 X1=-5:0.1:5; X2=-5:0.1:5; %Miu为均值向量 Miu=1,1; %E为协方差矩阵 E=3 0.0;

13、0.0 1.0; %y为求得的函数值 for i=1:length(X1)for j=1:length(X2)x=X1(i),X2(j);y(i,j)=exp(-0.5*(x-Miu)*inv(E)*(x-Miu);y(i,j)=y(i,j)/(2*pi)*sqrt(det(E);end end %显示函数值 meshc(X1,X2,y);,24 聚类的算法,(1) 简单聚类方法,算法运行中，两类合并为一类，不断重复进行。也称为谱系聚类法。,(2) 层次聚类法,(3) 动态聚类法,算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有C均值法、ISODATA法等。,算法运行中模

14、式的类别及类的中心一旦确定将不会改变。,24 聚类的算法-简单聚类方法,根据相似性阈值和最小距离原则, 条件及约定设待分类的模式为 ,选定类内距离门限 。 算法思想计算模式特征矢量到聚类中心的距离并和门限 比较，决定归属该类或作为新的一类中心。这种算法通常选择欧氏距离。,24 聚类的算法-简单聚类方法, 算法原理步骤 取任意的一个模式特征矢量作为第一个聚类中心。例 如，令 类的中心 。 计算下一个模式特征矢量 到 的距离 。若 ，则建立新的一类 ,其中心 。若 ，则 。,24 聚类的算法-简单聚类方法, 算法原理步骤 假设已有聚类中心 ，计算尚未确定类别的模式特征矢量 到各聚类中心 的距离 。如果 , 则 作为新的一类 的中心， ； 否则，如果 ,则指判 。检查是否所有的模式都分划完类别，如果都分划完了则结束；否则返到。,24 聚类的算法-简单聚类方法,简单聚类图例,24 聚类的算法-简单聚类方法,例2.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 10 11,9 10 11,