今天我们来学习 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 有什么异同呢?