实验目的

进一步理解关联规则算法（Apriori算法、FP-tree算法），利用weka实现数据集的挖掘处理，学会调整模型参数，读懂挖掘规则，解释规则的含义

实验要求

（1）随机选取数据集为对象，完成以下内容：（用两种方法：Apriori算法、FP-tree算法）

1. 文件导入与编辑；
2. 参数设置说明；
3. 结果截图；
4. 结果分析与对比。

（2）以下表，做关联规则挖掘

TID	Items
T1	{牛奶，面包}
T2	{面包，尿布，啤酒，鸡蛋}
T3	{牛奶，尿布，啤酒，可乐}
T4	{面包，牛奶，尿布，啤酒}
T5	{面包，牛奶，尿布，可乐}
T6	{牛奶，尿布，啤酒}
T7	{尿布，啤酒}
T8	{面包，牛奶，尿布}

5. 文件生成与编辑；
6. 参数设置说明；
7. 结果截图；
8. 结果分析。

supermarket数据实验过程

1. 文件导入与编辑

用“Explorer”打开“supermarket.arff”，如图1.1所示，打开的数据为离散型数据，可直接进行关联规则分析，切换到“Associate”选项卡进行分析。

图1.1 supermarket数据集

2. 参数设置说明

2.1 参数说明

• car：如果设为真，则会挖掘类关联规则而不是全局关联规则。
• classindex：类属性索引。如果设置为-1，最后的属性被当作类属性。
• Delta：以此数值为迭代递减单位。不断减小支持度直至达到最小支持度或产生了满足数量要求的规则。
• lowerBounfMinSupport：最小支持度下界
• merticType：度量类型，设置对规则进行排序的度量依据。可以是：置信度（类关联规则只能用置信度挖掘），提升度（lift），平衡度（leverage），确信度（conviction）。
• MinMtric：度量的最小值
• numRules：要发现的规则数
• outputItemSets： 如果设置为真，会在结果中输出项集。
• removeAllMissingCols： 移除全部为缺失值的列。
• significanceLevel ：重要程度。重要性测试（仅用于置信度）。
• upperBoundMinSupport： 最小支持度上界。 从这个值开始迭代减小最小支持度。
• verbose： 如果设置为真，则算法会以冗余模式运行。

2.2 参数设置

挖掘支持度在10%到100%之间，并且置信度超过0.9且置信度排在前10位的关联规则。

• “lowerBoundMinSupport”和“upperBoundMinSupport”分别设为0.1和1
• “metricType”设为confidence
• “minMetric”设为0.9
• “numRules”设为10

Apriori方法参数设置如下图2.2.1所示。

图2.2.1 Apriori方法参数设置图

FP-tree方法参数设置如下图2.2.2所示。

图2.2.2 FP-tree方法参数设置图

3. 结果截图

参数设定完成后单击start按钮，weka开始进行关联规则分析，Apriori算法结果如图3.1所示，FP-tree算法结果如图3.2所示。

图3.1 Apriori方法结果

图3.2 FP-tree方法结果

将Apriori方法中参数outputItemSets设置为TRUE，部分运行结果如图3.3所示。

图3.3 一频繁项目集

4. 结果分析

从图3.1，3.2中看出，挖掘出的前十条强关联规则中最大的置信度为0.92，其中一条是：biscuits=t frozen foods=t fruit=t total=high ==> bread and cake=t，图3.1显示一、二、三、四、五、六级频繁项目集在最小支持度为0.1的情况下分别有44，380，910，633，105，1个。
观察图3.3可以看到，相比较于图3.1，结果图中展示出了各级频繁项目集的详细信息。观察图3.1和3.2两种挖掘算法的结果图，可以看出两个算法在数据集以及设置参数一样的情况下，挖掘出的关联规则是相同的。
在运行过程中可以观察到在用Apriori算法挖掘关联规则时，程序右下方的小鸟动了3-4次，而FP-Tree算法挖掘时，小鸟只动了1次。小鸟动的次数直观的体现出程序的运行时间，由此可见在用Apriori做关联规则挖掘时要比FP-Tree算法多耗费2-3倍的时间。但又由图3.1，图3.3可以看出，Apriori挖掘出的结果信息可根据需求得到更详细的信息。

表格数据实验过程

1. 文件生成与编辑

将已给数据集进行处理，如图1.1所示，并将该数据集写入到csv文件中。

图1.1 处理后的数据集 用weka的open file导入处理后的数据集，如图1.2所示。

图1.2 打开处理后的数据集

看到数据集的文字部分是乱码的。打开weka安装目录，找到RunWeka.ini配置文件，找到fileEncoding=Cp1252，改成fileEncoding=Cp936（图1.3），点击保存关闭，再重新打开weka即可。

