=====================================================================
《機器學習實戰》系列部落格是部落客閱讀《機器學習實戰》這本書的筆記也包含一些其他python實作的機器學習算法 算法實作均采用python
github 源碼同步：https://github.com/Thinkgamer/Machine-Learning-With-Python
=====================================================================
Scikit-learn 實作的K-Means 算法請參考 ： 點選閱讀
K-Means 均值算法請參考：點選閱讀
首先二分-K均值是為了解決k-均值的使用者自定義輸入簇值k所延伸出來的自己判斷k數目，其基本思路是：
為了得到k個簇，将所有點的集合分裂成兩個簇，從這些簇中選取一個繼續分裂，如此下去，直到産生k個簇。
僞代碼：
初始化簇表，使之包含由所有的點組成的簇。
repeat
從簇表中取出一個簇。
{對標明的簇進行多次二分試驗}
for i=1 to 試驗次數 do
使用基本k均值，二分標明的簇。
endfor
從二分試驗中選擇具有最小誤差的兩個簇。
将這兩個簇添加到簇表中。
until 簇表中包含k個簇
比如要分成5個組，第一次分裂産生2個組，然後從這2個組中選一個目标函數産生的誤差比較大的，分裂這個組産生2個，這樣加上開始那1個就有3個組了，然後再從這3個組裡選一個分裂，産生4個組，重複此過程，産生5個組。這算是一中基本求精的思想。二分k均值不太受初始化的困擾，因為它執行了多次二分試驗并選取具有最小誤差的試驗結果，還因為每步隻有兩個質心。
優點與缺點
k均值簡單并且可以用于各種資料類型，它相當有效，盡管常常多次運作。然後k均值并不适合所有的資料類型。它不能處理非球形簇，不同尺寸和不同密度的簇。對包含離群點（噪聲點）的資料進行聚類時，k均值也有問題。
其實作的Python代碼如下：
#encoding:utf-8
from numpy import *
def loadDataSet(filename):
dataMat = [] #建立元祖
fr = open(filename)
for line in fr.readlines():
curLine = line.strip().split("\t")
fltLine = map(float,curLine) #使用map函數将curLine裡的數全部轉換為float型
dataMat.append(fltLine)
return dataMat
def distEclud(vecA,vecB): #計算兩個向量的歐式距離
return sqrt(sum(power(vecA-vecB,2)))
def randCent(dataSet,k): #位給定資料集建構一個包含k個随機質心的集合
n = shape(dataSet)[1] #shape函數此時傳回的是dataSet元祖的列數
centroids = mat(zeros((k,n))) #mat函數建立k行n列的矩陣，centroids存放簇中心
for j in range(n):
minJ = min(dataSet[:,j]) #第j列的最小值
rangeJ = float(max(dataSet[:,j]) - minJ)
centroids[:,j] = minJ + rangeJ * random.rand(k,1) #random.rand(k,1)産生shape(k,1)的矩陣
return centroids
def kMeans(dataSet,k,disMeas = distEclud,createCent = randCent):
m = shape(dataSet)[0] #shape函數此時傳回的是dataSet元祖的行數
clusterAssment = mat(zeros((m,2))) #建立一個m行2列的矩陣，第一列存放索引值，第二列存放誤差，誤差用來評價聚類效果
centroids = createCent(dataSet,k) #建立k個質心，調用createCent()函數
clusterChanged =True #标志變量，若為true則繼續疊代
print "質心位置更新過程變化："
while clusterChanged:
clusterChanged = False
for i in range(m):
minDist = inf #inf為正無窮大
minIndex = -1 #建立索引
for j in range(k):
#尋找最近的質心
disJI = disMeas(centroids[j,:],dataSet[i,:]) #計算每個點到質心的歐氏距離
if disJI(array([0, 0, 1]), array([0, 2, 0]))
#print array(nonzero(b2))
#=>[[0, 0, 1],[0, 2, 0]]
centroids[cent,:] = mean(ptsInClust,axis=0) #計算所有點的均值，選項axis=0表示沿矩陣的列方向進行均值計算
return centroids,clusterAssment #傳回所有的類質心與點配置設定結果
def bikMeans(dataSet,k,disMeas = distEclud):
m = shape(dataSet)[0] #shape函數此時傳回的是dataSet元祖的行數
clusterAssment = mat(zeros((m,2))) #建立一個m行2列的矩陣，第一列存放索引值，第二列存放誤差，誤差用來評價聚類效果
#建立一個初始簇
centroid0 = mean(dataSet,axis=0).tolist()[0]
centList = [centroid0]
print centList
print len(centList)
for j in range(m):
clusterAssment[j,1] = disMeas(mat(centroid0),dataSet[j,:])**2 #計算所有點的均值，選項axis=0表示沿矩陣的列方向進行均值計算
while (len(centList)<k):
lowestSSE = inf #inf正無窮大
for i in range(len(centList)):
#嘗試劃分每一簇
ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
centroidMat,splitClustAss = kMeans(ptsInCurrCluster,2,disMeas)
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 centList,clusterAssment
#return mat(centList),clusterAssment
datMat = mat(loadDataSet('data.txt'))
myCentList,myNewAssment = bikMeans(datMat,2)
print "最終質心：\n",myCentList
print "索引值和均值：\n",myNewAssment
掃一掃 關注微信公衆号！号主 專注于搜尋和推薦系統，嘗試使用算法去更好的服務于使用者，包括但不局限于機器學習，深度學習，強化學習，自然語言了解，知識圖譜，還不定時分享技術，資料，思考等文章！
【技術服務】，詳情點選檢視：https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg
