[机器学习]K-means算法详解：道理、优错误谬误、代码实现、变体及实际应用

a3102779 · 发表于 2024-7-15 18:47

文章首发于
转载请注明出处。
摘要

K-means算法是一种非常风行的无监督学习方式，主要应用于聚类问题。本篇博客将详细介绍K-means算法的道理、优错误谬误及实际应用场景。
算法道理

K-means算法的核心思想是将数据划分为K个独立的簇(cluster)，使得每个簇内的数据点距离尽可能小，而簇与簇之间的距离尽可能大。下面是K-means算法的具体法式：

初始化：选择K个数据点作为初始质心（centroid），这些质心可以是随机选择的，也可以是通过其他方式选定的。
分配：将每个数据点分配到离它比来的质心所代表的簇中。
更新：从头计算每个簇的质心，方式是将簇内所有数据点的均值作为新的质心。
反复法式2和3，直到质心不再发生显著变化或达到迭代次数上限。

长处

K-means算法具有以下长处：

简单易懂：K-means算法的法式简单，容易理解和实现。
计算效率高：K-means算法的时间复杂度相对较低，适用于大规模数据集。
可扩展性强：K-means算法可以通过各种改良和优化应用于分歧类型的数据和问题。

错误谬误

K-means算法也存在一些局限性：

需要预先指定K值：在实际应用中，选定合适的K值可能需要测验考试多种方式。
对初始质心敏感：算法的成果可能受到初始质心选择的影响，导致局部最优解。
对噪声和离群点敏感：K-means算法容易受到噪声和离群点的影响，可能导致簇划分不准确。
对簇形状和大小敏感：K-means算法假设簇是凸的和大小相似的，对于其他形状和大小的簇可能效果不佳。

代码实现

下面是使用Python和NumPy实现K-means算法的简单示例：

import numpy as np
def initialize_centroids(data, k):
# 从数据集中随机选择k个点作为初始质心
centroids = data[np.random.choice(data.shape[0], k, replace=False)]
return centroids
def assign_clusters(data, centroids):
# 计算数据点与质心之间的距离，并将数据点分配给比来的质心
distances = np.linalg.norm(data[:, np.newaxis] - centroids, axis=2)
cluster_labels = np.argmin(distances, axis=1)
return cluster_labels
def update_centroids(data, cluster_labels, k):
# 计算每个簇的新质心，即簇内数据点的均值
new_centroids = np.array([data[cluster_labels == i].mean(axis=0) for i in range(k)])
return new_centroids
def kmeans(data, k, max_iterations=100, tol=1e-4):
# 初始化质心
centroids = initialize_centroids(data, k)
for _ in range(max_iterations):
# 分配簇
cluster_labels = assign_clusters(data, centroids)
# 更新质心
new_centroids = update_centroids(data, cluster_labels, k)
# 查抄收敛条件
if np.linalg.norm(new_centroids - centroids) < tol:
break
centroids = new_centroids
return centroids, cluster_labels
# 示例：使用K-means算法对随机生成的数据进行聚类
np.random.seed(42)
data = np.random.rand(300, 2) # 生成300个二维数据点
k = 3 # 聚类数量
centroids, cluster_labels = kmeans(data, k)
print(”Centroids:\n”, centroids)
print(”Cluster Labels:\n”, cluster_labels)

复制代码

请注意，这是一个简化的实现，仅用于演示K-means算法的基本道理。在实际应用中，建议使用成熟的机器学习库，如scikit-learn，以获得更不变、高效的实现和额外的功能。
改良方式及变体

针对K-means算法的局限性，有以下改良方式：

选择合适的K值：可以测验考试分歧的K值，通过轮廓系数（Silhouette Coefficient）、肘部法例（Elbow Method）等方式评估聚类效果，选择最佳的K值。
优化初始质心选择：使用K-means++算法改良初始质心选择，降低算法收敛到局部最优解的风险。
增量式K-means：对于大规模数据集，可以采用增量式K-means算法进行分布式计算，提高计算效率。
引入核函数：将K-means算法扩展为Kernel K-means算法，使用核函数将数据映射到高维空间，措置非线性可分的数据。

K-means++

K-means++ 是一种改良的 K-means 算法，主要针对初始质心选择的问题。K-means++ 的优势在于能够选择更好的初始质心，从而提高算法的收敛速度，降低陷入局部最优解的风险。K-means++ 的初始质心选择法式如下：

从数据集中随机选择一个点作为第一个质心。
对于数据集中的每个点，计算它与当前已选择质心的比来距离。
以距离的平方作为权重，按照概率分布随机选择下一个质心。
反复法式2和3，直到选择了 K 个质心。
使用选定的初始质心运行 K-means 算法。

增量式K-means

增量式 K-means（Incremental K-means）也称为在线 K-means，是针对大规模数据集的一种改良算法。与传统的 K-means 算法分歧，增量式 K-means 每次只措置一个数据点，不竭更新质心，而不是一次性措置整个数据集。这种方式适用于分布式计算和大规模数据集，可以大大提高计算效率。增量式 K-means 的主要法式如下：

初始化 K 个质心。
遍历数据集，对每个数据点执行以下操作：
- 计算该点与当前质心的比来距离，将其分配到比来的簇。
- 更新被分配到的簇的质心。
反复法式2，直到质心不变或达到迭代次数上限。

Kernel K-means

Kernel K-means 是一种基于核方式的 K-means 算法，可以措置非线性可分的数据。核方式通过将数据映射到高维特征空间，使得原本在低维空间中不成分的数据在高维空间中变得线性可分。Kernel K-means 的主要法式如下：

选择合适的核函数（如 RBF 核、多项式核等）和参数。
将数据集映射到高维特征空间。
在高维特征空间中执行 K-means 算法。
将聚类成果投影回原始数据空间。

Kernel K-means 可以措置复杂的数据布局，但计算复杂度相对较高，可能不适合大规模数据集。在实际应用中，可以按照问题的特点选择合适的 K-means 算法变体。
应用场景

K-means算法广泛应用于各个范围，如：

图像分割：将图像中的像素聚类为K个簇，可以实现图像分割和简化。
文档聚类：将文档按照内容相似度进行聚类，有助于文档分类、信息检索和保举系统。
客户细分：将客户按照采办行为、兴趣爱好等特征进行聚类，有助于企业针对分歧群体制定个性化的营销策略。
异常检测：通过聚类，可以发现数据中的离群点或异常点，进而进行异常检测或数据清洗。
降维：K-means算法可以与主成分分析（PCA）等降维技术结合，实现数据降维和可视化。

		自动登录	找回密码
密码			立即注册