教学第8章-Kmeans聚类算法课件

数据挖掘算法、原理与实践王振武*数据挖掘算法、原理与实践王振武*1八、K-means聚类算法1.简介

K-means聚类算法就是基于距离的聚类算法（clusteralgorithm）

主要通过不断地取离种子点最近均值的算法2个中心点的kmeans*八、K-means聚类算法1.简介2个中心点的kmeans*2八、K-means聚类算法2.K-means聚类算法原理

K-means聚类算法的基本思想：一、指定需要划分的簇的个数k值;二、随机地选择k个初始数据对象点作为初始的聚类中心;三、计算其余的各个数据对象到这k个初始聚类中心的距离，把数据对象划归到距离它最近的那个中心所处在的簇类中;四、调整新类并且重新计算出新类的中心。五、计算聚类准则函数E，若E不满足收敛条件。重复二、三、四，六、结束*八、K-means聚类算法2.K-means聚类算法原理*3八、K-means聚类算法2.K-means聚类算法原理K-Means算法的工作框架：*八、K-means聚类算法2.K-means聚类算法原理*4八、K-means聚类算法2.K-means聚类算法原理K-means算法的工作流程*八、K-means聚类算法2.K-means聚类算法原理K5（补充）距离的算法的选择一般，我们都是以欧拉距离来计算与种子点的距离。但是，还有几种可以用于k-means的距离计算方法。1）闵可夫斯基距离——λ可以随意取值，可以是负数，也可以是正数，或是无穷大。2）欧拉距离——也就是第一个公式λ=2的情况3）市郊区距离公式——也就是第一个公式λ=1的情况4）余弦距离（常用于文本）——*（补充）距离的算法的选择*6（补充）距离的算法的选择

闵可夫斯基距离欧拉距离市郊区距离公式*（补充）距离的算法的选择闵可夫斯基距离欧拉距离市郊区距离公式7八、K-means聚类算法3K-means聚类算法特点及应用

3.1K-means聚类算法特点优点：（1）算法简单、快速。（2）对处理大数据集，该算法是相对可伸缩的和高效率的。（3）算法尝试找出使平方误差函数值最小的k个划分。缺点： （1）K-means聚类算法只有在簇的平均值被定义的情况下才能使用。（2）要求用户必须事先给出要生成的簇的数目k。（3）对初值敏感。（4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。（5）对于“噪声”和孤立点数据敏感。*八、K-means聚类算法3K-means聚类算法特点及应8K-means缺点以及改进（1）要求用户必须事先给出要生成的簇的数目k。这个k并不是最好的。解决：肘部算法肘部算法是一种启发式方法来估计最优聚类数量，称为肘部法则（ElbowMethod）。从图中可以看出，K值从1到3时，平均畸变程度变化最大。超过3以后，平均畸变程度变化显著降低。因此肘部就是K=3。各个类畸变程度（distortions）之和；每个类的畸变程度等于该类重心与其内部成员位置距离的平方和；最优解以成本函数最小化为目标，其中uk是第k个类的重心位置*K-means缺点以及改进从图中可以看出，K值从1到3时9K-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)较大的区间内，所以对应的点会以较大的概率被选中作为新的聚类中心。*K-means缺点以及改进1.先从我们的数据库随机挑个随机点10八、K-means聚类算法3K-means聚类算法特点及应用

3.2K-means聚类算法应用

（1）K-means算法在散货船代货运系统中的应用（2）K-Means算法在客户细分中的应用补充：K-means适用于各种各样的领域。比如文本分析、路径规划、神经网络、用户行为、生物信息等*八、K-means聚类算法3K-means聚类算法特点及应11八、K-means聚类算法实例分析一利用K-mean方法，对A~L12个数据分成两类。初始的随机点指定为M1(20,60)，M2(80,80)。列出每一次分类结果及每一类中的平均值（中心点）。

i=1,2*八、K-means聚类算法实例分析一

i=1,2*12八、K-means聚类算法*八、K-means聚类算法*13八、K-means聚类算法*八、K-means聚类算法*14八、K-means聚类算法

*八、K-means聚类算法

*15八、K-means聚类算法*八、K-means聚类算法*16八、K-means聚类算法实例分析二设有数据样本集合为X={1,5,10,9,26,32,16,21,14}，将X聚为3类，即K=3。随即选择前三个数值为初始的聚类中心，即z1=1,z2=5,z3=10（采用欧氏距离计算）第一次第二次*八、K-means聚类算法实例分析二第一次第二次*17八、K-means聚类算法在第五次迭代时，得到的三个簇与第四迭代结果相同，而且准则函数E收敛，迭代结束，结果如下表所示：

