1、基本概念

聚類分析簡稱聚類（clustering），是一個把數(shù)據(jù)集劃分成子集的過程，每一個子集是一個簇（cluster），使得簇中的樣本彼此相似，但與其他簇中的樣本不相似。

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

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

主要的聚類算法一般可以劃分為以下幾類：

2、Kmeans算法

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

算法步驟如下：

選擇K個點作為初始質(zhì)心（隨機產(chǎn)生或者從D中選取）  

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

2.1 k值選取

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

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

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

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

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

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

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

2.3 距離度量方法

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

在Kmeans算法中，一般采用歐氏距離計算兩個點的距離，歐氏距離如下：

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

舉個例子，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

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

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

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

2.4 質(zhì)心的計算

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

2.5 算法停止條件

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

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

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

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

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

所以你再看看算法步驟，其實就是一個迭代過程。

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

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

方法優(yōu)點：

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

缺點：

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

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

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

為了可視化聚類效果，對二維數(shù)據(jù)進行聚類并用matplot畫出數(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,標識讀入的文件是UTF-8編碼，需strip()切掉
        lineArr = lineArr.strip().split('\t')      #注意自己文件中每行數(shù)據(jù)中是用什么對列數(shù)據(jù)做分割  建議先用Word 規(guī)范一下要打開的文件
        dataSet.append([float(lineArr[0])/1.99759326,(float(lineArr[1])-100)/192230])   #數(shù)據(jù)規(guī)范化【0,1】
    print dataSet
    #設(shè)定不同k值以運算
    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) #顯示中心點
        print clf.inertia_  #顯示聚類效果
        mark1 = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
        #畫出所有樣例點 屬于同一分類的繪制同樣的顏色
        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']
        # 畫出質(zhì)點，用特殊圖型
        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):  #因為k 取值是2-9 （！不包括10） m取值是0-7
        plt.plot(m,loss[m],'bo')
    plt.show()

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

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

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

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

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

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

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

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

或者先使用MeanShift算法自動生成k值刪除游離點。

總結(jié)

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

最新評論