聚类分析算法——K-means聚类详解

聚类分析算法——K-means聚类详解

引用

CSDN

1.

https://blog.csdn.net/goTsHgo/article/details/143231544

K-means聚类是一种广泛使用的基于距离的聚类算法，其目标是将数据集划分为K个簇，使得簇内的点到簇中心的距离总和最小。本文将从K-means的底层原理、算法步骤、数学基础、距离度量方法、参数选择、优缺点以及源代码实现等多个维度进行详细解析。

1. K-means的核心思想

K-means的目标是将数据集划分为K个簇（clusters），使得每个数据点属于距离最近的簇中心。通过反复调整簇中心的位置，K-means不断优化簇内的紧密度，从而获得尽量紧凑、彼此分离的簇。

核心概念

• 簇（Cluster）：K-means通过最小化簇内距离的平方和，使得数据点在簇内聚集。一个簇是数据点的集合，这些点在某种意义上“彼此相似”。比如，可以将商场顾客分为“学生群体”“上班族”“退休老人”这三个簇。
• 簇中心（Centroid）：簇中心是簇中所有点的平均值，表示簇的中心位置。
• 簇分配和更新：K-means通过反复迭代，调整簇的分配，使得簇内数据点与质心的距离尽可能小，逐步收敛。

以簇中心为中心，划分范围

2. K-means聚类的工作流程

核心思想

K-means使用“最近距离”来分组：

1. 随机选择K个质心（初始中心点）。
2. 每个数据点分配到距离最近的质心所属的簇。
3. 重新计算每个簇的质心。
4. 重复步骤2和3，直到质心不再变化（或达到指定的迭代次数）。

算法步骤（结合例子）

K-means聚类的流程分为两个主要步骤：分配（Assignment）和更新（Update）。以下是详细步骤：

1. 选择K值：设定簇的数量K。
2. 初始化簇中心：随机选择K个数据点作为初始簇中心（centroids）。
3. 分配步骤（Assignment Step）：对于数据集中的每个点，将它分配到最近的簇中心对应的簇。这里的“距离”通常使用欧氏距离（Euclidean distance）。
4. 更新步骤（Update Step）：根据当前的簇分配，重新计算每个簇的中心，即计算簇内所有点的均值作为新的簇中心。
5. 重复3和4步：不断重复分配和更新步骤，直到簇中心不再发生变化（收敛）或达到指定的最大迭代次数。

假设我们有以下二维数据点，表示顾客的“消费金额”和“访问次数”：

目标是将这些点分为K=2个簇。

第一步：初始化质心

• 随机选择两个点作为初始质心（假设选择点1和点5）。
• 初始质心为：
• C1=(1,2)
• C2=(8,8)

第二步：分配簇
计算每个点到两个质心的欧几里得距离：

分配结果：

• 簇1：点1、点2、点3
• 簇2：点4、点5

第三步：重新计算质心
对于每个簇，计算新质心的位置：

• 簇1的质心：(平均x,平均y)=(1+2+4/3,2+1+5/3)=(2.33,2.67)
• 簇2的质心：(平均x,平均y)=(5+8/2,6+8/2)=(6.5,7.0)

更新质心为：

• C1=(2.33,2.67)
• C2=(6.5,7.0)

第四步：重复分配与更新
再次计算每个点到新质心的距离，重复“分配簇”和“重新计算质心”步骤，直到质心不再变化。

最终结果：

• 簇1：点1、点2、点3
• 簇2：点4、点5
  质心稳定在：
• C1=(2.33,2.67)
• C2=(6.5,6.0)

3. K-means的数学公式

K-means的目标是最小化簇内平方误差和（Within-Cluster Sum of Squares，WCSS），即每个点到其所属簇中心的距离的平方和，公式如下：

其中：

• K是簇的数量。
• Ci是第i个簇的点集。
• xj是属于Ci的数据点。
• μi是第i个簇的质心。
• d(xj,μi)表示数据点xj与簇中心μi之间的欧氏距离平方。

欧氏距离

K-means通常采用欧氏距离来衡量点到簇中心的距离，其公式为：

其中n是数据的维度。

4. K-means的伪代码

