深入理解K-Means聚類算法

什么是聚類分析

聚類分析是在數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)對(duì)象之間的關(guān)系，將數(shù)據(jù)進(jìn)行分組，組內(nèi)的相似性越大，組間的差別越大，則聚類效果越好。

不同的簇類型

聚類旨在發(fā)現(xiàn)有用的對(duì)象簇，在現(xiàn)實(shí)中我們用到很多的簇的類型，使用不同的簇類型劃分?jǐn)?shù)據(jù)的結(jié)果是不同的，如下的幾種簇類型。

明顯分離的

可以看到(a)中不同組中任意兩點(diǎn)之間的距離都大于組內(nèi)任意兩點(diǎn)之間的距離，明顯分離的簇不一定是球形的，可以具有任意的形狀。

基于原型的

簇是對(duì)象的集合，其中每個(gè)對(duì)象到定義該簇的原型的距離比其他簇的原型距離更近，如(b)所示的原型即為中心點(diǎn)，在一個(gè)簇中的數(shù)據(jù)到其中心點(diǎn)比到另一個(gè)簇的中心點(diǎn)更近。這是一種常見的基于中心的簇，最常用的K-Means就是這樣的一種簇類型。
這樣的簇趨向于球形。

基于密度的

簇是對(duì)象的密度區(qū)域，(d)所示的是基于密度的簇，當(dāng)簇不規(guī)則或相互盤繞，并且有早上和離群點(diǎn)事，常常使用基于密度的簇定義。

關(guān)于更多的簇介紹參考《數(shù)據(jù)挖掘導(dǎo)論》。

基本的聚類分析算法

1. K均值：
基于原型的、劃分的距離技術(shù)，它試圖發(fā)現(xiàn)用戶指定個(gè)數(shù)(K)的簇。

2. 凝聚的層次距離：
思想是開始時(shí)，每個(gè)點(diǎn)都作為一個(gè)單點(diǎn)簇，然后，重復(fù)的合并兩個(gè)最靠近的簇，直到嘗試單個(gè)、包含所有點(diǎn)的簇。

3. DBSCAN:
一種基于密度的劃分距離的算法，簇的個(gè)數(shù)有算法自動(dòng)的確定，低密度中的點(diǎn)被視為噪聲而忽略，因此其不產(chǎn)生完全聚類。

距離量度

不同的距離量度會(huì)對(duì)距離的結(jié)果產(chǎn)生影響，常見的距離量度如下所示：

K-Means算法

下面介紹K均值算法：

優(yōu)點(diǎn)：易于實(shí)現(xiàn)
缺點(diǎn)：可能收斂于局部最小值，在大規(guī)模數(shù)據(jù)收斂慢

算法思想較為簡(jiǎn)單如下所示：

選擇K個(gè)點(diǎn)作為初始質(zhì)心  
repeat  
    將每個(gè)點(diǎn)指派到最近的質(zhì)心，形成K個(gè)簇  
    重新計(jì)算每個(gè)簇的質(zhì)心  
until 簇不發(fā)生變化或達(dá)到最大迭代次數(shù)

這里的重新計(jì)算每個(gè)簇的質(zhì)心，如何計(jì)算的是根據(jù)目標(biāo)函數(shù)得來的，因此在開始時(shí)我們要考慮距離度量和目標(biāo)函數(shù)。

考慮歐幾里得距離的數(shù)據(jù)，使用誤差平方和（Sum of the Squared Error,SSE）作為聚類的目標(biāo)函數(shù)，兩次運(yùn)行K均值產(chǎn)生的兩個(gè)不同的簇集，我們更喜歡SSE最小的那個(gè)。

k表示k個(gè)聚類中心，ci表示第幾個(gè)中心，dist表示的是歐幾里得距離。
這里有一個(gè)問題就是為什么，我們更新質(zhì)心是讓所有的點(diǎn)的平均值，這里就是SSE所決定的。

下面用Python進(jìn)行實(shí)現(xiàn)

# dataSet樣本點(diǎn),k 簇的個(gè)數(shù)
# disMeas距離量度，默認(rèn)為歐幾里得距離
# createCent,初始點(diǎn)的選取
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0] #樣本數(shù)
    clusterAssment = mat(zeros((m,2))) #m*2的矩陣                   
    centroids = createCent(dataSet, k) #初始化k個(gè)中心
    clusterChanged = True             
    while clusterChanged:      #當(dāng)聚類不再變化
        clusterChanged = False
        for i in range(m):
            minDist = inf; minIndex = -1
            for j in range(k): #找到最近的質(zhì)心
                distJI = distMeas(centroids[j,:],dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI; minIndex = j
            if clusterAssment[i,0] != minIndex: clusterChanged = True
            # 第1列為所屬質(zhì)心，第2列為距離
            clusterAssment[i,:] = minIndex,minDist**2
        print centroids

        # 更改質(zhì)心位置
        for cent in range(k):
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:] = mean(ptsInClust, axis=0)
    return centroids, clusterAssment

重點(diǎn)理解一下：

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

