机器学习笔记：K-means聚类算法的Python实现

vlambda
2021-03-30

机器学习笔记：K-means聚类算法的Python实现

聚类是一种无监督学习，它将相似的对象归到同一个簇中，簇中的对象越相似，聚类的效果越好。聚类的目标是簇内数据相似度高，簇间拉大距离。K-means是聚类算法中的一种，能够将样本按照距离远近划分成不同个簇。其中 K是指簇的数量，means是指均值。

简

介

K-menas聚类算法过程

K-means算法的工作流程是这样的。首先，随机确定k个初始点作为质心，然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点距离其最近的质心，将其分配给该质心所对应的簇。之后每个簇的质心更新为该簇所有点的平均值。之后不断重复以上流程，直到质心位置不再改变（样本簇的分配不再改变）。

算法步骤

①随机选取k个样本作为初始的聚类中心。

②计算每个样本到各个聚类中心之间的距离，将每个样本分配给距离它最近的聚类中心，此时全部样本已划分为k组。

③更新聚类中心，将每组中样本的均值作为该组新的聚类中心。

④重复进行第二、三步，直到聚类中心趋于稳定，或者到达最大迭代次数。

寻找最优K值

簇内误差平方和是衡量聚类效果的常用方法，是指所有样本到对应质心的距的平方和，如下面的公式:

其中K为簇数,为第簇的质心，p是样本。

机器学习笔记：K-means聚类算法的Python实现

用 Elbow method（手肘法），随着K值的变大，SSE值下降的幅度越来越小，SSE下降开始不明显的那个点，就是我们需要的K值。下面是SSE-K的一般性关系。

Python代码部分实现

完成该算法的重点在于初始随机质心和距离的计算，只要解决了这两大问题，算法的实现会变得轻松许多。具体的算法和函数的使用见下述代码及其注释：

1. 数据的处理和包的使用

import random as rdimport numpy as npimport pandas as pdimport matplotlib.pyplot as pltimport matplotlib as mpl
# 读取csv文件的数据，只使用2~3列的数据（去掉Id数据和标签数据）data = pd.read_csv("D:\QQ文件/WTM.csv", header=0, usecols=[1,2])data = np.asarray(data)

2. K值的输入和距离的计算

k = int(input("请输入k的值："))
#用于计算不同的点之间距离的函数，返回一个距离列表（np类型的）def distance(data, cet, k): clalist = [] for i in data: squareDif = (np.tile(i, (k, 1)) - cet) ** 2 dis = (np.sum(squareDif, axis = 1)) ** 0.5 clalist.append(dis) clalist = np.asarray(clalist)    return clalist

3. 质心的确定和偏移量的计算

#用于计算中心点坐标位置和中心点位置的偏移量def new_chg(data, cet, k): clalist = distance(data, cet, k) minDisIdx = np.argmin(clalist, axis = 1) newCet = pd.DataFrame(data).groupby(minDisIdx).mean() newCet = newCet.values #中心点的偏移距离 chg = np.abs(newCet - cet)    return chg, newCet

4. K聚类函数的构建

#利用以上两个函数进行K聚类的函数def k_means(data, k): #随机选取中心点 listData = data.tolist() cet = rd.sample(listData, k)  #获取新的中心点和本次中心点的偏移量 chg, cet = new_chg(data, cet, k)  #判断中心的变化量是否为零或者接近零 flag = True while flag: chg, cet = new_chg(data, cet, k) cnt = 0 i = 0 while i < k: if (chg[i][1] < 10 ** -6) and (chg[i][0] < 10 ** -6): cnt += 1 i += 1 if cnt == k: flag = False cet = sorted(cet.tolist())  #根据中心确定每个集群 cluster = [] clalist = distance(data, cet, k) minDisIdx = np.argmin(clalist, axis = 1)  for i in range(k): cluster.append([])  for i, j in enumerate(minDisIdx): cluster[j].append(data[i].tolist())     return cet, cluster

5. 调用以上函数完成K聚类（包括绘制散点图）

#调用之前所写的函数，完成k聚类cet, cluster = k_means(data, k)
print("质心为：%s" % cet)print("集群为：%s" % cluster)
#作图可视化聚类结果部分mpl.rcParams["font.family"] = "SimHei"mpl.rcParams["axes.unicode_minus"] = False
plt.figure(figsize=(6,6))plt.xlabel("Density")plt.ylabel("Sugar")plt.title("使用K—means聚类结果显示（K = %d）" % k)
#构建颜色列表，用于给不同的簇上色colors = ["b", "g", "c", "m", "y"]ncolor = 0
#构建簇的名称列表，用于label标记的时候指示出是不同的簇labels = ["第一个簇", "第二个簇", "第三个簇", "第四个簇","第五个簇"]nlabel = 0
#将每个簇中的每个点画出（不同的簇采用不同的颜色）for i in range(k): for j in range(len(cluster[i])): if j == 0: plt.scatter(x = cluster[i][j][0], y = cluster[i][j][1], marker = 'o', color = colors[ncolor], label = labels[nlabel]) else: plt.scatter(x = cluster[i][j][0], y = cluster[i][j][1], marker = 'o', color = colors[ncolor])  ncolor += 1 nlabel += 1
for i in range(len(cet)): if i == 0: plt.scatter(x = cet[i][0], y = cet[i][1], marker = '*', color = 'r', label = "质心") else: plt.scatter(x = cet[i][0], y = cet[i][1], marker = '*', color = 'r') #设置标签位置plt.legend(loc="upper left")
plt.show()

