Python语言PPT14.3k均值和k中心点聚类 (2).pptx

1、K-means快速聚类出发点：希望克服层次聚类法在大样本时产生的出发点：希望克服层次聚类法在大样本时产生的困难，提高聚类效率困难，提高聚类效率做法：做法：通过用户通过用户事先指定聚类数目事先指定聚类数目的方式提高效率的方式提高效率因此，分层聚类可以对不同的聚类数而产生一因此，分层聚类可以对不同的聚类数而产生一系列的聚类解，而快速聚类只能产生单一的聚系列的聚类解，而快速聚类只能产生单一的聚类解类解Company Namewww.SucaiFK-means聚类是一种基于距离的聚类算法，采用距离作为相似是一种基于距离的聚类算法，采用距离作为相似性的评价指标。性的评价指标。ABCDEFIGJHK-me

2、ans聚类算法举例怎样把A,B.H,J 分成两类呢?A(1,4)B(2,4)CDEFIGJHRandomly choose A,B as the centre and K=2.ExampleAAdABdACdADdAFdAGdAHdAIdAJdAEdBAdBBdBCdBDdBFdBGdBHdBIdBJdBEd0111.412.243.614.475.394.245101.41122.833.614.473.614.24 So,we classify A,C as a cluster and B,E,D,F,G,H,I and J as another cluster.Step 1 and 2.

3、ABCDEFGHIJABdmeans distance ABACdBCdA(1,4)B(2,4)CDEFIGJHRandomly choose A,B as the centre and K=2.ExampleStep 3.),(jyixcenterji)5.4,1()254,211(,CA)875.2,75.3(,JIHGFEDB The new centers of the two clusters are(1,4.5)and(3.75,2.875)cluster 1cluster 2new centerABCDEFIGJH(1,4.5)(3.75,2.875)ExampleAdBdCdD

4、dFdGdHdIdJdEdAdBdCdDdFdGdHdIdJdEd0.51.120.51.121.83.914.725.594.615.322.972.083.482.753.580.911.532.411.892.25Step 2 again.,as the centre and K=2.So,we classify A,B,C,D,E as a cluster and F,G,H,I,J as another cluster.ABCDEFGHIJABCDEFIGJH(1,4.5)(3.75,2.875)ExampleStep 3 again.,as the centre and K=2.)

5、,(jyixcenterji)8.4,6.1(,EDCBAP)6.1,8.4(,JIHGFQ The new centers of the t w o c l u s t e r s a r e P(1.6,4.8)and Q(4.8,1.6)cluster 2cluster 1new centerABCDEFIGJHP(1.6,4.8)Q(4.8,1.6)ExamplePAdPBdPCdPDdPFdPGdPHdPIdPJdPEdQAdQBdQCdQDdQFdQGdQHdQIdQJdQEd10.890.630.451.263.694.405.224.495.104.493.695.104.45

6、.220.890.451.2610.63Step 2 again.So,we classify A,B,C,D,E as a cluster and F,G,H,I,J as another cluster.ABCDEFGHIJABCDEFIGJHP(1.6,4.8)Q(4.8,1.6)ExampleStep 3 again.),(jyixcenterji)8.4,6.1(,EDCBAM)6.1,8.4(,JIHGFN The new centers of the two clusters are equal to the original P(1.6,4.8)and Q(4.8,1.6)P,

7、Q as the centre and K=2.new centercluster 2cluster 1FinalABCDEFIGJHcluster 1cluster 2Clustering finished!Disadvantages o n e o f t h e m a i n disadvantages to k-means is the fact that you must specify the number of clusters(K)as an input to the algorithm.As designed,the algorithm is not capable of

8、determining the appropriate number of clusters and depends upon the user to identify this in advance.K=2K=3K-means聚类Example012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerA

9、ssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign思路：思路：1.1.指定最后要聚成指定最后要聚成K K类类2.2.指定指定k k个样本作为初始类中心个样本作为初始类中心3.3.按照距按照距k k个中心距离最近的原则把每个样本分派到各中心所在个中心距离最近的原则把每个样本分派到各中心所在的类中去的类中去,形成一个新的形成一个新的k k类，完成一次迭代类，完成一次迭代4.4.重新计算重新计算k k个类的类中心个类的类中心(计算每类各变量的

10、均值计算每类各变量的均值,以均值点作以均值点作为类中心为类中心)5.5.重复重复3 3步和步和4 4步，直到达到指定的迭代次数或达到终止迭代的条步，直到达到指定的迭代次数或达到终止迭代的条件件达到指定迭代次数达到指定迭代次数(maximum iteration),maximum iteration),默认默认1010次。次。收敛标准收敛标准(convergence),convergence),默认默认0.020.02，即：本次迭代产生的任意新类，即：本次迭代产生的任意新类,各各中心位置变化较小中心位置变化较小.其中最大的变化率小于其中最大的变化率小于2%.2%.K-means聚类算法的评价指标

