1 K-均值聚類（K-means）概述

1.1 聚類

“類”指的是具有相似性的集合。聚類是指將數(shù)據(jù)集劃分為若干類，使得類內(nèi)之間的數(shù)據(jù)最為相似，各類之間的數(shù)據(jù)相似度差別盡可能大。聚類分析就是以相似性為基礎(chǔ)，對(duì)數(shù)據(jù)集進(jìn)行聚類劃分，屬于無(wú)監(jiān)督學(xué)習(xí)。

1.2 無(wú)監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)

和KNN所不同，K-均值聚類屬于無(wú)監(jiān)督學(xué)習(xí)。那么監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)的區(qū)別在哪兒呢？監(jiān)督學(xué)習(xí)知道從對(duì)象（數(shù)據(jù)）中學(xué)習(xí)什么，而無(wú)監(jiān)督學(xué)習(xí)無(wú)需知道所要搜尋的目標(biāo)，它是根據(jù)算法得到數(shù)據(jù)的共同特征。比如用分類和聚類來(lái)說(shuō)，分類事先就知道所要得到的類別，而聚類則不一樣，只是以相似度為基礎(chǔ)，將對(duì)象分得不同的簇。

1.3 K-means

K-means算法具有悠久的歷史，并且也是最常用的聚類算法之一。K-means算法實(shí)施起來(lái)非常簡(jiǎn)單，因此，它非常適用于機(jī)器學(xué)習(xí)新手愛(ài)好者。
1967年，James MacQueen在他的論文《用于多變量觀測(cè)分類和分析的一些方法》中首次提出 “K-means”這一術(shù)語(yǔ)。1957年，貝爾實(shí)驗(yàn)室也將標(biāo)準(zhǔn)算法用于脈沖編碼調(diào)制技術(shù)。1965年，E.W. Forgy發(fā)表了本質(zhì)上相同的算法——Lloyd-Forgy算法。

k-means算法是一種簡(jiǎn)單的迭代型聚類算法，采用距離作為相似性指標(biāo)，從而發(fā)現(xiàn)給定數(shù)據(jù)集中的K個(gè)類，且每個(gè)類的中心是根據(jù)類中所有值的均值得到，每個(gè)類用聚類中心來(lái)描述。對(duì)于給定的一個(gè)包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X以及要分得的類別K,選取歐式距離作為相似度指標(biāo)，聚類目標(biāo)是使得各類的聚類平方和最小，即最小化：

1.4 K-Means算法的十大用例

K-means算法通?？梢詰?yīng)用于維數(shù)、數(shù)值都很小且連續(xù)的數(shù)據(jù)集，比如：從隨機(jī)分布的事物集合中將相同事物進(jìn)行分組。

• 1.文檔分類器
  根據(jù)標(biāo)簽、主題和文檔內(nèi)容將文檔分為多個(gè)不同的類別。這是一個(gè)非常標(biāo)準(zhǔn)且經(jīng)典的K-means算法分類問(wèn)題。首先，需要對(duì)文檔進(jìn)行初始化處理，將每個(gè)文檔都用矢量來(lái)表示，并使用術(shù)語(yǔ)頻率來(lái)識(shí)別常用術(shù)語(yǔ)進(jìn)行文檔分類，這一步很有必要。然后對(duì)文檔向量進(jìn)行聚類，識(shí)別文檔組中的相似性。 這里是用于文檔分類的K-means算法實(shí)現(xiàn)案例。

• 2.物品傳輸優(yōu)化
  使用K-means算法的組合找到無(wú)人機(jī)最佳發(fā)射位置和遺傳算法來(lái)解決旅行商的行車路線問(wèn)題，優(yōu)化無(wú)人機(jī)物品傳輸過(guò)程。

