天天看點
傳回

k均值聚類算法優缺點_機器學習實戰項目- K-Means（K-均值）聚類算法K-Means 算法K-Means 聚類算法函數

K-Means 算法

聚類是一種無監督的學習, 它将相似的對象歸到一個簇中, 将不相似對象歸到不同簇中.

相似這一概念取決于所選擇的相似度計算方法.

K-Means 是發現給定資料集的 K 個簇的聚類算法, 之是以稱之為 K-均值 是因為它可以發現 K 個不同的簇, 且每個簇的中心采用簇中所含值的均值計算而成.

簇個數 K 是使用者指定的, 每一個簇通過其質心(centroid), 即簇中所有點的中心來描述.

聚類與分類算法的最大差別在于, 分類的目标類别已知, 而聚類的目标類别是未知的.

優點: 容易實作缺點:可能收斂到局部最小值, 在大規模資料集上收斂較慢使用資料類型 : 數值型資料

K-Means 場景

主要用來聚類, 但是類别是未知的.

例如: 對地圖上的點進行聚類.

K-Means 術語

  • 簇: 所有資料點點集合，簇中的對象是相似的。
  • 質心: 簇中所有點的中心(計算所有點的均值而來).
  • SSE: Sum of Sqared Error(平方誤差和), SSE 值越小，表示越接近它們的質心. 由于對誤差取了平方，是以更加注重那麼遠離中心的點.

有關 簇 和 質心 術語更形象的介紹, 請參考下圖:

k均值聚類算法優缺點_機器學習實戰項目- K-Means（K-均值）聚類算法K-Means 算法K-Means 聚類算法函數

K-Means 工作流程

  1. 首先, 随機确定 K 個初始點作為質心(不是資料中的點).
  2. 然後将資料集中的每個點配置設定到一個簇中, 具體來講, 就是為每個點找到距其最近的質心, 并将其配置設定該質心所對應的簇. 這一步完成之後, 每個簇的質心更新為該簇說有點的平均值.

上述過程的 僞代碼 如下:

  • 建立 k 個點作為起始質心(通常是随機選擇)
  • 當任意一個點的簇配置設定結果發生改變時
  • 對資料集中的每個資料點
  • 對每個質心
  • 計算質心與資料點之間的距離
  • 将資料點配置設定到距其最近的簇
  • 對每一個簇, 計算簇中所有點的均值并将均值作為質心

K-Means 開發流程

收集資料：使用任意方法準備資料：需要數值型資料類計算距離, 也可以将标稱型資料映射為二值型資料再用于距離計算分析資料：使用任意方法訓練算法：此步驟不适用于 K-Means 算法測試算法：應用聚類算法、觀察結果.可以使用量化的誤差名額如誤差平方和(後面會介紹)來評價算法的結果.使用算法：可以用于所希望的任何應用.通常情況下, 簇質心可以代表整個簇的資料來做出決策.

K-Means 聚類算法函數

從檔案加載資料集

# 從文本中建構矩陣，加載文本檔案，然後處理def loadDataSet(fileName): # 通用函數，用來解析以 tab 鍵分隔的 floats(浮點數)，例如: 1.6589854.285136 dataMat = [] fr = open(fileName) for line in fr.readlines(): curLine = line.strip().split('') fltLine = map(float,curLine) # 映射所有的元素為 float(浮點數)類型 dataMat.append(fltLine) return dataMat

計算兩個向量的歐氏距離

# 計算兩個向量的歐式距離(可根據場景選擇)def distEclud(vecA, vecB): return sqrt(sum(power(vecA - vecB, 2))) # la.norm(vecA-vecB)

建構一個包含 K 個随機質心的集合

# 為給定資料集建構一個包含 k 個随機質心的集合。随機質心必須要在整個資料集的邊界之内，這可以通過找到資料集每一維的最小和最大值來完成。然後生成 0~1.0 之間的随機數并通過取值範圍和最小值，以便確定随機點在資料的邊界之内。def randCent(dataSet, k): n = shape(dataSet)[1] # 列的數量 centroids = mat(zeros((k,n))) # 建立k個質心矩陣 for j in range(n): # 建立随機簇質心，并且在每一維的邊界内 minJ = min(dataSet[:,j]) # 最小值 rangeJ = float(max(dataSet[:,j]) - minJ) # 範圍 = 最大值 - 最小值 centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1)) # 随機生成 return centroids

K-Means 聚類算法

