本節(jié)內(nèi)容：本節(jié)內(nèi)容是根據(jù)上學(xué)期所上的模式識別課程的作業(yè)整理而來，第一道題目是Kmeans聚類算法，數(shù)據(jù)集是Iris(鳶尾花的數(shù)據(jù)集)，分類數(shù)k是3，數(shù)據(jù)維數(shù)是4。

關(guān)于聚類

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

基本思想

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

基本步驟

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

復(fù)雜度分析

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

初始質(zhì)心的選擇

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

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

算法實驗

任務(wù)

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

數(shù)據(jù)集(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實現(xiàn)

算法流程

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

代碼如下

# 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--!!!產(chǎn)生隨機數(shù)錯誤，請重新運行程序！!!!--\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---------------------------------分類結(jié)果---------------------------------------\n\n')
 for out in result :
  print(out,end='\n')
 print('\n\n---------------------------------標(biāo)號簡記---------------------------------------\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類數(shù)據(jù)有:"%(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()

分類結(jié)果

a. 通過多次運行程序發(fā)現(xiàn)，所得結(jié)果與初始值的選定有著密切的關(guān)系，并且由于在我的程序中采用隨機數(shù)的方式產(chǎn)生初值，因此經(jīng)過觀察發(fā)現(xiàn)有多種結(jié)果。
b. 其中兩種常見的結(jié)果之一如下：
第1類數(shù)據(jù)有:（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類數(shù)據(jù)有:（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類數(shù)據(jù)有:（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. 結(jié)果之二：
第1類數(shù)據(jù)有:（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類數(shù)據(jù)有:（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類數(shù)據(jù)有:（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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。