1、基本概念

聚類(lèi)分析簡(jiǎn)稱(chēng)聚類(lèi)（clustering），是一個(gè)把數(shù)據(jù)集劃分成子集的過(guò)程，每一個(gè)子集是一個(gè)簇（cluster），使得簇中的樣本彼此相似，但與其他簇中的樣本不相似。

聚類(lèi)分析不需要事先知道樣本的類(lèi)別，甚至不用知道類(lèi)別個(gè)數(shù)，因此它是一種典型的無(wú)監(jiān)督學(xué)習(xí)算法，一般用于數(shù)據(jù)探索，比如群組發(fā)現(xiàn)和離群點(diǎn)檢測(cè)，還可以作為其他算法的預(yù)處理步驟。

在工作中遇到用戶畫(huà)像、群組劃分問(wèn)題，而kmeans聚類(lèi)這一無(wú)監(jiān)督學(xué)習(xí)算法，可以在無(wú)數(shù)據(jù)標(biāo)注訓(xùn)練情況下，基于距離按將群組劃分不同的簇。

主要的聚類(lèi)算法一般可以劃分為以下幾類(lèi)：

2、Kmeans算法

Kmeans屬于劃分方法的經(jīng)典聚類(lèi)方法。

算法步驟如下：

選擇K個(gè)點(diǎn)作為初始質(zhì)心（隨機(jī)產(chǎn)生或者從D中選?。? 

• repeat:將每個(gè)點(diǎn)分配到最近的質(zhì)心，形成K個(gè)簇; 重新計(jì)算每個(gè)簇的質(zhì)心  
• until:簇不發(fā)生變化或達(dá)到最大迭代次數(shù)

2.1 k值選取

k的值是用戶指定的，表示需要得到的簇的數(shù)目。

在運(yùn)用Kmeans算法時(shí)，我們一般不知道數(shù)據(jù)的分布情況，不可能知道數(shù)據(jù)的集群數(shù)目，所以一般通過(guò)枚舉來(lái)確定k的值。

另外，在實(shí)際應(yīng)用中，由于Kmean一般作為數(shù)據(jù)預(yù)處理，或者用于輔助分類(lèi)貼標(biāo)簽，所以k一般不會(huì)設(shè)置很大。

2.2 初始質(zhì)心的選取

Kmeans算法對(duì)初始質(zhì)心的選取比較敏感，選取不同的質(zhì)心，往往會(huì)得到不同的結(jié)果。

初始質(zhì)心的選取方法，常用以下兩種的簡(jiǎn)單方法：一種是隨機(jī)選取，一種是用戶指定。

需要注意的是，無(wú)論是隨機(jī)選取還是用戶指定，質(zhì)心都盡量不要超過(guò)原始數(shù)據(jù)的邊界，即質(zhì)心每一維度上的值要落在原始數(shù)據(jù)集每一維度的最小與最大值之間。

2.3 距離度量方法

距離度量方法（或者說(shuō)相似性度量方法）有很多種，常用的有歐氏距離，余弦相似度，街區(qū)距離，漢明距離等等。

在Kmeans算法中，一般采用歐氏距離計(jì)算兩個(gè)點(diǎn)的距離，歐氏距離如下：

distEclud(X,Y)=∑i=1n(Xi−Yi)2‾‾‾‾‾‾‾‾‾‾‾‾?

舉個(gè)例子，X=（1000，0.1），Y=（900，0.2）,那么它們的歐氏距離就是：

(1000−900)2+(0.1−0.2)2‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾√≈100 (1000−900)2+(0.1−0.2)2≈100

舉這個(gè)例子是為了說(shuō)明，當(dāng)原始數(shù)據(jù)中各個(gè)維度的數(shù)量級(jí)不同時(shí)，它們對(duì)結(jié)果的影響也隨之不同，那些數(shù)量級(jí)太小的維度，對(duì)于結(jié)果幾乎沒(méi)產(chǎn)生任何影響。

