為克服k均值算法收斂於局部最小值的問題，有人提出了另一個稱為二分k均值（bisecting Ｋ-means）的算法。該算法首先將所有點作為一個簇，然後將該簇一分為二。之後選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決於對其劃分是否可以最大程度降低SSE的值。上述基於SSE的劃分過程不斷重複，直到得到用戶指定的簇數目為止。
二分k均值算法的偽代碼形式如下：
將所有點看成一個簇
當簇數目小於k時
對於每一個簇
計算總誤差
在給定的簇上面進行K均值聚類（K=2）
計算將該簇一分為二之後的總誤差
選擇使得誤差最小的那個簇進行劃分操作
另一種做法是選擇SSE最大的簇進行劃分，直到簇數目達到用戶指定的數目為止。這個做法聽起來並不難實現。下面就來看一下該算法的實際效果。打開kMeans.py文件然後加入下面程序清單中的代碼。
程序清單10-3 二分K均值聚類算法
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2)))
#❶（以下兩行）創建一個初始簇
centroid0 = mean(dataSet, axis=0).tolist[0]
centList =[centroid0]
for j in range(m):
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
while (len(centList) < k):
lowestSSE = inf
for i in range(len(centList)):
#❷（以下兩行）嘗試劃分每一簇
ptsInCurrCluster =dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2 , distMeas)
sseSplit = sum(splitClustAss[:,1])
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
print \"sseSplit, and notSplit: \",sseSplit,sseNotSplit
if (sseSplit + sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy
lowestSSE = sseSplit + sseNotSplit
#❸（以下兩行）更新簇的分配結果
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] =len(centList)
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] =bestCentToSplit
print \'the bestCentToSplit is: \',bestCentToSplit
print \'the len of bestClustAss is: \', len(bestClustAss)
centList[bestCentToSplit] = bestNewCents[0,:]
centList.append(bestNewCents[1,:])
clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss
return mat(centList), clusterAssment
上述程序中的函數與程序清單10-2中函數kMeans的參數相同。在給定數據集、所期望的簇數目和距離計算方法的條件下，函數返回聚類結果。同kMeans一樣，用戶可以改變所使用的距離計算方法。
該函數首先創建一個矩陣來存儲數據集中每個點的簇分配結果及平方誤差，然後計算整個數據集的質心，並使用一個列表來保留所有的質心❶。得到上述質心之後，可以遍歷數據集中所有點來計算每個點到質心的誤差值。這些誤差值將會在後面用到。
接下來程序進入while循環，該循環會不停對簇進行劃分，直到得到想要的簇數目為止。可以通過考察簇列表中的值來獲得當前簇的數目。然後遍歷所有的簇來決定最佳的簇進行劃分。為此需要比較劃分前後的SSE。一開始將最小SSE置設為無窮大，然後遍歷簇列表centList中的每一個簇。對每個簇，將該簇中的所有點看成一個小的數據集ptsInCurrCluster。將ptsInCurrCluster輸入到函數kMeans中進行處理（Ｋ = 2）。k均值算法會生成兩個質心（簇），同時給出每個簇的誤差值❷。這些誤差與剩餘數據集的誤差之和作為本次劃分的誤差。如果該劃分的SSE值最小，則本次劃分被保存。一旦決定了要劃分的簇，接下來就要實際執行劃分操作。劃分操作很容易，只需要將要劃分的簇中所有點的簇分配結果進行修改即可。當使用kMeans函數並且指定簇數為2時，會得到兩個編號分別為0和1的結果簇。需要將這些簇編號修改為劃分簇及新加簇的編號，該過程可以通過兩個數組過濾器來完成❸。最後，新的簇分配結果被更新，新的質心會被添加到centList中。
當while循環結束時，同kMeans函數一樣，函數返回質心列表與簇分配結果。
下面看一下實際運行效果。將程序清單10-3中的代碼添加到文件kMeans.py並保存，然後在Python提示符下輸入：
>>> reload(kMeans)
<module \'kMeans\' from \'kMeans.py\'>
可以在最早的數據集上運行上述過程，也可以通過如下命令來導入圖10-2中那個「較難」的數據集：
>>> datMat3=mat(kMeans.loadDataSet(\'testSet2.txt\'))
要運行函數biKmeans，輸入如下命令：
>>> centList,myNewAssments=kMeans.biKmeans(datMat3,3) sseSplit, and notSplit: 491.233299302 0.0 the bestCentToSplit is: 0 the len of bestClustAss is: 60 sseSplit, and notSplit: 75.5010709203 35.9286648164 sseSplit, and notSplit: 21.40716341 455.304634485 the bestCentToSplit is: 0 the len of bestClustAss is: 40
現在看看質心結果：
>>> centList
[matrix([[-3.05126255, 3.2361123 ]]), matrix([[-0.28226155, -2.4449763 ]]),
matrix([[ 3.1084241, 3.0396009]])]
上述函數可以運行多次，聚類會收斂到全局最小值，而原始的kMeans函數偶爾會陷入局部最小值。圖10-3給出了數據集及運行biKmeans後的的質心的示意圖。
圖10-3 運行二分K均值算法後的簇分配示意圖，該算法總是產生較好的聚類結果
前面已經運行了二分K均值算法，下面將該算法應用於一些真實的數據集上。下一節將利用地圖上的地理位置坐標進行聚類。