K-means聚类（一）

概述我们的问题是：怎么给一堆数据分类？ 首先，每一类都叫一个簇（Cluster），如何才能算作是同一类能？ 我们有K-means聚类，DBSCAN（Density-Based Spatial Clustering of Application with Noise），hierarchical clustering等等这些聚类算法，这些算法区分同一类的方式都不同，比如DBSCAN，它是以一定的密度进行传

我们的问题是：怎么给一堆数据分类？

首先，每一类都叫一个簇（Cluster），如何才能算作是同一类能？

我们有K-means聚类，DBSCAN（Density-Based Spatial Clustering of Application with Noise），hIErarchical clustering等等这些聚类算法，这些算法区分同一类的方式都不同，比如DBSCAN，它是以一定的密度进行传播，将传播到的点都聚成一类，在某些场景，比如簇与簇之间有明显分隔的，DBSCAN显然要比k-means好。

下面是用k-means和DBSCAN划分一个笑脸的不同效果。

k-means算法

 

 

DBSCAN算法

 

不过对于均匀分布的数据，指定簇个数的k-means就要优于依靠密度发展的DBSCAN了。

k-means算法

 

DBSCAN算法

 

这些动画的演示你可在https://www.naftaliharris.com/blog/visualizing-k-means-clustering/上做到

 

 

 

使用pycharm手写k-means聚类算法

 

思路：

①随机生成1000个二维坐标的样本点

②指定划分成5类

③确定收敛阈值为0.2

④从1000个样本点中随机选出5个样本点，作为5个簇的中心

⑤每个中心为一个Cluster

⑥遍历1000个点，分别计算它们到5个中心点之间的距离，对每个点，我们得到5个距离，选择最小的，加入那个簇。

⑦第一次循环结束，我们分配好了1000个点的归属，得到了5个Cluster，对每个Cluster，计算里面包含的所有的点的均值，

也就是所有的x加起来除以总个数，所有的y加起来除以总个数，得到一个均值点。

⑧算出均值点到原来的中心点之间的距离，可以记为shift。对5个Cluster都这么做，我们会得到5个shift，挑出里边最大的biggest_shift

⑨如果biggest_shift小于收敛阈值0.2，跳出loop，否则，回到⑥

 

请注意，每个循环的时候，我们都要更新中心点，这是在第⑧步做的。代码十分详细，请看——

 

kmeans_tools.py

  1 # -*- Coding: utf-8 -*-  2   3 import math  4 import random  5   6   7 class Cluster(object):  8     """  9         聚类 10     """ 11  12     def __init__(self,samples): 13         if len(samples) == 0: 14             # 如果聚类中无样本点 15             raise Exception("错误：一个空的聚类！") 16  17         # 属于该聚类的样本点 18         self.samples = samples 19  20         # 该聚类中样本点的维度 21         self.n_dim = samples[0].n_dim 22  23         # 判断该聚类中所有样本点的维度是否相同 24         for sample in samples: 25             if sample.n_dim != self.n_dim: 26                 raise Exception("错误： 聚类中样本点的维度不一致！") 27  28         # 设置初始化的聚类中心 29         self.centroID = self.cal_centroID() 30  31     def __repr__(self): 32         """ 33             输出对象信息 34         """ 35         return str(self.samples) 36  37     def update(self,samples): 38         """ 39             计算之前的聚类中心和更新后聚类中心的距离 40         """ 41  42         old_centroID = self.centroID 43         #这里Lists[i]中的所有数据都赋给clusters[i]了 44         self.samples = samples 45         #这里把clusters[i]的centroID也更新了 46         self.centroID = self.cal_centroID() 47         shift = get_distance(old_centroID,self.centroID) 48         return shift 49  50     def cal_centroID(self): 51         """ 52            对于一组样本点计算其中心点 53         """ 54         #获取样本点的个数 55         n_samples = len(self.samples) 56         # 获取所有样本点的坐标（特征） 57         coords = [sample.coords for sample in self.samples] 58         # 将所有sample的横坐标合起来作为一个tuple，所有的纵坐标合起来作为一个tuple 59         unzipped = zip(*coords) 60         # 计算每个维度的均值 61         centroID_coords = [math.fsum(d_List)/n_samples for d_List in unzipped] 62         #将新得到的中心点封装成一个Sample 63         return Sample(centroID_coords) 64  65  66 class Sample(object): 67     """ 68         样本点类 69     """ 70     def __init__(self,coords): 71         self.coords = coords    # 样本点包含的坐标 72         self.n_dim = len(coords)    # 样本点维度 73  74     # 将coords转成str输出 75     # 方便查看 76     def __repr__(self): 77  78         return str(self.coords) 79  80  81 def get_distance(a,b): 82  83     #使用两点间的距离公式计算两个sample之间的距离 84     if a.n_dim != b.n_dim: 85         # 如果样本点维度不同 86         raise Exception("错误: 样本点维度不同，无法计算距离！") 87  88     acc_diff = 0.0 89     for i in range(a.n_dim): 90         square_diff = pow((a.coords[i]-b.coords[i]),2) 91         acc_diff += square_diff 92     distance = math.sqrt(acc_diff) 93  94     return distance 95  96  97 def gen_random_sample(n_dim,lower,upper): 98     """ 99         生成随机样本100     """101     # [random.uniform(lower,upper) for _ in range(n_dim)]得到的是一个二维的点，我们将其传入Sample102     #得到一个Sample对象103     sample = Sample([random.uniform(lower,upper) for _ in range(n_dim)])104     return sample

