进击数据挖掘十大算法(一):K-Means
聚类与分类的区别
分类:类别是已知的,通过对已知分类的数据进行训练和学习,找到这些不同类的特征,再对未分类的数据进行分类。属于监督学习。
聚类:事先不知道数据会分为几类,通过聚类分析将数据聚合成几个群体。聚类不需要对数据进行训练和学习。属于无监督学习。
关于监督学习和无监督学习,这里给一个简单的介绍:是否有监督,就看输入数据是否有标签,输入数据有标签,则为有监督学习,否则为无监督学习。
Github源码:QzmVc1/Data-Mining/K-Means/
参考链接:
一、概述
1.1 什么是聚类分析
聚类分析是在数据中发现数据对象之间的关系,将数据进行分组,组内的相似性越大,组间的差别越大,则聚类效果越好。
1.2 不同的簇类型
聚类旨在发现有用的对象簇,在现实中我们用到很多的簇的类型,使用不同的簇类型划分数据的结果是不同的,如下的几种簇类型。
1.2.1 明显分离的
可以看到(a)中不同组中任意两点之间的距离都大于组内任意两点之间的距离,明显分离的簇不一定是球形的,可以具有任意的形状。
1.2.2 基于原型的
簇是对象的集合,其中每个对象到定义该簇的原型的距离比其他簇的原型距离更近,如(b)所示的原型即为中心点,在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的基于中心的簇,最常用的K-Means就是这样的一种簇类型。
这样的簇趋向于球形。
1.2.3 基于密度的
簇是对象的密度区域,(d)所示的是基于密度的簇,当簇不规则或相互盘绕,并且有早上和离群点事,常常使用基于密度的簇定义。
1.3 基本的聚类分析算法
1.3.1 K均值:
基于原型的、划分的距离技术,它试图发现用户指定个数(K)的簇。
1.3.2 凝聚的层次距离:
开始时,每个点都作为一个单点簇,然后,重复的合并两个最靠近的簇,直到尝试单个、包含所有点的簇。
1.3.3 DBSCAN:
一种基于密度的划分距离的算法,簇的个数有算法自动的确定,低密度中的点被视为噪声而忽略,因此其不产生完全聚类。
1.4 距离量度
不同的距离量度会对距离的结果产生影响,常见的距离量度如下所示:
二、K-Means聚类
2.1 算法思想:
1 | 选择K个点作为初始质心 |
2.2 具体解释:
K-Means聚类算法的大致意思就是“物以类聚,人以群分”:
- 首先输入 k 的值,即我们指定希望通过聚类得到 k 个分组;
- 从数据集中随机选取 k 个数据点作为初始大佬(质心);
- 对集合中每一个小弟,计算与每一个大佬的距离,离哪个大佬距离近,就跟定哪个大佬。
- 这时每一个大佬手下都聚集了一票小弟,这时候召开选举大会,每一群选出新的大佬(即通过算法选出新的质心)。
- 如果新大佬和旧大佬之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大,趋于稳定,或者说收敛),可以认为我们进行的聚类已经达到期望的结果,算法终止。
- 如果新大佬和旧大佬距离变化很大,需要迭代3~5步骤。
下面举个非常形象简单的例子:
有6个点,从图上看应该可以分成两堆,前三个点一堆,后三个点另一堆。现在我手工地把K-Means计算过程演示一下,同时检验是不是和预期一致:
1.设定 k 值为2
2.选择初始大佬(就选 P1 和 P2)
3.计算小弟与大佬的距离:
从上图可以看出,所有的小弟都离 P2 更近,所以次站队的结果是:
A 组:P1
B 组:P2、P3、P4、P5、P6
4.召开选举大会:
A 组没什么可选的,大佬就是自己
B 组有5个人,需要重新选大佬,这里要注意选大佬的方法是每个人 X 坐标的平均值和 Y 坐标的平均值组成的新的点,为新大佬,也就是说这个大佬是“虚拟的”。因此,B 组选出新大哥的坐标为:P((1+3+8+9+10)/5,(2+1+8+10+7)/5)=(6.2,5.6)。
综合两组,新大哥为 P1’(0,0),P2’(6.2,5.6),而P2-P6重新成为小弟。
5.再次计算小弟到大佬的距离:
这时可以看到P2、P3离P1更近,P4、P5、P6离P哥更近,所以第二次站队的结果是:
A 组:P1、P2、P3
B 组:P4、P5、P6
6.第二届选举大会:
同样的方法选出新的虚拟大佬:P1’(1.33,1),P2’(9,8.33),P1-P6都成为小弟。
7.第三次计算小弟到大佬的距离:
这时可以看到 P1、P2、P3 离 P哥1 更近,P4、P5、P6离 P哥2 更近,所以第二次站队的结果是:
A 组:P1、P2、P3
B 组:P4、P5、P6
我们可以发现,这次站队的结果和上次没有任何变化了,说明已经收敛,聚类结束,聚类结果和我们最开始设想的结果完全一致。
三、K-Means算法Python实现
Github源码:QzmVc1/Data-Mining/K-Means/
3.1 Python代码
1 | """ |
3.2 数据集
共80组数据:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
801.658985 4.285136
-3.453687 3.424321
4.838138 -1.151539
-5.379713 -3.362104
0.972564 2.924086
-3.567919 1.531611
0.450614 -3.302219
-3.487105 -1.724432
2.668759 1.594842
-3.156485 3.191137
3.165506 -3.999838
-2.786837 -3.099354
4.208187 2.984927
-2.123337 2.943366
0.704199 -0.479481
-0.392370 -3.963704
2.831667 1.574018
-0.790153 3.343144
2.943496 -3.357075
-3.195883 -2.283926
2.336445 2.875106
-1.786345 2.554248
2.190101 -1.906020
-3.403367 -2.778288
1.778124 3.880832
-1.688346 2.230267
2.592976 -2.054368
-4.007257 -3.207066
2.257734 3.387564
-2.679011 0.785119
0.939512 -4.023563
-3.674424 -2.261084
2.046259 2.735279
-3.189470 1.780269
4.372646 -0.822248
-2.579316 -3.497576
1.889034 5.190400
-0.798747 2.185588
2.836520 -2.658556
-3.837877 -3.253815
2.096701 3.886007
-2.709034 2.923887
3.367037 -3.184789
-2.121479 -4.232586
2.329546 3.179764
-3.284816 3.273099
3.091414 -3.815232
-3.762093 -2.432191
3.542056 2.778832
-1.736822 4.241041
2.127073 -2.983680
-4.323818 -3.938116
3.792121 5.135768
-4.786473 3.358547
2.624081 -3.260715
-4.009299 -2.978115
2.493525 1.963710
-2.513661 2.642162
1.864375 -3.176309
-3.171184 -3.572452
2.894220 2.489128
-2.562539 2.884438
3.491078 -3.947487
-2.565729 -2.012114
3.332948 3.983102
-1.616805 3.573188
2.280615 -2.559444
-2.651229 -3.103198
2.321395 3.154987
-1.685703 2.939697
3.031012 -3.620252
-4.599622 -2.185829
4.196223 1.126677
-2.133863 3.093686
4.668892 -2.562705
-2.793241 -2.149706
2.884105 3.043438
-2.967647 2.848696
4.479332 -1.764772
-4.905566 -2.911070
3.3 运行结果
四、K-Means优点与缺点
优点: 易于实现
缺点:
- K值需要预先给定,属于预先知识,很多情况下K值的估计是非常困难的,对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确的K值的场景,可以进行迭代运算,然后找出Cost Function最小时所对应的K值,这个值往往能较好的描述有多少个簇类。
- K-Means算法对初始选取的聚类中心点是敏感的,不同的随机种子点得到的聚类结果完全不同。
- K-Means算法并不是能处理所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇。
- 对离群点的数据进行聚类时,K均值也有问题,这种情况下,离群点检测和删除有很大的帮助。
拙劣的初始质心
当初始质心是随机的进行初始化的时候,K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕,可能只能得到局部的最优解,而无法得到全局的最优解。如下图所示:
可以看到程序迭代了4次终止,其得到了局部的最优解,显然我们可以看到其不是全局最优的,我们仍然可以找到一个更小的SSE的聚类。
随机初始化的局限
你可能会想到:多次运行,每次使用一组不同的随机初始质心,然后选择一个具有最小的SSE的簇集。该策略非常的简单,但是效果可能不是很好,这取决于数据集合寻找的簇的个数。
K-Means优化算法
为了克服K-Means算法收敛于局部最小值的问题,提出了一种二分K-均值(bisecting K-means)算法。