Python如何實現Kmeans聚類算法

這篇文章主要講解了Python如何實現Kmeans聚類算法，內容清晰明了，對此有興趣的小伙伴可以學習一下，相信大家閱讀完之后會有幫助。

關于聚類

    聚類算法是這樣的一種算法：給定樣本數據Sample，要求將樣本Sample中相似的數據聚到一類。有了這個認識之后，就應該了解了聚類算法要干什么了吧。說白了，就是歸類。
    首先，我們需要考慮的是，如何衡量數據之間的相似程度？比如說，有一群說不同語言的人，我們一般是根據他們的方言來聚類的（當然，你也可以指定以身高來聚類）。這里，語言的相似性（或者身高）就成了我們衡量相似的量度了。在考慮存在海量數據，如微博上各種用戶的關系網，如何根據用戶的關注和被關注來聚類，給用戶推薦他們感興趣的用戶？這就是聚類算法研究的內容之一了。
    Kmeans就是這樣的聚類算法中比較簡單的算法，給定數據樣本集Sample和應該劃分的類數K，對樣本數據Sample進行聚類，最終形成K個cluster，其相似的度量是某條數據i與中心點的”距離”(這里所說的距離，不止于二維)。

基本思想

KMeans算法的基本思想是初始隨機給定K個簇中心，按照最鄰近原則把待分類樣本點分到各個簇。然后按平均法重新計算各個簇的質心，從而確定新的簇心。一直迭代，直到簇心的移動距離小于某個給定的值。

基本步驟

K-Means聚類算法主要分為三個步驟：
1，初始化k個聚類中心。
2，計算出每個對象跟這k個中心的距離（相似度計算，這個下面會提到），假如x這個對象跟y這個中心的距離最小（相似度最大），那么x屬于y這個中心。這一步就可以得到初步的k個聚類 。
3，在第二步得到的每個聚類分別計算出新的聚類中心，和舊的中心比對，假如不相同，則繼續第2步，直到新舊兩個中心相同，說明聚類不可變，已經成功 。

復雜度分析

時間復雜度：O(tKmn)，其中，t為迭代次數，K為簇的數目，m為記錄數，n為維數
空間復雜度：O((m+K)n)，其中，K為簇的數目，m為記錄數，n為維數

初始質心的選擇

    選擇適當的初始質心是基本kmeans算法的關鍵步驟。常見的方法是隨機的選取初始質心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡單，但是效果可能不好，這取決于數據集和尋找的簇的個數。
     第二種有效的方法是，取一個樣本，并使用層次聚類技術對它聚類。從層次聚類中提取K個簇，并用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：
        （1）樣本相對較小，例如數百到數千（層次聚類開銷較大）；
        （2）K相對于樣本大小較小

    第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然后，對于每個后繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用于點樣本。由于離群點很少（多了就不是離群點了），它們多半不會在隨機樣本中出現。計算量也大幅減少。
    第四種方法是使用canopy算法進行初始劃分。基于Canopy Method的聚類算法將聚類過程分為兩個階段：
   Stage1：聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy ，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬于任何Canopy的情況，可以把這一階段看做數據預處理。
  Stage2：在各個Canopy 內使用傳統的聚類方法(如K-means)，不屬于同一Canopy 的對象之間不進行相似性計算。從這個方法起碼可以看出兩點好處：首先，Canopy 不要太大且Canopy 之間重疊的不要太多的話會大大減少后續需要計算相似性的對象的個數；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy 個數完全可以作為這個K值，一定程度上減少了選擇K的盲目性。

算法實驗

任務

在給定的Iris.txt樣本文件中，用K-means聚類算法將150個4維樣本數據分成3類

數據集(Iris.txt)