循環(huán)每一個(gè)質(zhì)心，找到屬于當(dāng)前質(zhì)心的所有點(diǎn)，然后根據(jù)這些點(diǎn)去更新當(dāng)前的質(zhì)心。
nonzero()返回的是一個(gè)二維的數(shù)組，其表示非0的元素位置。

>>> from numpy import *
>>> a=array([[1,0,0],[0,1,2],[2,0,0]])
>>> a
array([[1, 0, 0],
       [0, 1, 2],
       [2, 0, 0]])
>>> nonzero(a)
(array([0, 1, 1, 2]), array([0, 1, 2, 0]))

表示第[0,0],[1,1] … 位非零元素。第一個(gè)數(shù)組為行，第二個(gè)數(shù)組為列，兩者進(jìn)行組合得到的。

ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
因此首先先比較clusterAssment[:,0].A==cent的真假，如果為真則記錄了他所在的行，因此在用切片進(jìn)行取值。

一些輔助的函數(shù)：

def loadDataSet(fileName):      #general function to parse tab -delimited floats
    dataMat = []                #assume last column is target value
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = map(float,curLine) #map all elements to float()
        dataMat.append(fltLine)
    return dataMat

def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)

def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))#create centroid mat
    for j in range(n):#create random cluster centers, within bounds of each dimension
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
    return centroids
運(yùn)行和結(jié)果

將上述代碼寫到kMeans.py中，然后打開python交互端。

>>> from numpy import *
>>> import kMeans
>>> dat=mat(kMeans.loadDataSet('testSet.txt')) #讀入數(shù)據(jù)
>>> center，clust=kMeans.kMeans(dat,4)
[[ 0.90796996  5.05836784]
 [-2.88425582  0.01687006]
 [-3.3447423  -1.01730512]
 [-0.32810867  0.48063528]]
[[ 1.90508653  3.530091  ]
 [-3.00984169  2.66771831]
 [-3.38237045 -2.9473363 ]
 [ 2.22463036 -1.37361589]]
[[ 2.54391447  3.21299611]
 [-2.46154315  2.78737555]
 [-3.38237045 -2.9473363 ]
 [ 2.8692781  -2.54779119]]
[[ 2.6265299   3.10868015]
 [-2.46154315  2.78737555]
 [-3.38237045 -2.9473363 ]
 [ 2.80293085 -2.7315146 ]]
# 作圖
>>>kMeans(dat,center)

繪圖的程序如下：

defdraw(data,center):length=len(center) fig=plt.figure# 繪制原始數(shù)據(jù)的散點(diǎn)圖plt.scatter(data[:,0],data[:,1],s=25,alpha=0.4)# 繪制簇的質(zhì)心點(diǎn)foriinrange(length): plt.annotate('center',xy=(center[i,0],center[i,1]),xytext=\ (center[i,0]+1,center[i,1]+1),arrowprops=dict(facecolor='red')) plt.show()

K-Means算法的缺陷

k均值算法非常簡(jiǎn)單且使用廣泛，但是其有主要的兩個(gè)缺陷：
1. K值需要預(yù)先給定，屬于預(yù)先知識(shí)，很多情況下K值的估計(jì)是非常困難的，對(duì)于像計(jì)算全部微信用戶的交往圈這樣的場(chǎng)景就完全的沒辦法用K-Means進(jìn)行。對(duì)于可以確定K值不會(huì)太大但不明確精確的K值的場(chǎng)景，可以進(jìn)行迭代運(yùn)算，然后找出Cost Function最小時(shí)所對(duì)應(yīng)的K值，這個(gè)值往往能較好的描述有多少個(gè)簇類。
2.K-Means算法對(duì)初始選取的聚類中心點(diǎn)是敏感的，不同的隨機(jī)種子點(diǎn)得到的聚類結(jié)果完全不同
3.K均值算法并不是很所有的數(shù)據(jù)類型。它不能處理非球形簇、不同尺寸和不同密度的簇，銀冠指定足夠大的簇的個(gè)數(shù)是他通常可以發(fā)現(xiàn)純子簇。
4.對(duì)離群點(diǎn)的數(shù)據(jù)進(jìn)行聚類時(shí)，K均值也有問題，這種情況下，離群點(diǎn)檢測(cè)和刪除有很大的幫助。

下面對(duì)初始質(zhì)心的選擇進(jìn)行討論：

拙劣的初始質(zhì)心

當(dāng)初始質(zhì)心是隨機(jī)的進(jìn)行初始化的時(shí)候，K均值的每次運(yùn)行將會(huì)產(chǎn)生不同的SSE,而且隨機(jī)的選擇初始質(zhì)心結(jié)果可能很糟糕，可能只能得到局部的最優(yōu)解，而無法得到全局的最優(yōu)解。如下圖所示：

可以看到程序迭代了4次終止，其得到了局部的最優(yōu)解，顯然我們可以看到其不是全局最優(yōu)的，我們?nèi)匀豢梢哉业揭粋€(gè)更小的SSE的聚類。

隨機(jī)初始化的局限

你可能會(huì)想到：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選擇一個(gè)具有最小的SSE的簇集。該策略非常的簡(jiǎn)單，但是效果可能不是很好，這取決于數(shù)據(jù)集合尋找的簇的個(gè)數(shù)。