图1.3 修改配置文件

重新打开weka，并导入数据，如图1.4所示，可看到中文显示正常。

图1.4 重新的打开数据集

2. 参数设置说明

设置最小支持度下界为0.4，最小置信度为0.6，挖掘规则数为10。
Apriori方法参数设置如图2.1所示。

图2.1 Apriori方法参数设置

FP-tree方法参数设置如图2.2所示。

图2.2 FP-tree参数设置

3. 结果截图

参数设定完成后单击start按钮，weka开始进行关联规则分析，Apriori算法结果如图3.1所示，FP-tree算法结果如图3.2所示。

图3.1 Apriori方法结果

图3.2 FP-tree方法结果

4. 结果分析

观察图3.1，可以看到用Apriori算法挖掘出一、二、三级频繁项目集分别为4，5，2个，没有生成四级频繁项目集。挖掘出两条置信度最大为1的强关联规则，分别为：啤酒 -> 尿布；牛奶，啤酒 -> 尿布。
观察图3.2，可以看到用FP-tree算法挖掘出7条强关联规则，其中有一条置信度最大为1的强关联规则为：啤酒 -> 尿布。

想必大家都听说过美国沃尔玛连锁超市“啤酒与尿不湿”的故事。为什么沃尔玛超市里会把婴儿的尿不湿和啤酒摆放在一起售卖呢？ 

因为超市发现尿不湿和啤酒的购买峰值曲线有极大的相似性，观察得知，美国家庭中母亲在家照顾孩子，就会让父亲下班后买尿不湿回家，而男士来到超市后习惯于给自己买上一罐啤酒。那么如果将啤酒放在尿不湿附近，将有很大概率提高啤酒的销售量。实践证明的确如此。

其实，这种通过研究已经产生的数据，将不同标的关联起来并挖掘二者之间联系的分析方法，就叫做关联分析法，也就是商场和电商领域的“购物篮分析”。

而这种数据关联的分析思维不仅仅可以使用在商品的售卖方面，研究的对象包含范围越广，表面上没有什么相关性、但是实际上有潜在的内关联价值的事物就越多。透过数据去挖掘这些关联规则就可以让商家制定相应的营销策略来提高销售量、让交通部门调整交通信号时长来治理交通、让政府制定有针对性的政策来促进经济等等。

今天小亿就来说说什么是关联分析，关联分析可以应用在哪些地方，以及如何做好商品的关联分析。

一、什么关联分析？

关联就是反映某个事物与其他事物之间相互依存关系，而关联分析是指在交易数据中，找出存在于项目集合之间的关联模式，即如果两个或多个事物之间存在一定的关联性，则其中一个事物就能通过其他事物进行预测。通常的做法是挖掘隐藏在数据中的相互关系，当两个或多个数据项的取值相互间高概率的重复出现时，那么就会认为它们之间存在一定的关联。

换句话说，两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。简单地来说，关联规则可以用这样的方式来表示：A→B，其中A被称为前提或者左部(LHS)，而B被称为结果或者右部(RHS)。如果我们要描述关于尿布和啤酒的关联规则（买尿布的人也会买啤酒），那么我们可以这样表示：买尿布→买啤酒。

关联规则是数据挖掘中的一个重要分支，其主要研究目的是从各种数据集中发现模式、相关性、关联或因果结构。关联规则有形如X→YX→Y 的蕴含表达式，其中X和Y是不相交的项集，即X∩Y=∅X∩Y=∅。

二、关联分析可以应用在哪些地方？

一些行业的关联规则十分清晰，例如人口普查、医疗诊断、甚至人类基因组中的蛋白质序列。在关联销售宝贝的价格规律，卖家改进关联营销策略方面，关联分析法的适用性尤为突出。

关联销售在具体营销操作中，往往会使用一种商品作为引入商品，另一种商品作为利润商品，营销人员往往会认为引入商品应当是低价的一种，那么是否女装类目中存在此类规律呢？

如果将关联比例大于10%的关联商品和结果商品的类目均价互相比较，就会发现既有用半身裙、小背心、雪纺衫之类的相对低价商品，关联至衬衫、裤子、连衣裙等相对高价商品的记录，也有用衬衫、短外套、连衣裙、西装等相对高单价商品，关联至裤子、连衣裙、T恤等相对低单价商品的记录，而且两种情况的数量基本一致。该分析结果告诉我们，至少在女装类目中，关联销售更多是基于买家的内在需求以及商品的性质、特征等而出现，并没有什么特定的低价导入、高价关联之类的规律存在。

