关联规则在购物篮分析中的应用_孙细明

《关联规则在购物篮分析中的应用_孙细明》由会员分享，可在线阅读，更多相关《关联规则在购物篮分析中的应用_孙细明（4页珍藏版）》请在金锄头文库上搜索。

1、总第 224期 2008年第 6期 计算机与数字工程 Co mputer D 是所有事务的集合, 即数据库; 每个事务T 是一些项目的集合, 使得 T A I, 每个事务可以用惟一的标识符 TID 来表示 1。设 A 为某些项目的集合, 如果 A AT, 则称事务 T 包含 A。关联规则就是如下形式的一种蕴含: A B。其中 A I, B I,并且 A HB= 。关联规则 A B 在数据库 D 中成 立的条件是:1)支持度 (Support)S表示事务在规则中出现的频率。关联规则 X Y的支持度 S定义为: S(X Y)=|T (XG Y) | |T |。其中, |T (X G Y) |指数据

2、集中包含X G Y的事务数; |T |表示数据集中的事务总数。 2)置信度 (Confidence)C 表示关联规则 X Y的强度。可定义为:C(X Y) =|T (X G Y) | |T (X ) |。其中, |T (X G Y) |指数据集中包含 X G Y 的事务数; |T (X ) |表示数据集中包含 X 的事务数。如果不考虑关联规则的支持度和可信度, 那么 在事务数据库中存在无穷多的关联规则。事实上,人们一般只对满足一定的支持度和可信度的关联规则感兴趣。为了挖掘出有意义的关联规则, 需要给定两个阈值: 最小支持度 (M in_sup)和最小可信度 (M in_conf), 同时满足最

3、小支持度阈值 ( m in_sup)和最小置信度阈值 ( m in_conf)的规则称作强 关联规则。习惯上, 我们将关联规则表示为 A B(S%, C% ), S%即用户规定的关联规则必须满足的最小支持度, 它表示了一组物品集在统计意义上的需满足的最低程度; C% 即用户规定的关联规则必须满足的最小可信度, 它反应了关联规则的最低可靠度 2。考察一些涉及许多物品的事务: 事务 1中出现了物品甲, 事务 2中出现了物品乙, 事务 3中则同时 出现了物品甲和乙。那么, 物品甲和乙在事务中的出现相互之间是否有规律可循呢? 在数据库的数据挖掘中, 关联规则就是描述这种在一个事务中物品之间同时出现的规

4、律的知识模式。更确切地说, 关联规则通过量化的数字描述这种在一个事务中的物品甲的出现对于物品乙的出现有多大的影响。具体来说, 关联规则是形式如下的一种规则, / 在购买计算机的客户中, 有 30 % 的人也同时购买了打印机。 0 用于关联规则发现的主要对象是事务型数据库, 其中针对的应用则是售货数据, 也称货篮数据。一个事务一般由如下几个部分组成: 事务处理时间, 一组顾客购买的物品, 有时也有顾客标识号 (如信用卡号 )。随着条形码技术的发展, 零售部门可以利用POS系统收集存储大量的售货数据。如果对这些 历史事务数据进行分析, 则可对顾客的购买行为提供极有价值的信息。例如, 可以帮助如何摆

5、放货架上的商品 (如把顾客经常同时买的商品放在一 起 ), 帮助规划市场 (怎样相互搭配进货 )。由此可见, 从事务数据中发现关联规则, 对于改进零售业等商业活动的决策非常重要。3 关键算法Apriori算法是挖掘产生布尔关联规则所需频繁 项集的基本算法, 也是一个很有影响的关联规则挖掘算法。它是根据有关频繁项集特性的先验知识( prior knowledge)而命名的。该算法利用了一个层次顺序搜索的循环方法来完成频繁项集的挖掘工 作; 这一循环方法就是利用 k-项集来产生 (k+ l) -项集。具体做法就是: 首先扫描数据库找出频繁 1- 项集, 记为 L1; 然后对 L1做连接操作生成 C

