当前位置：首页 > article >正文

【机器学习】K-means 聚类

article 2024/11/5 2:06:21

K-means 是一种经典的非监督学习聚类算法，常用于数据划分和模式识别。其核心思想是将数据集划分为 ( k ) 个互斥的簇，每个簇由一个质心（簇中心）来代表。

本文将系统性讲解 K-means 的原理，从算法步骤推导到实现细节，逐步展示如何用 Numpy 实现 K-means 算法，最后使用 Scikit-Learn 库验证结果，并可视化最终的聚类效果。

K-means 的基本原理

K-means 主要包含以下步骤：

初始化：随机选择 ( k ) 个初始中心点。
分配簇：将数据集中每个点分配到距离最近的中心点所在的簇。
更新中心点：对每个簇计算新的质心，并将质心更新为簇中的点的均值。
重复：重复“分配簇”和“更新中心点”这两个步骤，直到质心不再变化或达到最大迭代次数。

K-means 算法旨在最小化每个数据点到其所属簇质心的欧氏距离平方和，即簇内误差平方和（Within-Cluster Sum of Squares, WCSS）：

$\text{WCSS} = \sum_{i=1}^{k} \sum_{x \in C_i} ||x - \mu_i||^2$
其中 ( C_i ) 表示第 ( i ) 个簇，( \mu_i ) 表示第 ( i ) 个簇的质心。

用 Numpy 实现 K-means 算法

数据生成与初始化

首先，我们生成一组模拟数据以便后续聚类实验使用。这里我们生成三个簇，每个簇中心在不同的位置。

import numpy as np
import matplotlib.pyplot as plt

# 生成模拟数据
np.random.seed(0)
cluster_1 = np.random.randn(100, 2) + np.array([5, 5])
cluster_2 = np.random.randn(100, 2) + np.array([-5, -5])
cluster_3 = np.random.randn(100, 2) + np.array([5, -5])

# 合并数据
X = np.vstack((cluster_1, cluster_2, cluster_3))

# 绘制数据
plt.scatter(X[:, 0], X[:, 1], s=30)
plt.title("原始数据")
plt.show()

K-means 算法实现

接下来，我们实现 K-means 算法的每个步骤。

初始化质心

随机选择 ( k ) 个点作为初始质心。

def initialize_centroids(X, k):
    np.random.seed(0)
    random_indices = np.random.permutation(X.shape[0])
    centroids = X[random_indices[:k]]
    return centroids

计算距离并分配簇

计算每个点到质心的欧氏距离，并将其分配到最近的簇。

def compute_distances(X, centroids):
    distances = np.zeros((X.shape[0], len(centroids)))
    for i, centroid in enumerate(centroids):
        distances[:, i] = np.linalg.norm(X - centroid, axis=1)
    return distances

def assign_clusters(X, centroids):
    distances = compute_distances(X, centroids)
    return np.argmin(distances, axis=1)

更新质心

根据每个簇的所有点重新计算质心。

def update_centroids(X, labels, k):
    centroids = np.zeros((k, X.shape[1]))
    for i in range(k):
        cluster_points = X[labels == i]
        if len(cluster_points) > 0:
            centroids[i] = cluster_points.mean(axis=0)
    return centroids

K-means 主循环

整合上述函数，将它们放入一个循环中实现完整的 K-means 算法。

def kmeans(X, k, max_iters=100, tolerance=1e-4):
    centroids = initialize_centroids(X, k)
    for i in range(max_iters):
        old_centroids = centroids
        labels = assign_clusters(X, centroids)
        centroids = update_centroids(X, labels, k)
        
        # 检查质心是否收敛
        if np.all(np.abs(centroids - old_centroids) < tolerance):
            break
    return centroids, labels

运行 K-means 算法

运行 K-means 算法并可视化聚类结果。

# 设置簇数
k = 3
centroids, labels = kmeans(X, k)

# 可视化聚类结果
plt.scatter(X[:, 0], X[:, 1], c=labels, s=30, cmap="viridis")
plt.scatter(centroids[:, 0], centroids[:, 1], s=200, c="red", marker="X")
plt.title("K-means 聚类结果")
plt.show()

可视化 WCSS（簇内误差平方和）

为了确定最佳的簇数 ( k )，可以使用“肘部法则”观察 WCSS 随着 ( k ) 增加的变化。我们将计算不同簇数下的 WCSS 值，并绘制其趋势图。

def calculate_wcss(X, centroids, labels):
    wcss = 0
    for i in range(len(centroids)):
        cluster_points = X[labels == i]
        wcss += np.sum((cluster_points - centroids[i]) ** 2)
    return wcss

# 计算不同 k 值下的 WCSS
wcss_values = []
for k in range(1, 10):
    centroids, labels = kmeans(X, k)
    wcss = calculate_wcss(X, centroids, labels)
    wcss_values.append(wcss)

# 绘制 WCSS 趋势图
plt.plot(range(1, 10), wcss_values, marker="o")
plt.xlabel("簇数 k")
plt.ylabel("簇内误差平方和 (WCSS)")
plt.title("肘部法则选择最优簇数")
plt.show()

通常，随着 ( k ) 增加，WCSS 会减小，但会在某个 ( k ) 值后趋于平稳。肘部法则通过选择 WCSS 曲线弯曲点的 ( k ) 值，帮助确定最合适的聚类数。

使用 Scikit-Learn 实现 K-means 聚类

Scikit-Learn 提供了 KMeans 类，可以快速应用 K-means 算法。下面我们将使用它来验证我们之前手动实现的聚类效果。

from sklearn.cluster import KMeans

# 使用 Scikit-Learn 的 KMeans
kmeans_sklearn = KMeans(n_clusters=3, random_state=0)
kmeans_sklearn.fit(X)
labels_sklearn = kmeans_sklearn.labels_
centroids_sklearn = kmeans_sklearn.cluster_centers_

# 可视化 Scikit-Learn 的 K-means 聚类结果
plt.scatter(X[:, 0], X[:, 1], c=labels_sklearn, s=30, cmap="viridis")
plt.scatter(centroids_sklearn[:, 0], centroids_sklearn[:, 1], s=200, c="red", marker="X")
plt.title("Scikit-Learn K-means 聚类结果")
plt.show()

总结

本文详细介绍了 K-means 聚类算法的工作原理，手动实现了整个算法流程，包括初始化质心、分配簇、更新质心以及主循环，并可视化了聚类结果。为了选择最佳的簇数，我们还使用了肘部法则，绘制了不同簇数下的 WCSS。最后，我们通过 Scikit-Learn 库验证了手动实现的 K-means 效果并展示了聚类的可视化结果。

随机初始化质心可能导致 K-means 得到局部最优解，可以通过多次运行算法选取最佳模型。

查看全文

http://www.kler.cn/a/376673.html