5.1 3.5 1.4 0.2
4.9 3.0 1.4 0.2
4.7 3.2 1.3 0.2
4.6 3.1 1.5 0.2
5.0 3.6 1.4 0.2
5.4 3.9 1.7 0.4
4.6 3.4 1.4 0.3
5.0 3.4 1.5 0.2
4.4 2.9 1.4 0.2
4.9 3.1 1.5 0.1
5.4 3.7 1.5 0.2
4.8 3.4 1.6 0.2
4.8 3.0 1.4 0.1
4.3 3.0 1.1 0.1
5.8 4.0 1.2 0.2
5.7 4.4 1.5 0.4
5.4 3.9 1.3 0.4
5.1 3.5 1.4 0.3
5.7 3.8 1.7 0.3
5.1 3.8 1.5 0.3
5.4 3.4 1.7 0.2
5.1 3.7 1.5 0.4
4.6 3.6 1.0 0.2
5.1 3.3 1.7 0.5
4.8 3.4 1.9 0.2
5.0 3.0 1.6 0.2
5.0 3.4 1.6 0.4
5.2 3.5 1.5 0.2
5.2 3.4 1.4 0.2
4.7 3.2 1.6 0.2
4.8 3.1 1.6 0.2
5.4 3.4 1.5 0.4
5.2 4.1 1.5 0.1
5.5 4.2 1.4 0.2
4.9 3.1 1.5 0.2
5.0 3.2 1.2 0.2
5.5 3.5 1.3 0.2
4.9 3.6 1.4 0.1
4.4 3.0 1.3 0.2
5.1 3.4 1.5 0.2
5.0 3.5 1.3 0.3
4.5 2.3 1.3 0.3
4.4 3.2 1.3 0.2
5.0 3.5 1.6 0.6
5.1 3.8 1.9 0.4
4.8 3.0 1.4 0.3
5.1 3.8 1.6 0.2
4.6 3.2 1.4 0.2
5.3 3.7 1.5 0.2
5.0 3.3 1.4 0.2
7.0 3.2 4.7 1.4
6.4 3.2 4.5 1.5
6.9 3.1 4.9 1.5
5.5 2.3 4.0 1.3
6.5 2.8 4.6 1.5
5.7 2.8 4.5 1.3
6.3 3.3 4.7 1.6
4.9 2.4 3.3 1.0
6.6 2.9 4.6 1.3
5.2 2.7 3.9 1.4
5.0 2.0 3.5 1.0
5.9 3.0 4.2 1.5
6.0 2.2 4.0 1.0
6.1 2.9 4.7 1.4
5.6 2.9 3.9 1.3
6.7 3.1 4.4 1.4
5.6 3.0 4.5 1.5
5.8 2.7 4.1 1.0
6.2 2.2 4.5 1.5
5.6 2.5 3.9 1.1
5.9 3.2 4.8 1.8
6.1 2.8 4.0 1.3
6.3 2.5 4.9 1.5
6.1 2.8 4.7 1.2
6.4 2.9 4.3 1.3
6.6 3.0 4.4 1.4
6.8 2.8 4.8 1.4
6.7 3.0 5.0 1.7
6.0 2.9 4.5 1.5
5.7 2.6 3.5 1.0
5.5 2.4 3.8 1.1
5.5 2.4 3.7 1.0
5.8 2.7 3.9 1.2
6.0 2.7 5.1 1.6
5.4 3.0 4.5 1.5
6.0 3.4 4.5 1.6
6.7 3.1 4.7 1.5
6.3 2.3 4.4 1.3
5.6 3.0 4.1 1.3
5.5 2.5 5.0 1.3
5.5 2.6 4.4 1.2
6.1 3.0 4.6 1.4
5.8 2.6 4.0 1.2
5.0 2.3 3.3 1.0
5.6 2.7 4.2 1.3
5.7 3.0 4.2 1.2
5.7 2.9 4.2 1.3
6.2 2.9 4.3 1.3
5.1 2.5 3.0 1.1
5.7 2.8 4.1 1.3
6.3 3.3 6.0 2.5
5.8 2.7 5.1 1.9
7.1 3.0 5.9 2.1
6.3 2.9 5.6 1.8
6.5 3.0 5.8 2.2
7.6 3.0 6.6 2.1
4.9 2.5 4.5 1.7
7.3 2.9 6.3 1.8
6.7 2.5 5.8 1.8
7.2 3.6 6.1 2.5
6.5 3.2 5.1 2.0
6.4 2.7 5.3 1.9
6.8 3.0 5.5 2.1
5.7 2.5 5.0 2.0
5.8 2.8 5.1 2.4
6.4 3.2 5.3 2.3
6.5 3.0 5.5 1.8
7.7 3.8 6.7 2.2
7.7 2.6 6.9 2.3
6.0 2.2 5.0 1.5
6.9 3.2 5.7 2.3
5.6 2.8 4.9 2.0
7.7 2.8 6.7 2.0
6.3 2.7 4.9 1.8
6.7 3.3 5.7 2.1
7.2 3.2 6.0 1.8
6.2 2.8 4.8 1.8
6.1 3.0 4.9 1.8
6.4 2.8 5.6 2.1
7.2 3.0 5.8 1.6
7.4 2.8 6.1 1.9
7.9 3.8 6.4 2.0
6.4 2.8 5.6 2.2
6.3 2.8 5.1 1.5
6.1 2.6 5.6 1.4
7.7 3.0 6.1 2.3
6.3 3.4 5.6 2.4
6.4 3.1 5.5 1.8
6.0 3.0 4.8 1.8
6.9 3.1 5.4 2.1
6.7 3.1 5.6 2.4
6.9 3.1 5.1 2.3
5.8 2.7 5.1 1.9
6.8 3.2 5.9 2.3
6.7 3.3 5.7 2.5
6.7 3.0 5.2 2.3
6.3 2.5 5.0 1.9
6.5 3.0 5.2 2.0
6.2 3.4 5.4 2.3
5.9 3.0 5.1 1.8

