K-means聚类算法ppt课件.ppt

数据挖掘算法 原理与实践 1 八 K means聚类算法 1 简介K means聚类算法就是基于距离的聚类算法 clusteralgorithm 主要通过不断地取离种子点最近均值的算法 2个中心点的kmeans 2 八 K means聚类算法 2 K means聚类算法原理K means聚类算法的基本思想 一 指定需要划分的簇的个数k值 二 随机地选择k个初始数据对象点作为初始的聚类中心 三 计算其余的各个数据对象到这k个初始聚类中心的距离 把数据对象划归到距离它最近的那个中心所处在的簇类中 四 调整新类并且重新计算出新类的中心 五 计算聚类准则函数E 若E不满足收敛条件 重复二 三 四 六 结束 3 八 K means聚类算法 2 K means聚类算法原理K Means算法的工作框架 4 八 K means聚类算法 2 K means聚类算法原理 K means算法的工作流程 5 补充 距离的算法的选择一般 我们都是以欧拉距离来计算与种子点的距离 但是 还有几种可以用于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 对于 噪声 和孤立点数据敏感 8 K means缺点以及改进 1 要求用户必须事先给出要生成的簇的数目k 这个k并不是最好的 解决 肘部算法肘部算法是一种启发式方法来估计最优聚类数量 称为肘部法则 ElbowMethod 从图中可以看出 K值从1到3时 平均畸变程度变化最大 超过3以后 平均畸变程度变化显著降低 因此肘部就是K 3 各个类畸变程度 distortions 之和 每个类的畸变程度等于该类重心与其内部成员位置距离的平方和 最优解以成本函数最小化为目标 其中uk是第k个类的重心位置 9 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 八 K means聚类算法 3K means聚类算法特点及应用3 2K means聚类算法应用 1 K means算法在散货船代货运系统中的应用 2 K Means算法在客户细分中的应用补充 K means适用于各种各样的领域 比如文本分析 路径规划 神经网络 用户行为 生物信息等 11 八 K means聚类算法 实例分析一利用K mean方法 对A L12个数据分成两类 初始的随机点指定为M1 20 60 M2 80 80 列出每一次分类结果及每一类中的平均值 中心点 i 1 2 12 八 K means聚类算法 13 八 K means聚类算法 14 八 K means聚类算法 15 八 K means聚类算法 16 八 K means聚类算法 实例分析二设有数据样本集合为X 1 5 10 9 26 32 16 21 14 将X聚为3类 即K 3 随即选择前三个数值为初始的聚类中心 即z1 1 z2