算法簡介

K-means算法是硬聚類算法懂拾，是典型的基于原型的目標函數(shù)聚類方法的代表，它是數(shù)據(jù)點到原型的某種距離作為優(yōu)化的目標函數(shù)，利用函數(shù)求極值的方法得到迭代運算的調(diào)整規(guī)則欲鹏。K-means算法以歐式距離作為相似度測度屿聋，它是求對應某一初始聚類中心向量V最優(yōu)分類空扎，使得評價指標J最小藏鹊。算法采用誤差平方和準則函數(shù)作為聚類準則函數(shù)。

聚類問題

通常转锈，人們根據(jù)樣本間的某種距離或者相似性來定義聚類盘寡，即把相似的（或距離近的）樣本聚為同一類，而把不相似的（或距離遠的）樣本歸在其他類撮慨。

所謂聚類問題竿痰，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性砌溺，使用某種算法將D劃分成k個子集影涉，要求每個子集內(nèi)部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高规伐。其中每個子集叫做一個簇蟹倾。

k-means算法是一種很常見的聚類算法，它的基本思想是：通過迭代尋找k個聚類的一種劃分方案楷力，使得用這k個聚類的均值來代表相應各類樣本時所得的總體誤差最小喊式。

算法步驟

1. 從D中隨機取k個元素，作為k個簇的各自的中心萧朝。

2. 分別計算剩下的元素到k個簇中心的相異度岔留，將這些元素分別劃歸到相異度最低的簇。

3. 根據(jù)聚類結(jié)果检柬，重新計算k個簇各自的中心献联，計算方法是取簇中所有元素各自維度的算術(shù)平均數(shù)。

4. 將D中全部元素按照新的中心重新聚類何址。

5. 重復第4步里逆，直到聚類結(jié)果不再變化。

6. 將結(jié)果輸出用爪。

算法實現(xiàn)

import numpy as np
import random
import matplotlib.pyplot as plt

def euclDistance(vector1, vector2):
    '''
    計算兩個元素之間的歐氏距離
    '''
    return np.sqrt(np.sum(np.power(vector2 - vector1, 2)))

def initCentroids(dataSet, k):
    '''
    隨機生成K個初始質(zhì)心
    '''
    numSamples, dim = dataSet.shape #得到dataSet的行和列
    index = random.sample(range(numSamples),k) #隨機生成K個不重復的實數(shù)原押，返回一個列表。
    centroids = np.array([dataSet[i,:] for i in index]) #創(chuàng)建K個初始質(zhì)心放在一個數(shù)組中
    return centroids

def kmeans(dataSet, k):
    numSamples = dataSet.shape[0]
    clusterAssment = np.zeros((numSamples, 2)) #創(chuàng)建一個numSamples行2列的全零矩陣用于存儲元素的所屬簇和元素本身
    centroids = initCentroids(dataSet, k) #初始質(zhì)心
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(numSamples):
            #遍歷每一個元素
            minDistance = float("inf")  #設(shè)定元素與質(zhì)心之間的初始距離為無窮大
            ownGroup = 0 #設(shè)定元素初始所屬簇
            for j in range(k):
                #計算第i個元素分別與k個質(zhì)心的距離
                distance = euclDistance(centroids[j, :], dataSet[i, :])
                if distance < minDistance:
                    #把元素歸為與質(zhì)心歐式距離最小的那個簇中
                    minDistance = distance
                    ownGroup = j
            if clusterAssment[i, 1] != ownGroup:
                #判斷該元素所屬組是否發(fā)生變化偎血，若變化了就繼續(xù)進行循環(huán)诸衔，直到每個元素所屬組不在變化就結(jié)束循環(huán)
                clusterAssment[i, 1] = ownGroup
                clusterChanged = True
        for j in range(k):
            '''
            遍歷完所有元素后更新K個質(zhì)心
            clusterAssment[:, 1] == j #判斷每個元素是否屬于j組，是的話就返回True,否則返回False
            np.nonzero(clusterAssment[:, 1] == j)[0] #返回一個有兩個元素的tuple,第一個元素是這個數(shù)組(元素是布爾值的形式)中元素是True的下標
            dataSet[np.nonzero(clusterAssment[:, 1] == j)[0]] #得到屬于某個組的全部元素
            np.mean(pointsInCluster, axis=0) #計算每一個簇中所有元素的均值作為各自簇的新的質(zhì)心
            '''
            pointsInCluster = dataSet[np.nonzero(clusterAssment[:, 1] == j)[0]]
            centroids[j, :] = np.mean(pointsInCluster, axis=0)
    return centroids,clusterAssment

