关联分析算法-Apyori

环境：Python 3.6.5

安装包：Apyori 和 mlxtend

其中关联规则挖掘的最经典的例子就是沃尔玛的啤酒与尿布的故事 ，通过对超市购物篮数据进行分析，即顾客放入购物篮中不同商品之间的关系来分析顾客的购物习惯，发现美国妇女们经常会叮嘱丈夫下班后为孩子买尿布，30%-40%的丈夫同时会顺便购买喜爱的啤酒，超市就把尿布和啤酒放在一起销售增加销售额。

1. 关联分析概述

关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性，是数据挖掘的一个重要技术， 用于从大量数据中挖掘出有价值的数据项之间的相关关系。这种关系表现为两种形式：

• 1.频繁项集(frequency item sets)：经常频繁同时出现的一些物品集的集合；

• 2.关联规则(association rules): 意味着两种元素之间存在很强的关系。

在频繁项集的基础上，使用关联规则算法找出其中物品的关联结果。

简单点说，就是先找频繁项集，再根据关联规则找关联物品。

为什么要先找频繁项集呢？还是以超市为例，你想想啊，我们找物品关联规则的目的是什么，是为了提高物品的销售额。如果一个物品本身购买的人就不多，那么你再怎么提升，它也不会高到哪去。所以从效率和价值的角度来说，肯定是优先找出那些人们频繁购买的物品的关联物品。

2. 基本概念

项集：“属性-值”对的集合，一般情况下在实际操作中会省略属性。
候选项集：用来获取频繁项集的候选项集，候选项集中满足支持度条件的项集保留，不满足条件的舍弃。
频繁项集：在所有训练元组中同时出现的次数超过人工定义的阈值的项集称为频繁项集。
极大频繁项集：不存在包含当前频繁项集的频繁超集，则当前频繁项集就是极大频繁项集。

关联规则（Association Rules）

 两个不相交的非空集合X、Y，如果有X->Y，就说X->Y是一条关联规则

• 强度：支持度（support）、置信度（confidence）
• 效度：提升度（Lift）

挖掘定义

给定一个数据集，找出其中所有支持度support >= min_support、自信度

confidece >= min_confidece的关联规则

2.1 支持度的计算公式

suopport(X->Y)=集合X和集合Y中的项在一条记录中同时出现的次数/数据记录的个数

例如：

support（{啤酒}->{尿布}）
= 啤酒和尿布同时出现的次数/记录数
= 3/5=60%

2.2 置信度（Confidence）

confidence（X->Y）=集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数

例如：

confidence（{啤酒}->{尿布}）
= 啤酒和尿布同时出现的次数/啤酒出现的次数=3/3=100%

confidence（{尿布}->{啤酒}）
= 啤酒和尿布同时出现的次数/尿布出现的次数
= 3/4
= 75%

2.3 提升度（Lift）

度量规则是否可用的指标，描述的是相对于不用规则，使用规则可以提高多少，提升度大于1 ，规则有效

计算公式

lift（{A-B}）=confidence({A-B})/supper(B)

例如：

