大型数据库中的关联规则挖掘

《大型数据库中的关联规则挖掘》由会员分享，可在线阅读，更多相关《大型数据库中的关联规则挖掘（90页珍藏版）》请在金锄头文库上搜索。

1、大型数据库中的关联规则 挖掘什么是关联规则挖掘？n关联规则挖掘发现大量数据中项集之间有趣的 关联或相关联系。随着大量数据不停地收集和 存储，许多业界人士对于从他们的数据库中挖 掘关联规则越来越感兴趣。从大量商务事务记 录中发现n有趣的关联关系，可以帮助许多商务决策的制 定，如分类设计、交叉购物和贱卖分析。n关联规则挖掘的一个典型例子是购物篮分析。该过程 通过发现顾客放入其购物篮中不同商品（图6.1）之 间联系，分析顾客的购买习惯。通过了解哪些商品频 繁地被顾客同时购买，这种关联的发现可以帮助零售 商制定营销策略。n例如，在同一次去超级市场，如果顾客购买牛奶，他 也购买面包（和什么类型的面包）的

2、可能性有多大？ 通过帮助零售商有选择地经销和安排货架，这种信息 可以引导销售。例如，将牛奶和面包尽可能放近一些 ，可以进一步刺激一次去商店同时购买这些商品。“尿布与啤酒”典型关联分析案例n采用关联模型比较典型的案例是“尿布与啤酒” 的故事。在美国，一些年轻的父亲下班后经常 要到超市去买婴儿尿布，超市也因此发现了一 个规律，在购买婴儿尿布的年轻父亲们中，有 30%40%的人同时要买一些啤酒。超市随后 调整了货架的摆放，把尿布和啤酒放在一起， 明显增加了销售额。同样的，我们还可以根据 关联规则在商品销售方面做各种促销活动。购物篮分析n假定作为 AllElectronics 的分店经理，你想更加了解

3、 你的顾客的购物习惯。例如，你想知道“什么商品组 或集合顾客多半会在一次购物时同时购买？”为回答 你的问题，你可以在你的商店顾客事务零售数据上运 行购物篮分析。分析结果可以用于市场规划、广告策 划、分类设计。n例如，购物篮分析可以帮助经理设计不同的商店布局 。一种策略是：经常一块购买的商品可以放近一些， 以便进一步刺激这些商品一起销售。例如，如果顾客 购买计算机也倾向于同时购买财务软件，将硬件摆放 离软件陈列近一点，可能有助于增加二者的销售。n另一种策略是：将硬件和软件放在商店的两端 ，可能诱发买这些商品的顾客一路挑选其它商 品。例如，在决定购买一台很贵的计算机之后 ，去看软件陈列，购买财务软

4、件，路上可能看 到安全系统，可能会决定也买家庭安全系统。n购物篮分析也可以帮助零售商规划什么商品降 价出售。如果顾客趋向于同时购买计算机和打 印机，打印机降价出售可能既促使购买打印机 ，又促使购买计算机。购物篮分析n如果问题的全域是商店中所有商品的集合，则对每种 商品都可以用一个布尔量来表示该商品是否被顾客购 买，则每个购物篮都可以用一个布尔向量表示；而通 过分析布尔向量则可以得到商品被频繁关联或被同时 购买的模式，这些模式就可以用关联规则表示n关联规则的两个兴趣度度量q支持度q置信度6.1.2 基本概念n设 I = i1 , i2 ,., im 是项的集合。设任务相关 的数据D 是数据库事务

