《数据聚类》PPT课件.ppt

1、聚类方法,聚类方法概述 划分聚类方法 层次聚类方法 密度聚类方法 其它聚类方法,*,1,什么是聚类,聚类(clustering),指将样本分到不同的组中使得同一组中的样本差异尽可能的小，而不同组中的样本差异尽可能的大。 聚类得到的不同的组称为簇(cluster)。 一个好的聚类方法将产生以下的聚类 最大化类中的相似性 最小化类间的相似性,*,2,2020/9/11,数据仓库与数据挖掘,3,什么是聚类分析？,聚类分析是根据“物以类聚”的道理，对样本或指标进行分类的一种多元统计分析方法，它们讨论的对象是大量的样本，要求能合理地按各自的特性进行合理的分类，没有任何模式可供参考或依循，即在没有先验知识

2、的情况下进行的。,2020/9/11,数据仓库与数据挖掘,4,聚类分析的基本思想,基本思想是认为研究的样本或变量之间存在着程度不同的相似性（亲疏关系）。 根据一批样本的多个观测指标，找出一些能够度量样本或变量之间相似程度的统计量，以这些统计量作为分类的依据，把一些相似程度较大的样本（或指标）聚合为一类，把另外一些相似程度较大的样本（或指标）聚合为一类，直到把所有的样本（或指标）都聚合完毕，形成一个由小到大的分类系统。,2020/9/11,数据仓库与数据挖掘,5,聚类分析无处不在,谁经常光顾商店，谁买什么东西，买多少？ 按会员卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量聚类

3、 这样商店可以 识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购） 刻画不同的客户群的特征,2020/9/11,数据仓库与数据挖掘,8,聚类的应用领域,经济领域： 帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。 谁喜欢打国际长途，在什么时间，打到那里？ 对住宅区进行聚类，确定自动提款机ATM的安放位置 股票市场板块分析，找出最具活力的板块龙头股 企业信用等级分类 生物学领域： 推导植物和动物的分类； 对基因分类，获得对种群的认识 数据挖掘领域 作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究,聚类与分类的

4、差别,聚类与分类最主要的差别是聚类的样本不具有类别标号，而分类的样本具有类别标号。 聚类是无监督学习(unsupervised learning)，而分类是有监督学习(supervised learning)。因此，分类里有训练和测试，而聚类没有训练。 尽管分类是识别对象组类别的有效手段，但需要高昂的代价收集和标记训练样本集。因此，聚类提供了一种新的处理模式：先把数据集划分为组，然后给有限的组指定类别标号。,*,9,对聚类方法的一些要求,可伸缩性 处理不同类型属性的能力 发现任意形状的聚类 用于决定输入参数的领域知识最小化 处理噪声数据和孤立点的能力 对于输入纪录的顺序不敏感 高维性 基于约束

5、的聚类 可解释性和可用性,*,10,聚类分析中的数据类型,数据矩阵 相异度矩阵,*,11,标准度量的聚类描述,欧氏距离 衡量的是多维空间中各个点之间的绝对距离 曼哈顿距离 曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果 明考斯基距离 是对多个距离度量公式的概括性的表述，这里的p值是一个变量，当p=2的时候就得到了上面的欧氏距离。,*,12,聚类分析中的数据类型,向量对象的距离算法 余弦度量实际上计算的是向量x与y之间夹角的余弦值。 余弦度量对于平移与放大是不变的。,*,13,主要聚类方法的分类,聚类方法大致可以分为以下几类： 划分聚类方法 层次聚类方法 密度聚类方法 网格聚

6、类方法 基于模型的方法 其它聚类方法,*,14,主要聚类方法的分类,划分聚类方法 划分方法将给定的数据集划分成k份，每份为一个簇。划分方法通常采用迭代重定位技术，尝试通过对象在簇之间的移动在改进划分。,*,15,主要聚类方法的分类,层次聚类方法 层次聚类方法创建给定数据对象集的层次分解。一般可以分为凝聚法与分裂法。 凝聚法：也称为自底向上的方法，开始将每个对象形成单独的簇，然后逐次合并相近的对象或簇，直到满足终止条件。 分裂法：也称为自顶向下的方法，开始将所有对象放入一个簇中，每次迭代，簇分裂为更小的簇，直到满足终止条件。,*,16,主要聚类方法的分类,密度聚类方法 大部分划分方法基于对象间的