6、2, 扫 描数据库从 C2中选出 L2, 即频繁 2- 项集; 不断如此循环下去直到无法发现更多的频繁 k - 项集为止。每挖掘一层 LK就需要扫描整个数据库一遍。 算法高效的关键在于生成较小的候选项目集,也就是尽可能不生成和计算那些不可能成为频繁项目集的候选项目集。为提高按层次搜索并产生 相应频繁项集的处理效率, Apriori算法利用了这样一个基本性质: 即一个频繁项目集的任一子集必定也是频繁项目集。这个性质被目前的绝大部分 关联规则算法所继承。Apriori算法对关联规则的发现主要分为两步:第一步是迭代识别所有的频繁项集, 要求频繁项集 的支持率不低于用户设定的最低值 M in_sup

7、; 第二步是从频繁项集产生强关联规则, 即产生那些支持度和置信度分别大于或等于事先给定的支持度阈值(M in_sup)和置信度阈值 (M in_conf)的关联规则 3。Apriori算法利用层次循环发现频繁项集, 其算法伪代码如下:输入: 交易数据库 D,最小支持度阈值 m in_ sup 输出:D中的频繁项集 L L1= large 1- ite m sets; for ( k= 2 ; Lk- 1X ;k+ ) do begin Ck= apriori_gen ( Lk- 1, m in_sup); forall transactions tI D do begin Ct= subset

8、( Ck,t); forall candidates cI Ct do58 孙细明等: 关联规则在购物篮分析中的应用 第 36卷 c . count+ ;end Lk= cI Ck|c . count m in_supend Answer= UkLk;Apriori算法的第 步就是发现频繁 1- 项集 L1; 在第 至第 步, 利用 Lk- 1产生 Ck以便获得Lk。在第 步中, Apriori_gen过程产生相应的候选项集; 然后利用 Apriori性质删除那些子集为非频繁项集的候选项集。一旦产生所有候选, 就要扫描 数据库 (第 步 )。在第 步中, 对于数据库中的每个交易利用 subse

9、t函数来帮助发现该交易记录的所有 (已成为候选项集 )的子集, 由此累计每个候选项集的支持频度 (第 步 )。最终满足最小支 持频度的候选项集组成了频繁项集 L。这样可以利用一个过程来帮助从所获得频繁项集中生成所有的关联规则。 Apriori算法在发现频繁项目集的过程中完成两个操作: 一是连接, 二是删除操作。在连接过程中, Lk- 1与 Lk- 1连接以产生潜在候选项集; 删除过程中, 利用 Apriori性质删除候选项集中那些子集 为非频繁项集的项集 4。4 关联规则在购物篮分析的实例 描述4 . 1 研究背景及数据描述 在超市经营中, 商品的摆放位置对销售起着至关重要的作用。合理的商品布

10、局不但能节省顾客的购买时间, 而且能刺激顾客的购买欲望。往往许多依靠销售人员的经验认为没有一点联系的商品, 将它们摆放在一起, 可能会起到意想不到的销售效果。通过合理利用数据挖掘技术, 超市管理人员可以了解顾客的购买习惯和偏好, 考虑购买者在商店 里所穿行的路线、 购买时间和地点、 货架的使用效率、 畅销商品的类别、 不同商品一起购买的概率, 通过对商品销售品种的活跃性分析和关联性分析, 用主成分分析方法, 建立商品设置的最佳结构和商品 的最佳布局, 以提高超市销售额。在此笔者以一家实际的小型超市为实例, 利用超市 POS系统中保存的交易数据集中的数据进行有效分析, 再结合关联规则算法找到强关

11、联规则, 利用最终的结论实现超市合理的物品摆放及交叉销售策略。下面分析具体的实现方法和步骤, 为了表述分析的方法, 这里我们将只关注几种商品的的 销售情况, 为描述方便, 提取百货类几种商品并分别标记组成商品库: DB= 毛毯 A、脸盆 B 、 拖把C、枕头 D、 垃圾桶 E、 卫生纸 F。将 POS系统数据进行加工、 整理, 得到一个数 据表如表 1所示。表 1 商品交易表交易 商品毛毯 A脸盆 B拖把 C枕头 D垃圾 桶 E卫生 纸 FI D1010110 I D2101001I D3111010 I D4011011I D5101100 I D6001110I D7010100 I D8

