讀古今文學網 > 機器學習實戰 > 10.1 k均值聚類算法 >

10.1 k均值聚類算法

k均值聚類

優點：容易實現。 缺點：可能收斂到局部最小值，在大規模數據集上收斂較慢。 適用數據類型：數值型數據。

k均值是發現給定數據集的k個簇的算法。簇個數k是用戶給定的，每一個簇通過其質心（centroid），即簇中所有點的中心來描述。

k均值算法的工作流程是這樣的。首先，隨機確定k個初始點作為質心。然後將數據集中的每個點分配到一個簇中，具體來講，為每個點找距其最近的質心，並將其分配給該質心所對應的簇。這一步完成之後，每個簇的質心更新為該簇所有點的平均值。

上述過程的偽代碼表示如下： 　 

創建k個點作為起始質心（經常是隨機選擇）
當任意一個點的簇分配結果發生改變時
    對數據集中的每個數據點
        對每個質心
            計算質心與數據點之間的距離
        將數據點分配到距其最近的簇
    對每一個簇，計算簇中所有點的均值並將均值作為質心

K均值聚類的一般流程

  1. 收集數據：使用任意方法。
  2. 準備數據：需要數值型數據來計算距離，也可以將標稱型數據映射為二值型數據再用於距離計算。
  3. 分析數據：使用任意方法。
  4. 訓練算法：不適用於無監督學習，即無監督學習沒有訓練過程。
  5. 測試算法：應用聚類算法、觀察結果。可以使用量化的誤差指標如誤差平方和（後面會介紹）來評價算法的結果。
  6. 使用算法：可以用於所希望的任何應用。通常情況下，簇質心可以代表整個簇的數據來做出決策。

上面提到「最近」質心的說法，意味著需要進行某種距離計算。讀者可以使用所喜歡的任意距離度量方法。數據集上k均值算法的性能會受到所選距離計算方法的影響。下面給出k均值算法的代碼實現。首先創建一個名為kMeans.py的文件，然後將下面程序清單中的代碼添加到文件中。

程序清單 10-1 k均值聚類支持函數 

from numpy import *

def loadDataSet(fileName):
    dataMat = 
    fr = open(fileName)
    for line in fr.readlines:
        curLine = line.strip.split(\'t\')
        fltLine = map(float,curLine)
        dataMat.append(fltLine)
    return dataMat

def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2)))

def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))
    #構建簇質心
    for j in range(n):
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        entroids[:,j] = minJ + rangeJ * random.rand(k,1)
    return centroids

程序清單10-1中的代碼包含幾個k均值算法中要用到的輔助函數。第一個函數loadDataSet和上一章完全相同，它將文本文件導入到一個列表中。文本文件每一行為tab分隔的浮點數。每一個列表會被添加到dataMat中，最後返回dataMat。該返回值是一個包含許多其他列表的列表。這種格式可以很容易將很多值封裝到矩陣中。

下一個函數distEclud計算兩個向量的歐式距離。這是本章最先使用的距離函數，也可以使用其他距離函數。

最後一個函數是randCent，該函數為給定數據集構建一個包含k個隨機質心的集合。隨機質心必須要在整個數據集的邊界之內，這可以通過找到數據集每一維的最小和最大值來完成。然後生成0到1.0之間的隨機數並通過取值範圍和最小值，以便確保隨機點在數據的邊界之內 。接下來看一下這三個函數的實際效果。保存kMeans.py文件，然後在Python提示符下輸入： 

>>> import kMeans
>>> from numpy import *

要從文本文件中構建矩陣，輸入下面的命令（第10章的源代碼中給出了testSet.txt的內容）： 

