学习日记_20241110_聚类方法（K-Means）

前言

提醒：
文章内容为方便作者自己后日复习与查阅而进行的书写与发布，其中引用内容都会使用链接表明出处（如有侵权问题，请及时联系）。
其中内容多为一次书写，缺少检查与订正，如有问题或其他拓展及意见建议，欢迎评论区讨论交流。

聚类算法

聚类算法在各种领域中有广泛的应用，主要用于发现数据中的自然分组和模式。以下是一些常见的应用场景以及每种算法的优缺点：

经典应用场景

1. 市场细分：根据消费者的行为和特征，将他们分成不同的群体，以便进行有针对性的营销。

2. 图像分割： 将图像划分为多个区域或对象，以便进行进一步的分析或处理。

3. 社交网络分析：识别社交网络中的社区结构。

4. 文档分类：自动将文档分组到不同的主题或类别中。

5. 异常检测识别数据中的异常点或异常行为。

6. 基因表达分析：在生物信息学中，根据基因表达模式对基因进行聚类。

K-Means 聚类

1. K-Means 聚类

• 优点：
  • 算法简单，容易实现。
  • 计算速度快，适用于大规模数据集。
• 缺点：
  • 需要预先指定簇的数量 $K$。
  • 对于初始中心点选择敏感。
  • 只能找到球状簇，无法处理非凸形状的簇。
  • 对噪声和异常值敏感。

简单实例（函数库实现）

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
# 生成数据
X = np.random.rand(100, 2)
# K-Means 聚类
kmeans = KMeans(n_clusters=3)
kmeans.fit(X)
labels = kmeans.labels_
# 可视化
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], color='red')
plt.title('K-Means Clustering')
plt.show()

X数据分布：

代码运行结果：

数学表达

K-Means 聚类是一种常用的无监督学习算法，目的是将数据分为 $K$ 个簇，以最小化簇内数据点与簇中心的方差之和。下面是对
K-Means 聚类算法的详细介绍，包括其数学公式和步骤。

K-Means 算法步骤

1. 初始化

   从数据集中随机选择 $K$ 个点作为初始簇中心（质心），记作 { μ 1 , μ 2 , … , μ K } \{\mu_1, \mu_2, \ldots, \mu_K\} {μ1​,μ2​,…,μK​}。

2. 分配数据点

   对于每个数据点 ${\mathbf{x}}_i$，计算其与每个簇中心的距离，将其分配到距离最近的簇中。通常采用欧氏距离作为距离度量：

   $$\text{assign }{\mathbf{x}}_i\text{ to cluster }j=\arg \underset{k}{\min }\Vert {\mathbf{x}}_i-{\mu }_k{\Vert }^2$$

3. 更新簇中心

   对于每个簇 $j$，计算簇中所有数据点的均值作为新的簇中心：

   $${\mu }_j=\frac{1}{N_j}\sum _{{\mathbf{x}}_i\in C_j}{\mathbf{x}}_i$$

   其中 $C_j$ 表示簇 $j$ 中的所有数据点，$N_j$ 是簇 $j$ 中的点的数量。

4. 重复

   重复步骤 2 和步骤 3，直到簇中心不再发生变化或达到预设的迭代次数。

数学优化目标

K-Means 聚类的目标是最小化所有数据点到其所属簇中心的距离平方和。其优化目标函数为：

$$J=\sum _{j=1}^K\sum _{{\mathbf{x}}_i\in C_j}\Vert {\mathbf{x}}_i-{\mu }_j{\Vert }^2$$

这里，$J$ 是代价函数，表示簇内平方误差和。

收敛性

K-Means 算法通过交替优化分配和更新步骤最终收敛，因为每一步都使得代价函数 $J$单调递减。然而，算法可能收敛到局部最小值，因此初始化方式对最终结果有较大影响。

优点

• 实现简单，计算速度快。
• 在簇形状是凸的、簇的大小相似的情况下效果较好。

缺点

• 选择 $K$ 值比较困难，通常需要通过经验或使用评估指标（如肘部法则、轮廓系数）来选择。
• 对初始值敏感，可能导致收敛到局部最优。
• 适用于凸形簇，对于不同大小和密度的簇效果不好。
• 对噪声和孤立点敏感。

K-Means 聚类是一种简单有效的聚类方法，广泛应用于各种实际问题，但在使用中需注意其局限性和对参数选择的要求。

手动实现

import numpy as np

def initialize_centroids(X, K):
    # 从数据集中随机选择K个样本作为初始质心
    indices = np.random.choice(X.shape[0], K, replace=False)
    centroids = X[indices]
    return centroids

def assign_clusters(X, centroids):
    # 计算每个样本到每个质心的距离，并将样本分配到最近的质心
    distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))
    return np.argmin(distances, axis=0)

def update_centroids(X, labels, K):
    # 根据分配结果更新质心为每个簇中所有样本的均值
    centroids = np.array([X[labels == k].mean(axis=0) for k in range(K)])
    return centroids

def kmeans(X, K, max_iters=100, tol=1e-4):
    # 初始化质心
    centroids = initialize_centroids(X, K)
    for i in range(max_iters):
        # 分配样本到最近的质心
        labels = assign_clusters(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
# 示例用法
if __name__ == "__main__":
    # 生成一些测试数据
    X = np.array([[1.0, 2.0], [1.5, 1.8], [5.0, 8.0], 
                  [8.0, 8.0], [1.0, 0.6], [9.0, 11.0],
                  [8.0, 2.0], [10.0, 2.0], [9.0, 3.0]])
    # 设定簇的数量
    K = 3
    # 运行K-Means算法
    labels, centroids = kmeans(X, K)

    print("Cluster labels:", labels)
    print("Centroids:", centroids)

代码分析

1. np.random.choice(X.shape[0], K, replace=False)
numpy.random.choice(a, size=None, replace=True, p=None)
np.random.choice 是 NumPy 库中的一个函数，用于从给定的一维数组中生成随机样本。它可以指定样本的数量、是否允许重复选择等参数。

2. np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))

• centroids[:, np.newaxis]: 使用 np.newaxis 将 centroids 的形状从 (K, n_features) 变为 (K, 1, n_features)，这样做是为了实现广播（broadcasting），以便在后续计算中能够对每个质心与每个样本进行逐元素运算。
• X - centroids[:, np.newaxis]：这个操作会创建一个形状为 (K, n_samples, n_features) 的数组，表示每个质心与每个样本之间的差值。
• .sum(axis=2)：这个操作会对最后一个维度（特征维度）进行求和，结果是一个形状为 (K, n_samples) 的数组，表示每个样本与每个质心之间的特征平方和。

3. np.argmin(distances, axis=0)

• np.argmin 是一个NumPy函数，用于找到数组中最小值的索引。
• axis=0 表示沿着第一个轴（即行）查找最小值。这意味着对每个样本（每列）比较所有质心的距离，找到最小值对应的质心索引。