在今天主要探讨的商品销售这个目标上，“超市购物篮”数据的研究可以作为研究关联规则挖掘的一个典型的例子。不仅在线下超市，电商卖家的“满就送”、“多加一件包邮”等形式促销，也是商品关联销售思维演化来的。

但他们忽略了关联销售最重要的一个环节 ，就是消费者心理最想要什么东西，以及可以接受的心理价位是什么？这就需要对大量商品记录数据做分析，提取出能够反映顾客偏好的有用的规则。

如今疫情尚没有宣告终结，超市门店生意仍处困境，线上流量红利竞争持续，竞争的层面也在不断深化，已经从最基本的增加PV、提升PR、制造爆款……扩展到提升客单价、重购率，培养核心客户群、打造私域流量等方面。在这样的情况下，做好关联分析就会让你的企业在竞争中多一个抓手。具体而言，他可以帮助店铺实现以下营销目的：

1.提升页面浏览率：由于同一页面中会涉及到多个商品，当这些商品的关联性较强时，就会有效提升该页面以及其关联商品页面的PV。

2.给用户提供更多选择：一个消费者不管通过什么流量渠道进入店铺商品页都会有一定原因，而提供其真正具有购买需求的关联商品信息无疑会增加客户浏览的时间，给客户提供更多的选择，从而大大增加留住客户的比率，而这也就意味着更高的转化率和客单价！

3.提升利润商品的展现机会：现在电商卖家对做爆款是又爱又恨，爱的是他能带来流量，恨的是他带走了利润，其实，只要做好关联销售，将爆款商品和利润商品有效组合起来，就能获得流量和利润的双丰收！

除此以外，关联技术不但在商业领域被广泛应用，在医疗、保险、电信和证券等领域也得到了有效的应用。

三、如何依据数据做好关联分析？

1.关联规则的常用指标

分析事物关联关系需要将众多复杂的线索的拆解清晰，量化为对工作有用的指标，在关联分析的最开始，我们往往需要关注以下指标：

（1）支持度

在关联算法中很重要的一个概念是支持度(Support)，也就是数据集中包含某几个特定项的概率。比如在1000次的商品交易中同时出现了啤酒和尿布的次数是50次，那么此关联的支持度为5%。

支持度是指A商品和B商品同时被购买的概率，或者说某个商品组合的购买次数占总商品购买次数的比例，用图表示就是两者之间的交集。

其算法公式是：S=F[（A&B）/N]

其中S代表支持度，F代表概率函数，A&B代表购买了A且购买了B的次数，N代表购买总次数。

比如今天共有10笔订单，其中同时购买牛奶和面包的次数是6次，那么牛奶+面包组合的置信度就是6/10=60%

（2）置信度

和关联算法很相关的另一个概念是置信度(Confidence)，也就是在数据集中已经出现A时，B发生的概率，置信度的计算公式是：A与B同时出现的概率/A出现的概率。

置信度是指购买A之后又购买B的条件概率，简单说就是因为购买了A所以购买了B的概率，用图表示就是交集在A中的比例。

其算法公式是：C=F（A&B）/F（A）

其中C代表置信度，F表示条件概率，A&B代表购买了A且购买了B的次数，A代表购买A的次数。

比如今天共有10笔订单，其中购买A的次数是8，同时购买A和B的次数是6，则其置信度是6/8=75%

（3）提升度

提升度是先购买A对购买B的提升作用，用来判断商品组合方式是否具有实际价值，换句话说，就是看组合商品被购买的次数是否高于单独商品的购买次数，大于1说明该组合方式有效，小于1则说明无效。

其算法公式是：L=S（A&B）/[S（A）*S（B）]

其中L代表提升度，S（A&B）代表A商品和B商品同时被购买的支持度，S（A）*S（B）代表商品A被购买的概率与B被购买概率的乘积

比如今天共有10笔订单，购买A的次数是8，购买B的次数是4，购买A+B的次数是6，那么提升度是0.6/（0.8*0.4）>1，因此A+B的组合方式是有效的。

2.关联规则的分类

（1）根据规则中所处理的变量的类型，关联规则可以分为布尔型和数值型

布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型关联规则可以对数值型字段，原始数据进行处理，包含多种类型的变量。例如：性别=“女”=>职业=“会计” ，是布尔型关联规则；性别=“女”=>avg（收入）=3000，涉及的收入是数值类型，所以是一个数值型关联规则。

（2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则

在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。

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

在单维的关联规则中，我们只涉及到数据的一个维，处理单个属性中的一些关系，如用户购买的物品。多维的关联规则中要处理的数据将会涉及多个维，处理各个属性之间的某些关系。例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品是单维的关联规则；性别=“女”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是多维的一条关联规则。

