十大数据挖掘算法之Apriori

一、Apriori算法简介

1.1. 关联分析

在介绍Apriori算法之前我们需要先了解一下“关联分析”。关联分析指的是在大数据集中发现物品之间隐含关系，关联分析的一个著名案例就是“尿布与啤酒”。这些关系可以有两种形式：频繁项集和关联规则，频繁项集是经常出现在一块的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。而关联分析的目的就是发现频繁项集和发现关联规则

交易号码	商品
0	牛奶，莴笋
1	莴笋，尿布，啤酒，甜菜
2	牛奶，尿布，啤酒，橙汁
3	莴笋，牛奶，尿布，啤酒
4	莴笋，牛奶，尿布，橙汁

上面的交易清单中，集合{啤酒，尿布，牛奶}就是频繁项集的一个例子，也可以找到“尿布 -> 啤酒”的关联规则。

关联规则还可以应用于网站流量分析，电商商品推荐，流媒体音乐推荐等。

那么如何定义这些隐含关系？为此我们引入支持度和可信度的概念。

一个项集的支持度被定义为数据集中包含该项集的记录所占比例。例如，{尿布}的支持度为4/5，{尿布，啤酒}的支持度为3/5。

可信度是针对例如{尿布} -> {啤酒}的关联规则来定义的，这条规则的可信度定义为“支持度（{尿布，啤酒}）/ 支持度（尿布）”，则其可信度为3/4=0.75，这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适用。

1.2. Apriori原理

假设有商品0、1、2、3，如何对给定的集合{0，3}，计算其支持度？

先列一下所有可能的项集组合：
{0，1，2，3，01，02，03，12，13，23，012，013，023，123，0123}，共有15种组合方式。对于包含N种物品的数据集共有“2的N次方 - 1”种项集组合，对于现代计算机而言，这种呈指数爆炸增长的数据规模，即便007也要很长时间才能完成运算。

为了降低计算时间，研究人员发现一种Apriori原理，即如果某个项集是频繁的，那么它的所有子集也是频繁的，反过来说，如果一个项集是非频繁集，那么它的所有超集也是非频繁的。借助Apriori原理，我们就可以减少关系不大的项集。

比如，已知{2，3}是非频繁的，借助Apriori原理，那么{0，2，3}，{1，2，3}以及{0，1，2，3}也是非频繁的，所以这三个项集的支持度就不需要计算了。

二、使用Apriori算法来发现频繁集

Apriori算法的大概步骤：

1. 首先生成所有单个物品的项集列表；
2. 扫描交易记录，计算单物品项集的支持度；
3. 查看哪些单物品项集支持度满足要求所需的最小支持度；
4. 去掉不满足最小支持度的项集；
5. 对剩下的集合组合生成两元素的项集；
6. 再重新扫描交易记录，去掉不满足最小支持度的项集；
7. 重复，直到所有项集都被去掉。

2.1 生成一个候选项集

from numpy import *

def loadDataSet():
    '''创建一个用于测试的简单数据集'''
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
                
    C1.sort()
    return map(frozenset, C1)

这第一部分的代码中，定义了loadDataSet()函数和createC1()函数，loadDataSet()函数返回一个二维列表，createC1()函数返回一个包含所有单个物品的项集列表，此列表使用了Python中的frozenset类型，目的是使其不可改变。

def scanD(D, Ck, minSupport):
    '''
    三个参数分别是：数据集、候选项集列表以及最小支持度
    '''
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not can in ssCnt.keys(): 
                    ssCnt[can]=1
                else: 
                    ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0,key)
        supportData[key] = support
    return retList, supportData

此处定义的scanD()函数用于扫描交易记录并返回满足最小支持度的项集。简单运行测试一下：

