Aprior算法原理与实现|机器学习

引言

关联规则挖掘是数据挖掘中最活跃的研究方法之一 。最早由 Agrawal 等人在1993年提出。
最初的动机是用以解决“购物篮分析问题”，发现交易数据库中不同商品之间的关联规则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货，库存以及货架设计等。

之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作涉及到关联规则的挖掘理论的探索，原有的算法的改进和新算法的设计，并行关联规则挖掘(Parallel Association Rule Mining)，以及数量关联规则挖掘(Quantitive Association Rule Mining) 等问题。

在提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面，许多学者进行了不懈的努力。

相关概念

项与项集

设$ItemSet=\{item_1, item_2, …, item_n\}$是所有项的集合，其中，$item_k(k=1,2,…,n)$称为项；项的集合称为项集（$ItemSet$），包含$k$个项的项集称为$k$项集（$k-itemset$）。

事务与事务集

一个事务（又称：交易）$T$是一个项集，它是$ItemSet$ 的一个子集，每个事务均与一个唯一标识符$Tid$ 相关联；不同的事务一起组成了事务集$D$，它构成了关联规则发现的事务数据库。

关联规则

关联规则是形如$A\to B$ 的蕴涵式；

其中A、B均为$ItemSet$的子集且均不为空集，且$A\cap B=\varnothing$

支持度 (support)

关联规则的支持度定义如下：

