K-Means
k-means vs k-means++
據我所知，k-means 隨機選擇初始中心。由於它們是基於純粹的運氣，因此它們可能會被選中。K-means++ 算法試圖通過均勻分佈初始中心來解決這個問題。
- 這兩種算法能保證相同的結果嗎？或者，無論迭代多少次，選擇不當的初始質心都可能導致不好的結果。
- 假設有一個給定的數據集和給定數量的所需集群。只要收斂（不再中心移動），我們就會運行 k-means 算法。這個集群問題是否有確切的解決方案（給定 SSE），或者 k-means 在重新運行時有時會產生不同的結果？
- 如果對聚類問題有多個解決方案（給定數據集，給定集群數量），K-means++ 是否保證更好的結果，或者只是更快？更好是指更低的 SSE。
我問這些問題的原因是因為我正在尋找一種 k-means 算法來聚類一個巨大的數據集。我找到了一些 k-means++，但也有一些 CUDA 實現。如您所知，CUDA 正在使用 GPU，它可以並行運行數百個線程。（所以它真的可以加快整個過程）。但是到目前為止，我發現的所有 CUDA 實現都沒有 k-means++ 初始化。
K-means 從隨機分配集群中心開始，然後尋找“更好”的解決方案。K-means++ 從隨機分配一個集群中心開始，然後在給定第一個中心的情況下搜索其他中心。所以這兩種算法都使用隨機初始化作為起點，因此可以在不同的運行中給出不同的結果。作為示例，您可以查看本講座：Clustering As An Example Inference Problem，大約第 40 分鐘有 k-means 運行的示例，但整個講座很有趣。
所以，回答你的問題：
- 不，因為存在隨機初始化，不同的運行會給出不同的結果（參見講座中的示例）。他們應該給出可比較的結果，但這不能保證。此外，由於所有中心都是在 k-means 中隨機初始化的，因此它可以給出與 k-means++ 不同的結果。
- K-means 可以在不同的運行中給出不同的結果。
- k-means++ 論文提供了蒙特卡羅模擬結果，表明 k-means++ 速度更快，性能更好，因此不能保證，但可能會更好。
至於你的問題：k-means++ 選擇中心然後開始一個“經典”k-means。所以你可以做的是（1）使用選擇中心的算法部分，然後（2）在 k-means 的 GPU 實現中使用這些中心。這樣至少部分問題在基於 GPU 的軟件上得到解決，因此應該更快。