《数据挖掘 概念和技术3》由会员分享，可在线阅读，更多相关《数据挖掘 概念和技术3（22页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘: 概念和技术 Chapter 6 张晓辉 xiaohuifudan.edu复旦大学 （国际）数据库研究中心2001-11-61数据挖掘：概念和技术第6章：从大数据库中挖掘关联 规则n关联规则挖掘n从交易数据库中挖掘一维的布尔形关联规则n从交易数据库中挖掘多层次关联规则n在交易数据库和数据仓库中挖掘多维关联规则n从关联挖掘到相关性分析n基于约束的关联挖掘n小结2001-11-62数据挖掘：概念和技术多层关联规则n项通常具有层次n底层的项通常支持度也低n某些特定层的规则可能更 有意义n交易数据库可以按照维或 层编码n可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄2001-11-
2、63数据挖掘：概念和技术挖掘多层关联规则n自上而下，深度优先的方法：n先找高层的“强”规则： 牛奶 面包 20%, 60%.n再找他们底层的“弱”规则： 酸奶 黄面包 6%, 50%.n多层关联规则的变种n层次交叉的关联规则：酸奶 复旦面包房 黄面包n不同种分层方法间的关联规则：酸奶 复旦面包房面包2001-11-64数据挖掘：概念和技术多层关联规则: 支持度不变 vs. 支持度 递减n支持度不变: 在各层之间使用统一的支持度n+ 一个最小支持度阈值. 如果一个项集的父项集不具有 最小支持度，那他本身也不可能满足最小支持度。n 底层项不会成为频繁集，如果支持度n太高 丢失底层关联规则n太低 生
3、成太多的高层关联规则n支持度递减: 随着层次的降低支持度递减n4种搜索策略：n层与层独立n用k-项集跨层过滤n用项跨层过滤n用项进行可控跨层过滤2001-11-65数据挖掘：概念和技术支持度不变支持度不变多层挖掘牛奶support = 10%酸奶 support = 6%脱脂奶support = 4%层 1 min_sup = 5%层 2 min_sup = 5%2001-11-66数据挖掘：概念和技术支持度递减支持度递减多层挖掘酸奶 support = 6%脱脂奶 support = 4%层 1 min_sup = 5%层 2 min_sup = 3%牛奶support = 10%2001-
4、11-67数据挖掘：概念和技术多层关联：冗余过滤n由于“祖先”关系的原因，有些规则可能是多余的。n例子n牛奶 白面包 support = 8%, confidence = 70%n酸奶 白面包 support = 2%, confidence = 72%n我们称第一个规则是第二个规则的祖先n参考规则的祖先，如果他的支持度与我们“预期”的 支持度近似的话，我们就说这条规则是冗余的。2001-11-68数据挖掘：概念和技术多层挖掘：深度优先n自顶向下，深度优先的方法：n先挖掘高层频繁项：牛奶 (15%), 面包 (10%)n再挖掘他们底层的相对较弱的频繁项：酸奶 (5%), 白面包 (4%)n跨层
5、时对支持度的不同处理方法，对应了不同的 算法:n层之间支持度不变： 如果t的祖先是非频繁的，则不用考虑tn支持度随层递减： 则只考虑那些其祖先是频繁的/不可忽略的项2001-11-69数据挖掘：概念和技术数据挖掘查询的逐步精化n为什么要逐步精化n挖掘操作的代价可能高或低，结果可能细致或粗糙n在速度和质量之间折衷：逐步精化n超集覆盖特征：n预存储所有正面答案允许进一步正确性验证，而不必 验证已经错误的n2或多步挖掘：n先执行粗糙的、容易的操作 (超集覆盖)n然后在减少后的候选集上进行计算量大的算法 (Koperski & Han, SSD95).2001-11-610数据挖掘：概念和技术逐步求精
6、空间关联规则挖掘n空间关系的层次：n“g_close_to”: 邻近, 接触, 交叉, 包含n先搜索粗糙的关系然后再精化2001-11-611数据挖掘：概念和技术逐步求精空间关联规则挖掘(2)n空间关联规则的两步算法：n步骤 1: 粗糙空间计算 (用于过滤) n 用 MBR 或 R-tree 做粗糙估计n步骤 2: 细致空间算法 (用于精化)n 只计算已经通过空间计算的对象2001-11-612数据挖掘：概念和技术第6章：从大数据库中挖掘关联 规则n关联规则挖掘n从交易数据库中挖掘一维的布尔形关联规则n从交易数据库中挖掘多层次关联规则n在交易数据库和数据仓库中挖掘多维关联规则n从关联挖掘到相关
7、性分析n基于约束的关联挖掘n小结2001-11-613数据挖掘：概念和技术多维关联规则： 概念n单维规则： buys(X, “milk”) buys(X, “bread”)n多维规则： 2个以上维/谓词n维间关联规则 (维词不重复) age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)n混合维关联规则 (维词重复) age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)n类别属性n有限个值, 值之间无顺序关系n数量属性n数字的，值之间隐含了顺序关系2001-11-614数据挖掘：概念和技术挖掘多维
8、关联的技术n搜索频繁k-维词集合：n如: age, occupation, buys 是一个3-维词集合。n按照对 age 处理方式的不同，分为： 1. 用静态方法把数值属性离散化n数值属性可用预定义的概念层次加以离散化。 2. 带数量的关联规则n根据数据的分布动态的把数值属性离散化到不同的“箱 ”。 3. 基于距离的关联规则n用数据点之间的距离动态的离散化2001-11-615数据挖掘：概念和技术数值属性的静态离散化n在挖掘之前用概念层次先离散化n数值被替换为区间范围n关系数据库中，要找到所有频繁k-维词需要k或k+1次表扫 描。n适宜使用数据立方体nN维立方体的每个单元对应一个维词集合n使
9、用数据立方体速度更快(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)2001-11-616数据挖掘：概念和技术带数量的关联规则age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)n动态 离散化数值属性nSuch that the confidence or compactness of the rules mined is maximized.n2-维数量关联规则： Aquan1 Aquan2 Acatn用2-维表格
10、把“邻近”的 关联规则组合起来n例子 2001-11-617数据挖掘：概念和技术ARCS (关联规则聚集系统)ARCS 流程1. 分箱2. 查找频繁维词集合3. 聚集4. 优化2001-11-618数据挖掘：概念和技术ARCS的局限性n数值属性只能出现在规则的左侧n左侧只能有两个属性 (2维)nARCS 的改进n不用基于栅格的方法n等深分箱n基于局部完整性 测度的聚集n“Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agrawal.2001-11-619数据挖掘：概念
11、和技术挖掘基于距离的关联规则n分箱的方法没有体现数据间隔的语义n基于距离的分割是更有“意义”的离散化方法，考虑：n区间内密度或点的个数n区间内点的“紧密程度2001-11-620数据挖掘：概念和技术n记SX 为 N 个元组 t1, t2, , tN 在 属性集 X 上的投 影n则 SX 的直径:ndistx:距离量度,如 欧几里德距离或 Manhattan聚集和距离度量2001-11-621数据挖掘：概念和技术n用直径 d 评估聚集 CX 的密度，其中n查找聚集和基于距离的规则n用密度阈值 d0代替支持度n采用修改过的 BIRCH 聚集算法聚集和距离度量(Cont.)2001-11-622数据挖掘：概念和技术