Python實現

算法流程

第一步，將文件中的數據讀入到dataset列表中，通過len(dataset[0])來獲取數據維數，在測試樣例中是四維
第二步，產生聚類的初始位置。首先掃描數據，獲取每一維數據分量中的最大值和最小值，然后在這個區間上隨機產生一個值，循環k次(k為所分的類別),這樣就產生了聚類初始中心（k個）
第三步，按照最短距離（歐式距離）原則將所有樣本分配到k個聚類中心中的某一個，這步操作的結果是產生列表assigments，可以通過Python中的zip函數整合成字典。注意到原始聚類中心可能不在樣本中，因此可能出現分配的結果出現某一個聚類中心點集合為空，此時需要結束，提示“隨機數產生錯誤，需要重新運行”，以產生合適的初始中心。
第四步，計算各個聚類中心的新向量，更新距離，即每一類中每一維均值向量。然后再進行分配，比較前后兩個聚類中心向量是否相等，若不相等則進行循環，否則終止循環，進入下一步。
最后，將結果輸出到文件和屏幕中

代碼如下

# coding=gbk
#python edition: Python3.4.1,2014,9,24
from collections import defaultdict
from random import uniform
from math import sqrt

def read_points():
 dataset=[]
 with open('Iris.txt','r') as file:
  for line in file:
   if line =='\n':
    continue
   dataset.append(list(map(float,line.split(' '))))
  file.close() 
  return dataset

def write_results(listResult,dataset,k):
 with open('result.txt','a') as file:
  for kind in range(k):
    file.write( "CLASSINFO:%d\n"%(kind+1) )
    for j in listResult[kind]:
     file.write('%d\n'%j)
    file.write('\n')
  file.write('\n\n')
  file.close()

def point_avg(points):
 dimensions=len(points[0])
 new_center=[]
 for dimension in range(dimensions):
  sum=0
  for p in points:
   sum+=p[dimension]
  new_center.append(float("%.8f"%(sum/float(len(points)))))
 return new_center

