K-Means聚類算法
1、原理
第一步：選K個初始聚類中心，z1(1)能庆，z2(1)，…祷嘶，zK(1)，其中括號內(nèi)的序號為尋找聚類中心的迭代運算的次序號夺溢。聚類中心的向量值可任意設定论巍，例如可選開始的K個模式樣本的向量值作為初始聚類中心。
第二步：逐個將需分類的模式樣本{x}按最小距離準則分配給K個聚類中心中的某一個zj(1)风响。
假設i=j時嘉汰， ，則 钞诡，其中k為迭代運算的次序號郑现，第一次迭代k=1，Sj表示第j個聚類荧降，其聚類中心為zj接箫。
第三步：計算各個聚類中心的新的向量值，zj(k+1)朵诫，j=1,2,…,K
求各聚類域中所包含樣本的均值向量：
其中Nj為第j個聚類域Sj中所包含的樣本個數(shù)辛友。以均值向量作為新的聚類中心，可使如下聚類準則函數(shù)最屑舴怠：
在這一步中要分別計算K個聚類中的樣本均值向量废累，所以稱之為K-均值算法。
第四步：若 脱盲，j=1,2,…,K邑滨，則返回第二步，將模式樣本逐個重新分類钱反，重復迭代運算掖看；
若 ，j=1,2,…,K面哥，則算法收斂哎壳，計算結(jié)束尚卫。
2、程序?qū)崿F(xiàn)
def biKmeans(dataSet, k, distMeas=distEclud):
? ? m = shape(dataSet)[0]
? ? # 這里第一列為類別吱涉，第二列為SSE
? ? clusterAssment = mat(zeros((m,2)))
? ? # 看成一個簇是的質(zhì)心
? ? centroid0 = mean(dataSet, axis=0).tolist()[0]
? ? centList =[centroid0] #create a list with one centroid
? ? for j in range(m):? ? #計算只有一個簇是的誤差
? ? ? ? clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
? ? # 核心代碼
? ? while (len(centList) < k):
? ? ? ? lowestSSE = inf
? ? ? ? # 對于每一個質(zhì)心外里，嘗試的進行劃分
? ? ? ? for i in range(len(centList)):
? ? ? ? ? ? # 得到屬于該質(zhì)心的數(shù)據(jù)
? ? ? ? ? ? ptsInCurrCluster =\ dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
? ? ? ? ? ? # 對該質(zhì)心劃分成兩類
? ? ? ? ? ? centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
? ? ? ? ? ? # 計算該簇劃分后的SSE
? ? ? ? ? ? sseSplit = sum(splitClustAss[:,1])
? ? ? ? ? ? # 沒有參與劃分的簇的SSE
? ? ? ? ? ? sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
? ? ? ? ? ? print "sseSplit, and notSplit: ",sseSplit,sseNotSplit
? ? ? ? ? ? # 尋找最小的SSE進行劃分
? ? ? ? ? ? # 即對哪一個簇進行劃分后SSE最小
? ? ? ? ? ? if (sseSplit + sseNotSplit) < lowestSSE:
? ? ? ? ? ? ? ? bestCentToSplit = i
? ? ? ? ? ? ? ? bestNewCents = centroidMat
? ? ? ? ? ? ? ? bestClustAss = splitClustAss.copy()
? ? ? ? ? ? ? ? lowestSSE = sseSplit + sseNotSplit
? ? ? ? # 較難理解的部分
? ? ? ? bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
? ? ? ? bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
? ? ? ? print 'the bestCentToSplit is: ',bestCentToSplit
? ? ? ? print 'the len of bestClustAss is: ', len(bestClustAss)
? ? ? ? centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids
? ? ? ? centList.append(bestNewCents[1,:].tolist()[0])
? ? ? ? clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE
? ? return mat(centList), clusterAssment
3、結(jié)論1. K值需要預先給定特石，屬于預先知識级乐，很多情況下K值的估計是非常困難的县匠，對于像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行撒轮。對于可以確定K值不會太大但不明確精確的K值的場景乞旦，可以進行迭代運算，然后找出Cost Function最小時所對應的K值题山，這個值往往能較好的描述有多少個簇類兰粉。
2. K-Means算法對初始選取的聚類中心點是敏感的，不同的隨機種子點得到的聚類結(jié)果完全不同
3. K均值算法并不是很所有的數(shù)據(jù)類型顶瞳。它不能處理非球形簇、不同尺寸和不同密度的簇焰络，銀冠指定足夠大的簇的個數(shù)是他通常可以發(fā)現(xiàn)純子簇闪彼。
4. 對離群點的數(shù)據(jù)進行聚類時协饲，K均值也有問題畏腕，這種情況下茉稠，離群點檢測和刪除有很大的幫助。
