,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选版课件ppt,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,精选版课件ppt,*,数据挖掘算法、原理与实践,王振武,1,精选版课件ppt,数据挖掘算法、原理与实践王振武1精选版课件ppt,八、,K-means,聚类算法,1.,简介,K-means,聚类算法就是,基于距离,的聚类算法（cluster,algorithm,）,主要通过不断地取离种子点最近均值的算法,2,个中心点的,kmeans,2,精选版课件ppt,八、K-means聚类算法1.简介2个中心点的kmeans2,八、,K-means,聚类算法,2.K-means聚类算法原理,K-means聚类算法的基本思想：,一、指定需要划分的簇的个数k值;,二、随机地选择k个初始数据对象点作为初始的聚类中心;,三、计算其余的各个数据对象到这k个初始聚类中心的距离，把数据对象划归到距离它最近的那个中心所处在的簇类中;,四、调整新类并且重新计算出新类的中心。,五、计算聚类准则函数,E,，若,E,不满足收敛条件。重复二、三、四，,六、结束,3,精选版课件ppt,八、K-means聚类算法2.K-means聚类算法原理3,八、,K-means,聚类算法,2.K-means,聚类算法原理,K-Means,算法的工作框架：,4,精选版课件ppt,八、K-means聚类算法2.K-means聚类算法原理4,八、,K-means,聚类算法,2.K-means,聚类算法原理,K-means,算法的工作流程,5,精选版课件ppt,八、K-means聚类算法2.K-means聚类算法原理K,（补充）距离的算法的选择,一般，我们都是以欧拉距离来,计算与种子点的距离。但是，还有几种可以用于,k-means,的距离计算方法。,1）闵可夫斯基距离可以随意取值，可以是负数，也可以是正数，或是无穷大。,2）欧拉距离也就是第一个公式=2的情况,3）市郊区距离公式也就是第一个公式=1的情况,4,）余弦距离（常用于文本）,6,精选版课件ppt,（补充）距离的算法的选择6精选版课件ppt,（补充）距离的算法的选择,闵可夫斯基距离,欧拉距离,市郊区距离公式,7,精选版课件ppt,（补充）距离的算法的选择闵可夫斯基距离欧拉距离市郊区距离公式,八、,K-means,聚类算法,3 K-means,聚类算法特点及应用,3.1 K-means,聚类算法特点,优点：,（,1,）算法简单、快速。,（,2,）对处理大数据集，该算法是相对可伸缩的和高效率的。,（,3,）算法尝试找出使平方误差函数值最小的,k,个划分。,缺点：,（,1,）,K-means,聚类算法只有在簇的平均值被定义的情况下才能使用。,（,2,）要求用户必须事先给出要生成的簇的数目,k,。,（,3,）对初值敏感。,（,4,）不适合于发现非凸面形状的簇，或者大小差别很大的簇。,（,5,）对于“噪声”和孤立点数据敏感。,8,精选版课件ppt,八、K-means聚类算法3 K-means聚类算法特点及应,K-means缺点以及改进,（,1,）,要求用户必须事先给出要生成的簇的数目,k,。这个,k,并不是最好的。,解决,：肘部算法,肘部算法是一种,启发式方法来估计最优聚类数量，称为肘部法则（Elbow Method）。,从图中可以看出，K 值从1到3时，平均畸变程度变化最大。超过3以后，平均畸变程度变化显著降低。因此肘部就是 K=3。,各个类畸变程度（distortions）之和；每个类的畸变程度等于该类重心与其内部成员位置距离的平方和；最优解以成本函数最小化为目标，其中uk是第k个类的重心位置,9,精选版课件ppt,K-means缺点以及改进从图中可以看出，K 值从1到3时,K-means缺点以及改进,（,2,）,K-Means算法需要用初始随机种子点来搞，不同是起点结果不同。可能导致算法陷入局部最优。,解决,：K-Means+算法（初始的聚类中心之间的相互距离要尽可能的远）,1.,先从我们的数据库随机挑个随机点当“种子点”,2.,对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x)。,3.,然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x)中的随机值Random，然后用Random-=D(x)，直到其=0，此时的点就是下一个“种子点”。,4.,重复2和3直到k个聚类中心被选出来,5.,利用这k个初始的聚类中心来运行标准的k-means算法,假设A、B、C、D的D(x)如上图所示，当算法取值Sum(D(x)*random时，该值会以较大的概率落入D(x)较大的区间内，所以对应的点会以较大的概率被选中作为新的聚类中心。,10,精选版课件ppt,K-means缺点以及改进1.先从我们的数据库随机挑个随机点,八、,K-means,聚类算法,3 K-means,聚类算法特点及应用,3.2 K-means,聚类算法应用,（,1,）,K-means,算法在散货船代货运系统中的应用,（,2,）,K-Means,算法在客户细分中的应用,补充：,K-means 适用于各种各样的领域。比如,文本分析、路径规划、神经网络、用户行为、生物信息等,11,精选版课件ppt,八、K-means聚类算法3 K-means聚类算法特点及应,八、,K-means,聚类算法,实例分析一,利用,K-mean,方法，对,AL 12,个数据分成两类。初始的随机点指定为,M1(20,60),，,M2(80,80),。列出每一次分类结果及每一类中的平均值（中心点）。,i=1,2,12,精选版课件ppt,八、K-means聚类算法实例分析一i=1,212精选版课,八、,K-means,聚类算法,13,精选版课件ppt,八、K-means聚类算法13精选版课件ppt,八、,K-means,聚类算法,14,精选版课件ppt,八、K-means聚类算法14精选版课件ppt,八、,K-means,聚类算法,15,精选版课件ppt,八、K-means聚类算法15精选版课件ppt,八、,K-means,聚类算法,16,精选版课件ppt,八、K-means聚类算法16精选版课件ppt,八、,K-means,聚类算法,实例分析二,设有数据样本集合为,X=1,5,10,9,26,32,16,21,14,，将,X,聚为,3,类，即,K=3,。随即选择前三个数值为初始的聚类中心，即,z1=1,z2=5,z3=10,（采用欧氏距离计算）,第一次,第二次,17,精选版课件ppt,八、K-means聚类算法实例分析二第一次第二次17精选版课,八、,K-means,聚类算法,在第五次迭代时，得到的三个簇与第四迭代结果相同，而且准则函数,E,收敛，迭代,结束，结果如下表所示：,k,为迭代次数,18,精选版课件ppt,八、K-means聚类算法在第五次迭代时，得到的三个簇与第四,此课件下载可自行编辑修改，供参考！,感谢您的支持，我们努力做得更好！,精选版课件ppt,此课件下载可自行编辑修改，供参考！精选版课件ppt,