機器學習算法 - k-means Clustering K均值聚類

k-means Clustering即K均值聚類算法是一類運用廣泛的聚類算法。

相關定義

聚類

聚類是指把對象劃分為多個組或者“聚簇”，進而使得同組對象之間比較相似，而不同組對象之間差異較大。

因為聚類過程中，并沒有輸入和待聚類對象之間的聯系資訊，是以聚類通常被看做無監督學習。

k-means算法是一種簡單的聚類算法，主要通過疊代來将資料集分類。

算法描述

數學描述

算法的輸入對象可以看做是 d 維向量空間的一些點，即對集合D={xi|i=1,2,3,...,n}進行聚類，并且其中 xi∈Rd 表示第i個資料點。而k-means聚類則是對D中的所有資料點進行處理，聚類中心可以表示為 C={Ki|i=1,2,...,k} ，并且将每個資料點可以記為 xi∈S(Kj) 即表示對第 i 個資料點屬于聚類中心Kj。

對于聚類算法，通常需要定義一種依據來判斷每個資料點屬于哪個聚類中心，而這個依據通常被稱為代價函數。在一般情況下，我們選取的聚類函數通常如下：

Cost=Σki=1Σx∈S(Ki)∥x−μi∥2

其中 μi 是屬于第i個聚類 S(Ki) 的對象點的均值，即聚類中心 Ki 。聚類的目标則是最小換這個代價函數，使得每個資料點 xi 和最近的聚類中心 Kj 的歐幾裡得距離的平方和最小。

算法步驟

輸入：資料集 D ，聚類數k

輸出：聚類集合 C ，聚簇成員向量m⃗ 

1. 建立k個點作為起始質心
2. 當任意一個點的簇配置設定結果發生改變時
   • 對資料集中的每個資料點，對每個質心，計算質心與資料點之間的距離
   • 将資料點配置設定到離它距離最近的簇
   • 對每一個簇，計算簇中所有的點的均值并将均值作為新的聚類中心

至于算法中怎麼找到初始的聚類中心，怎麼計算，度量函數的選擇，在後面都會提到。

程式

python

相關輔助函數

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

#Eclud Distance
def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, )))

#Initial Random Clustering Centroids    
def randCent(dataSet, k):
    n = shape(dataSet)[]
    centroids = mat(zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,J]) - minJ)
        centroids[:,J] = minJ + rangeJ * random.rand(k,)
    return centroids
           

這個是兩個輔助的函數，第一個函數定義了我們之前說的常用的一個度量——歐幾裡得距離，簡稱歐式距離。第二個輔助函數是用來随機初始化聚類中心的函數，其中centroids是聚類中心，dataSet是資料集合，k是聚類中心的數量，其中随機化的方法是找到資料的最小值和最大值，再在這兩個數之間産生k個随機的值。

K-means算法

def kMeans(dataSet, k, distMeas = distEclud, createCent = randCent) :
    m = shape(dataSet)[]
    clusterAssment = mat(zeros((m,)))
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m) :
            minDist = inf
            minIndex = -
            for j in range(k) :
                distJI = distMeas(centroids[j,:],dataSet[i,:])
                if distJI < minDist :
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i,] != minIndex:
                clusterChanged = True
            clusterAssment[i,:] = minIndex, minDist**

        for cent in range(k) :
            ptsInClust = dataSet[nonzero(clusterAssment[:,].A == cent)[]]
            centroids[cent,:] = mean(ptsInClust, axis = )

    return centroids, clusterAssment
           

在這一部分算法中，按照上面的說明，總共包含了三部分内容，即初始化聚類中心，尋找對于每個目标點最近的聚類中心，更新聚類中心的位置，當且僅當聚類中心收斂時，停止算法。我個人認為這裡應當簡單的加上停止算法，當疊代一定的次數時。

算法初始化了一個m行，2列的一個矩陣clusterAssment，這個矩陣的每一行都對應了一個目标點，而每一行的第一個位置記錄了聚類中心，第二個位置記錄了這個目标點到聚類中心的距離的平方。在判斷聚類中心是否改變時，程式的判斷依據是新的距離和clusterAssment裡面儲存的距離的對比。

程式的最後一部分内容是通過計算每個聚類中心所對應的目标點的值得均值， 來重新計算聚類中心。

算法的局限性

局部最優解

k-means算法在本質上屬于非凸函數的貪婪下降求解算法， 是以在理論上，最後得到的收斂解都隻是局部最優解而并非是全局最優解。并且是否最終能夠取到全局最優解在一定程度上與初始的聚類中心的位置也是相關的，對相同的資料集，如果一開始選取的聚類中心不同，那麼最終聚類出的結果可能不相同。

是以在解決這個問題上，主要是通過合理的選擇初始化的聚類中心以及在算法上做優化防止出現局部最優解。

K的選取

在實際中，由于對資料集的分布情況缺乏先驗的了解，是以有可能并不能預先知道