【ML】K均值聚类及Python手写实现（详细）

目录

一、闵可夫斯基距离

1.1 曼哈顿距离

1.2 欧式距离

1.3 VDM距离

二、K_means聚类算法

2.1 算法流程

2.2 算法描述

三、Python实现K_means聚类算法

3.1 导入第三方模块

3.2 加载数据集函数

3.3 计算欧式距离函数

3.4 K_means聚类函数

3.5 聚类结果可视化函数

3.6 主函数

四、运行结果

4.1 终端输出

4.2 可视化输出

五、整体总结

六、总代码

写在前面

本篇文章介绍了K均值聚类算法的原理，以及使用Python从零实现该算法。若有不足，欢迎指正。

一、闵可夫斯基距离

对于给定两个样本：

闵可夫斯基距离公式：

n：代表特征数；

1.1 曼哈顿距离

p=1时，闵可夫斯基即是曼哈顿距离：

1.2 欧式距离

p=2时，闵可夫斯基距离即是欧氏距离：

1.3 VDM距离

上面计算距离的公式只适用于“连续属性”和“有序的离散属性”，而对于“无序的离散属性”上面公式显然不成立，需要用到下面的VDM公式，表示属性u上两个离散值a与b之间的距离：

：表示在属性u上取值为a的样本数；

：表示在第i个样本簇中在属性u上取值为a的样本数；

k：表示样本簇数（聚类数）；

二、K_means聚类算法

2.1 算法流程

2.2 算法描述

输入：输入样本集D和聚类数k。

过程：

首先从样本集D中随机选取k个样本作为初始的均值向量centers。

然后下面进入迭代聚类，初始化每一个簇cluster为空集，然后对每一个样本分别对每一个均值向量center计算距离，选择其中距离最小的，并将该样本划分进对应的簇中。

对划分好的每一个簇cluster重新计算得到新的均值向量new_center，并比较旧的均值向量，如果不相等则更新均值向量centers，如果相等则保持均值向量不变。直到所有的均值向量都不更新时跳出迭代循环，得到最终的聚类结果。

输出：输出聚类的最终结果clusters。

总之，整体流程：初始化均值向量——>聚类——>更新均值向量——>输出簇。

三、Python实现K_means聚类算法

3.1 导入第三方模块

import numpy as np import pandas as pd import matplotlib.pyplot as plt

（1）numpy、pandas模块用于数值处理；

（2）matplotlib.pyplot用于可视化数据；

3.2 加载数据集函数

#? 加载数据集 # return: 返回数据集dataSet和特征名称labels def loadDataSet(): dataSet = [[0.697, 0.460], [0.774, 0.376], [0.634, 0.264], [0.608, 0.318], [0.556, 0.215], [0.403, 0.237], [0.481, 0.149], [0.437, 0.211], [0.666, 0.091], [0.243, 0.267], [0.245, 0.057], [0.343, 0.099], [0.639, 0.161], [0.657, 0.198], [0.360, 0.370], [0.593, 0.042], [0.719, 0.103], [0.359, 0.188], [0.339, 0.241], [0.282, 0.257], [0.748, 0.232], [0.714, 0.346], [0.483, 0.312], [0.478, 0.437], [0.525, 0.369], [0.751, 0.489], [0.532, 0.472], [0.473, 0.376], [0.725, 0.445], [0.446, 0.459]] labels = ['密度','含糖率'] # 查看数据集 df = pd.DataFrame(data=dataSet, columns=labels) #print(df) return dataSet, labels

变量说明：

dataSet：西瓜集的数据集，一个二维矩阵，一共30行样本数据，第1列表示“密度”，第2表示“含糖率”；

labels：存放样本的特征名称；

df：数据集的二维结构；终端输出如下方图3-1；

返回值：

返回数据集dataSet，和特征名称labels；

函数作用：

加载数据集；

3.3 计算欧式距离函数

#? 求欧式距离 # params: sample:单个数据样本, center:k个样本的均值向量 # return: 返回单个样本sample属于哪一个簇的索引cls def distance(sample, centers): dist = np.power(sample - centers, 2).sum(axis=1) # 欧式距离 cls = np.argmin(dist) # 选出最小距离的索引 #print(dist) #print(cls) return cls

变量说明：

sample：传入的单个样本数据；

centers：k个均值向量；

dist：存储单个样本sample与各个均值向量center的欧式距离，是一个一维向量（因为均值向量不止一个）；

cls：存储一维向量dist中最小值的索引；

返回值：

返回单个样本sample划分到指定簇的索引cls；

函数作用：

计算欧氏距离，并对单样本sample划分进合适的簇；

3.4 K_means聚类函数

