簡述【聚類演算法】

01-24

所謂人以類聚，物以群分。人都喜歡跟自己像的人聚在一起，這些人或者樣子長得比較像，或者身高比較像，或者性格比較像，或者有共同的愛好，也就是身上有某些特徵是相似的。

而跟自己像的人聚在一起的過程，其實就是尋找朋友的過程，比如A認識B，因為跟B興趣相近於是成為了朋友，通過B又認識了C，發現興趣較一致於是也成為了朋友，那麼ABC三個人就是一個朋友群，這個朋友群的形成，是自下而上的迭代的過程。在100個人當中，可能有5個朋友群，這5個朋友群的形成可能要2個月。

而聚類演算法，跟以上的過程很像。

聚類演算法，是把距離作為特徵，通過自下而上的迭代方式（距離對比），快速地把一群樣本分成幾個類別的過程。

有人可能會說，幹嘛要聚類啊，肉眼看豬是豬牛是牛這不一下就分開了么，那如果是一萬頭豬跟牛，你能一下分開么？

又有人說豬跟牛長的那麼不一樣，一下就看出來了，還用機器？其實豬跟牛看的出分別是因為他們的外形太不一樣。實際上樣本可能有幾個甚至幾十個維度，光對比其中1,2個維度基本分不出差別。

所以聚類演算法，一般是面向大量的，同時維度在2個或2個以上的樣本群。

前面講到，聚類演算法是根據樣本之間的距離來將他們歸為一類的，這個距離不是普通的距離，理論上叫做歐氏距離。

為什麼不用普通的距離就好，用這麼拗口的歐式距離？那是為了衡量高於三維空間的樣本之間的距離。在二維和三維空間里，歐式距離就是我們理解的普通的距離。

在多維空間里，假設兩個樣本為a(x1,x2,x3,x4...xn)，b(y1,y2,y3,y4...yn)。那麼他們之間的歐式距離的計算公式是

那麼聚類演算法，是怎麼通過迭代的方式，將樣本聚成幾個類別的呢？

有一種最經典的K-Means聚類方法，他是這樣運作的：

1、在樣本中隨機選擇K個點，作為每個類別的初始中心點，這K是自己定的，假如你想將樣本分成3個類K就等於3,4個類K就等於4；
2、計算所有樣本離這K個初始中心點的距離並分別進行比較，選出其中最近的距離並把這個樣本歸到這個初始中心點的類別里，即總共劃分成K個類別；
3、捨棄原來的初始中心點，在劃分好的K個類別里分別計算出新的中心點，使得這些中心點距離他類別里的所有樣本的距離之和最小；
4、判斷新獲得的中心點是否與舊中心點一樣，如不一樣則回到第2步，重新計算所有樣本離這K個新的中心點的距離並進行比較，選出其中最近的距離並歸到這個新的中心點的類別里，繼續下面的步奏；如一樣則完成，即收斂。

可以用下面的圖很好地說明

有ABCDE5個樣本，一開始選定右邊的2個初始中心點，K=2，大家顏色都不一樣，誰都不服誰；

5個樣本分別對比跟2個初始中心點的距離，選距離近的傍依，這時5個樣本分成紅黑2群；

然後開始換老大啦，2個初始中心點消失，重新在2個類分別中心的位置出現2個新的中心點，這2個新的中心點離類別里樣本的距離之和必須是最小的；

新的老大出現，類別的劃分也不一樣啦，C開始叛變，皈依新老大，因為他離新老大更近一點；

新的老大消失，新新老大出現，發現劃分的類別沒有變化，幫派穩定，於是收斂。

用Python寫了一個簡單的聚類演算法：

import matplotlib.pyplot as pltimport randomimport mathfrom copy import copy#尋找新的中心點的函數def new(group): minimum=10000 o=[] for x1 in range(min(group["x"]),max(group["x"])): for y1 in range(min(group["y"]),max(group["y"])): j=0 red_sum=0 while j<=len(group["x"])-1: red_sum+=math.sqrt((group["x"][j]-x1)**2+(group["y"][j]-y1)**2) j+=1 o.append(red_sum) if(red_sum<minimum): minimum=copy(red_sum) x2=copy(x1) y2=copy(y1) return x2,y2#根據中心點聚類並且著色的函數def color(a,b,x,y): i=0 red={"x":[],"y":[]} blue={"x":[],"y":[]} black={"x":[],"y":[]} while i<=90: distance0=math.sqrt((int(a[i])-x[0])**2+(int(b[i])-y[0])**2) distance1=math.sqrt((int(a[i])-x[1])**2+(int(b[i])-y[1])**2) distance2=math.sqrt((int(a[i])-x[2])**2+(int(b[i])-y[2])**2) if (min(distance0,distance1,distance2)==distance0): plt.plot(a[i],b[i],"ro",color="red") red["x"].append(int(a[i])) red["y"].append(int(b[i])) elif (min(distance0,distance1,distance2)==distance1): plt.plot(a[i],b[i],"ro",color="blue") blue["x"].append(int(a[i])) blue["y"].append(int(b[i])) else: plt.plot(a[i],b[i],"ro",color="black") black["x"].append(int(a[i])) black["y"].append(int(b[i])) i+=1 return red,blue,blackdef main(): #讀取數據 file=open("d:/kmeans/data.txt") a=[] b=[] for line in file.readlines(): data=line.strip().split(",") a.append(data[0]) b.append(data[1]) #隨機選取3個初始中心點 x=[random.randint(1,20),random.randint(1,20),random.randint(1,20)] y=[random.randint(1,20),random.randint(1,20),random.randint(1,20)] red,blue,black=color(a,b,x,y) plt.plot(x[0],y[0],"x",color="red",markersize=15) plt.plot(x[1],y[1],"x",color="blue",markersize=15) plt.plot(x[2],y[2],"x",color="black",markersize=15) plt.axis([0,25,0,25]) plt.show() #循環執行函數，直到收斂 while (x[0],y[0]!=new(red)) or (x[1],y[1]!=new(blue)) or (x[2],y[2]!=new(black)): x[0],y[0]=new(red) x[1],y[1]=new(blue) x[2],y[2]=new(black) red,blue,black=color(a,b,x,y) plt.plot(x[0],y[0],"x",color="red",markersize=15) plt.plot(x[1],y[1],"x",color="blue",markersize=15) plt.plot(x[2],y[2],"x",color="black",markersize=15) plt.axis([0,25,0,25]) plt.show() file.close() if __name__=="__main__": main()

第一次聚類時，分布是這樣的

第二次聚類時，分布是這樣的

收斂時，分布是這樣的

輕點一贊，手有餘香，可以給我個贊么 (O^~^O)

更多原創文章請關注專欄數據挖掘機