K均值聚類演演算法

最著名的劃分聚類演演算法

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

目錄
1定義 2性質 3python實現

定義

聚類是一個將數據集中在某些方面相似的數據成員進行分類組織的過程，聚類就是一種發現這種內在結構的技術，聚類技術經常被稱為無監督學習。
k均值聚類是最著名的劃分聚類演演算法，由於簡潔和效率使得他成為所有聚類演演算法中最廣泛使用的。給定一個數據點集合和需要的聚類數目k，k由用戶指定，k均值演演算法根據某個距離函數反覆把數據分入k個聚類中。
偽代碼
選擇k個點作為初始質心。
repeat 將每個點指派到最近的質心，形成k個簇 重新計算每個簇的質心 until 質心不發生變化

性質

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

python實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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)

基本信息

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