龙空技术网

K-means算法笔记

爱生活的程序旺 96

前言:

目前各位老铁们对“二值图像质心算法”都比较重视,看官们都想要分析一些“二值图像质心算法”的相关内容。那么小编同时在网摘上搜集了一些有关“二值图像质心算法””的相关内容,希望你们能喜欢,兄弟们一起来学习一下吧!

简介

K-means算法又叫K-均值算法,是非监督学习中的聚类算法。

基本思想

在K-means算法中,用cluster来表示簇,K-means算法收敛等同于所有质心不再发生变化。基本的k-means算法流程如下:

选取k个初始质心(作为初始cluster,每个初始cluster只包含一个点);repeat: 对每个样本点,计算得到距离其最近的质心,将其类别标为该质心所对应的cluster; 重新计算k个cluster对应的质心(质心是cluster中样本点的均值);util 质心不再发生变化 或 到达最大迭代次数

K-means的本质是移动中心点,使其逐渐靠近数据“中心”,即最小化目标函数,目标函数为每个点到其簇质心的距离平方和:

目标函数

其中,N是元素个数,x表示元素,c(j)表示第j簇的质心。

优缺点

优点

简单、快速;对大数据集有较高的效率并且是可伸缩性的;时间复杂度接近于线性,适合挖掘大规模数据集。

缺点

只是局部最优,因而对初始质心的选取很敏感;选择能达到目标函数最优的K值是非常困难的。Python实现

首先,我们需要编写几个辅助函数:

加载测试数据集

加载测试数据集

计算欧拉距离(这里选取欧拉距离作为距离计算公式)

计算欧拉距离

初始化k个随机簇心

初始化k个随机簇心

有了以上辅助函数后,我们就可以根据K-means的基本思想与算法步骤实现K-means算法了。

K-means核心算法

至此,K-means算法的Python实现就已经完成了。我们可以加载一组测试数据,指定簇心个数,使用K-means算法进行聚类。

随机初始化

由于初始化的中心点对于最后的分类结果影响很大,因而很容易出现:当初始化的中心点不同时,其结果可能千差万别。因此为了分类结果更加合理,我们可以多次初始化中心点,即多次运行K-means算法,然后取Cost最小的分类结果。

二分K-means

为了克服K-means算法收敛域局部最小值的问题(对初始簇心的位置敏感),二分K-means出现了。该算法首先将所有点归于一个簇,然后将其一分为二。之后选择其中一个簇继续一分为二。选择的依据就是:该簇的划分是否可以最大程度降低SSE(误差平方和)的值。上述基于SSE的划分过程不断重复,直至簇数达到k为止。

将所有点看成一个簇当簇数目小于k时: 对于每一个簇: 计算总误差 在给定的簇上面进行K-means聚类(k=2) 计算将该簇一分为二之后的总误差 选择使得误差最小的那个簇进行划分操作
K的选择Elbow method

假设随着K的增大,cost function j的大小呈现以下形状:

cost function j

可以看到,当K=3时,J已经很小了,再增大K并不能大大减小J。说明此时K=3比较合适。

但是,以上情况并不常见,更一般的情况是:

更一般的cost function j

此时根本看不出哪里才是”手肘“,所以对此只能实践调研,按实际需求而定。

标签: #二值图像质心算法 #二值图像质心算法是什么 #kshingle算法