《模式识别原理、应用及实现》 课件 第5章聚类分析

5.1相似性测度5.1.1距离聚类的概念1.概念：“物以类聚”

聚类分析：根据模式之间的相似性对模式进行分类，是一种非监督分类方法。

有个特征值则组成n维向量，称为该样本的特征向量。它相当于特征空间中的一个点，以特征空间中，点间的距离函数作为模式相似性的测量，以“距离”作为模式分类的依据，距离越小，越“相似”。2．相似性的含义注意：聚类分析是否有效，与模式特征向量的分布形式有很大关系。选取的特征向量是否合适非常关键。例：酱油与可乐。5.2.2相似性测度复习：已知向量，则：相似性测度：衡量模式之间相似性的一种尺度。如：距离。1.欧氏距离（Euclid，欧几里德）——简称距离

设为两个

维模式样本，注意：1）各特征向量对应的维上应当是相同的物理量；注意物理量的单位。(D_Distance)

距离越小，越相似。欧氏距离定义为：

某些维上物理量采用的单位发生变化，会导致对同样的点集出现不同聚类结果的现象。5.2.2相似性测度b(5,0)d(4,5)c(1,4)a(0,1)12345012345(a)2）解决方法：使特征数据标准化，使其与变量的单位无关。d(0.4,5)c(0.1,4)a(0,1)123450123b(0.5,0)(b)b(5,0)c(1,0.4)d(4,0.5)a(0,0.1)123012345(c)5.2.2相似性测度对n维向量：

,2.马氏距离(Maharanobis)

平方表达式：式中，

：模式向量；

：均值向量；

：该类模式总体的协方差矩阵。(M_Mean)

(C_covariance)5.2.2相似性测度

表示的概念是各分量上模式样本到均值的距离，也就是在各维上模式的分散情况。越大，离均值越远。优点：排除了模式样本之间的相关影响。当时，马氏距离为欧氏距离。5.2.2相似性测度当m=2时，明氏距离为欧氏距离。

维模式样本向量

间的明氏距离表示为：式中，分别表示的第

个分量。街坊欧氏3.明氏距离(Minkowaki)当m=1时：称为“街坊”距离(“Cityblock”distance)当k=2时：图示5.2.2相似性测度4．汉明(Hamming)距离

设为

维二值（1或－1）模式样本向量，则两个模式向量的各分量取值均不同：；全相同：式中，分别表示的第

个分量。汉明距离：5．角度相似性函数是模式向量之间夹角的余弦。5.2.2相似性测度6．Tanimoto测度用于0，1二值特征的情况，

相似性测度函数的共同点都涉及到把两个相比较的向量的分量值组合起来，但怎样组合并无普遍有效的方法，对具体的模式分类，需视情况作适当选择。5.2.2相似性测度5.2基于距离阈值的聚类算法武汉理工大学5.2.1近邻聚类法2.算法描述①任取样本Xi

作为第一个聚类中心的初始值，如令Z1=X1

。②计算样本X2

到Z1

的欧氏距离，

若，定义一新的聚类中心Z2=X2

；

否则X2∈以Z1为中心的聚类。(T_threshold)1.问题：有N个待分类的模式，要求按距离阈值T分类到以

为聚类中心的模式类中。5.2.1近邻聚类法3.算法特点2）优点：计算简单。（一种虽粗糙但快速的方法）1）局限性：很大程度上依赖于第一个聚类中心的位置选择、待分类模式样本的排列次序、距离阈值T的大小以及样本分布的几何性质等。……依此类推，直到将所有的

个样本都进行分类。③假设已有聚类中心、

，计算

和，若

且

，则建立第三个聚类中心；否则∈离和

中最近者（最近邻的聚类中心）。

用先验知识指导阈值T和起始点Z1的选择，可获得合理的聚类结果。否则只能选择不同的初值重复试探，并对聚类结果进行验算，根据一定的评价标准，得出合理的聚类结果。对结果验算，类内各样本点间距离方差之和太大减小T，修改中心Z。4．算法讨论5.2.1近邻聚类法5.2.2最大最小距离算法1.问题：已知

个待分类的模式

，分类到聚类中心

对应的类别中。2.算法描述①选任意一模式样本做为第一聚类中心

。②选择离

距离最远的样本作为第二聚类中心

。③逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算min(Di1,Di2

)，i=1，…，N（

个最小距离）⑥将样本按最近距离划分到相应聚类中心对应的类别中。⑤重复步骤③④，直到没有新的聚类中心出现为止。④在所有最小距离中选出最大距离，如该最大值达到的一定分数比值(阈值T)以上，则相应的样本点取为新的聚类中心，返回③；否则，寻找聚类中心的工作结束。（θ：用试探法取为一固定分数，如1/2。）则