KMeans(X, K):
    1. 随机选择K个点作为初始簇中心
    2. 重复以下步骤，直到簇中心不再发生变化：
        a. 分配每个点到最近的簇中心
        b. 重新计算每个簇的中心，作为簇内所有点的均值
    3. 返回最终的簇分配和簇中心

分配步骤（Assignment Step）

对于每个数据点，找到距离最近的簇中心μj：

更新步骤（Update Step）

更新每个簇的中心μi为簇内所有点的均值：

5. K-means的时间复杂度分析

• 每次分配步骤：需要计算每个点到K个簇中心的距离，复杂度为O(nKd)。
• 更新步骤：重新计算每个簇的中心，需要遍历所有点，复杂度也是O(nKd)。
• 总复杂度：若迭代次数为T，则总体复杂度为O(TnKd)。

6. K-means的优缺点

优点

• 简单高效：适合大规模数据,处理大数据集时非常高效，具有良好的伸缩性。
• 收敛速度快：在适合的初始中心选择下，K-means通常可以较快收敛。

缺点

• 对初始点敏感：初始簇中心的选择对最终结果影响较大。
• 非凸形状簇(球形簇)：K-means假设每个簇是凸形且大小相近，不适合发现非凸形状的簇或大小差异很大的簇,如“月牙型”数据。
• 对噪声敏感：离群点会影响簇的中心计算。
• 局部最优：K-means不能保证全局最优，只能达到局部最优
• 数据种类限制：算法要求样本存在均值，限制了数据的种类

7. K值的选择

确定最佳的簇数K是K-means聚类中的一个难点。常用的选择方法有：

1. 肘部法（Elbow Method）：绘制不同K值下的WCSS图，寻找“肘部”点作为最佳K值。
2. 轮廓系数（Silhouette Coefficient）：衡量聚类结果的紧密度和分离度。通常，轮廓系数越高，聚类效果越好。
3. Calinski-Harabasz指数：衡量簇内的方差与簇间方差之比，值越大越好。

下图可以发现当k=4或者5时是最佳的情况SSE图像下降幅度最大放缓的情况在4-5之间。

8. Python实现K-means

我们可以使用scikit-learn中的KMeans，以及手动实现以便更深入理解。

8.1 使用scikit-learn实现K-means

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]]

8.2 手动实现K-means算法

以下是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=2)
print("最终簇:", labels)
print("质心位置:", centroids)

9. 收敛性与初始中心的选择

K-means的收敛性受到初始簇中心选择的影响。K-means++是一种改进的初始化方法，可以帮助选择更合理的初始中心，优先选择“距离最远”的点作为初始质心，减少陷入局部最优的风险。

K-means++初始中心选择步骤

1. 随机选择一个点作为第一个中心。
2. 对于每个点，计算其与已选择中心的最小距离。
3. 对于每一个未被选中的数据点，计算其到已选中心的距离D(x)，即对于数据点x，计算其到已选择的所有质心的最短距离D(x)，其中C是已选的聚类中心集合。
4. 加权选择下一个中心：根据每个数据点的距离D(x)的平方来选择下一个聚类中心，选择的概率与D(x)的值的大小成正比。也就是说，距离当前已选聚类中心远的点，被选为新中心的概率更大。
5. 重复步骤2，直到选择K个聚类中心。

为什么K-means++更好？

• 避免了随机初始化的问题：传统的K-means算法是随机选择聚类中心，可能导致聚类中心选择得非常接近，这样会导致算法陷入局部最优解，或者聚类效果不好。K-means++通过加权选择，确保了初始聚类中心的分布更加均匀，从而减少了这种风险。
• 提高了收敛速度：由于初始聚类中心已经比较合理，K-means++通常能更快收敛。K-means算法的收敛速度和初始中心的选择密切相关，选择较好的初始中心可以减少迭代次数。
• 更稳定的聚类结果：K-means++选择中心的方式使得最终聚类结果更加稳定，尤其在处理具有复杂结构或分布的数据时，相比传统的随机初始化方法，K-means++更能得到质量较高的聚类结果。

10. 总结

K-means是一种简单、快速的聚类算法，广泛应用于数据聚类任务。通过反复优化簇中心位置，K-means不断收敛并找到数据的聚类结构。然而，它对初始条件敏感，对簇形状有限制，适合于球形且均匀分布的簇。在实际应用中，可通过结合K-means++、肘部法和轮廓系数等手段改进其效果。