關(guān)于更多，參考《數(shù)據(jù)挖掘導(dǎo)論》

K-Means優(yōu)化算法

為了克服K-Means算法收斂于局部最小值的問題，提出了一種二分K-均值(bisecting K-means)

bisecting K-means

算法的偽代碼如下：

將所有的點(diǎn)看成是一個(gè)簇
當(dāng)簇小于數(shù)目k時(shí)
    對(duì)于每一個(gè)簇
        計(jì)算總誤差
        在給定的簇上進(jìn)行K-均值聚類,k值為2
        計(jì)算將該簇劃分成兩個(gè)簇后總誤差
    選擇是的誤差最小的那個(gè)簇進(jìn)行劃分
完整的Python代碼如下：

def biKmeans(dataSet, k, distMeas=distEclud):
    m = shape(dataSet)[0]
    # 這里第一列為類別，第二列為SSE
    clusterAssment = mat(zeros((m,2)))
    # 看成一個(gè)簇是的質(zhì)心
    centroid0 = mean(dataSet, axis=0).tolist()[0]
    centList =[centroid0] #create a list with one centroid
    for j in range(m):    #計(jì)算只有一個(gè)簇是的誤差
        clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2

    # 核心代碼
    while (len(centList) < k):
        lowestSSE = inf
        # 對(duì)于每一個(gè)質(zhì)心，嘗試的進(jìn)行劃分
        for i in range(len(centList)):
            # 得到屬于該質(zhì)心的數(shù)據(jù)
            ptsInCurrCluster =\ dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
            # 對(duì)該質(zhì)心劃分成兩類
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
            # 計(jì)算該簇劃分后的SSE
            sseSplit = sum(splitClustAss[:,1])
            # 沒有參與劃分的簇的SSE
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
            print "sseSplit, and notSplit: ",sseSplit,sseNotSplit
            # 尋找最小的SSE進(jìn)行劃分
            # 即對(duì)哪一個(gè)簇進(jìn)行劃分后SSE最小
            if (sseSplit + sseNotSplit) < lowestSSE:
                bestCentToSplit = i
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit

        # 較難理解的部分
        bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
        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]#replace a centroid with two best centroids
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE
    return mat(centList), clusterAssment
下面對(duì)最后的代碼進(jìn)行解析：

      bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
      bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit

這里是更改其所屬的類別，其中bestClustAss = splitClustAss.copy()是進(jìn)行k-means后所返回的矩陣，其中第一列為類別，第二列為SSE值，因?yàn)楫?dāng)k=2是k-means返回的是類別0，1兩類，因此這里講類別為1的更改為其質(zhì)心的長(zhǎng)度，而類別為0的返回的是該簇原先的類別。

舉個(gè)例子：
例如：目前劃分成了0，1兩個(gè)簇，而要求劃分成3個(gè)簇，則在算法進(jìn)行時(shí)，假設(shè)對(duì)1進(jìn)行劃分得到的SSE最小，則將1劃分成了2個(gè)簇，其返回值為0，1兩個(gè)簇，將返回為1的簇改成2，返回為0的簇改成1，因此現(xiàn)在就有0，1，2三個(gè)簇了。

  centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE

其中bestNewCents是k-means的返回簇中心的值，其有兩個(gè)值，分別是第一個(gè)簇，和第二個(gè)簇的坐標(biāo)(k=2)，這里將第一個(gè)坐標(biāo)賦值給 centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0],將另一個(gè)坐標(biāo)添加到centList中 centList.append(bestNewCents[1,:].tolist()[0])
運(yùn)行與結(jié)果

>>> from numpy import *
>>> import kMeans
>>> dat = mat(kMeans.loadDataSet('testSet2.txt'))
>>> cent,assment=kMeans.biKmeans(dat,3)
sseSplit, and notSplit:  570.722757425 0.0
the bestCentToSplit is:  0
the len of bestClustAss is:  60
sseSplit, and notSplit:  68.6865481262 38.0629506357
sseSplit, and notSplit:  22.9717718963 532.659806789
the bestCentToSplit is:  0
the len of bestClustAss is:  40

可以看到進(jìn)行了兩次的劃分，第一次最好的劃分是在0簇，第二次劃分是在1簇。
可視化如下圖所示：

Mini Batch k-Means

在原始的K-means算法中，每一次的劃分所有的樣本都要參與運(yùn)算，如果數(shù)據(jù)量非常大的話，這個(gè)時(shí)間是非常高的，因此有了一種分批處理的改進(jìn)算法。
使用Mini Batch（分批處理）的方法對(duì)數(shù)據(jù)點(diǎn)之間的距離進(jìn)行計(jì)算。
Mini Batch的好處：不必使用所有的數(shù)據(jù)樣本，而是從不同類別的樣本中抽取一部分樣本來代表各自類型進(jìn)行計(jì)算。n 由于計(jì)算樣本量少，所以會(huì)相應(yīng)的減少運(yùn)行時(shí)間n 但另一方面抽樣也必然會(huì)帶來準(zhǔn)確度的下降。