• 3.識(shí)別犯罪地點(diǎn)
  使用城市中特定地區(qū)的相關(guān)犯罪數(shù)據(jù)，分析犯罪類別、犯罪地點(diǎn)以及兩者之間的關(guān)聯(lián)，可以對(duì)城市或區(qū)域中容易犯罪的地區(qū)做高質(zhì)量的勘察。這是基于德里飛行情報(bào)區(qū)犯罪數(shù)據(jù)的論文。

• 4.客戶分類
  聚類能過(guò)幫助營(yíng)銷人員改善他們的客戶群（在其目標(biāo)區(qū)域內(nèi)工作），并根據(jù)客戶的購(gòu)買歷史、興趣或活動(dòng)監(jiān)控來(lái)對(duì)客戶類別做進(jìn)一步細(xì)分。這是關(guān)于電信運(yùn)營(yíng)商如何將預(yù)付費(fèi)客戶分為充值模式、發(fā)送短信和瀏覽網(wǎng)站幾個(gè)類別的白皮書。對(duì)客戶進(jìn)行分類有助于公司針對(duì)特定客戶群制定特定的廣告。

• 5.球隊(duì)狀態(tài)分析
  分析球員的狀態(tài)一直都是體育界的一個(gè)關(guān)鍵要素。隨著競(jìng)爭(zhēng)越來(lái)愈激烈，機(jī)器學(xué)習(xí)在這個(gè)領(lǐng)域也扮演著至關(guān)重要的角色。如果你想創(chuàng)建一個(gè)優(yōu)秀的隊(duì)伍并且喜歡根據(jù)球員狀態(tài)來(lái)識(shí)別類似的球員，那么K-means算法是一個(gè)很好的選擇。

• 6.保險(xiǎn)欺詐檢測(cè)
  機(jī)器學(xué)習(xí)在欺詐檢測(cè)中也扮演著一個(gè)至關(guān)重要的角色，在汽車、醫(yī)療保險(xiǎn)和保險(xiǎn)欺詐檢測(cè)領(lǐng)域中廣泛應(yīng)用。利用以往欺詐性索賠的歷史數(shù)據(jù)，根據(jù)它和欺詐性模式聚類的相似性來(lái)識(shí)別新的索賠。由于保險(xiǎn)欺詐可能會(huì)對(duì)公司造成數(shù)百萬(wàn)美元的損失，因此欺詐檢測(cè)對(duì)公司來(lái)說(shuō)至關(guān)重要。這是汽車保險(xiǎn)中使用聚類來(lái)檢測(cè)欺詐的白皮書。

• 7.乘車數(shù)據(jù)分析
  面向大眾公開(kāi)的Uber乘車信息的數(shù)據(jù)集，為我們提供了大量關(guān)于交通、運(yùn)輸時(shí)間、高峰乘車地點(diǎn)等有價(jià)值的數(shù)據(jù)集。分析這些數(shù)據(jù)不僅對(duì)Uber大有好處，而且有助于我們對(duì)城市的交通模式進(jìn)行深入的了解，來(lái)幫助我們做城市未來(lái)規(guī)劃。這是一篇使用單個(gè)樣本數(shù)據(jù)集來(lái)分析Uber數(shù)據(jù)過(guò)程的文章。

• 8.網(wǎng)絡(luò)分析犯罪分子
  網(wǎng)絡(luò)分析是從個(gè)人和團(tuán)體中收集數(shù)據(jù)來(lái)識(shí)別二者之間的重要關(guān)系的過(guò)程。網(wǎng)絡(luò)分析源自于犯罪檔案，該檔案提供了調(diào)查部門的信息，以對(duì)犯罪現(xiàn)場(chǎng)的罪犯進(jìn)行分類。這是一篇在學(xué)術(shù)環(huán)境中，如何根據(jù)用戶數(shù)據(jù)偏好對(duì)網(wǎng)絡(luò)用戶進(jìn)行 cyber-profile的論文。

