《关联规则分析》由会员分享,可在线阅读,更多相关《关联规则分析(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通过牺牲精确度来减少算法开销,为了提高效率,样本大小应该以可以放 在内存中为宜,可以适当降低最小支持度来减少遗