存在。为使聚类中心更有代表性，可取各类的样本均值作为聚类中心。例k=2时思路总结：先找中心后分类；关键：怎样开新类，聚类中心如何定。5.2.2最大最小距离算法5.2.2最大最小距离算法例2.1对图示模式样本用最大最小距离算法进行聚类分析。①选Z1=X1②距Z1最远，选为Z2。计算T。③对应最小距离中的最大值，且>T，选作Z3。结果：；；。④用全体模式对三个聚类中心计算最小距离中的最大值，无>T情况，停止寻找中心。⑤聚类10个最小距离中，

对应的距离>T,③5.3层次聚类法郭志强主讲武汉理工大学5.3层次聚类法思路：每个样本先自成一类，然后按距离准则逐步合并，减少类数。1.算法描述1）

个初始模式样本自成一类，即建立

类：计算各类之间（即各样本间）的距离，得一维距离矩阵

。“0”表示初始状态。(G_Group)2）假设已求得距离矩阵（

为逐次聚类合并的次数），找出

中的最小元素，将其对应的两类合并为一类。由此建立新的分类：3）计算合并后新类别之间的距离，得。4）跳至第2步，重复计算及合并。

结束条件：1）取距离阈值

，当的最小分量超过给定值

时，算法停止。所得即为聚类结果。2）或不设阈值

，一直将全部样本聚成一类为止，输出聚类的分级树。5.3层次聚类法例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。解：（1）将每一样本看作单独一类，得：计算各类间欧氏距离：…，，，；；5.3层次聚类法D(0)000000＊（2）将最小距离对应的类和合并为一类，

得新的分类。计算聚类后的距离矩阵：由递推出。得距离矩阵：5.3层次聚类法D(0)000000＊

D(1)00000（3）将中最小值对应的类合为一类，得。

D(2)0000＊5.3层次聚类法（4）将中最小值对应的类合为一类，得。

D(2)00＊00

D(3)000若给定的阈值为，中的最小元素，聚类结束。若无阈值，继续分下去，最终全部样本归为一类。可给出聚类过程的树状表示图。5.3层次聚类法5.4动态聚类算法武汉理工大学基本思想两种常用算法：*K-均值算法(或C-均值算法)*迭代自组织的数据分析算法(ISODATA,iterativeself-organizingdataanalysistechniquesalgorithm)

判断合理性选初始中心聚类合理不合理输出修改K-均值算法K-均值算法的聚类准则：聚类中心的选择应使准则函数

极小，即使

的值极小。

基于使聚类准则函数最小化，准则函数：聚类集中每一样本点到该类中心的距离平方和。对于第

个聚类集，准则函数定义为：第

个聚类集（域），聚类中心为

；

：第

个聚类集

中所包含的样本个数。对所有

个模式类有应有

即

可解得上式表明，

类的聚类中心应选为该类样本的均值。1.算法描述括号内序号：迭代运算的次序号。（1）任选

个初始聚类中心：Z1(1)，Z2(1)，…，ZK(1)

K-均值算法（2）按最小距离原则将其余样品分配到

个聚类中心中的某一个，即：若，则注意：

——迭代运算次序号；

——聚类中心的个数。

：第

类的样本数。（3）计算各个聚类中心的新向量值：（4）如果，则回到（2），将模式

样本逐个重新分类，重复迭代计算。这里：分别计算

个聚类中的样本均值向量，故称-均值算法。，算法收敛，计算完毕。如果K-均值算法聚类过程中，聚类中心位置或个数发生变化。“动态”聚类法？2.算法讨论结果受到所选聚类中心的个数和其初始位置，以及模式样本的几何性质及读入次序等的影响。实际应用中需要试探不同的K值和选择不同的聚类中心起始值。K-均值算法例2.3：已知20个模式样本如下，试用K-均值算法分类。解：①取K=2，并选：②计算距离，聚类：：

：K-均值算法：

：

……，可得到：③计算新的聚类中：④判断：，故返回第②步。K-均值算法②从新的聚类中心得：：┋：有：③计算聚类中心：K-均值算法④返回第②步，以，

