同义词K-means(K-means)一般指K均值聚类算法
- 中文名
- K均值聚类算法
- 外文名
- k-means clustering algorithm
- 类 型
- 聚类算法
- 提出者
- James MacQueen
- 提出时间
- 1967年
- 应 用
- 数据分析,信号处理,机器学习
k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k,k由用户指定,k均值算法根据某个距离函誉求数反复把数据归驼旋分入k个聚类中。
先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个:
- 1、没有(或最小数目)对象被重新分配给不同的聚类。
- 2、没有(或最小数目)聚类中心再发生变化。
- 3、误差平方和局部最小。
repeat 将每个点指派到最近的质心,形成k个簇 重新计算每个簇的质心 until 质心不发生变化
k均值聚类是使用最大期望算法(Expectation-Maximization algorithm)求解的高斯混合模型(Gaussian Mixture Model, GMM)在正态分布的协方差为单位矩阵,且隐变量的后验分布为一组狄拉克δ函数时所得到的特例 [1]。
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)