k 均值 - 是否有可能用更高的 k 获得更差的结果？

Question

我想找到在数据集上使用 k 均值的最佳 k。我使用下面的代码：

Sum_of_squared_distances = []
for k in range(1,15):
    print(k)
    Sum_of_squared_distances.append(KMeans(n_clusters=k).fit(x).inertia_)
plt.plot(range(1,15), Sum_of_squared_distances, 'bx-')
plt.xlabel('k')
plt.xticks(range(1,15))
plt.ylabel('Sum_of_squared_distances')
plt.title('Elbow Method For Optimal k')
plt.savefig('optimal-k.jpg')
plt.show()

我的结果是这样的：

如您所见，对于某些 k 值，k 越高，结果越差。我想知道这是可能的还是我做错了什么？一些深入的解释将不胜感激。

Answer 1

有可能。

对于给定的 k，K-means 并没有完全解决——这是一个 NP-Hard 问题。您看到的是通过基于启发式的优化算法实现的局部最优结果。

准确地说，如果您能够针对给定的 k 准确求解，您会看到图表严格下降。但是因为你不能，所以你会在你的情节中看到一个模式。

算法的结果取决于初始运行dom 起点，因此如果您运行每个 k 多次（即增加 n_init 中的参数 KMeans), 你会看到图表更平滑地下降，因为那样你会消除一些噪音。

k 均值 - 是否有可能用更高的 k 获得更差的结果？

k-means - is it possible to get worse result with higher k?

python

k-means

scikit-learn