首页 > 编程笔记 > Python笔记 阅读：39

k-means聚类算法详解（Python实现）

k-means（k-均值）聚类根据数据点与聚类中心的距离将数据点分配给 k 个簇中的一个。它首先在空间中随机分配聚类质心。然后，根据每个数据点与聚类质心的距离，将其分配到一个簇中。将每个点分配给一个簇后，再分配新的聚类质心。这个过程迭代运行，直到找到适当的聚类。假设簇的数量是已知的，并将数据点放入到一个簇中。

k-means聚类的基本原理

假定给定数据样本 X，包含了 n 个对象 X={X1, X2, …, Xn}，其中每个对象都具有 m 个维度的属性。k-means 算法的目标是将 n 个对象依据对象间的相似性聚集到指定的 k 个类簇中，每个对象属于且仅属于一个其到类簇中心距离最小的类簇中。

对于 k-means，首先需要初始化 k 个聚类中心 {C1, C2, …, Ck}，1<k≤n，然后通过计算每一个对象到第一个聚类中心的欧几里得距离：


式中：
依次比较每一个对象到每一个聚类中心的距离，将对象分配到距离最近的聚类中心的类簇中，得到 k 个类簇 {S1, S2,…, Sk}。

k-means 算法用中心定义了类簇的原理，类簇中心就是类簇内所有对象在各个维度的均值，其公式为：


式中，Ct 表示第 t 个聚类中心，1≤t≤K，|St| 表示第 t 个类簇中对象的个数，Xi 表示第 t 个类簇中第 i 个对象，1≤i≤|St|。

k-means算法流程

k-means 聚类适合分离的数据。当数据点重叠时，此聚类并不适用。与其他聚类技术相比，k-means 聚类速度更快，它提供了数据点之间的强大耦合。

k-means 聚类在许多应用中都很有用：
将聚类质心移到每个簇的数据中心，因此，可以使用训练数据集来生成聚类。当从测试数据中获取实例时，可以将它们分配到相应的簇中。

在某些情况下，K 没有明确定义，所以必须考虑 K 的最佳数量（后续讨论选取 K 值的解决方法）。当解决监督学习问题时，要考虑成本函数，并且会尽量最小化任务的成本。

k-means 是一个反复选代的过程，其算法分为以下 4 个步骤：

k-means随机分配聚类质心

下面通过一个例子来实现利用 Python 为随机数据分配聚类质心。

【实例】利用 k-means 聚类法为随机数据分配质心。首先我们随机生成 200 个点，就取（0，2000）范围内的，并确定质心个数，这里就取 3 个质心，也是随机生成（可以根据需求改变）如下： 
import random
import matplotlib.pyplot as plt

random_x = [random.randint(0,2000) for _ in range(200)]
random_y = [random.randint(0,2000) for _ in range(200)]
random_points = [(x, y) for x, y in zip(random_x, random_y)]

def generate_random_point(min_,max_):
    return random.randint(min_,max_), random.randint(min_,max_)

k1,k2,k3 = generate_random_point(-100,100), generate_random_point(-100,100), generate_random_point(-100,100)

plt.scatter(k1[0],k1[1],color = 'red',s=100)
plt.scatter(k2[0],k2[1],color = 'blue',s=100)
plt.scatter(k3[0],k3[1],color = 'green',s=100)
plt.scatter(random_x,random_y)
执行效果如下图所示：


图 3 确定质心个数

接着导入 numpy 来计算各个点与质心的距离，并根据每个点与质心的距离分类，与第一个点近则分配在列表的第一个位置，离第二个近则分配到第二个位置，以此类推，如下代码所示： 
import numpy as np

def dis(p1, p2):           # 这里的 p1, p2 是一个列表 [number1, number2] 的距离计算
    return np.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

random_points = [(x, y) for x, y in zip(random_x, random_y)]  # 将 100 个随机点塞进列表
groups = [[], [], []]      # 100 个点分成三类
for p in random_points:
    distances = [dis(p, k) for k in [k1, k2, k3]]  # k1, k2, k3 是随机生成的三个点
    min_index = np.argmin(distances)  # 取距离最近质心的下标
    groups[min_index].append(p)
groups
运行程序，输出如下：

[[(285,1802),
  (1320,1267),
  (828,1232),
  (884,1937),
  (247,1345),
  (688,206),
  (1998,430),
  (1146,327),
  (1755,571),
  (1944,1503),
  (1149,511),
  (361,1929),
  (259,1),
  …
  (862,1866),
  (1011,1427),
  (15,230)],
[],
[]]

可以看到，这 200 个点根据与三个质心的距离远近不同，已经被分成了三类，此时 groups 里面有三个列表，这三个列表里分别是分配给三个质心的点的位置，接着我们将其可视化，并且加入循环来迭代找到相对最优的质点，代码如下： 
previous_kernels = [k1,k2,k3]
circle_number = 10
for n in range(circle_number):
    plt.close()
    kernel_colors = ['red','yellow','green']
    new_kernels = []
    plt.scatter(previous_kernels[0][0],previous_kernels[0][1],color = kernel_colors[0],s=200)
    plt.scatter(previous_kernels[1][0],previous_kernels[1][1],color = kernel_colors[1],s=200)
    plt.scatter(previous_kernels[2][0],previous_kernels[2][1],color = kernel_colors[2],s=200)

    groups = [[],[],[]]
    for p in random_points:
        distances = [dis(p,k) for k in previous_kernels]
        min_index = np.argmin(distances)
        groups[min_index].append(p)
        print('第{}次'.format(n+1))
        for i,g in enumerate(groups):
            g_x = [_x for _x,_y in g]
            g_y = [_y for _x,_y in g]
            n_k_x,n_k_y = np.mean(g_x),np.mean(g_y)
            new_kernels.append([n_k_x,n_k_y])
            print('三个点之前的质心和现在的质心距离：{}'.format(dis(previous_kernels[i], [n_k_x,n_k_y])))
            plt.scatter(g_x,g_y,color = kernel_colors[i])
            plt.scatter(n_k_x,n_k_y,color = kernel_colors[i],alpha = 0.5,s=200)
    previous_kernels = new_kernels
运行程序，输出如下：

第1次
三个点之前的质心和现在的质心距离:344.046783724601
三个点之前的质心和现在的质心距离:178.67567512699137
三个点之前的质心和现在的质心距离:85.51258602308063
第2次
三个点之前的质心和现在的质心距离:223.75162213961798
三个点之前的质心和现在的质心距离:41.23571511332308
三个点之前的质心和现在的质心距离:132.0752155320645
...
第9次
三个点之前的质心和现在的质心距离：0.0
三个点之前的质心和现在的质心距离：0.0
三个点之前的质心和现在的质心距离：0.0
第10次
三个点之前的质心和现在的质心距离：0.0
三个点之前的质心和现在的质心距离：0.0
三个点之前的质心和现在的质心距离：0.0

效果如下图所示：


图 4 聚类效果

这里设置了总共迭代 10 次，可以看到在迭代到第 8 次的时候就找到了最优的质点，如图 4 所示。

k-means算法的优缺点

在 Python 中，k-means 算法的优点主要有：
k-means 算法的应用局限性表现在：

相关文章