python簡單實作k-means聚類算法

我對聚類算法的了解：将一堆，無劃分的資料，通過它們之間的相似度進行劃分。（簡單粗暴^。^）

根據上面的了解，K-means算法就能知名曉意了：就是将一堆無劃分的樣本資料，定義需要劃分為K堆，然後通過每個樣本資料點與中心點間的距離進行歸簇。（在k-means中需要在劃分前需指定中心點，這是它的缺點）

下面是官方一點的說法：

Ｋ-Means算法是最為經典的基于劃分的聚簇方法，是十大經典資料挖掘算法之一。簡單的說Ｋ-Means就是在沒有任何監督信号的情況下将資料分為K份的一種方法。聚類算法就是無監督學習中最常見的一種，給定一組資料，需要聚類算法去挖掘資料中的隐含資訊。聚類算法的應用很廣：顧客行為聚類，google新聞聚類等。K值是聚類結果中類别的數量。

其實k-means算法真的簡單，先不說代碼，就說原理，你隻要仔細了解一遍，用自己的語言總結一下，慢慢就能摸索出代碼。我剛學時參考了一篇部落格，找不到連接配接了，很感謝他寫的很簡單，了解的很快，過了一段時間用自己的思路将代碼摸索了出來。直接看完整代碼：

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

global K
global N
global spot
global unite
global mean
global count

def cluster():  #劃分每個點一個到簇
    global unite
    unite = []      #這裡千萬注意，需要每次都定義，否則會重複添加長度。當下一次運作cluster函數時才會重置unite清單
    for i in range(K):
        unite.append([])
    for i in range(len(spot)):
        max_max = np.iinfo(np.int32).max  #預定義一個極大值,用于比較
        flag = -1
        for j in range(K):
            n = (spot[i][0]-mean[j][0])**2+(spot[i][1]-mean[j][1])**2
            if(n<max_max):
                max_max = n
                flag = j
        unite[flag].append(spot[i])
    for i in range(K):
        print("第{}簇：{}".format(i,unite[i]))

def square_d():
    global count
    sum_E = 0
    for i in range(len(unite)):
        for j in range(len(unite[i])):
            sum_E += ((unite[i][j][0]-mean[i][0])**2 + (unite[i][j][1]-mean[i][1])**2)
    count +=1
    return sum_E

def remean():
    for i in range(len(unite)):
        sum_x = 0
        sum_y = 0
        for j in range(len(unite[i])):
            sum_x += unite[i][j][0]
            sum_y += unite[i][j][1]
        # if(len(unite[i]) == 0):     #分母不為0，如果前面判斷了中心值不一樣可以省略
        #     mean[i] = (0,0)
        # else:
        #     mean[i] = (sum_x/len(unite[i]),sum_y/len(unite[i]))
        mean[i] = (sum_x/len(unite[i]),sum_y/len(unite[i]))    #根據均值，重新定義的中心值

def show():
     #樣本資料橫坐标清單
    xx = []
    for i in range(K):
        xx.append([])
    #樣本資料縱坐标清單
    yy = []
    for i in range(K):
        yy.append([])
    #使用樣本坐标，繪制散點圖
    for i in range(K):
        for j in range(len(unite[i])):
            xx[i].append(unite[i][j][0])
        for j in range(len(unite[i])):
            yy[i].append(unite[i][j][1])
        plt.scatter(xx[i],yy[i],label=i)
        plt.scatter(mean[i][0],mean[i][1],label=i)
        plt.legend()
    #顯示散點圖
    plt.show()

if __name__=="__main__":
    K = 4   #聚類數    手動設定
    N = 30  #樣本數    手動設定
    spot = []   #樣本清單
    for i in range(N):
        spot.append((np.random.randint(50),np.random.randint(50)))  #50是我給它定義的範圍

    unite = []  #每個點歸屬簇
    mean = []   #每個簇的中心值

    set_t = set()
    while(1):           #雖然兩行代碼就可以搞定這個選值，但是我建議使用集合，防止重複值
        d = np.random.randint(N)    #當然如果你有更簡單的方法除外，就我覺得使用集合比較簡單
        set_t.add(d)
        if(len(set_t)==K):
            for i in set_t:
                mean.append(spot[i])
            break

    count = 0
    m = []
    for i in range(2):      #首先兩次循環，得出兩個比較的平方誤差
        cluster()       #聚類
        temp = square_d()   #計算平方誤差
        m.append(temp)
        print("第{}次聚類平方的內插補點為：{}".format(count,temp))
        remean()    #重定義中心值

    while(m[0] != m[1]):    #就兩次循環後，重複選中心值，直至相等
        m[0] = m[1]
        cluster()
        m[1] = square_d()
        print("第{}次聚類平方的內插補點為：{}".format(count,m[1]))
        remean()

    show()  #構散點圖    構圖與k-means無關，但是利用圖表将資料展示出來更直覺、更有說服力
           

這算是寫的很簡單的了，稍微複雜點的，定義每個部分的類于不同檔案，在每個類中更細緻的實作方法，再互相調用執行個體。

這裡我根據代碼總結了實作聚類的思想：

1：随機選擇K個中心值

2：根據樣本資料各點與中心點的距離來進行歸簇

3：通過整個簇的均值，重置每個簇的中心值

4：重複2、3，直至達到最大的疊代次數（例如：我這裡的條件設定為本次與上次的平方誤差相等）

适用範圍及缺陷：

K-Menas算法嘗試找到使平方誤差準則函數最小的簇。當潛在的簇形狀是凸面的，簇與簇之間差別較明顯，且簇大小相近時，其聚類結果較理想。對于處理大資料集合，該算法非常高效，且伸縮性較好。

但該算法除了要事先确定簇數K和對初始聚類中心敏感外，經常以局部最優結束，同時對“噪聲”和孤立點敏感，并且該方法不适于發現非凸面形狀的簇或大小差别很大的簇。

克服缺點的方法：使用盡量多的資料;使用中位數代替均值來克服outlier的問題。

優缺點是借鑒别人的，感覺比我總結的好那麼一點點。是以記住上面的步驟，就算忘記了模闆，也能自己慢慢摸索出來。