lift（{尿布}->{啤酒}）
= confidence（{尿布}->{啤酒}）/support(啤酒）
= 0.75/0.6 = 1.25

• 提升度 >1 且越高表明正相关性越高;
• 提升度 <1 且越低表明负相关性越高;
• 提升度 =1 表明没有相关性。

3. Apriori算法原理

3.1 两个定理

• 连接定理。若有两个k-1项集，每个项集按照“属性-值”（一般按值）的字母顺序进行排序。如果两个k-1项集的前k-2个项相同，而最后一 个项不同，则证明它们是可连接的，即这个k-1项集可以联姻，即可连接生成k项集。使如有两个3项集：｛a, b, c｝{a, b, d}，这两个3项集就是可连接的，它们可以连接生成4项集｛a, b, c, d｝。又如两个3项集｛a, b, c｝｛a, d, e｝，这两个3项集显示是不能连接生成3项集的。要记住，强扭的瓜是不甜的，也结不了果的。
• 频繁子集定理。若一个项集的子集不是频繁项集，则该项集肯定也不是频繁项集。这个很好理解，举一个例子，若存在3项集｛a, b, c｝，如果它的2项子集｛a, b｝的支持度即同时出现的次数达不到阈值，则｛a, b, c｝同时出现的次数显然也是达不到阈值的。因此，若存在一个项集的子集不是频繁项集，那么该项集就应该被无情的舍弃。倘若你舍不得，那么这个项集就会无情 的影响你的效率以及处理器资源，所以在这时，你必须无情，斩立决！

3.2 Apriori算法流程

1、扫描数据库，生成候选1项集和频繁1项集。

2、从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。

（1） 频繁k-1项集生成2项子集，这里的2项指的生成的子集中有两个k-1项集。

    **假如如有3个2项频繁集｛a, b｝｛b, c｝｛c, f｝**，则它所有的2项子集为｛｛a, b｝｛b, c｝｝｛｛a, b｝｛c, f｝｝｛｛b, c｝｛c, f｝｝
（2） 对由（1）生成的2项子集中的两个项集根据上面所述的定理**（连接定理）**进行连接，生成k项集。
（3） 对k项集中的每个项集根据如上所述的定理 （**频繁子集定理**） 进行计算，舍弃掉子集不是频繁项集即不在频繁k-1项集中的项集。
（4） 扫描数据库，计算第3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。

3、当当前生成的频繁k项集中只有一个项集时循环结束。

关联规则挖掘是寻找给定数据集中项之间的有趣联系。如下图所示：

img

其中，I={I1,I2,…Im}是m个不同项目的集合,集合中的元素称为项目（Item）。项目的集合I称为项目集合（Itemset），长度为k的项集成为k-项集。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得 T ⊆ I 。每个事务有一个标识符TID；设A是一个项集，事务T包含A当且仅当 A⊆I ，则关联规则形式为A=>B（其中 A ⊂ I ， B ⊂ I ，并且 A ∩ B = ∅）。

如上图中数据库D，包含4个事务，项集I={I1,I2,I3,I4,I5}，分析关联规则：I1=>I4，事务1、4包含I1，事务4同时包含I1和I4。
支持度support=1/4=25%（1个事务同时包含I1和I4,共有4个事务）指 在所有交易记录中有25%的交易记录同时包含I1和I4项目
置信度confidence=1/2=50%（1个事务同时包含I1和I4,2个事务包含I1）指 50%的顾客在购买I1时同时还会购买I4

使用关联规则对购物篮进行挖掘，通常采用两个步骤进行： 下面将通超市购物的例子对关联规则挖掘进行分析。
a.找出所有频繁项集（文章中我使用Apriori算法>=最小支持度的项集）
b.由频繁项集产生强关联规则（>=最小支持度和最小置信度）

3.3 举例-挖掘频繁项集

Apriori算法是一种对有影响的挖掘布尔关联规则频繁项集的算法，通过算法的连接和剪枝即可挖掘频繁项集。 补充频繁项集相关知识： K-项集：指包含K个项的项集； 项集的出现频率：指包含项集的事务数，简称为项集的频率、支持度计数或计数； 频繁项集：如果项集的出现频率大于或等于最小支持度计数阈值，则称它为频繁项集，其中频繁K-项集的集合通常记作Lk 。
下面直接通过例子描述该算法：如下图所示（注意Items已经排好序），使用Apriori算法关联规则挖掘数据集中的频繁项集。（最小支持度技术为2）

img

具体过程如下所示：

img

具体分析结果：
第一次扫描：对每个候选商品计数得C1，由于候选{D}支持度计数为1<最小支持度计数2，故删除{D}得频繁1-项集合L1；
第二次扫描：由L1产生候选C2并对候选计数得C2，比较候选支持度计数与最小支持度计数2得频繁2-项集合L2；
第三次扫描：用Apriori算法对L2进行连接和剪枝产生候选3项集合C3的过程如下：
1.连接：
C3=L2 (连接)L2={{A,C},{B,C},{B,E},{C,E}} {{A,C},{B,C},{B,E},{C,E}}={{A,B,C},{A,C,E},{B,C,E}}
2.剪枝：
{A,B,C}的2项子集{A,B},{A,C}和{B,C}，其中{A,B}不是 2项子集L2,因此不是频繁的，从C3中删除；
{A,C,E}的2项子集{A,C},{A,E}和{C,E}，其中{A,E}不是2项子集L2，因此不是频繁的，从C3中删除；
{B,C,E}的2项子集{B,C},{B,E}和{C,E}，它的所有2项子集都是L2的元素，保留C3中.

经过Apriori算法对L2连接和剪枝后产生候选3项集的集合为C3={B,C,E}. 在对该候选商品计数，由于等于最小支持度计数2，故得频繁3-项集合L3，同时由于4-项集中仅1个，故C4为空集，算法终止。

3.4 举例-频繁项集产生强关联规则

强关联规则是指：如果规则R：X=>Y满足support(X=>Y)>=supmin(最小支持度，它用于衡量规则需要满足的最低重要性)且confidence(X=>Y)>=confmin（最小置信度，它表示关联规则需要满足的最低可靠 性）称关联规则X=>Y为强关联规则，否则称关联规则X=>Y为弱关联规则。

例：下图是某日超市的购物记录（注意Items已经排好序），使用上面叙述的Apriori算法实现了挖掘频繁项集，其中频繁项集I={i1,i2,i5}为频繁3-项集合L3，求由I产生哪些强关联规则？（最小支持度阈值为20%，最小置信度阈值为80%）

img

I的非空子集有{i1,i2}、{i1,i5}、{i2,i5}、{i1}、{i2}和{i5}。
结果关联规则如下，每个都列出置信度
1).i1 ∧i2=>i5 ,共10个事务；5个事务包含i1,i2；2个事务包含i1,i2和i5 confidence=2/5=40%，support=2/10=20%
2).i1 ∧i5=>i2 ,共10个事务；2个事务包含i1,i5；2个事务包括i1,i2和i5 confidence=2/2=100%，support=2/10=20%
3).i2 ∧i5=>i1 ,共10个事务；2个事务包含i2,i5；2个事务包含i1,i2和i5 confidence=2/2=100%，support=2/10=20%
4).i1=>i2 ∧i5 ,共10个事务；7个事务包含i1；2个事务包含i1,i2和i5 confidence=2/7=28%，support=2/10=20%
5).i2=>i1 ∧i5 ,共10个事务；8个事务包含i2；2个事务包含i1,i2和i5 confidence=2/8=25%，support=2/10=20%
6).i5=>i1 ∧i2 ,共10个事务；2个事务包含i5；2个事务包含i1,i2和i5 confidence=2/2=100%，support=2/10=20%
因最小置信度阈值为80%,最小支持度阈值为20%,则236规则符合要求,是频繁项集I={i1,i2,i5}产生的强关联规则且可以输出。

