1 K-均值聚類（K-means）概述
1.1 聚類
“類”指的是具有相似性的集合。聚類是指將數(shù)據(jù)集劃分為若干類橱赠，使得類內(nèi)之間的數(shù)據(jù)最為相似，各類之間的數(shù)據(jù)相似度差別盡可能大押袍。聚類分析就是以相似性為基礎(chǔ)甸饱，對數(shù)據(jù)集進(jìn)行聚類劃分，屬于無監(jiān)督學(xué)習(xí)撑碴。
1.2 無監(jiān)督學(xué)習(xí)和監(jiān)督學(xué)習(xí)
和KNN所不同撑教，K-均值聚類屬于無監(jiān)督學(xué)習(xí)。那么監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的區(qū)別在哪兒呢醉拓？監(jiān)督學(xué)習(xí)知道從對象（數(shù)據(jù)）中學(xué)習(xí)什么伟姐，而無監(jiān)督學(xué)習(xí)無需知道所要搜尋的目標(biāo)，它是根據(jù)算法得到數(shù)據(jù)的共同特征亿卤。比如用分類和聚類來說愤兵，分類事先就知道所要得到的類別，而聚類則不一樣排吴，只是以相似度為基礎(chǔ)秆乳，將對象分得不同的簇。
1.3 K-means
K-means算法具有悠久的歷史，并且也是最常用的聚類算法之一屹堰。K-means算法實(shí)施起來非常簡單肛冶，因此，它非常適用于機(jī)器學(xué)習(xí)新手愛好者扯键。
1967年淑趾，James MacQueen在他的論文《用于多變量觀測分類和分析的一些方法》中首次提出 “K-means”這一術(shù)語。1957年忧陪，貝爾實(shí)驗(yàn)室也將標(biāo)準(zhǔn)算法用于脈沖編碼調(diào)制技術(shù)扣泊。1965年，E.W. Forgy發(fā)表了本質(zhì)上相同的算法——Lloyd-Forgy算法嘶摊。
k-means算法是一種簡單的迭代型聚類算法延蟹，采用距離作為相似性指標(biāo)，從而發(fā)現(xiàn)給定數(shù)據(jù)集中的K個(gè)類叶堆，且每個(gè)類的中心是根據(jù)類中所有值的均值得到阱飘，每個(gè)類用聚類中心來描述。對于給定的一個(gè)包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X以及要分得的類別K,選取歐式距離作為相似度指標(biāo)虱颗，聚類目標(biāo)是使得各類的聚類平方和最小沥匈，即最小化：
結(jié)合最小二乘法和拉格朗日原理，聚類中心為對應(yīng)類別中各數(shù)據(jù)點(diǎn)的平均值忘渔，同時(shí)為了使得算法收斂高帖，在迭代過程中，應(yīng)使最終的聚類中心盡可能的不變畦粮。
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算法分類問題员舵。首先，需要對文檔進(jìn)行初始化處理，將每個(gè)文檔都用矢量來表示，并使用術(shù)語頻率來識(shí)別常用術(shù)語進(jìn)行文檔分類贡翘，這一步很有必要。然后對文檔向量進(jìn)行聚類两疚，識(shí)別文檔組中的相似性床估。 這里是用于文檔分類的K-means算法實(shí)現(xiàn)案例含滴。2.物品傳輸優(yōu)化
使用K-means算法的組合找到無人機(jī)最佳發(fā)射位置和遺傳算法來解決旅行商的行車路線問題诱渤，優(yōu)化無人機(jī)物品傳輸過程。3.識(shí)別犯罪地點(diǎn)
使用城市中特定地區(qū)的相關(guān)犯罪數(shù)據(jù)谈况，分析犯罪類別勺美、犯罪地點(diǎn)以及兩者之間的關(guān)聯(lián)递胧，可以對城市或區(qū)域中容易犯罪的地區(qū)做高質(zhì)量的勘察。這是基于德里飛行情報(bào)區(qū)犯罪數(shù)據(jù)的論文赡茸。4.客戶分類
聚類能過幫助營銷人員改善他們的客戶群（在其目標(biāo)區(qū)域內(nèi)工作）缎脾，并根據(jù)客戶的購買歷史、興趣或活動(dòng)監(jiān)控來對客戶類別做進(jìn)一步細(xì)分占卧。這是關(guān)于電信運(yùn)營商如何將預(yù)付費(fèi)客戶分為充值模式遗菠、發(fā)送短信和瀏覽網(wǎng)站幾個(gè)類別的白皮書。對客戶進(jìn)行分類有助于公司針對特定客戶群制定特定的廣告华蜒。5.球隊(duì)狀態(tài)分析
分析球員的狀態(tài)一直都是體育界的一個(gè)關(guān)鍵要素辙纬。隨著競爭越來愈激烈，機(jī)器學(xué)習(xí)在這個(gè)領(lǐng)域也扮演著至關(guān)重要的角色叭喜。如果你想創(chuàng)建一個(gè)優(yōu)秀的隊(duì)伍并且喜歡根據(jù)球員狀態(tài)來識(shí)別類似的球員贺拣，那么K-means算法是一個(gè)很好的選擇。6.保險(xiǎn)欺詐檢測
機(jī)器學(xué)習(xí)在欺詐檢測中也扮演著一個(gè)至關(guān)重要的角色捂蕴，在汽車譬涡、醫(yī)療保險(xiǎn)和保險(xiǎn)欺詐檢測領(lǐng)域中廣泛應(yīng)用。利用以往欺詐性索賠的歷史數(shù)據(jù)啥辨，根據(jù)它和欺詐性模式聚類的相似性來識(shí)別新的索賠涡匀。由于保險(xiǎn)欺詐可能會(huì)對公司造成數(shù)百萬美元的損失，因此欺詐檢測對公司來說至關(guān)重要溉知。這是汽車保險(xiǎn)中使用聚類來檢測欺詐的白皮書渊跋。7.乘車數(shù)據(jù)分析
面向大眾公開的Uber乘車信息的數(shù)據(jù)集，為我們提供了大量關(guān)于交通着倾、運(yùn)輸時(shí)間拾酝、高峰乘車地點(diǎn)等有價(jià)值的數(shù)據(jù)集。分析這些數(shù)據(jù)不僅對Uber大有好處卡者，而且有助于我們對城市的交通模式進(jìn)行深入的了解蒿囤，來幫助我們做城市未來規(guī)劃。這是一篇使用單個(gè)樣本數(shù)據(jù)集來分析Uber數(shù)據(jù)過程的文章崇决。8.網(wǎng)絡(luò)分析犯罪分子
網(wǎng)絡(luò)分析是從個(gè)人和團(tuán)體中收集數(shù)據(jù)來識(shí)別二者之間的重要關(guān)系的過程材诽。網(wǎng)絡(luò)分析源自于犯罪檔案，該檔案提供了調(diào)查部門的信息恒傻，以對犯罪現(xiàn)場的罪犯進(jìn)行分類脸侥。這是一篇在學(xué)術(shù)環(huán)境中，如何根據(jù)用戶數(shù)據(jù)偏好對網(wǎng)絡(luò)用戶進(jìn)行 cyber-profile的論文盈厘。9.呼叫記錄詳細(xì)分析
通話詳細(xì)記錄（CDR）是電信公司在對用戶的通話睁枕、短信和網(wǎng)絡(luò)活動(dòng)信息的收集。將通話詳細(xì)記錄與客戶個(gè)人資料結(jié)合在一起，這能夠幫助電信公司對客戶需求做更多的預(yù)測外遇。在這篇文章中注簿，你將了解如何使用無監(jiān)督K-Means聚類算法對客戶一天24小時(shí)的活動(dòng)進(jìn)行聚類，來了解客戶數(shù)小時(shí)內(nèi)的使用情況跳仿。10.IT警報(bào)的自動(dòng)化聚類
大型企業(yè)IT基礎(chǔ)架構(gòu)技術(shù)組件（如網(wǎng)絡(luò)诡渴，存儲(chǔ)或數(shù)據(jù)庫）會(huì)生成大量的警報(bào)消息。由于警報(bào)消息可以指向具體的操作菲语，因此必須對警報(bào)信息進(jìn)行手動(dòng)篩選妄辩，確保后續(xù)過程的優(yōu)先級。對數(shù)據(jù)進(jìn)行聚類可以對警報(bào)類別和平均修復(fù)時(shí)間做深入了解山上，有助于對未來故障進(jìn)行預(yù)測恩袱。
1.5 應(yīng)用示例
想要將一組數(shù)據(jù)，分為三類胶哲，粉色數(shù)值大畔塔，黃色數(shù)值小。
最開心先初始化鸯屿，這里面選了最簡單的 3澈吨，2，1 作為各類的初始值寄摆。
剩下的數(shù)據(jù)里谅辣，每個(gè)都與三個(gè)初始值計(jì)算距離，然后歸類到離它最近的初始值所在類別婶恼。
分好類后桑阶，計(jì)算每一類的平均值，作為新一輪的中心點(diǎn)勾邦。
幾輪之后蚣录，分組不再變化了，就可以停止了眷篇。
1.6 算法流程
K-means是一個(gè)反復(fù)迭代的過程萎河，算法分為四個(gè)步驟：
1） 選取數(shù)據(jù)空間中的K個(gè)對象作為初始中心，每個(gè)對象代表一個(gè)聚類中心蕉饼；
2） 對于樣本中的數(shù)據(jù)對象，根據(jù)它們與這些聚類中心的歐氏距離昧港，按距離最近的準(zhǔn)則將它們分到距離它們最近的聚類中心（最相似）所對應(yīng)的類；
3） 更新聚類中心：將每個(gè)類別中所有對象所對應(yīng)的均值作為該類別的聚類中心创肥，計(jì)算目標(biāo)函數(shù)的值值朋；
4） 判斷聚類中心和目標(biāo)函數(shù)的值是否發(fā)生改變，若不變塔猾，則輸出結(jié)果稽坤，若改變丈甸，則返回2）。
用以下例子加以說明：
圖1：給定一個(gè)數(shù)據(jù)集尿褪；
圖2：根據(jù)K = 5初始化聚類中心睦擂，保證 聚類中心處于數(shù)據(jù)空間內(nèi)；
圖3：根據(jù)計(jì)算類內(nèi)對象和聚類中心之間的相似度指標(biāo)杖玲，將數(shù)據(jù)進(jìn)行劃分顿仇；
圖4：將類內(nèi)之間數(shù)據(jù)的均值作為聚類中心，更新聚類中心摆马。
最后判斷算法結(jié)束與否即可臼闻，目的是為了保證算法的收斂。
2 Python實(shí)現(xiàn)
2.1 計(jì)算過程
st=>start: 開始
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