11、簇内平方和整体平方和对于任意数据集而言，聚类误差平方和和质心数量高度相关，随着质心增加误差平方和将逐渐下降，虽然下降过程偶尔会有小幅起伏，不是严格递减评价指标误差平方和误差平方和还与数据集本身数据量大小、量纲大小、数据维度高度相关，数据量越大、量纲越大、维度越高则在相同质心数量情况下误差平方和也将更大K-means聚类算法的优点1）算法简单、快速。2）能处理大数据集，因为它的复杂度大约是O(nkt)。通常kn。这个算法经常以局部最优结束。3）算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果较好。K-means聚类算法的缺点1）K-me

12、ans聚类算法只有在簇的平均值被定义的情况下才能使用，不适用于某些应用，如涉及有分类属性的数据不适用。2）要求用户必须事先给出要生成的簇的数目k。3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。5）对于“噪声”和孤立点数据敏感非凸形状的簇Company Namewww.SucaiFK-meansK-means聚类的聚类的Map ReduceMap Reduce并行化算法并行化算法基本思路：将需要重复执行的步骤写到基本思路：将需要重复执行的步骤写到MapMap函数中。函数中。Map()Map()函数计算每个对象到中心点的距离，选函

13、数计算每个对象到中心点的距离，选择距每个对象最近的中心点，并输出择距每个对象最近的中心点，并输出 对。对。Reduce()Reduce()函数计算每个聚类中对象的距离均值函数计算每个聚类中对象的距离均值，并将这，并将这K K个均值作为下一轮初始中心点个均值作为下一轮初始中心点K-means聚类算法的Sklearn实现import numpy as npimport matplotlib.pyplot as pltfrom sklearn.cluster import KMeansX1,X2=,fr=open(C:km.txt)for line in fr.readlines():lineArr

14、=line.strip().split()X1.append(int(lineArr0)X2.append(int(lineArr1)X=np.array(list(zip(X1,X2).reshape(len(X1),2)model=KMeans(3).fit(X)#调用fit方法进行聚类，聚类数为3colors=b,g,r,cmarkers=o,s,x,vplt.axis(0,6,0,6)for i,l in enumerate(model.labels_):plt.plot(X1i,X2i,color=colorsl,marker=markersl,ls=None)#下面用倒三角形绘制均

15、值点centroids=model.cluster_centers_#centroids保存了所有均值点for i in range(3):#其中3表示聚类的类别数 plt.plot(centroidsi0,centroidsi1,markers3)plt.show()用SPSS进行k-均值聚类结果n若k=2，初始聚类中心取(5,3)、(1,2)，则若k=2，初始聚类中心取(3,5)、(2,1)，则4.4 K-medoids聚类算聚类算法法2023-11-202023-11-20基于划分的聚类方法基于划分的聚类方法nk-均值（均值（k-means）聚类算法）聚类算法n优点：速度快优点：速度快n

16、缺点：对离群点很敏感缺点：对离群点很敏感nk-中心点（中心点（k-Medoids）聚类算法）聚类算法n可解决对离群点敏感的问题可解决对离群点敏感的问题2023-11-20k-中心点聚类方法中心点聚类方法nk-中心点中心点(k-Medoids):n不采用簇中对象的平均值作为参照点不采用簇中对象的平均值作为参照点,而是而是选用簇选用簇中位置最中心的对象中位置最中心的对象,即中心点即中心点(medoid)作为参照作为参照点来代表该簇点来代表该簇.012345678910012345678910012345678910012345678910012345678910012345678910k-中心点中心点k-均值均值2023-11-20k-中心点聚类方法中心点聚类方法(续续)n找聚类中的代表对象找聚类中的代表对象(中心点中心点)nPAM(Partitioning Around Medoids,1987)nPAM 对于较小的数据集非常有效对于较小的数据集非常有效,但不能很好地扩展到但不能很好地扩展到大型数据集大型数据集nCLARA(Kaufmann&Rousseeuw,1990)抽样抽样nCLA