7种常用的聚类方法（k-means聚类算法）

7种常用的聚类方法（k-means聚类算法）1）原理比较简单，实现也是很容易，收敛速度快。 优点 2.对任意一个样本点，求其到K个聚类中心的距离，将样本点归类到距离最小的中心的聚类，如此迭代n次；3.每次迭代过程中，利用均值等方法更新各个聚类的中心点(质心)；4.对K个聚类中心，利用2 3步迭代更新后，如果位置点变化很小(可以设置阈值)，则认为达到稳定状态，迭代结束，对不同的聚类块和聚类中心可选择不同的颜色标注。

K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。K-Means算法有大量的变体，本文就从最传统的K-Means算法讲起，在其基础上讲述K-Means的优化变体方法。包括初始化优化K-Means 距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。

kmeans VS KNN

算法步骤：

1.（随机）选择K个聚类的初始中心；

2.对任意一个样本点，求其到K个聚类中心的距离，将样本点归类到距离最小的中心的聚类，如此迭代n次；

3.每次迭代过程中，利用均值等方法更新各个聚类的中心点(质心)；

4.对K个聚类中心，利用2 3步迭代更新后，如果位置点变化很小(可以设置阈值)，则认为达到稳定状态，迭代结束，对不同的聚类块和聚类中心可选择不同的颜色标注。

优点

1）原理比较简单，实现也是很容易，收敛速度快。

2）聚类效果较优。

3）算法的可解释度比较强。

4）主要需要调参的参数仅仅是簇数k。

缺点

1）K值的选取不好把握

2）对于不是凸的数据集比较难收敛

3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。

4） 最终结果和初始点的选择有关，容易陷入局部最优。

5） 对噪音和异常点比较的敏感。

传统的kmeans算法实践：

（1）创建kmeans工具类，定义Cluster、sample类，和生成样本的方式，以及距离的计算方式。根据不同的优化方式可以修改该工具类，比如距离的计算公式。也可以定义不同的sample特征用于聚类

下面以二维平面的点的欧氏距离作为聚类特征

# -*- coding:utf-8 -*- """ author：goldstine version: 1.0 date: 2021/3/29 project name:k-means tools https://gist.github.com/iandanforth/5862470 """ import math import random class Cluster(object): """ 聚类 """ def __init__(self samples): if len(samples)==0: raise Exception("错误，没有样本点的空聚类!") #属于该聚类的样本点 self.samples=samples #该聚类中样本点的维数 self.n_dim=samples[0].n_dim #判断该聚类中所有的样本点维度是否相同 for sample in samples: if sample.n_dim !=self.n_dim: raise Exception("错误：聚类中样本点的维度不一致！") #设置初始化的聚类中心 self.centerid=self.cal_centerid() def __repr__(self): """ 输出对象信息 :return: """ return str(self.samples) def update(self samples): """ 计算之前的聚类中心和更新之后的聚类中心的距离 :param samples: :return: """ old_centerid=self.centerid self.samples=samples self.centerid=self.cal_centerid() shift=get_distance(old_centerid self.centerid) return shift def cal_centerid(self): """ 对一组样本点计算其中心点 :return: """ n_samples=len(self.samples) #获取所有样本点的坐标特征 coords=[sample.coords for sample in self.samples] unzipped=zip(*coords) #计算每一个维度的均值 centerid_coords=[math.fsum(d_list)/n_samples for d_list in unzipped] return Sample(centerid_coords) class Sample(object): """ 样本点类 """ def __init__(self coords): self.coords=coords #样本点包含的坐标 self.n_dim=len(coords) #y样本点的维度 #s输出对象信息 def __repr__(self): return str(self.coords) def get_distance(a b): """ 返回样本点之间的欧氏距离 参考：https://en.wikipedia.org/wiki/Euclidean_distance#n_dimensions :param a: :param b: :return: """ if a.n_dim!=b.n_dim: #如果样本点维度不同 raise Exception("错误：样本点维度不同，无法计算距离!") acc_diff=0.0 for i in range(a.n_dim): square_diff=pow((a.coords[i]-b.coords[i]) 2) acc_diff =square_diff distance=math.sqrt(acc_diff) return distance def gen_random_sample(n_dim lower upper): """ 生成随机样本点 :param n_dim: :param lower: :param upper: :return: """ sample=Sample([random.uniform(lower upper) for _ in range(n_dim)]) return sample

（2）聚类算法的实现kmeans以及聚类结果的可视化

import random from kmeans_tools import Cluster get_distance gen_random_sample import matplotlib.pyplot as plt from matplotlib import colors as mcolors def kmeans(samples k cutooff): """ kmeans函数 :param samples: :param k: :param cutooff: :return: """ #随机选k个样本点作为初始聚类中心 init_samples=random.sample(samples k) #创建k个聚类，聚类的中心分别为随机初始的样本点 clusters=[Cluster([sample]) for sample in init_samples] #迭代循环直到聚类划分稳定 n_loop=0 while True: #初始化一组空列表用于存储每个聚类内的样本点 lists=[[] for _ in clusters] #开始迭代 n_loop =1 #遍历样本集中的每一个样本 for sample in samples: smallest_distance=get_distance(sample clusters[0].centerid) #初始化属于聚类0 cluster_index=0 #计算和其他聚类中心的距离 for i in range(k-1): #计算样本点sample和聚类中心的距离 distance=get_distance(sample clusters[i 1].centerid) #如果存在更小的距离，则更新距离 if distance<smallest_distance: smallest_distance=distance cluster_index=i 1 #找到最近的聚类中心，更新所属聚类 lists[cluster_index].append(sample) #初始化最大移动距离 biggest_shift=0.0 #计算本次迭代中，聚类中心的移动距离 for i in range(k): shift =clusters[i].update(lists[i]) #记录最大移动距离 biggest_shift=max(biggest_shift shift) #如果聚类中心移动的距离小于收敛阈值，即聚类稳定 if biggest_shift<cutooff: print("第{}次迭代后，聚类稳定".format(n_loop)) break return clusters def run_main(): """ 主函数 :return: """ #样本个数 n_samples=1000 #特征个数（特征维数），平面上的点特征维度为2 n_feat=2 #特征数值范围 实际上就是限定了一个矩形范围内的点 lower=0 upper=200 #聚类个数k n_cluster=5 #随机生成样本 samples=[gen_random_sample(n_feat lower upper) for _ in range(n_samples)] #收敛域值 cutoff=0.2 #聚类迭代的终止时间 clusters=kmeans(samples n_cluster cutoff) #输出结果 for i c in enumerate(clusters): for sample in c.samples: print('聚类--{}，样本点--{}'.format(i sample)) #可视化结果 plt.subplot() color_names=list(mcolors.cnames) for i c in enumerate(clusters): x=[] y=[] random.choice color=[color_names[i]]*len(c.samples) for sample in c.samples: x.append(sample.coords[0]) y.append(sample.coords[1]) plt.scatter(x y c=color) plt.show() if __name__=='__main__': run_main()