Clustering
為什麼 k-means 不給出全局最小值？
我讀到 k-means 算法只收斂到局部最小值而不是全局最小值。為什麼是這樣？我可以從邏輯上想到初始化如何影響最終的聚類，並且存在次優聚類的可能性，但我沒有找到任何可以在數學上證明這一點的東西。
另外，為什麼 k-means 是一個迭代過程？我們不能只是將目標函數部分區分為質心，將其等同於零以找到最小化該函數的質心嗎？為什麼我們必須使用梯度下降來逐步達到最小值？
您可以將 k-means 視為 EM 算法的特殊版本，這可能會有所幫助。
假設您正在估計每個集群的多元正態分佈，協方差矩陣固定為所有的單位矩陣，但均值可變在哪裡是集群的索引。顯然，如果參數已知，您可以分配每個點它的最大似然簇（即距離最少）。這個問題的EM算法幾乎等同於k-means。
反過來，如果你知道哪些點屬於哪個簇，你可以估計出最優的. 對此的封閉形式解決方案（找到全局最優值）基本上說要找到最大似然模型您將所有可能的點分配整合到集群中。因為即使只有 30 個點和兩個集群，也有大約 10 億個這樣的可能分配，這是無法計算的。
相反，我們可以對隱藏參數（或模型參數）進行一些猜測並迭代這兩個步驟（最終可能達到局部最大值）。如果您允許每個集群對一個點承擔部分責任，那麼您最終會得到 EM，如果您只是分配最佳集群，那麼您會得到 k-means。
因此，執行摘要：在概率方面，有一個全局解決方案，但它需要您迭代所有可能的集群。顯然，如果你有一個目標函數，也是如此。您可以迭代所有解決方案並最大化目標函數，但迭代次數是數據大小的指數。