进击数据挖掘十大算法(一):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
2
3
4
5
选择K个点作为初始质心
repeat
将每个点指派到最近的质心,形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数

2.2 具体解释:

K-Means聚类算法的大致意思就是“物以类聚,人以群分”:

  1. 首先输入 k 的值,即我们指定希望通过聚类得到 k 个分组;
  2. 从数据集中随机选取 k 个数据点作为初始大佬(质心);
  3. 对集合中每一个小弟,计算与每一个大佬的距离,离哪个大佬距离近,就跟定哪个大佬。
  4. 这时每一个大佬手下都聚集了一票小弟,这时候召开选举大会,每一群选出新的大佬(即通过算法选出新的质心)。
  5. 如果新大佬和旧大佬之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大,趋于稳定,或者说收敛),可以认为我们进行的聚类已经达到期望的结果,算法终止。
  6. 如果新大佬和旧大佬距离变化很大,需要迭代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
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
80
"""
author: QzmVc1
Time: 2019/1/23
"""
import numpy as np
import matplotlib.pyplot as plt

# 计算欧几里得距离
def distEclud(x,y):
return np.sqrt(np.sum((x-y)**2))

# 随机生成k个初始聚类中心
def randCent(dataSet,k):
lst = [] # 防止生成重复
i = 0
m,n = dataSet.shape
centroids = np.zeros((k,n)) # centroids 是保存k个质心的ndarray
while i < k:
index = np.random.randint(0,m)
if index not in lst:
lst.append(index)
centroids[i,:] = dataSet[index,:]
i += 1
return centroids

# K-Means算法具体实现
def KMeans(dataSet,k):
m = dataSet.shape[0]
# 生成k个初始聚类中心
centroids = randCent(dataSet,k)
# 第一列存样本属于哪一簇
# 第二列存样本的到簇的中心点的误差
clusterAssment = np.zeros((m,2)) # clusterAssment数组将各点和质心关联起来
clusterChange = True # 循环条件
while clusterChange:
clusterChange = False
for i in range(m): # 遍历每一个点
minIndex = -1
minDist = 10000
for j in range(k): # 计算该点归属于哪一个质心
dist = distEclud(centroids[j, :], dataSet[i, :])
if dist < minDist:
minIndex = j
minDist = dist
# 如果存在一个点没有收敛,则继续循环
if clusterAssment[i,0] != minIndex:
clusterChange = True
clusterAssment[i,:] = minIndex,minDist**2

# 计算新的k个质心
for j in range(k):
selectrow = dataSet[np.nonzero(clusterAssment[:,0]==j)[0]] # 获取簇类所有的点
centroids[j,:] = np.mean(selectrow,axis=0) # 对矩阵的行求均值

return centroids,clusterAssment

# 画聚类图
def showCluster(dataSet,k,centroids,clusterAssment):
m,n = dataSet.shape
marker = ['or', 'ob', 'og', 'ok', 'Dr', 'Db', 'Dg', 'Dk', '<r', 'pr']
if n != 2:
print("数据不是二维的!")
elif k > len(marker):
print("聚类结果超出限制!")
else:
# 绘制所有样本
for i in range(m):
plt.plot(dataSet[i,0],dataSet[i,1],marker[int(clusterAssment[i,0])])
# 绘制质心
for i in range(k):
plt.plot(centroids[i,0],centroids[i,1],marker[i+k])
plt.show()


# 加载数据集
dataSet = np.loadtxt('K-Means_Data.txt')
# 聚类个数
k = 4
centroids,clusterAssment = KMeans(dataSet,k)
showCluster(dataSet,k,centroids,clusterAssment)

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
80
1.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优点与缺点

优点: 易于实现

缺点:

  1. K值需要预先给定,属于预先知识,很多情况下K值的估计是非常困难的,对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确的K值的场景,可以进行迭代运算,然后找出Cost Function最小时所对应的K值,这个值往往能较好的描述有多少个簇类。
  2. K-Means算法对初始选取的聚类中心点是敏感的,不同的随机种子点得到的聚类结果完全不同。
  3. K-Means算法并不是能处理所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇。
  4. 对离群点的数据进行聚类时,K均值也有问题,这种情况下,离群点检测和删除有很大的帮助。

拙劣的初始质心

当初始质心是随机的进行初始化的时候,K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕,可能只能得到局部的最优解,而无法得到全局的最优解。如下图所示:

可以看到程序迭代了4次终止,其得到了局部的最优解,显然我们可以看到其不是全局最优的,我们仍然可以找到一个更小的SSE的聚类。

随机初始化的局限

你可能会想到:多次运行,每次使用一组不同的随机初始质心,然后选择一个具有最小的SSE的簇集。该策略非常的简单,但是效果可能不是很好,这取决于数据集合寻找的簇的个数。

K-Means优化算法

为了克服K-Means算法收敛于局部最小值的问题,提出了一种二分K-均值(bisecting K-means)算法。

待补充…