3.关联规则挖掘的相关算法

我们都知道，做数据分析的目的就是找到数据之间的关联和联系，而对于产品或商品来说，我们的目的是找出顾客购买行为的模式，比如说用户买了A商品，是否会对B商品产生什么影响；比如用户今天的购买行为，会不会对明天的销售量带来影响；比如不同的用户是否具有不同的购买模式等等。而这种挖掘方式要基于一定的规则，这个规则就是进行关联分析的算法

（1）Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。

算法的基本思想：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样；然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。

（2）AprioriTid算法

AprioriTid算法对Apriori算法做了调整，它的特点是在第一次遍历数据库D之后，就不再使用数据库来计算支持度，而是用集合Ck来完成。

基本思想：跟Apriori算法的步骤基本相同，只是在第一次通过之后，数据库不用于计算候选项集；生成另一个集合C'，其中每个成员具有每个事务的TID以及该事务中存在的大项集，这个集用于计算每个候选项集。

（3）SETM算法

基本思想：候选项目集在扫描数据库时即时生成，但在通过结束时计算，新的候选项集生成事务的TID与候选项集一起保存在顺序结构中；结束时，通过聚合该顺序结构来确定候选项集的支持计数。

（4）FP-tree算法

FP-tree算法又称FP-Growth算法，是在不使用候选代的情况下查找频繁项集的另一种方法，从而提高了性能。其核心是使用名为频繁模式树（FP-tree）的特殊数据结构，保留了项集关联信息。

基本思想：首先压缩输入数据库，创建一个FP树实例来表示频繁项；然后将压缩数据库分成一组条件数据库，每个条件数据库与一个频繁模式相关联；最后将每个数据库进行单独挖掘。

四、关联分析的步骤拆解

1.从原始资料集合中找出所有高频项目组(LargeItemsets)

高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一 水平。以一个包含A与B两个项目的2-itemset为例，我们可以求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度 (MinimumSupport)门槛值时，则{A,B}称为高频项目组。

一个满足最小支持度的k-itemset，则称为高频k-项目组 (Frequentk-itemset)，一般表示为Largek或Frequentk。算法并从Largek的项目组中再试图产生长度超过k的项目集 Largek+1，直到无法再找到更长的高频项目组为止。

2.产生关联规则

从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小可信度(MinimumConfidence)的条件门槛下，若一规则所求得的可信度满足最小可信度，则称此规则为关联规则。

例如：经由高频k-项目组{A,B}所产生的规则，若其可信度大于等于最小可信度，则称{A,B}为关联规则。

就“啤酒+尿布”这个案例而言，使用关联规则挖掘技术，对交易资料库中的记录进行资料挖掘，首先必须要设定最小支持度与最小可信度两个门槛值，在此假设最小 支持度min-support=5%且最小可信度min-confidence=65%。因此符合需求的关联规则将必须同时满足以上两个条件。若经过挖掘 所找到的关联规则{尿布，啤酒}满足下列条件，将可接受{尿布，啤酒}的关联规则。用公式可以描述为：

Support(尿布，啤酒)≥5%andConfidence(尿布，啤酒)≥65%

其 中，Support(尿布，啤酒)≥5%于此应用范例中的意义为：在所有的交易记录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行 为。Confidence(尿布，啤酒)≥65%于此应用范例中的意义为：在所有包含尿布的交易记录资料中，至少有65%的交易会同时购买啤酒。

因此，今后若有某消费者出现购买尿布的行为，我们将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据{尿布，啤酒}关联规则而定，因为就过去的交易记录而言，支持了“大部分购买尿布的交易，会同时购买啤酒”的消费行为。

从上面的介绍还可以看出，关联规则挖掘通常比较适用于记录中的指标取离散值的情况。

如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化(实际上就是将某个区间的值对应于某个值)，数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。

五、案例分享

如今关联规则挖掘的应用领域非常多，但凡需要分析事物和事物间的频繁模式的场景，都可以用到关联规则挖掘。

这项技术在一些众所周知的行业有了许多成熟应用，例如：电商或零售业的商品推荐、百度文库推荐相关文档、医疗推荐可能的治疗组合、生物研究中，发现有毒植物的共性特征，识别有毒植物、银行推荐相关联业务、搜索引擎推荐相关搜索关键词、门户网站通过点击流分析热点新闻。

最终目标是为运营策略提供依据、为数据决策提供佐证等等，但这不仅仅不要分析师有关联性思维，也需要在终端上确确实实的看到数据的关联性呈现。这里我们以一站式数据分析平台亿信ABI为例，来给大家分享关联分析的具体步骤：

1.准备数据

