聚类分析2.ppt

聚类分析 2 ?本节所要讨论的内容:将未知类别的样本集划分为若干子集(类、簇、聚类),划分的直接结果是完成了样本的分类,可能的间接结果是确定了分类器的参数。由于所有样本是没有类别标记的,所以通常称其为无监督学****根本思想是按照物以类聚的思路出发的,对未知类别的样本集根据样本之间的相似程度进行分类操作,相似的归为一类,不相似的归为另一类。这种过程称为聚类分析。 1 聚类分析 2 ?聚类分析之关键: ?什么叫做两个样本的相似? ?相似的度量如何? ?两个样本相似到什么程度归为一类? ?下面所要讨论的是相似性测度以及聚类准则。 2 聚类分析 2——相似性测度以及聚类准则?相似性测度:为了能够将样本集划分为不同的类别必须定义一种相似性度量(测度),用于度量样本之间的相似性及其差异。?常用的方法: ?明考斯基距离( Minkowski distance ) ?当q q = = 1 1时时, , d d称为称为曼哈坦距离曼哈坦距离( ( Manhattan Manhattan distance distance )也称为街坊距离)也称为街坊距离 q qpp qqj xi xj xi xj xi xjid)||...||| (|),( 2211???????|| ...||||),( 2211ppj xi xj xi xj xi xjid??????? 3 聚类分析 2——相似性测度以及聚类准则?相似性测度?常用的方法: ?当 q=2 时, d 就成为欧几里德距离: ?距离函数有如下特性: ? d(i,j) ? 0 ? d(i,i) = 0 ? d(i,j) = d(j,i) ? d(i,j) ? d(i,k) + d(k,j) )||...||| (|),( 2222 211ppj xi xj xi xj xi xjid??????? 4 聚类分析 2——相似性测度以及聚类准则?相似性测度?常用的方法: ?角度相似性度量函数: 可以认为是两个单位向量,之内积, 即为向量 x i与x j间夹角的余旋。|| || || || )(),( ji jTijixx xxxxS??|| ||/ iixx || ||/ jjxx5 聚类分析 2——相似性测度以及聚类准则?相似性度量方法的共同点:都涉及把两个向量的分量组合起来,但是怎样组合并没有有效地方法,对于具体的模式分类,需视情况作适当的的选择或将几种不同的方法联合使用。 6 聚类分析 2——相似性测度以及聚类准则?聚类准则: 为了评价聚类结果,必须定义一种准则函数。有了模式相似性测度和准则函数后,聚类就变成了使准则函数的极值的优化问题了。?常用的准则函数为:误差平方和准则函数。?若N i是第 i类R i中的所含的样本数, m i是这些样本的均值,即有 1 ii x R i m x N ??? 7 聚类分析 2——相似性测度以及聚类准则?聚类准则?误差平方和准则函数: ?误差平方和聚类准则 J度量了用 c个聚类中心 m 1 , m 2 , …, m c代表 c个样本子集时所产生的总的误差。对于不同的聚类, J的值一般是不同的,使得 J最小的聚类是误差平方和准则下的最优结果。一般称其为最小方差划分。?????? ciRx i imxJ 1 2 || ||8 聚类分析 2——分级聚类?聚类问题的三个要素:相似性测度、聚类准则和聚类算法。选定了相似性测度和聚类准则之后,现在的问题就是使用什么样的算法找出使得准则函数取极值的最好聚类结果。?聚类算法包括两大类:非迭代的分级聚类算法与迭代的动态聚类算法。 9 聚类分析 2——分级聚类?聚类分析的最终任务是:把含有 N个没有类别标记的样本集分成若干类。 10