-
K均值聚類算法
鎖定
- 中文名
- K均值聚類算法
- 外文名
- k-means clustering algorithm
- 類 型
- 聚類算法
- 提出者
- James MacQueen
- 提出時間
- 1967年
- 應 用
- 數據分析,信號處理,機器學習
K均值聚類算法定義
K均值聚類算法算法
先隨機選取K個對象作為初始的聚類中心。然後計算每個對象與各個種子聚類中心之間的距離,把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。一旦全部對象都被分配了,每個聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重複直到滿足某個終止條件。終止條件可以是以下任何一個:
- 1、沒有(或最小數目)對象被重新分配給不同的聚類。
- 2、沒有(或最小數目)聚類中心再發生變化。
- 3、誤差平方和局部最小。
選擇k個點作為初始質心。
repeat 將每個點指派到最近的質心,形成k個簇 重新計算每個簇的質心 until 質心不發生變化
K均值聚類算法性質
k均值聚類是使用最大期望算法(Expectation-Maximization algorithm)求解的高斯混合模型(Gaussian Mixture Model, GMM)在正態分佈的協方差為單位矩陣,且隱變量的後驗分佈為一組狄拉克δ函數時所得到的特例
[1]
。
K均值聚類算法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)
- 參考資料
-
- 1. Polykovskiy, D. and Novikov, A., Bayesian Methods for Machine Learning .Coursera and National Research University Higher School of Economics.2018[引用日期2018-12-13]