Kmeans聚类算法ppt课件.ppt

数据挖掘算法、原理与实践王振武1八、K- K-means聚类算法就是基于距离的聚类算法(clusteralgorithm)主要通过不断地取离种子点最近均值的算法2个中心点的kmeans2八、K--means聚类算法原理K-means聚类算法的基本思想:一、指定需要划分的簇的个数k值;二、随机地选择k个初始数据对象点作为初始的聚类中心;三、计算其余的各个数据对象到这k个初始聚类中心的距离,把数据对象划归到距离它最近的那个中心所处在的簇类中;四、调整新类并且重新计算出新类的中心。五、计算聚类准则函数E,若E不满足收敛条件。重复二、三、四,六、结束3八、K--means聚类算法原理K-Means算法的工作框架:4八、K--means聚类算法原理K-means算法的工作流程5(补充)距离的算法的选择一般,我们都是以欧拉距离来计算与种子点的距离。但是,还有几种可以用于k-means的距离计算方法。1)闵可夫斯基距离——λ可以随意取值,可以是负数,也可以是正数,或是无穷大。2)欧拉距离——也就是第一个公式λ=2的情况3)市郊区距离公式——也就是第一个公式λ=1的情况4)余弦距离(常用于文本)——6(补充)距离的算法的选择闵可夫斯基距离欧拉距离市郊区距离公式7八、K-means聚类算法3K--means聚类算法特点优点:(1)算法简单、快速。(2)对处理大数据集,该算法是相对可伸缩的和高效率的。(3)算法尝试找出使平方误差函数值最小的k个划分。缺点: (1)K-means聚类算法只有在簇的平均值被定义的情况下才能使用。(2)要求用户必须事先给出要生成的簇的数目k。(3)对初值敏感。(4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。(5)对于“噪声”和孤立点数据敏感。8K-means缺点以及改进(1)要求用户必须事先给出要生成的簇的数目k。这个k并不是最好的。解决:肘部算法肘部算法是一种启发式方法来估计最优聚类数量,称为肘部法则(ElbowMethod)。从图中可以看出,K值从1到3时,平均畸变程度变化最大。超过3以后,平均畸变程度变化显著降低。因此肘部就是K=3。各个类畸变程度(distortions)之和;每个类的畸变程度等于该类重心与其内部成员位置距离的平方和;最优解以成本函数最小化为目标,其中uk是第k个类的重心位置9K-means缺点以及改进(2)K-Means算法需要用初始随机种子点来搞,不同是起点结果不同。可能导致算法陷入局部最优。解决:K-Means++算法(初始的聚类中心之间的相互距离要尽可能的远)“种子点”,我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里,然后把这些距离加起来得到Sum(D(x))。,再取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先取一个能落在Sum(D(x))中的随机值Random,然后用Random-=D(x),直到其<=0,此时的点就是下一个“种子点”。-means算法假设A、B、C、D的D(x)如上图所示,当算法取值Sum(D(x))*random时,该值会以较大的概率落入D(x)较大的区间内,所以对应的点会以较大的概率被选中作为新的聚类中心。10