K-means聚類算法

算法優缺點：

優點：容易實現
缺點：可能收斂到局部最小值，在大規模數據集上收斂較慢
使用數據類型：數值型數據

算法思想

k-means算法實際上就是通過計算不同樣本間的距離來判斷他們的相近關系的，相近的就會放到同一個類別中去。

1.首先我們需要選擇一個k值，也就是我們希望把數據分成多少類，這里k值的選擇對結果的影響很大，Ng的課說的選擇方法有兩種一種是elbow method，簡單的說就是根據聚類的結果和k的函數關系判斷k為多少的時候效果最好。另一種則是根據具體的需求確定，比如說進行襯衫尺寸的聚類你可能就會考慮分成三類（L,M,S）等

2.然后我們需要選擇最初的聚類點（或者叫質心），這里的選擇一般是隨機選擇的，代碼中的是在數據范圍內隨機選擇，另一種是隨機選擇數據中的點。這些點的選擇會很大程度上影響到最終的結果，也就是說運氣不好的話就到局部最小值去了。這里有兩種處理方法，一種是多次取均值，另一種則是后面的改進算法（bisecting K-means）

3.終于我們開始進入正題了，接下來我們會把數據集中所有的點都計算下與這些質心的距離，把它們分到離它們質心最近的那一類中去。完成后我們則需要將每個簇算出平均值，用這個點作為新的質心。反復重復這兩步，直到收斂我們就得到了最終的結果。

函數

loadDataSet(fileName)
從文件中讀取數據集
distEclud(vecA, vecB)
計算距離，這里用的是歐氏距離，當然其他合理的距離都是可以的
randCent(dataSet, k)
隨機生成初始的質心，這里是雖具選取數據范圍內的點
kMeans(dataSet, k, distMeas=distEclud, createCent=randCent)
kmeans算法，輸入數據和k值。后面兩個事可選的距離計算方式和初始質心的選擇方式
show(dataSet, k, centroids, clusterAssment)
可視化結果

1.  1 #coding=utf-8 2 from numpy import * 3  4 def loadDataSet(fileName): 5     dataMat = [] 6     fr = open(fileName) 7     for line in fr.readlines(): 8         curLine = line.strip().split('/t') 9         fltLine = map(float, curLine)10         dataMat.append(fltLine)11     return dataMat12     13 #計算兩個向量的距離，用的是歐幾里得距離14 def distEclud(vecA, vecB):15     return sqrt(sum(power(vecA - vecB, 2)))16 17 #隨機生成初始的質心（ng的課說的初始方式是隨機選K個點）    18 def randCent(dataSet, k):19     n = shape(dataSet)[1]20     centroids = mat(zeros((k,n)))21     for j in range(n):22         minJ = min(dataSet[:,j])23         rangeJ = float(max(array(dataSet)[:,j]) - minJ)24         centroids[:,j] = minJ + rangeJ * random.rand(k,1)25     return centroids26     27 def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):28     m = shape(dataSet)[0]29     clusterAssment = mat(zeros((m,2)))#create mat to assign data points 30                                       #to a centroid, also holds SE of each point31     centroids = createCent(dataSet, k)32     clusterChanged = True33     while clusterChanged:34         clusterChanged = False35         for i in range(m):#for each data point assign it to the closest centroid36             minDist = inf37             minIndex = -138             for j in range(k):39                 distJI = distMeas(centroids[j,:],dataSet[i,:])40                 if distJI < minDist:41                     minDist = distJI; minIndex = j42             if clusterAssment[i,0] != minIndex: 43                 clusterChanged = True44             clusterAssment[i,:] = minIndex,minDist**245         PRint centroids46         for cent in range(k):#recalculate centroids47             ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster48             centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean 49     return centroids, clusterAssment50     51 def show(dataSet, k, centroids, clusterAssment):52     from matplotlib import pyplot as plt  53     numSamples, dim = dataSet.shape  54     mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']  55     for i in xrange(numSamples):  56         markIndex = int(clusterAssment[i, 0])  57         plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])  58     mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']  59     for i in range(k):  60         plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)  61     plt.show()62       63 def main():64     dataMat = mat(loadDataSet('testSet.txt'))65     myCentroids, clustAssing= kMeans(dataMat,4)66     print myCentroids67     show(dataMat, 4, myCentroids, clustAssing)  68     69     70 if __name__ == '__main__':71     main()