模式识别2010聚类分析.pdf

《模式识别2010聚类分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模式识别原理模式识别原理华中科技大学图像识别与人工智能研究所图像分析与智能系统研究室曹治国2010-10-201第第22章聚类分析章聚类分析••聚类分析的概念聚类分析的概念••相似性测度与聚类准则相似性测度与聚类准则••聚类算法聚类算法顺序聚类算法K均值算法K中值算法模糊K均值算法层次聚类算法谱聚类算法分类分类ClassificationClassification与聚类与聚类ClusteringClustering2010-10-203聚类的定义聚类的定义设X是数据集，即X={x,x,...,x}12N定义X的

2、m聚类R，将X分割成m个集合（聚类）C1,…Cm,使其满足下面三个条件：C≠∅,i=2,1,...,mimUC=Xii=1C∩C=∅,i≠j,i,j=2,1,...,mij2010-10-204聚类分析步骤聚类分析步骤FeatureSelection选择合适的特征描述样本ProximityMeasure选择合适的测度描述样本之间如何“相似”或“不相似”ClusteringCriterion选择合适的聚类准则ClusteringAlgorithm选择特定的算法，用于揭示数据集的聚类结构ValidationandIn

3、terpretationoftheResult结果的验证与判定2010-10-208为什么研究相似性测度为什么研究相似性测度“相似”、“不相似”依赖于聚类的类型致密型聚类、长条形聚类、球形或椭圆聚类所采用的相似度会不一样2010-10-209为什么研究聚类准则为什么研究聚类准则羊狗猫麻雀蜥蜴青蛙蓝鲨海鸥金鱼红鲣毒蛇繁衍后代的方式金鱼红鲣麻雀蜥蜴青蛙蓝鲨海鸥羊狗猫毒蛇肺是否存在麻雀蜥蜴金鱼红鲣海鸥羊狗猫青蛙蓝鲨毒蛇生活环境2010-10-2010为什么对结果需要验证判定为什么对结果需要验证判定专家知识2类还是4类？

4、2010-10-2011为什么研究聚类算法为什么研究聚类算法考虑聚类的数量：给定时间和资源，将集合X中的特征向量xi，i=1,…,N,N到聚类中的最好办法是识别所有的划分，并根据事先确定的准则选择最可能的聚类。令S(N,m)表示将N个向量聚类到m组的所有可能结果S(N,1)=1；S(N,N)=1；当m>Nm>NS(N,m))==0k令L表示N-1个向量分到k类的所有可能，k=m，m-1N−1第N个向量mL或者添加到N−1中的任一个成员的聚类中m−1L或者对N−1的每个成员形成一个新聚类S(N,m)=mS(N−,1

5、m)+S(N−,1m−)12010-10-2012为什么研究聚类算法为什么研究聚类算法S(N,m)=mS(N−,1m)+S(N−,1m−)1上式的解为：m1m−iiNS(N,m)=∑(−)1Cmim!i=0（该公式作为习题请课后证明）S(15)3,=2375101S(20)4,=4523211590168S(100)5,=10!!如果要评估100个样本分到5类的所有可能聚类，计算机计算每个聚类需要−12104810秒，则大约年后才会得到最可判断的聚类2010-10-2013为什么研究聚类算法为什么研究聚类算法聚类

6、算法可以视为：通过考虑包含在X中所有可能划分集合的一小部分，就可以得到可判断聚类的方案这个结果依赖于使用的算法和准则2010-10-2014第第22章聚类分析章聚类分析••聚类分析的概念聚类分析的概念••相似性测度与聚类准则相似性测度与聚类准则••聚类算法聚类算法顺序聚类算法K均值算法K中值算法模糊K均值算法层次聚类算法谱聚类算法第第22章聚类分析章聚类分析聚类测度不相似性测度（DissimilarityMeasure,DM）相似性测度（SimilarityMeasure,SM）GGG对于∀x,y,z∈Xd(•)

7、X上不相似性测度可用距离空间来度量，它必须满足：GGGG)1(d(x,y)>0∀x≠y,d(x,x)=0GGGG)2(d(x,y)=d(y,x)GGGGGG)3(d(x,y)≤d(x,z)+d(y,z)X上相似性测度可用s(•)来度量，它必须满足：GGGG)1(−∞

8、G设x=(x1,x2,"xn,)'y=(y1,y2,"yn)'GGGGn22/11，欧氏(Euclidean)距离：d(x,y)=

9、

10、x−y

11、

12、=[∑(xi−yi)]i=1GGn2，绝对值距离:d(x,y)=∑

13、xi−yi

14、i=1GG3，切氏(Chebyshev)距离:d(x,y)=max

15、xi−yi

16、iGGn4，明氏(Minkowski)距离:m/1md(x,y)=[∑