北京个人网站建设多少钱,成都十大传媒公司,大兵seo博客,哈尔滨seo建站K-means 聚类是一种常用的基于距离的聚类算法#xff0c;旨在将数据集划分为 个簇。算法的目标是最小化簇内的点到簇中心的距离总和。下面#xff0c;我们将从 K-means 的底层原理、算法步骤、数学基础、距离度量方法、参数选择、优缺点 和 源代码实现 等角度进行详细解析。… K-means 聚类是一种常用的基于距离的聚类算法旨在将数据集划分为 个簇。算法的目标是最小化簇内的点到簇中心的距离总和。下面我们将从 K-means 的底层原理、算法步骤、数学基础、距离度量方法、参数选择、优缺点 和 源代码实现 等角度进行详细解析。 1. K-means 的核心思想 K-means 的目标是将数据集划分为 个簇clusters使得每个数据点属于距离最近的簇中心。通过反复调整簇中心的位置K-means 不断优化簇内的紧密度从而获得尽量紧凑、彼此分离的簇。
核心思想
簇ClusterK-means 通过最小化簇内距离的平方和使得数据点在簇内聚集。簇中心Centroid簇中心是簇中所有点的平均值表示簇的中心位置。簇分配和更新K-means 通过不断更新簇分配和簇中心来逐步收敛。 2. K-means 的算法步骤 K-means 聚类的流程分为两个主要步骤分配Assignment和更新Update。以下是详细步骤 选择 K 值 设定簇的数量 。 初始化簇中心 随机选择 个数据点作为初始簇中心centroids。 分配步骤Assignment Step 对于数据集中的每个点将它分配到最近的簇中心对应的簇。这里的“距离”通常使用欧氏距离Euclidean distance。 更新步骤Update Step 根据当前的簇分配重新计算每个簇的中心即计算簇内所有点的均值作为新的簇中心。 重复 3 和 4 步 不断重复分配和更新步骤直到簇中心不再发生变化收敛或达到指定的最大迭代次数。 3. K-means 的数学公式 K-means 的目标是最小化簇内平方误差和Within-Cluster Sum of SquaresWCSS即每个点到其所属簇中心的距离的平方和公式如下 其中 是簇的数量。是第 个簇的点集。是属于 的数据点。是第 个簇的中心。 表示数据点 与簇中心 之间的欧氏距离平方。
欧氏距离
K-means 通常采用欧氏距离来衡量点到簇中心的距离其公式为 其中 n 是数据的维度。 4. K-means 的伪代码
KMeans(X, K):1. 随机选择 K 个点作为初始簇中心2. 重复以下步骤直到簇中心不再发生变化a. 分配每个点到最近的簇中心b. 重新计算每个簇的中心作为簇内所有点的均值3. 返回最终的簇分配和簇中心分配步骤Assignment Step
对于每个数据点找到距离最近的簇中心 μj 更新步骤Update Step
更新每个簇的中心 为簇内所有点的均值 5. K-means 的时间复杂度分析
每次分配步骤需要计算每个点到 个簇中心的距离复杂度为 。更新步骤重新计算每个簇的中心需要遍历所有点复杂度也是 。总复杂度若迭代次数为 则总体复杂度为 。 6. K-means 的优缺点
优点
简单高效在样本数量较少或维度较低时效果很好。收敛速度快在适合的初始中心选择下K-means 通常可以较快收敛。
缺点
对初始点敏感初始簇中心的选择对最终结果影响较大。只能发现球形簇K-means 假设每个簇是凸形且大小相近不能处理非球形的簇。对离群点敏感离群点会影响簇的中心计算。 7. K 值的选择
确定最佳的簇数 是 K-means 聚类中的一个难点。常用的选择方法有 肘部法Elbow Method 绘制不同 K 值下的 WCSS 图寻找“肘部”点作为最佳 值。 轮廓系数Silhouette Coefficient 衡量聚类结果的紧密度和分离度。通常轮廓系数越高聚类效果越好。 Calinski-Harabasz 指数 衡量簇内的方差与簇间方差之比值越大越好。 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_clusters2, random_state0).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 npdef initialize_centroids(X, k):indices np.random.choice(len(X), k, replaceFalse)return X[indices]def closest_centroid(X, centroids):distances np.linalg.norm(X[:, np.newaxis] - centroids, axis2)return np.argmin(distances, axis1)def update_centroids(X, labels, k):return np.array([X[labels i].mean(axis0) for i in range(k)])def kmeans(X, k, max_iters100, tol1e-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):breakcentroids new_centroidsreturn labels, centroids# 示例数据
X np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])# 运行 K-means
labels, centroids kmeans(X, k2)
print(Cluster labels:, labels)
print(Centroids:, centroids)9. 收敛性与初始中心的选择 K-means 的收敛性受到初始簇中心选择的影响。K-means 是一种改进的初始化方法可以帮助选择更合理的初始中心减少陷入局部最优的风险。
K-means 初始中心选择步骤
随机选择一个点作为第一个中心。对于每个点计算其与已选择中心的最小距离。根据与最近中心的距离平方值选择下一个中心概率越大则越有可能成为下一个中心。 10. 总结 K-means 是一种简单、快速的聚类算法广泛应用于数据聚类任务。通过反复优化簇中心位置K-means 不断收敛并找到数据的聚类结构。然而它对初始条件敏感对簇形状有限制适合于球形且均匀分布的簇。在实际应用中可通过结合 K-means、肘部法和轮廓系数等手段改进其效果。
