您当前的位置:悬赏问答

2017-11-12 08:46

作业五:什么是K-means算法? 10

如题,什么是K-means算法?是谁提出的,有什么应用?

提问者采纳

2017-11-12 08:46

Wikipedia: https://en.wikipedia.org/wiki/K-means_clustering

K-平均算法源于信号处理中的一种向量量化方法,现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是:把 n个点(可以是样本的一次观察或一个实例)划分到k个聚类中,使得每个点都属于离他最近的均值(此即聚类中心)对应的聚类,以之作为聚类的标准。

已知观测集 (x1,x2,...,xn),其中每个观测都是一个 d-维实向量,k-平均聚类要把这 n个观测划分到k个集合中(k≤n),使得组内平方和(WCSS within-cluster sum of squares)最小。换句话说,它的目标是找到使得下式满足的聚类Si

提出

虽然其思想能够追溯到1957年的Hugo Steinhaus ,术语“k-均值”于1967年才被James MacQueen首次使用。标准算法则是在1957年被Stuart Lloyd作为一种脉冲码调制的技术所提出,但直到1982年才被贝尔实验室公开出版。在1965年,E.W.Forgy发表了本质上相同的方法,所以这一算法有时被称为Lloyd-Forgy方法。更高效的版本则被Hartigan and Wong提出(1975/1979)。

应用:

k-均值聚类(尤其是使用如Lloyd's算法的启发式方法的聚类)即使是在巨大的数据集上也非常容易部署实施。正因为如此,它在很多领域都得到的成功的应用,如市场划分、机器视觉、 地质统计学、天文学和农业等。它经常作为其他算法的预处理步骤,比如要找到一个初始设置。

1.向量的量化

k-均值起源于信号处理领域,并且现在也能在这一领域找到应用。例如在计算机图形学中,色彩量化的任务,就是要把一张图像的色彩范围减少到一个固定的数目k上来。k-均值算法就能很容易地被用来处理这一任务,并得到不错的结果。其它得向量量化的例子有非随机抽样,在这里,为了进一步的分析,使用k-均值算法能很容易的从大规模数据集中选出k个合适的不同观测。

2.聚类分析

在聚类分析中,k-均值算法被用来将输入数据划分到k个部分(聚类)中。 然而,纯粹的k-均值算法并不是非常灵活,同样地,在使用上有一定局限(不过上面说到得向量量化,确实是一个理想的应用场景)。特别是,当没有额外的限制条件时,参数k是很难选择的(真如上面讨论过的一样)。算法的另一个限制就是它不能和任意的距离函数一起使用、不能处理非数值数据。而正是为了满足这些使用条件,许多其他的算法才被发展起来。

3.特征学习

在(半)监督学习或无监督学习中,k-均值聚类被用来进行特征学习(或字典学习)步骤。基本方法是,首先使用输入数据训练出一个k-均值聚类表示,然后把任意的输入数据投射到这一新的特征空间。 k-均值的这一应用能成功地与自然语言处理和计算机视觉中半监督学习的简单线性分类器结合起来。在对象识别任务中,它能展现出与其他复杂特征学习方法(如自动编码器、受限Boltzmann机等)相当的效果。然而,相比复杂方法,它需要更多的数据来达到相同的效果,因为每个数据点都只贡献了一个特征(而不是多重特征)。

 

算法详解:在wiki上并没有很明白的了解算法的原理,但经过自己在网上的寻找更好的理解了k-means算法,网址:http://coolshell.cn/articles/7779.html

在数据挖掘中, K-Means 算法是一种聚类分析的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。K-Means算法主要解决的问题如下图所示。我们可以看到,在图的左边有一些点,我们用肉眼可以看出来有四个点群,但是我们怎么通过计算机程序找出这几个点群来呢?于是就出现了我们的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 demo,用火狐浏览器可以实验K-means算法,感觉有时间可以去了解一下怎么做这种小程序

http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html

如上图,即为对1000个数据分成3个聚类,用的Euclidean算法,运行了8步。

其他 0 条回答




登录 后查看个人信息