K均值聚類算法

k均值聚類算法（k-means clustering algorithm）是一種疊代求解的聚類分析算法，其步驟是，預將數據分為K組，則隨機選取K個對象作為初始的聚類中心，然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本，聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重複直到滿足某個終止條件。終止條件可以是沒有（或最小數目）對象被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和局部最小。

基本介紹

• 中文名：K均值聚類算法
• 外文名：k-means clustering algorithm
• 類型：聚類算法
• 提出者：James MacQueen
• 提出時間：1967年
• 套用：數據分析，信號處理，機器學習

定義

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

k均值聚類是最著名的劃分聚類算法，由於簡潔和效率使得他成為所有聚類算法中最廣泛使用的。給定一個數據點集合和需要的聚類數目k，k由用戶指定，k均值算法根據某個距離函式反覆把數據分入k個聚類中。

算法

先隨機選取K個對象作為初始的聚類中心。然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。一旦全部對象都被分配了，每個聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重複直到滿足某個終止條件。終止條件可以是以下任何一個：

• 1、沒有（或最小數目）對象被重新分配給不同的聚類。
• 2、沒有（或最小數目）聚類中心再發生變化。
• 3、誤差平方和局部最小。

偽代碼

選擇k個點作為初始質心。

repeat 將每個點指派到最近的質心，形成k個簇 重新計算每個簇的質心 until 質心不發生變化

性質

k均值聚類是使用最大期望算法（Expectation-Maximization algorithm）求解的高斯混合模型（Gaussian Mixture Model, GMM）在常態分配的協方差為單位矩陣，且隱變數的後驗分布為一組狄拉克δ函式時所得到的特例。

python

import numpy as np
import pandas as pd
import random
import sys
import time
class KMeansClusterer:
    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():
            return result
        
        self.points=np.array(new_center)
        return self.cluster()
            
    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)