K均值分类——一分钟学会无监督学习算法
简单的K均值聚类k-means clustering algorithm
基本思想
K-Means算法就是对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大。
用数学表达式就是:
假设簇划分为则我们的误差E就是:
其中是簇Ci的均值向量.
如图,我们任意选取两个初值点为中心,计算各点到中心的距离,将他们划分到距离最近的簇。第二次循环,用各族的平均向量做为中心,继续上面操作。直到质心几乎不变。
可以证明,当中心为族的样本均值,代价函数最小,这也说明算法的合理性。
算法及改进算法
传统算法
- 选取K
- 从数据集D中随机选择k个样本作为初始的k个质心向量:尽量距离不能太小。
- repeat{
1.将簇划分C初始化为
2.将各个数据点划分到距离最近的类
3.对中所有的样本点重新计算新的质心
4质心几乎不改变,跳出循环
} - 输出
K-means++(优化初始化)
这个实际上就是在选取K个初始中心时,找K个距离最大的点。
elkan_K-means(减少迭代次数)
大样本优化Mini Batch K-Means
Mini Batch,也就是用样本集中的一部分的样本来做传统的K-Means,这样可以避免样本量太大时的计算难题,算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。
在Mini Batch K-Means中,我们会选择一个合适的批样本大小batch size,我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本一般是通过无放回的随机采样得到的。
为了增加算法的准确性,我们一般会多跑几次Mini Batch K-Means算法,用得到不同的随机采样集来得到聚类簇,选择其中最优的聚类簇。
一个不得回避的问题
如何确定最佳K值
拐点法
选取一系列K值,计算对应的代价。出现拐点的地方就是最优K值。
轮廓系数(Silhouette Coefficient)
对于数据点,我们定义这个系数为:
其中,a为到族内其他数据点的平均最距离,b为样本i与其他族样本点距离的平均值的最小值。
平均轮廓系数的取值范围为[-1,1],且簇内样本的距离越近,簇间样本距离越远,平均轮廓系数越大,聚类效果越好。那么,很自然地,平均轮廓系数最大的k便是最佳聚类数。
间隔统计量(Gap Statistic)
这是一个适用与几乎所有的聚类算法。
我们定义,的族内距离为
为族内样本数
证明
则对于聚类个数为 K 时,我们可以定义一个测度量为
即为
事实上我们之前的误差函数,就是从这里推出来的。实际上也是,的标准化。
间隔统计量为:
参考如何找K值