本節(jié)內(nèi)容：本節(jié)內(nèi)容是根據(jù)上學(xué)期所上的模式識(shí)別課程的作業(yè)整理而來(lái)，第一道題目是Kmeans聚類算法，數(shù)據(jù)集是Iris(鳶尾花的數(shù)據(jù)集)，分類數(shù)k是3，數(shù)據(jù)維數(shù)是4。
關(guān)于聚類
聚類算法是這樣的一種算法：給定樣本數(shù)據(jù)Sample，要求將樣本Sample中相似的數(shù)據(jù)聚到一類。有了這個(gè)認(rèn)識(shí)之后，就應(yīng)該了解了聚類算法要干什么了吧。說(shuō)白了，就是歸類。
首先，我們需要考慮的是，如何衡量數(shù)據(jù)之間的相似程度？比如說(shuō)，有一群說(shuō)不同語(yǔ)言的人，我們一般是根據(jù)他們的方言來(lái)聚類的（當(dāng)然，你也可以指定以身高來(lái)聚類）。這里，語(yǔ)言的相似性（或者身高）就成了我們衡量相似的量度了。在考慮存在海量數(shù)據(jù)，如微博上各種用戶的關(guān)系網(wǎng)，如何根據(jù)用戶的關(guān)注和被關(guān)注來(lái)聚類，給用戶推薦他們感興趣的用戶？這就是聚類算法研究的內(nèi)容之一了。
Kmeans就是這樣的聚類算法中比較簡(jiǎn)單的算法，給定數(shù)據(jù)樣本集Sample和應(yīng)該劃分的類數(shù)K，對(duì)樣本數(shù)據(jù)Sample進(jìn)行聚類，最終形成K個(gè)cluster，其相似的度量是某條數(shù)據(jù)i與中心點(diǎn)的”距離”(這里所說(shuō)的距離，不止于二維)。
基本思想
KMeans算法的基本思想是初始隨機(jī)給定K個(gè)簇中心，按照最鄰近原則把待分類樣本點(diǎn)分到各個(gè)簇。然后按平均法重新計(jì)算各個(gè)簇的質(zhì)心，從而確定新的簇心。一直迭代，直到簇心的移動(dòng)距離小于某個(gè)給定的值。
基本步驟
K-Means聚類算法主要分為三個(gè)步驟：
1，初始化k個(gè)聚類中心。
2，計(jì)算出每個(gè)對(duì)象跟這k個(gè)中心的距離（相似度計(jì)算，這個(gè)下面會(huì)提到），假如x這個(gè)對(duì)象跟y這個(gè)中心的距離最小（相似度最大），那么x屬于y這個(gè)中心。這一步就可以得到初步的k個(gè)聚類 。
3，在第二步得到的每個(gè)聚類分別計(jì)算出新的聚類中心，和舊的中心比對(duì)，假如不相同，則繼續(xù)第2步，直到新舊兩個(gè)中心相同，說(shuō)明聚類不可變，已經(jīng)成功 。
復(fù)雜度分析
時(shí)間復(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)鍵步驟。常見(jiàn)的方法是隨機(jī)的選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問(wèn)題的一種常用技術(shù)是：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡(jiǎn)單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個(gè)數(shù)。
第二種有效的方法是，取一個(gè)樣本，并使用層次聚類技術(shù)對(duì)它聚類。從層次聚類中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法通常很有效，但僅對(duì)下列情況有效：
（1）樣本相對(duì)較小，例如數(shù)百到數(shù)千（層次聚類開(kāi)銷較大）；
（2）K相對(duì)于樣本大小較小
第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。然后，對(duì)于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過(guò)的初始質(zhì)心最遠(yuǎn)的點(diǎn)。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的，而且是散開(kāi)的。但是，這種方法可能選中離群點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開(kāi)銷也非常大。為了克服這個(gè)問(wèn)題，通常該方法用于點(diǎn)樣本。由于離群點(diǎn)很少（多了就不是離群點(diǎn)了），它們多半不會(huì)在隨機(jī)樣本中出現(xiàn)。計(jì)算量也大幅減少。
第四種方法是使用canopy算法進(jìn)行初始劃分。基于Canopy Method的聚類算法將聚類過(guò)程分為兩個(gè)階段：
Stage1：聚類最耗費(fèi)計(jì)算的地方是計(jì)算對(duì)象相似性的時(shí)候，Canopy Method在第一階段選擇簡(jiǎn)單、計(jì)算代價(jià)較低的方法計(jì)算對(duì)象相似性，將相似的對(duì)象放在一個(gè)子集中，這個(gè)子集被叫做Canopy ，通過(guò)一系列計(jì)算得到若干Canopy，Canopy之間可以是重疊的，但不會(huì)存在某個(gè)對(duì)象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預(yù)處理。
Stage2：在各個(gè)Canopy 內(nèi)使用傳統(tǒng)的聚類方法(如K-means)，不屬于同一Canopy 的對(duì)象之間不進(jìn)行相似性計(jì)算。從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy 不要太大且Canopy 之間重疊的不要太多的話會(huì)大大減少后續(xù)需要計(jì)算相似性的對(duì)象的個(gè)數(shù)；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過(guò)Stage1得到的Canopy 個(gè)數(shù)完全可以作為這個(gè)K值，一定程度上減少了選擇K的盲目性。
算法實(shí)驗(yàn)
任務(wù)
在給定的Iris.txt樣本文件中，用K-means聚類算法將150個(gè)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實(shí)現(xiàn)
算法流程
第一步，將文件中的數(shù)據(jù)讀入到dataset列表中，通過(guò)len(dataset[0])來(lái)獲取數(shù)據(jù)維數(shù)，在測(cè)試樣例中是四維
第二步，產(chǎn)生聚類的初始位置。首先掃描數(shù)據(jù)，獲取每一維數(shù)據(jù)分量中的最大值和最小值，然后在這個(gè)區(qū)間上隨機(jī)產(chǎn)生一個(gè)值，循環(huán)k次(k為所分的類別),這樣就產(chǎn)生了聚類初始中心（k個(gè)）
第三步，按照最短距離（歐式距離）原則將所有樣本分配到k個(gè)聚類中心中的某一個(gè)，這步操作的結(jié)果是產(chǎn)生列表assigments，可以通過(guò)Python中的zip函數(shù)整合成字典。注意到原始聚類中心可能不在樣本中，因此可能出現(xiàn)分配的結(jié)果出現(xiàn)某一個(gè)聚類中心點(diǎn)集合為空，此時(shí)需要結(jié)束，提示“隨機(jī)數(shù)產(chǎn)生錯(cuò)誤，需要重新運(yùn)行”，以產(chǎn)生合適的初始中心。
第四步，計(jì)算各個(gè)聚類中心的新向量，更新距離，即每一類中每一維均值向量。然后再進(jìn)行分配，比較前后兩個(gè)聚類中心向量是否相等，若不相等則進(jìn)行循環(huán)，否則終止循環(huán)，進(jìn)入下一步。
最后，將結(jié)果輸出到文件和屏幕中
代碼如下
|
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
# coding=gbk#python edition: Python3.4.1,2014,9,24from collections import defaultdictfrom random import uniformfrom math import sqrtdef 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 datasetdef 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_centerdef 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 centersdef 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)生隨機(jī)數(shù)錯(cuò)誤，請(qǐng)重新運(yùn)行程序！!!!--\n") exit() return assignmentsdef 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 centersdef 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)號(hào)簡(jiǎ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類數(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. 通過(guò)多次運(yùn)行程序發(fā)現(xiàn)，所得結(jié)果與初始值的選定有著密切的關(guān)系，并且由于在我的程序中采用隨機(jī)數(shù)的方式產(chǎn)生初值，因此經(jīng)過(guò)觀察發(fā)現(xiàn)有多種結(jié)果。
b. 其中兩種常見(jiàn)的結(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
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/fzch_struggling/article/details/45009097
