程式扎記: [ ML In Action ] Unsupervised learning : The k-means clustering algorithm (2)

標籤

2013年4月8日 星期一

[ ML In Action ] Unsupervised learning : The k-means clustering algorithm (2)

Preface: 
在前面介紹 k-means clustering algorithm 時, 眼尖的你應該會發現 cluster 的數目是由 k 決定. 問題是我們怎麼知道 k 值是什麼? 另外使用 k-means clustering algorithm 有個問題就是它得到的是 local optimal, 也就是每次跑的結果可能都不一樣 (因為 centroid 是 random 決定) . 下面的圖是一個已經完成 k-means clustering algorithm 的結果, 但是透過你肉眼就可以發現它並非最佳的結果 global optimal : 
 

而有一種可以量測你 clustering output 的結果好壞稱為 SSE (sum of squared error), 也就是計算每個 cluster 的每一個 instance 到 該 cluster centroid 的距離的和. 照理說該值如果越小, 說明該 cluster 的密度越高, 也就越好. 那這樣說如果我取多一點 cluster (k 值越大), 不就密度越高越好嗎? 事實上魚與熊掌不可兼得, 你總是需要在密度與 cluster 數目間做取捨. 因為 cluster 越多則 cluster 間的區別度便會變小, 而造成無法將某些預期的結果區分開來. 

為了解決上圖的問題, 我們要介紹另一種 k-means clustering 的 方法. 它會設一個 threshold, 當某個 cluster 的 SSE 大於這個 threshold 時 (說明該 cluster 密度過大), 則將屬於該 cluster 的所有 instance 再跑一次 k-means, 但是這次設定 k=2. 如此 cluster 的數量必定會增加, 因次就需要一些做法來 merging clustering. 

Bisecting k-means: 
為了解決上面提到的應為 local optimal 造成 poor 的 clustering result, 這邊提出另一個方法 bisecting k-means: 它一開始使用一個 cluster, 接著 split 成 2 個 clusters; 再接著根據以降低 global SSE 值為目標挑選 cluster 繼續 split 直到達到預期的 cluster 數目. 底下是該 algorithm 的 pseudo code: 
  1. Start with all the points in one cluster  
  2. While the number of clusters is less than k  
  3.     for every cluster  
  4.         measure total error  
  5.         perform k-means clustering with k=2 on the given cluster  
  6.         measure total error after k-means has split the cluster in two  
  7.     choose the cluster split that gives the lowest error and commit this split  
接著底下是實作的代碼: 
  1. def biKmeans(dataSet, k, distMeas=distEclud):  
  2.     m = shape(dataSet)[0]  
  3.     clusterAssment = mat(zeros((m,2)))  
  4.     centroid0 = mean(dataSet, axis=0).tolist()[0]  
  5.     centList =[centroid0] #create a list with one centroid  
  6.     for j in range(m): # calc initial Error  
  7.         clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2  
  8.     while (len(centList) < k):  
  9.         lowestSSE = inf  
  10.         for i in range(len(centList)): # Search the best group to do k-means with best/smallest SSE.  
  11.             ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] #get the data points currently in cluster i  
  12.             centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)  
  13.             sseSplit = sum(splitClustAss[:,1]) # compare the SSE to the SSE of currrent split   
  14.             sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) # compare the SSE of instances except ones in cluster i  
  15.             print "sseSplit, and notSplit: ",sseSplit,sseNotSplit  
  16.             if (sseSplit + sseNotSplit) < lowestSSE:  
  17.                 bestCentToSplit = i  
  18.                 bestNewCents = centroidMat  
  19.                 bestClustAss = splitClustAss.copy()  
  20.                 lowestSSE = sseSplit + sseNotSplit  
  21.         bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) # Increase the cluster index  
  22.         bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit  
  23.         print 'the bestCentToSplit is: ',bestCentToSplit  
  24.         print 'the len of bestClustAss is: ', len(bestClustAss)  
  25.         centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0] # replace a centroid with two best centroids   
  26.         centList.append(bestNewCents[1,:].tolist()[0])  
  27.         clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss #reassign new clusters, and SSE  
  28.     return mat(centList), clusterAssment  
Experiment: 
接著你可以如下來使用上面的代碼: 
>>> import kMeans # 剛剛的代碼存放在 kMeans.py, 這邊載入 kMeans module
>>> from numpy import * # 載入 numpy 模組
>>> datMat3 = mat(kMeans.loadDataSet('testSet2.txt')) # 載入 test data set
>>> centList, myNewAssments=kMeans.biKmeans(datMat3, 3) # 執行 bisecting k-means, 切割成 3 個 clusters
>>> centList # 列印出 3 個 cluster 的 centroid
matrix([[-0.45965615, -2.7782156 ],
[ 2.93386365, 3.12782785],
[-2.94737575, 3.3263781 ]])

接著你可以使用下面代碼顯示 test data set 的分佈: 
>>> import matplotlib.pyplot as plt
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> ax.scatter(x=array(datMat3[:,0]).flatten(), y=array(datMat3[:,1]).flatten())

>>> plt.show()

 

或者你可以使用下面代碼將 Centroid 與 每個 Cluster 的 instance 以不同顏色標示出來: 
  1. #-*- coding: utf-8 -*-      
  2. from numpy import *    
  3. import matplotlib.pyplot as plt    
  4. import kMeans    
  5.     
  6. 1) Execute the k-means cluster algorithm    
  7. k = 3 # How many clusters?    
  8. datMat3 = mat(kMeans.loadDataSet('testSet2.txt'))    
  9. rst = kMeans.biKmeans(datMat3,k)    
  10.     
  11. 2) Output the centroid    
  12. fig = plt.figure()    
  13. ax = fig.add_subplot(111)    
  14. ax.scatter(x=array(rst[0][:,0]).flatten(), y=array(rst[0][:,1]).flatten(), c='pink', s=80)    
  15.     
  16. 3) Output the dataset with different according to its cluster.    
  17. color = ['red''blue''green''yellow']    
  18. for i in range(k):    
  19.     smc = datMat3[nonzero(rst[1][:,0].A==i)[0]] # sub data set of each cluster.    
  20.     ax.scatter(x=array(smc[:,0]).flatten(), y=array(smc[:,1]).flatten(), c=color[i], s=30)    
  21. plt.show()   
執行結果: 

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!