数据挖掘 概念和技术ar(3)

2001-11-6数据挖掘：概念和技术1数据挖掘:概念和技术—Chapter6—2001-11-6数据挖掘：概念和技术2第6章：从大数据库中挖掘关联规则关联规则挖掘从交易数据库中挖掘一维的布尔形关联规则从交易数据库中挖掘多层次关联规则在交易数据库和数据仓库中挖掘多维关联规则从关联挖掘到相关性分析基于约束的关联挖掘小结2001-11-6数据挖掘：概念和技术3多层关联规则项通常具有层次底层的项通常支持度也低某些特定层的规则可能更有意义交易数据库可以按照维或层编码可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄TIDItemsT1{111,121,211,221}T2{111,211,222,323}T3{112,122,221,411}T4{111,121}T5{111,122,211,221,413}2001-11-6数据挖掘：概念和技术4挖掘多层关联规则自上而下，深度优先的方法：先找高层的“强”规则：牛奶面包[20%,60%].再找他们底层的“弱”规则：酸奶黄面包[6%,50%].多层关联规则的变种层次交叉的关联规则：酸奶复旦面包房黄面包不同种分层方法间的关联规则：酸奶复旦面包房面包2001-11-6数据挖掘：概念和技术5多层关联规则:支持度不变vs.支持度递减支持度不变:在各层之间使用统一的支持度+一个最小支持度阈值.如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。–底层项不会成为频繁集，如果支持度太高丢失底层关联规则太低生成太多的高层关联规则支持度递减:随着层次的降低支持度递减4种搜索策略：层与层独立用k-项集跨层过滤用项跨层过滤用项进行可控跨层过滤2001-11-6数据挖掘：概念和技术6支持度不变支持度不变多层挖掘牛奶[support=10%]酸奶[support=6%]脱脂奶[support=4%]层1min_sup=5%层2min_sup=5%2001-11-6数据挖掘：概念和技术7支持度递减支持度递减多层挖掘酸奶[support=6%]脱脂奶[support=4%]层1min_sup=5%层2min_sup=3%牛奶[support=10%]2001-11-6数据挖掘：概念和技术8多层关联：冗余过滤由于“祖先”关系的原因，有些规则可能是多余的。例子牛奶白面包[support=8%,confidence=70%]酸奶白面包[support=2%,confidence=72%]我们称第一个规则是第二个规则的祖先参考规则的祖先，如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余的。2001-11-6数据挖掘：概念和技术9多层挖掘：深度优先自顶向下，深度优先的方法：先挖掘高层频繁项：牛奶(15%),面包(10%)再挖掘他们底层的相对较弱的频繁项：酸奶(5%),白面包(4%)跨层时对支持度的不同处理方法，对应了不同的算法:层之间支持度不变：如果t的祖先是非频繁的，则不用考虑t支持度随层递减：则只考虑那些其祖先是频繁的/不可忽略的项2001-11-6数据挖掘：概念和技术10数据挖掘查询的逐步精化为什么要逐步精化挖掘操作的代价可能高或低，结果可能细致或粗糙在速度和质量之间折衷：逐步精化超集覆盖特征：预存储所有正面答案—允许进一步正确性验证，而不必验证已经错误的2或多步挖掘：先执行粗糙的、容易的操作(超集覆盖)然后在减少后的候选集上进行计算量大的算法(Koperski&Han,SSD’95).2001-11-6数据挖掘：概念和技术11逐步求精空间关联规则挖掘空间关系的层次：“g_close_to”:邻近,接触,交叉,包含先搜索粗糙的关系然后再精化2001-11-6数据挖掘：概念和技术12逐步求精空间关联规则挖掘(2)空间关联规则的两步算法：步骤1:粗糙空间计算(用于过滤)用MBR或R-tree做粗糙估计步骤2:细致空间算法(用于精化)只计算已经通过空间计算的对象2001-11-6数据挖掘：概念和技术13第6章：从大数据库中挖掘关联规则关联规则挖掘从交易数据库中挖掘一维的布尔形关联规则从交易数据库中挖掘多层次关联规则在交易数据库和数据仓库中挖掘多维关联规则从关联挖掘到相关性分析基于约束的关联挖掘小结2001-11-6数据挖掘：概念和技术14多维关联规则：概念单维规则：buys(X,“milk”)buys(X,“bread”)多维规则：2个以上维/谓词维间关联规则(维词不重复)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合维关联规则(维词重复)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)类别属性有限个值,值之间无顺序关系数量属性数字的，值之间隐含了顺序关系2001-11-6数据挖掘：概念和技术15挖掘多维关联的技术搜索频繁k-维词集合：如:{age,occupation,buys}是一个3-维词集合。按照对age处理方式的不同，分为：1.用静态方法把数值属性离散化数值属性可用预定义的概念层次加以离散化。2.带数量的关联规则根据数据的分布动态的把数值属性离散化到不同的“箱”。3.基于距离的关联规则用数据点之间的距离动态的离散化2001-11-6数据挖掘：概念和技术16数值属性的静态离散化在挖掘之前用概念层次先离散化数值被替换为区间范围关系数据库中，要找到所有频繁k-维词需要k或k+1次表扫描。适宜使用数据立方体N维立方体的每个单元对应一个维词集合使用数据立方体速度更快(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)2001-11-6数据挖掘：概念和技术17带数量的关联规则age(X,”30-34”)income(X,”24K-48K”)buys(X,”highresolutionTV”)动态离散化数值属性Suchthattheconfidenceorcompactnessoftherulesminedismaximized.2-维数量关联规则：Aquan1Aquan2Acat用2-维表格把“邻近”的关联规则组合起来例子2001-11-6数据挖掘：概念和技术18ARCS(关联规则聚集系统)ARCS流程1.分箱2.查找频繁维词集合3.聚集4.优化2001-11-6数据挖掘：概念和技术19ARCS的局限性数值属性只能出现在规则的左侧左侧只能有两个属性(2维)ARCS的改进不用基于栅格的方法等深分箱基于局部完整性测度的聚集“MiningQuantitativeAssociationRulesinLargeRelationalTables”byR.SrikantandR.Agrawal.2001-11-6数据挖掘：概念和技术20挖掘基于距离的关联规则分箱的方法没有体现数据间隔的语义基于距离的分割是更有“意义”的离散化方法，考虑：区间内密度或点的个数区间内点的“紧密程度价格（$）等宽(宽度$10)等深(深度2)基于距离7[0,10][7,20][7,7]20[11,20][22,50][20,22]22[21,30][51,53][50,53]50[31,40]51[41,50]53[51,60]2001-11-6数据挖掘：概念和技术23海量管理资源免费下载：