5、的集合，其中每个事务 T是项的集合，使得T I。每一个事务有一个 标识符，称作TID。设A 是一个项集，事务T 包含A当且仅当A T。n关联规则是形如A B 的蕴涵式，其中A I ，B I，并且A B = 。规则A B 在事务 集D 中成立，具有支持度s，其中s 是D 中事 务包含A B（即，A 和B 二者）的百分比。6.1.2 基本概念n它是概率P(A B)。规则A B 在事务集D 中具有置信度c，如果D 中包含A 的事务同时 也包含B的百分比是c。这是条件概率P(B|A)。nsupport (A B ) = P(A B) (6.2)nconfidence (A B ) = P(B|A) (

6、6.3)6.1.2 基本概念n同时满足最小支持度阈值(min_sup)和最小置信度阈 值(min_conf)的规则称作强规则。为方便计，我们用 0%和100%之间的值，而不是用0 到1 之间的值表示 支持度和置信度。n项的集合称为项集。包含k 个项的项集称为k-项集。 集合computer, financial_management_software是 一个2-项集。项集的出现频率是包含项集的事务数， 简称为项集的频率、支持计数或计数。n项集满足最小支持度min_sup，如果项集的出现频率 大于或等于min_sup 与D 中事务总数的乘积。如果项 集满足最小支持度，则称它为频繁项集。频繁k -

7、项集 的集合通常记作Lk。基本概念示例n项的集合 I=A,B,C,D,E,Fn每个事务T由事务标识符TID标识，它是项的集合 q比如：TID(2000)=A,B,Cn任务相关数据D是数据库事务的集合规则度量：支持度和置信度Customer buys diaperCustomer buys bothCustomer buys beern对所有满足最小支持度和 置信度的关联规则q支持度s是指事务集D中包 含 的百分比q置信度c是指D中包含A的事 务同时也包含B的百分比n假设最小支持度为50%， 最小置信度为50%，则有 如下关联规则qA C (50%, 66.6%)qC A (50%, 100%)

8、大型数据库关联规则挖掘 (1)n基本概念qk项集：包含k个项的集合n牛奶，面包，黄油是个3项集q项集的频率是指包含项集的事务数q如果项集的频率大于（最小支持度D中的事务总数 ），则称该项集为频繁项集大型数据库关联规则挖掘 (2)n大型数据库中的关联规则挖掘包含两个过程：q找出所有频繁项集n大部分的计算都集中在这一步q由频繁项集产生强关联规则n即满足最小支持度和最小置信度的规则关联规则挖掘分类 (1)n关联规则有多种分类：q根据规则中所处理的值类型n布尔关联规则n量化关联规则（规则描述的是量化的项或属性间的关联性）q根据规则中涉及的数据维n单维关联规则n（仅涉及buys这个维）n多维关联规则关联

9、规则挖掘分类 (2)q根据规则集所涉及的抽象层n单层关联规则n多层关联规则 （在不同的抽象层发现关联规则）q根据关联挖掘的各种扩充n挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）n挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超 集c，使得每个包含c的事务也包含c）n（最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频 繁项集）由事务数据库挖掘单维布尔关联规则n最简单的关联规则挖掘，即单维、单层、布尔关联规 则的挖掘。最小支持度 50% 最小置信度 50%n对规则A C，其支持度 =50%n置信度Apriori算法 (1)nApriori算法是挖掘布尔关联规则频繁项集的算法n

10、Apriori算法利用的是Apriori性质：频繁项集的所有非 空子集也必须是频繁的。q 模式不可能比A更频繁的出现qApriori算法是反单调的，即一个集合如果不能通过测试，则 该集合的所有超集也不能通过相同的测试。qApriori性质通过减少搜索空间，来提高频繁项集逐层产生的 效率Apriori算法 (2)nApriori算法利用频繁项集性质的先验知识（ prior knowledge），通过逐层搜索的迭代方法 ，即将k-项集用于探察(k+1)-项集，来穷尽数 据集中的所有频繁项集。q先找到频繁1-项集集合L1,然后用L1找到频繁2-项集 集合L2，接着用L2找L3，直到找不到频繁k-项集

