数据挖掘概念与技术CHAPTER5-挖掘关联规则.ppt

1 第5章 挖掘关联规则 关联规则挖掘事务数据库中 单维布尔 关联规则挖掘的可伸缩算法挖掘各种关联 相关规则基于限制的关联挖掘 顺序模式挖掘小结 2 关联规则 关联规则反映一个事物与其他事物之间的相互依存性和关联性 如果两个或者多个事物之间存在一定的关联关系 那么 其中一个事物就能够通过其他事物预测到 典型的关联规则发现问题是对超市中的货篮数据 MarketBasket 进行分析 通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯 3 什么是关联规则挖掘 关联规则挖掘首先被Agrawal ImielinskiandSwami在1993年的SIGMOD会议上提出在事务 关系数据库中的项集和对象中发现频繁模式 关联规则 相关性或者因果结构频繁模式 数据库中频繁出现的项集目的 发现数据中的规律超市数据中的什么产品会一起购买 啤酒和尿布在买了一台PC之后下一步会购买 哪种DNA对这种药物敏感 我们如何自动对Web文档进行分类 4 频繁模式挖掘的重要性 许多重要数据挖掘任务的基础关联 相关性 因果性序列模式 空间模式 时间模式 多维关联分类 聚类分析更加广泛的用处购物篮分析 交叉销售 直销点击流分析 DNA序列分析等等 5 关联规则基本模型 IBM公司Almaden研究中心的R Agrawal首先提出关联规则模型 并给出求解算法AIS 随后又出现了SETM和Apriori等算法 其中 Apriori是关联规则模型中的经典算法 给定一组事务产生所有的关联规则满足最小支持度和最小可信度 6 关联规则基本模型 设I i1 im 为所有项目的集合 D为事务数据库 事务T是一个项目子集 T I 每一个事务具有唯一的事务标识TID 设A是一个由项目构成的集合 称为项集 事务T包含项集A 当且仅当A T 如果项集A中包含k个项目 则称其为k项集 项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度 如果项集的支持度超过用户给定的最小支持度阈值 就称该项集是频繁项集 或大项集 7 关联规则基本模型 关联规则是形如X Y的逻辑蕴含式 其中X I Y I 且X Y 如果事务数据库D中有s 的事务包含X Y 则称关联规则X Y的支持度为s 实际上 支持度是一个概率值 是一个相对计数 support X Y P X Y 项集的支持度计数 频率 support count包含项集的事务数若项集X的支持度记为support X 规则的信任度为support X Y support X 是一个条件概率P Y X confidence X Y P Y X support count X Y support count X 8 频繁模式和关联规则 ItemsetX x1 xk 找出满足最小支持度和置信度的所规则X Y支持度 s 事务包含X Y的概率置信度 c 事务含X也包含Y的条件概率 令supmin 50 confmin 50 Freq Pat A 3 B 3 D 4 E 3 AD 3 关联规则Associationrules A D 60 100 D A 60 75 9 挖掘关联规则 一个例子 规则A C 支持度 support A C 50 置信度 support A C support A 66 6 最小支持度50 最小置信度50 10 闭频繁项集and极大频繁项集 一个长模式包含子模式的数目 e g a1 a100 contains 1001 1002 110000 2100 1 1 27 1030sub patterns 解 Mineclosedpatternsandmax patternsinstead一个频繁项集X是闭的 如果X是频繁的 且不存在真超项集nosuper patternY X 有相同的支持度计数 proposedbyPasquier etal ICDT 99 项集X是极大频繁项集ifXisfrequentandthereexistsnofrequentsuper patternY X proposedbyBayardo SIGMOD 98 两者有不同 极大频繁项集定义中对真超集要松一些 11 闭频繁项集and极大频繁项集 Exercise DB Min sup 1 Whatisthesetofcloseditemset 1 2Whatisthesetofmax pattern 1Whatisthesetofallpatterns 12 关联规则基本模型 关联规则就是支持度和信任度分别满足用户给定阈值的规则 发现关联规则需要经历如下两个步骤 找出所有频繁项集 由频繁项集生成满足最小信任度阈值的规则 13 第5章 挖掘关联规则 关联规则挖掘事务数据库中 单维布尔 关联规则挖掘的可伸缩算法挖掘各种关联 相关规则基于限制的关联挖掘 顺序模式挖掘小结 14 Apriori算法的步骤 Apriori算法命名源于算法使用了频繁项集性质的先验 Prior 知识 Apriori算法将发现关联规则的过程分为两个步骤 通过迭代 检索出事务数据库中的所有频繁项集 即支持度不低于用户设定的阈值的项集 利用频繁项集构造出满足用户最小信任度的规则 挖掘或识别出所有频繁项集是该算法的核心 占整个计算量的大部分 15 频繁项集 为了避免计算所有项集的支持度 实际上频繁项集只占很少一部分 Apriori算法引入潜在频繁项集的概念 若潜在频繁k项集的集合记为Ck 频繁k项集的集合记为Lk m个项目构成的k项集的集合为 则三者之间满足关系Lk Ck 构成潜在频繁项集所遵循的原则是 频繁项集的子集必为频繁项集 16 关联规则的性质 性质1 频繁项集的子集必为频繁项集 性质2 非频繁项集的超集一定是非频繁的 Apriori算法运用性质1 通过已知的频繁项集构成长度更大的项集 并将其称为潜在频繁项集 潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合 以后只需计算潜在频繁项集的支持度 而不必计算所有不同项集的支持度 因此在一定程度上减少了计算量 17 Apriori 一种候选产生 测试方法 频繁项集的任何子集必须是频繁的如果 beer diaper nuts 是频繁的 beer diaper 也是每个包含 beer diaper nuts 的事务也包含 beer diaper Apriori剪枝原则 如果一个项集不是频繁的 将不产生 测试它的超集 方法 由长度为k的频繁项集产生长度为 k 1 的候选项集 并且根据DB测试这些候选性能研究表明了它的有效性和可伸缩性 18 Apriori算法 一个例子 数据库TDB 第1次扫描 C1 L1 L2 C2 C2 第2次扫描 C3 L3 第3次扫描 19 Apriori算法 1 L1 频繁1项集 2 for k 2 Lk 1 k dobegin 3 Ck apriori gen Lk 1 新的潜在频繁项集 4 foralltransactionst Ddobegin 5 Ct subset Ck t 找出t中包含的潜在的频繁项 6 forallcandidatesc Ctdo 7 c count 8 end 9 Lk c Ck c count minsup 10 end 11 Answer 20 Apriori的重要细节 如何产生候选 步骤1 Lk的自连接步骤2 剪枝候选产生的例子L3 abc abd acd ace bcd 自连接 L3 L3Abcd 由abc和abdAcde 由acd和ace剪枝 acde被删除 因为ade不在L3C4 abcd 21 如何产生候选 假定Lk 1中的项集已排序 按字典序排序 步骤1 Lk 1自连接insertintoCkselectp item1 p item2 p itemk 1 q itemk 1fromLk 1p Lk 1qwherep item1 q item1 p itemk 2 q itemk 2 p itemk 1 q itemk 1Step2 剪枝forallitemsetscinCkdoforall k 1 subsetssofcdoif sisnotinLk 1 thendeletecfromCk 22 例子 支持计数 2 23 例子 24 由频繁项集产生关联规则 根据公式产生关联规则对于每个频繁项集l 产生所有的非空子集对于l的每个非空子集s 如果则输出规则 s l s 25 频繁模式挖掘的挑战 挑战事务数据库的多遍扫描数量巨大的候选候选支持度计数繁重的工作量改进Apriori 基本思想减少事务数据库的扫描遍数压缩候选数量便于候选计数 26 提高Apriori算法的方法 Hash baseditemsetcounting 散列项集计数 Transactionreduction 事务压缩 Partitioning 划分 Sampling 采样 27 划分 只扫描数据库两次 项集在DB中是频繁的 它必须至少在DB的一个划分中是频繁的扫描1 划分数据库 并找出局部频繁模式localfrequentitemset扫描2 求出全局频繁模式A Savasere E Omiecinski andS Navathe Anefficientalgorithmforminingassociationinlargedatabases InVLDB 95 DB1 DB2 DBk DB sup1 i DB1 sup2 i DB2 supk i DBk sup i DB 28 抽样 频繁模式 选取原数据库的一个样本 使用Apriori算法在样本中挖掘频繁模式扫描一次数据库 验证在样本中发现的频繁模式 再次扫描数据库 找出遗漏的频繁模式牺牲一些精度换取有效性 H Toivonen Samplinglargedatabasesforassociationrules InVLDB 96 29 DHP 压缩候选的数量 散列项集到对应的桶中 一个其hash桶的计数小于阈值的k itemset不可能是频繁的J Park M Chen andP Yu Aneffectivehash basedalgorithmforminingassociationrules InSIGMOD 95 30 DIC Dynamicitemsetcounting 减少扫描次数 ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D Itemsetlattice 一旦确定A和D是频繁的 立即开始AD的计数一旦确定BCD的两个长度为2的子集是频繁的 立即开始BCD的计数 事务 1 itemsets 2 itemsets Apriori 1 itemsets 2 items 3 items DIC S BrinR Motwani J Ullman andS Tsur Dynamicitemsetcountingandimplicationrulesformarketbasketdata InSIGMOD 97 31 使用垂直数据格式挖掘频繁项集VerticalDataFormat 使用tid list 包含item的事务的标识的集合 M Zakietal Newalgorithmsforfastdiscoveryofassociationrules InKDD 97扫描一次数据集将水平格式数据转化为垂直格式通过频繁k项集的tid list的交集 计算对应 k 1 项集的tid list 32 频繁模式挖掘的瓶颈 多遍数据库扫描是昂贵的挖掘长模式需要很多遍扫描 并产生大量候选挖掘频繁模式i1i2 i100扫描次数 100候选个数 1001 1002 110000 2100 1 1 27 1030 瓶颈 候选产生 测试能够避免候选产生吗 33 挖掘频繁模式而不产生候选 使用局部频繁的项 由短模式增长产生长模式 abc 是频繁模式得到包含 abc 的所有事务 DB abc d 是DB abc中的局部频繁项 abcd是频繁模式 34 由事务数据库构造FP 树 min support 3 TIDItemsbought ordered frequentitems100 f a c d g i m p f c a m p 200 a b c f l m o f c a b m 300 b f h j o w f b 400 b c k s p c b p 500 a f c e l p m n f c a m p 扫描DB一次 找出频繁1 itemset 单个项的模式 按频率的降序将频繁项排序 得到f list再次扫描DB 构造FP 树 F list f c a b m p 35 划分模式和数据库 可以按照f list将频繁模式划分成子集F list f c a b m p包含p的模式包含m但不包含p的模式 包含c但不包含a b m p模式f完全性和非冗余性 36 从p 条件数据库找出含p的模式 从FP 树的频繁项头表开始沿着频繁项p的链搜索FP 树收集项p的所有变换的前缀路径形成p的模式基 条件模式基itemcond patternbasecf 3afc 3bfca 1 f 1 c 1mfca 2 fcab 1pfcam 2 cb 1 37 通过建立条件模式库得到频繁集 38 从条件模式基到条件FP 树 对于每个条件模式基累计条件模式基中每个项的计数构造模式基中频繁项的FP 树 m 条件模式基 fca 2 fcab 1 m的所有频繁模式m fm cm am fcm fam cam fcam f 4 c 1 b 1 p 1 b 1 c 3 a 3 b 1 m 2 p 2 m 1 头表Itemfrequencyheadf4c4a3b3m3p3 39 递归 挖掘每个条件FP 树 am 的条件模式基 fc 3 cm 的条件模式基 f 3 f 3 cm 条件FP 树 cam 的条件模式基 f 3 f 3 cam 条件FP 树 40 特殊情况 FP 树中的单个前缀路径 假定 条件 FP 树T具有单个共享的前缀路径P挖掘可以分解成两步将单个前缀路径归约成一个结点连接两部分的挖掘结果 41 使用FP 树挖掘频繁模式 基本思想 频繁模式增长通过模式和数据库划分递归地增长频繁模式方法 1 对于每个频繁项 构造它的条件模式基 2 然后构造它的条件FP 树 3 在新构造的条件FP 树上重复这一过程直到结果条件FP 树为空 或者它只包含一条路径 单个路径将产生其子路径的所有组合 每个子路径是一个频繁模式 42 FP 树结构的优点 完全性保留频繁模式挖掘的完整信息不截断任何事务的长模式压缩性压缩无关信息 非频繁的项被删除项按频率的降序排列 越是频繁出现 越可能被共享绝对不比原来的数据库大 不计结点链和计数字段 43 FP 增长的规模化 FP 树不能放在内存 怎么办 数据库投影数据库投影首先将数据库划分成一组投影数据库然后对每个投影数据库构造并挖掘FP 树 44 FP 增长vs Apriori 随支持度增长的可伸缩性 DatasetT25I20D10K 45 FP 增长vs 树 投影 随支持度增长的可伸缩性 DatasetT25I20D100K 46 为什么FP 增长是赢家 分治 根据已经得到的频繁模式划分任务和数据库导致较小的数据库的聚焦的搜索其它因素没有候选产生 没有候选测试压缩数据库 FP 树结构不重复地扫描整个数据库基本操作 局部频繁项计数和建立子FP 树 没有模式搜索和匹配 47 有关的其他方法 挖掘频繁闭项集合和最大模式CLOSET DMKD 00 挖掘序列模式FreeSpan KDD 00 PrefixSpan ICDE 01 频繁模式的基于限制的挖掘Convertibleconstraints KDD 00 ICDE 01 计算具有复杂度量的冰山数据方H treeandH cubingalgorithm SIGMOD 01 48 最大模式 频繁模式 a1 a100 包含 1001 1002 110000 2100 1 1 27 1030频繁子模式 最大模式 频繁模式 其真超模式都不是频繁的BCDE ACD是最大模式BCD不是最大模式 Min sup 2 49 MaxMiner 挖掘最大模式 扫描1 找出频繁项A B C D E扫描2 找出以下项集的支持度AB AC AD AE ABCDEBC BD BE BCDECD CE CDE DE由于BCDE是最大模式 不必在此后的扫描时检查BCD BDE CDER Bayato Efficientlymininglongpatternsfromdatabases InSIGMOD 98 潜在的最大模式 50 关联规则的可视化 PaneGraph 51 第5章 挖掘关联规则 关联规则挖掘事务数据库中 单维布尔 关联规则挖掘的可伸缩算法挖掘各种关联 相关规则基于限制的关联挖掘顺序模式挖掘小结 52 挖掘各种规则或规律性 多层关联规则 多维关联规则 量化关联规则 相关性和因果关系 比率规则 序列模式 显露模式 时间关联 局部周期性 53 多层关联规则 项常常形成层次结构 概念分层多个抽象层次上挖据得到的关联规则 多层关联规则灵活的支持度设定 较低层中的项一般具有较低的支持度 54 多层关联 冗余过滤 由于项之间的 祖先 联系 有些规则可能是多余的 例milk wheatbread support 8 confidence 70 2 milk wheatbread support 2 confidence 72 其中2 milk占milk的1 4我们可以说第一个规则是第二个规则的祖先 一个规则是冗余的 如果根据规则的祖先 其支持度和置信度都接近于 期望 值 55 多层挖掘 逐步深入 一种自顶向下 逐步深入的方法 首先挖掘最高层的频繁模式 milk 15 bread 10 然后挖掘它们下层 较弱的 频繁模式 2 milk 5 wheatbread 4 多层之间的不同的最小支持度阈值导致不同的算法 如果不同层之间采用相同的min support则丢弃t如果t 的任意祖先是非频繁的 如果在较低层采用递减的min support则只考察其祖先为频繁的项集 56 多维关联规则 单维规则 包括单个谓词 可以多次出现 或单个维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 数据的属性可分为两类分类属性有限个不同值 值之间无序量化属性数值的 值之间隐含次序 57 挖掘多维关联规则的技术 搜索频繁k 谓词集 包含k个合取谓词的集合例 age occupation buys 是一个3 谓词集 可以按如何处理age对技术分类 使用量化属性的静态离散化使用预先定义的概念分层 对量化属性静态地离散化 量化关联规则根据数据的分布 将量化属性离散化到 箱 基于距离的关联规则是一种动态的离散化过程 它考虑数据点之间的距离 58 量化属性的静态离散化 使用概念分层 在挖掘之前离散化 数值用区间值替换 在关系数据库中 找出所有的频繁k 谓词集需要k或k 1次表扫描 数据立方体非常适合挖掘 n 维方体对应于谓词集合的方体 从数据立方体挖掘可以快得多 59 量化关联规则 数值属性动态地离散化使挖出的规则的置信度或紧凑性最大化 2 维量化关联规则 Aquan1 Aquan2 Acat 分类属性 ARCS方法 使用2 D栅格 1 对属性进行 等宽 分箱2 找频繁谓词集3 规则聚类 对 相邻的 关联规则聚类形成一般关联规则 例 age X 34 35 income X 31K 50K buys X highresolutionTV 60 挖掘基于距离的关联规则 分箱方法不能紧扣区间数据的语义基于距离的划分 更有意义的离散化考虑 区间内点的密度 数量区间内点的 紧密性 61 具有灵活的支持度限制的多层ML MD多维关联规则 为什么 现实中项的出现频率差异很大购物中的钻石 表 笔一致的支持度可能不是一种好的模型灵活的模型通常 层越低 维的组合越多 长模式越长 支持度越小一般规则应当是特指的 易于理解的特殊的项或特殊的项群可能被个别地指定 并具有较高的优先权 62 兴趣度度量 相关性 Lift playbasketball eatcereal 40 66 7 是误导吃谷类食品的学生所占的百分比为75 比66 7 还高 playbasketball noteatcereal 20 33 3 更准确 其支持度和置信度都较低依赖 相关事件的度量 63 WhichMeasuresShouldBeUsed 提升度和 2不是好的相关度量 对于大的交易数据库all conforcoherencecouldbegoodmeasures Omiecinski TKDE 03 Over20interestingnessmeasureshavebeenproposed seeTan Kumar Sritastava KDD 02 Whicharegoodones 64 第5章 挖掘关联规则 关联规则挖掘事务数据库中 单维布尔 关联规则挖掘的可伸缩算法挖掘各种关联 相关规则基于限制的关联挖掘顺序模式挖掘频繁模式挖掘的应用 扩展小结 65 基于约束的数据挖掘 自动地找出数据库中的所有模式 不现实 模式可能太多 并不聚焦 数据挖掘应当是一个交互的过程用户使用数据挖掘查询语言 或图形用户界面 指导需要挖掘什么基于约束的挖掘用户灵活性 提供挖掘的约束系统优化 考察限制 寻找有效的挖掘 基于约束的挖掘 66 数据挖掘的约束 知识类型约束 分类 关联 等 数据约束 指定任务相关的数据集 使用类SQL查询找出Vancouver2000年12月份一起销售的产品对维 层约束 指定数据属性 概念分层结构的层次关于region price brand customercategory兴趣度约束强规则 min support 3 min confidence 60 规则 或模式 约束 指定规则形式小额销售 价格 200 67 元规则制导挖掘Meta RuleGuidedMining 元规则是带有部分约束谓词和常量的规则P1 X Y P2 X W buys X iPad 一个导致的规则age X 15 25 profession X student buys X iPad 通常情况 元规则如下形式的规则模板P1 P2 Pl Q1 Q2 Qr挖掘过程找出所有的频繁 l r 谓词集 基于最小支持度阈值 比须保留l子集的支持度 计数 计算规则的置信度 挖掘过程中 尽可能推进约束 见约束推进技术 尽可能地应用置信度 相关和其他度量 68 规则约束 剪枝搜索空间 规则约束的分类反单调性Anti monotonic单调性Monotonic简洁性Succinct 可转变的Convertible 不可转变的 69 规则约束 反单调性 反单调性当项集S违反规则约束时 它的任何超集合也违反约束sum S Price v是反单调的sum S Price v不是反单调的例 C range S profit 15是反单调的项集ab违反约束Cab的每个超集也违反约束C TDB min sup 2 70 规则约束 单调性 单调性当项集S满足约束时 它的任何超集合也满足约束sum S Price v是单调的min S Price v是单调的例 C range S profit 15项集ab满足Cab的每个超集合也满足C TDB min sup 2 71 简洁性 简洁性 给定满足约束C的项的集合A1 则满足C的任意集合S都基于A1 即 S包含一个属于A1的子集思想 不查看事务数据库 项集S是否满足约束C可以根据选取的项确定min S Price v是简洁的sum S Price v不是简洁的优化 如果C是简洁的 C是预计数可推进的 pre countingpushable 72 Apriori算法 一个例子 DatabaseD ScanD C1 L1 L2 C2 C2 ScanD C3 L3 ScanD 73 朴素算法 Apriori 约束 DatabaseD ScanD C1 L1 L2 C2 C2 ScanD C3 L3 ScanD 约束 Sum S price 5 74 受约束的Apriori算法 推进反单调约束 DatabaseD ScanD C1 L1 L2 C2 C2 ScanD C3 L3 ScanD 约束 Sum S price 5 75 转换 强硬的 约束 通过将项适当地排序 将强硬的约束转换成反单调的或单调的例C avg S profit 25将项按profit值的递减序排序如果项集afb违反Cafbh afb 也违反C约束C成为反单调的 TDB min sup 2 76 可转变的约束 设R项集的项以特定次序安排 可转变反单调如果项集S违反约束C 每个关于R以S为前缀的项集也违反约束C例 avg S v 如果项值递减序排列可转变单调如果项集S满足约束C 每个关于R以S为前缀的项集也满足约束C 例 avg S v 如果项值递增序排列 77 强可转变约束 avg X 25关于项值的递减序R 是可转变反单调的如果项集af违反约束C 每个以af为前缀的项集也违反C 如afdavg X 25关于项值的递增序R 1 是可转变单调的如果项集d满足约束C df和dfa也满足 它们具有前缀d这样 avg X 25是强可转变的 78 约束的性质汇总 79 约束的分类 可转变反单调 可转变单调 强可转变 不可转变的 简洁 反单调 单调 80 Apriori能够处理可转变的约束吗 可转变的 但既不是单调 反单调 也不是简洁的约束不能推进到Apriori挖掘算法的挖掘过程中在逐级的框架下 不能做直接基于该约束的剪枝项集df违反约束C avg X 25由于adf满足C Apriori需要df来组装adf 因此不能将df剪去但是 在模式增长框架下该约束可以推进到挖掘过程中 81 具有可转变约束的挖掘 C avg X 25 min sup 2以值的递减序R 列出事务中的每一个项关于R C是可转变反单调的扫描TDB一次删除非频繁项项h被删除项a和f是好的 基于投影的挖掘利用项投影的适当次序许多强硬的约束可以转变成 反 单调的 TDB min sup 2 82 讨论 处理多个约束 不同的约束需要不同的 甚至相互冲突的项序如果存在序R 使得约束C1和C2关于R是可转变的 则两个可转变的约束之间不存在冲突如果项序存在冲突试图先满足一个约束然后使用另一约束的序 在相应的投影数据库中挖掘频繁项集 83 文献 频繁模式挖掘方法 R Agarwal C Aggarwal andV V V Prasad Atreeprojectionalgorithmforgenerationoffrequentitemsets JournalofParallelandDistributedComputing 2000 R Agrawal T Imielinski andA Swami Miningassociationrulesbetweensetsofitemsinlargedatabases SIGMOD 93 207 216 Washington D C R AgrawalandR Srikant Fastalgorithmsforminingassociationrules VLDB 94487 499 Santiago Chile J Han J Pei andY Yin Miningfrequentpatternswithoutcandidategeneration InProc ACM SIGMOD 2000 pp 1 12 Dallas TX May2000 H Mannila H Toivonen andA I Verkamo Efficientalgorithmsfordiscoveringassociationrules KDD 94 181 192 Seattle WA July1994 84 文献 频繁模式挖掘方法 A Savasere E Omiecinski andS Navathe Anefficientalgorithmforminingassociationrulesinlargedatabases VLDB 95 432 443 Zurich Switzerland C Silverstein S Brin R Motwani andJ Ullman Scalabletechniquesforminingcausalstructures VLDB 98 594 605 NewYork NY R SrikantandR Agrawal Mininggeneralizedassociationrules VLDB 95 407 419 Zurich Switzerland Sept 1995 R SrikantandR Agrawal Miningquantitativeassociationrulesinlargerelationaltables SIGMOD 96 1 12 Montreal Canada H Toivonen Samplinglargedatabasesforassociationrules VLDB 96 134 145 Bombay India Sept 1996 M J Zaki S Parthasarathy M Ogihara andW Li Newalgorithmsforfastdiscoveryofassociationrules KDD 97 August1997 85 文献 频繁模式挖掘 性能改进 S Brin R Motwani J D Ullman andS Tsur Dynamicitemsetcountingandimplicationrulesformarketbasketanalysis SIGMOD 97 Tucson Arizona May1997 D W Cheung J Han V Ng andC Y Wong Maintenanceofdiscoveredassociationrulesinlargedatabases Anincrementalupdatingtechnique ICDE 96 NewOrleans LA T Fukuda Y Morimoto S Morishita andT Tokuyama Dataminingusingtwo dimensionaloptimizedassociationrules Scheme algorithms andvisualization SIGMOD 96 Montreal Canada E H Han G Karypis andV Kumar Scalableparalleldataminingforassociationrules SIGMOD 97 Tucson Arizona J S Park M S Chen andP S Yu Aneffectivehash basedalgorithmforminingassociationrules SIGMOD 95 SanJose CA May1995 86 文献 频繁模式挖掘 性能改进 G Piatetsky Shapiro Discovery analysis andpresentationofstrongrules InG Piatetsky ShapiroandW J Frawley KnowledgeDiscoveryinDatabases AAAI MITPress 1991 J S Park M S Chen andP S Yu Aneffectivehash basedalgorithmforminingassociationrules SIGMOD 95 SanJose CA S Sarawagi S Thomas andR Agrawal Integratingassociationruleminingwithrelationaldatabasesystems Alternativesandimplications SIGMOD 98 Seattle WA K Yoda T Fukuda Y Morimoto S Morishita andT Tokuyama Computingoptimizedrectilinearregionsforassociationrules KDD 97 NewportBeach CA Aug 1997 M J Zaki S Parthasarathy M Ogihara andW Li Parallelalgorithmfordiscoveryofassociationrules DataMiningandKnowledgeDiscovery 1 343 374 1997 87 文献 频繁模式挖掘 外延 S Brin R Motwani andC Silverstein Beyondmarketbasket Generalizingassociationrulestocorrelations SIGMOD 97 265 276 Tucson Arizona J HanandY Fu Discoveryofmultiple levelassociationrulesfromlargedatabases VLDB 95 420 431 Zurich Switzerland M Klemettinen H Mannila P Ronkainen H Toivonen andA I Verkamo Findinginterestingrulesfromlargesetsofdiscoveredassociationrules CIKM 94 401 408 Gaithersburg Maryland F Korn A Labrinidis Y Kotidis andC Faloutsos Ratiorules Anewparadigmforfast quantifiabledatamining VLDB 98 582 593 NewYork NY 88 文献 频繁模式挖掘 外延 B Lent A Swami andJ Widom Clusteringassociationrules ICDE 97 220 231 Birmingham England R Meo G Psaila andS Ceri AnewSQL likeoperatorforminingassociationrules VLDB 96 122 133 Bombay India R J MillerandY Yang Associationrulesoverintervaldata SIGMOD 97 452 461 Tucson Arizona A Savasere E Omiecinski andS Navathe Miningforstrongnegativeassociationsinalargedatabaseofcustomertransactions ICDE 98 494 502 Orlando FL Feb 1998 D Tsur J D Ullman S Abitboul C Clifton R Motwani andS Nestorov Queryflocks Ageneralizationofassociation rulemining SIGMOD 98 1 12 Seattle Washington J Pei A K H Tung J Han Fault TolerantFrequentPatternMining ProblemsandChallenges SIGMODDMKD 01 SantaBarbara CA 89 文献 挖掘最大模式和闭项集 R J Bayardo Efficientlymininglongpatternsfromdatabases SIGMOD 98 85 93 Seattle Washington J Pei J Han andR Mao CLOSET AnEfficientAlgorithmforMiningFrequentClosedItemsets Proc 2000ACM SIGMODInt WorkshoponDataMiningandKnowledgeDiscovery DMKD 00 Dallas TX May2000 N Pasquier Y Bastide R Taouil andL Lakhal Discoveringfrequentcloseditemsetsforassociationrules ICDT 99 398 416 Jerusalem Israel Jan 1999 M Zaki GeneratingNon RedundantAssociationRules KDD 00 Boston MA Aug 2000M Zaki CHARM AnEfficientAlgorithmforClosedAssociationRuleMining SIAM 02 90 文献 基于约束的频繁模式挖掘 G Grahne L Lakshmanan andX Wang Efficientminingofconstrainedcorrelatedsets ICDE 00 512 521 SanDiego CA Feb 2000 Y FuandJ Han Meta rule guidedminingofassociationrulesinrelationaldatabases KDOOD 95 39 46 Singapore Dec 1995 J Han L V S Lakshmanan andR T Ng Constraint Based MultidimensionalDataMining COMPUTER specialissuesonDataMining 32 8 46 50 1999 L V S Lakshmanan R Ng J HanandA Pang OptimizationofConstrainedFrequentSetQuerieswith2 VariableConstraints SIGMOD 99 91 文献 基于约束的频繁模式挖掘 R Ng L V S Lakshmanan J Han A Pang Exploratoryminingandpruningoptimizationsofconstrainedassociationrules SIGMOD 98J Pei J Han andL V S Lakshmanan MiningFrequentItemsetswithConvertibleConstraints Proc 2001Int Conf onDataEngineering ICDE 01 April2001 J PeiandJ Han CanWePushMoreConstraintsintoFrequentPatternMining Proc 2000Int Conf onKnowledgeDiscoveryandDataMining KDD 00 Boston MA August2000 R Srikant Q Vu andR Agrawal Miningassociationruleswithitemconstraints KDD 97 67 73 NewportBeach California 92 文献 序列模式挖掘方法 R AgrawalandR Srikant Miningsequentialpatterns ICDE 95 3 14 Taipei Taiwan R SrikantandR Agrawal Miningsequentialpatterns Generalizationsandperformanceimprovements EDBT 96 J Han J Pei B Mortazavi Asl Q Chen U Dayal M C Hsu FreeSpan FrequentPattern ProjectedSequentialPatternMining Proc 2000Int Conf onKnowledgeDiscoveryandDataMining KDD 00 Boston MA August2000 H Mannila HToivonen andA I Verkamo Discoveryoffrequentepisodesineventsequences DataMiningandKnowledgeDiscovery 1 259 289 1997 93 文献 序列模式挖掘方法 J Pei J Han H Pinto Q Chen U Dayal andM C Hsu PrefixSpan MiningSequentialPatternsEfficientlybyPrefix ProjectedPatternGrowth Proc 2001Int Conf onDataEngineering ICDE 01 Heidelberg Germany April2001 B Ozden S Ramaswamy andA Silberschatz Cyclicassociationrules ICDE 98 412 421 Orlando FL S Ramaswamy S Mahajan andA Silberschatz Onthediscoveryofinterestingpatternsinassociationrules VLDB 98 368 379 NewYork NY M J Zaki Efficientenumerationoffrequentsequences CIKM 98 Novermber1998 M N Garofalakis R Rastogi K Shim SPIRIT SequentialPatternMiningwithRegularExpressionConstraints VLDB1999 223 234 Edinburgh Scotland 94 文献 空间 多媒体 文本和Web数据库频繁模式挖掘 K Koperski J Han andG B Marchisio MiningSpatialandImageDatathroughProgressiveRefinementMethods Revueinternationaledegomatique EuropeanJournalofGISandSpatialAnalysis 9 4 425 440 1999 A K H Tung H Lu J Han andL Feng BreakingtheBarrierofTransactions MiningInter TransactionAssociationRules Proc 1999Int Conf onKnowledgeDiscoveryandDataMining KDD 99 SanDiego CA Aug 1999 pp 297 301 J Han G DongandY Yin EfficientMiningofPartialPeriodicPatternsinTimeSeriesDatabase Proc 1999Int Conf onDataEngineering ICDE 99 Sydney Australia March1999 pp 106 115 95 文献 空间 多媒体 文本和Web数据库频繁模式挖掘 H Lu L Feng andJ Han BeyondIntra TransactionAssociationAnalysis MiningMulti DimensionalInter TransactionAssociationRules ACMTransactionsonInformationSystems TOIS 00 18 4 423 454 2000 O R Zaiane M Xin J Han DiscoveringWebAccessPatternsandTrendsbyApplyingOLAPandDataMiningTechnologyonWebLogs Proc AdvancesinDigitalLibrariesConf ADL 98 SantaBarbara CA April1998 pp 19 29O R Zaiane J Han andH Zhu MiningRecurrentItemsinMultimediawithProgressiveResolutionRefinement Proc 2000Int Conf onDataEngineering ICDE 00 SanDiego CA Feb 2000 pp 461 470 96 文献 用于分类和数据方计算的频繁模式挖掘 K BeyerandR Ramakrishnan Bottom upcomputationofsparseandicebergcubes SIGMOD 99 359 370 Philadelphia PA June1999 M Fang N Shivakumar H Garcia Molina R Motwani andJ D Ullman Computingicebergqueriesefficiently VLDB 98 299 310 NewYork NY Aug 1998 J Han J Pei G Dong andK Wang ComputingIcebergDataCubeswithComplexMeasures Proc ACM SIGMOD 2001 SantaBarbara CA May2001 M Kamber J Han andJ Y Chiang Metarule guidedminingofmulti dimensionalassociationrulesusingdatacubes KDD 97 207 210 NewportBeach California K BeyerandR Ramakrishnan Bottom upcomputationofsparseandicebergcubes SIGMOD 99T Imielinski L Khachiyan andA Abdulghani Cubegrades Generalizingassociationrules TechnicalReport Aug 2000