Data Mining 笔记聚类k-means

一、概述

k-means 算法是一种基于划分partitioning methods聚类算法.

二、关于基于划分的算法

定义:给定n个对象或数据元组的数据库D,划分方法构建数据的k个划分(k n),每个划分表示一簇
方法:给定要构建的划分数目k,划分方法创建一个初始划分;然后采用迭代重定位技术,尝试通过对象在组建移动来改进划分.
k-means (MacQueen’67, Lloyd’57/’82): Each cluster is represented by the center of the cluster
k-medoids or PAM (Partition around medoids) (Kaufman & Rousseeuw’87): Each cluster is represented by one of the objects in the cluster

三、k-means?算法思想

?随机选择k个对象,每个对象初始地代表一个类的平均值;对剩余每个对象,根据其到类中心的距离,被划分到最近的类;然后重新计算每个类的平均值。不断重复这个过程,直到所有的样本都不能再分配为止。
输入:k-means-input
均值为:k-means-mean

四、k-means算法描述

输入:期望得到的簇的数目k,n个对象的数据D
输出:k个簇的集合
方法
(1)选择k个对象作为初始的簇的质心
(2)repeat
(3)计算对象与各个簇的质心的距离,将对象划分到距离其最近的簇
(4)重新计算每个新簇的均值
(5)Until簇的质心不再变化
?k-means-demo

五、一个简单的实例

最简单的例子,给下列数据聚类。

?输入:

????????? {2,4,10,12,3,20,30,11,25},k = 2。

则n步骤如下:

m1 m2 K1 K2
2 4 {2,3} {4,10,12,20,30,11,25}
2.5 16 {2,3,4} {10,12,20,30,11,25}
3 18 {2,3,4,10} {10,12,20,30,11,25}
4.75 19.6 {2,3,4,10,11,12} {20,30,25}
7 25 {2,3,4,10,11,12} {20,30,25}

六、关于算法

算法复杂度

? ?算法的计算复杂度为O(nkt)。?? n为数据集中对象的数目,? k为期望得到的簇的数目,? t为迭代的次数

优点

  • 聚类时间快

缺点

  • 用户必须事先指定聚类簇的个数
  • 常常终止于局部最优
  • 只适用于数值属性聚类(计算均值有意义)
  • 对噪声和异常数据也很敏感
  • 不同的初始值,结果可能不同
  • 不适合发现非凸面形状的簇

参考:

View 10ClusBasic.ppt and other presentations by idouba.

完。

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Data Mining 笔记聚类k-means


, ,

No comments yet.

发表评论