模式识别聚类精选文档.ppt

《模式识别聚类精选文档.ppt》由会员分享，可在线阅读，更多相关《模式识别聚类精选文档.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别聚类本讲稿第一页，共四十八页什么是聚类什么是聚类聚类是一种无监督分类法聚类是一种无监督分类法:没有预先指定没有预先指定的类别的类别分类：用已知类别的样本训练集来设计分类：用已知类别的样本训练集来设计分类器（监督学习）分类器（监督学习）聚类：用事先不知类别的样本，利用样聚类：用事先不知类别的样本，利用样本的先验知识来构造分类器（无监督学本的先验知识来构造分类器（无监督学习）习）l聚类分析无训练过程，训练与识别混合聚类分析无训练过程，训练与识别混合在一起。在一起。本讲稿第二页，共四十八页相似性度量相似性度量设有样本集设有样本集 ，要求按某，要求按某种相似性把分类，怎样实现？种相似性把分类，

2、怎样实现？聚类分析符合聚类分析符合“物以类聚，人以群分物以类聚，人以群分“的原则，它把相似性大的样本聚集为的原则，它把相似性大的样本聚集为一个类型，在特征空间里占据着一个局一个类型，在特征空间里占据着一个局部区域。每个局部区域都形成一个聚合部区域。每个局部区域都形成一个聚合中心，聚合中心代表相应类型。中心，聚合中心代表相应类型。本讲稿第三页，共四十八页如下图中，如下图中，(a)有一个聚合中心，有一个聚合中心，(b)、(c)有两个。有两个。本讲稿第四页，共四十八页聚类分析避免了估计类概率密度的困难，聚类分析避免了估计类概率密度的困难，对每个聚合中心来说都是局部密度极大对每个聚合中心来说都是局部密

3、度极大值位置，其附近密度高，距离越远密度值位置，其附近密度高，距离越远密度越小。越小。聚类分析的关键问题：如何在聚类过程聚类分析的关键问题：如何在聚类过程中自动地确定类型数目中自动地确定类型数目c。实际工作中，也可以给定值作为算法终实际工作中，也可以给定值作为算法终止的条件。止的条件。本讲稿第五页，共四十八页聚类分析的结果与特征的选取有很大的聚类分析的结果与特征的选取有很大的关系。不同的特征，分类的结果不同。关系。不同的特征，分类的结果不同。本讲稿第六页，共四十八页1.距离相似性度量距离相似性度量一个模式样本，对应特征空间里的一个一个模式样本，对应特征空间里的一个点。如果模式的特征是适当选择的

4、，也点。如果模式的特征是适当选择的，也就是各维特征对于分类来说都是有效的，就是各维特征对于分类来说都是有效的，那么同类样本就会密集地分布在一个区那么同类样本就会密集地分布在一个区域里，不同类的模式样本就会远离。因域里，不同类的模式样本就会远离。因此，点间距离远近反映了相应模式样本此，点间距离远近反映了相应模式样本所属类型有无差异，可以作为样本相似所属类型有无差异，可以作为样本相似性度量。距离越近，相似性越大，属于性度量。距离越近，相似性越大，属于一个类型。聚类分析中，最常用的就是一个类型。聚类分析中，最常用的就是距离相似性。距离相似性。本讲稿第七页，共四十八页（1）欧氏距离）欧氏距离欧氏距离简

5、称距离，模式样本向量欧氏距离简称距离，模式样本向量 x与与y之间的欧氏距之间的欧氏距离定义为：离定义为：d为特征空间的维数。为特征空间的维数。当当 较小时，表示较小时，表示x与与y在一个类型区域，反之，在一个类型区域，反之，则不在一个类型区域。这里有一个门限的选择问则不在一个类型区域。这里有一个门限的选择问题。若选择过大，则全部样本被视作一个唯一类题。若选择过大，则全部样本被视作一个唯一类型；若选取过小，则可能造成每个样本都单独构型；若选取过小，则可能造成每个样本都单独构成一个类型。必须正确选择门限值以保证正确分成一个类型。必须正确选择门限值以保证正确分类。类。本讲稿第八页，共四十八页（1）欧

