聚类算法教学文案.ppt

《聚类算法教学文案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、聚类算法什么是聚类聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分离。简单地说，聚类就是把相似的东西分到一组。聚类的现状及应用聚类技术正在蓬勃发展，对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进，而不同的方法适合于不同类型的数据，因此对各种聚类方法、聚类效果的比较成为值得研究的课题。聚类分析是一种重要的人类行为，早在孩提时代，一个人就通过不断改进下意识中

2、的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用，如用于模式识别、数据分析、图像处理、市场研究、客户分割、Web文档分类等。聚类算法选择与分类目前，有大量的聚类算法。而对于具体应用，聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法。几种聚类算法介绍划分聚类算法（K-means聚类算法）层次聚类算法（AGNES、DIANA）密度聚类算法（DBSCAN）K-means聚类

3、算法k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。假设我们提取到原始数据的集合为D(x1,x2,…,xn)，并且每个xi为d维的向量，K-means聚类的目的就是，在给定分类组数k（k≤n）值的条件下，将原始数据分成k类，S= {S1,S2, …,Sk}，在数值模型上，即对以下表达式求最小值：这里μi表示分类Si的平均值。k-means聚类算法计算机实现步骤1、从D中随机取k个元素，作为k个

4、簇的各自的中心。2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。4、将D中全部元素按照新的中心重新聚类。5、重复第4步，直到聚类结果不再变化。6、将结果输出。k-means聚类算法示例对于一个数据集合D，假设K=3，首先3个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色，如下图所示：k-means聚类算法示例然后进入第一次迭代：按照初始的中心点位置为每个数据点着上颜色，重新计算3个中心点，结果如下图所示：k-means聚类算法示例可以看到，由于初

5、始的中心点是随机选的，这样得出来的结果并不是很好，接下来是下一次迭代的结果：k-means聚类算法示例可以看到大致形状已经出来了。再经过两次迭代之后，基本上就收敛了，最终结果如下：k-means聚类算法示例但k-means并不是万能的，虽然许多时候都能收敛到一个比较好的结果，但是也有运气不好的时候会收敛到一个让人不满意的局部最优解，例如选用下面这几个初始中心点：k-means聚类算法示例最终会收敛到这样的结果：k-means聚类算法优缺点优点：1.算法快速、简单。2.对大数据集有较高的效率并且是可伸缩性的。3.时间复杂度近于线性，而且适合挖掘大规模数据集。缺点：1.K-means算法中K是

6、事先给定的，这个K值的选定是非常难以估计，很多时候，事先并不知道数据集应该分成多少个类别才最合适。2.K-means算法中，需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。3.不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。层次聚类当采用划分聚类方法（如k-means）K值选取十分困难时，我们不妨考虑可以考虑层次聚类。层次聚类是另一种主要的聚类方法，它具有一些十分必要的特性使得它成为广泛应用的聚类方法。它生成一系列嵌套的聚类树来完成聚类。

7、单点聚类处在树的最底层，在树的顶层有一个根节点聚类。根节点聚类覆盖了全部的所有数据点。可根据其聚类方式划分为：凝聚（自下而上）聚类和分裂（自上而下）聚类。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。AGNES算法AGNES(AGglomerativeNESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类