6. 手肘图的绘制部分

#绘制手肘图部分#设置SSE列表，用于存储不同K取值时计算所得SSE的值SSE = []
for k in range(1,18): cet, cluster = k_means(data, k) sse = 0 for i in range(k): for j in range(len(cluster[i])): dx = cluster[i][j][0] - cet[i][0] dy = cluster[i][j][1] - cet[i][1] sse += dx ** 2 + dy ** 2 SSE.append(sse) #作图可视化K-SSE关系部分mpl.rcParams["font.family"] = "SimHei"mpl.rcParams["axes.unicode_minus"] = False
plt.figure(figsize=(6,6))K = range(1,18)plt.xlabel("K")plt.ylabel("SSE")plt.title("SSE-K关系图")plt.plot(K, SSE, "o-")plt.show()

7. 采用Iris数据集K均值聚类

由于采用不同数据集所使用的代码基本一致，对于样本数较多的数据集只需要解决当K值较大时会出现有某些簇为空的情形，故只附上有区别于西瓜数据集的代码。

#用于计算中心点坐标位置和中心点位置的偏移量def new_chg(data, cet, k): clalist = distance(data, cet, k) minDisIdx = np.argmin(clalist, axis = 1) newCet = pd.DataFrame(data).groupby(minDisIdx).mean() newCet = newCet.values  #中心点的偏移距离（此处有更改，增加了判断条件，以确保newCet中的簇不会为空） if np.array(newCet).shape == np.array(cet).shape: chg = np.abs(newCet - cet) else: listData = data.tolist() addCet = rd.sample(listData, np.array(cet).shape[0] - np.array(newCet).shape[0]) newCet = newCet.tolist() newCet.extend(addCet) newCet = np.asarray(newCet) chg = np.abs(newCet - cet)return chg, newCet
#绘制手肘图部分#设置SSE列表，用于存储不同K取值时计算所得SSE的值（这里的变化为sse距离计算增加到了四个维度，定义了dx1~dx4）SSE = []
for k in range(1,150): cet, cluster = k_means(data, k) sse = 0 for i in range(k): for j in range(len(cluster[i])): dx1 = cluster[i][j][0] - cet[i][0] dx2 = cluster[i][j][1] - cet[i][1] dx3 = cluster[i][j][2] - cet[i][2] dx4 = cluster[i][j][3] - cet[i][3] sse += dx1 ** 2 + dx2 ** 2 + dx3 ** 2 + dx4 ** 2 SSE.append(sse) print(SSE)#作图可视化K-SSE关系部分mpl.rcParams["font.family"] = "SimHei"mpl.rcParams["axes.unicode_minus"] = False
plt.figure(figsize=(6,6))K = range(1,150)plt.xlabel("K")plt.ylabel("SSE")plt.title("SSE-K关系图")plt.plot(K, SSE, "o-")plt.show()

结果展示和分析部分

1. 聚类结果可视化图片

在该算法中，取的K值为1~5，绘制出了以下聚类散点图：

机器学习笔记：K-means聚类算法的Python实现

2. 手肘图分析

西瓜数据集一共有17个数据，于是可以采用K值的从1~17的遍历操作，绘制出手肘图，以便找出最佳的K值。

机器学习笔记：K-means聚类算法的Python实现

由图中可以看出，在K取3的时候，出现了手肘点，于是可以认为，对应该数据集，K取3时能够得到最好的聚类结果。

3. Iris数据集K均值聚类结果

以下为Iris数据集的K均值聚类结果图（取了K值从1~5的情况，为了绘图的方便，只在坐标轴上选取了两个维度）：

机器学习笔记：K-means聚类算法的Python实现

另外，还绘制了K取1~150的手肘图：

机器学习笔记：K-means聚类算法的Python实现

从图中可以看出，K取3的时候是手肘点，在该值是对于该数据集最好的聚类结果。

后记——总结分析

K均值聚类算法是典型的迭代算法，练习对该算法的代码编写，可以更好地理解迭代算法的实现过程，明白迭代算法的思想。由于是随机生成的初始点，导致每一次绘制出的手肘图都不一样。可以看到，初始点的选择的不同，会对实验结果产生影响，有时候这种影响是十分明显的，好的初始点选择能够使得算法很快收敛，迭代次数很少，而不优的初始点选择，则会导致迭代次数十分多，大大增加了代码的运行时间。

另外，可以尝试使用特殊的数据集进行K均值聚类，分析得到的聚类结果是否合理，同时可以绘制他们的手肘图，观察不同分布类型的数据K取何值更好。