聚类[3]–k-means

之前做热点图的时候需要有一个聚类分析的过程,我看这个图默认的是k-means,一直没理解这个到底是个什么东东,今天简单的梳理一下。

聚类分析是数据挖掘及机器学习领域内的重点问题之一,在数据挖掘、模式识别、决策支持、机器学习及图像分割等领域有广泛的应用,是最重要的数据分析方法之一。聚类是在给定的数据集合中寻找同类的数据子集合,每一个子集合形成一个类簇,同类簇中的数据具有更大的相似性。聚类算法大体上可分为基于划分的方法基于层次的方法基于密度的方法基于网格的方法以及基于模型的方法。

一、简介

k-means algorithm算法是一种得到最广泛使用的基于划分的聚类算法,把n个对象分为k个簇,以使簇内具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。它与处理混合正态分布的最大期望算法很相似,因为他们都试图找到数据中自然聚类的中心。

算法首先随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离,将它赋给最近的簇,然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。

它假设对象属性来自于空间向量,并且目标是使各个群组内部的均方误差总和最小。假设有k个群组Si, i=1,2,…,k。μi是群组Si内所有元素xj的重心,或叫中心点。

术语“k-means”最早是由James MacQueen在1967年提出的,这一观点可以追溯到1957年 Hugo Steinhaus所提出的想法。1957年,斯图亚特·劳埃德最先提出这一标准算法,当初是作为一门应用于脉码调制的技术,直到1982年,这一算法才在贝尔实验室被正式提出。1965年, E.W.Forgy发表了一个本质上是相同的方法,1975年和1979年,Hartigan和Wong分别提出了一个更高效的版本。

二、算法描述

输入:簇的数目k;包含n个对象的数据集D。
输出:k个簇的集合。
方法:
从D中任意选择k个对象作为初始簇中心;
repeat;
根据簇中对象的均值,将每个对象指派到最相似的簇;
更新簇均值,即计算每个簇中对象的均值;
计算准则函数;
until准则函数不再发生变化。

三、算法的性能分析

1)优点
(1)k-平均算法是解决聚类问题的一种经典算法,算法简单、快速。
(2)对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。
(3)算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,而簇与簇之间区别明显时,它的聚类效果很好。

2)缺点
(1)k-平均方法只有在簇的平均值被定义的情况下才能使用,不适用于某些应用,如涉及有分类属性的数据不适用。
(2)要求用户必须事先给出要生成的簇的数目k。
(3)对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。
(4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。
(5)对于”噪声”和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。

四、案例实践

  1. scikit-learn的实践 http://qinqianshan.com/unsupervised-learning-cluster/

参考资料
维基百科:http://zh.wikipedia.org/wiki/K平均算法
水逝流年博客: http://blog.csdn.net/xia7139/article/details/9046687

发表评论

电子邮件地址不会被公开。 必填项已用*标注