Sample类做样本点，样本点提供给Cluster做簇，gen_random_sample方法生成随机点，get_distance方法计算两点间的距离

 

main.py

  1 # -*- Coding: utf-8 -*-  2   3 import random  4 from kmeans_tools import Cluster,get_distance,gen_random_sample  5 import matplotlib.pyplot as plt  6 from matplotlib import colors as mcolors  7   8   9 def kmeans(samples,k,cutoff): 10  11     # 随机选k个样本点作为初始聚类中心 12     #random.sample返回的是samples中任选的5个sample,以它们作为初始的重心 13     init_samples = random.sample(samples,k) 14  15     # 创建k个聚类，聚类的中心分别为随机初始的样本点 16     #最初，clusters是有5个Cluster的List 17     #每个Cluster的centroID都是init_sample中的值，因为只有一个中心点嘛，它的中心自然就是自己了 18     #这也可以看成是初始化Cluster 19     clusters = [Cluster([sample]) for sample in init_samples] 20  21  22     # 迭代循环直到聚类划分稳定 23  24     #记录循环次数 25     n_loop = 0 26     while True: 27         # 初始化一组空列表用于存储每个聚类内的样本点 28         #注意：我们现在是要把所有的sample分开来存在这以下的5个空的List中 29         #但是，我们最终要得到的是分好类的clusters，并非分好的Lists，所以还会有将Lists中的值转移到clusters中的步骤 30         Lists = [[] for _ in clusters] 31  32         # 开始迭代 33         n_loop += 1 34         # 遍历样本集中的每个样本 35         for sample in samples: 36             # 计算样本点sample和第一个聚类中心的距离 37             smallest_distance = get_distance(sample,clusters[0].centroID) 38             # 初始化属于聚类 0 39             cluster_index = 0 40  41             # 计算和其他聚类中心的距离 42             #分别算出sample和另外四个cluster的centroID的距离 43             for i in range(k - 1): 44                 # 计算样本点sample和聚类中心的距离 45                 distance = get_distance(sample,clusters[i+1].centroID) 46                 # 如果存在更小的距离，更新距离 47                 if distance < smallest_distance: 48                     smallest_distance = distance 49                     cluster_index = i + 1 50  51             # 找到最近的聚类中心，更新所属聚类 52             Lists[cluster_index].append(sample) 53  54         #运行至此，1000个样本点根据距离最小的分类方案分别存在了5个List当中 55         # 初始化最大移动距离 56         biggest_shift = 0.0 57  58         # 计算本次迭代中，聚类中心移动的距离 59         for i in range(k): 60             #注意：这个update方法不仅计算出了原来的聚类中心和新的聚类中心的距离 61             #而且，他把List中的值更新到cluster当中了，并且每个cluster的centroID也在这一步更新了 62             shift = clusters[i].update(Lists[i]) 63             # 记录最大移动距离 64             biggest_shift = max(biggest_shift,shift) 65  66         # 如果聚类中心移动的距离小于收敛阈值，即：聚类稳定 67         if biggest_shift < cutoff: 68             print("第{}次迭代后，聚类稳定。".format(n_loop)) 69             break 70     # 返回聚类结果 71     return clusters 72  73  74 def run_main(): 75     """ 76         主函数 77     """ 78     # 样本个数 79     n_samples = 1000 80  81     # 维度 82     n_feat = 2 83  84     # 生成的点的范围，也就是0到200 85     lower = 0 86     upper = 200 87  88     # 聚类个数 89     n_cluster = 5 90  91     # 生成随机样本 92     samples = [gen_random_sample(n_feat,upper) for _ in range(n_samples)] 93  94     # 收敛阈值 95     cutoff = 0.2 96  97     #将1000个随机sample，聚类个数，和收敛阈值传入kmeans方法， 98     #返回的是经过无监督学习后自动分好类的5个Cluster 99     #此函数是理解kmeans的关键100     clusters = kmeans(samples,n_cluster,cutoff)101 102     # 输出结果103     for i,c in enumerate(clusters):104         for sample in c.samples:105             print(‘聚类--{}，样本点--{}‘.format(i,sample))106 107     # ---------------------算法结束，以下是画图-----------------------------------------------------------------108 109     # 可视化结果110     plt.subplot()111     color_names = List(mcolors.cnames)112     # 将5个Cluster以scatter的方式显示113     for i,c in enumerate(clusters):114         x = []115         y = []116 117         # 这里i是循环次数，是固定的，所以从color_names中取出的颜色也是固定的，这个你可以所以改动118         color = [color_names[i]] * len(c.samples)119         for sample in c.samples:120             x.append(sample.coords[0])121             y.append(sample.coords[1])122         plt.scatter(x,y,c=color)123     plt.show()124 125 if __name__ == ‘__main__‘:126     run_main()

kmeans方法的是算法的核心，我的注释已经写得十分详细了。

我们看看运行结果吧：

我在这里只是随机运行了三次，其实改变的只是样本点不同罢了，结果还是很满意的。

你当然可以改变k以及收敛阈值的值，观察结果的改变。

总结

以上是内存溢出为你收集整理的K-means聚类（一）全部内容，希望文章能够帮你解决K-means聚类（一）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。