>>> datMat=mat(kMeans.loadDataSet(\'testSet.txt\'))

讀者可以瞭解一下這個二維矩陣，後面將使用該矩陣來測試完整的k均值算法。下面看看randCent函數是否正常運行。首先，先看一下矩陣中的最大值與最小值： 

>>> min(datMat[:,0])
matrix([[-5.379713]])
>>> min(datMat[:,1])
matrix([[-4.232586]])
>>> max(datMat[:,1])
matrix([[ 5.1904]])
>>> max(datMat[:,0])
matrix([[ 4.838138]])

然後看看randCent函數能否生成min到max之間的值: 

>>> kMeans.randCent(datMat, 2)
matrix([[-3.24278889, -0.04213842],
        [-0.92437171, 3.19524231]])

從上面的結果可以看到，函數randCent確實會生成min到max之間的值。上述結果表明，這些函數都能夠按照預想的方式運行。最後測試一下距離計算方法： 

>>> kMeans.distEclud(datMat[0], datMat[1])
5.184632816681332

所有支持函數正常運行之後，就可以準備實現完整的k均值算法了。該算法會創建k個質心，然後將每個點分配到最近的質心，再重新計算質心。這個過程重複數次，直到數據點的簇分配結果不再改變為止。打開kMeans.py文件輸入下面程序清單中的代碼。

程序清單10-2　k均值聚類算法 

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroids = createCent(dataSet, 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 = distJI; minIndex = j
            if clusterAssment[i,0] != minIndex: clusterChanged = True
            clusterAssment[i,:] = minIndex,minDist**2
        #❷（以下四行）更新質心的位置
        print centroids
        for cent in range(k):
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:] = mean(ptsInClust, axis=0)
    return centroids, clusterAssment

上述清單給出了k均值算法。kMeans函數接受4個輸入參數。只有數據集及簇的數目是必選參數，而用來計算距離和創建初始質心的函數都是可選的。kMeans函數一開始確定數據集中數據點的總數，然後創建一個矩陣來存儲每個點的簇分配結果。簇分配結果矩陣clusterAssment包含兩列：一列記錄簇索引值，第二列存儲誤差。這裡的誤差是指當前點到簇質心的距離，後邊會使用該誤差來評價聚類的效果。

按照上述方式（即計算質心-分配-重新計算）反覆迭代，直到所有數據點的簇分配結果不再改變為止。程序中可以創建一個標誌變量clusterChanged，如果該值為True，則繼續迭代。上述迭代使用while循環來實現。接下來遍歷所有數據找到距離每個點最近的質心，這可以通過對每個點遍歷所有質心並計算點到每個質心的距離來完成❶。計算距離是使用distMeas參數給出的距離函數，默認距離函數是distEclud，該函數的實現已經在程序清單10-1中給出。如果任一點的簇分配結果發生改變，則更新clusterChanged標誌。

最後，遍歷所有質心並更新它們的取值❷。具體實現步驟如下：首先通過數組過濾來獲得給定簇的所有點；然後計算所有點的均值，選項axis = 0表示沿矩陣的列方向進行均值計算；最後，程序返回所有的類質心與點分配結果。圖10-1給出了一個聚類結果的示意圖。

圖10-1　k均值聚類的結果示意圖。圖中數據集在三次迭代之後收斂。形狀相似的數據點被分到同樣的簇中，簇中心使用十字來表示

接下來看看程序清單10-2的運行效果。保存kMeans.py文件後，在Python提示符下輸入： 

>>> reload(kMeans)
<module \'kMeans\' from \'kMeans.pyc\'>

如果沒有將前面例子中的datMat數據複製過來，則可以輸入下面的命令（記住要導入NumPy）： 

>>> datMat=mat(kMeans.loadDataSet(\'testSet.txt\'))

現在就可以對datMat中的數據點進行聚類處理。從圖像中可以大概預先知道最後的結果應該有4個簇，所以可以輸入如下命令： 

>>> myCentroids, clustAssing = kMeans.kMeans(datMat,4)
[[-4.06724228 0.21993975]
 [ 0.73633558 -1.41299247]
 [-2.59754537 3.15378974]
 [ 4.49190084 3.46005807]]
[[-3.62111442 -2.36505947]
 [ 2.21588922 -2.88365904]
 [-2.38799628 2.96837672]
 [ 2.6265299 3.10868015]]
[[-3.53973889 -2.89384326]
 [ 2.65077367 -2.79019029]
 [-2.46154315 2.78737555]
 [ 2.6265299 3.10868015]]

上面的結果給出了4個質心。可以看到，經過3次迭代之後k均值算法收斂。這4個質心以及原始數據的散點圖在圖10-1中給出。

到目前為止，關於聚類的一切進展都很順利，但事情並不總是如此。接下來會討論k均值算法可能出現的問題及其解決辦法。

    機器學習實戰