6、氏距离（续）欧氏距离（续）另外，模式特征坐标单位的选取也会强另外，模式特征坐标单位的选取也会强烈地影响聚类结果。烈地影响聚类结果。例如：一个二维模式，一个特征是长度，例如：一个二维模式，一个特征是长度，另一个特征是压力。另一个特征是压力。l当长度由厘米变为米，在当长度由厘米变为米，在 中长度中长度特征的比重会下降，同样，若把比重单特征的比重会下降，同样，若把比重单位由毫米汞柱高度变成厘米汞柱高度，位由毫米汞柱高度变成厘米汞柱高度，中压力特征的影响也会下降。中压力特征的影响也会下降。本讲稿第九页，共四十八页（1）欧氏距离（续）欧氏距离（续）可以用图表示上述情况：从上图看出，(b)、(c)特征空间

7、划分是不同的。(b)中 为一类，为另一类，(c)中 为一类，为另一类。本讲稿第十页，共四十八页（1）欧氏距离（续）欧氏距离（续）另外，使用欧氏距离度量时，还要注意另外，使用欧氏距离度量时，还要注意模式样本测量值的选取，应该是有效反模式样本测量值的选取，应该是有效反映类别属性特征（各类属性的代表应均映类别属性特征（各类属性的代表应均衡）。但马氏距离可解决不均衡（一个衡）。但马氏距离可解决不均衡（一个多，一个少）的问题。多，一个少）的问题。例如，取例如，取5个样本，其中有个样本，其中有4个反映对分个反映对分类有意义的特征类有意义的特征A，只有，只有1个对分类有个对分类有意义的特征意义的特征B，欧氏

8、距离的计算结果，欧氏距离的计算结果，则主要体现特征则主要体现特征A。本讲稿第十一页，共四十八页（2）马氏（）马氏（Mahalanobis）距离）距离定义：马氏距离的平方定义：马氏距离的平方l其中，为均值向量，为协方差矩阵。其中，为均值向量，为协方差矩阵。马氏距离排除了不同特征之间相关性的马氏距离排除了不同特征之间相关性的影响，其关键在于协方差矩阵的计算。影响，其关键在于协方差矩阵的计算。当为对角阵时，各特征之间才完全独立当为对角阵时，各特征之间才完全独立；当为单位矩阵时，马氏距离等于欧氏；当为单位矩阵时，马氏距离等于欧氏距离。距离。马氏距离比较适用于对样本已有初步分马氏距离比较适用于对样本已有

9、初步分类的情况，做进一步考核、修正。类的情况，做进一步考核、修正。本讲稿第十二页，共四十八页（3）明氏（）明氏（Minkowsky）距离）距离定义：明氏距离定义：明氏距离:它是若干距离函数的通式：它是若干距离函数的通式：时，等于欧氏距离；时，等于欧氏距离；时，称为时，称为“街坊街坊”（city block）距离。距离。本讲稿第十三页，共四十八页2.角度相似性度量角度相似性度量样本样本x与与y之间的角度相似性度量定义为之间的角度相似性度量定义为它们之间夹角的余弦，即它们之间夹角的余弦，即 l也是单位向量之间的点积（内积）。越大，越大，x与与y越相似。常用于情报越相似。常用于情报检索、植物分类、疾

10、病分类。检索、植物分类、疾病分类。本讲稿第十四页，共四十八页2.角度相似性度量角度相似性度量 满足：满足：当当 时，时，达到最大。对于坐达到最大。对于坐标系的旋转及放大、缩小标系的旋转及放大、缩小 是不变是不变的量，但对位移和一般性的线性变换不的量，但对位移和一般性的线性变换不是不变的。是不变的。l样本与核的相似性度量样本与核的相似性度量l近邻函数值相等近邻函数值相等本讲稿第十五页，共四十八页样本相似性度量是聚类分析的基础，针样本相似性度量是聚类分析的基础，针对具体问题，选择适当的相似性度量是对具体问题，选择适当的相似性度量是保证聚类质量的重要问题。但有了相似保证聚类质量的重要问题。但有了相似

