《数据仓库与数据挖掘》课件4关联规则挖掘理论和算法

n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第4章 关联规则挖掘理论和算法 内容提要 关联规则挖掘是数据挖掘研究的基 础 n关联规则挖掘（Association Rule Mining）是数据挖掘中研究 较早而且至今仍活跃的研究方法之一。 n最早是由Agrawal等人提出的（1993）。最初提出的动机是 针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发 现交易数据库（Transaction Database）中不同商品之间的联系规 则。 n关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论 、算法设计、算法的性能以及应用推广、并行关联规则挖掘以及 数量关联规则挖掘等。 n关联规则挖掘是数据挖掘的其他研究分支的基础。 事务数据库 n设I= i1，i2，im 是一个项目集合，事务数 据库D= t1，t2，tn 是由一系列具有唯一标识 TID的事务组成，每个事务ti（i=1，2，n）都对 应I上的一个子集。 n一个事务数据库可以用来刻画： n购物记录： I是全部物品集合， D是购物 清单，每个元组ti是一次购买物品的集合（它当然 是I的一个子集）。 n其它应用问题 支持度与频繁项目集 n定义（项目集的支持度）. 给定一个全局项目集I 和事务数据库D，一个项目集I1I在D上的支持度（ Support）是包含I1的事务在D中所占的百分比： support（ I1 ）=| t D | I1 t| / | D|。 n定义（频繁项目集）.给定全局项目集I和事务数 据库D ，D中所有满足用户指定的最小支持度（ Minsupport）的项目集，即大于或等于minsupport的 I的非空子集，称为频繁项目集（频集：Frequent Itemsets）。在频繁项目集中挑选出所有不被其他元 素包含的频繁项目集称为最大频繁项目集（最大频集 ： Maximum Frequent Itemsets）。 可信度与关联规则 n定义（关联规则与可信度）.给定一个全局项目 集I和事务数据库D，一个定义在I和D上的关联规则形 如I1I2，并且它的可信度或信任度或置信度（ Confidence）是指包含I1和I2的事务数与包含I1的事务 数之比，即： Confidence（I1I2）= P（ I1 | I2 ） Confidence（I1I2）= support（I1I2）/ support（I1 ）， 其中I1，I2I，I1I2=。 定义（强关联规则）. D在I上满足最小支持度和 最小信任度（Minconfidence）的关联规则称为强关 联规则（Strong Association Rule）。 关联规则挖掘基本过程 n关联规则挖掘问题可以划分成两个子问题： n1. 发现频繁项目集:通过用户给定 Minsupport ，寻找所有频繁项目集或者最大频繁 项目集。 n2生成关联规则:通过用户给定 Minconfidence ，在频繁项目集中，寻找关联规则 。 n第1个子问题是近年来关联规则挖掘算法研究的 重点。 n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 项目集格空间理论 定理1（ Appriori 属性1）. 如果项目集X 是频繁项目集 ，那么它的所有非空子集都是频繁项目集。 证明 设X是一个项目集，事务数据库T 中支持X 的元组数为s。对 X的任一非空子集为Y，设T中支持Y的元组数为s1。 根据项目集支持数的定义，很容易知道支持X 的元组一定支持Y， 所以s1 s，即support（Y） support（X）。 按假设：项目集X 是频繁项目集，即support(X) minsupport， 所以support（Y） support（X） minsupport，因此Y是频繁 项目集。 n定理2（ Appriori 属性2）.如果项目集X 是非频繁项目 集，那么它的所有超集都是非频繁项目集。证明 （略） 经典的发现频繁项目集算法 n1994年，Agrawal 等人提出了著名的Apriori 算 法。 n算法1 Apriori（发现频繁项目集） （1） L1 = large 1-itemsets; /所有1-项目频集 （2） FOR （k=2; Lk-1; k+） DO BEGIN （3） Ck=apriori-gen（Lk-1）; / Ck是k-候选集 （4） FOR all transactions tD DO BEGIN （5） Ct=subset（Ck，t）; / Ct是所有t包含的候选集元素 （6） FOR all candidates c Ct DO （7） c.count+; （8） END （9） Lk=cCk |c.countminsup_count （10） END （11） L= Lk; apriori-gen过程 n算法apriori中调用了apriori-gen（Lk-1），是为了 通过（k-1）-频集产生K-侯选集。 nhas_infrequent_subset（c， Lk-1） ，判断c是否加入到k-侯选集中。 （1） FOR all itemset p Lk-1 DO （2） FOR all itemset qLk-1 DO （3） IF p.item1=q.item1， ， p.itemk-2=q.itemk-2， p.itemk-1 1） THEN /generate rules with subsets of xm-1 as antecedents （7） genrules（lk， xm-1）; （8） END （9）END； Rule-generate算法例子 nMinconfidence=80% 序号lkxm-1confidencesupport规则（是否是强规则） 123523100%50%235（是） 2235267%50%235（否） 3235367%50%325（否） 42352567%50%253（否） 5235567%50%523（否） 623535100%50%352（是） n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 Apriori算法的性能瓶颈 nApriori作为经典的频繁项目集生成算法，在数据挖掘 中具有里程碑的作用。 nApriori算法有两个致命的性能瓶颈: 1多次扫描事务数据库，需要很大的I/O负 载 对每次k循环，侯选集Ck中的每个元素都必须通过扫 描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包 含10个项的话，那么就至少需要扫描事务数据库10遍。 2可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁 项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集 对时间和主存空间都是一种挑战。 n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 提高Apriori算法效率的技术 n一些算法虽然仍然遵循Apriori 属性，但是由于引入了相 关技术，在一定程度上改善了Apriori算法适应性和效率。 n主要的改进方法有： n基于数据分割（Partition）的方法：基本原理是“在 一个划分中的支持度小于最小支持度的k-项集不可能是全 局频繁的”。 n基于散列（Hash）的方法：基本原理是“在一个 hash桶内支持度小于最小支持度的k-项集不可能是全局频 繁的”。 n基于采样的方法：基本原理是“通过采样技术，评 估被采样的子集中，并依次来估计k-项集的全局频度”。 n其他：如，动态删除没有用的事务：“不包含任何Lk 的事务对未来的扫描结果不会产生影响，因而可以删除”。 基于数据分割的方法 n定理3-5 设数据集D被分割成分块D1， D2， ， Dn ，全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数minsup_counti （i=1，2，n），按 着如下方法生成：minsup_counti= minsup_count *|Di| /|D| 则所有的局部频繁项目集涵盖全局频繁项目集。 n作用： n1合理利用主存空间：数据分割将大数据集 分成小的块，为块内数据一次性导入主存提供机会。 n2支持并行挖掘算法：每个分块的局部频繁 项目集是独立生成的，因此提供了开发并行数据挖掘 算法的良好机制。 基于散列的方法 n1995，Park等发现寻找频繁项目集的主要计算 是在生成2-频繁项目集上。因此，Park等利用了这个 性质引入杂凑技术来改进产生2-频繁项目集的方法。 n 例子：桶地址 =（10x+y）mod 7； minsupport_count=3 TID Items 1 I1，I2，I5 2 I2，I4 3 I2，I3 4 I1，I2，I4 5 I1，I3 6 I2，I3 7 I1，I3 8 I1，I2，I3，I5 9 I1，I2，I3 桶地址 0 1 2 3 4 5 6 桶计数 2 2 4 2 2 4 4 桶内 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I3，I5 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 L2=I2，I3 ， I1，I2 ， I1，I3 n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 探索新的理论 n随着数据库容量的增大，重复访问 数据库（外存）将导致性能低下。因此 ，探索新的理论和算法来减少数据库的 扫描次数和侯选集空间占用，已经成为 近年来关联规则挖掘研究的热点之一。 n两个典型的方法： nClose算法 nFP-tree算法 Close算法对应的原理 n一个频繁闭合项目集的所有闭合子 集一定是频繁的；一个非频繁闭合项目 集的所有闭合超集一定是非频繁的。 n什么是一个闭合的项目集？ n一个项目集C是闭合的，当且仅当对 于在C中的任何元素，不可能在C中存在小 于或等于它的支持度的子集。 n例如，C1=AB3，ABC2是闭合的 ； C2=AB2，ABC2不是闭合的； Close算法的例子 n下面是Close算法作用到表4-1数据集的执行过程 （假如minsup_count=3）： n扫描数据库得到L1=(A,3), (B,5), (C,4), (D,3), (E,3)；相应关闭项目集为 Cl (A)=ABC,3，Cl (B)=B,5，Cl (C)=BC,4，Cl (D)=BD,3， Cl(E)=BE,3 ； nL2=(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)；相 应关闭集为C2 (AB)=ABC,3； nL3，L4，L5不用测，于是频繁大项集为ABC 。 样本数据库 TIDItemset 1 A，B，C，D 2B，C，E 3A，B，C，E 4B，D，E 5A，B，C，D FP-tree算法的基本原理 n进行2次数据库扫描：一次对所有1-项目的频度 排序；一次将数据库信息转变成紧缩内存结构。 n不使用侯选集，直接压缩数据库成一个频繁模式 树，通过频繁模式树可以直接得到频集。 FP-tree算法的基本原理 n基本步骤是： n两次扫描数据库，生成频繁模式树FP-Tree： n扫描数据库一次，得到所有1-项目的频度 排序表T； n依照T，再扫描数据库，得到FP-Tree。 n使用FP-Tree，生成频集： n为FP-tree中的每个节点生成条件模式库； n用条件模式库构造对应的条件FP-tree； n递归挖掘条件FP-trees同时增长其包含的频 繁集： n如果条件FP-tree只包含一个路 径，则直接生成所包含的频繁集。 生成频繁模式树FP-Tree n f:4c:1 b:1 p:1 b:1c:3 a:3 b:1m:2 p:2m:1 T Item frequency head f4 c4 a3 b3 m3 p3 min_support = 0.5 TIDOriginal Items (ordered) frequent items 100f, a, c, d, g, i, m, pf, c, a, m, p 200a, b, c, f, l, m, of, c, a, b, m 300 b, f, h, j, of, b 400 b, c, k, s, pc, b, p 500 a, f, c, e, l, p, m, nf, c, a, m, p 挖掘频集步骤1：生成条件模式库 n为每个节点， 寻找它的所有前缀路径并 记录其频度，形成CPB CPB itemcond. pattern base cf:3 afc:3 bfca:1, f:1, c:1 mfca:2, fcab:1 pfcam:2, cb:1 f:4c:1 b:1 p:1 b:1c:3 a:3 b:1m:2 p:2m:1 T Item frequency head f4 c4 a3 b3 m3 p3 挖掘频集步骤2：构造C-FP-tree n为每一个节点，通过FP-tree构造一个C-FP-tree n例如，m节点的C-FP-tree为： m-CPB: fca:2, fcab:1 f:3 c:3 a:3 m-conditional FP-tree f:4c:1 b:1 p:1 b:1c:3 a:3 b:1m:2 p:2m:1 T Item frequency head f4 c4 a3 b3 m3 p3 挖掘频集步骤3：递归构造C-FP- tree n f:3 c:3 a:3 m-conditional FP-tree f:3 c:3 am-conditional FP-tree f:3 cm-conditional FP-tree f:3 cam-conditional FP-tree 所有频集： m, fm, cm, am, fcm, fam, cam, fcam 单路径可以形成频集 n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 项目序列集概念 n“项目序列（Itemsequence）”来替代大多数文献 中出现的“项目集（Itemset）”可以简化挖掘的过程 。 n所谓项目序列是指项目集中的元素按着某种标准 进行有序排列。例如，我们可以按项目名称的字典顺 序排列，也可以象FP-Tree算法那样，按它们在数据 库中出现次数的多少降序排列。 n为了重复利用对数据库的扫描信息，把来自数据 库的信息组织成项目序列集（Set of itemsequences ）形式，并且对项目序列集格及其操作代数化。在这 样的代数系统下研究适应关联规则挖掘问题的操作算 子 . 项目序列集格 n定义3-5 一个项目序列集格空间可以用三元组（ I，S，p）来刻画，其中含义如下： n项目定义域I：I= i1，i2，im 为所有 项目集； n项目序列集变量集S：S中的每个项目序列 集变量形式为ISS=IS1，IS2，ISn，其中ISi （i=1，2，n）是定义在I上项目序列； n操作p ：关于S中的项目序列集变量的操 作集。 项目序列集格 n定义3-6（项目序列集间（上）的属于（）、 包含（）、并（）、交（）、差（）等操作 和普通的集合操作相同。 n例子： 设ISS1=AB，CD和ISS2=ABCD ，AD是定义在I =A，B，C，D上的项目序列集 ，则ABISS1；ABISS2；ABISS1； ABISS2；ISS1ISS2=AB，CD，ABCD，AD ；ISS1ISS2= 。 项目序列集格上的亚操作 n定义3-7 设ISS1和ISS2是定义在I上的两个项目序列 集，IS是定义在I上的一个项目序列，定义如下操作： n亚属于（sub）： ISsub ISS1当且仅当 IS1ISS1使得ISIS1； n亚包含（sub）： ISS1subISS2当且仅当 IS1ISS1 IS1subISS2； n亚交（sub）：ISS1subISS2=IS | ISsubISS1 且ISsubISS2； n亚并（sub）：ISS1subISS2=IS | ISsubISS1或ISsubISS2。 n例如，对上面的例子，虽然AB ISS2中，但是AB sub ISS2。 基于项目序列集操作的关联规则挖掘算法 算法3-14 ISS-DM Algorithm 输入：数据库D 输出：最大频繁项目序列集ISS* （1）Input（minsup_count）； （2）ISS ; ISS* ； （3）FOR all ISD DO BEGIN /取D的一个项目序列IS （4） join（IS，ISS）； （5） make_fre（IS，ISS，ISS*）； （6）END （7）AnswerISS* njoin（IS，ISS）完成数据库中一个项目序列（元 组）加入项目序列集后，它及它的子项目序列的频度维护。 nmake_fre（IS，ISS，ISS*）从ISS挑选频繁的并 加入到ISS*。 ISS-DM例子 n 操作 ISISS频繁ISS*说明 初始 1 ABCD （ABCD，1） 2 BCE（ABCD，1），（BCE，1）BC 3 ABCE（ABCD，1），（BCE，1），（ABCE，1）ABC，BCE裁*BC;BCE 4 BDE（ABCD，1），（ABCE，1），（BDE，1）ABC，BCE， BD 5 ABCD（ABCD，2），（ABCE，1），（BDE，1） ABCD，BCE 裁*ABC;BD;ABCD Answ（ABCE，1），（BDE，1） ABCD，BCE n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 衡量关联规则挖掘结果的有效性 n应该从多种综合角度来考虑： n准确性：挖掘出的规则必须反映数据的实 际情况。 n实用性：挖掘出的规则必须是简洁可用的 。 n新颖性：挖掘出的关联规则可以为用户提 供新的有价值信息。 n改善关联规则挖掘质量是一件很困难的工作。必 须采用事先预防、过程控制以及事后评估等多种方法 ，其中使用合适的机制（如约束），让用户主动参与 挖掘工作是解决问题的关键。粗略地说，可以在用户 主观和系统客观两个层面上考虑关联规则挖掘的质量 问题。 用户主观层面 n一个规则的有用与否最终取决于用户的感觉。 n用户可以在不同的层面、不同的阶段、使用不同 的方法来主观设定约束条件。 n从被约束的对象来看，有下面几种常用的方法： n知识类型的约束：针对应用问题选择有效 的知识表达模式。例如，如果一个商业企业希望 根据客户特点进行有针对性地销售，那么使用分 类或聚类形式可以帮助用户形成客户群。 用户主观层面 n数据的约束：对数据的约束可以起到减少 数据挖掘算法所用的数据量、提高数据质量等作 用。 n维/层次约束：限制聚焦的维数或粒度层 次，也可以针对不同的维设置约束条件。 n知识内容的约束：可以通过限定要挖掘的 知识的内容，如指定单价大于10的交易项目，减 少探索的代价和加快知识的形成过程。 n针对具体知识类型的约束：针对具体知识 类型的进行约束挖掘形式和实现机制的研究。 系统客观层面 n使用“支持度-可信度” 的关联规则挖掘度量框架 ，在客观上也可能出现与事实不相符的结果。例如， “计算机游戏和录象产品是负相关的”问题。 n重新考虑关联规则的客观度量问题。例如， nBrin等考虑的蕴涵规则（Implication Rule ）； nChen等给出的R-兴趣（R-Interesting）规 则度量方法等。 n这些工作都期望通过引入新的度量机制和 重新认识关联规则的系统客观性来改善挖掘质量 。 n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 内容提要 约束在数据挖掘中的作用 n聚焦挖掘任务，提高挖掘效率：利用约束，可以 把具体的挖掘任务转换成对系统工作的控制，从而使 挖掘工作按着我们期望的方向发展。约束的使用可以 在知识发现的任何阶段进行，快速聚焦挖掘任务，进 而提高挖掘效率。 n保证挖掘的精确性：挖掘结果的精确性，不仅体 现在它的可信程度，而且取决于它的有用性。约束的 使用可以帮助我们发现问题，并及时加以调整，使知 识发现的各个阶段按着正确的方向发展。 约束在数据挖掘中的作用 n控制系统的使用规模：数据挖掘和知识发 现应用最常犯的错误就是无限制的扩大规模 。约束数据挖掘的思想为系统的增量式扩充 提供条件。当基本的原则和目标确定后，可 以把一些有待验证和优化的问题以约束参数 的形式交互式输入，通过实验找到最佳值。 约束的类型 n一些常用的名词和符号： n定义3-12 设项目集I=i1，i2，im，事务数据 库T=，模式S和S*都是项目集I的子集，如果S*S ，则称S*是S的子模式（Subpattern）；S是S*的超模式（ Superpattern）。 n定义3-13 一个约束C是作用于项目集I的幂集（ Powerset）上的谓词。约束C对于一个模式S的结果用布尔变 量来表示，即C（S）=True/False：C（S）=True表示S满足 约束条件；C（S）=False表示S不满足约束条件。 n定义3-14 对于被讨论的项目集I，满意模式集（ Satisfying Pattern Set），记为SATc（I）是指那些完全满足 约束C的项目集的全体。 约束的类型 n将约束条件用于频繁集的查询无非是找出 那些满足C的频繁集。 n约束的常见类型有： n单调性约束（Monotone Constraint）； n反单调性约束（Anti-monotone Constraint ）； n可转变的约束（Convertibale Constraint） ； n简洁性约束（Succinct Constraint）。 单调性约束 n定义3-15 所谓一个约束Cm是单调 性的约束是指满足Cm的任何项目集S的 超集也能满足 Cm。 n例如，“sum（price）100”的约束 是一个单调性约束。因为一个项目集满 足这个条件，那么它的超集也一定满足 这个条件。现实世界中有许多条件满足 这样的性质，如“属于”、“包含”等。 反单调性约束 n定义3-16 约束Ca是反单调的是指对 于任意给定的不满足Ca的项目集S，不 存在S的超集能够满足Ca。 n例如，“sum（price）C（S* ）。 n例如，对于Avg（S） v，令I为一组以 升序排列数值的项目集。如果 S满足约束， 那么S的后缀S*也满足 avg（S*）v。 可转变的约束 n定义3-18 如果一个约束C满足下面的条 件，那么称它是单调可转变的： nC（S）既不是单调性约束，也不是反单调 性约束； n若存在顺序R，使得经R排序后的I满足： 任给 S*suffix_S，有C（S*）=C（S）。 n例如，对于Avg（S） v，令I为一组以降 序排列数值的项目集。如果S的后缀S*满足约 束avg（S*） v，那么S也满足 avg（S）v 。 简洁性约束 n定义3-19 一个项目子集Is 是一个简 洁集（Succinct Set），如果对于某些选 择性谓词p，该项目子集能够表示为p （I）的形式，其中是选择符。 n如果一个约束是简洁的，那么我们 就可以直接使用SQL查询来得到满足条 件的集合。在挖掘的不同阶段可以尽量 尝试简洁性的约束，这样可以避免不必 要的测试。 简洁性约束 n定义3-20 SP2I 是一个强简洁集 （Succinct Power Set），如果有一个 数目不变的简洁集I1，I2，IkI，SP 能够用I1，I2，Ik的并、差运算表示 出来。 n定义3-21 约束Cs是简洁的，假如 SATCs（I）是一个强简洁集。 约束之间的关系 n Succinctness Anti-monotonicityMonotonicity Convertible constraints Inconvertible constraints n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题 nApriori的改进算法 n对项目集格空间理论的发展 n基于项目序列集操作的关联规则挖掘算法 n改善关联规则挖掘质量问题 n约束数据挖掘问题 n关联规则挖掘中的一些更深入的问题 n数量关联规则挖掘方法 第5章 关联规则挖掘理论和算法 多层次关联规则挖掘 n根据规则中涉及到的层次，多层次关联规则可以 分为： n同层关联规则：如果一个关联规则对应的项目是同 一个粒度层次，那么它是同层关联规则。 n层间关联规则：如果在不同的粒度层次上考虑问题 ，那么可能得到的是层间关联规则。 n多层次关联规则挖掘的度量方法可以沿用 “支持 度-可信度”的框架。不过，多层次关联规则挖掘有两 种基本的设置支持度的策略： 多层次关联规则挖掘 n统一的最小支持度：算法实现容易，而且很容易支 持层间的关联规则生成。但是弊端也是显然的： n不同层次可能考虑问题的精度不同、面向的用户群不 同。 n对于一些用户，可能觉得支持度太小，产生了过多不 感兴趣的规则。而对于另外的用户来说，又认为支持度太大， 有用信息丢失过多。 n不同层次使用不同的最小支持度：每个层次都有自 己的最小支持度。较低层次的最小支持度相对较小，而较高 层次的最小支持度相对较大。这种方法增加了挖掘的灵活性 。但是，也留下了许多相关问题需要解决： n首先，不同层次间的支持度应该有所关联，只有正确 地刻画这种联系或找到转换方法，才能使生成的关联规则相对 客观。 n其次，由于具有不同的支持度，层间的关联规则挖掘 也是必须解决的问题。例如，有人提出层间关联规则应该根据 较低层次的最小支持度来定。 多维关联规则挖掘 n多维关联规则可以有： n维内的关联规则：例如，“年龄（X， 2030）职业（X，学生）=购买（X，笔记本 电脑）”。这里我们就涉及到三个维：年龄、职业 、购买。 n混合维关联规则：这类规则允许同一个维 重复出现。例如，“年龄（X，2030）购买（X ，笔记本电脑） = 购买（X，打印机）”。由于 同一个维“购买”在规则中重复出现，因此为挖掘带 来难度。但是，这类规则更具有普遍性，具有更 好的应用价值，因此近年来得到普遍关注。 数量关联数规则的分类 n根据数值属性的处理方式，主要技术有： n数值属性的静态离散化：数值属性使用预 定义的概念分层，在挖掘之前进行离散化，数值 属性的值用相应的区间来替代。例如，income的 概念分层可以用于用区间值“020K”，“2130K” ，“3140K”来替换属性原来的数值。 n数值属性的动态离散化：动态离散化过程 需要考虑数据的关联和程度，使用相应的度量手 段，如数据点之间的距离，来跟踪数据的语意。 n基于特定的技术进行离散化：常用的方法 是根据数据的分布，将数值属性离散化到“箱（Bin ）”。由于这些箱可能在挖掘过程中进一步组合， 因此有动态的特征。离散化的动态体现在分区合 并等过程中。三种常用的分箱策略是等宽分箱、 等深分箱和基于同质的分箱。 数量关联数规则的分类 n根据使用的规则模板，主要技术有： n复杂的挖掘模板形式：类似于“数值属性分类属性 数值属性分类属性”这样的规则。例如， sex=femaleage20，30 =wages$5，$10。这类规则 较为复杂，是一般性的数量关联规则。 n分类规则的挖掘模板：简单的挖掘模板形式 类似于“数值属性分类属性分类属性”这样的规则 。例如，smoke=Yesage60，80 =heart- desease=Yes。此类规则的左端通常表示的是数据库 的的几个连续或分类属性，右端则是一个预定义的类 。这样的模板很适合用于分类规则的挖掘。 n其他挖掘模板：例如，挖掘模板形式类似于“ 分类属性数值属性分类属性”这样的规则。这和第 二类规则形式恰好相反，但对有些问题，这类规则非 常有意义。 数量关联规则挖掘的一般步 骤 n以Boolean关联规则算法及其理论为基础，是解决数 量关联规则的挖掘问题的最有效途径之一。较典型的数量 关联规则挖掘的主要步骤有： n1对每个数值属性进行离散化：选取或设计 合适的离散化算法，对数据库中的所有数值属性进行离 散化。 n2离散区间整数化：对分类属性或数值属性 的离散区间，将其值映射成连续的整数标识。这样做的 目的是使数据归整以利于挖掘。 n3在离散化的数据集上生成频繁项目集：此 步和前面介绍的生成频繁项目集的步骤类似。 n4产生关联规则：和前面介绍的方法类似。 n5确定感兴趣的 （Interesting）关联规则 作为输出 数值属性离散化问题 n数值属性离散化是关键问题，处理不当会 带来如下问题： n过小置信度问题：若区间的数目过少，则 支持区间的元组数目增加，包含区间的强项目集 的支持度上升，但在强项目集的子集支持度不变 的情况下，将导致右端包含该子集的规则置信度 下降，若不能达到置信度阈值，就会造成信息丢 失。 n过小支持度问题：划分的区间数目过多， 则区间的支持度下降，不能有效的生成期望的频 繁项目集。 数值属性离散化问题 n离散化可能会把本来很紧密的数据分割开 来，结果就会生成大量没有意义的无用规则。 n离散化会带来区间的组合爆炸。假设某数 值属性划分成n个基区间，由于相邻的两个连续属 性又可以合并生成更大的区间，这样反反复复的 合并，最终的区间数目就有O（nn）个。所以具体 离散化过程中必须有一种停机条件，当区间合并 到一定程