聚类算法——K-Means算法

m0_拉丁

855人浏览 · 2025-02-16 22:36:39

m0_拉丁 · 2025-02-16 22:36:39 发布

1.生动描述（简单易懂）🎨

想象你有一堆五颜六色的糖果🍬🍭🍫，散落在桌子上。你的任务是把这些糖果分成几组，每组糖果的颜色要尽量相似。这就是K-Means算法要做的事情！

第一步：选几个“队长”👑

你先选几个“队长”（这些队长就是K-Means算法中的“中心点”）。比如你选3个队长：红队队长❤️、蓝队队长💙、绿队队长💚。

第二步：糖果找队长🤔

每个糖果会看看自己离哪个队长最近，然后加入那个队伍。比如：

红色的糖果🍬会说：“我离红队队长❤️最近，我要加入红队！”
蓝色的糖果🍭会说：“我离蓝队队长💙最近，我要加入蓝队！”
绿色的糖果🍫会说：“我离绿队队长💚最近，我要加入绿队！”

第三步：队长搬家🚶‍♂️

等所有糖果都找到队伍后，队长们会说：“我要搬到我的队伍中间去！”于是，红队队长❤️会走到所有红队糖果的中间，蓝队队长💙和绿队队长💚也会做同样的事情。

第四步：重新分组🔄

队长搬完家后，糖果们可能会发现：“咦，现在离我更近的队长变了！”于是它们会重新选择队伍。比如：

有的糖果🍬原本在红队，但现在离蓝队队长💙更近了，就会跳到蓝队。
有的糖果🍭原本在蓝队，但现在离绿队队长💚更近了，就会跳到绿队。

第五步：重复直到稳定⏳

队长们会一直搬家，糖果们也会一直重新分组，直到大家都不再变动了。这时候，糖果们就被分成了几组，每组糖果的颜色都很相似啦！🎉

2.标准原理公式📊

现在，我们用数学公式来描述K-Means算法的原理。

1. 目标

K-Means算法的目标是将数据点（比如糖果🍬）分成K组（比如3组），使得每组内的数据点尽量相似，组间的数据点尽量不同。用数学语言来说，就是最小化组内平方误差（Within-Cluster Sum of Squares, WCSS）：

2. 算法步骤

K-Means算法通过以下步骤实现目标：

初始化：随机选择K个中心点μ1,μ2,…,μKμ1,μ2,…,μK。
分配：将每个数据点x分配到离它最近的中心点所在的组：
更新：重新计算每个组的中心点：

$(|C_i|\text{是第}i\text{组的数据点数量。})$
重复：重复步骤2和步骤3，直到中心点不再变化（或变化很小）。

python代码

import numpy as np
import matplotlib.pyplot as plt

# 生成随机数据点
def generate_data(num_points, num_clusters):
    """
    生成随机数据点。
    :param num_points: 每组数据点的数量
    :param num_clusters: 组数
    :return: 数据点和真实中心点
    """
    # 随机生成中心点
    centers = np.random.rand(num_clusters, 2) * 10  # 在0到10的范围内生成中心点
    # 围绕中心点生成数据点
    data = np.vstack([np.random.randn(num_points, 2) + center for center in centers])
    return data, centers


# 计算欧氏距离
def euclidean_distance(x1, x2):
    """
    计算两个点之间的欧氏距离。
    :param x1: 点1
    :param x2: 点2
    :return: 欧氏距离
    """
    return np.sqrt(np.sum((x1 - x2) ** 2))  # 欧氏距离公式


# K-Means算法
def kmeans(data, k, max_iters=100):
    """
    K-Means算法实现。
    :param data: 数据点
    :param k: 组数
    :param max_iters: 最大迭代次数
    :return: 中心点和分组结果
    """
    # 1. 随机初始化中心点
    centroids = data[np.random.choice(range(len(data)), k, replace=False)]  # 从数据中随机选择k个点作为初始中心点
    
    for _ in range(max_iters):
        # 2. 分配步骤：将每个数据点分配到最近的中心点
        clusters = [[] for _ in range(k)]  # 初始化k个空组
        for point in data:
            # 计算当前点到每个中心点的距离
            distances = [euclidean_distance(point, centroid) for centroid in centroids]
            cluster_idx = np.argmin(distances)  # 找到最近的中心点索引
            clusters[cluster_idx].append(point)  # 将点分配到对应的组
        
        # 3. 更新步骤：重新计算中心点
        new_centroids = []
        for cluster in clusters:
            if cluster:  # 如果组不为空
                new_centroids.append(np.mean(cluster, axis=0))  # 计算组内点的平均值作为新中心点
            else:  # 如果组为空，保持原中心点
                new_centroids.append(centroids[len(new_centroids)])
        
        # 检查中心点是否变化
        if np.allclose(centroids, new_centroids):
            break  # 如果中心点不再变化，停止迭代
        
        centroids = new_centroids  # 更新中心点
    
    return centroids, clusters


# 可视化结果
def plot_clusters(data, clusters, centroids):
    """
    可视化聚类结果。
    :param data: 数据点
    :param clusters: 分组结果
    :param centroids: 中心点
    """
    colors = ['r', 'g', 'b', 'y', 'c', 'm']  # 定义颜色
    for i, cluster in enumerate(clusters):
        if cluster:  # 如果组不为空
            cluster = np.array(cluster)  # 将组转换为numpy数组
            plt.scatter(cluster[:, 0], cluster[:, 1], color=colors[i], label=f'Cluster {i+1}')  # 绘制组内点
    # 绘制中心点
    plt.scatter(np.array(centroids)[:, 0], np.array(centroids)[:, 1], color='black', marker='x', label='Centroids')
    plt.legend()  # 显示图例
    plt.title('K-Means Clustering')  # 设置标题
    plt.show()  # 显示图像


# 主程序
if __name__ == "__main__":
    # 生成数据
    num_points = 100  # 每组数据点的数量
    num_clusters = 3  # 组数
    data, true_centers = generate_data(num_points, num_clusters)  # 生成随机数据点和真实中心点
    
    # 运行K-Means算法
    k = 3  # 设定K值
    centroids, clusters = kmeans(data, k)  # 调用K-Means算法
    
    # 可视化结果
    plot_clusters(data, clusters, centroids)  # 绘制聚类结果