11、性度量还不够，还必须有适当的聚类准性度量还不够，还必须有适当的聚类准则函数。聚类准则函数对聚类质量也有则函数。聚类准则函数对聚类质量也有重大影响。重大影响。相似性度量相似性度量 集合与集合的相似性。集合与集合的相似性。相似性准则相似性准则 分类效果好坏的评价准分类效果好坏的评价准则则 本讲稿第十六页，共四十八页聚类准则函数聚类准则函数在样本相似性度量的基础上，聚类分在样本相似性度量的基础上，聚类分析还需要一定的准则函数，才能把真析还需要一定的准则函数，才能把真正属于同一类的样本聚合成一个类型正属于同一类的样本聚合成一个类型的子集，而把不同类的样本分离开来。的子集，而把不同类的样本分离开来。如果

12、聚类准则函数选得好，聚类质量如果聚类准则函数选得好，聚类质量就会高。就会高。本讲稿第十七页，共四十八页聚类准则函数聚类准则函数同时，聚类准则函数还可以用来评价一同时，聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不满种聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以优足要求，就要重复执行聚类过程，以优化结果。在重复优化中，可以改变相似化结果。在重复优化中，可以改变相似性度量，也可以选用新的聚类准则。性度量，也可以选用新的聚类准则。本讲稿第十八页，共四十八页1误差平方和准则（最常用的）误差平方和准则（最常用的）假定有混合样本假定有混合样本 ，采用，采用某种相似性度量，

13、某种相似性度量，被聚合成被聚合成 c个分离个分离开的子集，每个子集是一个类型，它们开的子集，每个子集是一个类型，它们分别包含分别包含 个样本。个样本。为了衡量聚类的质量，采用误差平方和为了衡量聚类的质量，采用误差平方和 聚类准则函数，定义为：聚类准则函数，定义为：mj是个集合的中心，可以用来代表c个类型。本讲稿第十九页，共四十八页误差平方和准则（续）误差平方和准则（续）是样本和集合中心的函数。在样本是样本和集合中心的函数。在样本集集X给定的情况下，给定的情况下，的取值取决于的取值取决于c个集合中心。个集合中心。描述个描述个n试验样本聚合试验样本聚合成成c个类型时，所产生的总误差平方和。个类型时

14、，所产生的总误差平方和。越小越好。越小越好。本讲稿第二十页，共四十八页误差平方和准则（续）误差平方和准则（续）误差平方和准则适用于各类样本比较密误差平方和准则适用于各类样本比较密集且样本数目悬殊不大的样本分布。例集且样本数目悬殊不大的样本分布。例如：如：上图的样本分布，共有3个类型，各个类型的样本数目相差不多（10个左右）。类内较密集，误差平方和很小，类别之间距离远。本讲稿第二十一页，共四十八页误差平方和准则（续）误差平方和准则（续）注意：如果不同类型的样本数目相差很注意：如果不同类型的样本数目相差很大，采用误差平方和准则，有可能把样大，采用误差平方和准则，有可能把样本数目多的类型分开，以便达

15、到总的本数目多的类型分开，以便达到总的 最小。如下图所示：最小。如下图所示：本讲稿第二十二页，共四十八页误差平方和准则（续）误差平方和准则（续）下面进一步说明上述问题：下面进一步说明上述问题：例如：有5个样本，如下图所示 本讲稿第二十三页，共四十八页误差平方和准则（续）误差平方和准则（续）虚线为正确类型区分域，实线为采用误差平方和最小准则时的类别区分。虚线划分时：本讲稿第二十四页，共四十八页误差平方和准则（续）误差平方和准则（续）实线划分时：所以 ，如果按误差平方和准则聚类将得到错误结果。本讲稿第二十五页，共四十八页2加权平均平方距离和准则加权平均平方距离和准则定义：加权平均平方距离和准则定义