• 9.呼叫記錄詳細(xì)分析
  通話詳細(xì)記錄（CDR）是電信公司在對(duì)用戶的通話、短信和網(wǎng)絡(luò)活動(dòng)信息的收集。將通話詳細(xì)記錄與客戶個(gè)人資料結(jié)合在一起，這能夠幫助電信公司對(duì)客戶需求做更多的預(yù)測(cè)。在這篇文章中，你將了解如何使用無(wú)監(jiān)督K-Means聚類算法對(duì)客戶一天24小時(shí)的活動(dòng)進(jìn)行聚類，來(lái)了解客戶數(shù)小時(shí)內(nèi)的使用情況。

• 10.IT警報(bào)的自動(dòng)化聚類
  大型企業(yè)IT基礎(chǔ)架構(gòu)技術(shù)組件（如網(wǎng)絡(luò)，存儲(chǔ)或數(shù)據(jù)庫(kù)）會(huì)生成大量的警報(bào)消息。由于警報(bào)消息可以指向具體的操作，因此必須對(duì)警報(bào)信息進(jìn)行手動(dòng)篩選，確保后續(xù)過(guò)程的優(yōu)先級(jí)。對(duì)數(shù)據(jù)進(jìn)行聚類可以對(duì)警報(bào)類別和平均修復(fù)時(shí)間做深入了解，有助于對(duì)未來(lái)故障進(jìn)行預(yù)測(cè)。

1.5 應(yīng)用示例

想要將一組數(shù)據(jù)，分為三類，粉色數(shù)值大，黃色數(shù)值小。
最開(kāi)心先初始化，這里面選了最簡(jiǎn)單的 3，2，1 作為各類的初始值。
剩下的數(shù)據(jù)里，每個(gè)都與三個(gè)初始值計(jì)算距離，然后歸類到離它最近的初始值所在類別。

分好類后，計(jì)算每一類的平均值，作為新一輪的中心點(diǎn)。

1.6 算法流程

K-means是一個(gè)反復(fù)迭代的過(guò)程，算法分為四個(gè)步驟：
1） 選取數(shù)據(jù)空間中的K個(gè)對(duì)象作為初始中心，每個(gè)對(duì)象代表一個(gè)聚類中心；
2） 對(duì)于樣本中的數(shù)據(jù)對(duì)象，根據(jù)它們與這些聚類中心的歐氏距離，按距離最近的準(zhǔn)則將它們分到距離它們最近的聚類中心（最相似）所對(duì)應(yīng)的類；
3） 更新聚類中心：將每個(gè)類別中所有對(duì)象所對(duì)應(yīng)的均值作為該類別的聚類中心，計(jì)算目標(biāo)函數(shù)的值；
4） 判斷聚類中心和目標(biāo)函數(shù)的值是否發(fā)生改變，若不變，則輸出結(jié)果，若改變，則返回2）。

用以下例子加以說(shuō)明：

圖1：給定一個(gè)數(shù)據(jù)集；
圖2：根據(jù)K = 5初始化聚類中心，保證　聚類中心處于數(shù)據(jù)空間內(nèi)；
圖3：根據(jù)計(jì)算類內(nèi)對(duì)象和聚類中心之間的相似度指標(biāo)，將數(shù)據(jù)進(jìn)行劃分；
圖4：將類內(nèi)之間數(shù)據(jù)的均值作為聚類中心，更新聚類中心。
最后判斷算法結(jié)束與否即可，目的是為了保證算法的收斂。

2 Python實(shí)現(xiàn)

2.1 計(jì)算過(guò)程

st=>start: 開(kāi)始
e=>end: 結(jié)束
op1=>operation: 讀入數(shù)據(jù)
op2=>operation: 隨機(jī)初始化聚類中心
cond=>condition: 是否聚類是否變化
op3=>operation: 尋找最近的點(diǎn)加入聚類
op4=>operation: 更新聚類中心
op5=>operation: 輸出結(jié)果

st->op1->op2->op3->op4->cond
cond(yes)->op3
cond(no)->op5->e

2.2 輸入樣例

