Apriori算法详解

1.相关概念

支持率： 一个项集$I$在事务集合 Γ = { T 1 , T 2 , … , T n } \Gamma=

$$\begin{Bmatrix}T_1,T_2,\ldots,T_n\end{Bmatrix}$$ Γ={T1​,T2​,…,Tn​​}中包含子集$I$的事务占全体事务的比例称之为支持率。

在上述事务集合中，项集{A,E}的支持率是2/5=0.4,项集{E,F}的支持率是3/5=0.6。

频繁项集挖掘： 给定一个事务的集合 Γ = { T 1 , T 2 , … , T n } \Gamma=

$$\begin{Bmatrix}T_1,T_2,\ldots,T_n\end{Bmatrix}$$ Γ={T1​,T2​,…,Tn​​}，其中每个事务$T_i$是项集总空间$U$的一个子集，从$\Gamma$中找到所有项集$I$,其中$I$满足支持率不低于预先设定的最小支持率。例如，上述事务集合中，若设定minsup=0.5,项集{E,F}和{D,E}都是频繁项集。

向下闭包性： 频繁项集的子集一定是频繁项集。下图是频繁项集的搜索树，能很好的观察到向下闭包性

这条性质非常重要，因为它的逆否命题为：若子集不是频繁的，那么超集一定不是频繁的。据此，在频繁项集的搜索过程中，可以直接丢弃非频繁的子集，那么它的所有超集都不会被搜索到，这叫搜索树的剪枝。Apriori算法采用了向下闭包性，极大的提高了挖掘效率。

2.Apriori

简述： 挖掘频繁项集在逻辑上就是搜索一颗枚举树并计算结点支持率的过程。在不知道Apriori算法的情况下，我们应该自然而然地想到暴力算法：穷举所有非空子集（$2^n-1$个），挨个计算子集的支持率看是否小于最小支持率。然而，暴力算法效率很低。不过，Apriori算法利用了向下闭包性，在逻辑上对枚举树进行了剪枝操作，当n很大时极大的减少了搜索的子集个数，提高了效率。

算法过程： 首先，生成长度为k的候选项集(k从1开始)，计算它们的支持率；然后，根据支持率生成长度为k的频繁项集，这个时候非频繁的k项集被抛弃了；之后，用k频繁项集生成长度为（k+1）的候选项集，再计算它们的支持率。如此重复上述过程直到不存在更大的频繁项集为止。

用图解的方法描述一下算法过程：

记$F_k$为k频繁项集，$C_k$为k候选项集，$OUT$为所有频繁项集的集合，Apriori算法描述如下：

Apriori算法是一个迭代的过程，看上去很简单，但是注意到每次迭代中有两个重要的步骤：超集生成和支持率计数。超集生成是指通过k阶频繁项集生成无重复的k+1阶候选项集，支持率计数是计算候选项集在给定事务集合上的支持率。这两个步骤是Apriori算法的难点，因为它们都是时间复杂度比较高的操作。Apriori算法的高效率不仅仅来源于剪枝操作，还源于高效的超集生成算法和支持率计数算法。

3. 代码实现

生成候选集： 当k>1时，若k频繁项集中两项有交集的话，那么交集元素一定是k-1个，那么两者求并集可以生成k+1阶候选集；没有交集，什么也不做。当k=1时，直接两两求并集。平均时间复杂度是$O(m{n}^2)$,n是频繁项集的总数，m是频繁项集的长度。如下代码所示：

#生成候选集
def produce_Candinate(F,k):
    n =len(F)
    #候选集开始为空
    C=[]

    #频繁项集长度为1时，两两求并集
    if (k-1)==0:
        for i in range(0,n-1):
            for j in range(i+1,n):
                tmp = set(F[i])|set(F[j])
                C.append(list(tmp))
    #否则，两两连接
    else:
        for i in range(0,n-1):
            for j in range(i+1,n):
                #如果两个集合没有交集，不能做连接操作
                if len(set(F[i])&set(F[j])) ==0:
                    continue
                #求并集
                tmp = set(F[i]) | set(F[j])
                if list(tmp) not in C:
                    C.append(list(tmp))
    return  C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

支持率计算： 候选项逐个和事务求交集得到的长度和候选项的长度相同认为包含于事务中。时间复杂为$O(n\ast m\ast t)$,m为候选项集的数目，n为事务的数目,t为候选项集的长度。

#计算支持率
def support(item,T):
    n=len(T)
    l=len(item)
    count=0
    for x in T:
        if  len(set(x)&set(item)) == l:
            count=count+1
    return  1.0*count/n
1
2
3
4
5
6
7
8
9

Apriori代码示例：

#Apriori算法挖掘频繁项集
def frencunt_item_minning(T,minsup):
    k=1
    #结果集
    out=[]
    #生成1候选集
    C=[]
    for x in T:
        C=list(set(x)|set(C))
    #生成1频繁项集
    F=[]
    for i in C:
       if support(list(i),T) >= minsup:
           F.append([i])

    #迭代
    while (len(F)>0):
        out.append(F)
        #生成k+1候选集
        C=produce_Candinate(F,k)
        #生成k+1频繁项集
        F=[]
        for i in C:
            if support(i,T) >=minsup:
                F.append(i)
        k=k+1
    return out



T=[['A','B','E'],['D','E','F'],['A','C','D','E'],['D','E','F'],['C','E','F']]
out =frencunt_item_minning(T,0.3)
print('频繁项集')
for i in out:
    print(i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

结果为：

这里的实现代码，生成超集和支持率计数的效率都比较低。有很多方法可以优化Apriori，在此不再讨论。（例如，使用枚举树为数据结构。）