我们准备了某超市的一些购物篮数据。该数据集有7个字段。根据关联规则的挖掘特性，需要选择一个事务字段和一个事项字段。不然发现，CARD_NO(卡号)字段同一卡号购买过多种不同商品，可作为事务字段，而GOODS(购买商品)字段可作为事项字段。另外，界面信息显示，该数据集有2800条购买数据，由939个客户(卡号)购买了11种不同商品，符合“经常同时购买”的特征。接下来我们开始用数据集训练一个合适的关联规则模型。

2.训练模型

先创建一个挖掘过程，选择关联规则FP-Growth进入挖掘过程界面。系统内置了两种关联规则算法，他们的参数设置都一样。我们选择性能较好的FP-Growth算法。再选择“购物篮”数据集，选择CARD_NO字段为事务字段，GOODS字段为项字段，设置所有数据参与挖掘(100%抽样)。最低支持度设置为5项，最小可信度设置为40%。注意，这两个参数设置过大，可能挖掘不出关联规则，可根据实现情况调整。点击”训练模型”菜单查看训练出来的关联规则。

如上图所示，该模型挖掘到了100条关联规则。每条关联规则左边代表。系统虽然内置了FP-Growth和Apriori两种挖掘算法，而且操作方法一样，但它们还是存在以下特点：

（1）Apriori算法效率较低，计算过程中需要多次扫描整个数据集，占用较多的内存和计算时间；

（2）FP-Growth算法效率较高，只需要扫描两次数据集，占用更少的内存和计算时间。但对于长事务(同一事务，很多事项)，会造成FP树深度过大，计算时间显著增加。

所以在选择算法时，绝大部分情况下，可以优先选择FP-Growth算法。

3.模型应用

关联规则模型的应用同其它类型的挖掘模型，也是要先发布选择好的关联规则模型，再制作相应的模型应用用于关联规则的显示和查询。这里就不重复讲解了。

从购物篮分析到关联规则挖掘 Apriori算法

​ 随着大量数据不断的收集和存储，许多业界人士对于从他们的数据库中挖掘知识越来越感兴趣。对于商场而言，从大量的商务事务记录中发现有价值的的关联关系，可以为货物摆放和分析顾客购物习惯等许多商务决策过程提供帮助。

购物篮分析

​ 购物篮分析是一个典型的关联规则挖掘实例，例如如下图所示的9次购物中不同顾客购物篮中的商品，以此可以分析商品之间的关联和顾客的购物习惯，可以分析顾客可能会在一次购物中同时购买哪些商品。

​ 一种简单的分析策略是通过搜索上述9个购买事务中的商品集合，那些经常出现在同一个商品集合中的商品可以认为他们之间存在关联关系，有很大概率会被顾客同时购买。

频繁项集

​ 为了便于分析，我们为商品引入数字ID，购买事务也用事务编号代替，上述9个购买事务用数字化表示如下表所示：

​ 同时，我们引入一些基础概念：

• 项集 itemset：在购物篮分析中一个购买事务就是一个项集，购物篮中的商品就是该项集的项 ， 包含 k 个项的项集称为 k 项集
• 频度/支持度计数 support_count：包含指定项集的事务数称为支持度计数，在购物篮分析中指的是同一个商品集合出现的次数
• 频繁项集 frequent itemset：满足最小支持度阈值的项集称为频繁项集，在购物篮分析中即为多次出现且满足最小频度的商品集合。

​ 我们预设频繁项集的最小频度为2，可以直观的看出 $I1,I2,I3$ 和 $I1,I2,I5$ 被同时购买的次数是2，所以这两种商品组合可以被视为频繁项集，且这些商品之间可能存在关联关系。

关联规则

​ 频繁项集中的项可能存在关联关系，如何得出这种关系呢？一种简单的关联关系分析方法就是计算商品组合之间的条件概率，以 $I1,I2,I5$ 为例得出商品之间关系过程如下：

​ 我们考虑最小条件概率为 80% 的购买模式才被视为有效的关联关系，则只有第 3 条、第 5 条和第 6 条是有效的商品关联关系。对应到商品就是： 麦片 > (牛奶，面包)；(牛奶，麦片) > 面包； (面包，麦片) > 牛奶。

​ 上面得到的这种商品的购买模式可以用关联规则的形式表示，例如：(牛奶，麦片) > 面包： { I 1 , I 5 } = > I 2 \left\{I1, I5\right\} => I2 {I1,I5}=>I2 可以使用如下的关联规则表示：
{ I 1 , I 5 } = > I 2 [ s u p p o r t = 22 % ; c o n f i d e n c e = 100 % ] \left\{I1, I5\right\} => I2[support = 22\%; confidence = 100\%] {I1,I5}=>I2[support=22%;confidence=100%]
​ 其中，关联规则的支持度 support 和置信度 confidence 是规则兴趣度的两个度量：