(自己的推测：如果给定的是最小支持度计数为2，则有10个事务，最小支持度阈值supmin=2/10=20%)

在实际应用中订单每天增加，我们采用增量的方式计算，去掉支持度的限制。

4. Apriori算法实战

mlxtend

我们用一个简单的例子来用一下Apriori吧，这里用到的库是mlxtend。

在放代码之前，先介绍下Apriori算法的参数吧。

def apriori(df, min_support=0.5,  
            use_colnames=False, 
            max_len=None)
参数如下：
df：这个不用说，就是我们的数据集。
min_support：给定的最小支持度。
use_colnames：默认False，则返回的物品组合用编号显示，为True的话直接显示物品名称。
max_len：最大物品组合数，默认是None，不做限制。如果只需要计算两个物品组合的话，便将这个值设置为2。

# coding:utf-8
from mlxtend.preprocessing import TransactionEncoder

from mlxtend.frequent_patterns import apriori

from mlxtend.frequent_patterns import association_rules

import pandas as pd

df_arr = [['苹果','香蕉','鸭梨'],

['橘子','葡萄','苹果','哈密瓜','火龙果'],

['香蕉','哈密瓜','火龙果','葡萄'],

['橘子','橡胶'],

['哈密瓜','鸭梨','葡萄']

]

