K-Means 聚类算法实现 - Python 代码详解

本文提供完整的 Python 代码实现 K-Means 聚类算法，并解释了核心函数的功能和实现细节。代码包含随机初始化中心点、寻找最近中心点、计算损失函数等关键步骤，可供学习和参考。

import scipy.io as sio  # load mat
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
import numpy as np
from sklearn.cluster import KMeans

# 生成随机的k个中心,请使用sample(k)
def random_init(data, k):
    #data：数据集 k：聚类中心个数
    #返回 k 个聚类中心并转换成array数组
    #********** Begin **********#
    return data.sample(k).values
    #********** End **********#

# 单个找寻聚类
def find_cluster(x, centroids):
    #x:待聚类点坐标  centroids:中心坐标
    #********** Begin **********#
    distances = np.apply_along_axis(func1d=np.linalg.norm, axis=1, arr=centroids-x.reshape(1,-1))
    #********** End **********#
    return np.argmin(distances)

# 集体data聚类标签
def assign_cluster(data, centroids):
    return np.apply_along_axis(lambda x: find_cluster(x, centroids), axis=1, arr=data.values)
#  data中增加一列聚类标签C
def combineDataC(data, C):
    dataC = data.copy()
    dataC['C'] = C
    return dataC

# 新中心点，同时去掉C， 再转换成array数组
def newCentroids(data, C):
    dataC = combineDataC(data, C)
    return dataC.groupby('C', as_index=False).mean().sort_values(by='C').drop('C', axis=1).values


# 损失函数
def cost(data, centroids, C):
    #data:数据集 centroids:中心坐标 C:聚类标签
    m = data.shape[0] # 样本量
    dataCentroids = centroids[C] # 各行的中心坐标
    #********** Begin **********#
    distances = np.apply_along_axis(func1d=np.linalg.norm, axis=1, arr=data.values - dataCentroids)
    #********** End **********#
    return distances.sum()/m


# kmeans通道，运行一次
def kMeansIter(data, k, epoch=100, tol=0.0001):
    # 生成最初的中心坐标
    centroids = random_init(data, k)

    costProgress = []  # 用来存放递归聚类的每次损失
    # 分配聚类标签
    for i in range(epoch):
        C = assign_cluster(data, centroids)
        centroids = newCentroids(data, C)
        costProgress.append(cost(data, centroids, C))

        if len(costProgress) > 1:
            if np.abs(costProgress[-1] - costProgress[-2]) / costProgress[-1] < tol:
                break

    return C, centroids, costProgress[-1]

# 每个k运行n_init次，套用kmeans通道
def kMeans(data, k, epoch=100, n_init=10):
    tries = np.array([kMeansIter(data, k) for _ in range(n_init)])
    leasrCostIndex = np.argmin(tries[:, -1])
    return tries[leasrCostIndex]

# 补全代码中begin和end之间的代码
# 使得结果为0.7047863060539973
data = pd.DataFrame(np.random.rand(100, 2))
cluster_labels, centroids, cost = kMeans(data, k=3)
print(cost)

代码详解

random_init(data, k): 随机初始化 k 个聚类中心。
- 使用 data.sample(k) 从数据集中随机抽取 k 个样本作为初始中心点。
- 将选取的样本转换为 numpy.array 数组。
find_cluster(x, centroids): 找到单个数据点 x 距离最近的聚类中心。
- 使用 np.apply_along_axis 函数，对 centroids - x.reshape(1, -1) 的每一行计算欧氏距离（L2 范数）。
- 使用 np.argmin 找到距离最小的中心点索引，并返回该索引。
assign_cluster(data, centroids): 为数据集中的所有数据点分配聚类标签。
- 使用 np.apply_along_axis 函数，对 data 的每一行数据调用 find_cluster 函数，得到其所属聚类的标签。
- 返回一个包含所有数据点聚类标签的数组。
combineDataC(data, C): 将聚类标签 C 添加到数据集 data 中。
- 复制数据集 data，并添加一个新的列 'C'，存储每个样本的聚类标签。
- 返回添加了 'C' 列的数据集。
newCentroids(data, C): 计算新的聚类中心点。
- 将聚类标签 C 添加到数据集 data 中。
- 使用 groupby 函数按照 'C' 列对数据进行分组。
- 使用 mean 函数计算每个聚类组的平均值，并删除 'C' 列。
- 将计算后的平均值转换为 numpy.array 数组并返回。
cost(data, centroids, C): 计算损失函数。
- 计算所有样本点到其所属聚类中心的距离，并进行求和。
- 返回平均距离，即损失函数值。
kMeansIter(data, k, epoch=100, tol=0.0001): 运行一次 K-Means 算法迭代。
- 初始化聚类中心。
- 进行 epoch 次迭代，每次迭代执行以下步骤：
  - 为每个样本点分配聚类标签。
  - 计算新的聚类中心。
  - 计算损失函数并记录到 costProgress 中。
- 当损失函数变化小于 tol 时停止迭代。
- 返回聚类标签、聚类中心和最后一次迭代的损失函数值。
kMeans(data, k, epoch=100, n_init=10): 运行 K-Means 算法，进行 n_init 次随机初始化，并选择损失函数最小的结果。
- 循环 n_init 次，每次运行一次 kMeansIter 函数。
- 记录每次运行的结果。
- 选择损失函数最小的运行结果，并返回聚类标签、聚类中心和最后一次迭代的损失函数值。

运行结果

使用随机生成的 100 个二维数据点进行测试，运行代码后，得到损失函数值为：

0.7047863060539973

总结

本文提供了一个完整的 Python 代码实现 K-Means 聚类算法，解释了每个函数的功能和实现细节，以及如何使用该代码进行测试。希望能帮助读者更好地理解和应用 K-Means 算法。