k为迭代次数*八、K-means聚类算法在第五次迭代时，得到的三个簇与第四18数据挖掘算法、原理与实践王振武*数据挖掘算法、原理与实践王振武*19八、K-means聚类算法1.简介

K-means聚类算法就是基于距离的聚类算法（clusteralgorithm）

主要通过不断地取离种子点最近均值的算法2个中心点的kmeans*八、K-means聚类算法1.简介2个中心点的kmeans*20八、K-means聚类算法2.K-means聚类算法原理

K-means聚类算法的基本思想：一、指定需要划分的簇的个数k值;二、随机地选择k个初始数据对象点作为初始的聚类中心;三、计算其余的各个数据对象到这k个初始聚类中心的距离，把数据对象划归到距离它最近的那个中心所处在的簇类中;四、调整新类并且重新计算出新类的中心。五、计算聚类准则函数E，若E不满足收敛条件。重复二、三、四，六、结束*八、K-means聚类算法2.K-means聚类算法原理*21八、K-means聚类算法2.K-means聚类算法原理K-Means算法的工作框架：*八、K-means聚类算法2.K-means聚类算法原理*22八、K-means聚类算法2.K-means聚类算法原理K-means算法的工作流程*八、K-means聚类算法2.K-means聚类算法原理K23（补充）距离的算法的选择一般，我们都是以欧拉距离来计算与种子点的距离。但是，还有几种可以用于k-means的距离计算方法。1）闵可夫斯基距离——λ可以随意取值，可以是负数，也可以是正数，或是无穷大。2）欧拉距离——也就是第一个公式λ=2的情况3）市郊区距离公式——也就是第一个公式λ=1的情况4）余弦距离（常用于文本）——*（补充）距离的算法的选择*24（补充）距离的算法的选择

闵可夫斯基距离欧拉距离市郊区距离公式*（补充）距离的算法的选择闵可夫斯基距离欧拉距离市郊区距离公式25八、K-means聚类算法3K-means聚类算法特点及应用

3.1K-means聚类算法特点优点：（1）算法简单、快速。（2）对处理大数据集，该算法是相对可伸缩的和高效率的。（3）算法尝试找出使平方误差函数值最小的k个划分。缺点： （1）K-means聚类算法只有在簇的平均值被定义的情况下才能使用。（2）要求用户必须事先给出要生成的簇的数目k。（3）对初值敏感。（4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。（5）对于“噪声”和孤立点数据敏感。*八、K-means聚类算法3K-means聚类算法特点及应26K-means缺点以及改进（1）要求用户必须事先给出要生成的簇的数目k。这个k并不是最好的。解决：肘部算法肘部算法是一种启发式方法来估计最优聚类数量，称为肘部法则（ElbowMethod）。从图中可以看出，K值从1到3时，平均畸变程度变化最大。超过3以后，平均畸变程度变化显著降低。因此肘部就是K=3。各个类畸变程度（distortions）之和；每个类的畸变程度等于该类重心与其内部成员位置距离的平方和；最优解以成本函数最小化为目标，其中uk是第k个类的重心位置*K-means缺点以及改进从图中可以看出，K值从1到3时27K-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)较大的区间内，所以对应的点会以较大的概率被选中作为新的聚类中心。*K-means缺点以及改进1.先从我们的数据库随机挑个随机点28八、K-means聚类算法3K-means聚类算法特点及应用

3.2K-means聚类算法应用

（1）K-means算法在散货船代货运系统中的应用（2）K-Means算法在客户细分中的应用补充：K-means适用于各种各样的领域。比如文本分析、路径规划、神经网络、用户行为、生物信息等*八、K-means聚类算法3K-means聚类算法特点及应29八、K-means聚类算法实例分析一利用K-mean方法，对A~L12个数据分成两类。初始的随机点指定为M1(20,60)，M2(80,80)。列出每一次分类结果及每一类中的平均值（中心点）。

i=1,2*八、K-means聚类算法实例分析一

i=1,2*30八、K-means聚类算法*八、K-means聚类算法*31八、K-means聚类算法*八、K-means聚类算法*32八、K-means聚类算法

*八、K-means聚类算法

*33八、K-means聚类算法*八、K-means聚类算法*34八