#转换为算法可接受模型（布尔值）

te = TransactionEncoder()

df_tf = te.fit_transform(df_arr)

df = pd.DataFrame(df_tf,columns=te.columns_)

#利用 Apriori,设置支持度求频繁项集
frequent_itemsets = apriori(df,min_support=0.4,use_colnames= True)
print(frequent_itemsets)


#求关联规则,设置最小置信度为0.15
rules = association_rules(frequent_itemsets,metric = 'confidence',min_threshold = 0.15)
'''
参数介绍：
- frequent_itemsets：这个不用说，就是 Apriori 计算后的频繁项集。
- metric：可选值['support','confidence','lift','leverage','conviction']。
里面比较常用的就是置信度和支持度。这个参数和下面的min_threshold参数配合使用。
- min_threshold：参数类型是浮点型，根据 metric 不同可选值有不同的范围，
    metric = 'support'  => 取值范围 [0,1]
    metric = 'confidence'  => 取值范围 [0,1]
    metric = 'lift'  => 取值范围 [0, inf]
support_only：默认是 False。仅计算有支持度的项集，若缺失支持度则用 NaNs 填充。
'''
#设置最小提升度

rules = rules.drop(rules[rules.lift <1.0].index)

#设置标题索引并打印结果

rules.rename(columns = {'antecedents':'from','consequents':'to','support':'sup','confidence':'conf'},inplace = True)

rules = rules[['from','to','sup','conf','lift']]

print(rules)

# rules为Dataframe格式，可根据自身需求存入文件

# 也可以根据列名只展示部分数据
out_data = rules[['antecedents','consequents','support','confidence','lift']]

# 检索数据
for r in zip(out_data['antecedents'],out_data['consequents'],out_data['support'],
             out_data['confidence'],out_data['lift']):
    qy = list(r[0])
    hg = list(r[1])

# 排序查询数据
r = rules.sort_values(by = ['confidence','lift'],ascending=False)
print(r)

5. 总结

分析一下支撑指标的可行性，如下面的例子

在所分析的10000个事务中,6000个事务包含计算机游戏,7500个包含游戏机游戏,4000个事务同时包含两者。

关联规则（计算机游戏，游戏机游戏） 支持度为0.4，看似很高，但其实这个关联规则是一个误导。

在用户购买了计算机游戏后有 （4000÷6000）0.667 的概率的去购买游戏机游戏，而在没有任何前提条件时，用户反而有（7500÷10000）0.75的概率去购买游戏机游戏，也就是说设置了购买计算机游戏这样的条件反而会降低用户去购买游戏机游戏的概率，所以计算机游戏和游戏机游戏是相斥的。

在理论上 把 0.667除以0.75称为提升度，具体公式：

P(B|A)/P(B)

称为A条件对于B事件的提升度,如果该值=1,说明两个条件没有任何关联,如果<1,说明A条件(或者说A事件的发生)与B事件是相斥的, 一般在数据挖掘中当提升度大于3时,我们才承认挖掘出的关联规则是有价值的。

提升度是一种比较简单地判断手段,在实际应用中它受零事务的影响较大,零事务在本例中可以理解为既没有买计算机游戏也没有买游戏机游戏的事务,其值为 10000-4000-2000-3500=500,很小,但在现实中,这个值往往其实是很大的。如果保持其他数据不变，把10000个事务改成1000000个事务，那么计算出的提升度就会明显增大，此时的零事务很大（1000000-4000-2000-3500），可见提升度是与零事务有关的。