dataSet = loadDataSet()
print(dataSet)
C1 = list(createC1(dataSet))
print(C1)
D = list(map(set,dataSet))
print(D)
# 有了集合形式的数据，就可以去掉那些不满足最小支持度的项集了。这里使用0.5作为最小支持度。
L1, suppData0 = scanD(D,C1,0.5)
print(L1)
# 打印结果：
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
[{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]

L1的结果表明，L1列表中的每个单物品项集至少出现在50%以上的交易记录中，而物品4并没有达到最小支持度。

2.2 组织完整的Apriori算法

def aprioriGen(Lk, k): 
    '''
    参数为：频繁项集列表Lk，项集个数k
    输出候选项集Ck
    '''
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk): 
            # 前k个项相同时，将两个集合合并
            L1 = list(Lk[i])[:k-2]
            L2 = list(Lk[j])[:k-2]
            L1.sort()
            L2.sort()
            if L1==L2: #if first k-2 elements are equal
                retList.append(Lk[i] | Lk[j]) #set union
    return retList

def apriori(dataSet, minSupport = 0.5):
    C1 = list(createC1(dataSet))
    D = list(map(set, dataSet))
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

此处定义两个函数：apriori()和aprioriGen()，其中主函数是apriori()，它会调用aprioriGen()来创建候选项集Ck。给apriori()函数传递一个数据集以及一个支持度，函数会生成候选项集的列表。执行一下试试：

L,suppData = apriori(dataSet)
print(L)
# 打印结果
[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})],
 [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})],
 [frozenset({2, 3, 5})],
 []]

L的结果表明列表中的项出现在50%的交易记录中。

3. 从频繁项集中挖掘关联规则

我们得到频繁项集“{尿布，啤酒}”，可能存在关联规则“尿布 -> 啤酒”，但“啤酒 -> 尿布”就不一定成立，所以我们需要将关联规则给挖出来。

def generateRules(L, supportData, minConf=0.7):
    '''
    参数为：频繁项集列表、包括那些频繁项集支持数据的字典、最小可信度阈值
    支持度数据来自scanD返回的suppDara字典
    函数生成一个包含可信度的规则列表
    '''
    bigRuleList = []
    for i in range(1, len(L)):
        # 只获取有两个或更多元素的集合
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            if (i > 1):
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList         

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq] #计算可信度
        if conf >= minConf: 
            print(freqSet-conseq,'-->',conseq,'conf:',conf)
            brl.append((freqSet-conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    m = len(H[0])
    if (len(freqSet) > (m + 1)): #尝试进一步合并
        Hmp1 = aprioriGen(H, m+1)#创建Hm+1条新候选规则
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):    #至少需要两个集合合并
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

代码源自《机器学习实战》，修改了一下Python2与Python3之间的兼容问题后直接复制粘贴了。执行一下吧：

rules = generateRules(L,suppData,minConf=0.7)
print(rules)
# 打印结果
frozenset({5}) --> frozenset({2}) conf: 1.0
frozenset({2}) --> frozenset({5}) conf: 1.0
frozenset({1}) --> frozenset({3}) conf: 1.0
[(frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({1}), frozenset({3}), 1.0)]

4. 简单示例：发现毒蘑菇的相似特征

我们现在有一个关于野生蘑菇的数据集，寻找毒蘑菇的一些公共特征。

数据集的前几行如下：

1 3 9 13 23 25 34 36...
2 3 9 14 23 26 34 36...
2 4 9 15 23 27 34 36...

第一个特征表示有毒或者可食用。如果有毒则为2，可食用则为1.下一个特征是蘑菇伞的形状，有六种可能的值，分别用整数3~8表示。

mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
L,suppData = apriori(mushDatSet,minSupport=0.3)
# 在结果中可以搜索包含有毒特征值2的频繁项集
for item in L[1]:
    if item.intersection('2'):
        print(item)
# 打印结果
frozenset({'28', '2'})
frozenset({'2', '53'})
frozenset({'23', '2'})
frozenset({'34', '2'})
frozenset({'36', '2'})
frozenset({'2', '59'})
frozenset({'2', '63'})
frozenset({'67', '2'})
frozenset({'2', '76'})
frozenset({'85', '2'})
frozenset({'2', '86'})
frozenset({'90', '2'})
frozenset({'93', '2'})
frozenset({'39', '2'})

也可以在更大项集，比如 L[3]中重复上述过程。

在这个例子，我们并没有寻找关联规则，因为有时候我们只需要找到一些相关的特征，比如毒蘑菇的特征。