北京大学信息管理系《数据挖掘导论》讲义第三章关联规则挖掘北京大学信息管理系2016年秋
北京大学信息管理系 《数据挖掘导论》讲义 第三章 关联规则挖掘 北京大学信息管理系 2016 年秋
北京大学信息管理系数据挖掘导论第三章目录第三章关联规则挖掘33.1相关概念33.1.1购物篮分析33.1.2支持度、置信度与关联规则3.1.3关联规则挖掘43.2频繁项集的产生53.2.1格结构53.2.2Apriori性质63.2.2Apriori算法63.3规则的产生73.3.1由频繁项集产生关联规则，73.3.2基于置信度的剪枝83.3.2提高Apriori方法的有效性..83.4关联规则挖掘在图情领域中的应用103.4.1在信息检索中的应用.10.113.4.2在图书馆服务中的应用.3.4.3在学科关系中的应用11.123.5关联规则挖掘的案例与软件操作3.5.1关联规则挖掘（SPSSModeler）..123.5.2关联规则挖掘（R语言）.18参考文献，242
北京大学信息管理系 数据挖掘导论 第三章 2 目录 第三章 关联规则挖掘. 3 3.1 相关概念. 3 3.1.1 购物篮分析.3 3.1.2 支持度、置信度与关联规则.4 3.1.3 关联规则挖掘.4 3.2 频繁项集的产生. 5 3.2.1 格结构.5 3.2.2 Apriori 性质.6 3.2.2 Apriori 算法.6 3.3 规则的产生. 7 3.3.1 由频繁项集产生关联规则.7 3.3.2 基于置信度的剪枝.8 3.3.2 提高 Apriori 方法的有效性.8 3.4 关联规则挖掘在图情领域中的应用. 10 3.4.1 在信息检索中的应用.10 3.4.2 在图书馆服务中的应用.11 3.4.3 在学科关系中的应用.11 3.5 关联规则挖掘的案例与软件操作. 12 3.5.1 关联规则挖掘（SPSS Modeler） .12 3.5.2 关联规则挖掘（R 语言）.18 参考文献. 24
北京大学信息管理系数据挖掘导论第三章第三章关联规则挖掘现实生活中，许多企业在运营的过程中积累了大量的数据。例如，某超市的收银台每天都能收集大量的顾客购物数据。假设你是某超市的销售经理，正在与一位刚在超市购买了微波炉和厨具的顾客交谈，你应该向他推荐什么产品？这时候如果知道其他同时购买微波炉和厨具的顾客又频繁购买什么产品，将会对你的推荐起很大帮助。本章主要介绍一种关联分析（associationanalysis）的方法，用于发现隐藏在大型数据集中有意义的联系。3.1相关概念本节通过一个超市购物篮的迷你数据集来解释关联规则挖掘的基本概念。3.1.1购物篮分析“啤酒与尿布的故事是关联规则挖掘的一个经典案例。超市拥有大量的商品，如牛奶、面包等，顾客将所购买的商品放入到自已的购物篮中，即为购物篮事务（marketbaskettransaction)。例3.1购物篮分析。表3-1给出了一个超市购物篮的例子，其中每一行对应一个事务，包含一个唯一标识TID和某顾客购买商品的集合。超市管理者可通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯（例如，哪些物品经常被顾客购买：同一次购买中，哪些商品经常会被一起购买：一般用户的购买过程中是否存在一定的购买时间序列等），以实现利润最大化。表3-1购物篮事务的例子TID项集1{面包，牛奶2(面包，尿布，啤酒，鸡蛋)3（牛奶，尿布，啤酒，可乐）4(面包，牛奶，尿布，啤酒）5(面包，牛奶，尿布，可乐)购物篮数据还可以用二元形式表示。表3-1对应的购物篮事务可表示为：表3-2购物篮事务的二元表示TID面包牛奶尿布啤酒鸡蛋可乐11100002101101030111141100115111001其中，每行对应一个事务，每列对应一个项。项用二元变量表示，如果项在事务中出现，则它的主值为1，否则为0从以上购物篮数据中可以看出许多购买尿布的顾客也购买啤酒，因此可提取出如下规则：（尿布）一→啤酒）。该规则表明尿布和啤酒的销售之间存在很强的联系，超市管理者可以使用这类规则于营销规划、广告策划或超市布局中。例如用该规则指导超市布局，一种策略是将啤酒和尿布相邻摆放，以便进一步刺激二者的同时销售；另一种策略是把啤酒和尿布摆放在3
北京大学信息管理系 数据挖掘导论 第三章 3 第三章 关联规则挖掘 现实生活中，许多企业在运营的过程中积累了大量的数据。例如，某超市的收银台每天 都能收集大量的顾客购物数据。假设你是某超市的销售经理，正在与一位刚在超市购买了微 波炉和厨具的顾客交谈，你应该向他推荐什么产品？这时候如果知道其他同时购买微波炉和 厨具的顾客又频繁购买什么产品，将会对你的推荐起很大帮助。 本章主要介绍一种关联分析（association analysis）的方法，用于发现隐藏在大型数据集 中有意义的联系。 3.1 相关概念 本节通过一个超市购物篮的迷你数据集来解释关联规则挖掘的基本概念。 3.1.1 购物篮分析 “啤酒与尿布”的故事是关联规则挖掘的一个经典案例。超市拥有大量的商品，如牛奶、 面包等，顾客将所购买的商品放入到自己的购物篮中，即为购物篮事务（market basket transaction）。 例 3.1 购物篮分析。表 3-1 给出了一个超市购物篮的例子，其中每一行对应一个事务， 包含一个唯一标识 TID 和某顾客购买商品的集合。超市管理者可通过发现顾客放入购物篮 中的不同商品之间的联系，分析顾客的购买习惯（例如，哪些物品经常被顾客购买；同一次 购买中，哪些商品经常会被一起购买；一般用户的购买过程中是否存在一定的购买时间序列 等），以实现利润最大化。 表 3-1 购物篮事务的例子 TID 项集 1 {面包，牛奶} 2 {面包，尿布，啤酒，鸡蛋} 3 {牛奶，尿布，啤酒，可乐} 4 {面包，牛奶，尿布，啤酒} 5 {面包，牛奶，尿布，可乐} 购物篮数据还可以用二元形式表示。表 3-1 对应的购物篮事务可表示为： 表 3-2 购物篮事务的二元表示 TID 面包 牛奶 尿布 啤酒 鸡蛋 可乐 1 1 1 0 0 0 0 2 1 0 1 1 1 0 3 0 1 1 1 0 1 4 1 1 1 1 0 0 5 1 1 1 0 0 1 其中，每行对应一个事务，每列对应一个项。项用二元变量表示，如果项在事务中出现， 则它的主值为 1，否则为 0。 从以上购物篮数据中可以看出许多购买尿布的顾客也购买啤酒，因此可提取出如下规则： {尿布}→{啤酒}。该规则表明尿布和啤酒的销售之间存在很强的联系，超市管理者可以使用 这类规则于营销规划、广告策划或超市布局中。例如用该规则指导超市布局，一种策略是将 啤酒和尿布相邻摆放，以便进一步刺激二者的同时销售；另一种策略是把啤酒和尿布摆放在
北京大学信息管理系数据挖掘导论第三章超市的两端，诱发买这两种商品的顾客一路挑选其它商品。3.1.2支持度、置信度与关联规则设I={ii,i2.,in)是购物篮数据中所有项的集合，T-{ti,t2.,tm)是所有事务的集合。在例3.1中，I=（面包，牛奶，尿布，啤酒，鸡蛋，可乐），其中（面包）、（牛奶）等为项（item）；T={t, t2, t3, t4, ts] 。事务t（transaction）是项的集合（tSl)，每一个事务都对应一个唯一的标识（如交易号，记作TID)；事务t的宽度定义为事务t中包含的项的个数：如果一个项集包含k个项，则称其为k项集，如例3.1中t事务的项集为面包，牛奶），是一个2项集。若项集X是I中一些项的集合，且X是事务t的子集，则称事务t包含项集X。例3.1中，t2事务包含项集（啤酒，尿布），但不包含项集（面包，牛奶）。项集的一个重要性质是它的支持度计数，为某项集的出现频率，即包含该项集的事务个数。如例3.1中，（面包，牛奶)项集的支持度计数为3，因为该项集同时出现在了t，t4和ts三个事务中。关联规则（associationrule）是所有形如X→Y的蕴涵式，其中X和Y是不相交的项集。关联规则的有趣性可以用支持度与置信度来度量，支持度（support）用来描述给定项集的频繁程度，置信度（confidence）用来确定Y在包含X的事务中出现的频繁程度。二者的度量公式如下。·支持度support(X= Y) = Support.count (XuY)m其中support_count（XUY）为项集(X,Y)的支持度计数，即包含项X和Y的交易数；m为总交易数。置信度·support_count(XuY)confidence(X=→Y)=support_count(x)support_count（X）为购买商品X的交易数。支持度可反映规则的有用性，因为低支持度的规则可能只是偶尔出现。从超市管理者的角度去看，顾客很少同时购买的商品可能对促销无益，因此支持度通常用来删去那些无意义的规则。置信度可反映规则的确定性，如果顾客在购买X时一定会购买B，那么就可以将这两种商品进行捆绑销售。关联规则的基本表现形式如下：前提条件→结论[支持度，置信度]以上节提到的购物篮数据为例，可得到如下关联规则：规则一：（尿布→[啤酒[60%,75%]规则二：（牛奶，尿布}一→[啤酒[40%67%]规则一指60%的人同时购买了尿布和啤酒，买了尿布的人中有75%的人同时购买了啤酒；规则二指40%的人同时购买了牛奶、尿布和啤酒，同时买了牛奶和尿布的人中有67%的人还购买了啤酒。3.1.3关联规则挖掘关联规则挖掘就是发现大量数据中项集之间有趣的关联。一般情况下，有趣的关联规则是指满足最小支持度阅值和最小置信度值的关联规则。这些阅值可以由用户或某领域专家来设定。4
北京大学信息管理系 数据挖掘导论 第三章 4 超市的两端，诱发买这两种商品的顾客一路挑选其它商品。 3.1.2 支持度、置信度与关联规则 设 I ={i1 , i2 ,., in}是购物篮数据中所有项的集合，T={t1, t2,.,tm}是所有事务的集合。在 例 3.1 中，I={面包，牛奶，尿布，啤酒，鸡蛋，可乐}，其中{面包}、{牛奶}等为项（item）； T={t1, t2, t3, t4, t5}。 事务 （t transaction）是项的集合（t ⊆I），每一个事务都对应一个唯一的标识（如交易号， 记作 TID）；事务 t 的宽度定义为事务 t 中包含的项的个数；如果一个项集包含 k 个项，则称 其为 k 项集，如例 3.1 中 t1 事务的项集为{面包，牛奶}，是一个 2 项集。 若项集 X 是 I 中一些项的集合，且 X 是事务 t 的子集，则称事务 t 包含项集 X。例 3.1 中，t2 事务包含项集{啤酒，尿布}，但不包含项集{面包，牛奶}。 项集的一个重要性质是它的支持度计数，为某项集的出现频率，即包含该项集的事务个 数。如例 3.1 中，{面包，牛奶}项集的支持度计数为 3，因为该项集同时出现在了 t1，t4和 t5 三个事务中。 关联规则（association rule）是所有形如 X→Y 的蕴涵式，其中 X 和 Y 是不相交的项集。 关联规则的有趣性可以用支持度与置信度来度量，支持度（support）用来描述给定项集的频 繁程度，置信度（confidence）用来确定 Y 在包含 X 的事务中出现的频繁程度。二者的度量 公式如下。 支持度 support(X ⇒ Y) = support_count（X ∪ Y） m 其中 support_count（X∪Y）为项集{X, Y}的支持度计数，即包含项 X 和 Y 的交易数； m 为总交易数。 置信度 confidence(X ⇒ Y) = support_count（X ∪ Y） support_count（X） support_count（X）为购买商品 X 的交易数。 支持度可反映规则的有用性，因为低支持度的规则可能只是偶尔出现。从超市管理者的 角度去看，顾客很少同时购买的商品可能对促销无益，因此支持度通常用来删去那些无意义 的规则。置信度可反映规则的确定性，如果顾客在购买 X 时一定会购买 B，那么就可以将这 两种商品进行捆绑销售。 关联规则的基本表现形式如下： 前提条件→结论[支持度，置信度] 以上节提到的购物篮数据为例，可得到如下关联规则： 规则一：{尿布}→{啤酒} [60%, 75%] 规则二：{牛奶，尿布}→{啤酒} [40%, 67%] 规则一指 60%的人同时购买了尿布和啤酒，买了尿布的人中有 75%的人同时购买了啤 酒；规则二指 40%的人同时购买了牛奶、尿布和啤酒，同时买了牛奶和尿布的人中有 67%的 人还购买了啤酒。 3.1.3 关联规则挖掘 关联规则挖掘就是发现大量数据中项集之间有趣的关联。一般情况下，有趣的关联规则 是指满足最小支持度阈值和最小置信度阈值的关联规则。这些阈值可以由用户或某领域专家 来设定
北京大学信息管理系数据挖掘导论第三章挖掘关联规则的一个原始方法是计算每个可能规则的支持度与置信度，但该方法的代价太高，达到指数级：具体地说，从包含d个项的数据集中提取的可能的规则总数为R=3d2(d+1)+1。即使对于例3.1中的小数据集，这种方法也需要计算602条规则的支持度和置信度。如果设定最小支持度阅值为20%，最小置信度为50%，则80%以上的规则都将被丢弃，使得大部分计算是无用的开销。为了避免进行不必要的计算，应事先对规则剪枝。提高关联规则挖掘算法性能的第一步是拆分支持度和置信度，由二者的度量公式可看出，规则X→Y的支持度仅依赖于其对应项集XUY的支持度。例如，下面的规则有相同的支持度，因为它们都涉及到同一个项集啤酒，尿布，牛奶！。如果该项集是非频繁的，则可以立即剪掉这6个候选规则，而不必计算它们的置信度。(啤酒，尿布)一→{牛奶)，(啤酒，牛奶)一→（尿布)（尿布，牛奶)→（啤酒），（啤酒）→（尿布，牛奶）（牛奶)→啤酒，尿布），（尿布）→啤酒，牛奶）因此，大多数关联规则挖掘算法采用的是一种两步的策略：（1）频繁项集的产生：其目标是发现满足最小支持度值的所有项集，这些项集称作频繁项集（frequentitemset）。（2）规则的产生：其目标是从上步所产生的频繁项集中提取满足最小置信度的规则。关联规则挖掘所花费的时间主要是在生成频繁项集上，因为找出的频繁项集往往不会很多，利用频繁项集生成规则也就不会花太多的时间，而生成频繁项集需要测试很多的备选项集，如果不加优化，所需的时间是0(2n)。3.2频繁项集的产生3.2.1格结构图3-1为项集I={a,b,c,d,e)的格结构（latticestructure），用来枚举所有可能的项集。(nul)DB(A)(℃)(EI-中Z1(AD)(AE)BO(BD)(BE)(CD)(CE)AB(AC)DE(ABD(ACD)(ACE)(BCD)(BCE)(BDE)(ABC)(ABE)(ADE)(CDE(ABCE)ABCD）（ABDE)）（ACDE）（BCDE）(ABCDE)图3-1项集的格结构5
北京大学信息管理系 数据挖掘导论 第三章 5 挖掘关联规则的一个原始方法是计算每个可能规则的支持度与置信度，但该方法的代价 太高，达到指数级；具体地说，从包含 d 个项的数据集中提取的可能的规则总数为 R=3d - 2 (d+1)+1。即使对于例 3.1 中的小数据集，这种方法也需要计算 602 条规则的支持度和置信度。 如果设定最小支持度阈值为 20%，最小置信度为 50%，则 80%以上的规则都将被丢弃，使 得大部分计算是无用的开销。为了避免进行不必要的计算，应事先对规则剪枝。 提高关联规则挖掘算法性能的第一步是拆分支持度和置信度，由二者的度量公式可看出， 规则 X→Y 的支持度仅依赖于其对应项集 X∪Y 的支持度。例如，下面的规则有相同的支持 度，因为它们都涉及到同一个项集{啤酒，尿布，牛奶}。如果该项集是非频繁的，则可以立 即剪掉这 6 个候选规则，而不必计算它们的置信度。 {啤酒，尿布}→{牛奶}，{啤酒，牛奶}→{尿布} {尿布，牛奶}→{啤酒}，{啤酒}→{尿布，牛奶} {牛奶}→{啤酒，尿布}，{尿布}→{啤酒，牛奶} 因此，大多数关联规则挖掘算法采用的是一种两步的策略： （1）频繁项集的产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称作 频繁项集（frequent itemset）。 （2）规则的产生：其目标是从上步所产生的频繁项集中提取满足最小置信度的规则。 关联规则挖掘所花费的时间主要是在生成频繁项集上，因为找出的频繁项集往往不会很 多，利用频繁项集生成规则也就不会花太多的时间，而生成频繁项集需要测试很多的备选项 集，如果不加优化，所需的时间是 O(2n )。 3.2 频繁项集的产生 3.2.1 格结构 图 3-1 为项集 I={a, b, c, d, e}的格结构（lattice structure），用来枚举所有可能的项集。 图 3-1 项集的格结构 null AB AC AD AE BC BD BE CD CE DE A B C D E ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCDE