本文已參與「新人創作禮」活動，一起開啟掘金創作之路

K均值聚類演算法介紹

我們來介紹K均值聚類演算法，首先讀者要知道，聚類是一類無監督的學習，它將相似的物件歸到同一個簇中。簇內的資料越相似，則聚類效果越好。無監督學習是指沒有事先標記好訓練集的型別。聚類和分類都是對記錄進行分組；但分類則有預先定義的類別。 K均值聚類演算法其實很簡單，就如上圖所述，我們緊接著就引出K均值聚類的演算法。 K均值聚類演算法的優點就是演算法簡單，讀者在上面也看到了；而它的缺點是：可能收斂到區域性最小值，在大規模資料集上收斂較慢。K均值聚類適應的資料型別是，數值型資料。直觀上看，K均值聚類演算法的結果就是這樣的：

K均值聚類演算法的實現

在普遍的演算法實現中，我們都可以按照以下流程了進行： K-均值聚類的一般流程

(1) 收集資料：使用任意方法。 
(2) 準備資料：需要數值型資料來計算距離，也可以將標稱型資料對映為二值型資料再用
於距離計算。 
(3) 分析資料：使用任意方法。 
(4) 訓練演算法：不適用於無監督學習，即無監督學習沒有訓練過程。 
(5) 測試演算法：應用聚類演算法、觀察結果。可以使用量化的誤差指標如誤差平方和（後面
 會介紹）來評價演算法的結果。 
(6) 使用演算法：可以用於所希望的任何應用。通常情況下，簇質心可以代表整個簇的資料
來做出決策。

==匯入資料==

python def loadDataSet(fileName): #general function to parse tab -delimited floats dataMat = [] #assume last column is target value fr = open(fileName) for line in fr.readlines(): curLine = line.strip().split('\t') fltLine = list(map(float,curLine)) #map all elements to float() dataMat.append(fltLine) return dataMat

==計算歐式距離==

python def distEclud(vecA, vecB): return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)

==產生隨機質心==

python def randCent(dataSet, k): n = shape(dataSet)[1] centroids = mat(zeros((k,n)))#create centroid mat for j in range(n):#create random cluster centers, within bounds of each dimension minJ = min(dataSet[:,j]) rangeJ = float(max(dataSet[:,j]) - minJ) centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1)) return centroids

==K均值聚類演算法==

python def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): m = shape(dataSet)[0] clusterAssment = mat(zeros((m,2)))#create mat to assign data points #to a centroid, also holds SE of each point centroids = createCent(dataSet, k) clusterChanged = True while clusterChanged: clusterChanged = False for i in range(m):#for each data point assign it to the closest centroid minDist = inf; minIndex = -1 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) for cent in range(k):#recalculate centroids ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean return centroids, clusterAssment 但是K均值聚類演算法是有缺陷的 為了克服這一缺陷，我們引入2分-K均值聚類演算法。首先，我們說明數理統計中的一個概念SSE

2分-K均值聚類演算法

接下來，我們正式進行引入。 思路：將所有的點作成一個簇，然後選擇可以使得SSE最大程度降低的簇一分為二，不斷迴圈到滿足數目為止。 二分K-均值演算法的虛擬碼形式如下：

2分-K均值聚類演算法的實現

==二分K-均值聚類演算法==

```python def biKmeans(dataSet, k, distMeas=distEclud): m = shape(dataSet)[0] clusterAssment = mat(zeros((m,2))) centroid0 = mean(dataSet, axis=0).tolist()[0] centList =[centroid0] #create a list with one centroid for j in range(m):#calc initial Error clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2 while (len(centList) < k): lowestSSE = inf for i in range(len(centList)): ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]#get the data points currently in cluster i centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas) sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) print("sseSplit, and notSplit: ",sseSplit,sseNotSplit) 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

```