任務(wù)
- 利用K-均值聚類算法對(duì)未標(biāo)注數(shù)據(jù)分組
- 對(duì)聚類得到的簇進(jìn)行后處理
- 二分K-均值聚類算法
思想
- 聚類算法幾乎可以用于任何對(duì)象侦啸，簇內(nèi)對(duì)象越相似，聚類效果越好偎痛。
- 相似度取決于相似度的計(jì)算方法衅鹿，根據(jù)具體應(yīng)用選擇相似度的計(jì)算方法
- K-均值可以發(fā)現(xiàn)k個(gè)不同的簇，且每個(gè)簇的中心都采用簇中所含值的均值計(jì)算而成
- 簇識(shí)別給出簇類結(jié)果的含義偷俭。
- 聚類與分類最大區(qū)別在于浪讳，分類的目標(biāo)事先知道缰盏，而聚類是未知的。聚類產(chǎn)生的結(jié)果與分類相同，只是類別沒有預(yù)先定義口猜。所以聚類算法也叫無監(jiān)督分類负溪。
缺點(diǎn)與改進(jìn)
- 簡(jiǎn)單K-均值算法的一些缺陷，可以用二分K-均值算法（bisecting k-means）解決
一济炎、K-均值聚類算法的構(gòu)建
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：容易實(shí)現(xiàn)
缺點(diǎn)：可能收斂與局部最小值川抡，在大規(guī)模數(shù)據(jù)集上收斂較慢
使用范圍
數(shù)值型數(shù)據(jù)
構(gòu)建步驟
給定數(shù)據(jù)集k個(gè)簇，每個(gè)簇通過其質(zhì)心（centroid）,即簇中所有點(diǎn)的中心來描述
偽代碼：
創(chuàng)建k個(gè)點(diǎn)作為起始質(zhì)心（經(jīng)常是隨機(jī)選擇）
當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生變化時(shí)：
對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn):
對(duì)每個(gè)質(zhì)心：
計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)之間的距離
將數(shù)據(jù)點(diǎn)分配到距離其最近的簇
對(duì)每一個(gè)簇须尚，計(jì)算簇中所有點(diǎn)的均值崖堤，并將均值作為該簇的中心
編寫輔助函數(shù)：
from numpy import *
"""
創(chuàng)建k個(gè)點(diǎn)作為起始質(zhì)心（經(jīng)常是隨機(jī)選擇）
當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生變化時(shí)：
對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn):
對(duì)每個(gè)質(zhì)心：
計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)之間的距離
將數(shù)據(jù)點(diǎn)分配到距離其最近的簇
對(duì)每一個(gè)簇，計(jì)算簇中所有點(diǎn)的均值耐床，并將均值作為該簇的中心
"""
#輔助函數(shù)
def loadDataSet(fileName): #將文本文件轉(zhuǎn)換成列表的列表格式
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = list(map(float, curLine))
dataMat.append(fltLine)
return dataMat
def distEclud(vecA, vecB): #計(jì)算兩個(gè)向量之間的歐氏距離
return sqrt(sum(power(vecA - vecB, 2)))
def randCent(dataSet, k):
#構(gòu)建一個(gè)包含k個(gè)隨機(jī)質(zhì)心的集合
#隨機(jī)質(zhì)心必須在整個(gè)數(shù)據(jù)集的邊界之內(nèi)
n = shape(dataSet)[1] #獲得列數(shù)
centroids = mat(zeros((k, n))) #構(gòu)建k行n列的質(zhì)心
for j in range(n):
minJ = min(dataSet[:,j]) #獲得數(shù)據(jù)集中每一個(gè)維（每列）的最小值
rangeJ = float(max(dataSet[:,j] - minJ)) #獲得數(shù)據(jù)集中每一個(gè)維（每列）的取值范圍
centroids[:,j] = minJ + rangeJ * random.rand(k,1) #生成[0, 1.0]之間的隨機(jī)數(shù)
#通過取值范圍和最小值密幔，確保隨機(jī)點(diǎn)在數(shù)據(jù)的邊界之內(nèi)
return centroids
測(cè)試運(yùn)行：
In [66]: import kMeans
In [67]: from numpy import *
In [68]: datMat = mat(kMeans.loadDataSet('testSet.txt'))
In [69]: min(datMat[:,0])
Out[69]: matrix([[-5.379713]])
In [70]: min(datMat[:,1])
Out[70]: matrix([[-4.232586]])
In [71]: max(datMat[:,1])
Out[71]: matrix([[5.1904]])
In [72]: max(datMat[:,0])
Out[72]: matrix([[4.838138]])
In [73]: kMeans.randCent(datMat, 2)
Out[73]:
matrix([[ 0.50953466, -3.71200331],
[ 3.98163501, -2.66656359]])
In [74]: kMeans.distEclud(datMat[0], datMat[1])
Out[74]: 5.184632816681332
實(shí)現(xiàn)完整的K-均值算法
- 該算法會(huì)構(gòu)建k個(gè)質(zhì)心，然后將每個(gè)點(diǎn)分配到最近的質(zhì)心撩轰，再重新計(jì)算胯甩。
- 這個(gè)過程重復(fù)無數(shù)次，直到數(shù)據(jù)點(diǎn)的簇分配結(jié)果不再改變?yōu)橹?/li>
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
m = shape(dataSet)[0] #獲得數(shù)據(jù)點(diǎn)的總數(shù)
clusterAssment = mat(zeros((m,2))) #創(chuàng)建一個(gè)矩陣來存儲(chǔ)每個(gè)點(diǎn)的簇分配結(jié)果：
#第一列記錄簇索引值堪嫂，第二列存儲(chǔ)誤差
#誤差：當(dāng)前點(diǎn)到簇質(zhì)心的距離偎箫。后面將使用該誤差來評(píng)價(jià)聚類的效果
centroids = createCent(dataSet, k)
#循環(huán)迭代，直到所有數(shù)據(jù)點(diǎn)的簇分配不再改變?yōu)橹? clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m): #對(duì)dataSet中的每個(gè)數(shù)據(jù)點(diǎn)
minDist = inf; minIndex = -1
#遍歷所有質(zhì)心皆串，并計(jì)算當(dāng)前點(diǎn)到每個(gè)質(zhì)心的距離
for j in range(k):
distJI = distMeas(centroids[j,:], dataSet[i,:])
if distJI < minDist:
minDist = distJI; minIndex = j
if clusterAssment[i,0] != minIndex:
clusterChanged = True
clusterAssment[i,:] = minIndex, minDist**2 #記錄簇索引值與誤差
print(centroids)
#最后淹办，遍歷所有質(zhì)心并更新它們的取值
for cent in range(k):
#通過數(shù)組過濾，獲得給定簇的所有點(diǎn)
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
centroids[cent,:] = mean(ptsInClust, axis=0) #計(jì)算所有點(diǎn)的均值愚战，axis=0
return centroids, clusterAssment
運(yùn)行：
In [83]: import importlib
In [84]: importlib.reload(kMeans)
Out[84]: <module 'kMeans' from 'D:\\Data\\File\\ML\\kMeans.py'>
In [85]: datMat = mat(kMeans.loadDataSet('testSet.txt'))
In [86]: myCentroids, clustAssing = kMeans.KMeans(datMat, 4)
[[ 1.00280717 0.11770989]
[-1.73165675 -3.43839335]
[ 2.55164274 -2.32833514]
[ 3.63722591 0.00961112]]
[[-0.93031861 2.9279739 ]
[-3.19984738 -2.96423548]
[ 2.7475792 -3.14066887]
[ 3.57953285 1.76429869]]
[[-1.94392522 2.96291883]
[-3.38237045 -2.9473363 ]
[ 2.72031426 -2.83200232]
[ 2.91014783 2.71954072]]
[[-2.46154315 2.78737555]
[-3.38237045 -2.9473363 ]
[ 2.80293085 -2.7315146 ]
[ 2.6265299 3.10868015]]
使用后處理來提高聚類性能
由于K-均值算法可能只收斂到局部最小值娇唯，而非全局最小值
聚類的目標(biāo)是在保持簇?cái)?shù)目不變的情況下，提高簇的質(zhì)量
將具有最大SSE值的簇寂玲，劃分為兩個(gè)簇
可以將最大簇包含的點(diǎn)過濾出來塔插，并且在這些點(diǎn)上再運(yùn)行K-均值算法
為了保持簇總數(shù)不變，將某兩個(gè)分錯(cuò)的簇的質(zhì)心進(jìn)行合并（兩種量化的方法）
- ①合并最近的質(zhì)心
通過計(jì)算所有質(zhì)心之間的距離拓哟，然后合并距離最近的兩個(gè)點(diǎn) - ②合并兩個(gè)使得SSE增幅最小的質(zhì)心
合并兩個(gè)簇想许，然后計(jì)算總SSE值。在所有可能的兩個(gè)簇上重復(fù)這個(gè)處理過程断序，直到找到合并最佳的兩個(gè)簇為止流纹。
二、二分K-均值算法（bisecting K-means）
思想
- 將所有點(diǎn)看成一個(gè)簇
- 對(duì)該簇一分為二
- 選擇可以最大程度降低SSE值的其中一個(gè)簇繼續(xù)進(jìn)行劃分
- 上述基于SSE的劃分過程不斷重復(fù)违诗，直到得到用戶指定的簇?cái)?shù)目為止
偽代碼
將所有點(diǎn)看成一個(gè)簇
當(dāng)簇?cái)?shù)目小于k時(shí)：
對(duì)于每一個(gè)簇：
計(jì)算總誤差
在給定的簇上面進(jìn)行K-均值聚類（k=2）
計(jì)算該簇一分為二之后的總誤差
選擇使得誤差最小的那個(gè)簇進(jìn)行劃分操作
另一種做法是選擇SSE最大的簇進(jìn)行劃分操作漱凝，直到簇?cái)?shù)目達(dá)到用戶指定的數(shù)目為止
代碼
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2)))
centroid0 = mean(dataSet, axis=0).tolist()[0] #計(jì)算整個(gè)數(shù)據(jù)集的質(zhì)心
centList = [centroid0] #創(chuàng)建一個(gè)初始化簇，并使用一個(gè)列表來保存所有質(zhì)心
for j in range(m): #遍歷數(shù)據(jù)集诸迟，計(jì)算每個(gè)點(diǎn)到質(zhì)心的誤差值（距離的平方）
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
# 嘗試劃分已有的每一個(gè)簇,尋找使得SSE降幅最大的那個(gè)簇,然后對(duì)其進(jìn)行2-Means聚類劃分
while (len(centList) < k):
lowestSSE = inf
for i in range(len(centList)):
#嘗試劃分每一個(gè)簇
ptsInCurrCluster = \
dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] #選擇每一個(gè)簇中的所有點(diǎn)茸炒，作為一個(gè)小的數(shù)據(jù)集
centroidMat, splitClustAss = \
kMeans(ptsInCurrCluster, 2, distMeas) #將該簇用kMeans一分為二愕乎，給出質(zhì)心，分配的質(zhì)心和誤差值
sseSplit = sum(splitClustAss[:,1]) #計(jì)算這個(gè)簇劃分成兩個(gè)簇以后的誤差的和
sseNotSplit = \
sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) #計(jì)算剩余未被劃分的簇（剩余數(shù)據(jù)集）的誤差的和
print("sseSplit, and sseNotSplit: ", sseSplit, sseNotSplit)
if (sseSplit + sseNotSplit) < lowestSSE: #如何該劃分的SSE值最小壁公，則本次劃分被保存
bestCentToSplit = i
bestNewCents = centroidMat.copy()
bestClustAss = splitClustAss.copy() #該簇的劃分情況
lowestSSE = sseSplit + sseNotSplit
#實(shí)際執(zhí)行劃分操作：把要?jiǎng)澐值拇刂械乃悬c(diǎn)的簇分配結(jié)果進(jìn)行修正
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] =\
len(centList) #新加簇的編號(hào)
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] =\
bestCentToSplit #劃分簇的編號(hào)
print('the bestCentToSplit is: ', bestCentToSplit)
print('the len of bestClustss is: ', len(bestClustAss))
#新的質(zhì)心被添加到centList
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0] #將cluster0的簇的質(zhì)心分配到原本簇的質(zhì)心
centList.append(bestNewCents[1,:].tolist()[0]) #將cluster1的簇質(zhì)心添加到centList
clusterAssment[nonzero(clusterAssment[:,0].A ==\
bestCentToSplit)[0], :] = bestClustAss #將原本被劃分的簇感论，更新簇分配的結(jié)果
return mat(centList), clusterAssment
運(yùn)行：
> importlib.reload(kMeans)
> datMat3=mat(kMeans.loadDataSet('testSet2.txt'))
> centList,myNewAssments = kMeans.biKmeans(datMat3,3)
sseSplit, and sseNotSplit: 570.7227574246755 0.0
the bestCentToSplit is: 0
the len of bestClustss is: 60
sseSplit, and sseNotSplit: 68.68654812621844 38.06295063565756
the bestCentToSplit is: 0
the len of bestClustss is: 40
sseSplit, and sseNotSplit: 22.971771896318412 68.68654812621844
the bestCentToSplit is: 1
the len of bestClustss is: 20
質(zhì)心：
In [96]: centList
Out[96]:
matrix([[ 2.02712544, 3.50141167],
[-2.94737575, 3.3263781 ],
[ 3.67574036, 2.82216836],
[-0.45965615, -2.7782156 ]])
質(zhì)心示意圖：
import matplotlib.pyplot as plt
centroids_x = centList[:,0]
centroids_y = centList[:,1]
plt.scatter(centroids_x.tolist(),centroids_y.tolist(),
marker = 'x',
s=150, linewidths = 5,
zorder = 10,
c=['green', 'red','blue','black'])
聚類會(huì)收斂到全局最小值，原始的kMeans()函數(shù)偶爾會(huì)陷入·局部最小值
