理学数据挖掘关联规则挖掘

购物篮分析“啤酒和尿布”的故事是营销届的神话，“啤酒”和“尿布”两个看上去没有关系的商品摆放在一起进行销售、并获得了很好的销售收益，这种现象就是卖场中商品之间的关联性，研究“啤酒与尿布”关联的方法就是购物篮分析，购物篮分析是沃尔玛秘而不宣的独门武器，购物篮分析可以帮助我们在门店的销售过程中找到具有关联关系的商品，并以此获得销售收益的增长！

D={牛肉，鸡肉，牛奶，奶酪，靴子，衣服，…..}t1:牛肉、鸡肉、牛奶t2:牛肉、奶酪t3:奶酪、靴子t4:牛肉、鸡肉、奶酪t5:牛肉、鸡肉、衣服、奶酪、牛奶

t6:鸡肉、衣服、牛奶t7:鸡肉、牛奶、衣服..............如何从客户购物篮中找出具有关联关系的商品组合呢？关联规则挖掘技术关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。

关联规则简介关联规则(AssociationRuleMining)挖掘是数据挖掘中最活跃的研究方法之一最早是由R.Agrawal等人提出的其目的是为了发现超市交易数据库中不同商品之间的关联关系。一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。经典的关联规则挖掘算法：Apriori算法和FP-growth算法关联规则挖掘

1.1关联规则挖掘的基本概念

1.购物篮分析－引发关联规则挖掘的例子

问题：“什么商品组或集合顾客多半会在一次购物中同时购买？”购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，通过对购物篮清单的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。〖例1〗购买计算机与购买财务管理软件的关联规则可表示为：computerfinancial_management_software [support=2%,confidence=60%]support为支持度，confidence为置信度。该规则表示：在所分析的全部事务中，有2％的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60％也购买了财务管理软件。理解：关联分析中的三个重要的概念

举例：10000个人购买了产品，其中购买A产品的人是1000个，购买B产品的人是2000个，AB同时购买的人是800个。支持度指的是关联的产品（假定A产品和B产品关联）同时购买的人数占总人数的比例，即800/10000=8%，有8%的用户同时购买了A和B两个产品；可信度指的是在购买了一个产品之后购买另外一个产品的可能性，如购买了A产品之后购买B产品的可信度=800/1000=80%支持度可信度〖定义4－2〗关联规则X

Y对事物集D的支持度（support）定义为D中包含有事务X和Y的百分比。关联规则X

Y对事务集合D的置信度（confidence）定义为D中包含有X的事务数与同时包含Y的百分比。即：l

support(XY)＝(包含X和Y的事务数/事务总数)×100％

l

confidence(XY)＝(包含X和Y的事务数/包含X的事务数)×100％〖定义4－3〗置信度和支持度均大于给定阈值（即最小置信度阈值和最小支持度阈值）。即：

support(X

Y)>＝min_sup confidence(XY)>＝min_conf的关联规则称为强规则；否则称为弱规则。数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。强规则X

Y对应的项集（X∪Y）必定是频繁集。因此，可以把关联规则挖掘划分为以下两个子问题：根据最小支持度找出事务集D中的所有频繁项集。―核心根据频繁项集和最小置信度产生关联规则。―较易规则度量：支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,

包含{X、Y}的交易中也包含Z的条件概率设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)ABDCABACADBCBDCDØABCABDBCDACDABCDTransaction-idItemsbought10A,B,C20A,C30A,D，B40B,E,F，cLetmin_support=50%,min_conf=50%:CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerForruleA

