社区首页 >专栏 >【数据挖掘】数据挖掘总结 ( K-Means 聚类算法 | 一维数据的 K-Means 聚类 ) ★

【数据挖掘】数据挖掘总结 ( K-Means 聚类算法 | 一维数据的 K-Means 聚类 ) ★

韩曙亮

发布于 2023-03-28 12:31:02

9520

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

参考博客 :

一、 K-Means 聚类算法流程

K-Means 算法步骤 : 给定数据集

$\rm X$

, 该数据集有

$\rm n$

个样本 , 将其分成

$\rm K$

个聚类 ;

① 中心点初始化 : 为

$\rm K$

个聚类分组选择初始的中心点 , 这些中心点称为 Means ; 可以依据经验 , 也可以随意选择 ;

② 计算距离 : 计算

$\rm n$

个对象与

$\rm K$

个中心点的距离 ; ( 共计算

$\rm n \times K$

次 )

③ 聚类分组 : 每个对象与

$\rm K$

个中心点的值已计算出 , 将每个对象分配给距离其最近的中心点对应的聚类 ;

④ 计算中心点 : 根据聚类分组中的样本 , 计算每个聚类的中心点 ;

⑤ 迭代直至收敛 : 迭代执行 ② ③ ④ 步骤 , 直到 聚类算法收敛 , 即 中心点和分组经过多少次迭代都不再改变 , 也就是本次计算的中心点与上一次的中心点一样 ;

给定一组样本 , 和一组中心点 , 计算所有样本到所有中心点的距离 , 给样本分组 , 计算分好组的样本的中心点 , 重新计算所有样本到所有中心点的距离 , 继续进行分组 , 一直迭代执行上述操作 , 直到连续两次样本分组不再变化 ;

二、一维数据的 K-Means 聚类

给定数据集

$\rm \{ 1,3,5,8,9,11,12,13,37,43,45,49,51,65 \}$

, 初始中心点

$\rm \{ 1, 20, 40 \}$

, 使用 K-Means 算法对数据集进行聚类分析 ;

1、第一次迭代

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

距离计算示例 :

$1$

与

$20$

的距离就是差值的绝对值

$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

$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$

重新分组 :

$\rm K_1 = \{ 1 , 3 , 5 , 8, 9 \}$

$\rm K_2 = \{ 11 , 12 , 13 \}$

$\rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \}$

新的中心点计算过程 :

$\rm C_1 = \cfrac{1 + 3 + 5 + 8 + 9}{5} = 5$

$\rm C_2 = \cfrac{11 + 12 + 13}{3} = 12$

$\rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 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

$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$

重新分组 :

$\rm K_1 = \{ 1 , 3 , 5 , 8 \}$

$\rm K_2 = \{ 9, 11 , 12 , 13 \}$

$\rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \}$

新的中心点计算过程 :

$\rm C_1 = \cfrac{1 + 3 + 5 + 8 }{5} = 4$

$\rm C_2 = \cfrac{9 + 11 + 12 + 13}{3} = 11$

$\rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 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

$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$

重新分组 :

$\rm K_1 = \{ 1 , 3 , 5 \}$

$\rm K_2 = \{ 8, 9, 11 , 12 , 13 \}$

$\rm K_3 = \{ 37 , 43 , 45 , 49 , 51 , 65 \}$

新的中心点计算过程 :

$\rm C_1 = \cfrac{1 + 3 + 5 }{5} = 3$

$\rm C_2 = \cfrac{8 + 9 + 11 + 12 + 13}{3} = 10$

$\rm C_3 = \cfrac{37 + 43 + 45 + 49 + 51 + 65}{6} = 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