• 支持度 support：支持度是指事件 A 和事件 B 同时发生的概率，即联合概率：

$$support(A=>B)=P(AB)=\frac{support\_count(A\bigcap B)}{support\_count(all)}$$

• 置信度 confidence：置信度指的是发生事件 A 的情况下发生事件 B 的概率，即条件概率：

$$confidence(A=>B)=P(B|A)=\frac{support\_count(A\bigcup B)}{support\_count(A)}$$

• 强规则：同时满足预定义的最小支持度 (min_𝑠𝑢𝑝𝑝𝑜𝑟𝑡)和最小置信度 (min_𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒)的规则称为强规则。

关联规则挖掘步骤

1. 找出所有的频繁项集：这些项集的每一个频繁出现的次数大于等于预定义的最小支持度计数(min_𝑠𝑢𝑝𝑝𝑜𝑟𝑡_𝑐𝑜𝑢𝑛𝑡)
2. 由频繁项集产生强关联规则：这些规则必须同时满足预定义的最小支持度(min_𝑠𝑢𝑝𝑝𝑜𝑟𝑡)和最小置信度(min_𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒)

Apriori 算法

​ 超市中的商品种类数以万计，假设我们要分析其中 100 种商品的关联关系那这一百种商品可以构成的项集数目如下：

​ 可见随着项数目的增加，项集的数目是呈指数级增长的，这将带来极大的计算和存储问题。为了提高频繁项集的搜索效率，Apriori 算法使用一种称为先验性质的重要性质用于压缩搜索空间。

• 先验性质描述为：频繁项集的所有非空子集也一定是频繁的。
• 先验性质的逆否命题： 如果一个项集是非频繁的，那么它的所有超集也都是非频繁的。

​ 如下图所示，例如项集 { I 1 , I 2 } \left\{I1,I2\right\} {I1,I2}是非频繁的，那么它的超集 { I 1 , I 2 , I 3 } , { I 1 , I 2 , I 4 } , { I 1 , I 2 , I 3 , I 4 } \left\{I1,I2,I3\right\},\left\{I1,I2,I4\right\},\left\{I1,I2,I3,I4\right\} {I1,I2,I3},{I1,I2,I4},{I1,I2,I3,I4}都是非频繁项集，采用这种性质可以大幅度的压缩频繁项集的产生和计算。

Apriori 算法原理

​ 如下图所示，Apriori 算法是一种逐层搜索的迭代方法，使用 k 项集去搜索 k+1 项。首先， 生成频繁 1 项集： 扫描数据库，累计每个项的计数，收集满足最小支持度的项形成频繁 1 项集记为 𝐿1。然后，基于 𝐿1找出频繁 2 项集记为 𝐿2 基于𝐿2找出频繁 3 项集记为 𝐿3，如此逐层迭代搜索，直到不能在产生新的频繁 k 项集。

​ Apriori 算法中除了第一层频繁项集挖掘，后面的逐层迭代都由以下两个步骤组成：

连接步生成候选项集集合

​ Apriori 算法在每一层搜索迭代中，通过将上一层频繁项集的集合 𝐿_𝑘−1与自身连接产生候选 k 项集的集合 𝐶𝑘。

​ 𝐿_𝑘−1中频繁项集 𝑙1 和 𝑙2 可连接的条件是： 𝑙1 和 𝑙2 的 k-2 个项是相同的。

剪枝步生成频繁项集集合

​ 连接步生成的候选 k 项集的集合 𝐶𝑘 是待求的频繁 k 项集集合 L𝑘的超集。从 𝐶𝑘 中找出频繁项集需要反复扫描数据库，确定 𝐶𝑘 中每个候选的计数，并根据最小支持度确定 L𝑘。
​ 当事务中项的数目很大时，将产生巨大的搜索空间，为了压缩 𝐶𝑘，使用先验性质对 𝐶𝑘 进行剪枝。即任何非频繁的 k-1 项集都不是频繁 k 项集的子集。所以，如果一个候选 k 项集的 k-1 项子集不在 L_𝑘-1 中，则该候选是非频繁的并从 𝐶𝑘 中剔除。

Apriori 算法实例

​ 基于前面购物篮分析例子中的 9 个事务，使用 Apriori 算法挖掘频繁项集。预设最小支持度为 20% 即最小支持度计数大于等于 2 ，最小置信度为 80%。

1. 挖掘频繁 1 项集：扫描数据库 D 中的所有事务，对每一个项的出现次数计数，得到候选 1 项集集合 𝐶1，根据最小支持度 20% 即最小支持度计数为 2 确定频繁 1 项集集合 𝐿1。

