Pra*_*rni 3 gradient cluster-analysis data-mining k-means convergence
我读到k-means算法只收敛到局部最小值而不是全局最小值.为什么是这样？我可以从逻辑上思考初始化如何影响最终的聚类,并且有可能进行次优聚类,但我没有找到任何可以在数学上证明这一点的东西.
另外,为什么k-means是一个迭代过程？我们难道不能将目标函数wrt部分区分为质心,将其等于零以找到最小化此函数的质心吗？为什么我们必须使用梯度下降来逐步达到最小值？
Duk*_*ing 10
考虑:
. c .
. c .
其中c是聚类质心.该算法将停止,但更好的解决方案是:
. .
c c
. .
关于证明 - 您不需要数学证明来证明某些事情并非总是如此,您只需要一个反例,如上所述.您可以将上述内容转换为数学证明,但这是不必要的,通常需要大量工作; 即使在学术界,仅仅举一个反例来反驳某些东西也是可以接受的.
根据定义,k-means算法是一个迭代过程,它只是它的工作方式.聚类的问题是NP难的,因此使用精确的算法来计算质心将花费非常长的时间.
不要混淆问题和算法.
k均值问题是找到质心的最小二乘分配.
有多种算法可供查找解决方案.
有一种明显的方法可以找到全局最优:枚举所有k^n可能的赋值 - 这将产生全局最小值,但是在指数运行时.
更加注意在更快的时间内找到近似解决方案.
Lloyd/Forgy算法是一种EM风格的迭代模型细化方法,只需因为存在有限数量的状态而保证收敛到局部最小值,并且目标函数必须在每一步中减少.此算法通常O(n*k*i)在i << n通常的位置运行,但它可能只找到局部最小值.
MacQueens方法在技术上不是迭代的.它是一种单通道,一元一元的算法,甚至在Lloyd意义上也找不到局部最小值.(然而,您可以在数据集上运行多次传递,直到收敛,以获得局部最小值!)如果您执行单次传递O(n*k),则为多次传递添加i.它可能会或可能不会比劳埃德更多的通行证.
还有Hartigan和Wong.我不记得细节了,IIRC它是Lloyd/Forgy的一个聪明,更懒惰的变体,所以可能O(n*k*i)也是这样(虽然可能不会重新计算所有n*k距离以便以后的迭代？)
你也可以做一个只测试l随机分配的随机算法.它可能根本找不到最小值,但在"线性"时间内运行O(n*l).
哦,您可以尝试不同的随机初始化,以提高您找到全局最小值的机会.添加t试验次数的因子......