数据挖掘挖掘频繁模式关联和相关课件

1、2022/8/7数据挖掘：概念和技术1第5章：挖掘频繁模式、关联和相关5.1 基本概念和路线图5.2 有效的和可伸缩的频繁项集挖掘方法5.3 挖掘各种类型的关联规则5.4 由关联挖掘到相关性分析5.5 基于约束的关联挖掘5.6 小结2022/8/7数据挖掘：概念和技术2什么是关联挖掘?关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用：购物篮分析、交叉销售、产品目录设计、赔本销售分析（loss-leader analysis）、聚集、分类等。举例： 规则形式： “Body Head support, confidenc

2、e”.buys(x, “diapers”) buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%2022/8/7数据挖掘：概念和技术3关联规则：基本概念给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品)查找: 所有描述一个项目集合与其他项目集合相关性的规则E.g., 98% of people who purchase tires and auto accessories also get automotive services done应用* 护理用

3、品 (商店应该怎样提高护理用品的销售？)家用电器 * (其他商品的库存有什么影响?)在产品直销中使用附加邮寄2022/8/7数据挖掘：概念和技术4规则度量：支持度与可信度查找所有的规则 X & Y Z 具有最小支持度和可信度支持度, s, 一次交易中包含X 、 Y 、 Z的可能性置信度, c, 包含X 、 Y的交易中也包含Z的条件概率设最小支持度为50%, 最小可信度为 50%, 则可得到A C (50%, 66.6%)C A (50%, 100%)买尿布的客户二者都买的客户买啤酒的客户2022/8/7数据挖掘：概念和技术5关联规则挖掘：路线图布尔 vs. 定量 关联 (基于规则中所处理数据的

4、值类型)buys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60%age(x, “30.39”) income(x, “42.48K”) buys(x, “PC”) 1%, 75%单维 vs. 多维 关联 (基于规则中涉及的数据维)(例子同上)单层 vs. 多层 分析(基于规则集所涉及的抽象层)那个品种牌子的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合项集2022/8/7数据挖掘：概念和技术6第6章：从大数据库中挖掘关联规则6.1 关联规则挖掘6.2由事务数据库挖掘单维

5、布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关性分析6.6基于约束的关联挖掘6.7小结2022/8/7数据挖掘：概念和技术7关联规则挖掘一个例子对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的最小值尺度 50%最小可信度 50%2022/8/7数据挖掘：概念和技术8关键步骤：挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如, 如果AB

6、 是频繁集，则 A B 也一定是频繁集从1到k（k-频繁集）递归查找频繁集用得到的频繁集生成关联规则2022/8/7数据挖掘：概念和技术9Apriori算法连接: 用 Lk-1自连接得到候选k-项集Ck修剪: 一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 2; Lk-1 !=; k+) do begin Ck = candidates generated from

7、Lk-1; for each transaction t in database do increment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support endreturn k Lk;2022/8/7数据挖掘：概念和技术10Apriori算法 例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 D2022/8/7数据挖掘：概念和技术11如何生成候选集假定 Lk-1 中的项按顺序排列第一步: 自连接 Lk-1 insert into Ck

8、select p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1第二步: 修剪For all itemsets c in Ck doFor all (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2022/8/7数据挖掘：概念和技术12计算支持度为什么会成为一个问题？候选集的个数非常巨大 一笔交易可能包含多个候选集2

9、022/8/7数据挖掘：概念和技术13生成候选集的例子L3=abc, abd, acd, ace, bcd自连接 : L3*L3abc 和 abd 得到 abcd acd 和 ace 得到 acde修剪:ade 不在 L3中，删除 acdeC4=abcd2022/8/7数据挖掘：概念和技术14提高Apriori效率的方法1.基于Hash的项集计数: 若 k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。(157页图6-6)2.减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集，下一步计算时删除这些记录。3.划分: 一个项集要想在整个数据

10、库中是频繁的，那么他至少在数据库的一个分割上是频繁的。 两次扫描数据。(157页图6-7)4.抽样: 使用小的支持度+完整性验证方法。在小的抽样集上找到局部频繁项集，然后在全部数据集找频繁项集。5.动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。2022/8/7数据挖掘：概念和技术15Apriori 够快了吗? 性能瓶颈Apriori算法的核心:用频繁的(k 1)-项集生成候选的频繁 k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori 的瓶颈: 候选集生成巨大的候选集:104 个频繁1-项集要生成 107 个候选 2-项集要找尺寸为100的频繁模式

11、，如 a1, a2, , a100, 你必须先产生2100 1030 个候选集多次扫描数据库： 如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描2022/8/7数据挖掘：概念和技术16挖掘频繁集 不用生成候选集频繁模式增长 (FP-增长)用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘又完备的避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则: 分别挖掘条件数据库2022/8/7数据挖掘：概念和技术17用 FP-tree挖掘频繁集基本

12、思想 (分而治之)用FP-tree地归增长频繁集方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的相集都是频繁集)2022/8/7数据挖掘：概念和技术18挖掘 FP-tree的主要步骤为FP-tree中的每个节点生成条件模式库用条件模式库构造对应的条件FP-tree递归构造条件 FP-trees 同时增长其包含的频繁集如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。2022/8/7数据挖掘：概念和技术19步骤1: 建立 FP-tree