#? K_means聚类 # params: dataSet:数据集, k:聚类数 # return: 返回最终的各个均值向量centers和划分好的所有簇clusters # 关键变量: clusters:各个簇, centers:各个均值向量 def k_means(dataSet, k): dataSet = np.array(dataSet) #? 选取均值向量centers np.random.seed(123) # 设置随机数种子(保证每次运行文件随机数不变) centers = dataSet[np.random.choice(dataSet.shape[0], k, replace=False)] # 初始化k个均值向量(随机选取k个样本) #print(centers) #? 进入循环迭代训练 while True: #? 计算所有簇clusters clusters = [[] for i in range(k)] # 初始化k个簇 #print(clusters) for sample in dataSet: clusters_index = distance(sample, centers) # 计算欧氏距离 clusters[clusters_index].append(sample) # 划分到对应簇 #? 计算新均值向量centers new_center0 = np.array(clusters[0]).mean(axis=0) new_center1 = np.array(clusters[1]).mean(axis=0) new_center2 = np.array(clusters[2]).mean(axis=0) # 判断是否满足训练完成的条件 if (new_center0 == centers[0]).all() and (new_center1 == centers[1]).all() and (new_center2 == centers[2]).all(): break #? 更新均值向量centers else: centers[0] = new_center0 centers[1] = new_center1 centers[2] = new_center2 return centers, clusters

变量说明：

dataSet：数据集；

k：聚类数；

centers：存储各个簇的均值向量；

clusters：存储划分出来的各个簇；

sample：数据集中的单个样本；

new_center0：计算出的新第一个簇的均值向量；

返回值：

返回最终划分好的所有簇clusters，以及每个簇的均值向量（中心）；

函数作用：

该函数中首先随机选取了k个样本作为每个簇的初始均值向量。然后进入循环迭代聚类，先遍历各个样本求其欧氏距离对其进行簇的划分，再重新计算各个簇的均值向量，进行更新每个簇的均值向量，直到所有簇的均值向量都不更新跳出循环，说明所有簇已经聚类完毕。

3.5 聚类结果可视化函数

#? 可视化 # params: dataSet:数据集, clusters:簇, centers:均值向量 def clusters_show(dataSet, clusters, centers): plt.figure(figsize=(12, 5)) # 设置整个画布尺寸 color = ["m", "b", "c"] # 设置色彩集 marker = ["*", "^", "p"] # 设置标记集 #? 绘制聚类之前的散点图 plt.subplot(1,2,1) plt.title("Before K_means") # 图像标题 plt.xlabel("density", loc="center") # x轴名称 plt.ylabel("sugar", loc="center") # y轴名称 dataSet = np.array(dataSet) plt.scatter(dataSet[:, 0], # 散点的横坐标 dataSet[:, 1], # 散点的纵坐标 c='m', # 散点的颜色【品红】 marker='.', # 散点的样式【点】 s=150, # 散点的面积【150】 label='sample') # 散点的图例 plt.legend() # (不稳定)显示图例 plt.gca().set_aspect(1) # x、y轴单位长度相等 #? 绘制聚类之后的散点图 plt.subplot(1,2,2) plt.title("After K_means") # 图像标题 plt.xlabel("density", loc="center") # x轴名称 plt.ylabel("sugar", loc="center") # y轴名称 for index, cluster in enumerate(clusters): cluster = np.array(cluster) plt.scatter(cluster[:, 0], # 散点的横坐标 cluster[:, 1], # 散点的纵坐标 c=color[index], # 散点的颜色 marker=marker[index], # 散点的样式 s=100, # 散点的面积 label=index) # 散点的图例 #? 绘制聚类后的中心点(均值向量) plt.scatter(centers[:, 0], # 散点横坐标 centers[:, 1], # 散点纵坐标 c='r', # 散点的颜色【红色】 marker='o', # 散点的样式【圆】 s=100, # 散点的面积【100】 label="centers") # 散点的图例 plt.legend() # (不稳定)显示图例 plt.gca().set_aspect(1) # 使x、y轴单位长度相等 plt.show()

变量说明：

dataSet：数据集；

clusters：所有簇；

centers：各个簇的均值向量；

函数作用：

该函数首先自定义了一些颜色集和标记集，用于后面区别聚类后的不同类别的样本散点。

可视化函数中画了两个子图分别来显示聚类前（title：Before K_means）和聚类后（title: After K_means）的样本散点分布。通过两个子图在同一个画布中的对比可以看出聚类的效果。首先绘制了聚类前的子图；又绘制了聚类后的子图，聚类后的子图中不同类别的样本在图中呈现的散点样式、颜色均不同，易于用肉眼看出聚类的不同类别分布；紧接着又在聚类后的子图中绘制了不同类别的中心（均值向量）centers，用于呈现聚类的中心点。最终的可视化呈现效果可在结果分析中可以看到。