12、101000从表 1我们可以提取交易单信息如下:I D 1= B、 D、 E; I D 2= A、 C 、 F; ID 3= A、 B、 C、 E; I D 4= B 、 C、 E、 F; I D 5= A、 C、 D; I D 6= C、 D、 E; I D 7= B 、 D; I D 8= A、 C。4 . 2 实现步骤 假定最小支持度 M in_sup= 0 . 25 , 由 Apriori算法找出满足 M in_sup= 0 . 25的最大频繁项集的执行过程如下:1)算法第一次扫描数据库, 确定 1- 项集及各 元素的覆盖频度。如下:2)利用 L1 L1来产生候选项集 C2, 由 C2

13、确定 频繁 2- 项集。如下:3)利用 L2 L2进行连接操作, 获得候选 3-59第 36卷 ( 2008)第 6期 计算机与数字工程 项集 C3。根据 Apriori的性质, / 一个频繁项集的所有子集也是频繁的0, 删除了其中不是频繁项集的一些候选项集, 其结果如下:4)利用 L3 L3进行连接操作得到 C4, 根据Apriori性质可知 C4= , 算法到此结束。销售数据库 DB经过扫描、 筛选、 连接、 删除一系列操作, 最终得到所需要的最大频繁 3- 项集 L3 = B, C, E 。由已得到最大频繁项集 L = B, C,E , 再结合关联规则生成算法可产生的以下几种关联规则。结

14、合本文第二节中置信度的定义, 分别 计算以下几种关联规则的置信度 ( confidence), 其结果如下:B, C E confidence= 2/2= 1B, E Cconfidence= 2/3= 0 . 67 E, C Bconfidence= 2/2= 1B C, Econfidence= 2/4= 0 . 5C B, Econfidence= 2/5= 0 . 4 E B, Cconfidence= 2/4= 0 . 5假定最小可信度阈值 M in_conf= 0 . 6 , 则上述产生的关联规则中只有三条规则满足强规则, 可以输出。它们分别是: B, C EB, E CE, C

15、B 很容易看出, 在 脸盆 B 、 拖把 C、 垃圾桶 E三种商品当中, 在购买其中两个商品的前提下, 购买另外一个商品的概率是很高的。根据算法所推出的结果, 该小型超市把 脸盆、 拖把、 垃圾桶 这三 种不同类的商品摆放到一起或非常临近的位置。最终通过销售报表可以看出, 在不改变商品价格的前提下, 三种商品的销售额都提高了 16 . 8 %。由此看出, 通过数据挖掘得到的商品关联规则给商家 带来了极大的经济效益。5 结语购物篮分析是当前数据挖掘最直接、 最简单、 最有效的应用领域, 它能够在潜在的客户群体中发现新客户、 建立响应模型; 能够确定交叉销售策略而销售更多的产品; 能够发现并防止客

16、户的流失; 能够将更好的服务提供给更有价值的客户 5。虽然本文挖掘数据比较少, 仅限于特定时间的消费数据, 但无论数据的多少, 其工作原理都是一样的, 得到的结果对研究局部人群购买趋势还是有一定的 指导意义。随着经济的发展, 购物篮分析在大型超市中的应用将会越来越广。与此同时也存在一些不利因素, 由于数据本身的局限性, 无法对每一个顾客每 次消费情况进行跟踪调查, 因此数据广度是有限的; 另外有些数据很难得到, 如涉及顾客隐私的情况, 因此数据的深度也相当有限。从实际操作的角 度考虑, 虽然持卡消费的顾客仅是全部顾客的一部分, 但他们是有代表性的顾客群, 而且往往是较稳定的有价值的顾客群。在进行购物篮分析时, 应主要通过对这些持卡用户的消费进行分析,