为中心进行聚类。②以新的聚类中心分类，求得的分类结果与前一次迭代结果相同：③计算新聚类中心向量值，聚类中心与前一次结果相同，即：④，故算法收敛，得聚类中心为结果图示：K-均值算法图2.10K-均值算法聚类结果X1X4X3X5X8X9X7X10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X20K-均值算法模式识别36/justinruan/Learning-ML学以致用，知行合一（实践篇）K均值的编程算例375.5.1K均值算法回顾（1）随机地选择k个样本，每个样本初始地代表了一个簇的平均值或中心。（2）对剩余的每个样本根据其与各个簇中心的距离，将它赋给最近的簇，然后重新计算每个簇的平均值。（3）这个过程不断重复，直到准则函数收敛（比如：质心不变）。38K均值算例使用K-Means算法实现对样本的分类，选择的样本为二维特征，设置两个聚类中心，画出样本聚类情况，并判断[2,3],[6,9]分别属于哪一类。20个样本如下：

[0,0],[1,0],[0,1],[1,1],[2,1],[1,2],[2,2],[3,2],[6,6],[7,6],[8,6],[6,7],[7,7],[8,7],[9,7],[7,8],[8,8],[9,8],[8,9],[9,9]39K均值的实现40训练41计算一个样本到k个中心的距离初始化簇中心42聚类与可视化43预测44K均值与SK-Learn455.5.2sk-learn里的k-均值算法KMeans

算法需要指定numberofclusters（簇的数量）。它可以很好地scales（扩展）到largenumberofsamples（大量样本），并已经被广泛应用于许多不同领域的应用领域。46classsklearn.cluster.KMeans(n_clusters=8,init='k-means++',n_init=10,max_iter=300,tol=0.0001,precompute_distances='auto',verbose=0,random_state=None,copy_x=True,n_jobs=1,algorithm='auto')sklearn.cluster.KmeansParametersn_clusters:要形成的簇数init

:初始化方法,defaultsto‘k-means++’n_init:使用不同质心种子运行k-means算法的次数。最终结果将是n_init连续运行的最佳输出。max_iter:最大的迭代次数tol

:算法逐渐收敛的相对容差47classsklearn.cluster.KMeans(n_clusters=8,init=‘k-means++’,n_init=10,max_iter=300,tol=0.0001,......')5.5.2sklearn里的k-均值算法1.生成一组包含两个特征的200个样本，有4个类中心48Kmeans模型拟合设置类别数量为3，并计算出其拟合后的成本在这里，cost是计算训练样本到其所属的聚类中心点的距离的总和49显示聚类的结果50这里聚成3类,成本为-668不同k的聚类结果5111.3K-均值对文档进行聚类分析有一个博客平台，用户在平台上发布博客，我们如何对博客进行聚类分析，以方便展示不同类别下的热门文章呢？准备数据我们使用前面使用过的语料库“数据20news-18828.tar.gz”选择语料库的一部分生成聚类用的样本集，（四个主题的文档，3949个文档）5211.3.2加载数据集53计算TF-IDF向量54计算TF-IDF设定的参数：Max_df=0.4表示一个单词在40%的文档中出现过，则它是高频词，对聚类没有作用，将它从词典中剔除。Min_df=2表示一个单词只在2个以下的文档里出现（词频太低），则也将它从词典中剔除。Max_features将词典按TF-IDF权重从高到低进行排序，然后取前面权重高的单词构成词典。11.3.3文本聚类分析55将要进行3次聚类分析，选择最好的聚类结果输出inertia_：float样本到它们最近的聚类中心的距离平方和。56clusteringdocuments...InitializationcompleteIteration0,inertia7480.523Iteration1,inertia3843.548Iteration2,inertia3829.504Iteration3,inertia3824.543Iteration4,inertia3822.478Iteration5,inertia3821.589Iteration6,inertia3821.275Iteration7,inertia3821.143Iteration8,inertia3821.053Iteration9,inertia3821.030…Iteration13,inertia3820.988Iteration14,inertia3820.981Iteration15,inertia3820.975Iteration16,inertia3820.971Iteration17,inertia3820.969Convergedatiteration17:centershift0.000000e+00withintolerance4.896692e-07InitializationcompleteIteration0,inertia7535.355Iteration1,inertia3843.625Iteration2,inertia3832.804Iteration3,inertia3828.910Iteration4,inertia3826.489Iteration5,inertia3824.398Iteration6,inertia3823.290Iteration7,inertia3822.602Iteration8,inertia3822.134Iteration9,inertia3821.872...Iteration25,inertia3821.390Iteration26,inertia3821.387Iteration27,inertia3821.381Iteration28,inertia3821.380Iteration29,inertia3821.377Convergedatiteration29:centershift0.000000e+00withintolerance4.896692e-07InitializationcompleteIteration0,inertia7456.814Iteration1,inertia3843.981Iteration2,inertia3830.044Iteration3,inertia3823.183Iteration4,inertia3821.185It