6.3由事务数据库挖掘多层关联规则.ppt

6 3由事务数据库挖掘多层关联规则 组员 张弛薛宇 什么是关联规则挖掘 关联规则挖掘 从事务数据库 关系数据库和其他信息存储中的大量数据的项集之间发现有趣的 频繁出现的模式 关联和相关性 应用 购物篮分析 分类设计 捆绑销售等 对于许多应用 由于多维数据空间的稀疏性 在低层或原始层的数据项很难找出强关联规则 在较高的概念层发现的强关联规则可能提供普遍意义的知识 然而对于一个用户代表普遍意义的知识对于另一个用户可能是新颖的 这样 数据挖掘系统应当提供一种能力 在多个抽象层挖掘挖掘关联规则 并容易在不同的抽象空间转换 多层关联规则挖掘 多层关联规则 数据项中经常会形成概念分层底层的数据项 其支持度往往也较低这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度 All Computeraccessory software laptop financial mouse color printer computer desktop IBM edu Microsoft b w HP Sony wristpad Logitech TID Items T1 IBMD C Sonyb w T2 Ms edu Sw Ms fin Sw T3 Logi mouse Ergowaywristpad T4 IBMD C Ms Fin Sw T5 IBMD C Ergoway 多层关联规则 在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的通常 事务数据库中的数据也是根据维和概念分层来进行储存的这为从事务数据库中挖掘不同层次的关联规则提供了可能 在多个抽象层挖掘关联规则 并在不同的抽象层进行转化 是数据挖掘系统应该提供的能力 挖掘多层关联规则的方法 通常 多层关联规则的挖掘还是使用置信度 支持度框架 可以采用自顶向下策略由概念层1开始向下 到较低的更特定的概念层 对每个概念层的频繁项计算累加计数每一层的关联规则挖掘可以使用Apriori等多种方法概念分层中 一个节点的支持度肯定不小于该节点的任何子节点的支持度 先找高层的关联规则 computer printer 20 60 再找较低层的关联规则 laptop colorprinter 10 50 交叉层关联规则跨越概念层边界的规则Computer b wprinter使用较低层的最小支持度值 多层关联 一致支持度 一致支持度 对所有层都使用一致的最小支持度优点 搜索时容易采用优化策略 即一个项如果不满足支持度太高 将丢掉出现在较低抽象层中有意义的关联规则支持度太低 会在较高层产生太多的无兴趣的规则 多层关联 递减支持度 使用递减支持度 可以解决使用一致支持度时在最小支持度值上设定的困难递减支持度 在较低层使用递减的最小支持度每一层都有自己的一个独立的最小支持度抽象层越低 对应的最小支持度越小 min sup 5 min sup 5 min sup 3 多层关联 搜索策略 具有递减支持度的多层关联规则的搜索策略逐层独立 完全的宽度搜索 没有频繁项集的背景知识用于剪枝层交叉单项过滤 一个第i层的项被考察 当且仅当它在第 i 1 层的父节点是频繁的 computer laptopcomputer desktopcomputer min sup 12 层交叉k项集过滤 一个第i层的k项集被考察 当且仅当它在第 i 1 层的对应父节点k 项集是频繁的 P165 图6 15 computer printer laptopcomputer colorprinter desktopcomputer b wprinter support 7 support 1 support 2 support 1 support 3 min sup 5 min sup 2 多层关联 搜索策略 搜索策略比较逐层独立策略条件松 可能导致底层考察大量非频繁项层交叉k项集过滤策略限制太强 仅允许考察频繁k 项集的子女层交叉单项过滤策略是上述两者的折中 但仍可能丢失低层频繁项 图6 14 受控的层交叉单项过滤策略 层交叉单项过滤策略的改进版本设置一个层传递临界值 用于向较低层传递相对频繁的项 即如果满足层传递临界值 则允许考察不满足最小支持度临界值的项的子女用户对进一步控制多概念层上的挖掘过程有了更多的灵活性 同时减少无意义关联的考察和产生 min sup 12 level passage support 8 min sup 3 检查冗余的多层关联规则 概念分层在数据挖掘中是有用的 因为他们允许不同的抽象层的知识发现 如多层关联规则 挖掘多层关联规则时 由于项间的 祖先 关系 有些发现的规则将是冗余的desktopcomputer b wprinter sup 8 con 70 1 IBMdesktopcomputer b wprinter sup 2 con 72 2 上例中 我们说第一个规则是第二个规则的 祖先 如果根据规则的祖先 他的支持度和置信度都接近 期望 值 作为解释 规则1有70 置信度 8 支持度 并且大约四分之一的deskt