C:support=support({A}

{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%关联规则就是支持度和信任度分别满足用户给定阈值的规则。发现关联规则需要经历如下两个步骤：找出所有频繁项集。由频繁项集生成满足最小信任度阈值的规则。以商场超市的市场数据库为例，形式化地描述关联规则。〖定义4－1〗设I={i1，i2，…,im}是项的集合，表示各种商品的集合；D={t1，t2，…,tn}为交易集，表示每笔交易的集合（是全体事务的集合）。其中每一个事务T都是项的集合，且有T

I。每个事务都有一个相关的唯一标识符和它对应，也就是事务标识符或TID。设X为一个由项目构成的集合，称为项集，当且仅当X

T时我们说事务T包含X。项集X在在事务数据库DB中出现的次数占总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。关联规则是形如X

Y的蕴含式，其中X

I，Y

I且X

Y=

，则X称为规则的条件，Y称为规则的结果。如果事务数据库DB中有s%的事务包含XY，则称关联规则X

Y的支持度为s%。支持度是一个概率值。2.关联规则关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性。项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系。

一个简单事务数据库模型数据库DB：TID项001ACD002BCE003ABCE004BE表4-13.关联规则挖掘关联规则挖掘：给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和最小支持度。〖例〗购买商品事务如下表所示，设最小支持度为50%,最小可信度为50%,则可得到以下关联规则：

A

C(50%,66.6%) C

A(50%,100%)

支持度可信度表4-24.关联规则挖掘的分类（1）

基于规则中处理的变量的类别 基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联规则：如果规则考虑的关联是项“在”或“不在”，则关联规则是布尔型的。例如，由购物篮分析得出的关联规则。量化型关联规则：如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。例如：以下是量化型关联规则的一个例子（其中X为表示顾客的变量，量化属性age和income已经离散化）：age(X,“30…39”)∧income(“42K…48K”) buys(X,“high_resolution_TV”)量化型关联规则中也可以包含多种变量。例如：性别=“女”=>职业=“秘书”，是布尔型关联规则；性别=“女”=>avg（月收入）=2300，涉及的收入是数值类型，所以是一个量化型关联规则。（2）基于规则中数据的抽象层次 基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。

单层的关联规则：所有的变量都不涉及不同抽象层次的项或属性。 例如：

buys(X,“computer”) buys(X,“printer”)

顾客X购买的商品不涉及不同抽象层次（“computer”

和“printer”在同一个抽象层），因此是单层关联规则。多层的关联规则：变量涉及不同抽象层次的项或属性。 例如：

age(X,“30…39”) buys(X,“laptopcomputer”) age(X,“30…39”) buys(X,“computer”) 顾客X购买的商品涉及不同抽象层次（“computer”

在比“laptopcomputer”高的抽象层），因此是多层关联规则。

（3）基于规则中涉及到的数据的维数基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。

单维关联规则：处理单个维中属性间的关系，即在单维的关联规则中，只涉及到数据的一个维。 例如：用户购买的物品：“咖啡=>砂糖”，这条规则只涉及到用户的购买的物品。多维关联规则：处理多个维中属性之间的关系，即在多维的关联规则中，要处理的数据将会涉及多个维。 例如：性别=“女”=>职业=“秘书”，这条规则就涉及到两个维中字段的信息，是两个维上的一条关联规则。给出了关联规则的分类之后，就可以考虑某个具体的关联规则挖掘算法适用于哪一类规则的挖掘，某类关联规则又可以用哪些不同的方法进行处理。最简单的是单维、单层、布尔型的关联规则。1.术语关联规则挖掘即给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和最小支持度。

4.2关联规则挖掘的过程〖定义4－4〗在关联规则挖掘算法中，把项目的集合称为项集（itemset），包含有k个项目的项集称为k-项集。包含项集的事务数称为项集的出现频率，简称为项集的频率或支持度计数。如果项集的出现频率大于或等于最小支持度s与D中事务总数的乘积，则称该项集满足最小支持度s。如果项集满足最小支持度，则称该项集为频繁项集（frequentitemset）。〖例〗一个食品连锁店保留着每周的事务记录，其中每一条事务表示在一项收款机业务中卖出的项目。连锁店的管理会收到一个事务汇总报告，报告表明了每种项目的销售量是多少。此外，他们要定期了解哪些项目经常被顾客一起购买。他们发现顾客购买了花生酱后，100%地会购买面包。而且，顾客购买了花生酱后，有33%也购买果冻。不过，所有事务中大约只有50%包含花生酱。被用于在其中寻找关联规则的数据库可以看作为一个元组集合，每个元组包含一组项目。一个元组可能是：

{花生酱、面包、果冻}包含三个项目：花生酱、面包、果冻每个项目表示购买的一种产品一个元组是一次购买的产品列表演示关联规则的样本数据事务项目t1面包、果冻、花生酱t2面包、花生酱t3面包、牛奶、花生酱t4啤酒、面包t5啤酒、牛奶表4-3找出的所有项目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生酱0果冻20啤酒、果冻、牛奶0牛奶40啤酒、果冻、花生酱0花生酱60啤酒、牛奶、花生酱0啤酒、面包20面包、果冻、牛奶0啤酒、果冻0面包、果冻、花生酱20啤酒、牛奶20面包、牛奶、花生酱20啤酒、花生酱0果冻、牛奶、花生酱0面包、果冻、20啤酒、面包、果冻、牛奶0面包、果冻20啤酒、面包、果冻、花生酱0面包、花生酱60啤酒、面包、牛奶、花生酱0果冻、牛奶0啤酒、果冻、牛奶、花生酱0果冻、花生酱20面包、果冻、牛奶、花生酱0牛奶、花生酱20啤酒、面包、果冻、牛奶、花生酱0啤酒、面包、果冻0项目的个数成指数增长：从5个项目的集合得到31个项目集合（忽略空集）表4-42．关联规则的挖掘过程最常用的关联规则挖掘方法被分解为下面两步：第1步：找出所有的频繁项集，即找出支持度大于或等于给定的最小支持度阈值的所有项集。可以从1到k递归查找k-频繁项集。第2步：由频繁项集产生强关联规则，即找出满足最小支持度和最小置信度的关联规则。找出满足定义的大项目集从大项目集（频繁项目集）生成关联规则〖定义4－5〗大（频繁）项目集是出现次数大于阈值S的项目集。用符号L表示大项目集组成的整个集合，用

表示一个特定的大项目集。一旦找出大项目集，则对于任何有趣的关联规则X

Y，在频繁项目集的集合中一定有XY。任何大项目集的子集也是大的4.3

大项目集关联规则中使用了大量的符号，这些符号汇总如下。一个特定符号所带的下标表示所考虑的集合的大小，例如，lk表示一个大小为k的项目集。一些算法将事务集合分为若干个分区，在这种情况下，用p表示分区的数目，用上标表明分区的编号。例如，Di表示D的第i个分区。关联规则使用的符号符号描述符号描述D事务数据库X

Y关联规则tiD中的事务L大项目集的集合s支持度lL中的大项目集

可信度C候选项目集的集合X，Y项目集p分区的数目表10-5几个概念：潜在的大项目集称为候选。所有被计数的（潜在大的）项目集的集合称为候选项目集C。关联规则使用的一个性能度量指标是C的大小。找出所有大项目集以后，关联规则的生成变得非常直接。有关算法：改自[AS94]，用support返回输入项目集的支持度。输入：

D //事务数据库

I //项目集合

L //大项目集

s //支持度

//可信度（置信度）输出:

R //满足s和

的关联规则集合ARGen算法：

R=；

foreachlLdo foreachxlsuchthatx

do

if

support(l)/support(x)

then

R=R

{x

(l-x)}；有关算法演示：参考表4-3、4-4假定输入的支持度和可信度分别为s=30%和

=50%。利用该s值得到如下大项目集的集合：L={{啤酒},{面包},{牛奶}，{花生酱},{面包、花生酱}}查看最后一个大项目集可以生成的关联规则,其中：l={面包、花生酱}有两个非空子集：{面包}和{花生酱}对于第一个非空子集，可得：support({面包、花生酱})/support({面包})=60/80=0.75意味着关联规则：“面包

花生酱”的置信度为75%，因为其置信度高于

，所以是一条有效的关联规则。演示关联规则的样本数据事务项目t1面包、果冻、花生酱t2面包、花生酱t3面包、牛奶、花生酱t4啤酒、面包t5啤酒、牛奶表4-3找出的所有项目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生酱0果冻20啤酒、果冻、牛奶0牛奶40啤酒、果冻、花生酱0花生酱60啤酒、牛奶、花生酱0啤酒、面包20面包、果冻、牛奶0啤酒、果冻0面包、果冻、花生酱20啤酒、牛奶20面包、牛奶、花生酱20啤酒、花生酱0果冻、牛奶、花生酱0面包、果冻、20啤酒、面包、果冻、牛奶0面包、果冻20啤酒、面包、果冻、花生酱0面包、花生酱60啤酒、面包、牛奶、花生酱0果冻、牛奶0啤酒、果冻、牛奶、花生酱0果冻、花生酱20面包、果冻、牛奶、花生酱0牛奶、花生酱20啤酒、面包、果冻、牛奶、花生酱0啤酒、面包、果冻0项目的个数成指数增长：从5个项目的集合得到31个项目集合（忽略空集）表4-4对于第二个非空子集，可得：support({面包、花生酱})/support({花生酱})=60/60=1意味着关联规则：“花生酱

面包”的置信度为100%，也是一条有效的关联规则。找出大项目集的算法可以很简单，但代价很高。简单的方法是：对出现在事务中的所有项目集进行计数。给定一个大小为m的项目集合，共有2m个子集，去掉空集，则潜在的大项目集数为2m-1。随着项目数的增多，潜在的大项目集数成爆炸性增长。（当m=5，为31个；当m=30，变成1073741823个）解决问题的难点：如何高效确定所有大项目集。大部分关联规则算法都利用巧妙的方法来减少要计数的项目集。4.4关联规则挖掘的Apriori算法4.4.1Apriori算法的基本思想Apriori算法是一种最有影响的挖掘布尔关联规则大（频繁）项目集的算法。它使用一种称作逐层搜索的迭代算法，通过k-项集用于探索（k+1）-项集。已经为大部分商业产品所使用。Apriori算法的基本思想是：首先，通过扫描数据集，产生一个大的候选数据项集,并计算每个候选数据项发生的次数，然后基于预先给定的最小支持度生成频繁1-项集的集合，该集合记作；然后基于和数据集中的数据，产生频繁2-项集；用同样的方法，直到生成频繁n-项集，其中已不再可能生成满足最小支持度的（N+1）－项集。最后，从大数据项集中导出规则。在第一次迭代的第一步中，产生的候选集包含所有1-项集，实为数据库中所有的项，再计算各自的支持度。实例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}21.大项目集的性质

大项目集的任一子集也一定是大的。大项目集也称作是向下封闭的，如果一个项目集满足最小支持度的要求，其所有的子集也满足这一要求。其逆命题：如果知道一个项目集是小的，就不需要生成它的任何超集来作为它的候选集，因为它们也一定是小的。Apriori性质基于如下事实：根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即sup（I）<min_sup。如果将项A添加到I，则结果项集（即I∪A）不可能比I更频繁出现。因此，I∪A也不是频繁的，即sup（I∪A）<min_sup。频繁项集的Apriori性质用于压缩搜索空间（剪枝），以提高逐层产生频繁项集的效率。Apriori算法利用了大项目集的这些性质用图表示上述性质，例子中有四个项目{A，B，C，D}，格中的线表示子集关系，大项目集的性质表明：如果原来的项目集是大的，则在路径中位于其上的任何集合也一定是大的。ABDCABACADBCBDCDØABCABDBCDACDABCD{A，B，C，D}项目集的格结构项目{ACD}的非空子集是：{AC，AD，CD，A，C，D}如果{A，C，D}是大的，则其每一个子集也是大的，如果其任何一个子集是小的，则{A，C，D}也是小的。ØABDCABACADBCBDCDABCABDBCDACDABCD{A，C，D}的子集项目{ACD}的非空子集是：{AC，AD，CD，A，C，D}按照Apriori算法：在第i趟扫描的过程中，对Ci进行计数，只有那些大的候选集被用于生成下一趟扫描的候选集，即用Li生成Ci+1。只有一个项目集的所有子集都是大的，它才被认为是候选。为了生成大小为i+1的候选，要对前一趟扫描发现的大项目集进行连接运算。表示：Lk*Lk={X

Y其中X，Y

Lk，|X

Y|=k–1}例：对表4-3进行演算，其中s=30%，

=50%假如有项目集合I={1，2，3，4，5}，有事务集T：

1,2,31,2,41,3,41,2,3,51,3,52,4,51,2,3,4

设定minsup=3/7，misconf=5/7。首先：生成频繁项目集：

1-频繁项目集：{1}，{2}，{3}，{4}，{5}

生成2-频繁项目集：根据1-频繁项目集生成所有的包含2个元素的项目集：任意取两个只有最后一个元素不同的1-频繁项目集，求其并集，由于每个1-频繁项目集元素只有一个，所以生成的项目集如下：

{1，2}，{1，3}，{1，4}，{1，5}

{2，3}，{2，4}，{2，5}

{3，4}，{3，5}

{4，5}计算它们的支持度，发现只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度满足要求，因此求得2-频繁项目集：

{1，2}，{1，3}，{1，4}，{2，3}，{2，4}

生成3-频繁项目集：因为{1，2}，{1，3}，{1，4}除了最后一个元素以外都相同，所以求{1，2}，{1，3}的并集得到{1，2，3}，

{1，2}和{1，4}的并集得到{1，2，4}，{1，3}和{1，4}的并集得到{1，3，4}。但是由于{1，3，4}的子集{3，4}不在2-频繁项目集中，所以需要把{1，3，4}剔除掉。然后再来计算{1，2，3}和{1，2，4}的支持度，发现{1，2，3}的支持度为3/7，{1，2，4}的支持度为2/7，所以需要把{1，2，4}剔除。同理可以对{2，3}，{2，4}求并集得到{2，3，4}，但是{2，3，4}的支持度不满足要求，所以需要剔除掉。因此得到3-频繁项目集：{1，2，3}。到此频繁项目集生成过程结束。注意生成频繁项目集的时候，频繁项目集中的元素个数最大值为事务集中事务中含有的最大元素个数，即若事务集中事务包含的最大元素个数为k，那么最多能生成k-频繁项目集，这个原因很简单，因为事务集合中的所有事务都不包含（k+1）个元素，所以不可能存在（k+1）-频繁项目集。在生成过程中，若得到的频繁项目集个数小于2，生成过程也可以结束了。现在需要生成强关联规则：这里只说明3-频繁项目集生成关联规则的过程：对于集合{1，2，3}先生成1-后件的关联规则：（1，2）—>3，

置信度=3/4（1，3）—>2，置信度=3/5（2，3）—>1

置信度=3/3（1，3）—>2的置信度不满足要求，所以剔除掉。因此得到1后件的集合{1}，{3}，然后再以{1，3}作为后件

2—>1，3

置信度=3/5不满足要求，所以对于3-频繁项目集生成的强关联规则为：（1，2）—>3和（2，3）—>1。演示关联规则的样本数据事务项目t1面包、果冻、花生酱t2面包、花生酱t3面包、牛奶、花生酱t4啤酒、面包t5啤酒、牛奶表4-3回忆找出的所有项目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生酱0果冻20啤酒、果冻、牛奶0牛奶40啤酒、果冻、花生酱0花生酱60啤酒、牛奶、花生酱0啤酒、面包20面包、果冻、牛奶0啤酒、果冻0面包、果冻、花生酱20啤酒、牛奶20面包、牛奶、花生酱20啤酒、花生酱0果冻、牛奶、花生酱0面包、果冻、20啤酒、面包、果冻、牛奶0面包、果冻20啤酒、面包、果冻、花生酱0面包、花生酱60啤酒、面包、牛奶、花生酱0果冻、牛奶0啤酒、果冻、牛奶、花生酱0果冻、花生酱20面包、果冻、牛奶、花生酱0牛奶、花生酱20啤酒、面包、果冻、牛奶、花生酱0啤酒、面包、果冻0项目的个数成指数增长：从5个项目的集合得到31个项目集合（忽略空集）表4-4趟数候选大项目集1{啤酒}，{面包}，{果冻}，{牛奶}，{花生酱}{啤酒}，{面包}，{牛奶}，{花生酱}2{啤酒，面包}，{啤酒，牛奶}，{啤酒，花生酱}，{面包，牛奶}，{面包，花生酱}，{牛奶，花生酱}{面包，花生酱}对表4-3采用Apriori算法为了组合出下一级候选，每个项目集除了一个项目之外，其它的项目都相同。因为只有一个大小为2的大项目集，所以没有大小为3的候选4.4.2Apriori算法中的关键步骤Apriori算法中的关键步骤是由Lk-1找Lk，该步骤可分为两步：第1步（连接）：为找Lk，通过Lk-1与自己连接产生候选K-项集的集合。将该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集，记号li[j]表示li的第j项。执行连接Lk-1和Lk-1，其中Lk-1的元素是可连接，如果它们前（k-2）个项相同而且第（k-2）项不同（为简单计，设l1[k-1]<l2[k-1]），即：l1[1]=l2[1]∧l1[2]=l2[2]∧……∧l1[k-2]=l2[k-2]∧l1[k-1]<l2[k-1]则Lk-1的元素l1和l2是可连接的。连接l1和l2产生的结果的项集是l1[1]l1[2]……l1[k-1]l2[k-1]。第2步（剪枝）：Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。一个称为Apriori-Gen的算法：用于生成除第一趟之外的每一趟扫描的候选项目集。所有的单元素项目集在第一趟时作为候选使用。前一趟发现的大项目集的集合Li-1与自身进行连接运算以确定候选。为了组合出下一级候选，每个项目集除了一个项目之外，其它的项目都相同。Apriori-Gen算法实例：一个女士服装店在一天中有20个收款机事务记录，如表：衣服事务样本事务项目事务项目t1罩衣t11T恤t2鞋，裙子，T恤t12罩衣，牛仔裤，鞋，裙子，T恤t3牛仔裤，T恤t13牛仔裤，鞋，短裤，T恤t4牛仔裤，鞋，T恤t14鞋，裙子，T恤t5牛仔裤，短裤t15牛仔裤，T恤t6鞋，T恤t16裙子，T恤t7牛仔裤，裙子t17罩衣，牛仔裤，裙子t8牛仔裤，鞋，短裤，T恤t18牛仔裤，鞋，短裤，T恤t9牛仔裤t19牛仔裤t10牛仔裤，鞋，T恤t20牛仔裤，鞋，短裤，T恤Apriori-Gen实例扫描候选集大项目集1{罩衣}，{牛仔裤}，{鞋}，{短裤}，{裙子}，{T恤}{牛仔裤}，{鞋}，{短裤}，{裙子}，{T恤}2{牛仔裤，鞋}，{牛仔裤，短裤}，{牛仔裤，裙子}，{牛仔裤，T恤}，{鞋，短裤}，{鞋，裙子}，{鞋，T恤}，{短裤，裙子}，{短裤，T恤}，{裙子，T恤}{牛仔裤，鞋}，{牛仔裤，短裤}，{牛仔裤，T恤}，{鞋，短裤}，{鞋，T恤}，{短裤，T恤}，{裙子，T恤}3{牛仔裤，鞋，短裤}，{牛仔裤，鞋，T恤}，{牛仔裤，短裤，T恤}，{牛仔裤，裙子，T恤}，{鞋，短裤，T恤}，{鞋，裙子，T恤}，{短裤，裙子，T恤}{牛仔裤，鞋，短裤}，{牛仔裤，鞋，T恤}，{牛仔裤，短裤，T恤}，{鞋，短裤，T恤}4{牛仔裤，鞋，短裤，T恤}{牛仔裤，鞋，短裤，T恤}5

Apriori-Gen算法处理过程：第一趟扫描得到6个候选项目集，其中5个候选是大的。对该5个候选应用Apriori-Gen算法，将每一个候选与另外4个进行组合，得到第二趟扫描：4+3+2+1=10个候选，其中7个候选是大的。在7个候选中再应用Apriori-Gen算法，将每一个项目集与另外一个与之具有一个公共成员的项目集进行连接运算，第三趟扫描后得到4个大项目集。第四趟扫描后只剩下一个大项目集，也不存在下一趟计数为5个的新项目集。在客户关系管理（CRM）理论中有一个经典的2/8原则，即80%利润来自20%客户。那么，这20%的客户都有什么特征呢？调查发现，大部分企业每年有20%～50%的客户是变动的。企业一方面在挖空心思争取新客户，另一面却不断失去老客户。有没有办法找出，失去的是哪一类型的客户，得到的又是哪种类型的客户。在竞争激烈的商业时代，资源占有成为决定企业生死成败的关键。在客户关系方面，企业总希望建立与客户最稳固的关系，并最有效率地把这种关系转化为利润，即留住老顾客、发展新顾客并锁定利润率最高的客户，这也就是CRM要重点研究的问题。为了实现这个目标，企业就需要尽可能地了解客户的行为，但这种了解不可能通过与客户接触直接获得，因为企业不可能挨个与客户交谈，而且他们所需要的信息单个客户往往无法提供。4.9

关联规则挖掘在CRM中的应用4.9.1CRM简介企业所能做的，就是尽可能收集顾客的信息，借助各种分析方法，透过无序的、表层的信息挖出内在的知识和规律，这就当前十分流行的数据挖掘技术所研究的。在挖出大量信息之后，企业就可以根据这些规律或用这些信息设计数学模型，对未发生行为做出结果预测，为企业的综合经营决策、市场策划提供依据。在CRM中，数据挖掘是从大量的有关客户的数据中挖掘出隐含的、先前未知的、对企业决策有潜在价值的知识和规则。

数据挖掘的第一步就是挖出顾客的特征描述。企业在了解客户信息方面永不满足，他们不仅会想方设法了解顾客的地址、年龄、性别、收入、职业、教育程度等基本信息，对婚姻、配偶、家庭状况、疾病、爱好等等的收集也是不遗余力。也由于这个原因，在谈到CRM的时候，个人隐私便成为一个敏感话题。

（1）客户特征：通过客户行为分析，归类出消费额最高、最为稳定的客户群，确定为“黄金客户”。针对不同的客户档次，确定相应的营销投入。对于“黄金客户”，往往还需要制定个性化营销策略，以求留住高利润客户。所以，不要期待在CRM时代继续人人平等。当然，成功的CRM不会让顾客感觉到歧视。如果你不幸发现自己受到的待遇比别人低，很有可能别人是“黄金”，而你是“白银”或者“黑铁”。

（2）“黄金客户”：通过与客户接触，收集大量客户消费行为信息，通过分析，得出客户最关注的方面，从而有针对性地进行营销活动，把钱花在“点”上。同样的广告内容，根据客户不同的行为习惯，有的人会接到电话，有的人就可能收到信函；同一个企业，会给他们的客户发送不同的信息，而这些信息往往就是顾客感兴趣的方面。不要惊讶于为什么企业给你送来的正是你最需要的、最满意的，你和其他与你相似的顾客的数据，在企业的数据仓库里经不住百般“拷打”，已经集体招供了。

（3）客户关注点：（4）客户忠诚度：得出客户持久性、牢固性及稳定性分析。对于高忠诚度客户，要注意保持其良好印象，对于低忠诚度客户，要么不要浪费钱财，要么就下大工夫把他们培养成忠诚客户。在CRM中，必不可少的要素是将海量的、复杂的客户行为数据集中起来的，形成整合的、结构化的数据仓库（DataWearhouse），这是数据挖掘的基础。在此基础上，就需要借助大量的知识和方法，把表面的、无序的信息整合，揭示出潜在的关联性和规律，从而用于指导决策。4.9.2关联规则挖掘在CRM中的应用类别

主要类别：横向关联

次序关联

横向关联是挖掘表面看似独立的事件间的相互关系，例如“90%的顾客在一次购买活动中购买商品A的同时购买商品B”之类的知识。比如经典的“尿布和啤酒”的故事，就是利用这种方法，发现二者之间有很高的相关系数，引起重视，然后深入分析后才找出内在原因的。

横向关联