16、：加权平均平方距离和准则 式中：式中：是类内样本间平均平方距离，是类内样本间平均平方距离，即所有的样本之间距离的平均值即所有的样本之间距离的平均值。本讲稿第二十六页，共四十八页加权平均平方距离和准则（续）加权平均平方距离和准则（续）为为 类的先验概率，可以用样本数类的先验概率，可以用样本数目目 和样本总数目和样本总数目 来估计来估计 因此：因此：本讲稿第二十七页，共四十八页加权平均平方距离和准则（续）加权平均平方距离和准则（续）用用 重新讨论误差平方和准则中所举重新讨论误差平方和准则中所举例子。例子。5个样本，如图所示。个样本，如图所示。本讲稿第二十八页，共四十八页本讲稿第二十九页，共四十八页

17、加权平均平方距离和准则（续）加权平均平方距离和准则（续）虽然虽然 ，但已较接近。所以，当各，但已较接近。所以，当各类样本数目相差悬殊时，使用加权平均类样本数目相差悬殊时，使用加权平均平方距离和准则，要比使用误差平方和平方距离和准则，要比使用误差平方和准则容易得到正确聚类结果。同准则容易得到正确聚类结果。同 一样，一样，越小，样本类内越密集。以聚合中心为越小，样本类内越密集。以聚合中心为极大值的局部区域密度越高，聚类结果极大值的局部区域密度越高，聚类结果越好。越好。本讲稿第三十页，共四十八页3类间距离和准则类间距离和准则类间距离和可用于描述聚类结果的类间类间距离和可用于描述聚类结果的类间距离分布

18、状态。它定义为：距离分布状态。它定义为：加权类间距离和：加权类间距离和：式中，本讲稿第三十一页，共四十八页类间距离和准则（续）类间距离和准则（续）对于两类问题，类间距离常用下式计算对于两类问题，类间距离常用下式计算类间距离和准则描述不同类型之间的分类间距离和准则描述不同类型之间的分离程度，所以值越大，表示各类之间分离程度，所以值越大，表示各类之间分离性好，聚类质量高。离性好，聚类质量高。本讲稿第三十二页，共四十八页4散射矩阵散射矩阵为了对聚类质量有一个全面的描述和考为了对聚类质量有一个全面的描述和考核标准，可以通过散射矩阵引导出一些核标准，可以通过散射矩阵引导出一些准则函数，它们不但反映同类样

19、本的聚准则函数，它们不但反映同类样本的聚集程度，而且也反映不同类之间的分离集程度，而且也反映不同类之间的分离程度。程度。本讲稿第三十三页，共四十八页散射矩阵（续）散射矩阵（续）假定混合样本集假定混合样本集X的的n个样本被聚集成个样本被聚集成c个类型的子集个类型的子集Xj，每个子集有，每个子集有nj个样本，个样本，则类内散射矩阵则类内散射矩阵 定义为：定义为：其中其中 为某一个类型的类内散射矩阵：为某一个类型的类内散射矩阵：本讲稿第三十四页，共四十八页散射矩阵（续）散射矩阵（续）类间散射矩阵类间散射矩阵 定义为：定义为：式中，式中，为各类型的均值向量，为各类型的均值向量，为全为全部样本的均值向量

20、，部样本的均值向量，()为各类型为各类型先验概率。先验概率。本讲稿第三十五页，共四十八页定义全部样本的总散射矩阵定义全部样本的总散射矩阵 为：为：上述上述3个散射矩阵有如下关系：个散射矩阵有如下关系：这一结果表明，对于给定的混合样本集，这一结果表明，对于给定的混合样本集，类内散射的减少，将导致类间散射的增类内散射的减少，将导致类间散射的增加。对某一聚类结果，类内散射越小越加。对某一聚类结果，类内散射越小越好，类间散射越大越好。好，类间散射越大越好。本讲稿第三十六页，共四十八页利用利用 、可以定义如下的可以定义如下的4个聚类个聚类准则：准则：表示矩阵的迹，也就是对角线元素表示矩阵的迹，也就是对角