2. 挖掘频繁2项集：首先，连接步： 将频繁 1 项集集合中的元素进行连接产生候选 2 项集集合 𝐶2。然后，剪枝步： 𝐶2 中所有候选的子集都是频繁的，所以不删除任何候选。最后，确定频繁项集 ：扫描数据库 D 中的所有事务，对 𝐶2中的每一个候选项集的出现次数计数 ，根据最小支持度确定频繁 2 项集 𝐿2。

3. 挖掘频繁3项集：首先，连接步： 将频繁 2 项集集合中的元素进行连接产生候选 3 项集集合 𝐶3。然后，剪枝步： 检查 𝐶3 中候选项集的子集是否都是频繁的，如果存在非频繁的子集，将该候选项集从 𝐶3 中删除。最后，确定频繁项集 ：扫描数据库 D 中的所有事务，对 𝐶3 中的每一个候选项集的出现次数计数 ，根据最小支持度确定频繁 3 项集 𝐿3。

4. 停止寻找频繁项集： { I 1 , I 2 , I 3 } \left\{I1,I2,I3\right\} {I1,I2,I3} 和 { I 1 , I 2 , I 5 } \left\{I1,I2,I5\right\} {I1,I2,I5} 连接的唯一个候选项集是 { I 1 , I 2 , I 3 , I 5 } \left\{I1,I2,I3,I5\right\} {I1,I2,I3,I5}，但是其子集 { I 1 , I 3 , I 5 } \left\{I1,I3,I5\right\} {I1,I3,I5}和 { I 2 , I 3 , I 5 } \left\{I2,I3,I5\right\} {I2,I3,I5} 都是非频繁的，该候选项集将被剪去得到的候选 4 项集集合 𝐶4 为空，算法终止。所以最终得到的最大频繁项集是 { I 1 , I 2 , I 3 } \left\{I1,I2,I3\right\} {I1,I2,I3} 和 { I 1 , I 2 , I 5 } \left\{I1,I2,I5\right\} {I1,I2,I5} 。

5. 由频繁项集产生关联规则：关联规则产生，首先，对于每个频繁项集 𝑙，产生 𝑙的所有非空子集集合 𝑆；然后，对于 𝑙的每个非空子集 𝑠, 𝑙 在 𝑠下的条件概率满足最小置信度 (min_𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒) 则可以输出规则 𝑠⇒(𝑙−𝑠)，这个规则是满足最小支持度和置信度的强规则。
   

Apriori 算法Python实现

# 产生频繁1项集
def scanD(D, Ck,minSupport) :#识别频繁项目集
    S = {}
    for i in D:
        for j in Ck:
            if j.issubset(i): 
                if j not in S.keys():
                    S[j] = 1
                else:
                    S[j] += 1
    numItems = float(len(D)) 
    L= []
    N=[]
    supportData = {} #候选集项Ck的支持度字典(key:候选项，value: 文持度)
    for key in S:
        support = S[key] / numItems
        supportData[key] = support
        if support >= minSupport:
            L. append(key)
        else:
            N.append(key)
    return L,N,supportData

# Apriori算法 连接步和剪枝步
def aprioriGen(Lk,k,N):
    Ck=[]
    lenLk = len(Lk)
    for i in range(lenLk):
        # 连接步 (子连接运算)
        for j in range(i + 1,lenLk):
            L1 = list(Lk[i])[:k - 2]
            L1.sort()
            L2 = list(Lk[j])[:k - 2]
            L2.sort()
            if L1==L2:
                Ck.append(Lk[i]|Lk[j])#加入并集
        # 剪枝步 把子集中有属于非频繁项目集的项目删掉
        for i in N:
            for j in Ck:
                if set(i).issubset(j):
                    Ck.remove(j)                   
    return Ck

# Apriori算法 逐层迭代
def apriori(D,minSupport):
    C1 = createCl(D)
    L1,N,supportData = scanD(D,C1,minSupport)
    L=[L1]
    k=2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2],k,N)
        Lk,Nk,supK = scanD(D,Ck,minSupport)
        supportData.update(supK)
        N += Nk
        L.append(Lk)
        k +=1
    return L,N,supportData

Apriori 算法改进

Apriori 仍可能产生大量的候选集

​ Apriori 算法虽然通过剪枝在很大程度上压缩了候选项集集合，但是在逐层迭代搜索过程中，如果要生成一个很长的规则，这将产生大量的中间元素，仍然会产生大量的候选集，需要大量的计算和存储资源。

使用哈希函数生成候选集

