第十一章 K-Means(K均值)演算法模型實現（上）

來自專欄 數據模型的那些事兒聚類演算法用於根據數據的特徵發現數據項的相似性，並將相似的數據項放在同一個組中，相似性採用距離進行描述。

K-means聚類

簡單的說，一般流程如下：先隨機選取k個點，將每個點分配給它們，得到最初的k個分類；在每個分類中計算均值，將點重新分配，劃歸到最近的中心點；重複上述步驟直到點的劃歸不再改變。

K-Means演算法的SAS實現

K-means演算法可以用SAS的proc fastclus實現。主要涉及兩個問題。首先是初始點的選擇。如果指定replace=random，則系統隨機選取maxcluster選項指定個數的完整觀測作為凝聚點。如果分析員對研究情景比較了解，可以利用專業知識指定初始分類，那麼可以在proc fastclus中設定seed=dataset選項，SAS會從dataset中讀取前k個觀測作為初始凝聚點。此外，SAS還提供了系統自動選擇初始凝聚點的方法，該方法需要指定maxclusters和radius選項，其中radius為凝聚點之間允許的最小距離。默認值是maxclusters=100，radius=0，效果是選取數據集中的前100個觀測作為凝聚點。fastclus過程總是選擇第一個完整觀測作為第一個凝聚點，然後依次考察剩餘觀測，與第一個凝聚點的距離大於radius指定值的觀測作為第二個凝聚點。當凝聚點的個數未達到maxcluster，且所考察觀測與已有凝聚點間距離均大於radius指定值時，則所考察的觀測成為下一個凝聚點。如果一個觀測完整且與所有凝聚點距離均大於radius，但凝聚點個數已經達到最大值，此時fastclus過程進行兩種替換檢驗，檢驗能否用當前觀測替換已有凝聚點。第一個檢驗是替換距離最近兩凝聚點檢驗，如果凝聚點與當前觀測的最小距離大於已有凝聚點的最小距離，則一個已有凝聚點將被替換，當前觀測將替換距離最近的兩個凝聚點中的一個，使得替換後當前觀測與最近距離兩凝聚點中未被替換的那個距離最遠。第二個檢驗是替換當前觀測最近凝聚點檢驗，如果當前觀測到除最近凝聚點外的所有凝聚點的最小距離大於當前觀測最近凝聚點到所有其他凝聚點的最小距離，進行替換。如果兩種檢驗都說明該觀測不能替換已有凝聚點，則轉向下一個觀測，直到考察完數據集中的所有觀測。當然，這種檢測可以用replace=none|part|full來控制，none表示不進行替換檢驗，part表示只進行第一種替換檢驗；full為默認值，兩種替換檢驗都進行。 另一個問題是分類的修改方法。默認的方法是按批修改法，即選定一批凝聚點後；將所有觀測按與其距離最近的凝聚點歸類；計算每一類重心，將重心作為新的凝聚點，若新凝聚點與舊凝聚點完全重合，則終止演算法，否則重新歸類。批量修改法是全部觀測調整完畢後，才改變類的凝聚點，而逐個修改法是每個觀測一旦調整後立即改變類凝聚點，而立即改變需要演算法即時驗證改變後的凝聚點集合是否仍然滿足radius的約束。如果不滿足radius的約束，SAS會將小於radius的兩類合併，計算重心，作為合併後類的凝聚點，如此往複，直到凝聚點滿足radius條件。要讓SAS執行逐個修改法，需要聲明drift選項。

補充 K-means聚類演算法的問題是，均值的計算受異常點的干擾比較嚴重。為了克服這個問題，可以採用K中值法。

K-medoid聚類

PAM（Partition Around Medoids）是K-medoid的基礎演算法，基本流程如下：首先隨機選擇k個對象作為中心，把每個對象分配給離它最近的中心。然後隨機地選擇一個非中心對象替換中心對象，計算分配後的距離改進量。聚類的過程就是不斷迭代，進行中心對象和非中心對象的反覆替換過程，直到目標函數不再有改進為止。

PAM演算法的問題在於伸縮性不好，需要測試所有的替換，只適用於小數據量的聚類。為了提高該演算法的可伸縮性，有人提出了CLARAN演算法，本質如下：從總體數據中生成多個樣本數據，在每個樣本數據上應用PAM演算法得到一組K中值點；取出所有樣本中結果最好的那一組作為最後的解。

CLARAN演算法存在的問題是，演算法的聚類質量依賴於樣本的質量。 為了提高PAM和CLARAN演算法的聚類質量，有人在CLARAN演算法的基礎上提出了CLARANS演算法。與CLARAN相比，最大的區別在於沒有一個時刻演算法局限於固定的一個樣本中，自始自終，演算法的樣本數據都是隨機抽樣的。其演算法過程如下。將每套k個中值點作為一個節點，若兩個節點之間有k-1個點相同，則成為鄰居。用戶事先指定兩個數，一是最大的鄰居數，二是最大的局部最優點數。演算法隨機選取一個當前點，隨機地取出其中的一個鄰居，看目標值是否有改進，如果有改進，則用鄰居替代當前點，重新開始搜索鄰居的過程；若抽取了最大鄰居數的鄰居，發現當前點最優，那麼就找到了一個局部最優點。找到一個局部最優點後，再隨機抽取一個當前點，進行上面的過程，直到找到了用戶指定最大數量的局部最優點。比較每個局部最優點的目標值，取最優的那個點作為結果，即可得到k個中值點，於是k個類就可以輕鬆得到。CLARANS演算法的效果不錯，但演算法複雜度更高。