$$\begin{aligned} \text{Support}(A)&=\frac {\#(A)}{|D|}\\ \text{Support}(A\to B)&=P(A,B)=\frac {\#(A,B)}{|D|} \end{aligned}$$

其中，$\#(·)$ 表示包含项集的事务数，简记为项集的频度或计数.

置信度 (confidence)

$$\text{Confidence}(A \to B)=P(B|A)=\frac{P(A , B)}{P(A)}=\frac{\#(A , B)}{\#(A)}$$

提升度 (lift,或兴趣度 interest )

$$\text{Lift}(A\to B)=\frac{P(A, B)}{P(A)P(B)}=\frac{P(B|A)}{P(B)}$$

强关联规则

若对关联规则：$A\to B$，有$Support(A\to B)\ge SupMin$，且$Confidence(A\to B)\ge ConfMin$

则称该关联规则为强关联规则，否则为弱关联规则。

其中，$SupMin$是关联规则的最小支持度，用于衡量规则需要满足的最低重要性；

$ConfMin$是关联规则的最小置信度，表示关联规则需要满足的最低可靠性.

算法步骤

算法思路

大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：

• 频繁项集产生（Frequent Itemset Generation）：发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。
• 强关联规则的产生（Rule Generation）：从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则。

---

根据上述概念，我们可以很直观地得出如何进行挖掘。

以商品购买为例，假设一家商店，出售5种商品，分别为商品A，B，C，D，E。希望通过挖掘买家购买商品的订单数据，来进行商品之间的组合促销或者说是摆放位置，那么我们需要怎么做呢？

Step1:对商品进行抽象表示，即是设$ItemSet=\{A,B,C,D,E\}$；

Sept2:枚举所有可能的购买组合，即是找出属于$ItemSet$的所有项集，得到数据库。一般我们用 “格结构”（Lattice structure）表述；

Step3:遍历所有可能项集，通过计算对应的$Support(·)$与设定好的$SupMin$从而得到频繁项集；

Step4:遍历所有频繁项集，通过计算对应的$Confidence(·)$与设定好的$ConfMin$从而得到强规则。

重要性质/剪枝

在上述算法步骤中，我们很容易发现遍历所有的可能项集是十分“暴力”的，当商品数很多的情况下很容易出现 组合爆炸 的情况。

因此，在Aprior算法中，提出了如下性质或称先验原理：

• 性质1：如果一个集合是频繁项集，则它的所有子集都是频繁项集
  • 如$\{X,Y,Z\}$是频繁项集，则$\{X,Y\}、\{X,Z\}、\{Y,Z\}$等项集也是频繁的
• 性质2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集
  • 如$\{X\}$不是频繁项集，则有$Support(X) \le SupMin$，因此$P(X\to Y)\le SupMin$恒成立

---

上图表示当我们发现{A,B}是非频繁集时，就代表所有包含它的超级也是非频繁的，即可以将它们都剪除。

伪代码

样例演示

下面给出一个具体的例子，最开始数据库里有4条事务，通过将$SupMin=2$ 设为支持度阈值，最后筛选出来的频繁集为$\{B,C,E\}$。

其中，左下角$L_2$到$C_3$这一步值得注意，其实这一步就是在执行伪代码中第一个蓝色框条所标注的：$C_{k+1}=GenerateCandidates(L_k)$

其执行伪代码如下：

表示，对$L_k$ 集合中的元素（该元素也是集合）进行两两合并，即$Self-Join$，合并条件是被合并的两个集合只有一个元素不同，从而能够合并得到长度是$k+1$的新集合，从而将其作为$C_{k+1}$ 的元素之一。

而合并之后同样需要剪枝，即$Pruning$。通过判断合并出来的新集合是否有不属于$L_k$的子集来进行剪枝，如果有则将其从$C_{k+1}$中删除。

图示如下：

以上面的实例为例，$k=3$ 时，有$\begin{aligned}L_k=\left\{ \{A,B,C\},\{A,B,D\},\{A,C,D\},\{A,C,E\},\{B,C,D\} \right\}\end{aligned}$. 于是两两合并：

$$\begin{aligned} \Omega_1=\{A,B,C\}\cup\{A,B,D\}=\{A,B,C,D\}\\ \Omega_2=\{A,C,D\}\cup\{A,C,E\}=\{A,C,D,E\} \end{aligned}$$

从而有：$C_{k+1}=\{\Omega_1,\Omega_2\}$

但其中，$\Omega_1$的子集$\{B,C,D\}\in L_k$，但$\Omega_2$的子集$\{B,C,D\}\notin L_k$，我们知道如果他不属于$L_k$的话，说明他不是频繁项集，因此作为他的超集的$\Omega_2$ 就应该被剔除，所以我们要：

$$form\quad C_{k+1} \quad delete \quad \Omega_2$$

最终，$C_{k+1}=\{\Omega_1\}$.

Python实现

# 读取数据集
def loadDataSet():
    '''
    	可自定义读取数据方式，此处仅作示例
    '''
    datas =  [['l1', 'l2', 'l5'], ['l2', 'l4'], ['l2', 'l3'],
            ['l1', 'l2', 'l4'], ['l1', 'l3'], ['l2', 'l3'],
            ['l1', 'l3'], ['l1', 'l2', 'l3', 'l5'], ['l1', 'l2', 'l3']]
    return datas

# 生成初始候选项集C1
def createC1(DataSet):
    C1 = []
    # 从数据集中每一项事务(T)中提取item
    # 将其作为独立集合存入C1中
    for T in DataSet:
        for item in T:
            if not [item] in C1:
            	C1.append([item])
    # 排序C1，并返回C1的不可变列表
    C1.sort()
    return list(map(frozenset,C1))

# 通过对Ck查询与计算得到Lk
def GenerateFrequent(D,Ck,SupMin):
    numS = {} #用于统计规则的出现频次
    for Tid in D:
        for item in Ck:
            if item.issubset(Tid):
                if not item in numS:
                    numS[item] = 1
                else:
                    numS[item] += 1
                    
    numItems = float(len(D)) #保存样本总数
    Lk = []
    supportData = {}
    # 计算每个规则的支持度并保存
    for item in numS:
        support = numS[item]/numItems
        if support >= SupMin:
            Lk.insert(0,item)
        supportData[item] = support
    return Lk,supportData

# 对Lk频繁项集合并生成下一个Ck
def GenerateCandidates(Lk,k):
    Ck = []
    lenLk = len(Lk)
    # 通过i,j两个指针进行两两比较，符合则合并
    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:
                Ckitem = Lk[i]|Lk[j]
                # 剪枝
                if is_apriori(Ckitem,Lk):
                    Ck.append(Ckitem)
    return Ck

# 通过性质2判断是否为频繁项集(剪枝)
def is_apriori(Ckitem,Lk):
    for item in Ckitem:
        if Ckitem-frozenset([item]) not in Lk:
            return False
    return True

# 得到所有频繁项集all_L和支持度supportData
def aprior(DataSet,SupMin=0.2):
    C1 = createC1(DataSet) #生成C1
    D = list(map(set,DataSet)) #将每个集合内重复元素清除
    L1,supportData = GenerateFrequent(D,C1,SupMin) #获取L1和当前支持度集合
    all_L = [L1] # 保存L1
    k = 2
    # 循环计算直到Lk为空
    while(len(all_L[k-2])>0):
        Ck = GenerateCandidates(all_L[k-2],k)
        Lk,supK = GenerateFrequent(D,Ck,SupMin)
        supportData.update(supK) #更新支持度集合
        all_L.append(Lk) #更新Lk
        k += 1
    return all_L,supportData

# 获取强关联规则
def generateRules(all_L,supportData,ConfMin=0.7):
    bigRuleList = [] # 保存强关联规则
    subSetList = [] 
    # 遍历所有频繁项集
    for i in range(0,len(all_L)):
        for freqSet in all_L[i]:
            for subSet in subSetList:
                # 计算频繁项集freqSet的非空子集subSet置信度
            	if subSet.issubset(freqSet):
                    conf = supportData[freqSet]/supportData[freqSet-subSet]
                    bigRule = (freqSet-subSet,subSet,conf)
                    if conf >= ConfMin:
                        # 输出结果并保存
                        print(bigRule[0],'=>',bigRule[1],' conf:',conf)
                        bigRuleList.append(bigRule)
            subSetList.append(freqSet)     
    return bigRuleList

if __name__=='__main__':
    DataSet=loadDataSet()
    L,supportData=aprior(DataSet)
    bigRules = generateRules(L,supportData)

参考资料

1.Apriori算法详解|简书

2.Aprior算法介绍与python实现

3.【机器学习】Apriori算法——原理及代码