K-means 学习笔记

前言

K-means 算法是最为经典的基于划分的聚簇方法，是经典数据挖掘算法之一。简单的说就是在没有任何监督信号的情况下将数据分为 K 份的一种方法, 也就是分门别类。

K-means 算法

算法原理

基本思想:

给定 K 值和 K 个初始类中心点，把每个点分到离其最近的类中心点所代表的类中，所有点分配完毕之后，根据一个类内的所有点重新计算该类的中心点（平均值），然后再迭代的进行分配点和更新类中心点的步骤，直至类中心点的变化很小，或者达到指定的迭代次数。

对一个样本集 D=x1,x2,⋯ ,xnD={x_1,x_2,\cdots,x_n}, 这里每个 x 都有 m 个维度的属性, 我们想要将其划分为 k 个聚类

首先，我们从样本集 D 中随机获取 k 个样本作为初始类中心点 c1,c2,⋯ ,ck{c_1,c_2,\cdots,c_k}

然后计算每一个对象到每一个聚类中心的欧式距离:

dis(xi,cj)=∑t=1m(xi,t−cj,t)2dis(x_i,c_j) =\sqrt{\sum_{t=1}^m(x_{i,t}-c_{j,t})^2}

其中，m 为样本点的纬度属性

依次比较每一个对象到每一个聚类中心的距离，将对象分配到距离最近的聚类中心的类簇中，得到 k 个类 S1,S2,⋯ ,SK{S_1,S_2,\cdots,S_K}

类中心就是类内所有对象在各个维度的均值，其计算公式如下

ck=1∣Sk∣∑xi∈Skxic_{k} = \frac{1}{|S_k|} \sum_{x_i \in S_k}x_i

其中, ckc_k 为第 k 个聚类的中心，∣Sk∣|S_k| 为第 k 个聚类中元素的个数。

总的来说，K-means 算法的基本思想还是容易理解的，主要流程可以分为如下几步：

  1. 选择聚类的个数 K
  2. 任意产生 k 个聚类, 然后确定聚类中心（或者直接生成 K 个中心）
  3. 把每个数据点分配到离它最近的中心点
  4. 再迭代计算新聚类的新中心
  5. 重复以上步骤直到满足收敛要求

效果展示如下：

算法实现

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import numpy as np
import matplotlib.pyplot as plt


# 加载数据
def loadDataSet(file):
    dataSet = np.loadtxt(file, delimiter='\t')
    return dataSet


# 计算欧式距离
def euclDistance(x, y):
    return np.sqrt(np.sum((x - y) ** 2))  # 计算欧氏距离


# 初始化 k 个聚类中心
def getCenter(dataSet, k):
    # 行，列大小
    m, n = dataSet.shape
    # 初始化 k 个聚类中心
    center = np.zeros((k, n))
    for i in range(k):
        # 产生 k 个 [0, m) 的数
        index = int(np.random.uniform(0, m))
        center[i, :] = dataSet[index, :]
    return center


# k均值聚类
def KMeans(dataSet, k):
    m = np.shape(dataSet)[0]  # 行的数目
    # 第一列存样本属于哪一类，初始为 0
    # 第二列存样本的到类的中心点的误差
    clusterAssment = np.mat(np.zeros((m, 2)))  # 创建 m 行 2 列的矩阵
    clusterChange = True  # 记录样本的点类是否发生变化

    # 第1步 初始化center
    center = getCenter(dataSet, k)
    # 如果上一次迭代过程中仍有样本点的类别发生变化，则继续计算
    while clusterChange:
        clusterChange = False

        # 遍历所有的样本（行数）
        for i in range(m):
            minDist = np.inf
            minIndex = -1

            # 第2步 找出离样本点最近的质心
            # 遍历所有质心
            for j in range(k):
                # 计算该样本到质心的欧式距离
                distance = euclDistance(center[j, :], dataSet[i, :])
                if distance < minDist:
                    minDist = distance  # 更新最短距离
                    minIndex = j  # 更新离该样本最近的中心

            # 第 3 步：更新每一行样本所属的类
            # 如果样本类别发生变化
            if clusterAssment[i, 0] != minIndex:
                clusterChange = True
                # 更新类别以及误差
                clusterAssment[i, :] = minIndex, minDist**2

        # 第 4 步：更新质心
        # 遍历每一个类
        for j in range(k):
            # .A 将矩阵转化为数组
            # nonzero(a) 返回数组a中非零元素的索引值数组
            pointsInCluster = dataSet[np.nonzero(
                clusterAssment[:, 0].A == j)[0]]  # 获取类所有的点
            center[j, :] = np.mean(pointsInCluster, axis=0)   # 对矩阵的行求均值

    print("Congratulations,cluster complete!")
    return center, clusterAssment


def showCluster(dataSet, k, center, clusterAssment):
    m, n = dataSet.shape
    if n != 2:
        print("数据不是二维的")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("k值太大了")
        return 1

    # 绘制所有的样本
    for i in range(m):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    # 绘制质心
    for i in range(k):
        plt.plot(center[i, 0], center[i, 1], mark[i])
    plt.show()


dataSet = loadDataSet("test.txt")
k = 4
center, clusterAssment = KMeans(dataSet, k)

showCluster(dataSet, k, center, clusterAssment)

优缺点

  1. 原理比较简单，实现也是很容易，收敛速度快
  2. 算法的可解释度比较强
  3. 聚类中心的个数 K 需要事先给定，但在实际中 K 值的选定是非常困难的
  4. k-means 算法需要随机地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。

K-means++ 算法

上面我们提到 k-means 算法需要随机地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。对于这个问题，K-means++ 算法进行了优化。

算法原理

K-means++ 算法初始化聚类中心的策略也非常简单，流程如下：

  1. 从数据集中随机选择一个点作为第一个聚类中心
  2. 计算每个样本与最近一个聚类中心的距离, 距离越大表示被选取作为聚类中心的概率越大
  3. 用轮盘法选出下一个聚类中心
  4. 重复上述过程，直到选择出 k 个聚类中心
  5. 执行标准的 K-means 算法

效果展示如下：

算法实现

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
# 样本点到最近的聚类中心的距离
def getClosestDist(data, center):
    min_dist = np.inf
    m = np.shape(center)[0]  # 当前已经初始化的聚类中心的个数
    for i in range(m):
        # 计算样本点与每个聚类中心之间的距离
        d = euclDistance(center[i, :], data)
        # 选择最短距离
        if min_dist > d:
            min_dist = d
    return min_dist


# 初始化 k 个聚类中心
def getCenterPlusPlus(dataSet, k):
    m, n = dataSet.shape
    # 初始化 k 个聚类中心
    center = np.zeros((k, n))
    # 1、随机选择一个样本点为第一个聚类中心
    index = np.random.randint(0, m)
    center[0, :] = dataSet[index, :]
    # 初始化一个距离的序列
    d = [0.0 for _ in range(m)]

    for i in range(1, k):
        sum_all = 0
        for j in range(m):
            # 2、对每一个样本找到最近的聚类中心点
            d[j] = getClosestDist(dataSet[j, ], center[0:i, ])
            # 将所有的最短距离相加
            sum_all += d[j]
        # 3、用轮盘法选出下一个聚类中心
        # 取得sum_all之间的随机值
        sum_all *= np.random.random()
        for j, dis in enumerate(d):
            sum_all -= dis
            if sum_all > 0:
                continue
            # 选择新的聚类中心
            center[i, :] = dataSet[j, :]
            break
    return center

参考资料