PythonAI算法
K-means 聚类算法原理与实现详解
本文详细介绍了 K-means 聚类算法的原理、工作流程及数学基础。K-means 通过将数据划分为 K 个簇，最小化簇内距离平方和来实现聚类。文章涵盖了算法步骤、时间复杂度、优缺点分析以及 K 值选择方法（如肘部法）。此外，提供了基于 scikit-learn 和手动实现的 Python 代码示例，并介绍了 K-means++ 初始化方法以改善收敛性和稳定性。该算法适用于大规模数据，但对初始值和异常值敏感。
本文详细介绍了 K-means 聚类算法的原理、工作流程及数学基础。K-means 通过将数据划分为 K 个簇，最小化簇内距离平方和来实现聚类。文章涵盖了算法步骤、时间复杂度、优缺点分析以及 K 值选择方法（如肘部法）。此外，提供了基于 scikit-learn 和手动实现的 Python 代码示例，并介绍了 K-means++ 初始化方法以改善收敛性和稳定性。该算法适用于大规模数据，但对初始值和异常值敏感。
K-means 聚类是一种常用的基于距离的聚类算法，旨在将数据集划分为 K 个簇。算法的目标是最小化簇内的点到簇中心的距离总和。下面，我们将从 K-means 的底层原理、算法步骤、数学基础、距离度量方法、参数选择、优缺点和源代码实现等角度进行详细解析。
K-means 的目标是将数据集划分为 K 个簇（clusters），使得每个数据点属于距离最近的簇中心。通过反复调整簇中心的位置，K-means 不断优化簇内的紧密度，从而获得尽量紧凑、彼此分离的簇。
如下图：
以簇中心为中心，划分范围
K-means 使用'最近距离'来分组：
K-means 聚类的流程分为两个主要步骤：分配（Assignment）和更新（Update）。以下是详细步骤：
初始化簇中心： 随机选择 K 个数据点作为初始簇中心（centroids）。
选择 K 值： 设定簇的数量 K。
假设我们有以下二维数据点，表示顾客的'消费金额'和'访问次数'：
| 数据点编号 | 消费金额（x） | 访问次数（y） |
|---|---|---|
| 点 1 | 1 | 2 |
| 点 2 | 2 | 1 |
| 点 3 | 4 | 5 |
| 点 4 | 5 | 6 |
| 点 5 | 8 | 8 |
目标是将这些点分为 K=2 个簇。
计算每个点到两个质心的欧几里得距离：
$d = \sqrt{ (x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$
| 数据点编号 | 到 C1 的距离 | 到 C2 的距离 | 最近质心 | 分配簇 |
|---|---|---|---|---|
| 点 1 | 0 | 8.49 | C1 | 簇 1 |
| 点 2 | 1.41 | 8.06 | C1 | 簇 1 |
| 点 3 | 4.24 | 5.0 | C1 | 簇 1 |
| 点 4 | 5.0 | 4.24 | C2 | 簇 2 |
| 点 5 | 8.49 | 0 | C2 | 簇 2 |
分配结果：
对于每个簇，计算新质心的位置：
更新质心为：
再次计算每个点到新质心的距离，重复'分配簇'和'重新计算质心'步骤，直到质心不再变化。
最终结果：
质心稳定在：
K-means 的目标是最小化簇内平方误差和（Within-Cluster Sum of Squares，WCSS），即每个点到其所属簇中心的距离的平方和，公式如下：
$\sum_{i=1}^{K} \sum_{x \in C_i} | x - \mu_i |^2$
其中：
K-means 通常采用欧氏距离来衡量点到簇中心的距离，其公式为：
$d(x,\mu) = \sqrt{\sum_{j=1}^{n}(x_j - \mu_j)^2}$
其中 n 是数据的维度。
KMeans(X, K):
1. 随机选择 K 个点作为初始簇中心
2. 重复以下步骤，直到簇中心不再发生变化：
a. 分配每个点到最近的簇中心
b. 重新计算每个簇的中心，作为簇内所有点的均值
3. 返回最终的簇分配和簇中心
对于每个数据点，找到距离最近的簇中心 $\mu_j$：
$c_i = \arg\min_j | x_i - \mu_j |$!
更新每个簇的中心 $\mu_j$ 为簇内所有点的均值：
$\mu_j = \frac{1}{|C_j|} \sum_{x \in C_j} x$
总复杂度：若迭代次数为 $T$，则总体复杂度为 $O(nKT)$。
更新步骤：重新计算每个簇的中心，需要遍历所有点，复杂度也是 $O(nK)$。
每次分配步骤：需要计算每个点到 $K$ 个簇中心的距离，复杂度为 $O(nK)$。
确定最佳的簇数 K 是 K-means 聚类中的一个难点。常用的选择方法有：
肘部法（Elbow Method）： 绘制不同 K 值下的 WCSS 图，寻找'肘部'点作为最佳 K 值。
下图可以发现当 k=4 或者 5 时是最佳的情况 SSE 图像下降幅度最大放缓的情况在 4-5 之间。
我们可以使用 scikit-learn 中的 KMeans，以及手动实现以便更深入理解。
from sklearn.cluster import KMeans
import numpy as np
# 生成示例数据
X = np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])
# 初始化并训练 KMeans 模型
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
# 获取簇标签和簇中心
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
print("Cluster labels:", labels)
print("Centroids:", centroids)
输出：
Cluster labels: [0 0 0 1 1 1]
Centroids: [[ 2. 2.33333333]
[13.66666667 31.66666667]]
以下是 K-means 的核心逻辑手动实现：
import numpy as np
def initialize_centroids(X, k):
indices = np.random.choice(len(X), k, replace=False)
return X[indices]
def closest_centroid(X, centroids):
distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
return np.argmin(distances, axis=1)
def update_centroids(X, labels, k):
return np.array([X[labels == i].mean(axis=0) for i in range(k)])
def kmeans(X, k, max_iters=100, tol=1e-4):
centroids = initialize_centroids(X, k)
for i in range(max_iters):
labels = closest_centroid(X, centroids)
new_centroids = update_centroids(X, labels, k)
if np.all(np.abs(new_centroids - centroids) < tol):
break
centroids = new_centroids
return labels, centroids
# 示例数据
X = np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])
# 运行 K-means
labels, centroids = kmeans(X, k=)
(, labels)
(, centroids)
K-means 的收敛性受到初始簇中心选择的影响。K-means++ 是一种改进的初始化方法，可以帮助选择更合理的初始中心，优先选择'距离最远'的点作为初始质心，减少陷入局部最优的风险。
K-means 是一种简单、快速的聚类算法，广泛应用于数据聚类任务。通过反复优化簇中心位置，K-means 不断收敛并找到数据的聚类结构。然而，它对初始条件敏感，对簇形状有限制，适合于球形且均匀分布的簇。在实际应用中，可通过结合 K-means++、肘部法和轮廓系数等手段改进其效果。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online