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

解密K-means：简单易懂的算法指南

article 2025/2/5 14:42:25

一、什么是聚类分析？

想象你在超市整理货架：把饮料放在一起，零食归为一类，日用品另放一个区域——这个过程本质上就是聚类。在机器学习中，聚类算法就是帮计算机自动完成这种分类任务的工具。

关键特点：

无监督学习：不需要预先标记的数据
发现数据内在结构
适用于客户分群、图像分割、文档归类等场景

二、K-means算法核心原理

算法三步曲

选队长：随机选择K个初始中心点（质心）
站队伍：每个数据点加入最近的质心队伍
换队长：根据队伍成员重新计算中心点
重复2-3步直到队伍稳定

数学本质

最小化平方误差：
$\sum_{i=1}^k \sum_{x \in C_i} ||x - \mu_i||^2$
其中 $\mu_i$ 是第i个聚类的中心

三、关键实现细节

1. 距离计算

使用欧氏距离（直线距离）：
$\sqrt{\sum_{i=1}^n (p_i - q_i)^2}$

实际代码中使用向量化计算：

# 计算所有点到所有质心的距离
distances = np.linalg.norm(points[:, np.newaxis] - centroids, axis=2)

2. 空聚类处理

当某个聚类没有数据点时：

常见策略：随机选择一个数据点作为新质心
改进方案：使用K-means++初始化

3. 收敛判断

当质心移动距离小于阈值时停止迭代：

if np.allclose(centroids, new_centroids, atol=1e-4):
    break

Code

import numpy as np

def euclidean_distance(a, b):
    return np.sqrt(((a - b) ** 2).sum(axis=1))

def k_means_clustering(points, k, initial_centroids, max_iterations):
    points = np.array(points)
    centroids = np.array(initial_centroids)
    
    for iteration in range(max_iterations):
        # Assign points to the nearest centroid
        distances = np.array([euclidean_distance(points, centroid) for centroid in centroids])
        assignments = np.argmin(distances, axis=0)

        new_centroids = np.array([points[assignments == i].mean(axis=0) if len(points[assignments == i]) > 0 else centroids[i] for i in range(k)])
        
        # Check for convergence
        if np.allclose(centroids, new_centroids, atol=1e-4):
		    break
        centroids = new_centroids
        centroids = np.round(centroids,4)
    return [tuple(centroid) for centroid in centroids]