# k-means 聚類算法# 該算法會建立k個質心，然後将每個點配置設定到最近的質心，再重新計算質心。# 這個過程重複數次，直到資料點的簇配置設定結果不再改變位置。# 運作結果(多次運作結果可能會不一樣，可以試試，原因為随機質心的影響，但總的結果是對的， 因為資料足夠相似，也可能會陷入局部最小值)def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): m = shape(dataSet)[0] # 行數 clusterAssment = mat(zeros((m, 2))) # 建立一個與 dataSet 行數一樣，但是有兩列的矩陣，用來儲存簇配置設定結果 centroids = createCent(dataSet, k) # 建立質心，随機k個質心 clusterChanged = True while clusterChanged: clusterChanged = False for i in range(m): # 循環每一個資料點并配置設定到最近的質心中去 minDist = inf; minIndex = -1 for j in range(k): distJI = distMeas(centroids[j,:],dataSet[i,:]) # 計算資料點到質心的距離 if distJI < minDist: # 如果距離比 minDist(最小距離)還小，更新 minDist(最小距離)和最小質心的 index(索引) minDist = distJI; minIndex = j if clusterAssment[i, 0] != minIndex: # 簇配置設定結果改變 clusterChanged = True # 簇改變 clusterAssment[i, :] = minIndex,minDist**2 # 更新簇配置設定結果為最小質心的 index(索引)，minDist(最小距離)的平方 print centroids for cent in range(k): # 更新質心 ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A==cent)[0]] # 擷取該簇中的所有點 centroids[cent,:] = mean(ptsInClust, axis=0) # 将質心修改為簇中所有點的平均值，mean 就是求平均值的 return centroids, clusterAssment

測試函數

  1. 測試一下以上的基礎函數是否可以如預期運作, 請看: https://github.com/apachecn/MachineLearning/blob/master/src/python/10.kmeans/kMeans.py
  2. 測試一下 kMeans 函數是否可以如預期運作, 請看: https://github.com/apachecn/MachineLearning/blob/master/src/python/10.kmeans/kMeans.py

參考運作結果如下:

k均值聚類算法優缺點_機器學習實戰項目- K-Means（K-均值）聚類算法K-Means 算法K-Means 聚類算法函數
在 kMeans 的函數測試中，可能偶爾會陷入局部最小值(局部最優的結果，但不是全局最優的結果).

K-Means 聚類算法的缺陷

在 kMeans 的函數測試中，可能偶爾會陷入局部最小值(局部最優的結果，但不是全局最優的結果).

局部最小值的的情況如下:

k均值聚類算法優缺點_機器學習實戰項目- K-Means（K-均值）聚類算法K-Means 算法K-Means 聚類算法函數

是以為了克服 KMeans 算法收斂于局部最小值的問題，有更厲害的大佬提出了另一個稱之為二分K-均值(bisecting K-Means)的算法.

二分 K-Means 聚類算法

該算法首先将所有點作為一個簇，然後将該簇一分為二。

之後選擇其中一個簇繼續進行劃分，選擇哪一個簇進行劃分取決于對其劃分時候可以最大程度降低 SSE(平方和誤差)的值。

上述基于 SSE 的劃分過程不斷重複，直到得到使用者指定的簇數目為止。

二分 K-Means 聚類算法僞代碼

  • 将所有點看成一個簇
  • 當簇數目小雨 k 時
  • 對于每一個簇
  • 計算總誤差
  • 在給定的簇上面進行 KMeans 聚類(k=2)
  • 計算将該簇一分為二之後的總誤差
  • 選擇使得誤差最小的那個簇進行劃分操作

另一種做法是選擇 SSE 最大的簇進行劃分，直到簇數目達到使用者指定的數目位置。 接下來主要介紹該做法。

二分 K-Means 聚類算法代碼

# 二分 KMeans 聚類算法, 基于 kMeans 基礎之上的優化，以避免陷入局部最小值def biKMeans(dataSet, k, distMeas=distEclud): m = shape(dataSet)[0] clusterAssment = mat(zeros((m,2))) # 儲存每個資料點的簇配置設定結果和平方誤差 centroid0 = mean(dataSet, axis=0).tolist()[0] # 質心初始化為所有資料點的均值 centList =[centroid0] # 初始化隻有 1 個質心的 list for j in range(m): # 計算所有資料點到初始質心的距離平方誤差 clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2 while (len(centList) < k): # 當質心數量小于 k 時 lowestSSE = inf for i in range(len(centList)): # 對每一個質心 ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] # 擷取目前簇 i 下的所有資料點 centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas) # 将目前簇 i 進行二分 kMeans 處理 sseSplit = sum(splitClustAss[:,1]) # 将二分 kMeans 結果中的平方和的距離進行求和 sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) # 将未參與二分 kMeans 配置設定結果中的平方和的距離進行求和 print "sseSplit, and notSplit:
k均值聚類算法優缺點
上一篇: K-均值聚類算法(K-Means)sklearn.cluster.k_means
下一篇: k均值聚類算法優缺點_K-均值聚類算法(K-Means)

繼續閱讀