K均值算法

K均值算法（K-means clustering）是一种常用的聚类分析方法，属于无监督学习算法。该算法试图将数据点分成K个不同的簇，使得每个数据点都属于距离最近的质心所对应的簇。

算法原理

K均值算法的基本流程如下：

随机选择K个点作为初始质心（centroids）
将每个数据点分配到距离最近的质心所代表的簇
重新计算每个簇的质心（即簇中所有点的均值）
重复步骤2和3，直到质心基本不再变化或达到最大迭代次数

数学表示

对于给定的数据集 $\{x_1, x_2, ..., x_n\}$ ，K均值算法的目标是将这些数据点分成K个簇 $S = \{S_1, S_2, ..., S_K\}$ ，以最小化所有点到其对应簇质心的距离平方和：

J = \sum_{i=1}^{K}\sum_{x \in S_i}||x - \mu_i||^2

其中， $\mu_i$ 是簇 $S_i$ 的质心。

代码实现

使用scikit-learn库

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

# 生成示例数据
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 创建K均值模型
kmeans = KMeans(n_clusters=4, random_state=0)

# 训练模型
kmeans.fit(X)

# 获取聚类标签和质心
labels = kmeans.labels_
centers = kmeans.cluster_centers_

# 可视化结果
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.5)
plt.title('K均值聚类结果')
plt.savefig('kmeans_result.png')
plt.show()

print(f"聚类中心点坐标:\n{centers}")

从零实现K均值算法

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

class KMeans:
    def __init__(self, k=3, max_iters=100, tol=1e-4):
        self.k = k
        self.max_iters = max_iters
        self.tol = tol
        self.centroids = None
      
    def fit(self, X):
        # 随机初始化质心
        idx = np.random.choice(len(X), self.k, replace=False)
        self.centroids = X[idx]
      
        # 存储历史质心位置用于可视化
        self.history = [self.centroids.copy()]
      
        for _ in range(self.max_iters):
            # 分配样本到最近的质心
            labels = self._assign_clusters(X)
          
            # 更新质心
            old_centroids = self.centroids.copy()
            for i in range(self.k):
                if np.sum(labels == i) > 0:
                    self.centroids[i] = np.mean(X[labels == i], axis=0)
          
            # 存储新的质心位置
            self.history.append(self.centroids.copy())
          
            # 检查是否收敛
            if np.sum((self.centroids - old_centroids) ** 2) < self.tol:
                break
              
        return self
  
    def _assign_clusters(self, X):
        # 计算每个样本到每个质心的距离
        distances = np.sqrt(((X[:, np.newaxis, :] - self.centroids[np.newaxis, :, :]) ** 2).sum(axis=2))
        # 返回距离最小的质心索引
        return np.argmin(distances, axis=1)
  
    def predict(self, X):
        return self._assign_clusters(X)

算法可视化

下面是K均值算法聚类过程的可视化示例：

上图显示了K均值算法迭代过程中质心（红色X）和数据点分配的变化。每次迭代，数据点被分配到最近的质心，然后质心位置被重新计算。

如何选择最优的K值

选择合适的K值是K均值算法的关键问题。常用的方法有：

肘部法则（Elbow Method）：计算不同K值下的簇内平方和（WSS，Within-Cluster Sum of Square），并绘制WSS-K曲线。当K增加时，WSS通常会下降，在最佳K值处，WSS下降速度会明显变缓，形成一个"肘部"。

wcss = []
for k in range(1, 11):
    kmeans = KMeans(n_clusters=k, random_state=0)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)  # inertia_是簇内平方和

plt.figure(figsize=(10, 6))
plt.plot(range(1, 11), wcss, marker='o')
plt.title('肘部法则')
plt.xlabel('簇数量(k)')
plt.ylabel('WCSS')
plt.savefig('elbow_method.png')
plt.show()

轮廓系数（Silhouette Coefficient）：衡量样本与其自身所在簇的相似度与其他簇的相似度之间的差异。轮廓系数越接近1，聚类效果越好。

from sklearn.metrics import silhouette_score

silhouette_scores = []
for k in range(2, 11):  # 注意：轮廓系数需要至少2个簇
    kmeans = KMeans(n_clusters=k, random_state=0)
    labels = kmeans.fit_predict(X)
    silhouette_scores.append(silhouette_score(X, labels))

plt.figure(figsize=(10, 6))
plt.plot(range(2, 11), silhouette_scores, marker='o')
plt.title('轮廓系数法')
plt.xlabel('簇数量(k)')
plt.ylabel('轮廓系数')
plt.savefig('silhouette_method.png')
plt.show()

K均值算法的优缺点

优点

简单易于理解和实现
对大数据集计算效率较高
当簇近似球形分布时效果好

缺点

需要预先指定簇的数量K
对初始质心的选择敏感，可能陷入局部最优
对离群点敏感
只能发现凸形状的簇，对非凸形状的簇效果较差
每个点必须被分配到一个簇中

应用场景

K均值算法广泛应用于：

客户细分
图像压缩
文档聚类
异常检测
推荐系统

小结

K均值算法是一种简单有效的聚类算法，尤其适用于大规模数据集。尽管它有一些局限性，如需要预先指定K值和对初始质心敏感，但在实践中仍被广泛使用，特别是作为其他更复杂聚类方法的基准或初步分析工具。

算法原理​

数学表示​

代码实现​

使用scikit-learn库​

从零实现K均值算法​

算法可视化​

如何选择最优的K值​

K均值算法的优缺点​

优点​

缺点​

应用场景​

小结​