基本思想

首先二分-K均值是為了解決k-均值的用戶自定義輸入簇值k所延伸出來的自己判斷k數(shù)目，其基本思路是：

為了得到k個(gè)簇，將所有點(diǎn)的集合分裂成兩個(gè)簇，從這些簇中選取一個(gè)繼續(xù)分裂，如此下去，直到產(chǎn)生k個(gè)簇。

比如要分成5個(gè)組，第一次分裂產(chǎn)生2個(gè)組，然后從這2個(gè)組中選一個(gè)目標(biāo)函數(shù)產(chǎn)生的誤差比較大的，分裂這個(gè)組產(chǎn)生2個(gè)，這樣加上開始那1個(gè)就有3個(gè)組了，然后再從這3個(gè)組里選一個(gè)分裂，產(chǎn)生4個(gè)組，重復(fù)此過程，產(chǎn)生5個(gè)組。這算是一中基本求精的思想。二分k均值不太受初始化的困擾，因?yàn)樗鼒?zhí)行了多次二分試驗(yàn)并選取具有最小誤差的試驗(yàn)結(jié)果，還因?yàn)槊坎街挥袃蓚€(gè)質(zhì)心。

偽代碼：

初始化簇表，使之包含由所有的點(diǎn)組成的簇。
repeat
    從簇表中取出一個(gè)簇。
    {對(duì)選定的簇進(jìn)行多次二分試驗(yàn)}
    for i=1 to 試驗(yàn)次數(shù) do
          使用基本k均值，二分選定的簇。
    endfor
    從二分試驗(yàn)中選擇具有最小誤差的兩個(gè)簇。
    將這兩個(gè)簇添加到簇表中。
    until 簇表中包含k個(gè)簇

優(yōu)點(diǎn)與缺點(diǎn)

k均值簡單并且可以用于各種數(shù)據(jù)類型，它相當(dāng)有效，盡管常常多次運(yùn)行。然后k均值并不適合所有的數(shù)據(jù)類型。它不能處理非球形簇，不同尺寸和不同密度的簇。對(duì)包含離群點(diǎn)（噪聲點(diǎn)）的數(shù)據(jù)進(jìn)行聚類時(shí)，k均值也有問題。