13、 （159页图6-8）从FP-tree的头表开始按照每个频繁项的连接遍历 FP-tree列出能够到达此项的所有前缀路径，得到条件模式库步骤2:建立条件FP-tree进行挖掘（159页图6-9）对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-tree2022/8/7数据挖掘：概念和技术20为什么 频繁集增长 速度快？性能研究显示FP-growth 比Apriori快一个数量级, 同样也比 tree-projection 快。原因不生成候选集，不用候选测试。使用紧缩的数据结构避免重复数据库扫描基本操作是计数和建立 FP-tree 树2022/8/7数据挖掘：概念和技术21FP-gro

14、wth vs. Apriori: 相对于支持度的扩展性Data set T25I20D10K2022/8/7数据挖掘：概念和技术22FP-growth vs. Tree-Projection:相对于支持度的扩展性Data set T25I20D100K2022/8/7数据挖掘：概念和技术23关联规则结果显示 (Table Form )2022/8/7数据挖掘：概念和技术24关联规则可视化Using Plane Graph2022/8/7数据挖掘：概念和技术25关联规则可视化Using Rule Graph2022/8/7数据挖掘：概念和技术26第6章：从大数据库中挖掘关联规则6.1 关联规则挖

15、掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关性分析6.6基于约束的关联挖掘6.7小结2022/8/7数据挖掘：概念和技术27多层关联规则项通常具有层次底层的项通常支持度也低某些特定层的规则可能更有意义交易数据库可以按照维或层编码可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄2022/8/7数据挖掘：概念和技术28挖掘多层关联规则自上而下，深度优先的方法：先找高层的“强”规则：牛奶 面包 20%, 60%.再找他们底层的“弱”规则：酸奶 黄面包 6%, 50%.多层关联规则的变种1 支持度不

16、变: 在各层之间使用统一的支持度（164页图6-12）+ 一个最小支持度阈值. 如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。 底层项不会成为频繁集，如果支持度太高 丢失底层关联规则太低 生成太多的高层关联规则2 支持度递减: 随着层次的降低支持度递减（164页图6-13）2022/8/7数据挖掘：概念和技术29多层关联规则: 支持度不变 vs. 支持度递减3层次交叉单项过滤： （165页图6-14）4层次交叉K-项过滤： （165页图6-15）4种搜索策略：层与层独立用k-项集跨层过滤用项跨层过滤用项进行可控跨层过滤2022/8/7数据挖掘：概念和技术30支持度不变支

17、持度不变多层挖掘牛奶support = 10%酸奶 support = 6%脱脂奶support = 4%层 1min_sup = 5%层 2min_sup = 5%2022/8/7数据挖掘：概念和技术31支持度递减支持度递减多层挖掘酸奶 support = 6%脱脂奶 support = 4%层 1min_sup = 5%层 2min_sup = 3%牛奶support = 10%2022/8/7数据挖掘：概念和技术32多层关联：冗余过滤由于“祖先”关系的原因，有些规则可能是多余的。例子奶制品 白面包 support = 8%, confidence = 70%酸奶 白面包 support

18、= 2%, confidence = 72%酸奶占奶制品25%我们称第一个规则是第二个规则的祖先参考规则的祖先，如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余的。2022/8/7数据挖掘：概念和技术33数据挖掘查询的逐步精化为什么要逐步精化挖掘操作的代价可能高或低，结果可能过细致或粗糙在速度和质量之间折衷：逐步精化超集覆盖特征：预存储所有正面答案允许进一步正确性验证，而不必验证已经错误的2或多步挖掘：先执行粗糙的、容易的操作 (超集覆盖)然后在减少后的候选集上进行计算量大的算法 (Koperski & Han, SSD95).2022/8/7数据挖掘：概念和技术34第6章

