浅读K-means

百度百科释义为

  K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

  在数据挖掘中,K-Means算法是一种cluster analysis的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。

问题

  K-Means算法主要解决的问题如下图所示。我们可以看到,在图的左边有一些点,用肉眼可以看出来有四个点群,但是我们怎么通过计算机程序找出这几个点群来呢?于是就出现了K-Means算法。

K-Means要解决的问题

工作原理

K-MEANS算法

  输入:聚类个数k,以及包含 n个数据对象的数据库。

  输出:满足方差最小标准的k个聚类

K-Means算法概要

  从上图中,我们可以看到,A,B,C,D,E是五个在图中点。而灰色的点是我们的种子点,也就是我们用来找点群的点。有两个种子点,所以K=2。

  然后,K-Means的算法如下:

  1.随机在图中取K(这里K=2)个种子点。

  2.然后对图中的所有点求到这K个种子点的距离,假如点Pi离种子点Si最近,那么Pi属于Si点群。(上图中,我们可以看到A,B属于上面的种子点,C,D,E属于下面中部的种子点)

  3.接下来,我们要移动种子点到属于他的“点群”的中心。(见图上的第三步)

  4.然后重复第2)和第3)步,直到,种子点没有移动(我们可以看到图中的第四步上面的种子点聚合了A,B,C,下面的种子点聚合了D,E)。

工作过程k-means 算法的工作过程

  说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然 后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

算法优点

K-Means聚类算法的优点主要集中在:

1.算法快速、简单;

2.对大数据集有较高的效率并且是可伸缩性的;

3.时间复杂度近于线性,而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(nkt) ,其中n代表数据集中对象的数量,t代表着算法迭代的次数,k代表着簇的数目。

算法缺点

k-means 算法缺点

① 在 K-means 算法中 K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂,得到较为合理的类型数目 K,例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献中,是根据方差分析理论,应用混合 F统计量来确定最佳分类数,并应用了模糊划分熵来验证最佳分类数的正确性。在文献中,使用了一种结合全协方差矩阵的 RPCL 算法,并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则,来自动决定类的适当数目。它的思想是:对每个输入而言,不仅竞争获胜单元的权值被修正以适应输入值,而且对次胜单元采用惩罚的方法使之远离输入值。

② 在 K-means 算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果,这也成为 K-means算法的一个主要问题。对于该问题的解决,许多算法采用遗传算法(GA),例如文献 中采用遗传算法(GA)进行初始化,以内部聚类准则作为评价指标。

③ 从 K-means 算法框架可以看出,该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进,提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑,通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中,使用的 K-means 算法是对样本数据进行聚类,无论是初始点的选择还是一次迭代完成时对数据的调整,都是建立在随机选取的样本数据的基础之上,这样可以提高算法的收敛速度。

参考博客:http://www.csdn.net/article/2012-07-03/2807073-k-means

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WD学习记录

机器学习 学习笔记(20)深度前馈网络

深度前馈网络(deep feedforward network),也叫做前馈神经网络(feedforward neural network)或者多层感知机(mu...

3613
来自专栏人工智能LeadAI

常见激活函数总结 | 深度学习笔记2

01激活函数概览 基本上,入门深度学习的第一件事情就是了解”神经元”的构造,激活函数算是最基本的一个”部件”了吧.那激活函数到底有什么用呢?为什么需要激活函数?...

4458
来自专栏WD学习记录

机器学习深度学习 笔试面试题目整理(2)

(1) 思想    改变全连接为局部连接,这是由于图片的特殊性造成的(图像的一部分的统计特性与其他部分是一样的),通过局部连接和参数共享大范围的减少参数值。可...

3172
来自专栏AI科技大本营的专栏

笔记 |《深度学习原理与TensorFlow实践》学习笔记(三)

作者 | 王清 目录 图像识别的经典课题 计算机视觉 图像识别课题 卷积神经网络原理 前深度学习时代 卷积操作Convolution 池化Pooling ReL...

3755
来自专栏专知

概率论之概念解析:极大似然估计

【导读】本文是数据科学家Jonny Brooks-Bartlett概率论基础概念系列博客中的“极大似然估计”一章,主要讲解了极大似然估计的若干概念。分别介绍了参...

3437
来自专栏机器学习和数学

[机智的机器在学习] 卷积神经网络入门教程(2)

今天继续回归卷积神经网络的入门教程,主要是介绍全连接网络的训练过程,通俗的讲就是我们入门教程(1)里面讲的是全连接网络长什么样,神经元之间的关系是什么样的,里面...

3654
来自专栏CDA数据分析师

三分钟看懂机器学习中应该注意哪些问题?

本文简单谈谈机器学习中应该注意的一些问题。仅供大家参考学习和讨论。 1. 特征预处理 机器学习中的输入数据必须是数值类型的,但是现实问题中不免会有一些类别类型的...

19210
来自专栏PPV课数据科学社区

机器学习算法基础概念学习总结

1.基础概念 (1) 10折交叉验证:英文名是10-fold cross-validation,用来测试算法的准确性。是常用的测试方法。将数据集分成10份。轮...

3864
来自专栏机器学习原理

机器学习(6)——决策树前言:

前言: 通过第前面的学习介绍了机器学习回归模型创建的流程,并且知道了机器学习要做的事情是找到目标函数,优化它,通过每次迭代都使目标函数值最小,最优解就是目标函数...

50310
来自专栏大数据挖掘DT机器学习

算法工程师的面试难不难,如何准备?-图像处理/CV/ML/DL到HR面总结

把一些相关的知识点总结一下。这个比长,感兴趣的挑自己相关的那部分看。 都是一些基础知识,面相关岗位问到的比较多。 (回答时对算法要有一定的见解,最好不要照书上的...

7645

扫码关注云+社区

领取腾讯云代金券