天天看點
傳回

【機器學習實戰】第10章 K-Means（均值）聚類算法 第 10 章 K-Means（K-均值）聚類算法

第 10 章 K-Means（K-均值）聚類算法

【機器學習實戰】第10章 K-Means（均值）聚類算法 第 10 章 K-Means（K-均值）聚類算法

K-Means 算法

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

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

K-Means 是發現給定資料集的 K 個簇的聚類算法, 之是以稱之為 

K-均值

 是因為它可以發現 K 個不同的簇, 且每個簇的中心采用簇中所含值的均值計算而成.

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

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

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

K-Means 場景

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

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

K-Means 術語

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

有關 

簇

 和 

質心

 術語更形象的介紹, 請參考下圖:

【機器學習實戰】第10章 K-Means（均值）聚類算法 第 10 章 K-Means（K-均值）聚類算法

K-Means 工作流程

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

上述過程的 

僞代碼

 如下:

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

K-Means 開發流程 

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

K-Means 聚類算法函數

從檔案加載資料集 

# 從文本中建構矩陣，加載文本檔案，然後處理
def loadDataSet(fileName):    # 通用函數，用來解析以 tab 鍵分隔的 floats（浮點數），例如: 1.658985	4.285136
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        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

參考運作結果如下:

【機器學習實戰】第10章 K-Means（均值）聚類算法 第 10 章 K-Means（K-均值）聚類算法
在 kMeans 的函數測試中，可能偶爾會陷入局部最小值（局部最優的結果，但不是全局最優的結果）.

K-Means 聚類算法的缺陷

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

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

【機器學習實戰】第10章 K-Means（均值）聚類算法 第 10 章 K-Means（K-均值）聚類算法

是以為了克服 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: ",sseSplit,sseNotSplit
            if (sseSplit + sseNotSplit) < lowestSSE: # 總的（未拆分和已拆分）誤差和越小，越相似，效果越優化，劃分的結果更好（注意：這裡的了解很重要，不明白的地方可以和我們一起讨論）
                bestCentToSplit = i
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit
        # 找出最好的簇配置設定結果    
        bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) # 調用二分 kMeans 的結果，預設簇是 0,1. 當然也可以改成其它的數字
        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,:].tolist()[0] # 更新原質心 list 中的第 i 個質心為使用二分 kMeans 後 bestNewCents 的第一個質心
        centList.append(bestNewCents[1,:].tolist()[0]) # 添加 bestNewCents 的第二個質心
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss # 重新配置設定最好簇下的資料（質心）以及SSE
    return mat(centList), clusterAssment

測試二分 KMeans 聚類算法

  • 測試一下二分 KMeans 聚類算法，請看: https://github.com/apachecn/MachineLearning/blob/master/src/python/10.kmeans/kMeans.py

上述函數可以運作多次，聚類會收斂到全局最小值，而原始的 kMeans() 函數偶爾會陷入局部最小值。

運作參考結果如下:

【機器學習實戰】第10章 K-Means（均值）聚類算法 第 10 章 K-Means（K-均值）聚類算法
  • 作者：那伊抹微笑
  • GitHub位址: https://github.com/apachecn/MachineLearning
  • 版權聲明：歡迎轉載學習 => 請标注資訊來源于 ApacheCN
機器學習 k-means k均值算法 機器學習實戰 ApacheCN
上一篇: python中requests包的text和content方法的差別
下一篇: 開啟虛拟機顯示‘内部錯誤’的解決辦法_F_hawk189

繼續閱讀