3.6 主函数

#? 主函数 if __name__=='__main__': dataSet, labels = loadDataSet() centers, clusters = k_means(dataSet, 3) # 可视化输出 clusters_show(dataSet, clusters, centers) # 终端输出 print("=====================第一个簇=====================") print(f'第1个簇共有样本 {len(clusters[0])} 个') print(f'均值向量：{centers[0]}') print(pd.DataFrame(clusters[0], columns=labels)) print("=====================第二个簇=====================") print(f'第2个簇共有样本 {len(clusters[1])} 个') print(f'均值向量：{centers[1]}') print(pd.DataFrame(clusters[1], columns=labels)) print("=====================第三个簇=====================") print(f'第3个簇共有样本 {len(clusters[2])} 个') print(f'均值向量：{centers[2]}') print(pd.DataFrame(clusters[2], columns=labels))

函数作用：

将上述所有的函数模块连接成一个整体，相互协作共同实现K_means聚类算法。通过调用k_means()函数可以看到我们选择的聚类数为3。下面就是调用可视化函数进行可视化输出；在下面是设置在终端输出的一些信息：每个簇包含的样本总数、其均值向量、所包含的所有样本数据。

四、运行结果

4.1 终端输出

第1个簇中包含了9个样本数据，其均值向量为[0.633,0.162]：

第2个簇中包含了12个样本数据，其均值向量为[0.601,0.405]：

第3个簇中包含了9个样本数据，其均值向量为[0.335,0.214]：

4.2 可视化输出

左图为聚类前的样本分布散点图，右图为聚类后的样本被不同标记不同颜色标记类别后的散点图。

从聚类后的效果可以看到聚类了3类，“星号”、“三角形”、“五边形”分别表示了这3类，“红色点”代表每一类的中心center（均值向量），通过观察发现center大致都分布在其类别的中心位置，符合理论。聚类效果还是很好的，能够很好的对样本进行类别集中划分。

五、整体总结

理解上述代码中的一些基本知识：

1、np.power(sample - centers, 2).sum(axis=1)

axis=1 : 横向(行)求sum; axis=0 : 纵向(列)求sum；

sample : 一维向量(数组只有一行数据); centers : 二维向量(数组有多行数据)；

np.power(一维 - 二维, 2) : sample分别于centers中的每一行数据进行减法并power操作, 返回一个二维向量；

.sum(axis=1) : 对上面得到的二维向量按行求和, 得到一个一维向量；

2、cls = np.argmin(dist)

np.argmin(dist) : dist这里是一个一维向量, 。argmin()函数返回其最小值的索引；

3、(new_center0 == centers[0]).all()

两者均为数组类型，每个数组具有2个元素，使整体的bool值明确还需使用.all()/.any()来明确其真值；

4、dataSet[np.random.choice(dataSet.shape[0], k, replace=False)]

dataSet.shape[0] : 查看dataSet有多少行数据,此处是一个整数；

np.random.choice(dataSet.shape[0], k, replace=False) : 在上面求得的整数中随机取k个数值,replace=False限制随机取数时不可以重复取同一个数值；

dataSet[数值] : 取索引为指定数值的dataSet元素；

5、plt.sactter(..., label=...) 后使用 plt.legend()

问题所在: 绘制散点图时已设置标签,如plt.sactter(..., label=...),最后plt.show时图像中不显示图例；

解决方法: plt.scatter(..., label=...)后使用plt.legend()；

6、plt.gca().set_aspect(1)

对某一子图使用,使该图像的x、y轴的单位长度相等；

六、总代码