7、距离进行聚类，这样的方法只能发现球形簇，不能发现任意形状的簇。 基于密度的聚类方法的思想是：只要邻域中的密度超过某个阈值，就继续聚类。 基于密度的聚类方法既可以发现任意形状的簇，也可以过滤噪声。,*,17,主要聚类方法的分类,网格聚类方法：把对象空间化为有限的数目单元，形成一个网格结构，所有的聚类操作都在网格结构内进行。它的优点是处理速度快。 基于模型的聚类方法：为每个簇假定一个模型，并寻找数据对给定模型的最佳组合。 其它聚类方法包括：针对高维数据的聚类方法，基于约束条件的聚类方法等等。,*,18,划分聚类算法,给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇

8、。也就是说，它将数据划分为k个簇，而且这k个划分满足下列条件： 每一个簇至少包含一个对象。 每一个对象属于且仅属于一个簇。 对于给定的k，算法首先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改进之后的划分方案都较前一次更好。 k-means算法 PAM算法,*,19,划分聚类算法,一种直接方法就是观察聚类的类内差异(within cluster variation)和类间差异(Between cluster variation)。 类内差异：衡量聚类的紧凑性，类内差异可以用特定的距离函数来定义，例如， 类间差异：衡量不同聚类之间的距离，类间差异定义为聚类中心间的距离，例如

9、， 聚类的总体质量可被定义为w(c)和b(c)的一个单调组合，比如w(c) / b(c) 。,*,20,k-means算法,k-means 算法基本步骤 从 n个数据对象任意选择 k 个对象作为初始聚类中心； 根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； 重新计算每个(有变化)聚类的均值(中心对象)； 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。,*,21,k-means算法,*,22,算法5-1 k-means算法 输入：簇的数目k和包含n个样本的数据库。 输出：k个簇，使平方误差准则

10、最小。 （1)assign initial value for means; /*任意选择k个对象作为初始的簇中心；*/ (2) REPEAT (3) FOR j=1 to n DO assign each xj to the closest centers; (4) FOR i=1 to k DO / *更新簇平均值*/ (5) Compute /*计算准则函数E*/ (6) UNTIL E不再明显地发生变化。,k-means算法,初始化聚类中心(k=3)； 根据每个样本到各个中心的距离，计算k个簇。 使用每个簇的样本，对每个簇生成新的中心。 重复STEP2和STEP3直到终止条件满足。,*

11、,23,划分聚类算法,请使用k-means算法对左边的样本进行分类，其中k=2，初始中心为样本1和样本3。(第一次迭代),*,24,样本数据 序号 属性 1 属性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,划分聚类算法,红色的样本属于一个簇，橙色的样本属于一个簇 计算每个簇新的中心 使用新的中心，重新对每个样本所在的簇进行分配(第二次迭代),*,25,样本数据 序号 属性 1 属性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,划分聚类算法,红色的样本属于一个簇，橙色的样本属于一个簇

12、 计算每个簇新的中心 使用新的中心，重新对每个样本所在的簇进行分配(第三次迭代) 簇的分配情况没有变化，聚类终止,*,26,样本数据 序号 属性 1 属性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,k-means算法例题,*,27,样本数据 序号 属性 1 属性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,根据所给的数据通过对其实施k-means (设n=8，k=2),，其主要执行执行步骤： 第一次迭代：假定随机选择的两个对象，如序号1和序号3当作初始点，分别找到离两点最近的对象，

13、并产生两个簇1，2和3，4，5，6，7，8。 对于产生的簇分别计算平均值，得到平均值点。 对于1，2，平均值点为（1.5，1）（这里的平均值是简单的相加出2）； 对于3，4，5，6，7，8，平均值点为（3.5，3）。 第二次迭代：通过平均值调整对象的所在的簇，重新聚类，即将所有点按离平均值点（1.5，1）、（3.5，1）最近的原则重新分配。得到两个新的簇：1，2，3，4和5，6，7，8。重新计算簇平均值点，得到新的平均值点为（1.5，1.5）和（4.5，3.5）。 第三次迭代：将所有点按离平均值点（1.5，1.5）和（4.5，3.5）最近的原则重新分配，调整对象，簇仍然为1，2，3，4和5，6

14、，7，8，发现没有出现重新分配，而且准则函数收敛，程序结束。,迭代次数平均值平均值产生的新簇新平均值新平均值 （簇1） （簇2） （簇1） （簇2） 1（1，1）（1，2）1，2，3，4，5，6，7，8（1.5，1）（3.5，3） 2（1.5，1）（3.5，3）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5） 3（1.5，1.5）（4.5，3.5）1，2，3，4，5，6，7，8（1.5，1.5）（4.5，3.5）,样本数据 序号 属性 1 属性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,练习,请使用k-means算法对