def showCluster(dataSet, k, centroids, clusterAssment):
    '''
    可視化
    '''
    numSamples, dim = dataSet.shape
    if dim != 2:
        print "Sorry! I can not draw because the dimension of your data is not 2!"
        return 1
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print "Sorry! Your k is too large! please contact Zouxy"
        return 1
    for i in xrange(numSamples):
        #不同的組顯示不同的顏色("o"表示形狀為圓形颇玷，后面表示不同的顏色)
        markIndex = int(clusterAssment[i, 1])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    for i in range(k):
        # 標識出質(zhì)心("D"表示形狀為菱形笨农，后面表示不同的顏色)
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

    plt.show()

if __name__ == "__main__":
    '''
    需求是給一個數(shù)據(jù)集，根據(jù)各個元素之間的關(guān)系把具有相似屬性的元素歸為一類帖渠，就是把數(shù)據(jù)集根據(jù)不同的分類要求分成不同的類谒亦。
    '''
    dataSet = []
    f = open("數(shù)據(jù)集在很多博客里面可以找到，在此就不貼出了",'r')
    for line in f.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])
    dataSet = np.array(dataSet)
    k = 4
    centroids, clusterAssment = kmeans(dataSet, k)
    showCluster(dataSet, k, centroids, clusterAssment)

結(jié)果展示

看起來還不錯

jieguo

算法評估

1. 在 K-means 算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的份招。很多時候切揭，事先并不知道給定的數(shù)據(jù)集應該分成多少個類別才最合適。這也是 K-means 算法的一個不足锁摔。有的算法是通過類的自動合并和分裂伴箩，得到較為合理的類型數(shù)目 K，例如 ISODATA 算法鄙漏。關(guān)于 K-means 算法中聚類數(shù)目K 值的確定在文獻中，是根據(jù)方差分析理論棺蛛，應用混合 F統(tǒng)計量來確定最佳分類數(shù)怔蚌，并應用了模糊劃分熵來驗證最佳分類數(shù)的正確性。在文獻中旁赊，使用了一種結(jié)合全協(xié)方差矩陣的 RPCL 算法桦踊，并逐步刪除那些只包含少量訓練數(shù)據(jù)的類。而文獻中使用的是一種稱為次勝者受罰的競爭學習規(guī)則终畅，來自動決定類的適當數(shù)目籍胯。它的思想是：對每個輸入而言，不僅競爭獲勝單元的權(quán)值被修正以適應輸入值离福，而且對次勝單元采用懲罰的方法使之遠離輸入值杖狼。
2. 在 K-means 算法中，首先需要根據(jù)初始聚類中心來確定一個初始劃分妖爷，然后對初始劃分進行優(yōu)化蝶涩。這個初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始值選擇的不好絮识，可能無法得到有效的聚類結(jié)果绿聘，這也成為 K-means算法的一個主要問題。對于該問題的解決次舌，許多算法采用遺傳算法（GA）熄攘，例如文獻 中采用遺傳算法（GA）進行初始化，以內(nèi)部聚類準則作為評價指標彼念。
3. 從 K-means 算法框架可以看出挪圾，該算法需要不斷地進行樣本分類調(diào)整，不斷地計算調(diào)整后的新的聚類中心国拇，因此當數(shù)據(jù)量非常大時洛史，算法的時間開銷是非常大的。所以需要對算法的時間復雜度進行分析酱吝、改進也殖，提高算法應用范圍。在文獻中從該算法的時間復雜度進行分析考慮，通過一定的相似性準則來去掉聚類中心的侯選集忆嗜。而在文獻中己儒，使用的 K-means 算法是對樣本數(shù)據(jù)進行聚類，無論是初始點的選擇還是一次迭代完成時對數(shù)據(jù)的調(diào)整捆毫，都是建立在隨機選取的樣本數(shù)據(jù)的基礎(chǔ)之上闪湾，這樣可以提高算法的收斂速度。

應用場景

分析一個公司的客戶分類绩卤，這樣可以對不同的客戶使用不同的商業(yè)策略途样，或是電子商務(wù)中分析商品相似度，歸類商品濒憋，從而可以使用一些不同的銷售策略何暇，等等。