关联规则分析

《关联规则分析》由会员分享，可在线阅读，更多相关《关联规则分析（54页珍藏版）》请在金锄头文库上搜索。

1、关联规则分析-大型数据库中关联规则挖掘 （概念描述、关联规则分析、分类、预测、聚类及孤立点分析等等） 用DMQL深入学习各种数据挖掘功能之二 什么是关联规则挖掘？ n关联规则挖掘： q从事务数据库，关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的、频繁出现的模式、 关联和相关性。 q主要的兴趣度度量指标有两个：置信度、支持度， 如果一个模式既满足支持度和置信度要求，则称这 个模式为强关联规则。 n应用： q购物篮分析、分类设计、捆绑销售和亏本销售分析 举例一： “尿布与啤酒”隐藏的典型关联分析案例 n采用关联模型比较典型的案例是“尿布与啤酒” 的故事。在美国，一些年轻的父亲下班后经常

2、 要到超市去买婴儿尿布，超市也因此发现了一 个规律，在购买婴儿尿布的年轻父亲们中，有 30%40%的人同时要买一些啤酒。超市随后 调整了货架的摆放，把尿布和啤酒放在一起， 明显增加了销售额。同样的，我们还可以根据 关联规则在商品销售方面做各种促销活动。 举例二：购物篮分析 n如果问题的全域是商店中所有商品的集合，则 对每种商品都可以用一个布尔量来表示该商品 是否被顾客购买，则每个购物篮都可以用一个 布尔向量表示（0001001100）；而通过分析布尔 向量则可以得到商品被频繁关联或被同时购买 的模式，这些模式就可以用关联规则表示。 思考：这种布尔购物篮有什么缺陷？影响挖掘结果吗？ n关联规则的

3、两个兴趣度度量 q支持度 q置信度 关联规则：基本概念 n给定： q项的集合（进行关联分析时问题的邻域所包含的项的集合）： I=i1,i2,.,in q任务相关数据D是数据库事务的集合，每个事务T则是项的集合， 使得 。例如每个事务就是购买的一个订单，每个订单记录的 是购买的哪些商品的信息，项的集合就是商店里所有商品种类的集 合，每个订单就是关于这个订单中购买的商品种类的集合。 这样 ，一个订单中购买商品种类总是被商场所有商品种类的集合所包含 。 q为了进行关联规则分析，我们将每个事务由事务标识符TID标识； qA,B为两个项集，事务T包含A当且仅当 ，一般分析两个项集 。 n则关联规则是如下

4、蕴涵式： q其中 并且 （空集），表示规则 在事务集D中成立，并且具有支持度s和置信度c 规则度量：支持度和置信度 Customer buys diaper Customer buys both Customer buys beer n对所有满足最小支持度和 置信度的关联规则 q支持度s是指事务集D中包 含 的百分比 q注意： 不是或，是模式间的连接，是union q置信度c是指D中包含A的 事务同时也包含B的百分比 n假设最小支持度为50%， 最小置信度为50%，则有 如下关联规则 qA C (50%, 66.6%) qC A (50%, 100%) 大型数据库关联规则挖掘中如何降低计 算复

5、杂度，提高关联规则效率 n基本概念 qk项集：包含k个项的集合 n牛奶，面包，黄油是个3项集 q项集的频率是指包含项集的事务数占总的事务数的百分比 q如果项集的频率大于（最小支持度D中的事务总数），则称 该项集为频繁项集（即满足最小支持度要求的项集） n大型数据库中的关联规则挖掘包含两个过程： q找出所有频繁项集 n涉及到大量数据读取和计算，所以大部分的计算都集中在这一 步，完成后找到的项集其本身已经满足了最小支持度规则 q由频繁项集产生强关联规则 n即满足最小支持度和最小置信度的规则 关联规则挖掘一个线路图 n关联规则有多种分类： q1、根据规则中所处理的值类型 n布尔关联规则（用布尔值01

6、表示） n量化的关联规则（对各个维进行量化衡量，不是简单 的01表示） q2、根据规则中设计的数据维 n单维关联规则 n多维关联规则（如上例，涉及到年龄、收入和购买三 个维的关联规则） q3、根据规则集所涉及的抽象层 n单层关联规则（关联规则表达时不涉及到概念分层） n多层关联规则（关联规则表达时涉及到概念分层，其 内部隐含有概念分层的关系） q4、根据关联挖掘的各种扩充 n挖掘最大的频繁模式（该模式的任何真超模式都是非 频繁的，意味着这个模式是最大的频繁模式） n挖掘频繁闭项集（一个项集c是频繁闭项集，如果不 存在其真超集c，使得每个包含c的事务也包含c， 意味着c的任何一个真超集都不可能是

7、频繁的，我们 就说c是频繁闭项集） 由事务数据库挖掘单维布尔关联规则 n最简单的关联规则挖掘，即单维、单层、布尔关联规 则的挖掘，而且我们的举例尽量不涉及概念分层。 首先挖掘频繁项集，其前提条件是： 最小支持度 50%，且最小置信度 50% n对规则A C，其支持度 =50% n置信度分A推导C和由C推导A，以A推导C为例： Apriori算法（计算大型数据库时挖掘关联规则的常用算法之一） nApriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项 集用于探察(k+1)-项集，来穷尽数据集中的所有频繁 项集（通过先验知识挖掘未知知识）。

