python實作K均值聚類算法

之前做大作業的時候本來想用聚類法給點集分類的，但是太複雜了，于是最後沒有采用這個方案。現在把之前做的一些工作整理出來寫個小部落格。

K-means聚類法原理：

聚類是一個将資料集中在某些方面相似的資料成員進行分類組織的過程，聚類就是一種發現這種内在結構的技術，聚類技術經常被稱為無監督學習。

K-Means算法的思想很簡單，對于給定的樣本集，按照樣本之間的距離大小，将樣本集劃分為K個簇。讓簇内的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

如何計算？

如果用資料表達式表示，假設簇劃分為 ( C 1 , C 2 , . . . C k ) ({C_1},{C_2},...{C_k}) (C1​,C2​,...Ck​)，則我們的目标是最小化平方誤差E：

E = ∑ i = 1 k ∑ x ∈ C i ∥ x − μ i ∥ 2 2 E = \sum\limits_{i = 1}^k {\sum\limits_{x \in {C_i}} {\left\| {x - {\mu _i}} \right\|_2^2} } E=i=1∑k​x∈Ci​∑​∥x−μi​∥22​

其中 μ i μ_i μi​是簇 C i C_i Ci​的均值向量，有時也稱為質心，表達式為：

μ i = 1 ∣ C i ∣ ∑ x ∈ C i x {\mu _i} = \frac{1}{{\left| {{C_i}} \right|}}\sum\limits_{x \in {C_i}} x μi​=∣Ci​∣1​x∈Ci​∑​x

如果我們想直接求上式的最小值并不容易，這是一個NP難的問題，是以隻能采用啟發式的疊代方法。

下圖是K均值聚類法的一個示意圖：

上圖a表達了初始的資料集，假設k=2。在圖b中，我們随機選擇了兩個k類所對應的類别質心，即圖中的紅色質心和藍色質心，然後分别求樣本中所有點到這兩個質心的距離，并标記每個樣本的類别為和該樣本距離最小的質心的類别，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪疊代後的類别。此時我們對我們目前标記為紅色和藍色的點分别求其新的質心，如圖4所示，新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重複了我們在圖c和圖d的過程，即将所有點的類别标記為距離最近的質心的類别并求新的質心。最終我們得到的兩個類别如圖f。

當然在實際K-Mean算法中，我們一般會多次運作圖c和圖d，才能達到最終的比較優的類别。

我的解決方案是在代碼中使用的是循環10次（可調），選擇總距離最小的那個方案。

代碼部分：

class KMeansClusterer:  # k均值聚類
    def __init__(self, ndarray, cluster_num):
        self.ndarray = ndarray
        self.cluster_num = cluster_num
        self.points = self.__pick_start_point(ndarray, cluster_num)

    def cluster(self):
        result = []
        for i in range(self.cluster_num):
            result.append([])
        for item in self.ndarray:
            distance_min = sys.maxsize
            index = -1
            for i in range(len(self.points)):
                distance = self.__distance(item, self.points[i])
                if distance < distance_min:
                    distance_min = distance
                    index = i
            result[index] = result[index] + [item.tolist()]
        new_center = []
        for item in result:
            new_center.append(self.__center(item).tolist())
        # 中心點未改變，說明達到穩态，結束遞歸
        if (self.points == new_center).all():
            sum=self.__sumdis(result)
            return result,self.points,sum
        self.points = np.array(new_center)
        return self.cluster()

    def __sumdis(self,result):
        #計算總距離和
        sum=0
        for i in range(len(self.points)):
            for j in range(len(result[i])):
                sum+=self.__distance(result[i][j],self.points[i])
        return sum

    def __center(self, list):
        # 計算每一列的平均值
        return np.array(list).mean(axis=0)

    def __distance(self, p1, p2):
        #計算兩點間距
        tmp = 0
        for i in range(len(p1)):
            tmp += pow(p1[i] - p2[i], 2)
        return pow(tmp, 0.5)

    def __pick_start_point(self, ndarray, cluster_num):
        if cluster_num < 0 or cluster_num > ndarray.shape[0]:
            raise Exception("簇數設定有誤")
        # 取點的下标
        indexes = random.sample(np.arange(0, ndarray.shape[0], step=1).tolist(), cluster_num)
        points = []
        for index in indexes:
            points.append(ndarray[index].tolist())
        return np.array(points)

           

運作結果如下：

結果如上圖所示，這是之前大作業得到的點集，不同顔色的點分屬于不同類型的點集，五角星為每個點集的中心點。

調用函數後得到的是點集以及總距離。代碼使用示例我放在資源包裡，有需要自取。