聚类算法--以K-means算法为例.ppt
《聚类算法--以K-means算法为例.ppt》由会员分享,可在线阅读,更多相关《聚类算法--以K-means算法为例.ppt(16页珍藏版)》请在三一文库上搜索。
1、聚类算法聚类算法 - -以以K-meansK-means算法为例算法为例 安英博 2013.12.26 分类是指将数据归于一系列已知类别之中的某个 类的分类过程。分类作为一种监督学习方法,要 求必须事先明确知道各个类别的信息,并且断言 所有待分类项都有一个类别与之对应。但是很多 时候上述条件得不到满足,尤其是在处理海量数 据的时候。 聚类是根据客体属性对一系列未分类的客体进行 类别的识别,把一组个体按照相似性归成若干 类。聚类属于无监督学习。 分类和聚类 在商业上,聚类可以帮助市场分析人员从消费者数据 库中区分出不同的消费群体来,并且概括出每一类消 费者的消费习惯。它作为数据挖掘中的一个模块,
2、可 以作为一个单独的工具来发现数据库中分布的一些深 层的信息,并且概括出每一类的特点,或者把注意力 放在某一个特定的类上做进一步的分析。 聚类分析的算法可以分为划分法、层次法、基于密度 的方法、基于网格的方法、基于模型的方法。其中, 最广泛使用的聚类算法k-means算法属于划分法。 聚类算法 给定一个有N个元组或者纪录的数据集,划分法将构造K 个分组,每一个分组就代表一个聚类,KN。而且这K个分 组满足下列条件: (1) 每一个分组至少包含一个数据纪录; (2)每一个数据纪录属于且仅属于一个分组(某些模糊 聚类算法中该条件可以放宽); 对于给定的K,算法首先给出一个初始的分组方法,以后 通过
3、反复迭代的方法改变分组,使得每一次改进之后的分组 方案都较前一次好,而所谓好的标准就是:同一分组中的记 录越近越好,而不同分组中的纪录越远越好。 划分法 k-means算法,也被称为k-均值或k-平均。 该算法首先随机地选择k个对象作为初始的k个簇的质心 ;然后对剩余的每个对象,根据其与各个质心的距离,将它 赋给最近的簇,然后重新计算每个簇的质心;这个过程不断 重复,直到准则函数收敛。通常采用的准则函数为平方误差 和准则函数,即 SSE(sum of the squared error),其定义如 下: SSE是数据库中所有对象的平方误差总和,p为数据对象 ,mi是簇Ci的平均值。这个准则函数
4、使生成的结果尽可能的 紧凑和独立。 k-means算法 下面给出k-means算法的具体步骤: (l) 给定大小为n的数据集,令I=1,选取k个初始聚类中心 Zj(I),j=1,2,3,k; (2) 计算每个数据对象与聚类中心的距离D(xi,Zj(I),i=1, 2,3n,j=l,2,3,k,如果满足 D(xi,Zk(I) =minD(xi,Zj(I),i=l,2,3,n 则 xiC k; (3) 计算k个新的聚类中心: 即取聚类中所有元素各自维度的算术平均数; (4) 判断:若Zj(I+1)Zj(I),j=l,2,3,k,则I=I+1, 返回(2);否则算法结束。 k-means算法描述 距
5、离D的计算方法 1. 欧几里得距离: 其意义就是两个元素在欧氏空间中的集合距离,因为 其直观易懂且可解释性强,被广泛用于标识两个标量元 素的相异度。 2. 曼哈顿距离: 3. 闵可夫斯基距离: k-means算法描述 K-Means 的算法如下: 随机在图中取k(这里k=2)个种子点。 对图中的所有点求到这k个种子点的距离,假如点 Pi 离种子点 Si 最近,那么 Pi 属于 Si 点群。(上图中,我们可以看到A、B属于 上面的种子点,C、D、E属于下面中部的种子点) 移动种子点到属于他的“点群”的中心。(见图上的第三步) 然后重复第2)和第3)步,直到种子点不再移动(图中的第四步上 面的种子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 means
链接地址:https://www.31doc.com/p-2572575.html