8、 q先找到频繁1-项集集合（即单个项出现的频率）L1,然后用L1 找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k- 项集，找每个Lk需要一次数据库扫描，过程用到下面性质。 nApriori性质：频繁项集的所有非空子集也必须是频繁 的。（ 模式不可能比A更频繁的出现，即A与B 的非空交集不可能比A大，只能被包含） qApriori算法是反单调的，即一个集合如果不能通过测试，则 该集合的所有超集（注意超集与真超集概念是怎么样的？其 定义与子集相对！）也不能通过相同的测试。 Apriori算法步骤 nApriori算法由连接和剪枝两个步骤组成。 n连接：为了找Lk，通过Lk-1与自己连

9、接产生候选k-项集 的集合，该候选k项集记为Ck。 qLk-1中的两个元素L1和L2可以执行连接操作 的条件是 nCk是Lk的超集，即它的成员可能不是频繁的，但是所 有频繁的k-项集都在Ck中（为什么？）。因此可以通 过扫描数据库，通过计算每个k-项集的支持度来得到 Lk 。 q为了减少计算量，可以使用Apriori性质，即如果一个k-项集 的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直 接从Ck删除。 Apriori算法示例（如何挖掘满足最小支持度的关联的频繁项集 ） Database TDB 1st scan C1 L1 L2 C2 C2 2rd scan C3 L3 3

10、rd scan TidItems 10A, C, D 20B, C, E 30A, B, C, E 40B, E Itemsetsup A2 B3 C3 D1 E3 Itemsetsup A2 B3 C3 E3 Itemset A, B A, C A, E B, C B, E C, E Itemsetsup A, B1 A, C2 A, E1 B, C2 B, E3 C, E2 Itemsetsup A, C2 B, C2 B, E3 C, E2 Itemset B, C, E Itemsetsup B, C, E2 注意：我们假设最小支持度是50%，则最小支持计数是2个，则L1时删除D，则

11、任何包含D的超集其出现次数都不可能再超过1次，即Apriori性质所讲的内容。 剪 枝 结 果 连接！ 最终，挖掘出2项集中4个 和3项集中1个频繁项集！ C3 Itemset 不在 L2中 A,B,C A,B B,C,E 都在 A,C,E A,E 连接！ Apriori算法示例 使用Apiori性质由L2产生C3 n1 连接：至少有一个元素相同时，才能进行两两连接 qC3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E， 我们认为任何频繁的三项集都包含在此C3中！ n2使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的

12、 ，对候选项C3，我们可以删除其子集为非频繁的选项： qA,B,C的2项子集是A,B,A,C,B,C，其中A,B不是L2的元素， 所以删除这个选项； qA,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素 ，所以删除这个选项； qB,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是 L2的元素，因此保留这个选项。 n3这样，剪枝后得到C3=B,C,E Apriori算法示例 由频繁项集产生关联规则 n同时满足最小支持度和最小置信度的才是强关 联规则，从频繁项集产生的规则都满足支持度 要求，而其置信度则可由一下公式计算： n每个关联规则可由如下过程产生： q对于

13、每个频繁项集 l，产生 l 的所有非空子集； q对于每个非空子集s，如果 则输出规则“ ” Apriori算法用伪码表示其形式 ： n基本思路步骤为： 算法：Apriori使用根据候选生成的逐层迭代找出频繁项表 输入：与任务相关的事务数据库D；最小支持临界值min_sup 输出：D中的频繁项集L n具体代码，略。代码了解即可，但要掌握Apriori算法的计算思想。 提高Apriori算法的有效性(1) nApriori算法主要的挑战 q要对数据进行多次扫描； q会产生大量的候选项集； q对候选项集的支持度计算非常繁琐； n解决思路 q减少对数据的扫描次数； q缩小产生的候选项集； q改进对候选

14、项集的支持度计算方法 n方法1：基于hash表的项集计数 q将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可 以通过将桶中的项集计数跟最小支持计数相比较先淘汰一部分项集。可以 发现：同一个项集只能放在同一个桶中，虽然一个桶中可能包含多个项集 。如果桶内模式计数总数达不到最小计数要求，则这个桶中任意模式都达 不到计数要求，那么我们直接删掉该桶。 q通过hash表方法可以先排除一部分不满足条件的项集。 提高Apriori算法的有效性(2) n方法2：事务压缩（压缩进一步迭代的事务数） q不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的 计算中可以加上

15、标记或删除，因为连k项集都不满足要求，那么由k项集生 成的(k+1)项集肯定也不满足。如果一个子集是不频繁的，那么它的任何一 个真超子集也是不频繁的。 n方法3：划分（常用方法） q最大优势，显著提高效率：挖掘频繁项集只需两次数据扫描。 q基本思想是将一个大的数据段划分为n个小数据段（可以非均匀划分） qD中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。 q第一次扫描：将数据划分为多个部分并找到局部频繁项集（模式在这个段 的局部范围它出现的次数必须大于最小支持度*该段的总事务数） q第二次扫描：评估每个局部频繁项集的实际支持度，以确定这个局部频繁 项集是否是全局频繁项集 提高Apriori算法的有效性(3) n方法4：选样（因为我们是要挖掘大部分的频繁模式，而不是 必须挖掘全部有用模式，所以选样选的好的话会在保持一定精 确度基础上大大提高效率，然而选样仍会丢失部分频繁模式） q基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频 繁模式 q通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放 在内存中为宜，可以适当降低最小支持度来减少遗