- 一、 K-Means 聚类算法流程
- 二、 一维数据的 K-Means 聚类
- 1、 第一次迭代
- 2、 第二次迭代
- 3、 第三次迭代
- 4、 第四次迭代
参考博客 :
- 【数据挖掘】聚类算法 简介 ( 基于划分的聚类方法 | 基于层次的聚类方法 | 基于密度的聚类方法 | 基于方格的聚类方法 | 基于模型的聚类方法 )
- 【数据挖掘】基于划分的聚类方法 ( K-Means 算法简介 | K-Means 算法步骤 | K-Means 图示 )
- 【数据挖掘】K-Means 一维数据聚类分析示例
- 【数据挖掘】K-Means 二维数据聚类分析 ( K-Means 迭代总结 | K-Means 初始中心点选择方案 | K-Means 算法优缺点 | K-Means 算法变种 )
K-Means 算法 步骤 : 给定数据集 X \rm X X , 该数据集有 n \rm n n 个样本 , 将其分成 K \rm K K 个聚类 ;
① 中心点初始化 : 为 K \rm K K 个聚类分组选择初始的中心点 , 这些中心点称为 Means ; 可以依据经验 , 也可以随意选择 ;
② 计算距离 : 计算 n \rm n n 个对象与 K \rm K K 个中心点 的距离 ; ( 共计算 n × K \rm n \times K n×K 次 )
③ 聚类分组 : 每个对象与 K \rm K K 个中心点的值已计算出 , 将每个对象分配给距离其最近的中心点对应的聚类 ;
④ 计算中心点 : 根据聚类分组中的样本 , 计算每个聚类的中心点 ;
⑤ 迭代直至收敛 : 迭代执行 ② ③ ④ 步骤 , 直到 聚类算法收敛 , 即 中心点 和 分组 经过多少次迭代都不再改变 , 也就是本次计算的中心点与上一次的中心点一样 ;
给定 一组样本 , 和 一组中心点 , 计算 所有样本 到 所有中心点 的距离 , 给样本 分组 , 计算分好组的样本的中心点 , 重新计算所有样本到所有中心点的距离 , 继续进行分组 , 一直迭代执行上述操作 , 直到连续两次样本分组不再变化 ;
二、 一维数据的 K-Means 聚类给定数据集 { 1 , 3 , 5 , 8 , 9 , 11 , 12 , 13 , 37 , 43 , 45 , 49 , 51 , 65 } \rm \{ 1,3,5,8,9,11,12,13,37,43,45,49,51,65 \} {1,3,5,8,9,11,12,13,37,43,45,49,51,65} , 初始中心点 { 1 , 20 , 40 } \rm \{ 1, 20, 40 \} {1,20,40} , 使用 K-Means 算法对数据集进行聚类分析 ;
1、 第一次迭代第一次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;
距离计算示例 : 1 1 1 与 20 20 20 的距离就是差值的绝对值 19 19 19 ;
样本值聚类 C 1 C_1 C1 C 2 C_2 C2 C 3 C_3 C3中心值 1 1 1 20 20 20 40 40 40 P 1 P_{1} P1 1 1 1 0 0 0 19 19 19 39 39 39 P 2 P_2 P2 3 3 3 2 2 2 17 17 17 37 37 37 P 3 P_3 P3 5 5 5 4 4 4 15 15 15 35 35 35 P 4 P_4 P4 8 8 8 7 7 7 12 12 12 32 32 32 P 5 P_5 P5 9 9 9 8 8 8 11 11 11 31 31 31 P 6 P_6 P6 11 11 11 10 10 10 9 9 9 29 29 29 P 7 P_7 P7 12 12 12 11 11 11 8 8 8 28 28 28 P 8 P_8 P8 13 13 13 12 12 12 7 7 7 27 27 27 P 9 P_9 P9 37 37 37 36 36 36 17 17 17 3 3 3 P 10 P_{10} P10 43 43 43 42 42 42 23 23 23 3 3 3 P 11 P_{11} P11 45 45 45 44 44 44 25 25 25 5 5 5 P 12 P_{12} P12 49 49 49 48 48 48 29 29 29 9 9 9 P 13 P_{13} P13 51 51 51 50 50 50 31 31 31 11 11 11 P 14 P_{14} P14 65 65 65 64 64 64 45 45 45 25 25 25重新分组 :
K 1 = { 1 , 3 , 5 , 8 , 9 } \rm K_1 = \{ 1 , 3 , 5 , 8, 9 \} K1={1,3,5,8,9}
K 2 = { 11 , 12 , 13 } \rm K_2 = \{ 11 , 12 , 13 \} K2={11,12,13}
K 3 = { 37 , 43 , 45 , 49 , 51 , 65 } \rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \} K3={37,43,45,49,51,65}
新的中心点计算过程 :
C 1 = 1 + 3 + 5 + 8 + 9 5 = 5 \rm C_1 = \cfrac{1 + 3 + 5 + 8 + 9}{5} = 5 C1=51+3+5+8+9=5
C 2 = 11 + 12 + 13 3 = 12 \rm C_2 = \cfrac{11 + 12 + 13}{3} = 12 C2=311+12+13=12
C 3 = 37 + 43 + 45 + 49 + 51 + 65 6 = 48 \rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 48 C3=637+43+45+49+51+65=48
2、 第二次迭代第二次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;
年龄聚类 C 1 C_1 C1 C 2 C_2 C2 C 3 C_3 C3中心值 5 5 5 12 12 12 48 48 48 P 1 P_{1} P1 1 1 1 4 4 4 11 11 11 47 47 47 P 2 P_2 P2 3 3 3 2 2 2 9 9 9 45 45 45 P 3 P_3 P3 5 5 5 0 0 0 7 7 7 43 43 43 P 4 P_4 P4 8 8 8 3 3 3 4 4 4 40 40 40 P 5 P_5 P5 9 9 9 4 4 4 3 3 3 39 39 39 P 6 P_6 P6 11 11 11 6 6 6 1 1 1 37 37 37 P 7 P_7 P7 12 12 12 7 7 7 0 0 0 36 36 36 P 8 P_8 P8 13 13 13 8 8 8 1 1 1 35 35 35 P 9 P_9 P9 37 37 37 25 25 25 17 17 17 11 11 11 P 10 P_{10} P10 43 43 43 38 38 38 31 31 31 5 5 5 P 11 P_{11} P11 45 45 45 40 40 40 33 33 33 3 3 3 P 12 P_{12} P12 49 49 49 44 44 44 37 37 37 1 1 1 P 13 P_{13} P13 51 51 51 46 46 46 39 39 39 3 3 3 P 14 P_{14} P14 65 65 65 60 60 60 53 53 53 17 17 17重新分组 :
K 1 = { 1 , 3 , 5 , 8 } \rm K_1 = \{ 1 , 3 , 5 , 8 \} K1={1,3,5,8}
K 2 = { 9 , 11 , 12 , 13 } \rm K_2 = \{ 9, 11 , 12 , 13 \} K2={9,11,12,13}
K 3 = { 37 , 43 , 45 , 49 , 51 , 65 } \rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \} K3={37,43,45,49,51,65}
新的中心点计算过程 :
C 1 = 1 + 3 + 5 + 8 5 = 4 \rm C_1 = \cfrac{1 + 3 + 5 + 8 }{5} = 4 C1=51+3+5+8=4
C 2 = 9 + 11 + 12 + 13 3 = 11 \rm C_2 = \cfrac{9 + 11 + 12 + 13}{3} = 11 C2=39+11+12+13=11
C 3 = 37 + 43 + 45 + 49 + 51 + 65 6 = 48 \rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 48 C3=637+43+45+49+51+65=48
3、 第三次迭代第三次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;
年龄聚类 C 1 C_1 C1 C 2 C_2 C2 C 3 C_3 C3中心值 4 4 4 11 11 11 48 48 48 P 1 P_{1} P1 1 1 1 3 3 3 10 10 10 47 47 47 P 2 P_2 P2 3 3 3 1 1 1 8 8 8 45 45 45 P 3 P_3 P3 5 5 5 1 1 1 6 6 6 43 43 43 P 4 P_4 P4 8 8 8 4 4 4 3 3 3 40 40 40 P 5 P_5 P5 9 9 9 5 5 5 2 2 2 39 39 39 P 6 P_6 P6 11 11 11 7 7 7 0 0 0 37 37 37 P 7 P_7 P7 12 12 12 8 8 8 1 1 1 36 36 36 P 8 P_8 P8 13 13 13 9 9 9 2 2 2 35 35 35 P 9 P_9 P9 37 37 37 33 33 33 26 26 26 11 11 11 P 10 P_{10} P10 43 43 43 39 39 39 32 32 32 5 5 5 P 11 P_{11} P11 45 45 45 41 41 41 34 34 34 3 3 3 P 12 P_{12} P12 49 49 49 45 45 45 38 38 38 1 1 1 P 13 P_{13} P13 51 51 51 47 47 47 40 40 40 3 3 3 P 14 P_{14} P14 65 65 65 61 61 61 54 54 54 17 17 17重新分组 :
K 1 = { 1 , 3 , 5 } \rm K_1 = \{ 1 , 3 , 5 \} K1={1,3,5}
K 2 = { 8 , 9 , 11 , 12 , 13 } \rm K_2 = \{ 8, 9, 11 , 12 , 13 \} K2={8,9,11,12,13}
K 3 = { 37 , 43 , 45 , 49 , 51 , 65 } \rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \} K3={37,43,45,49,51,65}
新的中心点计算过程 :
C 1 = 1 + 3 + 5 5 = 3 \rm C_1 = \cfrac{1 + 3 + 5 }{5} = 3 C1=51+3+5=3
C 2 = 8 + 9 + 11 + 12 + 13 3 = 10 \rm C_2 = \cfrac{8 + 9 + 11 + 12 + 13}{3} = 10 C2=38+9+11+12+13=10
C 3 = 37 + 43 + 45 + 49 + 51 + 65 6 = 48 \rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 48 C3=637+43+45+49+51+65=48
4、 第四次迭代第四次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;
年龄聚类 C 1 C_1 C1 C 2 C_2 C2 C 3 C_3 C3中心值 4 4 4 11 11 11 48 48 48 P 1 P_{1} P1 1 1 1 3 3 3 10 10 10 47 47 47 P 2 P_2 P2 3 3 3 1 1 1 8 8 8 45 45 45 P 3 P_3 P3 5 5 5 1 1 1 6 6 6 43 43 43 P 4 P_4 P4 8 8 8 4 4 4 3 3 3 40 40 40 P 5 P_5 P5 9 9 9 5 5 5 2 2 2 39 39 39 P 6 P_6 P6 11 11 11 7 7 7 0 0 0 37 37 37 P 7 P_7 P7 12 12 12 8 8 8 1 1 1 36 36 36 P 8 P_8 P8 13 13 13 9 9 9 2 2 2 35 35 35 P 9 P_9 P9 37 37 37 33 33 33 26 26 26 11 11 11 P 10 P_{10} P10 43 43 43 39 39 39 32 32 32 5 5 5 P 11 P_{11} P11 45 45 45 41 41 41 34 34 34 3 3 3 P 12 P_{12} P12 49 49 49 45 45 45 38 38 38 1 1 1 P 13 P_{13} P13 51 51 51 47 47 47 40 40 40 3 3 3 P 14 P_{14} P14 65 65 65 61 61 61 54 54 54 17 17 17重新分组 :
K 1 = { 1 , 3 , 5 } \rm K_1 = \{ 1 , 3 , 5 \} K1={1,3,5}
K 2 = { 8 , 9 , 11 , 12 , 13 } \rm K_2 = \{ 8, 9, 11 , 12 , 13 \} K2={8,9,11,12,13}
K 3 = { 37 , 43 , 45 , 49 , 51 , 65 } \rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \} K3={37,43,45,49,51,65}
新的中心点计算过程 :
C 1 = 1 + 3 + 5 5 = 3 \rm C_1 = \cfrac{1 + 3 + 5 }{5} = 3 C1=51+3+5=3
C 2 = 8 + 9 + 11 + 12 + 13 3 = 10 \rm C_2 = \cfrac{8 + 9 + 11 + 12 + 13}{3} = 10 C2=38+9+11+12+13=10
C 3 = 37 + 43 + 45 + 49 + 51 + 65 6 = 48 \rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 48 C3=637+43+45+49+51+65=48
第四次迭代与第三次迭代值相同 , 因此第三次迭代的结果就是 K-Means 聚类算法最终结果 ;
详细解析参考 【数据挖掘】K-Means 一维数据聚类分析示例