def update_centers(data_set ,assignments,k):
 new_means = defaultdict(list)
 centers = []
 for assignment ,point in zip(assignments , data_set):
  new_means[assignment].append(point)
 for i in range(k):
  points=new_means[i]
  centers.append(point_avg(points))
 return centers

def assign_points(data_points,centers):
 assignments=[]
 for point in data_points:
  shortest=float('inf')
  shortest_index = 0
  for i in range(len(centers)):
   value=distance(point,centers[i])
   if value<shortest:
    shortest=value
    shortest_index=i
  assignments.append(shortest_index)
 if len(set(assignments))<len(centers) :
   print("\n--!!!產生隨機數錯誤，請重新運行程序！!!!--\n")
   exit()
 return assignments

def distance(a,b):
 dimention=len(a)
 sum=0
 for i in range(dimention):
  sq=(a[i]-b[i])**2
  sum+=sq
 return sqrt(sum)

def generate_k(data_set,k):
 centers=[]
 dimentions=len(data_set[0])
 min_max=defaultdict(int)
 for point in data_set:
  for i in range(dimentions):
   value=point[i]
   min_key='min_%d'%i
   max_key='max_%d'%i
   if min_key not in min_max or value<min_max[min_key]:
    min_max[min_key]=value
   if max_key not in min_max or value>min_max[max_key]:
    min_max[max_key]=value
 for j in range(k):
  rand_point=[]
  for i in range(dimentions):
   min_val=min_max['min_%d'%i]
   max_val=min_max['max_%d'%i]
   tmp=float("%.8f"%(uniform(min_val,max_val)))
   rand_point.append(tmp)
  centers.append(rand_point)
 return centers

def k_means(dataset,k):
 k_points=generate_k(dataset,k)
 assignments=assign_points(dataset,k_points)
 old_assignments=None
 while assignments !=old_assignments:
  new_centers=update_centers(dataset,assignments,k)
  old_assignments=assignments
  assignments=assign_points(dataset,new_centers)
 result=list(zip(assignments,dataset))
 print('\n\n---------------------------------分類結果---------------------------------------\n\n')
 for out in result :
  print(out,end='\n')
 print('\n\n---------------------------------標號簡記---------------------------------------\n\n')
 listResult=[[] for i in range(k)]
 count=0
 for i in assignments:
  listResult[i].append(count)
  count=count+1
 write_results(listResult,dataset,k)
 for kind in range(k):
  print("第%d類數據有:"%(kind+1))
  count=0
  for j in listResult[kind]:
    print(j,end=' ')
    count=count+1
    if count%25==0:
     print('\n')
  print('\n')
 print('\n\n--------------------------------------------------------------------------------\n\n')

def main():
 dataset=read_points()
 k_means(dataset,3)

if __name__ == "__main__": 
 main()

分類結果

a. 通過多次運行程序發現，所得結果與初始值的選定有著密切的關系，并且由于在我的程序中采用隨機數的方式產生初值，因此經過觀察發現有多種結果。
b. 其中兩種常見的結果之一如下：
第1類數據有:（50）
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
第2類數據有:（38）
52 77 100 102 103 104 105 107 108 109 110 111 112 115 116 117 118 120 122 124 125 128 129 130 131 132 134 135 136 137 139 140 141 143 144 145 147 148
第3類數據有:（62）
50 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
76 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 101 106
113 114 119 121 123 126 127 133 138 142 146 149
c. 結果之二：
第1類數據有:（50）
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
第2類數據有:（61）
51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 101 106 113
114 119 121 123 126 127 133 138 142 146 149
第3類數據有:（39）
50 52 77 100 102 103 104 105 107 108 109 110 111 112 115 116 117 118 120 122 124 125 128 129 130 131 132 134 135 136 137 139 140 141 143 144 145 147 148

看完上述內容，是不是對Python如何實現Kmeans聚類算法有進一步的了解，如果還想學習更多內容，歡迎關注億速云行業資訊頻道。