比如所舉的例子中的第二個(gè)維度的0.1，0.2，與第一個(gè)維度1000的數(shù)量級(jí)相差了一萬(wàn)倍。

為了賦予數(shù)據(jù)每個(gè)維度同等的重要性，我們?cè)谶\(yùn)用歐氏距離時(shí)，必須先對(duì)數(shù)據(jù)進(jìn)行規(guī)范化，比如將每個(gè)維度都縮放到[0,1]之間。

2.4 質(zhì)心的計(jì)算

在Kmeans算法中，將簇中所有樣本的均值作為該簇的質(zhì)心。這也是Kmeans名字的由來(lái)吧。

2.5 算法停止條件

在兩種情況下算法應(yīng)該停止：一種是達(dá)到了指定的最大迭代次數(shù)，一種是算法已經(jīng)收斂，即各個(gè)簇的質(zhì)心不再發(fā)生變化。關(guān)于算法的收斂，在2.5部分討論。

2.6 代價(jià)函數(shù)與算法收斂

Kmeans算法的代價(jià)函數(shù)比較簡(jiǎn)單，就是每個(gè)樣本點(diǎn)與其所屬質(zhì)心的距離的平方和（誤差平方和，Sum of Squared Error,簡(jiǎn)稱(chēng)SSE）:

J(c,u)=∑i=1k||X(i)−uc(i)||2

與其他機(jī)器學(xué)習(xí)算法一樣，我們要最小化這個(gè)代價(jià)函數(shù)，但這個(gè)函數(shù)沒(méi)有解析解，所以只能通過(guò)迭代求解的方法來(lái)逼近最優(yōu)解（這一點(diǎn)也和眾多機(jī)器學(xué)習(xí)算法一樣吧）。

所以你再看看算法步驟，其實(shí)就是一個(gè)迭代過(guò)程。

由于代價(jià)函數(shù)（SSE）是非凸函數(shù)，所以在運(yùn)用Kmeans算法時(shí)，不能保證收斂到一個(gè)全局的最優(yōu)解，我們得到的一般是一個(gè)局部的最優(yōu)解。

因此，為了取得比較好的效果，一般會(huì)多跑幾次算法（用不同的初始質(zhì)心），得到多個(gè)局部最優(yōu)解，比較它們的SSE，選取SSE最小的那個(gè)。

方法優(yōu)點(diǎn)：

• k-平均算法是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，算法簡(jiǎn)單、快速。
• 對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮的和高效率的，因?yàn)樗膹?fù)雜度大約是O（nkt），其中n是所有對(duì)象的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。通常k<<n。這個(gè)算法經(jīng)常以局部最優(yōu)結(jié)束。
• 算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)簇是密集的、球狀或團(tuán)狀的，而簇與簇之間區(qū)別明顯時(shí)，它的聚類(lèi)效果很好。

缺點(diǎn)：

• K 是事先給定的，這個(gè) K 值的選定是非常難以估計(jì)的；
• 對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同的聚類(lèi)結(jié)果。一旦初始值選擇的不好，可能無(wú)法得到有效的聚類(lèi)結(jié)果；
• 該算法需要不斷地進(jìn)行樣本分類(lèi)調(diào)整，不斷地計(jì)算調(diào)整后的新的聚類(lèi)中心，因此當(dāng)數(shù)據(jù)量非常大時(shí)，算法的時(shí)間開(kāi)銷(xiāo)是非常大的。
• 不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇；
• 對(duì)于”噪聲”和孤立點(diǎn)數(shù)據(jù)敏感，少量的該類(lèi)數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大影響。

3、Kmeans算法實(shí)現(xiàn)

采用python實(shí)現(xiàn)，基于numpy、sklearn庫(kù)，其中從sklearn.cluster中import KMeans。