15、左边的样本进行分类，其中k=3，初始中心为样本1、样本3和样本7。,*,28,样本数据 序号 属性 1 属性 2 1 1 1 2 2 1 3 1 2 4 2 2 5 4 3 6 5 3 7 4 4 8 5 4,k-means算法的性能分析,主要优点： 是解决聚类问题的一种经典算法，简单、快速。 对处理大数据集，该算法是相对可伸缩和高效率的。 当结果簇是密集的，它的效果较好。 主要缺点 在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。 不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于

16、“躁声”和孤立点数据是敏感的。,*,29,k-means算法的几种变异,k -means算法对于孤立点是敏感的。为了解决这个问题，我们引入了k-中心点算法，该算法不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。,*,30,PAM算法,PAM是最早提出的k-中心点算法之一，它选用簇中最中心的对象作为代表对象，试图对n个对象给出k个划分。 代表对象也被称为是中心点，其他对象则被称为非代表对象。 最初随机选择k个对象作为中心点，该算法反复地用非代表对象来代替中心点，试图找出更好的中心点，以改

17、进聚类的质量。,*,31,层次聚类算法,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为： 凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。 分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。 层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。,*,32,AGNES算法,AGNES (AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度有多

18、种不同的计算方法。聚类的合并过程反复进行直到所有的对象最终满足簇数目。,*,33,算法5-3 AGNES（自底向上凝聚算法） 输入：包含n个对象的数据库。 输出：满足终止条件的若干个簇。 (1) 将每个对象当成一个初始簇； (2) REPEAT (3) 计算任意两个簇的距离，并找到最近的两个簇； (4) 合并两个簇，生成新的簇的集合； (5) UNTIL 终止条件得到满足；,AGNES算法,两个簇的距离可以通过以下定义得到 若采用最小距离的定义，簇与簇的合并方式称为单链接方法。,*,34,AGNES算法,假如空间中的五个点A、，各点之间的距离关系如表1所示，其中A,B是一个簇，C，D，E是一个

19、簇。计算这两个簇的最小距离与最大距离。,*,35,AGNES算法,使用AGNES算法对下面的数据集进行聚类。,*,36,AGNES算法,使用AGNES算法对下面 的数据集进行聚类。 l=4 l=3 l=2 l=1 l=0 A B C D E,*,37,AGNES算法,使用AGNES算法对下面 的数据集进行聚类。 l=4 l=3 l=2 l=1 l=0 A B C D E,*,38,AGNES算法,使用AGNES算法对下面 的数据集进行聚类。 l=4 l=3 l=2 l=1 l=0 A B C D E,*,39,AGNES算法,使用AGNES算法对下面 的数据集进行聚类。 l=4 l=3 l=2

20、 l=1 l=0 A B C D E,*,40,AGNES算法,层次聚类方法的终止条件： 设定一个最小距离阈值D，如果最相近的两个簇的距离已经超过D，则它们不需再合并，聚类终止。 限定簇的个数k，当得到的簇的个数已经达到k，则聚类终止。,*,41,AGNES算法性能分析,AGNES算法比较简单，但一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。增加新的样本对结果的影响较大。 假定在开始的时候有n个簇，在结束的时候有1个簇，因此在主循环中有n次迭代，在第i次迭代中，我们必须在n-i+1个簇中找到最靠近的两个聚类。另外算法必须计算所有对象两两之间的距

21、离，因此这个算法的复杂度为 O(n2)，该算法对于n很大的情况是不适用的。,*,42,第五章 聚类方法 内容提要,聚类方法概述 划分聚类方法 层次聚类方法 密度聚类方法 其它聚类方法,*,43,密度聚类算法,密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类球形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。 但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的I/O操作。 代表算

22、法有：DBSCAN、OPTICS、DENCLUE算法等。,*,44,DBSCAN算法,DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。,*,45,DBSCAN算法,定义 5-3 对象的-临域：给定对象在半径内的区域。 定义 5-4 核心对象：如果一个对象的-临域至少包含最小数目MinPts个对象，则称该对象为核心对象。 例如，

23、在下图中，=1cm，MinPts=5，q是一个核心对象。,*,46,DBSCAN算法,定义 5-5 直接密度可达：给定一个对象集合D，如果p是在q的-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。 例如，在下图中，=1cm，MinPts=5，q是一个核心对象，对象p从对象q出发是直接密度可达的。,*,47,DBSCAN算法,定义 5-6 密度可达的：如果存在一个对象链p1，p2，pn，p1=q，pn=p，对piD，（1=i=n），pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。 例如，在下图中，=1cm，MinPts=5，q是一个核心对象，p1是从q关于和MitPts直接密度可达，p是从p1关于和MitPts直接密度可达，则对象p从对象q关于和MinPts密度可达的。,*,48,DBSCAN算法,定义 5-7密度相连的：如果对象集合D中存在一个对象o，使得对象p和q是从o关于和MinP