第4章 聚类(一).ppt

非监督学习 ——聚类 什么是聚类 分类问题是利用已知类别的样品来构造分类器。其训练集样品是已知类别的，所以又称为有监督分类。在已知类别样品的指导下对单个待测样品进行分类。 聚类问题则不同，它事先不了解一批样品中的每一个样品的类别或者其他的先验知识，而唯一的分类根据是样品的特性。利用样品的特性来构造分类器，这种分类称为无监督分类，通常叫做聚类。 相似性 聚类分析是对样本数据进行分类分析的一个工具，许多学科要根据所测得的或感知到的相似性对数据进行分类，把样本数据归入到各个聚合类中，且在同一个聚合类中的模式比不同聚合类中的模式更相似，从而对模式间的相互关系做出估计。 相似性度量 设有样本集 ，要求按某种相似性将其分类，怎样实现？ 聚类分析符合“物以类聚，人以群分“的原则，它把相似性大的样本聚集为一个类型，在特征空间里占据着一个局部区域。每个局部区域都形成一个聚合中心，聚合中心代表相应类型。 如下图中，(a)有一个聚合中心，(b)、(c)有两个。 聚类分析避免了估计类概率密度的困难，对每个聚合中心来说都是局部密度极大值位置，其附近密度高，距离越远密度越小。 聚类分析的关键问题：如何在聚类过程中自动地确定类型数目c。 实际工作中，也可以给定值作为算法终止的条件。 聚类分析的结果与特征的选取有很大的关系。不同的特征，分类的结果不同。 1.距离相似性度量 一个模式样本，对应特征空间里的一个点。如果模式的特征是适当选择的，也就是各维特征对于分类来说都是有效的，那么同类样本就会密集地分布在一个区域里，不同类的模式样本就会远离。因此，点间距离远近反映了相应模式样本所属类型有无差异，可以作为样本相似性度量。距离越近，相似性越大，属于一个类型。聚类分析中，最常用的就是距离相似性。 （1）欧氏距离（Euler） 欧氏距离简称距离，模式样本向量 x与y之间的欧氏距离定义为： d为特征空间的维数。 当 较小时，表示x与y在一个类型区域，反之，则不在一个类型区域。这里有一个门限的选择问题。若选择过大，则全部样本被视作一个唯一类型；若选取过小，则可能造成每个样本都单独构成一个类型。必须正确选择门限值以保证正确分类。 （1）欧氏距离（续） 另外，模式特征坐标单位的选取也会强烈地影响聚类结果。 例如：一个二维模式，一个特征是长度，另一个特征是压力。 当长度由厘米变为米，在 中长度特征的比重会下降，同样，若把比重单位由毫米汞柱高度变成厘米汞柱高度， 中压力特征的影响也会下降。 （1）欧氏距离（续） 可以用图表示上述情况： 从上图看出，(b)、(c)特征空间划分是不同的。(b)中 为一类， 为另一类，(c) 中 为一类， 为另一类。 （1）欧氏距离（续） 另外，使用欧氏距离度量时，还要注意模式样本测量值的选取，应该是有效反映类别属性特征（各类属性的代表应均衡）。但马氏距离可解决不均衡（一个多，一个少）的问题。 例如，取5个样本，其中有4个反映对分类有意义的特征A，只有1个对分类有意义的特征B，欧氏距离的计算结果，则主要体现特征A。 （2）马氏（Mahalanobis）距离 定义：马氏距离的平方 其中， 为协方差矩阵。 马氏距离排除了不同特征之间相关性的影响，其关键在于协方差矩阵的计算。当为对角阵时，各特征之间才完全独立；当为单位矩阵时，马氏距离等于欧氏距离。 马氏距离比较适用于对样本已有初步分类的情况，做进一步考核、修正。 基本概念 协方差: Cov(X,Y)=E{ [ X-E(X) ] [ Y-E(Y) ] } 协方差矩阵 Σ=E{(X-E[X])(X-E[X])T]} 矩阵中的第(i,j)个元素是xi与xj的协方差 （3）明氏（Minkowsky）距离 定义：明氏距离: 它是若干距离函数的通式： 时，等于欧氏距离； 时，称为“街区”（city block）距离。 （4）切氏（Chebyshev）距离 2. 角度相似性度量 样本x与y之间的角度相似性度量定义为它们之间夹角的余弦，即 也是单位向量之间的点积（内积）。 越大， x与y越相似。常用于情报检索、植物分类、疾病分类。 2. 角度相似性度量 满足：