K-means聚类算法原理及python实现

一.聚类算法的简介

        对于”监督学习“(supervised learning)，其训练样本是带有标记信息的，并且监督学习的目的是：对带有标记的数据集进行模型学习，从而便于对新的样本进行分类。而在“无监督学习”(unsupervised learning)中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。对于无监督学习，应用最广的便是”聚类“(clustering)。
        “聚类算法“试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念或类别。
        我们可以通过下面这个图来理解：

        上图是未做标记的样本集，通过他们的分布，我们很容易对上图中的样本做出以下几种划分。
                当需要将其划分为两个簇时，即 k=2时：

        当需要将其划分为四个簇时，即 k=4 时：

二.K-means聚类算法

• 优点：容易实现
• 缺点：可能收敛到局部最小值，在大规模数据上收敛较慢

三.K-means算法步骤详解

Step1.K值的选择

k 的选择一般是按照实际需求进行决定，或在实现算法时直接给定 k 值。

Step2.距离度量

        将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略，在欧式空间中采用的是欧式距离，在处理文档中采用的是余弦相似度函数，有时候也采用曼哈顿距离作为度量，不同的情况实用的度量公式是不同的。

2.1.欧式距离

2.2.曼哈顿距离

2.3.余弦相似度

Step3.新质心的计算

        对于分类后的产生的k个簇，分别计算到簇内其他点距离均值最小的点作为质心（对于拥有坐标的簇可以计算每个簇坐标的均值作为质心）

Step4.是否停止K-means

        质心不再改变，或给定loop最大次数loopLimit

四.python实现+代码详解

        以下是python得实例代码以及代码的详解，应该可以理解的。

import random import pandas as pd import numpy as np import matplotlib.pyplot as plt # 计算欧拉距离 def calcDis(dataSet, centroids, k): clalist=[] for data in dataSet: diff = np.tile(data, (k, 1)) - centroids #相减 (np.tile(a,(2,1))就是把a先沿x轴复制1倍，即没有复制，仍然是 [0,1,2]。 再把结果沿y方向复制2倍得到array([[0,1,2],[0,1,2]])) squaredDiff = diff  2 #平方 squaredDist = np.sum(squaredDiff, axis=1) #和 (axis=1表示行) distance = squaredDist  0.5 #开根号 clalist.append(distance) clalist = np.array(clalist) #返回一个每个点到质点的距离len(dateSet)*k的数组 return clalist # 计算质心 def classify(dataSet, centroids, k): # 计算样本到质心的距离 clalist = calcDis(dataSet, centroids, k) # 分组并计算新的质心 minDistIndices = np.argmin(clalist, axis=1) #axis=1 表示求出每行的最小值的下标 newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean() #DataFramte(dataSet)对DataSet分组，groupby(min)按照min进行统计分类，mean()对分类结果求均值 newCentroids = newCentroids.values # 计算变化量 changed = newCentroids - centroids return changed, newCentroids # 使用k-means分类 def kmeans(dataSet, k): # 随机取质心 centroids = random.sample(dataSet, k) # 更新质心 直到变化量全为0 changed, newCentroids = classify(dataSet, centroids, k) while np.any(changed != 0): changed, newCentroids = classify(dataSet, newCentroids, k) centroids = sorted(newCentroids.tolist()) #tolist()将矩阵转换成列表 sorted()排序 # 根据质心计算每个集群 cluster = [] clalist = calcDis(dataSet, centroids, k) #调用欧拉距离 minDistIndices = np.argmin(clalist, axis=1) for i in range(k): cluster.append([]) for i, j in enumerate(minDistIndices): #enymerate()可同时遍历索引和遍历元素 cluster[j].append(dataSet[i]) return centroids, cluster # 创建数据集 def createDataSet(): return [[1, 1], [1, 2], [2, 1], [6, 4], [6, 3], [5, 4]] if __name__=='__main__': dataset = createDataSet() centroids, cluster = kmeans(dataset, 2) print('质心为：%s' % centroids) print('集群为：%s' % cluster) for i in range(len(dataset)): plt.scatter(dataset[i][0],dataset[i][1], marker = 'o',color = 'green', s = 40 ,label = '原始点') # 记号形状 颜色 点的大小 设置标签 for j in range(len(centroids)): plt.scatter(centroids[j][0],centroids[j][1],marker='x',color='red',s=50,label='质心') plt.show() 

五.K-means算法补充

1.对初始化敏感，初始质点k给定的不同，可能会产生不同的聚类结果。如下图所示，右边是k=2的结果，这个就正好，而左图是k=3的结果，可以看到右上角得这两个簇应该是可以合并成一个簇的。

4.最终会收敛。不管初始点如何选择，最终都会收敛。可是是全局收敛，也可能是局部收敛。

六.小结

        1. 聚类是一种无监督的学习方法。聚类区别于分类，即事先不知道要寻找的内容，没有预先设定好的目标变量。

        2. 聚类将数据点归到多个簇中，其中相似的数据点归为同一簇，而不相似的点归为不同的簇。相似度的计算方法有很多，具体的应用选择合适的相似度计算方法

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

        4. K-means算法虽然有效，但是容易受到初始簇质心的情况而影响，有可能陷入局部最优解。为了解决这个问题，可以使用另外一种称为二分K-means的聚类算法。二分K-means算法首先将所有数据点分为一个簇；然后使用K-means（k=2）对其进行划分；下一次迭代时，选择使得SSE下降程度最大的簇进行划分；重复该过程，直至簇的个数达到指定的数目为止。实验表明，二分K-means算法的聚类效果要好于普通的K-means聚类算法。