关联规则分析及应用

关联规则（Apriori算法）

关联分析直观理解

关联分析中最有名的例⼦是“尿布与啤酒”。据报道，美国中西部的⼀家连锁店发现，男⼈们会在周四购买尿布和啤酒。这样商店实际上可以将尿布与啤酒放在⼀块，并确保在周四全价销售从⽽获利。当然，这家商店并没有这么做。

频繁项集是指那些经常出现在⼀起的物品集合，⽐如{葡萄酒，尿布, ⾖奶}就是频繁项集的⼀个例⼦

⽀持度（support）

⼀个项集的⽀持度（support）被定义为数据集中包含该项集的记录所占的⽐例 {⾖奶}的⽀持度为4/5。{⾖奶，尿布}的⽀持度为3/5

可信度（confidence ）

可信度或置信度（confidence）是针对⼀条诸如{尿布} ➞ {葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“⽀持度({尿布, 葡萄酒})/⽀持度({尿布})”。由于{尿布, 葡萄酒}的⽀持度为3/5，尿布的⽀持度为4/5，所以“尿布 ➞ 葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适⽤。Apriori算法的⽬标是找到最⼤的K项频繁集 ⽀持度和可信度是⽤来量化关联分析是否成功的⽅法。假设想找到⽀持度⼤于0.8的所有项集，应该如何去做？⼀个办法是⽣成⼀个物品所有可能组合的清单，然后对每⼀种组合统计它出现的频繁程度，但当物品成千上万时，⾮常慢，这时就能⽤Apriori算法

关联分析中最有名的例⼦是“尿布与啤酒”。据报道，美国中西部的⼀家连锁店发现，男⼈们会在周四购买尿布和啤酒。这样商店实际上可以将尿布与啤酒放在⼀块，并确保在周四全价销售从⽽获利。当然，这家商店并没有这么做。

⼀般我们使⽤三个指标来度量⼀个关联规则，这三个指标分别是：⽀持度、置信度和提升度。

Support（⽀持度）：表⽰同时包含A和B的事务占所有事务的⽐例。如果⽤P(A)表⽰使⽤A事务的⽐例，那么Support=P(A&B)

Confidence（可信度）：表⽰使⽤包含A的事务中同时包含B事务的⽐例，即同时包含A和B的事务占包含A事务的⽐例。公式表达：Confidence=P(A&B)/P(A)

２０１０年４月　第１４卷第２期　宁波职业技术学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｎｉｎｇｂｏ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ａｐｒ，２０１０　Ｖ０】．１４　Ｎｏ．２　

关联规则分析在学生成绩管理中的应用　

林治　

（扬州职业大学信息工程学院，江苏扬州　２２５００２）　

摘　要：介绍了数据挖掘中的关联规则分析的概念、特点和常用算法，并利用改进的Ａｐｆｉｏｆｉ算法对高职高专　院校信息技术公共课考试成绩进行了分析指导。　

关键词：关联规则分析；数据挖掘；Ａｐｆｉｏｆｉ算法　中图分类号：ＴＰ　３ｌ１．１３２　文献标识码：Ａ　文章编号：１６７１－２１５３（２０１０）０２—００６４—０４　

１　关联规则的基本概念　３　Ａｐｒｉｏｒｉ算法的改进　

关联规则挖掘就是在大量的数据中发现数据　

项之间的关系，是数据挖掘领域中研究的热点问　

题。关联规则的概念最早由Ｒ．Ａｇｒａｗａｌ，Ｔ．Ｉｍｉｅｌｉｎｓｋｉ　

和Ａ．Ｓｗａｍｉ提出，应用于交易数据库，用来发现超　

级市场中用户购买商品之间的隐含关系，即关联　

规则．以便为商场的决策提供依据（如：把用户经　

常购买的商品摆放在一起）。　

关联规则问题可以分解为以下两个子问题：　

（１）找｝ＪＩ存在于事务数据库中的所有大项集。　

项集　的支持度Ｓｕｐｐｏｒｔ（Ｘ）不小于用户给定的最　

小支持度ｍｉｎｓｕｐ，则称　为大项集。　

（２）￣ｌｌ用大项集生成关联规则。对于每个大项　

集Ａ，若Ｂ∈Ａ，Ｂ≠　，且Ｓｕｐｐｏｒｔ（Ａ）／Ｓｕｐｐｏｒｔ（Ｂ）≥　

ｍｉｎｃｏｎｆ，则有关联规则　＝＞（Ａ—Ｂ）。　本文在经典的Ａｐｒｉｏｒｉ基础上，采用新的数据　

结构，改进后的算法拟采用基于链表的数据结构，　

链表涉及３种结点，分别为项集头结点、项结点、　

事务结点【　。链表的一级兄弟结点从左到右按照　

子集支持度计数的递增顺序排列，这样即使１一项　

集很大的情况下，也将只产生较少的候选２一项集，　

２一项集再产生更少的候选３一项集等等，从而提高　

了系统的性能。　

２０１３年１月　总第５１０期第１期　经济论坛　Ｅｃｏｎｏｍｉｃ　Ｆｏｒｕｍ　Ｊａｎ．２０１３　Ｇｅｎ．５１０　Ｎｏ．１　

基于　ＫＡ　中关联规则的分析及应用举例　

文／王彦增曹正　【摘　要】关联规则的数据挖掘，可以发现购物篮数据库中不同商品间潜在的关系。应用软件ＷＥＫＡ可　以非常便利、直观地进行数据挖掘工作，对于商品的交叉销售及货架的商品摆放具有一定的指导作用。　【关键词】关联规则分析；ＷＥＫＡ；数据挖掘；Ａｐｒｉｏｒｉ算法　【作者简介】王彦增，浙江理工大学经济管理学院硕士研究生，研究方向：电子商务、市场营销；曹正，浙　江理工大学经济管理学院教授，硕士生导师，研究方向：战略管理与零售管理。　现今各行业数据激增，如何在茫茫数据库中挖　掘出有效利用的信息已成为一大难题。针对此情　况，如何利用一些经典的数据挖掘工具以及相应算　法进行数据挖掘工作已成为热门课题。本文仅针对　数据挖掘工作中关联规则的挖掘进行了一定阐述，　总结了利用ＷＥＫＡ进行数据挖掘的一般步骤，并　进行了应用举例。　一、应用软件ＷＥＫＡ简介　ＷＥＫＡ，全名是怀卡托智能分析环境（Ｗａｉｋａ．　ｔｏ　Ｅｎｖｉｒｏｎｍｅｎｔ　ｆｏｒ　Ｋｎｏｗｌｅｄｇｅ　Ａｎａｌｙｓｉｓ），是一个功能　全面的机器学习（ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ）和数据挖掘应用　程序平台。ＷＥＫＡ是新西兰怀卡托（Ｗａｉｋａｔｏ）大　学开发的一种用Ｊａｖａ编写的开源的机器学习以及数　据挖掘软件，可以运行于几乎所有的操作平台，包　括Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ、Ｍａｃｉｎｔｏｓｈ等，ＷＥＫＡ中共有　十几个Ｊａｖａ程序包，其中涉及关联算法的是ａｓｓｏｃｉ．　ａｔｉｏｎｓ和ｃｏｒｅ两个包。　二、数据挖掘中的关联规则挖掘　（一）关联规则概述　关联规则首先是在１９９３年的ＳＩＧＭＯＤ会议上　被Ａｇｒａｗｌ、Ｉｍｉｅｌｉｎｓｋｉ和Ｓｗａｍｉ提出的，其目的是便　于发现事物、关系数据库中的项集和对象中发现关　联规则、相关性或者因果结构。找出大量数据集中　数据项之间的有趣的关联和相关联系的规则，对于　交叉销售（ｃｒｏｓｓ　ｍａｒｋｅｔｉｎｇ）和配送服务等都是很　有价值的。　（二）关联规则主要概念、参数　设Ｉ＝｛ｉｌ’　一ｉ　｝是由ｎ个不同的项目组成的集　合，Ｄ为事务数据库，其中事务Ｔ时Ｉ的子集，即Ｔ　Ｉ，每一个事务都有一个惟一标识符ＴＩＤ。设Ａ是　一个由项目组成的集合，事务Ｔ包含事务Ａ。如果　项目Ａ包含ｋ个项目，则称其为ｋ项集。而Ａ对Ｂ　的相关的关联规则的蕴涵式表示为Ａ：＝＞Ｂ，其中Ａ　Ｉ，Ｂ　Ｉ，且ＡｎＢ＝　。　一般可用四个参数来描述一对关联规则的属　性：置信度（Ｃｏｎｆｉｄｅｎｃｅ）、支持度（Ｓｕｐｐｏｒｔ）、期　望置信度和作用度（Ｌｉｆｔ）。　（三）关联规则的挖掘　关联规则的挖掘即发现数据项之间的强关联　规则。强关联规则的挖掘定义为：同时满足用户　给定的最小支持度（ｍｉｎ—ｓｕｐ）和最小置信度　（ｍｉｎ＿ｃｏｎｆ）的关联规则。　三、使用ＷＥＫＡ进行关联规则数据挖掘一般　步骤　（一）在ＷＥＫＡ下关联规则数据挖掘步骤　１．数据准备。数据准备是对源数据进行一定的　预处理，在保证数据准确的前提下，去除冗余、错　误的数据，提高数据处理的效果以及质量。　２．数据转换、载入和处理。在使用Ｗｅｋａ前，　首先要了解Ｗｅｋａ的数据格式，Ｗｅｋａ的期望格式是　ＡＲＦＦ（Ａｔｔｒｉｂｕｔｅ—Ｒｅｌａｔｉｏｎ　Ｆｉｌｅ　Ｆｏｒｍａｔ）。然而，在　使用Ｗｅｋａ进行数据挖掘时，往往发现数据的存放　格式不是ＡＲＦＦ格式。但是大多数情况下数据会存　放在微软的Ｅｘｃｅｌ电子数据表中，在数据转换方面　Ｗｅｋａ提供了对ＣＳＶ文件的支持，同时还提供了通　过ＪＤＢＣ访问数据库的功能。　因为Ｗｅｋａ具有读入“．ＣＳＶ”格式文件的能　力。假定已经正确安装Ｗｅｋａ，点击ｅｘｐｌｏｒｅｒ命令　框，ｆ在Ｐｒｅｐｒｏｃｅｓｓ　ｔａｂ）点击“Ｏｐｅｎ”，并导航带包　含数据文件（．ＣＳＶ或．ａｒｆｆ）的目录。　数据简单处理包括：①选择或过滤属性，一旦　

一，关联分析定义关联分析，就是从大规模数据中，发现对象之间隐含关系与规律的过程，也称为关联规则学习。例如：购物篮分析，最早是为了发现超市销售数据库中不同的商品之间的关联关系。用于寻找数据集中各项之间的关联关系。根据所挖掘的关联关系，可以从一个属性的信息来推断另一个属性的信息。当置信度达到某一阈值时，可以认为规则成立。常用的关联分析算法

二，关联规则概念1.项与项集项，指我们分析数据中的一个对象；项集，就是若干项的项构成的集合，如集合{牛奶、麦片、糖}是一个3项集2.支持度某项集在数据集中出现的概率。即项集在记录中出现的次数，除以数据集中所有记录的数量。支持度体现的是某项集的频繁程度，只有某项集的支持度达到一定程度，我们才有研究该项集的必要。support(A)=count(A)/count(dataset)=P(A)3.置信度项集A发生，则项集B发生的概率。关联规则{A->B}中，A与B同时出现的次数，除以A出现的次数。置信度体现的是关联规则的可靠程度，如果关联规则{A->B}的置信度较高，则说明当A发生时，B有很大概率也会发生，这样就可能会带来研究价值。4.提升度关联规则{A->B}中，提升度是指{A->B}的置信度，除以B的支持度提升度体现的是组合（应用关联规则）相对不组合(不应用关联规则)的比值，如果提升度大于1，则说明应用该关联规则是有价值的。如果提升度小于1，说明应用该关联规则起到了负面影响。因此，我们应该尽可能让关联规则的提升度大于1，提升度越大，则应用关联规则的效果越好。（注：如果两个事件相互独立，P(AB)=p(A)*P(B),提升度为1）.5.频繁项集如果项集I的支持度满足预定义的最小支持度阈值，则I是频繁项集。通常情况下，我们只会对频繁出现的项集进行研究。如果一个频繁项集含有K个元素，我们称之为频繁K项集。6.最小支持度用户或专家定义的衡量支持度的一个阈值，表示项集在统计意义上的最低重要性。7.最小置信度用户或专家定义的衡量置信度的一个阈值，表示关联规则的最低可靠性。同时满足最小支持度阈值和最小置信度阈值的规则成为强规则。目前，设置最小支持度和最小置信度，大部分根据业务经验设置初始值，然后经过多次调整，获取与业务相符的关联规则结果。三，关联分析过程关联分析包含2个过程：从数据集中寻找频繁项集，从频繁项集中生成关联规则。1.寻找频繁项集首先，我们需要找到所有的频繁项集，即经常出现在一起的对象集合，实际上，找到频繁项集并不复杂，我们只需要按照如下的步骤来进行操作即可：a.遍历对象之间所有可能的组合（包含单个对象的组合），每种组合构成一个项集。b.针对每一个项集A，计算A的支持度(A出现的次数除以记录总数)c.返回所有支持度大于阈值的项集。以上的理论是没有问题，但是，却很难再实际应用中使用，因为，对象之间任意组合构成的项集，数量可能非常大。例如，在上图中，4个不同的对象，就可以构成15种组合。而对于含有N个对象的数据集，总共可以构成2ⁿ-1种组合，这是一个非常大的数字。因此，为了降低计算量，我们使用Apriori算法原理进行优化。Apriori算法原理可以解释如下：1）如果X是频繁项集，则其所有子集也是频繁项集。