K-means算法的优化目标和初始化要点

原创 2018-07-08 23:23 阅读(231)次

K-means算法的优化目标

K-means算法的原来我在上一篇 K-means算法原理 提到了。但具体实现还有几个要点需要注意。

K-means算法的结果很依赖于一开始初始化类别点,不同初始化点会得到不同的聚类结果,但全局最优解往往只有一个,其他的结果只能是局部最优解。

如何分辨全局最优解还是局部最优解?

这就需要一个判定的方法。这和分类,回归问题一样(最小化代价函数),需要找到K-means算法的最优化目标。

运行K-means算法中有两组重要的变量将会随着算法运行而不断改变,第1个就是每个数据点在每轮循环的时候所属于的类别,也就是每个类别暂时包含的数据点集合。第2个即是每轮循环不断变化的类别点的位置(坐标,也可以理解成一组多维空间的向量)。

把这两组变量作为参数,写成 

其中m是数据点的总数,K是类别总数。

最小化J函数,就是K-means的优化目标。我们也称J函数为失真代价函数,distortion cost function。表示的是K-means算法的失真度。

 正式K-means算法中数据点和类别点的距离的平方。

可以看出K-means运行过程中正式一直在最小化J函数。簇分配过程就是固定μ集合,变化c集合数据来最小化J函数的过程,而移动聚类中心过程,则是固定了c集合,变化μ集合的过程,同样也是在最小化J函数。

J函数可以用来证明K-means算法在收敛,同时可以用来判断不同的聚类结果哪个更好,排除局部最优解。只要把不同次的收敛后的聚类结果带入J函数,对比J函数的结果,J函数更大的一次聚类结果就是局部最优解。找出失真代价函数J最小的那次则很可能就是全局最优解,起码是当前局部最优解。

这次提到了不同次,正是因为K-means聚类结果是取决于初始化的,不同的初始化就可能出现局部最优解。要计算出全局最优解,就需要多次进行K-means算法。一般分别运行50-1000次,而每次只在随机初始化类别点不同,算法方向是一致的。

K-means的初始化

K-means的初始化也是有讲究的,盲目的随机初始化类别点,可能会出现在上文 K-means算法原理 提到的可能出现类别点在一开始没有包含任何一个数据点的情况出现。为了避免这种情况发生,推荐的是用随机数据点作为类别点,这样最少也能包含一个数据点。

另外需要聚类的类别总数K应该要小于数据点m,否则聚类结果失去意义。

K值太大,多次用不同的随机初始化类别点的方式对于得到全局最优解帮助不大。但当K值在2-10之间的时候,多次随机的方式还是能提升聚类结果的。

本文完。

本站作品的版权皆为作品作者所有。

本站文字和内容为本站编辑或翻译,部分内容属本站原创,所以转载前务必通知本站并以超链接形式注明内容来自本站,否则以免带来不必要的麻烦。

本站内容欢迎分享,但拒绝有商业目的的转载!


上一篇:K-means算法原理
下一篇:Jib初识