进击数据挖掘十大算法(一):K-Means

发表于 更新于 分类于 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟

聚类与分类的区别

分类：类别是已知的，通过对已知分类的数据进行训练和学习，找到这些不同类的特征，再对未分类的数据进行分类。属于监督学习。

聚类：事先不知道数据会分为几类，通过聚类分析将数据聚合成几个群体。聚类不需要对数据进行训练和学习。属于无监督学习。

关于监督学习和无监督学习，这里给一个简单的介绍：是否有监督，就看输入数据是否有标签，输入数据有标签，则为有监督学习，否则为无监督学习。

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)算法。

待补充…