import numpy as np import pandas as pd import matplotlib.pyplot as plt #? 加载数据集 # return: 返回数据集dataSet和特征名称labels def loadDataSet(): dataSet = [[0.697, 0.460], [0.774, 0.376], [0.634, 0.264], [0.608, 0.318], [0.556, 0.215], [0.403, 0.237], [0.481, 0.149], [0.437, 0.211], [0.666, 0.091], [0.243, 0.267], [0.245, 0.057], [0.343, 0.099], [0.639, 0.161], [0.657, 0.198], [0.360, 0.370], [0.593, 0.042], [0.719, 0.103], [0.359, 0.188], [0.339, 0.241], [0.282, 0.257], [0.748, 0.232], [0.714, 0.346], [0.483, 0.312], [0.478, 0.437], [0.525, 0.369], [0.751, 0.489], [0.532, 0.472], [0.473, 0.376], [0.725, 0.445], [0.446, 0.459]] labels = ['密度','含糖率'] # 查看数据集 df = pd.DataFrame(data=dataSet, columns=labels) #print(df) return dataSet, labels #? 求欧式距离 # params: sample:单个数据样本, center:k个样本的均值向量 # return: 返回单个样本sample属于哪一个簇的索引cls def distance(sample, centers): dist = np.power(sample - centers, 2).sum(axis=1) # 欧式距离 cls = np.argmin(dist) # 选出最小距离的索引 #print(dist) #print(cls) return cls #? K_means聚类 # params: dataSet:数据集, k:聚类数 # return: 返回最终的各个均值向量centers和划分好的所有簇clusters # 关键变量: clusters:各个簇, centers:各个均值向量 def k_means(dataSet, k): dataSet = np.array(dataSet) #? 选取均值向量centers np.random.seed(123) # 设置随机数种子(保证每次运行文件随机数不变) centers = dataSet[np.random.choice(dataSet.shape[0], k, replace=False)] # 初始化k个均值向量(随机选取k个样本) #print(centers) #? 进入循环迭代训练 while True: #? 计算所有簇clusters clusters = [[] for i in range(k)] # 初始化k个簇 #print(clusters) for sample in dataSet: clusters_index = distance(sample, centers) # 计算欧氏距离 clusters[clusters_index].append(sample) # 划分到对应簇 #? 计算新均值向量centers new_center0 = np.array(clusters[0]).mean(axis=0) new_center1 = np.array(clusters[1]).mean(axis=0) new_center2 = np.array(clusters[2]).mean(axis=0) # 判断是否满足训练完成的条件 if (new_center0 == centers[0]).all() and (new_center1 == centers[1]).all() and (new_center2 == centers[2]).all(): break #? 更新均值向量centers else: centers[0] = new_center0 centers[1] = new_center1 centers[2] = new_center2 return centers, clusters #? 可视化 # params: dataSet:数据集, clusters:簇, centers:均值向量 def clusters_show(dataSet, clusters, centers): plt.figure(figsize=(12, 5)) # 设置整个画布尺寸 color = ["m", "b", "c"] # 设置色彩集 marker = ["*", "^", "p"] # 设置标记集 #? 绘制聚类之前的散点图 plt.subplot(1,2,1) plt.title("Before K_means") # 图像标题 plt.xlabel("density", loc="center") # x轴名称 plt.ylabel("sugar", loc="center") # y轴名称 dataSet = np.array(dataSet) plt.scatter(dataSet[:, 0], # 散点的横坐标 dataSet[:, 1], # 散点的纵坐标 c='m', # 散点的颜色【品红】 marker='.', # 散点的样式【点】 s=150, # 散点的面积【150】 label='sample') # 散点的图例 plt.legend() # (不稳定)显示图例 plt.gca().set_aspect(1) # x、y轴单位长度相等 #? 绘制聚类之后的散点图 plt.subplot(1,2,2) plt.title("After K_means") # 图像标题 plt.xlabel("density", loc="center") # x轴名称 plt.ylabel("sugar", loc="center") # y轴名称 for index, cluster in enumerate(clusters): cluster = np.array(cluster) plt.scatter(cluster[:, 0], # 散点的横坐标 cluster[:, 1], # 散点的纵坐标 c=color[index], # 散点的颜色 marker=marker[index], # 散点的样式 s=100, # 散点的面积 label=index) # 散点的图例 #? 绘制聚类后的中心点(均值向量) plt.scatter(centers[:, 0], # 散点横坐标 centers[:, 1], # 散点纵坐标 c='r', # 散点的颜色【红色】 marker='o', # 散点的样式【圆】 s=100, # 散点的面积【100】 label="centers") # 散点的图例 plt.legend() # (不稳定)显示图例 plt.gca().set_aspect(1) # 使x、y轴单位长度相等 plt.show() #? 主函数 if __name__=='__main__': dataSet, labels = loadDataSet() centers, clusters = k_means(dataSet, 3) # 可视化输出 clusters_show(dataSet, clusters, centers) # 终端输出 print("=====================第一个簇=====================") print(f'第1个簇共有样本 {len(clusters[0])} 个') print(f'均值向量：{centers[0]}') print(pd.DataFrame(clusters[0], columns=labels)) print("=====================第二个簇=====================") print(f'第2个簇共有样本 {len(clusters[1])} 个') print(f'均值向量：{centers[1]}') print(pd.DataFrame(clusters[1], columns=labels)) print("=====================第三个簇=====================") print(f'第3个簇共有样本 {len(clusters[2])} 个') print(f'均值向量：{centers[2]}') print(pd.DataFrame(clusters[2], columns=labels))