​ 在基于 𝐿𝑘−1生成候选项集集合 𝐶𝑘时，直接使用哈希函数生成候选项集，达到压缩候选项集目的。
​ 例如上述 Apriori 实例中由 𝐿1生成候选项集集合 𝐶2 时，使用如下哈希函数创建哈希表：
$$h(x,y)=(10x+y)mod7$$
​ 如果预设最小支持度计数为 3 ，则哈希地址为 0 、 1 、 3 、 4 中的候选项集都不可能是频繁的直接被剔除。

频繁模式增长算法 FP-growth

​ FP-growth 算法直接避免了繁杂而开销巨大的候选项集生成过程，采用如下分治策略：
​ (1) 首先，将代表频繁项集的数据库压缩到一棵频繁模式树 FP-Tree
​ (2) 然后，把这种压缩后的数据库划分成一组条件数据库 ，每个数据库关联一个频繁项或模式段，并分别挖掘每个条件数据库。对于每个模式段只需要考察与它相关联的数据集。随着被考察模式的增长，这种方法可以显著地压缩被搜索的数据集大小。

1. 构造频繁模式树 FP-tree ：首先，导出频繁 1 项集集合 𝐿，且将该频繁 1 项集集合按支持度计数降序排序 。然后，依据 𝐿构造频繁模式树，先创建树的根节点，用 null 标记；接着扫描数据库，将每个事务的项集中的项按 𝐿 的次序创建节点，并对每一个事物创建一个分枝。

2. 从FP-tree中挖掘频繁模式：从初始后缀模式即长度为1 的频繁模式开始挖掘，构造一个由 FP-tree 中与该后缀模式一起出现的前缀路径集组成的子数据库，称为该频繁模式的条件模式基。然后，构造该频繁模式的条件 FP-tree ，并递归地在该树上挖掘频繁模式。模式增长通过后缀模式与条件FP-tree产生的频繁模式连接实现。

Apriori 会产生大量虚假的关联规则

​ Apriori 算法衡量和生成关联规则的标准主要有两个，即支持度和置信度。但仅用这两个标准来衡量关联规则，往往会发现大量冗余的、虚假的关联规则。例如，有 10 个购物事物中有 6 个包含购买可口可乐的事物，有 7 个包含购买百事可乐的事务，同时包含购买可口可乐和百事可乐的事务有 4 个。预设最小支持度为 30%，最小置信度为 60%，使用 Apriori 算法可以得到如下关联规则：

​ 事实上可口可乐和百事可乐的购买事务是负相关的，买一种会降低另一种被购买的可能性，所以这个关联规则是虚假的。

​ 可以看出仅仅使用支持度和置信度不足以过滤掉冗余的和虚假的关联规则。为此，可以使用相关性度量来扩充关联规则的支持度-置信度框架。加入了相关性度量的关联规则称为相关规则用如下形式表示：
$$A=>B[support,confidence,correlation]$$
​ 常用的相关性度量由：

1. 提升度：提升度是一种简单的相关性度量，如果值小于 1 表示 A 的出现和 B 的出现是负相关的，如果值大于 1 表示两者是正相关的，如果值等于 1 表示 A 和 B 是独立的，两者不具有相关性 。

2. 卡方检验：卡方检验也可以用于相关性度量通过表示实际观测值 (𝑎)与理论推断值 (𝑝)之间的偏离程度即卡方值大小来表示相关性 。 如果卡方值越大二者偏差程度越大呈负相关，反之二者偏差越小呈正相关，若两个值完全相等时，卡方值就为 0 表明理论值完全符合 表示事件互相独立 。

Apriori 对稀有信息分析效果差

​ Apriori 的频繁项集挖掘是基于最小支持度实现的，然而可能有一些有价值的规则的支持度小于这一预设的最小支持度或由于数据量较少无法正确生成相关规则。对于这种数据不平衡的情况，需要尽量减少事务总数的评估影响。

​ 零事务，提升度和卡方检验都受到被分析事务总数的影响，例如有102100 个事务中，可口可乐百事可乐被同时购买的事务有 100 个，可口可乐被单独购买的事务 1000 个，百事可乐被单独购买的事务有 1000 个。这个数据计算出来的提升度和卡方值都出现正关联错误评估。这是由大量的不包含那些考查项集的事务影响造成的，这些事务称为零事务 。实际情况中零事务的个数往往比被考察事务个数大很多。

​ 可以使用不平衡比来评估两个项集的不平衡程度，不平衡比值越大说明两个项集不平衡情况严重，若不平衡比值为 0 说明其平衡情况较好 ，计算公式如下：

​ 常用的零不变性度量如下所示：

完整Apriori算法 PPT 和 Python 实现代码下载地址：下载地址