数据挖掘--K-means

K-Means方法是MacQueen1967年提出的。给定一个数据集合X和一个整数K(?n),K-Means方法是将X分成K个聚类并使得在每个聚类中所有值与该聚类中心距离的总和最小。

K-Means聚类方法分为以下几步:

[1] 给K个cluster选择最初的中心点,称为K个Means。

[2] 计算每个对象和每个中心点之间的距离。

[3] 把每个对象分配给距它最近的中心点做属的cluster。

[4] 重新计算每个cluster的中心点。

[5] 重复2,3,4步,直到算法收敛。

以下几张图动态展示了这几个步骤:

数据挖掘--K-means

数据挖掘--K-means

数据挖掘--K-means

数据挖掘--K-means

数据挖掘--K-means

数据挖掘--K-means

 数据挖掘--K-means

 下面,我们以一个具体的例子来说明一下K-means算法的实现。

数据挖掘--K-means

 数据挖掘--K-means

 数据挖掘--K-means

 数据挖掘--K-means

K-means算法的优缺点:

优点:

(1)对于处理大数据量具有可扩充性和高效率。算法的复杂度是O(tkn),其中n是对象的个数,k是cluster的个数,t是循环的次数,通常k,t<<n。

(2)可以实现局部最优化,如果要找全局最优,可以用退火算法或者遗传算法

缺点:

(1)Cluster的个数必须事先确定,在有些应用中,事先并不知道cluster的个数。

(2)K个中心点必须事先预定,而对于有些字符属性,很难确定中心点。

(3)不能处理噪音数据。

(4)不能处理有些分布的数据(例如凹形)

K-Means方法的变种

(1) K-Modes :处理分类属性

(2) K-Prototypes:处理分类和数值属性

(3) K-Medoids

它们与K-Means方法的主要区别在于:

(1)最初的K个中心点的选择不同。

(2)距离的计算方式不同。

(3)计算cluster的中心点的策略不同。

相关推荐