19、：从大数据库中挖掘关联规则6.1 关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关性分析6.6基于约束的关联挖掘6.7小结2022/8/7数据挖掘：概念和技术35多维关联规则： 概念单维规则：buys(X, “milk”) buys(X, “bread”)多维规则： 2个以上维/谓词维间关联规则 (维词不重复)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)混合维关联规则 (维词重复)age(X,”19-25”) buys(X, “po

20、pcorn”) buys(X, “coke”)类别属性有限个值, 值之间无顺序关系数量属性数字的，值之间隐含了顺序关系2022/8/7数据挖掘：概念和技术36挖掘多维关联的技术搜索频繁k-维词集合：如: age, occupation, buys 是一个3-维词集合。按照对 age 处理方式的不同，分为：1. 用静态方法把数值属性离散化数值属性可用预定义的概念层次加以离散化。2. 带数量的关联规则根据数据的分布，动态的把数值属性离散化到不同的“箱”。3. 基于距离的关联规则用数据点之间的距离动态的离散化2022/8/7数据挖掘：概念和技术37数值属性的静态离散化在挖掘之前用概念层次先离散化数值

21、被替换为区间范围关系数据库中，要找到所有频繁k-维词需要k或k+1次表扫描。适宜使用数据立方体N维立方体的每个单元 对应一个维词集合使用数据立方体速度更快(income)(age)()(buys)(age, income)(age,buys)(income,buys)(age,income,buys)2022/8/7数据挖掘：概念和技术38带数量的关联规则age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)动态 离散化数值属性使满足某种挖掘标准，如最大化挖掘规则的置信度紧凑性.2-维数量关联规则： Aquan1 Aq

22、uan2 Acat用2-维表格把“邻近”的关联规则组合起来例子 2022/8/7数据挖掘：概念和技术39ARCS (关联规则聚集系统) （170页图6-18）ARCS 流程1. 分箱2. 查找频繁维词 集合3. 关联规则聚类4. 优化2022/8/7数据挖掘：概念和技术40ARCS的局限性数值属性只能出现在规则的左侧左侧只能有两个属性 (2维)ARCS 的改进不用基于栅格的方法等深分箱基于局部完整性 测度的聚集“Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agraw

23、al.2022/8/7数据挖掘：概念和技术41挖掘基于距离的关联规则分箱的方法没有体现数据间隔的语义基于距离的分割是更有“意义”的离散化方法，考虑：区间内密度或点的个数区间内点的“紧密程度2022/8/7数据挖掘：概念和技术42第6章：从大数据库中挖掘关联规则6.1 关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关性分析6.6基于约束的关联挖掘6.7小结2022/8/7数据挖掘：概念和技术43强关联规则不一定是有趣的（168例5.8）由关联分析到相关分析 项集A与项集B独立 P(AB)=P(A

24、)P(B) 项集A、B的相关性提升度 corrAB=P(AB)/P(A)P(B)（169页例5.9）卡方分析 卡方值 （169页例5.10）全置信度 余弦度量比较四种相关度量 （170页例5.11）2022/8/7数据挖掘：概念和技术44第6章：从大数据库中挖掘关联规则6.1 关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由关系数据库和数据仓库挖掘多维关联规则6.5由关联挖掘到相关性分析6.6基于约束的关联挖掘6.7小结2022/8/7数据挖掘：概念和技术456.6.1 基于约束的挖掘使用约束的必要性在数据挖掘中常使用的几种约束：知识类型约束：指定要

25、挖掘的知识类型 如关联规则数据约束： 指定与任务相关的数据集 Find product pairs sold together in Vancouver in Dec.98.维/层次约束:指定所用的维或概念结构中的层in relevance to region, price, brand, customer category.规则约束：指定要挖掘的规则形式(如规则模板)单价 (price $200).兴趣度约束：指定规则兴趣度阈值或统计度量如 (min_support 3%, min_confidence 60%).2022/8/7数据挖掘：概念和技术46假定AllElectronics的一个

26、销售多维数据库有如下关系(176页)Sales(customer_name,item_name,transaction_id)Lives(customer_name,region,city)Items(item_name,category，price)Transaction(transaction_id,day,month,year) (1) mine associations as (2)lives(C,_,”Pudong”)sales(C,I,S)=sales(C,JT) (3) from sales (4)where S.year=1999 &T.year=1999 &I.categor

