一步步教你轻松学K-means聚类算法
(白寧超 ??2018年9月13日09:10:33)
導讀：k-均值算法（英文：k-means clustering），屬于比較常用的算法之一，文本首先介紹聚類的理論知識包括什么是聚類、聚類的應用、聚類思想、聚類優缺點等等；然后通過k-均值聚類案例實現及其可視化有一個直觀的感受，針對算法模型進行分析和結果優化提出了二分k-means算法。最后我們調用機器學習庫函數，很短的代碼完成聚類算法。（本文原創，轉載必須注明出處： 一步步教你輕松學K-means聚類算法
目錄
1?機器學習：一步步教你輕松學KNN模型算法
2?機器學習：一步步教你輕松學決策樹算法
3?機器學習：一步步教你輕松學樸素貝葉斯模型算法理論篇1?
4?機器學習：一步步教你輕松學樸素貝葉斯模型實現篇2?
5?機器學習：一步步教你輕松學樸素貝葉斯模型算法Sklearn深度篇3
6?機器學習：一步步教你輕松學邏輯回歸模型算法
7?機器學習：一步步教你輕松學K-means聚類算法
8?機器學習：一步步教你輕松學關聯規則Apriori算法
9?機器學習：?一步步教你輕松學支持向量機SVM算法之理論篇1
10?機器學習： 一步步教你輕松學支持向量機SVM算法之案例篇2
11?機器學習： 一步步教你輕松學主成分分析PCA降維算法
12?機器學習：?一步步教你輕松學支持向量機SVM降維算法
更多文章請點擊這里>>
理論介紹
聚類
什么是聚類
統計數據分析的一門技術，在許多領域受到廣泛應用，包括機器學習，數據挖掘，模式識別，圖像分析以及生物信息。聚類是把相似的對象通過靜態分類的方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐標系中更加短的空間距離等。
聚類的應用
在商務上，聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。在生物學上，聚類能用于推導植物和動物的分類，對基因進行分類，獲得對種群中固有結構的認識。聚類在地球觀測數據庫中相似地區的確定，汽車保險單持有者的分組，及根據房子的類型、價值和地理位置對一個城市中房屋的分組上也可以發揮作用。聚類也能用于對Web上的文檔進行分類，以發現信息。諸如此類，聚類有著廣泛的實際應用。
K-means（k均值）聚類算法
什么是k-means聚類算法
k-平均算法（英文：k-means clustering）源于信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行于數據挖掘領域。k-平均聚類的目的是：把 n個點劃分到k個聚類中，使得每個點都屬于離他最近的均值（此即聚類中心）對應的聚類，以之作為聚類的標準。k-平均聚類與k-近鄰之間沒有任何關系（后者是另一流行的機器學習技術）。
K-Means 是發現給定數據集的 K 個簇的聚類算法, 之所以稱之為 K-均值 是因為它可以發現 K 個不同的簇, 且每個簇的中心采用簇中所含值的均值計算而成.簇個數 K 是用戶指定的, 每一個簇通過其質心（centroid）, 即簇中所有點的中心來描述.
聚類與分類算法的最大區別在于, 分類的目標類別已知, 而聚類的目標類別是未知的.
發展歷史
雖然其思想能夠追溯到1957年的Hugo Steinhaus，術語“k-均值”于1967年才被James MacQueen 首次使用。標準算法則是在1957年被Stuart Lloyd作為一種脈沖碼調制的技術所提出，但直到1982年才被貝爾實驗室公開出版。在1965年，E.W.Forgy發表了本質上相同的方法，所以這一算法有時被稱為Lloyd-Forgy方法。更高效的版本則被Hartigan and Wong提出。
算法描述
已知觀測集，其中每個觀測都是一個 d-維實向量，k-平均聚類要把這 n個觀測劃分到k個集合中(k≤n),使得組內平方和最小。換句話說，它的目標是找到使得下式滿足的聚類，
其中 是 中所有點的均值。
k-means術語
- 簇: 所有數據的點集合，簇中的對象是相似的。
- 質心: 簇中所有點的中心（計算所有點的均值而來）.
- SSE: Sum of Sqared Error（誤差平方和）, 它被用來評估模型的好壞，SSE 值越小，表示越接近它們的質心. 聚類效果越 好。由于對誤差取了平方，因此更加注重那些遠離中心的點（一般為邊界點或離群點）。詳情見kmeans的評價標準。
有關 簇 和 質心 術語更形象的介紹, 請參考下圖:
k-means應用場景
kmeans，用于數據集內種類屬性不明晰，希望能夠通過數據挖掘出或自動歸類出有相似特點的對象的場景。其商業界的應用場景一般為挖掘出具有相似特點的潛在客戶群體以便公司能夠重點研究、對癥下藥。
例如，在2000年和2004年的美國總統大選中，候選人的得票數比較接近或者說非常接近。任一候選人得到的普選票數的最大百分比為50.7%而最小百分比為47.9% 如果1%的選民將手中的選票投向另外的候選人，那么選舉結果就會截然不同。 實際上，如果妥善加以引導與吸引，少部分選民就會轉換立場。盡管這類選舉者占的比例較低，但當候選人的選票接近時，這些人的立場無疑會對選舉結果產生非常大的影響。如何找出這類選民，以及如何在有限的預算下采取措施來吸引他們？ 答案就是聚類（Clustering)。
那么，具體如何實施呢？首先，收集用戶的信息，可以同時收集用戶滿意或不滿意的信息，這是因為任何對用戶重要的內容都可能影響用戶的投票結果。然后，將這些信息輸入到某個聚類算法中。接著，對聚類結果中的每一個簇（最好選擇最大簇 ）， 精心構造能夠吸引該簇選民的消息。最后， 開展競選活動并觀察上述做法是否有效。
另一個例子就是產品部門的市場調研了。為了更好的了解自己的用戶，產品部門可以采用聚類的方法得到不同特征的用戶群體，然后針對不同的用戶群體可以對癥下藥，為他們提供更加精準有效的服務。
k-means算法思想
先隨機選取K個對象作為初始的聚類中心。然后計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。一旦全部對象都被分配了，每個聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是以下任何一個：
- 沒有（或最小數目）對象被重新分配給不同的聚類。
- 沒有（或最小數目）聚類中心再發生變化。
- 誤差平方和局部最小。
得到相互分離的球狀聚類，在這些聚類中，均值點趨向收斂于聚類中心。 一般會希望得到的聚類大小大致相當，這樣把每個觀測都分配到離它最近的聚類中心（即均值點）就是比較正確的分配方案。
k-means工作流程
創建 k 個點作為起始質心（通常是隨機選擇） 當任意一個點的簇分配結果發生改變時（不改變時算法結束）對數據集中的每個數據點對每個質心計算質心與數據點之間的距離將數據點分配到距其最近的簇對每一個簇, 計算簇中所有點的均值并將均值作為質心k-means開發流程
收集數據：使用任意方法 準備數據：需要數值型數據類計算距離, 也可以將標稱型數據映射為二值型數據再用于距離計算 分析數據：使用任意方法 訓練算法：不適用于無監督學習，即無監督學習不需要訓練步驟 測試算法：應用聚類算法、觀察結果.可以使用量化的誤差指標如誤差平方和（后面會介紹）來評價算法的結果. 使用算法：可以用于所希望的任何應用.通常情況下, 簇質心可以代表整個簇的數據來做出決策.k-means評價標準
k-means算法因為手動選取k值和初始化隨機質心的緣故，每一次的結果不會完全一樣，而且由于手動選取k值，我們需要知道我們選取的k值是否合理，聚類效果好不好，那么如何來評價某一次的聚類效果呢？也許將它們畫在圖上直接觀察是最好的辦法，但現實是，我們的數據不會僅僅只有兩個特征，一般來說都有十幾個特征，而觀察十幾維的空間對我們來說是一個無法完成的任務。因此，我們需要一個公式來幫助我們判斷聚類的性能，這個公式就是SSE (Sum of Squared Error, 誤差平方和 ），它其實就是每一個點到其簇內質心的距離的平方值的總和，這個數值對應kmeans函數中clusterAssment矩陣的第一列之和。 SSE值越小表示數據點越接近于它們的質心，聚類效果也越好。 因為對誤差取了平方，因此更加重視那些遠離中心的點。一種肯定可以降低SSE值的方法是增加簇的個數，但這違背了聚類的目標。聚類的目標是在保持簇數目不變的情況下提高簇的質量。
k-means優缺點
-
優點:
屬于無監督學習，無須準備訓練集
原理簡單，實現起來較為容易
結果可解釋性較好 -
缺點:
聚類數目k是一個輸入參數。選擇不恰當的k值可能會導致糟糕的聚類結果。這也是為什么要進行特征檢查來決定數據集的聚類數目了。
可能收斂到局部最小值, 在大規模數據集上收斂較慢
對于異常點、離群點敏感
使用數據類型 : 數值型數據
k-means聚類算法實現
案例描述
我們假設這樣的一個案例需求：某公司發布一批新型手機，根據客戶熱衷度進行投放。公司市場人員收集其中四個地區用戶對手機的滿意程度（由兩個特征決定的）。分析哪個區域對手機產品比較熱衷，對應的進行市場銷售工作。這里就用到k-means聚類算法。
從文件加載數據集
上文中我們收集好四個地區用戶對產品滿意的特征數據值，轉化為向量預先保存到文本中（關于詞向量轉化及其詞袋模型問題，參考：決策樹算法模型研究與案例分析一文）。我們加載文件并以數據矩陣形式返回數據集，代碼實現如下：
'''加載數據集''' def loadDataSet(fileName):dataSet = [] # 初始化一個空列表fr = open(fileName)for line in fr.readlines():# 切割每一行的數據curLine = line.strip().split('\t')# 將數據追加到dataMat，映射所有的元素為 float類型fltLine = list(map(float,curLine)) dataSet.append(fltLine)return mat(dataSet)我們打印看下結果：
計算兩個向量的歐氏距離
上文在k均值算法思想和工作流程都提到過，我們一個重要的方法就是隨機設置質心，然后比較每條數據（可以理解為單一客戶的特征數據）與質心之間的距離。這里距離公式包括很多，本文采用的是歐式距離計算，其代碼實現如下：
'''歐氏距離計算函數''' def distEclud(vecA, vecB):return sqrt(sum(power(vecA - vecB, 2)))構建一個包含 K 個隨機質心的集合
接下來，我們構建隨機質心（中心點），這里的K值是經過數據觀察隨機設置的值，假如k=3，代表我們將數據集分為3個簇，也就是說分為3個部分。我們隨機質心在整個數據集的邊界之內，這可以通過找到數據集每一維的最小和最大值來完成,然后生成0到1.0之間的隨機數并通過取值范圍和最小值,以便確保隨機點在數據的邊界之內
'''
隨機質心
'''
def randCent(dataMat, k):
我們測試下k=3的隨機質心結果：
K-Means 聚類算法
我們基于以上算法構建k均值算法，該算法會創建k個質心，然后將每個點分配到最近的質心，再重新計算質心。這個過程重復數次，直到數據點的簇分配結果不再改變位置。返回類質心與點分配結果（多次運行結果可能會不一樣，可以試試，原因為隨機質心的影響，但總的結果是對的，因為數據足夠相似，也可能會陷入局部最小值），代碼實現如下：
''' 創建K個質心,然后將每個點分配到最近的質心,再重新計算質心。 這個過程重復數次,直到數據點的簇分配結果不再改變為止 ''' def kMeans(dataMat, k, distMeas=distEclud, createCent=randCent):# 獲取樣本數和特征數m, n = shape(dataMat)# 初始化一個矩陣來存儲每個點的簇分配結果# clusterAssment包含兩個列:一列記錄簇索引值,第二列存儲誤差(誤差是指當前點到簇質心的距離,后面會使用該誤差來評價聚類的效果)clusterAssment = mat(zeros((m, 2)))# 創建質心,隨機K個質心centroids = createCent(dataMat, k)# 初始化標志變量,用于判斷迭代是否繼續,如果True,則繼續迭代clusterChanged = Truewhile clusterChanged:clusterChanged = False# 遍歷所有數據找到距離每個點最近的質心,# 可以通過對每個點遍歷所有質心并計算點到每個質心的距離來完成for i in range(m):minDist = inf # 正無窮minIndex = -1for j in range(k):# 計算數據點到質心的距離# 計算距離是使用distMeas參數給出的距離公式,默認距離函數是distEcluddistJI = distMeas(centroids[j, :], dataMat[i, :])# 如果距離比minDist(最小距離)還小,更新minDist(最小距離)和最小質心的index(索引)if distJI < minDist:minDist = distJIminIndex = j# 如果任一點的簇分配結果發生改變,則更新clusterChanged標志if clusterAssment[i, 0] != minIndex:# print(clusterAssment[i, 0],minIndex)clusterChanged = True# 更新簇分配結果為最小質心的index(索引),minDist(最小距離)的平方clusterAssment[i, :] = minIndex, minDist ** 2# print(centroids)# 遍歷所有質心并更新它們的取值for cent in range(k):# 通過數據過濾來獲得給定簇的所有點ptsInClust = dataMat[nonzero(clusterAssment[:, 0].A == cent)[0]]# 計算所有點的均值,axis=0表示沿矩陣的列方向進行均值計算centroids[cent, :] = mean(ptsInClust, axis=0)# axis=0列方向# 返回所有的類質心與點分配結果return centroids, clusterAssment測試查看下運行結果：
分析數據：聚類可視化
通過上文返回的數據結果，似乎我們還不能直觀感受，接下來我們采用可視化分析方法直觀感受下，代碼實現如下：
''' 可視化展示 ''' def kmeanShow(dataMat,centers,clusterAssment):plt.scatter(np.array(dataMat)[:, 0], np.array(dataMat)[:, 1], c=np.array(clusterAssment)[:, 0].T)plt.scatter(centers[:, 0].tolist(), centers[:, 1].tolist(), c="r")plt.show()測試查看可視化結果：
結果討論與分析
局部最小值（局部最優的結果，但不是全局最優的結果）
上文可視化結果顯示，其中兩個簇聚集在一起，也就說說沒有達到我們預期的效果。出現這個問題有很多原因，可能是k值取的不合適，可能是距離函數不合適，可能是最初隨機選取的質心靠的太近，也可能是數據本身分布的問題。
為了解決這個問題，我們可以對生成的簇進行后處理，一種方法是將具有最大SSE值的簇劃分成兩個簇。具體實現時可以將最大簇包含的點過濾出來并在這些點上運行K-均值算法，令k設為2。
為了保持簇總數不變，可以將某兩個簇進行合并。從上圖中很明顯就可以看出，應該將上圖下部兩個出錯的簇質心進行合并。那么問題來了，我們可以很容易對二維數據上的聚類進行可視化， 但是如果遇到40維的數據應該如何去做？
有兩種可以量化的辦法：合并最近的質心，或者合并兩個使得SSE增幅最小的質心。 第一種思路通過計算所有質心之間的距離， 然后合并距離最近的兩個點來實現。第二種方法需要合并兩個簇然后計算總SSE值。必須在所有可能的兩個簇上重復上述處理過程，直到找到合并最佳的兩個簇為止。
因為上述后處理過程實在是有些繁瑣，所以有更厲害的大佬提出了另一個稱之為二分K-均值（bisecting K-Means）的算法.
二分 K-Means 聚類算法
算法描述
該算法首先將所有點作為一個簇，然后將該簇一分為二。之后選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決于對其劃分時候可以最大程度降低 SSE（平方和誤差）的值。上述基于 SSE 的劃分過程不斷重復，直到得到用戶指定的簇數目為止。
二分 K-Means 聚類算法偽代碼
將所有點看成一個簇 當簇數目小于 k 時 對于每一個簇計算總誤差在給定的簇上面進行 KMeans 聚類（k=2）計算將該簇一分為二之后的總誤差 選擇使得誤差最小的那個簇進行劃分操作另一種做法是選擇 SSE 最大的簇進行劃分，直到簇數目達到用戶指定的數目位置。
二分 K-Means 聚類算法代碼
根據算法思想，我們基于k均值算法做了少許的改動，代碼實現如下：
'''在給定數據集,所期望的簇數目和距離計算方法的條件下,函數返回聚類結果''' def biKmeans(dataMat, k, distMeas=distEclud):m, n = shape(dataMat)# 創建一個矩陣來存儲數據集中每個點的簇分配結果及平方誤差clusterAssment = mat(zeros((m, 2)))# 計算整個數據集的質心,并使用一個列表來保留所有的質心centroid0 = mean(dataMat, axis=0).tolist()[0]centList = [centroid0] # [-0.15772275000000002, 1.2253301166666664]# 遍歷數據集中所有點來計算每個點到質心的誤差值for j in range(m):clusterAssment[j, 1] = distMeas(mat(centroid0), dataMat[j, :]) ** 2# 對簇不停的進行劃分,直到得到想要的簇數目為止while (len(centList) < k):# 初始化最小SSE為無窮大,用于比較劃分前后的SSElowestSSE = inf# 通過考察簇列表中的值來獲得當前簇的數目,遍歷所有的簇來決定最佳的簇進行劃分for i in range(len(centList)):# 對每一個簇,將該簇中的所有點堪稱一個小的數據集ptsInCurrCluster = dataMat[nonzero(clusterAssment[:, 0].A == i)[0], :]# 將ptsInCurrCluster輸入到函數kMeans中進行處理,k=2,# kMeans會生成兩個質心(簇),同時給出每個簇的誤差值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)# 如果本次劃分的SSE值最小,則本次劃分被保存if (sseSplit + sseNotSplit) < lowestSSE:bestCentToSplit = ibestNewCents = centroidMatbestClustAss = splitClustAss.copy()lowestSSE = sseSplit + sseNotSplit# 找出最好的簇分配結果# 調用kmeans函數并且指定簇數為2時,會得到兩個編號分別為0和1的結果簇bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)# 更新為最佳質心bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplitprint('the bestCentToSplit is: ', bestCentToSplit)print('the len of bestClustAss is: ', len(bestClustAss))# 更新質心列表# 更新原質心list中的第i個質心為使用二分kMeans后bestNewCents的第一個質心centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]# 添加bestNewCents的第二個質心centList.append(bestNewCents[1, :].tolist()[0])# 重新分配最好簇下的數據(質心)以及SSEclusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAssreturn mat(centList), clusterAssment測試二分 KMeans 聚類算法
經過改進后，我們運行biKmeans函數得到可視化結果如下：
總結：如此我們得到預想的結果，解決了局部最優的問題，聚類會收斂到全局最小值。而原始的 kMeans() 函數偶爾會陷入局部最小值。
調用機器學習庫sklearn實現k-means 聚類
加載數據集
# 加載數據集 dataMat = [] fr = open("./testSet2.txt") # 注意，這個是相對路徑 for line in fr.readlines():curLine = line.strip().split('\t')fltLine = list(map(float,curLine)) # 映射所有的元素為 float（浮點數）類型dataMat.append(fltLine)訓練k-means算法模型
km = KMeans(n_clusters=3) # 初始化 km.fit(dataMat) # 擬合 km_pred = km.predict(dataMat) # 預測 centers = km.cluster_centers_ # 質心可視化結果
plt.scatter(np.array(dataMat)[:, 1], np.array(dataMat)[:, 0], c=km_pred) plt.scatter(centers[:, 1], centers[:, 0], c="r") plt.show()聚類結果
參考文獻
完整代碼下載
源碼請進【機器學習和自然語言QQ群：436303759】文件下載：
作者聲明
本文版權歸作者所有，旨在技術交流使用。未經作者同意禁止轉載，轉載后需在文章頁面明顯位置給出原文連接，否則相關責任自行承擔。
?
?
?
?
?
?
?
?
總結
以上是生活随笔為你收集整理的一步步教你轻松学K-means聚类算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Less 命令技巧，从底部网上看
- 下一篇： Android中的消息机制