Artificial Intelligence-k-means算法

Artificial Intelligence

k-means算法

基本概念

K-means聚类算法（K-均值算法），是一种广泛使用的聚类算法，其中k是需要指定的参数，即需要创建的簇的数目，K-means算法中的k个簇的质心可以通过随机的方式获得，但是这些点需要位于数据范围内。在算法中，计算每个点到质心得距离，选择距离最小的质心对应的簇作为该数据点的划分，然后再基于该分配过程后更新簇的质心。重复上述过程，直至各个簇的质心不再变化为止。

原理

上图a表达了初始的数据集，假设k=2。

在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心。

然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示。

经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。

此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。

图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。

最终我们得到的两个类别如图f。

优缺点

优点

1. 属于无监督学习，无须准备训练集；
2. 结果可解释性较好。

缺点

1. 聚类数目k是一个输入参数。选择不恰当的k值可能会导致糟糕的聚类结果；
2. 可能收敛到局部最小值, 在大规模数据集上收敛较慢；
3. 对于异常点比较敏感。

代码实现

import numpy
import random
import matplotlib.pyplot as pltdef findCentroids(data_get, k):    # 随机获取k个质心return random.sample(data_get, k)def calculateDistance(vecA, vecB):    # 计算向量vecA和向量vecB之间的欧氏距离return numpy.sqrt(numpy.sum(numpy.square(vecA - vecB)))def minDistance(data_get, centroidList):# 计算data_get中的元素与centroidList中k个聚类中心的欧式距离，找出距离最小的# 将该元素加入相应的聚类中clusterDict = dict()  # 用字典存储聚类结果for element in data_get:vecA = numpy.array(element)  # 转换成数组形式flag = 0  # 元素分类标记，记录与相应聚类距离最近的那个类minDis = float("inf")  # 初始化为最大值for i in range(len(centroidList)):vecB = numpy.array(centroidList[i])distance = calculateDistance(vecA, vecB)  # 两向量间的欧式距离if distance < minDis:minDis = distanceflag = i  # 保存与当前item距离最近的那个聚类的标记if flag not in clusterDict.keys():  # 簇标记不存在，进行初始化clusterDict[flag] = list()clusterDict[flag].append(element)  # 加入相应的类中return clusterDict  # 返回新的聚类结果def getCentroids(clusterDict):centroidList = list()for key in clusterDict.keys():centroid = numpy.mean(numpy.array(clusterDict[key]), axis=0)  # 求聚类中心即求解每列的均值centroidList.append(centroid)return numpy.array(centroidList).tolist()def calculate_Var(clusterDict, centroidList):# 计算聚类间的均方误差# 将类中各个向量与聚类中心的距离进行累加求和sum = 0.0for key in clusterDict.keys():vecA = numpy.array(centroidList[key])distance = 0.0for item in clusterDict[key]:vecB = numpy.array(item)distance += calculateDistance(vecA, vecB)sum += distancereturn sumdef showCluster(centroidList, clusterDict):# 画聚类结果colorMark = ['or', 'ob', 'og', 'ok', 'oy', 'ow']  # 元素标记centroidMark = ['dr', 'db', 'dg', 'dk', 'dy', 'dw']  # 聚类中心标记for key in clusterDict.keys():plt.plot(centroidList[key][0], centroidList[key][1], centroidMark[key], markersize=12)  # 画聚类中心for item in clusterDict[key]:plt.plot(item[0], item[1], colorMark[key])  # 画类下的点plt.show()data = [[0.0, 0.0], [3.0, 8.0], [2.0, 2.0], [1.0, 1.0], [5.0, 3.0],[4.0, 8.0], [6.0, 3.0], [5.0, 4.0], [6.0, 4.0], [7.0, 5.0]]if __name__ == '__main__':centroidList = findCentroids(data, 3)  # 随机获取3个聚类中心clusterDict = minDistance(data, centroidList)  # 第一次聚类迭代newVar = calculate_Var(clusterDict, centroidList)  # 计算均方误差值，通过新旧均方误差来获得迭代终止条件oldVar = -0.0001  # 初始化均方误差print('***** 第1次迭代 *****')for key in clusterDict.keys():print('聚类中心: ', centroidList[key])print('对应聚类: ',clusterDict[key])print('平均均方误差: ', newVar)showCluster(centroidList, clusterDict)  # 展示聚类结果k = 2while abs(newVar - oldVar) >= 0.0001:  # 当连续两次聚类结果差距小于0.0001时，迭代结束centroidList = getCentroids(clusterDict)  # 获得新的聚类中心clusterDict = minDistance(data, centroidList)  # 新的聚类结果oldVar = newVarnewVar = calculate_Var(clusterDict, centroidList)print('***** 第%d次迭代 *****' % k)for key in clusterDict.keys():print('聚类中心: ', centroidList[key])print('对应聚类: ', clusterDict[key])print('平均均方误差: ', newVar)showCluster(centroidList, clusterDict)  # 展示聚类结果k += 1

运行结果