27、y=J.category (5)group by C,I.category (6)having sum(I.price=500 (7)with support threshold=1% (8)with confidence threshold=50%Lives(C,_,”Pudong”)Sales(C,”Census_CD”,_)Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_) 1.5%,65%2022/8/7数据挖掘：概念和技术476.6.2 约束的分类单调性约束(monotone constraint)反单调性约束(anti-monotone

28、constraint)可转变的约束(convertibale constraint)简洁性约束(succinct constraint)不可转变的约束(non-convertibale constraint)2022/8/7数据挖掘：概念和技术48约束的有关概念项目集：I=i1,i2,im,交易：T=模式S是项目集的子集，S=ij1,ij2,ijk模式S包含与T,T=,iff S=It; S是S的子模式(subpattern)且S 是S的超模式(superpattern)，if 有S=v ， v是S的一个项集约束Cm 是单调的iff.对于任给的满足Cm的项集(模式) S, 每一个S的超集都能够

29、满足 Cm e.g: Cm : min(S)=v, v是S的一个项集第九章 数据挖掘的应用和发展趋势9.1 复杂数据对象的多维分析和描述性挖掘9.2 空间数据挖掘9.3 多媒体数据挖掘9.4 时序数据和序列数据的挖掘9.5 文本数据库挖掘9.6 Web挖掘9.1 复杂数据对象的多维分析和描述性挖掘结构化数据的概化空间和多媒体数据概化中的聚集和近似计算对象标识符和类/子类层次的概化类复合层次的概化对象立方体的构造与挖掘用分而治之方法对规划数据库进行基于概化的挖掘9.2 空间数据挖掘空间数据立方体构造和空间OLAP空间关联分析空间聚类方法空间分类和空间趋势分析光栅数据库挖掘9.3 多媒体数据挖掘多

30、媒体数据的相似性搜索 基于颜色直方图的特征标识；多特征构成的特征标识；基于小波的特征标识；带有区域粒度的小波特征表识多媒体数据的多维分析多媒体数据的分类和预测分析多媒体数据中的关联规则挖掘9.4 时序数据和序列数据的挖掘趋势分析 长期或趋势变化；循环变动或循环变化； 季节性变动或季节性变化；非规则或随机变化时序分析中的相似搜索序列模式挖掘周期分析 挖掘全周期模式；挖掘部分周期模式； 挖掘循环或周期关联规则。9.5 文本数据库挖掘文本数据分析和信息检索 研究大量文本文档的信息组织和检索 基本度量：查准率；查全率。文本挖掘：基于关键字的关联和文档分类9.6 Web挖掘挖掘Web链接结构，识别权威W

31、eb页面Web文档的自动分类多层Web信息库的构造Web使用记录的挖掘第十章 数据挖掘的应用和发展趋势10.1 数据挖掘的应用10.2 数据挖掘系统产品和研究原型10.3 数据挖掘的其他主题10.4 数据挖掘的社会影响10.5 数据挖掘的发展趋势10.1 数据挖掘的应用针对生物医学和DNA数据分析的数据挖掘针对金融数据分析的数据挖掘零售业中的数据挖掘电信业中的数据挖掘10.2 数据挖掘系统产品和研究原型怎样选择一个数据挖掘系统 数据类型；系统问题；数据源；数据挖掘的功能和方法；数据挖掘系统和数据仓库系统的结合；可伸缩性；可视化工具；数据挖掘查询语言和图形用户接口。 商用数据挖掘系统的例子 In

32、telligent Miner: IBM Enterprise Miner :SAS; MineSet SGI; Clementine SPSS; DBMiner DBMiner Technology10.3 数据挖掘的其他主题可视化数据挖掘 数据可视化；数据挖掘结果可视化；数据挖掘过程可视化；交互式的数据挖掘视频和音频数据挖掘科学和统计数据挖掘数据挖掘的理论基础数据挖掘和智能查询应答 例10.110.4 数据挖掘的社会影响数据挖掘是宣传出来的还是持久的稳定增长的商业数据挖掘只是经理的事还是每个人的事数据挖掘对隐私或数据安全构成威胁么？10.5 数据挖掘的发展趋势应用的探索可伸缩的数据挖掘方法

33、数据挖掘与数据库系统、数据仓库系统和WEB数据库系统的集成数据挖掘语言的标准化可视化数据挖掘复杂数据类型挖掘的新方法WEB挖掘数据挖掘中的隐私保护与数据信息安全Chapter 8. 聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（Partitioning Methods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结 划分方法: 基本概念划分方法: 将一个包含n个数据对象的数据库组织成k个划分（k=n），其中每个划分代表一个簇（Cluster）。给定一个k，要构造出k个簇，并满足采用的划分准则：全局最优:尽可能的列举所有的

34、划分；启发式方法: k-平均和k-中心点算法k-平均 (MacQueen67):由簇的中心来代表簇；k-中心点或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每个簇由簇中的某个数据对象来代表。 K-平均算法给定k，算法的处理流程如下:1.随机的把所有对象分配到k个非空的簇中；2.计算每个簇的平均值，并用该平均值代表相应的簇；3.将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中； 4.回到第二步，直到不再有新的分配发生。K-平均算法例子K-平均算法优点 相对高效的: 算法复杂度O(tkn), 其中n 是数据对象的个数

