数据挖掘Chapter9

1、9.5 可伸缩的聚类算法可伸缩的聚类算法BIRCHnBIRCH(Balanced Iterative Reducing and Clustering using Hierarchies): 利用层次方法的平衡迭代归约和聚类利用层次方法的平衡迭代归约和聚类n由由Zhang, Ramakrishnan和和Livny 提出提出(SIGMOD96)n两个重要概念两个重要概念n聚类特征聚类特征(Clustering Feature, CF)n聚类特征树聚类特征树(Clustering Feature Tree, CF树树)n聚类特征聚类特征n聚类特征聚类特征(CF)是一个三元组，给出对象子类的信息的汇总

2、描述是一个三元组，给出对象子类的信息的汇总描述 n设某个子类中有设某个子类中有N个个d维的点或对象维的点或对象oi，则该子类的，则该子类的CF定义如下定义如下 CF=其中其中, N是子类中的点数是子类中的点数(0阶矩阶矩); 是是N个数据点的线性和个数据点的线性和(1阶矩阶矩); 是是N个数据点的平方和个数据点的平方和(2阶矩阶矩)Nii1O OL LS SNii12O OSSSS2022-3-7数据挖掘导论2聚类特征聚类特征nClustering Feature: CF = nN: 数据点数目数据点数目nLS: Ni=1XinSS: Ni=1Xi2CF = (3,4)(2,6)(4,5)(4

3、,7)(3,8)2022-3-7数据挖掘导论3BIRCH的的CF树树n聚类特征聚类特征 n从统计学的观点来看，聚类特征是对给定子类统计汇总从统计学的观点来看，聚类特征是对给定子类统计汇总: 子类的子类的0阶、阶、1阶和阶和 2阶矩阶矩( moments ) n记录了计算聚类的关键度量记录了计算聚类的关键度量, 并有效地利用了存储并有效地利用了存储, 因为它汇总了关因为它汇总了关于子类的信息，而不是存储所有的对象于子类的信息，而不是存储所有的对象 CF 树是高度平衡的树树是高度平衡的树, 它存储了层次聚类的聚类特征它存储了层次聚类的聚类特征 n树中的非叶节点有后代或树中的非叶节点有后代或“孩子孩

4、子” n非叶节点存储了其孩子的非叶节点存储了其孩子的CF的总和的总和, 即汇总了关于其孩子的聚类信即汇总了关于其孩子的聚类信息息 nCF树有两个参数树有两个参数 -影响影响CF树的大小树的大小n分支因子分支因子B: 定义非树叶节点的孩子的最大个数定义非树叶节点的孩子的最大个数阈值阈值T: 给出了存储在树的叶子节点中的子类的最大直径给出了存储在树的叶子节点中的子类的最大直径 2022-3-7数据挖掘导论4BIRCH ( (续续) )nBIRCH增量地构造一棵增量地构造一棵 CF 树树(Clustering Feature Tree) , CF树是一个层树是一个层次数据结构次数据结构, 用于多阶段

5、聚类用于多阶段聚类n阶段阶段 1: 扫描扫描 DB , 建立一棵初始的存放在内存的建立一棵初始的存放在内存的 CF树树(数据的多层数据的多层压缩压缩, 试图保留数据内在的聚类结构试图保留数据内在的聚类结构 )n阶段阶段 2: 使用某种聚类算法对使用某种聚类算法对CF树的叶节点进行聚类树的叶节点进行聚类. n在阶段一在阶段一, 随着对象被插入随着对象被插入, CF树被动态地构造树被动态地构造. n一个对象被插入到最近的叶子条目一个对象被插入到最近的叶子条目(子聚类子聚类). n如果在插入后存储在叶子节点中的子类的直径大于阀值如果在插入后存储在叶子节点中的子类的直径大于阀值, 那么该那么该叶子节点

6、叶子节点(可能还有其他节点可能还有其他节点)被分裂被分裂. n新对象插入后新对象插入后. 关于该对象的信息向着树根传递关于该对象的信息向着树根传递-类似于类似于B+树树构建中的插入和节点分裂构建中的插入和节点分裂 n通过修改阀值通过修改阀值, CF树的大小可以改变树的大小可以改变2022-3-7数据挖掘导论5BIRCH ( (续续) )n重建过程从旧树的叶子节点建造一个新树重建过程从旧树的叶子节点建造一个新树. 这样这样, 重建树的过程不需重建树的过程不需要重读所有的对象要重读所有的对象 -建树只需读一次数据建树只需读一次数据 n在阶段二被采用任何聚类算法在阶段二被采用任何聚类算法, 例如典型

7、的划分方法例如典型的划分方法nBIRCH的性能的性能n支持增量聚类支持增量聚类n线性可伸缩性线性可伸缩性: 计算复杂性计算复杂性O(n), 单遍扫描单遍扫描, 附加的扫描可以改善聚类附加的扫描可以改善聚类质量质量n较好的聚类质量较好的聚类质量n缺点缺点n只能处理数值数据只能处理数值数据nCF树节点不是用户所认为的自然簇树节点不是用户所认为的自然簇, 当簇不是球形的时当簇不是球形的时, BIRCH不不能很好地聚类能很好地聚类n对数据的输入次序敏感对数据的输入次序敏感2022-3-7数据挖掘导论6CURE: 基本思想基本思想nCURE（Clustering Using REpresentative

