-
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]
