《機器學習實戰》學習總結（十）——K-均值聚類（k-Means）

摘要

1.k-均值聚類

2.二分k-均值聚類

3.代碼實現與注釋

k-均值聚類

首先說一下什麼叫無監督學習。我們之前所講的分類問題也好，回歸問題也好，其樣本的真實標記都是已經告訴我們的。但是無監督學習其訓練樣本並沒有標記信息。

k-均值分類是無監督學習的一種，它想把給定數據劃分為k類，這裡的k是我們給定的參數。

k均值分類的工作流程是這樣的：首先隨機確定k個初始值作為質心，之後計算每個樣本點到k個質心的距離，將樣本分配給距離其最近的質心。這一步完成後，將k個類的質心更新為該類所有點的平均值。重複上述步驟，直到更新後聚類的結果不變。

其偽代碼如下：

一般情況下，距離的度量我們可以用歐式距離：

二分k-均值聚類

k-均值聚類有時會收斂於局部最小值，如下圖所示：

「+」代表分類中心，我們可以看到其分類的效果並不好，說明k-均值分類並沒有讓其收斂到全局最小值。

為了解決這個問題，發明了二分k-均值分類演算法。

該演算法首先將所有樣本點作為一個簇，然後將該簇一分為二。之後選擇其中一個簇繼續劃分，選擇哪一個簇進行劃分取決於對其劃分是否可以最大程度降低樣本到質心的距離之和。劃分完之後，這時已經將樣本劃分為了3簇，之後再選擇一個簇繼續劃分。不斷重複上述過程，直到簇數目的數量到達k個。

以上就是k-均值演算法的全部原理部分，這個演算法不難，希望能給大家幫助。下面是代碼實現。

代碼實現與注釋

1.k-均值聚類函數

程序清單：

from numpy import *# K均值聚類支持函數# 數據載入def loadDataSet(fileName): dataMat=[] fr=open(fileName) for line in fr.readlines(): curLine=line.strip().split( ) fltLine=list(map(float,curLine)) dataMat.append(fltLine) return dataMat# 計算兩個向量的距離def distEclud(vecA,vecB): return sqrt(sum(power(vecA-vecB,2)))# 創建初始隨機質點def randCent(dataSet,k): n=shape(dataSet)[1] centroids=mat(zeros((k,n))) for j in range(n): minJ=min(dataSet[:,j]) rangeJ=float(max(dataSet[:,j]-minJ)) # 注意random.rand(k,1)返回的是k*1，數值在（0，1）之間的隨機數 centroids[:,j]=minJ+rangeJ*random.rand(k,1) return centroids# k均值聚類演算法def kMeans(dataSet,k,distMeans=distEclud,createCent=randCent): m=shape(dataSet)[0] # 第一列存儲簇索引值，第二列存儲誤差 clusterAssment=mat(zeros((m,2))) # 初始化質心位置 cenrtroids=createCent(dataSet,k) # 標誌位 clusterChanged=True while(clusterChanged): clusterChanged=False # 對每一個樣本 for i in range(m): # 初始化最小距離為無窮大，索引值為-1 minDist=inf;minIndex=-1 # 對每一個分類中心 for j in range(k): # 計算距離 distJI=distMeans(cenrtroids[j,:],dataSet[i,:]) # 找到距離樣本最近的分類中心 if(distJI<minDist): minDist=distJI;minIndex=j if(clusterAssment[i,0]!=minIndex): clusterChanged=True # 更新樣本索引值和距離 clusterAssment[i,:]=minIndex,minDist**2 print(cenrtroids) # 更新質心位置 for cent in range(k): ptsInclust=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] cenrtroids[cent,:]=mean(ptsInclust,axis=0) return cenrtroids,clusterAssment

2.二分k-均值聚類

程序清單：

# 二分K均值聚類演算法def biKmeans(dataSet,k,disMeas=distEclud): m=shape(dataSet)[0] # 存儲每個樣本點的簇分配結果和平方誤差 clusterAssment=mat(zeros((m,2))) # 初始化質心 centroid0=mean(dataSet,axis=0).tolist()[0] # centList列表中保留質心的位置 centList=[centroid0] # 計算樣本中所有點到質心的誤差值 for j in range(m): clusterAssment[j,1]=disMeas(centroid0,dataSet[j,:])**2 while(len(centList)<k): lowestSSE=inf # 遍歷所有的簇 for i in range(len(centList)): # 將簇類為i的點放到ptsIncurrCluster中 ptsIncurrCluster=dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] # 返回2分類的結果 centroidMat,splitClustAss=kMeans(ptsIncurrCluster,2,disMeas) # 返回分類後的誤差和 sseSplit=sum(splitClustAss[:,1]) # 得到剩餘沒劃分的誤差之和 sseNotSplit=sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) print("sseSplit,and :",sseSplit,sseNotSplit) # 如果以i類二分之後的誤差之後小於最小誤差 if((sseSplit+sseNotSplit)<lowestSSE): # 最好的劃分簇為i bestCentToSplit=i # 新的質心 bestNewCents=centroidMat bestClustAss=splitClustAss.copy() # 更新簇的分配結果 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

以上就是k-均值演算法的全部內容，下一節我們一起學習概率圖模型。

聲明

最後，所有資料均本人自學整理所得，如有錯誤，歡迎指正，有什麼建議也歡迎交流，讓我們共同進步！轉載請註明作者與出處

以上原理部分主要來自於《機器學習》—周志華，《統計學習方法》—李航，《機器學習實戰》—Peter Harrington。代碼部分主要來自於《機器學習實戰》，我對代碼進行了版本的改進，文中代碼用Python3實現，這是機器學習主流語言，本人也會儘力對代碼做出較為詳盡的注釋。