python3 kMeans 演算法實現：

# coding=utf-8 import numpyfrom numpy import * from numpy.random.mtrand import power from numpy import mat#載入數據def loadDataMat(fileName): dataMat = [] fr = open(fileName) for line in fr.readlines(): #print line curLine = line.strip().split(,) #print curLine fltLine =list(map(float,curLine)) #map all elements to float() ，map函數在python2與python3中輸出結果不同，python2中map函數輸出的是一個list，python3中map函數輸出的是一個迭代，所以這裡要轉換成list. #print(fltLine) dataMat.append(fltLine) #print(dataMat) return dataMat # 計算歐式距離 def distEclud(vecA, vecB): return sqrt(sum(numpy.power(abs(vecA-vecB),2))) #power函數在numpy與matplotlib中都存在，但這裡的power函數是numpy模塊里的，所以引用時要說明，不然會報錯。# 尋找K個隨機質心 def randCent(dataMat, k): n =shape(dataMat)[1] centroids =mat(zeros((k,n))) #這裡的zeros函數是numpy里的，所以必須要import numpy for j in range(n): # 每列中的最小值 minJ = numpy.min(dataMat[:,j]) #這裡的min與max函數也是numpy里的，當時運行時報錯，加了numpy.就沒問題了 # 每列中的最大值減去最小值 rangeJ = float(numpy.max(dataMat[:,j]) - minJ) # 得到k個質心 centroids[:,j] =mat(minJ +rangeJ * random.rand(k,1)) return centroids def kMeans(dataMat, k, distMeas=distEclud,createCent=randCent): m =shape(dataMat)[0] #注意數據格式的轉化，這裡的clusterAssment是matrix格式的 clusterAssment = mat(zeros((m,2))) #print(clusterAssment) centroids = createCent(dataMat, k) #print(centroids) clusterChanged =True while clusterChanged: clusterChanged = False #數據是二維的，有m行，對每一行即每個樣本進行迭代計算 for i in range(m): minDist =inf;minIndex =-1 for j in range(k): # 計算任意點和數k個質心的距離 distJI =distMeas(centroids[j,:],dataMat[i,:]) #選出最小的距離 if distJI < minDist: minDist =distJI ;minIndex=j #更新數據，直到最小值的索引不變 if clusterAssment[i,0] != minIndex :clusterChanged=True #clusterAssment存儲的是每行即每個樣本對應的質心的最小索引和值 clusterAssment[i,:] = minIndex,minDist**2 #print (centroids) #print(clusterAssment) #更新質心，取對應相同質心的所有行索引的平均值，作為新的質心axis=0表示沿著二維數組的列來取的平均值。 for cent in range(k): #clusterAssment[i,0].A操作是將numpy的mat格式矩陣轉換為數組 ptsInClust = dataMat[nonzero(clusterAssment[:,0].A==cent)[0]] centroids[cent,:] =mean(ptsInClust,axis=0) return centroids,clusterAssmentif __name__==__main__:#主函數調用 import matplotlib matplotlib.use(Agg)#後面的savefig保存照片時要用到這個 from matplotlib import pyplot as plt from matplotlib.pyplot import savefig #要劃分的聚類數目 k=3 #載入數據 dataMat = mat(loadDataMat(C:/Users/HZF/Desktop/python數據挖掘十大演算法實現/11.csv)) #print (dataMat) numSamples = dataMat.shape[0] #print(numSamples)#計算聚類中心 centroids,clusterAssment =kMeans(dataMat,k) print (centroids,clusterAssment)#畫出所有的聚類數據，根據所處聚類中心的不同用不同的表示方法 mark = [or, ob, og, ok, ^r, +r, sr, dr, <r, pr] for i in range(numSamples): markIndex = int(clusterAssment[i, 0]) plt.plot(dataMat[i, 0], dataMat[i, 1], mark[markIndex])#畫出聚類中心 mark = [Dr, Db, Dg, Dk, ^b, +b, sb, db, <b, pb]# 畫聚類中心，一共有四類 for i in range(k): plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12) plt.savefig(glp.png, dpi = 75)#savefig可以保存照片到當前位置 plt.show() #plt.savefig(glp.png, dpi = 75)#if __name__==__main__: #k=4 #dataMat = mat(loadDataMat(testSet.txt)) #myCentroids,clusterAssment =kMeans(dataMat,k) #plt.show() #savefig(glp.jpg, dpi = 75)

（未完待續）
推薦閱讀：