21、线元素之和，之和，|为行列式。为行列式。J1J4同时考虑了同时考虑了类内的散射和类间散射，为了得到好的类内的散射和类间散射，为了得到好的聚类结果，它们的值越大越好。聚类结果，它们的值越大越好。本讲稿第三十七页，共四十八页两种简单的聚类算法两种简单的聚类算法 介绍两种简单的聚类分析方法，它是对介绍两种简单的聚类分析方法，它是对某些关键性的元素进行试探性的选取，某些关键性的元素进行试探性的选取，使某种聚类准则达到最优，又称为基于使某种聚类准则达到最优，又称为基于试探的聚类算法。试探的聚类算法。l采用最近邻规则的聚类算法采用最近邻规则的聚类算法 l最大最小距离聚类算法最大最小距离聚类算法本讲稿第三十

22、八页，共四十八页1采用最近邻规则的聚类算法采用最近邻规则的聚类算法假设已有混合样本集假设已有混合样本集 ，按，按照最近邻原则进行聚类，算法如下：照最近邻原则进行聚类，算法如下：选取距离阈值选取距离阈值T，并且任取一个样本，并且任取一个样本作为第一个聚类中心作为第一个聚类中心Z1，如：，如：。计算样本计算样本 到到Z1的距离的距离D21：若若 ，则，则 ，否则令，否则令 为第二为第二个聚合中心，个聚合中心，。本讲稿第三十九页，共四十八页采用最近邻规则的聚类算法（续）采用最近邻规则的聚类算法（续）设设 ，计算，计算 到到 Z1和和Z2的距离的距离D31和和D32，若，若 D31 T和和D32 T，

23、则建立第，则建立第三个聚合中心。否则把三个聚合中心。否则把 归于最近邻归于最近邻的聚合中心。依此类推，直到把所有样的聚合中心。依此类推，直到把所有样本都进行分类。本都进行分类。按照某种聚类准则考察聚类结果，若按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值不满意，则重新选取距离阈值T、第一、第一个聚合中心个聚合中心Z1，返回，返回，直到满意，直到满意，算法结束。算法结束。本讲稿第四十页，共四十八页在样本分布一定时，该算法的结果在很在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取大程度上取决于第一个聚合中心的选取和距离阈值的大小。和距离阈值的大小。该算法的优点是简单

24、，如果有样本分布该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选的先验知识用于指导阈值和起始点的选取，则可较快得到合理结果。对于高维取，则可较快得到合理结果。对于高维的样本集来说，则只有经过多次试探，的样本集来说，则只有经过多次试探，并对聚类结果进行验算，从而选择最优并对聚类结果进行验算，从而选择最优的聚类结果。的聚类结果。采用最近邻规则的聚类算法（续）采用最近邻规则的聚类算法（续）本讲稿第四十一页，共四十八页2最大最小距离聚类算法最大最小距离聚类算法该算法以欧氏距离为基础，除首先辨识该算法以欧氏距离为基础，除首先辨识最远的聚类中心外，与上述算法相似。最远的聚类中心外，与上述算法相似。用一个例子说明该算法。用一个例子说明该算法。本讲稿第四十二页，共四十八页例：样本分布如图所示。本讲稿第四十三页，共四十八页本讲稿第四十四页，共四十八页本讲稿第四十五页，共四十八页本讲稿第四十六页，共四十八页本讲稿第四十七页，共四十八页该算法的聚类结果与参数该算法的聚类结果与参数 和起始点和起始点Z1的选取关系重大。若无先验样本分布的选取关系重大。若无先验样本分布知识，则只有用试探法通过多次试探优知识，则只有用试探法通过多次试探优化，若有先验知识用于指导化，若有先验知识用于指导 和和Z1选取，选取，则算法可以很快收敛。则算法可以很快收敛。本讲稿第四十八页，共四十八页