参考博客 :

• 【数据挖掘】聚类算法 简介 ( 基于划分的聚类方法 | 基于层次的聚类方法 | 基于密度的聚类方法 | 基于方格的聚类方法 | 基于模型的聚类方法 )
• 【数据挖掘】基于划分的聚类方法 ( K-Means 算法简介 | K-Means 算法步骤 | K-Means 图示 )
• 【数据挖掘】K-Means 一维数据聚类分析示例
• 【数据挖掘】K-Means 二维数据聚类分析 ( K-Means 迭代总结 | K-Means 初始中心点选择方案 | K-Means 算法优缺点 | K-Means 算法变种 )

一、 K-Means 聚类算法流程

---

K-Means 算法 步骤 : 给定数据集 $\mathrm{X}$ , 该数据集有 $\mathrm{n}$ 个样本 , 将其分成 $\mathrm{K}$ 个聚类 ;

① 中心点初始化 : 为 $\mathrm{K}$ 个聚类分组选择初始的中心点 , 这些中心点称为 Means ; 可以依据经验 , 也可以随意选择 ;

② 计算距离 : 计算 $\mathrm{n}$ 个对象与 $\mathrm{K}$ 个中心点 的距离 ; ( 共计算 $\mathrm{n}\times \mathrm{K}$ 次 )

③ 聚类分组 : 每个对象与 $\mathrm{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$ 与 $20$ 的距离就是差值的绝对值 $19$ ;

	样本值
聚类		$C_1$	$C_2$	$C_3$
中心值		$1$	$20$	$40$
$P_1$	$1$	$0$	$19$	$39$
$P_2$	$3$	$2$	$17$	$37$
$P_3$	$5$	$4$	$15$	$35$
$P_4$	$8$	$7$	$12$	$32$
$P_5$	$9$	$8$	$11$	$31$
$P_6$	$11$	$10$	$9$	$29$
$P_7$	$12$	$11$	$8$	$28$
$P_8$	$13$	$12$	$7$	$27$
$P_9$	$37$	$36$	$17$	$3$
$P_{10}$	$43$	$42$	$23$	$3$
$P_{11}$	$45$	$44$	$25$	$5$
$P_{12}$	$49$	$48$	$29$	$9$
$P_{13}$	$51$	$50$	$31$	$11$
$P_{14}$	$65$	$64$	$45$	$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}

新的中心点计算过程 :

${\mathrm{C}}_1=\frac{1+3+5+8+9}{5}=5$

${\mathrm{C}}_2=\frac{11+12+13}{3}=12$

${\mathrm{C}}_3=\frac{37+43+45+49+51+65}{6}=48$

2、 第二次迭代

第二次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;

	年龄
聚类		$C_1$	$C_2$	$C_3$
中心值		$5$	$12$	$48$
$P_1$	$1$	$4$	$11$	$47$
$P_2$	$3$	$2$	$9$	$45$
$P_3$	$5$	$0$	$7$	$43$
$P_4$	$8$	$3$	$4$	$40$
$P_5$	$9$	$4$	$3$	$39$
$P_6$	$11$	$6$	$1$	$37$
$P_7$	$12$	$7$	$0$	$36$
$P_8$	$13$	$8$	$1$	$35$
$P_9$	$37$	$25$	$17$	$11$
$P_{10}$	$43$	$38$	$31$	$5$
$P_{11}$	$45$	$40$	$33$	$3$
$P_{12}$	$49$	$44$	$37$	$1$
$P_{13}$	$51$	$46$	$39$	$3$
$P_{14}$	$65$	$60$	$53$	$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}

新的中心点计算过程 :

${\mathrm{C}}_1=\frac{1+3+5+8}{5}=4$

${\mathrm{C}}_2=\frac{9+11+12+13}{3}=11$

${\mathrm{C}}_3=\frac{37+43+45+49+51+65}{6}=48$

3、 第三次迭代

第三次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;

	年龄
聚类		$C_1$	$C_2$	$C_3$
中心值		$4$	$11$	$48$
$P_1$	$1$	$3$	$10$	$47$
$P_2$	$3$	$1$	$8$	$45$
$P_3$	$5$	$1$	$6$	$43$
$P_4$	$8$	$4$	$3$	$40$
$P_5$	$9$	$5$	$2$	$39$
$P_6$	$11$	$7$	$0$	$37$
$P_7$	$12$	$8$	$1$	$36$
$P_8$	$13$	$9$	$2$	$35$
$P_9$	$37$	$33$	$26$	$11$
$P_{10}$	$43$	$39$	$32$	$5$
$P_{11}$	$45$	$41$	$34$	$3$
$P_{12}$	$49$	$45$	$38$	$1$
$P_{13}$	$51$	$47$	$40$	$3$
$P_{14}$	$65$	$61$	$54$	$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}

新的中心点计算过程 :

${\mathrm{C}}_1=\frac{1+3+5}{5}=3$

${\mathrm{C}}_2=\frac{8+9+11+12+13}{3}=10$

${\mathrm{C}}_3=\frac{37+43+45+49+51+65}{6}=48$

4、 第四次迭代

第四次迭代 : 计算每个样本值与每个中心点的距离 , 将样本分类到最近的中心点所在的分组 , 计算每个分组新的中心值 ;

	年龄
聚类		$C_1$	$C_2$	$C_3$
中心值		$4$	$11$	$48$
$P_1$	$1$	$3$	$10$	$47$
$P_2$	$3$	$1$	$8$	$45$
$P_3$	$5$	$1$	$6$	$43$
$P_4$	$8$	$4$	$3$	$40$
$P_5$	$9$	$5$	$2$	$39$
$P_6$	$11$	$7$	$0$	$37$
$P_7$	$12$	$8$	$1$	$36$
$P_8$	$13$	$9$	$2$	$35$
$P_9$	$37$	$33$	$26$	$11$
$P_{10}$	$43$	$39$	$32$	$5$
$P_{11}$	$45$	$41$	$34$	$3$
$P_{12}$	$49$	$45$	$38$	$1$
$P_{13}$	$51$	$47$	$40$	$3$
$P_{14}$	$65$	$61$	$54$	$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}

新的中心点计算过程 :

${\mathrm{C}}_1=\frac{1+3+5}{5}=3$

${\mathrm{C}}_2=\frac{8+9+11+12+13}{3}=10$

${\mathrm{C}}_3=\frac{37+43+45+49+51+65}{6}=48$

第四次迭代与第三次迭代值相同 , 因此第三次迭代的结果就是 K-Means 聚类算法最终结果 ;

详细解析参考 【数据挖掘】K-Means 一维数据聚类分析示例