今天我们来学习 K-Means 算法，这是一种非监督学习。所谓的监督学习和非监督学习的区别就是样本中是否存在标签，对于有标签的样本做分析就是监督学习，而对没有标签的样本做分析就属于非监督学习。
K-Means 解决的是聚类的问题，就是把样本根据某些特征，按照某些中心点，聚类在一起，从而达到分类的效果。K 代表的是 K 类，Means 代表的是中心，所以该算法的本质其实就是确定 K 类的中心点，当我们找到中心点后，也就完成了聚类。
聚类的应用场景是非常多的，比如给用户群分类，对用户行为划分等待，特别是在没有标签的情况下，只能只用聚类的方式做分析。
K-Means 原理
还记得我们在 KNN 算法中使用的 offer 案例吗
现在我们把这个例子稍微修改下
我们把例子中每个人是否能够获得 offer 这个信息去掉，即我们现在拥有的信息只是每个人的工作经验和当前工资，那么对于小 K 来说，该怎么判别他是否能够获得 offer 呢
K-Means 模型假设
将某一些数据分为不同的类别，在相同的类别中数据之间的距离应该都很近，也就是说离得越近的数据应该越相似，再进一步说明，数据之间的相似度与它们之间的欧式距离成反比。这就是 k-means 模型的假设。
有了这个假设，我们对将数据分为不同的类别的算法就更明确了，尽可能将离得近的数据划分为一个类别。那么现在的问题就转变为一个求中心和距离的问题了。
K-Means 算法
其实 K-Means 算法也是非常简单的一种算法，我们可以把它概括为两步
- 初始化
随机选择 K 个点，作为初始中心，每个点代表一个 group
- 迭代更新
1）计算每个点到所有中心点的距离，把最近的距离记录下来并把 group 赋给当前的点
2）针对每一个 group 里的点，计算其平均并把该值作为 group 的新的中心点
3）重复上面的两步，直到 group 不再变化为止，或者到达设置的最大迭代次数。
下面我们使用一组图片来具体体会下这个算法的过程
图片 a：有初始状态如图中的样本，现在随机选择两个初始点
图片 b：依次计算所有样本点到两个初始点的距离，根据距离的大小，把样本点分配到不同的中心点上。
图片 c：再把左上部分的点计算平均值，得到左上部分的新的中心点，右下类同，可以得到新的中心点，这就是一个迭代后的聚类情况
图片 d：开始第二次迭代，再把所有的点依次计算到中心点的距离，可以得到新的聚类情况
图片 e：再次计算新的聚类中点的平均值，得出新的中心点
图片 f：重复 d 的过程，中心点不再变化
图片 i：聚类完成
K-Means 算法实现
首先我们先导入下准备好的规整的数据
from copy import deepcopy import numpy as np import pandas as pd from matplotlib import pyplot as plt k_means_data = pd.read_csv('k-meansdata.csv') print(k_means_data.shape) print(k_means_data.head()) >>> (3000, 2) V1 V2 0 2.072345 -3.241693 1 17.936710 15.784810 2 1.083576 7.319176 3 11.120670 14.406780 4 23.711550 2.557729
下面再把我们准备的数据可视化出来，整体观察下
data1 = k_means_data['V1'].values data2 = k_means_data['V2'].values X = np.array(list(zip(data1, data2))) plt.scatter(X[:,0], X[:,1], s=6)
可以清楚的看出，当前的数据可以大致聚类成3类，那么下面我们就手写一个 k-Means 算法来完成这个聚类的过程
def self_kmeans(data, k): m, n = data.shape results = np.empty(m) cores = np.copy(data[np.random.randint(0, m, size=k)]) coreChange = True while coreChange: for i in range(m): distance = np.linalg.norm(data[i] - cores, axis=1) result = np.argmin(distance) results[i] = result cores_old = deepcopy(cores) for i in range(k): points = [data[j] for j in range(m) if results[j] == i] cores[i] = np.mean(points, axis=0) if (cores_old == cores).all(): return results, cores
我们来逐行看下代码
我们定义了一个 self_kmeans 的函数，接收两个参数，第一个是样本数据，是矩阵的形式；第二个是需要聚类的数量 k
接着我们通过 shape 属性获取到矩阵数据的行和列的数值，再定义聚类结果 results，用于存储最终的聚类结果。
对于中心点 cores，是通过 numpy 的 randint 函数来做随即处理的。
接下来就就如 while 循环了，首先遍历所有的样本（ for i in range(m)），并计算样本与中心点的距离，通过 norm 范数来计算。
所谓的范数，是线性代数领域的概念，是具有长度概念的函数，而向量二范数就是向量的长度。
接下来，通过计算距离，把距离最短的归为一类，再把当前的中心点保存下来。
下面更新中心点，遍历 K 值，求出每个类别里所有点的均值，作为新的中心点。
最后的 if 判断代码是用来退出 while 循环的，如果中心点不再改变，再退出函数，返回类别和中心点。
下面我们运行下函数，看看结果如何
result, core = self_kmeans(X, 3) colors = ['r', 'g', 'b', 'y', 'c', 'm'] fig, ax = plt.subplots() for i in range(3): points = np.array([X[j] for j in range(len(X)) if result[j] == i]) ax.scatter(points[:, 0], points[:, 1], s=7, c=colors[i]) ax.scatter(cores[:, 0], cores[:, 1], marker='*', s=200, c='#050505')
可以看到，还是比较好的聚类区分出了三类数据点，当然这里我们准备的数据样本比较简单，如果我们使用随机的样本点呢，聚类结果会是怎么样的呢
我们把样本点 X 替换一下
X = np.random.random((200, 2))*10
对于这种完全随机的样本点，我们再带入 K-Means 函数，查看结果
第一次运行
第二次运行
第三次运行
可以明显的看出，每次运行的结果，都会有微小的差别，这说明不同的初始数据，最后产生的聚类结果也不尽相同。
K-Means 的几个问题
不同的初始化数据，是否会产生不同的结果：
就如同我们上面演示所示，不同的初始化数据，最终的聚类结果也不相同。
那么该如何更好的选择初始化数据呢，一般可以采用 k-means++ 的方式来处理
k-means++
它的工作流程大致如下：
1、从输入的数据点集合中随机选择一个点作为第一个聚类中心
2、对于数据集中的每一个点 x，计算它与最近聚类中心(指已选择的聚类中心)的距离 D(x)
3、选择一个新的数据点作为新的聚类中心，选择的原则是：D(x) 较大的点，被选取作为聚类中心的概率较大
4、重复2和3直到 k 个聚类中心被选出来
5、利用这 k 个初始的聚类中心来运行标准的 k-means 算法
我们可以看到，通过 k-means++ 的逻辑，可以很好的保证我们选择的初始数据点不会过于集中，这样就能保证更好的聚类效果，也能减少计算量。
K 值该如何选择：
对于 K 值的选择，主要使用手肘法
手肘法
手肘法的评判指标是误差平方和
其核心思想是随着聚类 K 的增大，样本划分会更加精细，每个类别的聚合程度会逐渐提高，那么误差平方和就会逐渐变小。当 K 小于真实的聚类数时，SS 的下降幅度会很大，而当 K 大于真实的聚类数时，SS 的下降幅度会变的很小，如果画成一条曲线，会类似于一个手肘的形状，故而称为手肘法。
类似图表如下
可以看到从 k = 4 开始曲线的变化逐渐变缓，所以 k = 4 应该是最佳的 k 值
对于手肘法和 k-means++ 的具体使用，我们会在下一节详细讲解。
优缺点
优点
算法简单，容易理解，而且适用于高维数据
缺点
对离群点、噪声点和孤立点很敏感，初始点的选择好坏，决定了聚类结果的好坏
总结
今天讲解了 K-Means 算法的原理和算法模型，K-Means 的两个核心点就是设置初始数据和迭代更新中心点。
接下来我们又手动实现了一个简单的 K-Means 算法，通过不同的数据验证，我们还发现不同的初始值，不会产生不同的聚类结果，所以初始值的选择是非常重要的。
对于初始值的选择，我们一般采用 k-means++ 的方式来处理，尽量使得 K 个初始点之间的距离最大；而对于 K 值的选择，可以使用手肘法，通过观察曲线的拐点来选择最佳的 K 值。
本文涉及的代码和数据可以在这里下载
https://github.com/zhouwei713/DataAnalyse/tree/master/K-Means
练习题
今天讲的 K-Means 和前面学习的 K-NN 有什么异同呢？