15.55,28.65
14.9,27.55
14.45,28.35
14.15,28.8
13.75,28.05
13.35,28.45
13,29.15
13.45,27.5
13.6,26.5
12.8,27.35

2.3 代碼實(shí)現(xiàn)

__author__ = 'Bobby'

from numpy import *
import matplotlib.pyplot as plt
import time

INF = 9999999.0

def loadDataSet(fileName, splitChar='\t'):
    """
    輸入：文件名
    輸出：數(shù)據(jù)集
    描述：從文件讀入數(shù)據(jù)集
    """
    dataSet = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curline = line.strip().split(splitChar)
            fltline = list(map(float, curline))
            dataSet.append(fltline)
    return dataSet

def createDataSet():
    """
    輸出：數(shù)據(jù)集
    描述：生成數(shù)據(jù)集
    """
    dataSet = [[0.0, 2.0],
               [0.0, 0.0],
               [1.5, 0.0],
               [5.0, 0.0],
               [5.0, 2.0]]
    return dataSet

def distEclud(vecA, vecB):
    """
    輸入：向量A, 向量B
    輸出：兩個(gè)向量的歐式距離
    """
    return sqrt(sum(power(vecA - vecB, 2)))

def randCent(dataSet, k):
    """
    輸入：數(shù)據(jù)集, 聚類個(gè)數(shù)
    輸出：k個(gè)隨機(jī)質(zhì)心的矩陣
    """
    n = shape(dataSet)[1]
    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, 1)
    return centroids

def kMeans(dataSet, k, distMeans=distEclud, createCent=randCent):
    """
    輸入：數(shù)據(jù)集, 聚類個(gè)數(shù), 距離計(jì)算函數(shù), 生成隨機(jī)質(zhì)心函數(shù)
    輸出：質(zhì)心矩陣, 簇分配和距離矩陣
    """
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m, 2)))
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m): # 尋找最近的質(zhì)心
            minDist = INF
            minIndex = -1
            for j in range(k):
                distJI = distMeans(centroids[j, :], dataSet[i, :])
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist**2
        for cent in range(k): # 更新質(zhì)心的位置
            ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]]
            centroids[cent, :] = mean(ptsInClust, axis=0)
    return centroids, clusterAssment

def plotFeature(dataSet, centroids, clusterAssment):
    m = shape(centroids)[0]
    fig = plt.figure()
    scatterMarkers = ['s', 'o', '^', '8', 'p', 'd', 'v', 'h', '>', '<']
    scatterColors = ['blue', 'green', 'yellow', 'purple', 'orange', 'black', 'brown']
    ax = fig.add_subplot(111)
    for i in range(m):
        ptsInCurCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]
        markerStyle = scatterMarkers[i % len(scatterMarkers)]
        colorSytle = scatterColors[i % len(scatterColors)]
        ax.scatter(ptsInCurCluster[:, 0].flatten().A[0], ptsInCurCluster[:, 1].flatten().A[0], marker=markerStyle, c=colorSytle, s=90)
    ax.scatter(centroids[:, 0].flatten().A[0], centroids[:, 1].flatten().A[0], marker='+', c='red', s=300)

def main():
    #dataSet = loadDataSet('testSet2.txt')
    dataSet = loadDataSet('788points.txt', splitChar=',')
    #dataSet = createDataSet()
    dataSet = mat(dataSet)
    resultCentroids, clustAssing = kMeans(dataSet, 6)
    print('*******************')
    print(resultCentroids)
    print('*******************')
    plotFeature(dataSet, resultCentroids, clustAssing)

if __name__ == '__main__':
    start = time.clock()
    main()
    end = time.clock()
    print('finish all in %s' % str(end - start))
    plt.show()

2.4 輸出樣例

*******************
[[32.69453125 22.13789062]
 [33.14278846  8.79375   ]
 [21.16041667 22.89895833]
 [ 9.25928144 22.98113772]
 [ 9.81847826  7.59311594]
 [19.0637931   7.06551724]]
*******************
finish all in 2.270720974