什麼是二分K均值演算法？

二分K均值演算法是對基本K均值演算法的簡單改進，其核心思想是：為了得到K個聚類，將一些點的集合分成兩個聚類，選擇其中一個聚類進行分割，以此類推，直到產生K個聚類。

K均值演算法接收輸入引數k，並將n個物件的集合分成k個聚類，使得聚類內的相似性高，而聚類間的相似性低。聚類相似性是根據聚類中物件的平均值來評估的，該平均值可以看作是聚類的中心或重心。

均值的初始值是任意指定的。這些值可以隨機指定，或者可以使用前k個輸入項的值。收斂標準可以基於平方誤差，但並非必須如此。例如，演算法可以被分配到多個叢集。其他終止方法是設定固定的迭代次數。可以設定最大迭代次數，即使沒有收斂也能保證程式結束。

二分K均值演算法步驟如下：

• 初始化聚類列表，包含一個包含所有點的聚類。

• 重複

• 從聚類列表中移除一個聚類。

• {對選定的聚類執行多次“試驗”二分。

• 對於i：1到試驗次數執行

• 使用基本K均值演算法對選擇的聚類進行二分。

• 結束迴圈

• 選擇總SSE最小的二分聚類。

• 將這兩個聚類插入到聚類列表中。

• 直到聚類列表包含K個聚類。

選擇哪個聚類進行分割的方法有很多種。它可以在每一步選擇最大的聚類，選擇SSE最大的聚類，或者使用基於大小和SSE的元素。不同的選擇會導致不同的聚類結果。

可以使用它們的中心點作為基本K均值演算法的初始中心點來改進最終的聚類結果。這一點很重要，因為雖然K均值演算法保證能找到關於SSE的區域性最小值的聚類，但在二分K均值演算法中，它是“區域性”地使用K均值演算法，即對單個聚類進行二分。因此，最終的聚類集並不一定代表關於總SSE的區域性最小值。

最後，透過記錄K均值演算法對聚類進行二分時建立的一系列聚類，也可以使用二分K均值演算法來建立層次聚類。

Ginni

更新於：2022年2月14日

5K+瀏覽量

啟動你的職業生涯

完成課程獲得認證

開始學習