為了可視化聚類(lèi)效果，對(duì)二維數(shù)據(jù)進(jìn)行聚類(lèi)并用matplot畫(huà)出數(shù)據(jù)不同簇的劃分。

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
@author: liuweima
"""
from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy
import time
import matplotlib.pyplot as plt
import sys
reload(sys)
sys.setdefaultencoding('utf8')
if __name__ == '__main__':
    ## step 1: 加載數(shù)據(jù)
    print "step 1: load data..."
    dataSet = []
    loss = []
    fileIn = open('path')
    for line in fileIn.readlines():
        lineArr = line.strip('\xef\xbb\xbf')      # '\xef\xbb\xbf'是BOM,標(biāo)識(shí)讀入的文件是UTF-8編碼，需strip()切掉
        lineArr = lineArr.strip().split('\t')      #注意自己文件中每行數(shù)據(jù)中是用什么對(duì)列數(shù)據(jù)做分割  建議先用Word 規(guī)范一下要打開(kāi)的文件
        dataSet.append([float(lineArr[0])/1.99759326,(float(lineArr[1])-100)/192230])   #數(shù)據(jù)規(guī)范化【0,1】
    print dataSet
    #設(shè)定不同k值以運(yùn)算
    for k in range(2,10):
        clf = KMeans(n_clusters=k) #設(shè)定k  ?。。。。。。。。?！這里就是調(diào)用KMeans算法
        s = clf.fit(dataSet) #加載數(shù)據(jù)集合
        numSamples = len(dataSet)
        centroids = clf.labels_
        print centroids,type(centroids) #顯示中心點(diǎn)
        print clf.inertia_  #顯示聚類(lèi)效果
        mark1 = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
        #畫(huà)出所有樣例點(diǎn) 屬于同一分類(lèi)的繪制同樣的顏色
        for i in xrange(numSamples):
            #markIndex = int(clusterAssment[i, 0])
            plt.plot(dataSet[i][0], dataSet[i][1], mark1[clf.labels_[i]]) #mark[markIndex])
        mark2 = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
        # 畫(huà)出質(zhì)點(diǎn)，用特殊圖型
        centroids =  clf.cluster_centers_
        for i in range(k):
            plt.plot(centroids[i][0], centroids[i][1], mark2[i], markersize = 12)
            #print centroids[i, 0], centroids[i, 1]
        plt.show()
        loss.append(clf.inertia_)
    for m in range(8):  #因?yàn)閗 取值是2-9 （！不包括10） m取值是0-7
        plt.plot(m,loss[m],'bo')
    plt.show()

質(zhì)心的初始化、最大迭代次數(shù)都為默認(rèn)值。

其中讀取文件一些坑已經(jīng)做了備注。整個(gè)kmeans算法不是很耗時(shí)，主要在畫(huà)圖上花費(fèi)時(shí)間。以我跑十萬(wàn)級(jí)別的數(shù)據(jù)來(lái)看，畫(huà)圖很費(fèi)時(shí)間。

聚類(lèi)結(jié)果圖 ，涉及業(yè)務(wù)，就不貼出了。

貼出，k取range(2,30)時(shí)，kmeans的誤差平方和（SSE）曲線圖。

為了彌補(bǔ)經(jīng)典kmeans聚類(lèi)算法的不足，出現(xiàn)了一些改進(jìn)型kmeans

比如二分Kmeans算法（bisectingKmeans）是為了克服Kmeans算法收斂于局部最小值的問(wèn)題而提出的。

該算法首先將所有點(diǎn)作為一個(gè)簇，然后將該簇一分為二。之后選擇其中一個(gè)簇繼續(xù)劃分，選擇哪一個(gè)簇進(jìn)行劃分

取決于對(duì)其劃分是否可以最大程度降低SSE的值，上述過(guò)程不斷迭代，直到得到用戶指定的簇?cái)?shù)目為止。

或者先使用MeanShift算法自動(dòng)生成k值刪除游離點(diǎn)。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論