11、， 找每个Lk需要一次数据库扫描。Apriori算法步骤nApriori算法由连接和剪枝两个步骤组成。n连接步：为找Lk，通过Lk - 1 与自己连接产生候选k-项集 的集合。该候选项集的集合记作Ck。n设l1 和l2 是Lk - 1 中的项集。记号lij表示li 的第j 项（例如 ，l1k-2表示l1 的倒数第3 项）。n为方便计，假定事务或项集中的项按字典次序排序。执 行连接 ；其中，Lk - 1 的元素是可连接的，如果它 们前(k-2)个项相同；即，Lk - 1 的元素l1 和l2 是可连接的 ，如果n(l1 1 = l2 1) (l1 2= l2 2) . (l1 k-2 = l2 k

12、-2) (l1 k-1 1)。n例如，当扫描数据库中每个事务，由C1 中的候选1- 项集产生频繁1-项集L1 时，我们可以对每个事务产生 所有的2-项集，将它们散列（即，映射）到散列表结 构的不同桶中，并增加对应的桶计数（图6.6）。n在散列表中对应的桶计数低于支持度阈值的2-项集不 可能是频繁2-项集，因而应当由候选项集中删除。n这种基于散列的技术可以大大压缩要考察的k-项集（ 特别是当k = 2 时）。6.2.3 提高Apriori的有效性6.2.3 提高Apriori的有效性n（2）事务压缩（压缩进一步迭代扫描的事务 数）：不包含任何k-项集的事务不可能包含任 何(k+1)-项集。n这样

13、，这种事务在其后的考虑时，可以加上标 记或删除，因为为产生j-项集(j k)，扫描数据 库时不再需要它们。6.2.3 提高Apriori的有效性n划分（为找候选项集划分数据）：可以使用划分技术 ，它只需要两次数据库扫描，以挖掘频繁项集（图 6.7）。n它包含两遍。在第I 遍，算法将D 中的事务划分成n 个非重叠的部分。n如果D 中事务的最小支持度阈值为min_sup，则每个 部分的最小支持度计数为min_sup该部分中事务数 。n对每一部分，找出该部分内的频繁项集。这些称作局 部频繁项集。该过程使用一种特殊的数据结构，对于 每个项集，记录包含项集中项的事务的TID。这使得 对于k = 1,2,

14、，找出所有的局部频繁k-项集只需要扫 描一次数据库。6.2.3 提高Apriori的有效性n局部频繁项集可能不是整个数据库 D 的频繁 项集。D 的任何频繁项集必须作为局部频繁项 集至少出现在一个部分中。n这样，所有的局部频繁项集作为D 的候选项集 。所有部分的频繁项集的集合形成D 的全局候 选项集。n在第II 遍，第二次扫描D，评估每个候选的实 际支持度，以确定全局频繁项集。每一部分的 大小和划分的数目这样确定，使得每一部分能 够放入内存，这样每遍只需要读一次。6.2.3 提高Apriori的有效性n（4）选样（在给定数据的一个子集挖掘）：选样方 法的基本思想是：选取给定数据库D 的随机样本

15、S， 然后，在S 而不是在D 中搜索频繁项集。用这种方法 ，我们牺牲了一些精度换取了有效性。样本S的大小 这样选取，使得可以在内存搜索S 中频繁项集；这样 ，总共只需要扫描一次S 中的事务。由于我们搜索S 中而不是 D 中的频繁项集，我们可能丢失一些全局频 繁项集。为减少这种可能性，我们使用比最小支持度 低的支持度阈值来找出局部于S 的频繁项集（记作LS ）。6.2.3 提高Apriori的有效性n然后，数据库的其余部分用于计算LS 中每个 项集的实际频繁度。有一种机制可以用来确定 是否所有的频繁项集都包含在LS 中。如果LS 实际包含了D 中的所有频繁项集，只需要扫描 一次D。否则，可以做第

16、二次扫描，以找出在 第一次扫描时遗漏的频繁项集。当效率最为重 要时，如计算密集的应用必须在不同的数据上 运行时，选样方法特别合适。6.2.3 提高Apriori的有效性n（5）动态项集计数（在扫描的不同点添加候选项集 ）：动态项集计数技术将数据库划分为标记开始点的 块。不象Apriori 仅在每次完整的数据库扫描之前确定 新的候选，在这种变形中，可以在任何开始点添加新 的候选项集。该技术动态地评估已被计数的所有项集 的支持度，如果一个项集的所有子集已被确定为频繁 的，则添加它作为新的候选。结果算法需要的数据库 扫描比Apriori 少。n其它变形涉及多层和多维关联规则挖掘，在本章的其 余部分讨论。涉及空间数据、时间序列数据和多媒体 数据的关联挖掘在第9 章讨论