我读到 k-means 算法只收敛到局部最小值而不是全局最小值。为什么是这样？我可以从逻辑上想到初始化如何影响最终的聚类，并且存在次优聚类的可能性，但我没有找到任何可以在数学上证明这一点的东西。
另外，为什么 k-means 是一个迭代过程？我们不能只是将目标函数部分区分为质心，将其等同于零以找到最小化该函数的质心吗？为什么我们必须使用梯度下降来逐步达到最小值？
问问题
12197 次
2 回答
14
考虑：
. c .
. c .
其中 c 是簇质心。该算法将停止，但更好的解决方案是：
. .
c c
. .
关于证明 - 您不需要数学证明来证明某些事情并不总是正确的，您只需要一个反例，如上所述。您可能可以将上述内容转换为数学证明，但这是不必要的，通常需要大量工作；即使在学术界，也可以接受仅仅给出一个反例来反驳某事。
根据定义，k-means 算法是一个迭代过程，它就是它的工作方式。聚类的问题是 NP-hard，因此使用精确的算法来计算质心将花费大量时间。
于 2013-01-29T07:13:24.527 回答
8
不要将问题和算法混为一谈。
k 均值问题是找到质心的最小二乘分配。
有多种算法可以找到解决方案。
有一种明显的方法可以找到全局最优值：枚举所有k^n可能的分配——这将产生一个全局最小值，但在指数运行时。
人们更加关注在更快的时间内找到近似解决方案。
Lloyd/Forgy 算法是一种 EM 风格的迭代模型细化方法，它保证收敛到局部最小值，因为状态数量有限，并且目标函数必须在每一步中减小。该算法通常在O(n*k*i)哪里运行i << n，但它可能只找到局部最小值。
MacQueens 方法在技术上不是迭代的。这是一种单程、一次一个元素的算法，甚至无法找到 Lloyd 意义上的局部最小值。（但是，您可以在数据集上多次运行它，直到收敛，以获得局部最小值！）如果您执行单次遍历，它的 in O(n*k)，对于多次遍历 add i。它可能需要也可能不会比 Lloyd 需要更多的通行证。
然后是Hartigan和Wong。我不记得细节了，IIRC 它是 Lloyd/Forgy 的一个聪明、更懒惰的变体，所以也可能在 中O(n*k*i)（尽管可能不会n*k为以后的迭代重新计算所有距离？）
你也可以做一个随机算法来测试l随机分配。它可能根本找不到最小值，而是以“线性”时间运行O(n*l)。
哦，您可以尝试不同的随机初始化，以提高找到全局最小值的机会。添加t试验次数的因素...
于 2013-01-29T08:26:15.487 回答