演算法的理解
Bi這裡是的意思就是Binary，二進位制的意思，所以有時候叫這個演算法為二進Kmeans演算法。為什麼我們需要用BiKmeans呢，就是為了解決初始化k個隨機的質心點時其中一個或者多個點由於位置太極端而導致迭代的過程中消失的問題。BiKmeans只是Kmeans其中一個最佳化方案，其實還是有很多最佳化的方案，這裡BiKmeans容易講解和理解，並且容易用numpy， pandas實現。
那為什麼二進Kmeans演算法可以有效的解決這個問題呢。我們需要從二進Kmeans的基礎看是講起。其實BiKmeans的迭代過程類似於一個決策樹。首先我們看一下Kmeans演算法的步驟。
利用之前寫好的Kmeans演算法包，設定k為2。所以每次傳入一個數據集的時候，都是進行2分類。
假設我們預先想分出K個簇。
使用Kmeans（k=2）將資料集分成2個簇，記錄SSE
對於每一個簇來說，都有自己當前的SSE，取名為父節點SSE
a。 對這些簇都進行Kmeans二分類，並且記錄分出的2個簇的SSE只和，稱之為子節點總SSE
b。 記錄這個簇被2分類之後SSE的差值，SSE差值 = 父節點SSE - 子節點SSE
選擇SSE差值最大的那個簇進行劃分，而其他的簇不進行劃分。
重複第二的步驟，直到簇的總個數達到K
用決策樹的方法理解BiKmeans
那這個演算法其實就是非常的類似決策樹的演算法。在決策樹節點由父節點劃分成子節點的過程中，用的是gini不純度來判斷是否需要劃分，我們選擇不純度差值最大的那個特徵來做劃分。這裡也類似，我們最後的目標是最小化SSE，所以對每一個簇來說，都可以得出該簇在劃分出成2個簇之後總體上SSE降低了多少，我們需要做的就是保持其他的簇不變，選取的就是那個能夠最大程度的降低SSE的那個簇進行Kmeans二分類。
那個演算法裡面還是有個缺陷，就是在演算法的過程中，會對每個簇重複計算劃分後SSE的差值，所以這裡我在對每個簇做劃分後，記錄下它的SSE差值，後期就可以直接使用SSE，不用重新再計算一遍了。
我們首先用決策樹的概念來看下BiKmeans，我們目標是分成4個簇，首先有我們有我們的根節點，也就是我們的整體的資料集，假設這個資料集的SSE為100。
使用Kmeans對根節點做2分類。得出2個簇，簇內SSE分別為40和30，也就是說如果我們對整體資料集做一次Kmeans二分類的話，我們的整體SSE會下降100-（30+40）=30
在此時可以對每個葉節點的資料集進行二分類，檢視這個簇做二分Kmeans後，SSE下降多少。從這裡可以看出，對簇1來說，SSE的變化為40-（20+15）=5，對簇2來說，SSE的變化為30-（10+10）=10。所以說對這2個簇來說的話，應該保留簇1，對簇2進行二分Kmeans。這樣的話可以最大程度的減少總體SSE，因為簇2二分Kmeans後SSE下降的最快。結果就是以下的情況，當前葉節點有3個，也就是說當前我們有3個簇，還沒有達到我們的目標，4個簇，繼續對每個葉節點進行劃分。注，這裡原來的簇2就不復存在了，變成了小一點的簇2和簇3。
從上面的圖看出，現在有3個簇，對每個簇都做二分Kmeans，之前簇1的SSE差值已經算過了，是40-（20+15）=5，對於簇2來說，SSE變化為10-（8+1）=1， 對於簇3來說，SSE的變化為10-（7+1）=2。這裡簇1的SSE變化值最大，優先對簇1做二分Kmeans，得出以下結果。
當前決策樹一共有4個葉節點，每個葉節點都代表一個簇，簇的個數已經達到我們的目標。演算法結束。
程式碼實現
首先先讀取資料，讀取的是上次我們在Kmeans中間過程最後展示原始Kmeans理論缺陷的那組資料。
from Kmeans_pack import *
r = 4 k = 3 x ， y = make_blobs（n_samples = 400， cluster_std = ［0。2， 0。4， 0。4， 0。4］， centers = ［［0。3，-1］，［1，1］，［-1，1］， ［-1，-1］］， random_state = r ） np。random。seed（r） sim_data = pd。DataFrame（x， columns = ［‘x’， ‘y’］） sim_data［‘label’］ = y dataset = sim_data。copy（）
現在我們嘗試的將資料只做一次二分Kmeans的迭代，檢視結果，這個時候會有兩種結果
在這兩個情況下，我們看到2分Kmeans可以將當前資料集分成2個簇，緊接著我們就需要嘗試分別對藍色和黃色的簇進行2分Kmeans檢視每個簇劃分後SSE下降了少。我們會首先寫一個Split函式，對每個傳進去的資料集進行2分Kmeans。但是這裡需要注意是否是第一次做劃分，就比如上面的情況。
這裡我們首先有個split函式，專門用來對傳入的資料做2分Kmeans，算出聚類前和聚類後的SSE，比如說假如這個時候我們有x和y，\bar{x}
x
ˉ和\bar{y}
y
ˉ為x和y的平均值
\left［ \begin{matrix} （x_{1}-\bar{x}）^2 + （y_{1}-\bar{y}）^2 \\ （x_{2}-\bar{x}）^2 + （y_{2}-\bar{y}）^2 \\ （x_{3}-\bar{x}）^2 + （y_{3}-\bar{y}）^2 \end{matrix} \right］⎣⎡（
x
1−
x
ˉ）2+（
y
1−
y
ˉ）2（
x
2−
x
ˉ）2+（
y
2−
y
ˉ）2（
x
3−
x
ˉ）2+（
y
3−
y
ˉ）2⎦⎤
用的方法就是使用np。power（data - mean， 2）。sum（axis = 1）得出的就是這個簇一開始的SSE。
將資料集帶入之前寫的Kmeans_regular後設置k=2，會給出SSE_list， SSE_list［-1］會給出Kmeans聚類好資料集之後2個簇加起來SSE的綜合，並且也會給出curr_group， 用來劃分我們的簇，方便選取其中的簇帶入下一次迭代
def Split（dataset）：
#假設當前資料不是第一次二分Kmeans，就是說傳進來的是整體的資料集，當前的質心點就是每個特徵的平均值
temp_data = dataset。loc［：， dataset。columns ！= ‘label’］。copy（）
#計算當前資料集的SSE
current_error = np。power（temp_data - temp_data。mean（）， 2）。sum（）。sum（）
#對資料集做二分Kmeans
curr_group， SSE_list， centers = Kmeans_regular（temp_data， k = 2）
#記錄二分後的SSE
after_split_error = SSE_list［-1］
#已經有了curr_group將二分類後的資料集先拿出來
clusters = list（dataset。groupby（curr_group））
#這裡有非常非常少的情況會出現二分Kmeans中初始的質心點其中一個由於離所有的都太遠，導致丟失的情況
#所以這裡多加了一個判斷，假如其中一個質心掉了，那上面給的clusters只有一個而不是兩個
#在這個情況下，dataset沒有被成功二分類，我們需要將dataset自身給return，進行下一次迭代，肯定有一次迭代能成功分出2個簇
#所以在這個情況下entropy就是current_error， cluster1就是dataset自己，cluster2為空
if len（clusters） == 1： entropy = current_error return ［entropy， dataset， None， current_error］
#分別取出2個簇
cluster1， cluster2 = ［i［1］ for i in clusters］
#計算這個簇做了二分Kmeans後SSE下降的多少
entropy = current_error - after_split_error
#最後返回結果，返回當前這個簇二分後的SSE差值，分出的簇1和簇2，還有當前這個簇的SSE
return ［entropy， cluster1， cluster2， current_error］
這個函式寫好之後我們來測試一下，當前我們將所有的資料全部傳進去後，給出的結果
entropy， cluster1， cluster2， current_error = Split（dataset） entropy， cluster1。shape［0］， cluster2。shape［0］， current_error
（432。9176440191153， 200， 200， 813。3842612925762）
當前資料集做完二分後整體SSE由原來的813，下降了432。92。
接下來就是需要完成2分Kmeans的迭代過程
def bi_iterate（dataset， k = 4）：
#首先準備一個空的cluster_info_list，這個list是用來存二分後的結果，裡面每一個元素都是一個簇
#對於每個元素來說，它代表的是個簇，裡面記錄的這個簇的［entropy， cluster1， cluster2， current_error］
#也就是每個簇的［SSE差值，第一個二分後的簇，第二個二分後的簇，當前簇的SSE］
cluster_info_list = ［］
#使用while做迴圈直到cluster_info_list裡面一共達到k個簇的時候停止
while len（cluster_info_list） < k：
#假如當前我們是第一次迭代的話也就是cluster_info_list是空list的話做以下操作
if len（cluster_info_list） == 0：
#直接用Split函式，將整體資料集放入cluster_info_list裡，然後下面的操作都不用，continue進入下一個迴圈
cluster_info_list。append（Split（dataset）） continue
#首先將cluster_info_list最後一個元素取出來，cluster_info_list裡面是所有簇的資訊
#我們後面會對cluster_info_list做sort，由於cluster_info_list裡面每個元素的第一位是SSE差值
#所以我們做完sort後，最後一個元素肯定是SSE差值（entropy）最大的那一個，也就是我們需要下一步做二分的簇
#將最後一個元素裡的2個clusters取出來後，將這個當前在cluster_info_list裡SSE最大的一個簇刪除掉（pop方法）
#取而代之的是Split（cluster1）和Split（cluster2），也是就嘗試著對新的兩個cluster嘗試去算SSE差值
cluster1， cluster2 = cluster_info_list［-1］［1：-1］ cluster_info_list。pop（-1）
#將Split（cluster1）和Split（cluster2）的結果追加到cluster_info_list
#注意假如只有cluster2給出的是None，則碰到二分類不成功的情況，cluster1還為原來上一次dataset，cluster2為空
#不將cluster2追加到cluster_info_list當中
cluster_info_list。append（Split（cluster1）） if cluster2 is not None： cluster_info_list。append（Split（cluster2））
#整體的cluster_info_list進行一次sort，找出當前所有的簇中，哪一個簇的SSE差值最大
#這裡我們是需要對整體cluster_info_list做sort，因為新追加進去的2個心cluster的SSE差值可能沒有cluster_info_list裡已經記錄的簇的SSE大。
cluster_info_list。sort（）
#進入下一個迴圈
return cluster_info_list
將總共的程式碼都放在一起，內容不多，和網上的程式碼相比的話，簡單易懂量少，也避免了效率較低的for迴圈。
from Kmeans_pack import * def Split（dataset）： temp_data = dataset。loc［：， dataset。columns ！= ‘label’］。copy（） current_error = np。power（temp_data - temp_data。mean（）， 2）。sum（）。sum（） curr_group， SSE_list， centers = Kmeans_regular（temp_data， k = 2） after_split_error = SSE_list［-1］ clusters = list（dataset。groupby（curr_group）） if len（clusters） == 1： entropy = current_error return ［entropy， dataset， None， None， current_error］ cluster1， cluster2 = ［i［1］ for i in clusters］ entropy = current_error - after_split_error return ［entropy， cluster1， cluster2， centers， curr_group， current_error， dataset］ def bi_Kmeans（dataset， k = 4）： cluster_info_list = ［］ while len（cluster_info_list） < k： if len（cluster_info_list） == 0： cluster_info_list。append（Split（dataset）） continue cluster1， cluster2 = cluster_info_list［-1］［1：3］ cluster_info_list。pop（-1） cluster_info_list。append（Split（cluster1）） if cluster2 is not None： cluster_info_list。append（Split（cluster2）） cluster_info_list。sort（） return cluster_info_list
我們測試一下程式碼，返回的cluster_info_list裡面所有的元素都是簇的資訊，每個元素的最後一位都是這個簇的簇內SSE，所以我們可以用列表解析的方法將每個元素的最後一位取出來，進行相加就能得到BiKmeans最後的結果給出的整體的SSE，我們可以看出在資料集要4個簇的前提下，我們SSE最後為95。64
np。random。seed（1） cluster_info_list = bi_Kmeans（dataset， k = 4）
ReKmeans和BiKmeans的結果對比
我們也可以將這個結果和原始寫好的Kmeans_regular做比較
regular_SSE = ［］ bi_SSE = ［］ for i in range（50）： curr_group， SSE_list， centers = Kmeans_regular（dataset， k = 4） cluster_info_list = bi_Kmeans（dataset， k = 4） bi_sse = sum（［i［-1］ for i in cluster_info_list］） regular_SSE。append（SSE_list［-1］） bi_SSE。append（bi_sse）
data_compare = pd。DataFrame（{‘ReKmeans’：regular_SSE，‘BiKmeans’：bi_SSE}） data = ［go。Scatter（x = data_compare。index + 1， y = data_compare［i］， mode = ‘lines+markers’， name = i ） for i in data_compare。columns］ layout = go。Layout（title = ‘原始Kmeans與二分Kmeans的SSE穩定性比較’， xaxis = {‘title’ ： ‘次數’}， yaxis = {‘title’ ： ‘SSE值’}， template = ‘plotly_white’ ） fig = go。Figure（data = data， layout = layout）
#fig。show（）
我們這裡隨機的跑30次，來比較最後2個演算法所得到的SSE，我們這裡主要檢視穩定性。可以從圖中看出對於原始的（RegularKmeans）的SSE非常不穩定，而對於BiKmeans來說的話，SSE非常穩定，一直保持在大約95左右。這裡就體現出的BiKmeans的優點，可以很大機率的（不是絕無可能）保證每次隨機生成的2個質心點不會因為太極端而導致其中一個丟失的問題，從而導致最後SSE很高，結果陷入區域性最優的這樣一個問題。
BiKmeans大致中間過程
這裡我們不會像Kmeans中間過程那樣給出詳細的從隨機選取的質心點到收斂的過程。我們這個給出一個大致的BiKmeans中間過程，有助於同學們理解。
