K-表示需要很长时间

Question

我第一次在我的项目中使用 k 均值。我的数据集有超过 400,000 行和 11 列，我对 k= 3、5、7、9 和 10 运行 k 均值。花费了超过 65 分钟，但仍然没有输出。这正常吗？这是我第一次，所以我不知道会发生什么

我正在使用Python、Visual Studio

sse = []
silhouette_scores = []
k_values = [3, 5, 7, 9]

for k in k_values:
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=1, init='k-means++')
    kmeans.fit(x_pca)
    sse.append(kmeans.inertia_)
    silhouette_scores.append(silhouette_score(x_pca, kmeans.labels_))

# the elbow method
plt.figure(figsize=(10, 6))
plt.plot(k_values, sse, marker='o')
plt.title('Elbow Method for Optimal k')
plt.xlabel('Number of clusters (k)')
plt.ylabel('Sum of Squared Errors (SSE)')
plt.show()

# silhouette scores
plt.figure(figsize=(10, 6))
plt.plot(k_values, silhouette_scores, marker='o')
plt.title('Silhouette Score for Optimal k')
plt.xlabel('Number of clusters (k)')
plt.ylabel('Silhouette Score')
plt.show()

Answer 1

分析

不是你的 K 均值慢，而是

silhouette_score

。

K-means的时间复杂度为

𝑂( 𝑛 × 𝐾 × 𝐼 × 𝑑 )
◦ 𝑛 = number of points,
◦ 𝐾 = number of clusters,
◦ 𝐼 = number of iterations,
◦ 𝑑 = number of attributes

其中最难评估的是

I

，但可以安全地假设它大约为 10-50 次迭代，在

sklearn

默认设置中最多为 300 次。

因此，对于包含 400 000 个点、3-9 个聚类、10-300 次迭代和 11 个属性的数据集，最大复杂度将为 11880000000，或 1.188x10⁸。实际上，这花了我 0.4 秒的时间来获取具有

k=3

的维度示例数据框。

但是，轮廓分数的复杂度是

O(n²)

，所以在你的情况下是160000000000或1.6x10¹¹。与 K 均值计算的“最坏情况”相比，这大约增加了 1000 倍。实际上，可能会增加 10000 倍，因为迭代可能会 k=3。< 100. It took me 30 minutes to run even one pass with 该怎么办？

所以对于“这正常吗？”的问题，答案是

是

。 可以使用

sklearnpairwise_distances

之类的方法预先计算距离矩阵，然后将其传递给 silhouette_score(precomputed_distance_matrix_of_x_pca, kmeans.labels_, metric="precomputed")，但不太可能带来任何显着的加速。

您最好的选择可能是寻找选择簇编号的替代方法，或者只是让代码运行所需的时间。至少考虑在循环之间添加打印来输出进度。