35、, k 是簇的个数, t是迭代的次数，通常k, t n.算法通常终止于局部最优解；缺点只有当平均值有意义的情况下才能使用，对于类别字段不适用；必须事先给定要生成的簇的个数；对“噪声”和异常数据敏感；不能发现非凸面形状的数据。K-平均算法的变种一些变种在下面几个方面有所不同：初始k个平均值的选择；相异度的计算；计算簇的平均值的策略；处理种类字段: k-模算法 (Huang98)用模来替代平均值；用新的相异度计算方法来处理类别字段；用基于频率的方法来修改簇的模；k-原型算法：综合k-平均和k-模算法，能同时处理类别字段和数值字段。K-中心点算法找出簇中位置最中心的对象，即中心点来代表簇PAM (P

36、artitioning Around Medoids, 1987)设定一个中心点的初始集合，然后反复的用非中心点对象来替代中心点对象，以改进聚类的质量；PAM 算法在大数据集上效率较低，没有良好的可伸缩性；CLARA (Kaufmann & Rousseeuw, 1990)CLARANS (Ng & Han, 1994): Randomized samplingPAM (Partitioning Around Medoids) (1987)PAM (Kaufman and Rousseeuw, 1987）用真实的数据对象来代表簇随机选择k个对象作为初始的中心点；Repeat对每一个由非中心对象

37、h 和中心对象 i, 计算i被h替代的总代价 Tcih 对每一个有h和I组成的对象对 If TCih 0, i 被 h替换然后将每一个非中心点对象根据与中心点的距离分配给离它最近的中心点Until不发生变化。PAM Clustering: Total swapping cost TCih=jCjihjihttihjhitjtihjCLARA (Clustering Large Applications) (1990)CLARA (Kaufmann and Rousseeuw in 1990)该算法首先获得数据集的多个采样，然后在每个采样上使用PAM算法，最后返回最好的聚类结果作为输出。优点:

38、能够处理大数据集。缺点:效率依赖于采样的大小；如果样本发生偏斜，基于样本的一个好的聚类不一定代表得了整个数据集合的一个好的聚类；CLARANS (“Randomized” CLARA) (1994)CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han94)CLARANS 在搜索的每一步动态的抽取一个样本；聚类过程可以被描述为对一个图的搜索，图中的每个节点是一个潜在的解，即k个中心点的集合；在替换 了一个中心点后的结果被称为当前结果的邻居。如果找到了一个局部最优，算法从随即选择的节点开始寻找新的局部最优；比

39、PAM 和 CLARA更有效和有更好的伸缩性；采用聚焦技术和空间数据结构等能进一步提高性能(Ester et al.95)Chapter 8. Cluster Analysis什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（Partitioning Methods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结层次方法采用距离作为衡量聚类的标准。该方法不在需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d

40、eStep 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)AGNES (Agglomerative Nesting)由 Kaufmann 和 Rousseeuw 提出；(1990)使用单链接方法和差异度矩阵； 合并那些具有最小差异度的节点；Go on in a non-descending fashion最后所有的对象合并形成一个簇。A Dendrogram Shows How the Clusters are Merged HierarchicallyDecompose data objects into a seve

41、ral levels of nested partitioning (tree of clusters), called a dendrogram. A clustering of the data objects is obtained by cutting the dendrogram at the desired level, then each connected component forms a cluster.DIANA (Divisive Analysis)由 Kaufmann 和 Rousseeuw 提出(1990)AGNES算法的逆过程；最终每个新的簇只包含一个对象；Mor

42、e on Hierarchical Clustering Methods层次方法的主要缺点：没有良好的伸缩性: 时间复杂度至少是 O(n2)一旦一个合并或分裂被执行，就不能修复；综合层次聚类和其它的聚类技术：BIRCH (1996): uses CF-tree and incrementally adjusts the quality of sub-clustersCURE (1998): selects well-scattered points from the cluster and then shrinks them towards the center of the cluster

43、by a specified fractionCHAMELEON (1999): hierarchical clustering using dynamic modelingBIRCH (1996)Birch: Balanced Iterative Reducing and Clustering using Hierarchies, by Zhang, Ramakrishnan, Livny (SIGMOD96)增量的构造一个CF树Phase 1: 扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构； Phase 2: 采用某个聚类算法对CF树的叶子节点进行聚类；可伸缩性: 数据集合的单