機器學習-聚類演算法-k-均值聚類-python詳解
- 2019 年 11 月 27 日
- 筆記
本文中，演算法實現程式碼筆者自行做了詳細的注釋，別的內容系引用原文：http://blog.csdn.net/zouxy09/article/details/17589329
演算法優缺點：
優點：容易實現 缺點：可能收斂到局部最小值，在大規模數據集上收斂較慢 使用數據類型：數值型數據
演算法思想
k-means演算法實際上就是通過計算不同樣本間的距離來判斷他們的相近關係的，相近的就會放到同一個類別中去。
1.首先我們需要選擇一個k值，也就是我們希望把數據分成多少類，這裡k值的選擇對結果的影響很大，Ng的課說的選擇方法有兩種一種是elbow method，簡單的說就是根據聚類的結果和k的函數關係判斷k為多少的時候效果最好。另一種則是根據具體的需求確定，比如說進行襯衫尺寸的聚類你可能就會考慮分成三類（L,M,S）等
2.然後我們需要選擇最初的聚類點（或者叫質心），這裡的選擇一般是隨機選擇的，程式碼中的是在數據範圍內隨機選擇，另一種是隨機選擇數據中的點。這些點的選擇會很大程度上影響到最終的結果，也就是說運氣不好的話就到局部最小值去了。這裡有兩種處理方法，一種是多次取均值，另一種則是後面的改進演算法（bisecting K-means）
3.終於我們開始進入正題了，接下來我們會把數據集中所有的點都計算下與這些質心的距離，把它們分到離它們質心最近的那一類中去。完成後我們則需要將每個簇算出平均值，用這個點作為新的質心。反覆重複這兩步，直到收斂我們就得到了最終的結果
開發包的導入
本次實踐導入的包有numpy（更強的數值表達和計算能力），matplotlib（主要是用裡面的pyplot，畫圖展示用的），因為針對不同的應用，會用到不同的包，所以強烈建議需要用到python的朋友下一個setuptools工具，安裝完成之後，在cmd（windows）下輸入easy_install ，
基本K均值演算法
############################################################################
1：選擇K個點作為初始質心（實現部分用的是隨機選取質心）
2：repeat
3： 將每個點指派到最近的質心，形成K個簇
4： 重新計算每個簇的質心
5：until 質心不發生改變
######################################################################
數據集合下載
程式碼部分（解析全在注釋里）
from numpy import * import time import matplotlib.pyplot as plt # 計算歐式距離 def euclDistance(vector1, vector2): return sqrt(sum(power(vector2 - vector1, 2))) # 0ρ = sqrt( (x1-x2)^2+(y1-y2)^2 ) |x| = √( x2 + y2 ) # power 對列表計算2次方 求和後開方 # 初始化質心隨機樣本 def initCentroids(dataSet, k): numSamples, dim = dataSet.shape #獲取數據集合的行列總數 centroids = zeros((k, dim)) for i in range(k): index = int(random.uniform(0, numSamples)) # uniform() 方法將隨機生成下一個實數，它在[x,y]範圍內。 centroids[i, :] = dataSet[index, :] return centroids # k-means cluster def kmeans(dataSet, k): numSamples = dataSet.shape[0]#行數 clusterAssment = mat(zeros((numSamples, 2))) # clusterChanged = True #停止循環標誌位 ## step 1: init 初始化k個質點 centroids = initCentroids(dataSet, k) while clusterChanged: clusterChanged = False ## for each 行 for i in xrange(numSamples): minDist = 100000.0 # 設定一個極大值 minIndex = 0 ## for each centroid ## step 2: 尋找最接近的質心 for j in range(k): distance = euclDistance(centroids[j, :], dataSet[i, :]) # 將centroids（k個初始化質心）的j行和dataset（數據全集）的i行 算歐式距離，返回數值型距離 if distance < minDist: # 找距離最近的質點，記錄下來。 minDist = distance minIndex = j ## step 3: update its cluster # 跟新這個簇 if clusterAssment[i, 0] != minIndex: clusterChanged = True # clusterAssment 是一個n行2列的矩陣 Assment 評估 clusterAssment[i, :] = minIndex, minDist**2 #賦值為 新的質點標號 ## step 4: update centroids for j in range(k): # 屬於j這個質點的所有數值的平均值算出成為新的質點 pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]] centroids[j, :] = mean(pointsInCluster, axis = 0) print 'Congratulations, cluster complete!' return centroids, clusterAssment # show your cluster only available with 2-D data def showCluster(dataSet, k, centroids, clusterAssment): numSamples, dim = dataSet.shape if dim != 2: print "Sorry! I can not draw because the dimension of your data is not 2!" return 1 mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr'] if k > len(mark): print "Sorry! Your k is too large! please contact Zouxy" return 1 # 畫出所有樣例點 屬於同一分類的繪製同樣的顏色 for i in xrange(numSamples): markIndex = int(clusterAssment[i, 0]) plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex]) mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb'] #設定顏色 # draw the centroids # 畫出質點，用特殊圖型 for i in range(k): plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12) plt.show() if __name__ == '__main__': ## step 1: 載入數據 print "step 1: load data..." dataSet = [] fileIn = open('./data.txt') for line in fileIn.readlines(): lineArr = line.strip().split(' ') # Python strip() 方法用於移除字元串頭尾指定的字元（默認為空格） # 再按照數據之間的空格作為分隔符。 dataSet.append([float(lineArr[0]), float(lineArr[1])]) # 返回加入到dataset中的每組數據為一個列表。形成二維數組 ## step 2: 開始聚類... print "step 2: clustering..." dataSet = mat(dataSet) # mat 函數，將數組轉化為矩陣 k = 3 centroids, clusterAssment = kmeans(dataSet, k) ## step 3: show the result print "step 3: show the result..." showCluster(dataSet, k, centroids, clusterAssment)
聚類結果：
分別是2,3,4個k值情況下的
四、演算法分析
分析部分來源於 http://blog.csdn.net/zouxy09/article/details/17589329
k-means演算法比較簡單，但也有幾個比較大的缺點：
（1）k值的選擇是用戶指定的，不同的k得到的結果會有挺大的不同，如下圖所示，左邊是k=3的結果，這個就太稀疏了，藍色的那個簇其實是可以再劃分成兩個簇的。而右圖是k=5的結果，可以看到紅色菱形和藍色菱形這兩個簇應該是可以合併成一個簇的：
（2）對k個初始質心的選擇比較敏感，容易陷入局部最小值。例如，我們上面的演算法運行的時候，有可能會得到不同的結果，如下面這兩種情況。K-means也是收斂了，只是收斂到了局部最小值：
（3）存在局限性，如下面這種非球狀的數據分布就搞不定了：
（4）資料庫比較大的時候，收斂會比較慢。
k-means老早就出現在江湖了。所以以上的這些不足也被世人的目光敏銳的捕捉到，並融入世人的智慧進行了某種程度上的改良。例如問題（1）對k的選擇可以先用一些演算法分析數據的分布，如重心和密度等，然後選擇合適的k。而對問題（2），有人提出了另一個成為二分k均值（bisecting k-means）演算法，它對初始的k個質心的選擇就不太敏感，這個演算法我們下一個博文再分析和實現。
原創文章，轉載請註明： 轉載自URl-team
本文鏈接地址: 機器學習-聚類演算法-k-均值聚類-python詳解
No related posts.