8、） n使用簇中的多个代表点来表示一个簇使用簇中的多个代表点来表示一个簇n这些点捕获了簇的几何形状这些点捕获了簇的几何形状n代表点相对分散代表点相对分散: 第一个代表点选择离簇中心最远的点第一个代表点选择离簇中心最远的点, 而其余而其余的点选择离所有已经选取的点最远的点的点选择离所有已经选取的点最远的点n代表点的个数是一个参数代表点的个数是一个参数, 业已发现业已发现10或更大的值效果很好或更大的值效果很好 n一旦选定代表点，它们就以因子一旦选定代表点，它们就以因子 向簇中心收缩向簇中心收缩 n例如例如, 对于对于 = 0.7, 一个到中心的距离为一个到中心的距离为10个单位的代表点将移动个单位

9、的代表点将移动3个单位个单位n使用一种凝聚层次聚类方案进行实际的聚类使用一种凝聚层次聚类方案进行实际的聚类n两个簇之间的距离是任意两个代表点（在它们向它们代表的中两个簇之间的距离是任意两个代表点（在它们向它们代表的中心收缩之后）之间的最短距离心收缩之后）之间的最短距离 n = 0, 等价于基于质心的层次聚类等价于基于质心的层次聚类n = 1, 与单链层次聚类大致相同与单链层次聚类大致相同 2022-3-7数据挖掘导论7CURE: 基本思想基本思想n在聚类过程的两个不同阶段删除离群点在聚类过程的两个不同阶段删除离群点 n第一个阶段一般出现在簇的个数是原来点数的第一个阶段一般出现在簇的个数是原来点

10、数的1/3时删除增长缓时删除增长缓慢的簇慢的簇 n如果一个簇增长缓慢如果一个簇增长缓慢, 则意味它主要由离群点组成则意味它主要由离群点组成 n第二个离群点删除阶段出现在簇的个数达到第二个离群点删除阶段出现在簇的个数达到K（期望的簇个数）（期望的簇个数）的量级时的量级时. 此时此时, 小簇又被删除小簇又被删除 nCURE使用了两种技术来加快聚类过程使用了两种技术来加快聚类过程n第一种技术第一种技术: 取随机样本取随机样本, 并在抽样的数据点上进行层次聚类并在抽样的数据点上进行层次聚类, 随随后是最终扫描后是最终扫描, 将数据集中剩余的点指派到簇中将数据集中剩余的点指派到簇中n第二种技术第二种技术

11、: 划分样本数据划分样本数据, 然后聚类每个划分中的点然后聚类每个划分中的点 2022-3-7数据挖掘导论8CURE: 算法算法mqmpqmqK是期望的簇个数，是期望的簇个数，m是点的个数，是点的个数，p是划分的个数，而是划分的个数，而q是一个划分是一个划分中的点的期望压缩中的点的期望压缩2022-3-7数据挖掘导论9CURE: 细节细节nCURE的抽样的抽样 定理定理9.1 设设0 f 1, m是对象的个数是对象的个数, 簇簇Ci的大小为的大小为mi. 如果样本的大如果样本的大小小s满足满足则我们将以概率则我们将以概率1 （0 1）从簇）从簇Ci得到至少得到至少f mi个对象个对象n例：假定

12、有例：假定有100 000个对象个对象, n如果簇如果簇Ci的大小是的大小是1 000, 我们的目标是以我们的目标是以80%的可能性得到的可能性得到10%的的Ci簇对象簇对象n此时此时, f = 0.1, = 0.2, m = 100 000, 这样这样s = 11962n如果簇如果簇Ci有有50个对象个对象, 目标是得到目标是得到5%的的Ci簇对象簇对象, 则大小为则大小为6440的样的样本就足够了本就足够了 2111loglog2logiiimmsfmfmmm2022-3-7数据挖掘导论109.6 使用哪种聚类算法使用哪种聚类算法 聚类的类型聚类的类型 n应用对聚类类型的要求应用对聚类类型

13、的要求n创建生物学分类法，层次是首选的创建生物学分类法，层次是首选的 n旨在汇总的聚类，划分聚类是常用的旨在汇总的聚类，划分聚类是常用的 n应用是否要求聚类所有对象应用是否要求聚类所有对象n浏览文档需要聚类大部分文档浏览文档需要聚类大部分文档n找出文档主题希望产生凝聚的簇（可能许多文档未包含在内）找出文档主题希望产生凝聚的簇（可能许多文档未包含在内）n精确聚类精确聚类vs模糊聚类模糊聚类n概率和模糊方案提供了指明对象在各簇的概率或隶属度概率和模糊方案提供了指明对象在各簇的概率或隶属度 n基于密度的聚类具有核心点概念基于密度的聚类具有核心点概念 n划分聚类有中心点划分聚类有中心点2022-3-7数据挖掘导论12簇的类型簇的类型 n簇的类型是否与应用匹配簇的类型是否与应用匹配 n三种类型三种类型n基于原型的、基于图的和基于密度的基于原型的、基于图的和基于密度的 n基于原型的聚类方案以及某些基于图的聚类方案（全链、质心和基于原型的聚类方案以及