数据挖掘 关联分析与 Apriori 算法

关联分析是指关联数据挖掘，它的目标是发现事务数据库中不同项集之间的联系。数据库中的项集实际上就是一组数据（或者按照 Python 的习惯叫元组），比如在超市的数据库中每一次购买记录就是一个项集，比如它可能是这样的：（牛奶，尿布，圆葱），很多个这样的项集就构成了整个超市的数据库。当然为了更好的说明问题，在这个例子中我们把其他数据（比如购买数量，购买时间等等）都删除掉了，只保留了每一次购买的商品名。

比如上图就是一个简单的购物车事务数据库的例子，按照上面的说法，我们称每一行为一个项集，因为我们已经把购买数量去掉了，所以项集中不会出现重复的商品（项）。

我们的目标是根据数据库中的这组数据看看顾客购买的商品之间有没有什么联系，比如购买了牛奶和麦片的人会不会倾向于购买面包。

为了方便说明我们把 {牛奶，面包} 和 {麦片} 之间这种微妙的关系写成： ，我们叫它关联规则（Latex 里面中文太丑了，所以我用了英文，没错 Oatmeal（麦片））。但是这个记法很简单，而且很重要的一点它表明了这种关系具有方向性，你一定注意到那个箭头了吧。

另外我们还是得描述一下这两组东西之间关系有多么的强烈，是买了 {牛奶，面包} 的人一定会购买麦片，还是偶尔才会购买麦片。这个很简单比如在这个例子里面有三个人购买了 {牛奶，面包}：1 号，2 号和 3 号。但是其中只有一个人同时也购买了 {麦片}。所以我们说：这个关联规则的置信度（confidence）为 1/3 。

但是仅仅有 confidence 很大还不足以说明问题，比如我们发现购买了{牛奶，麦片} 的顾客全都购买了 {牛奶}，此时 confidence 为 1 。我们此时很开心，我们找到了一个关联性很强的规则，我们对这个关联规则很有信心。但是后来我们发现购买了 {牛奶，麦片，面包} 的顾客很少，在这个例子中只有 1 个人，他占整个数据库数据数量的 1/4。所以我们说这个关联规则的支持度（support）为 1/4 。支持度是对这个关联规则重要性的度量。如果这个关系很强烈，但是一百个人中只有一个人这样购买了，那么这个关联规则依然没有什么研究的价值。

从上面的公式中你也可以看到实际上 support 就是这个规则的频率，（我想你还记得频率=频数/样本总量 吧）所以对于 support 比较高的关联规则我们称之为频繁项集。那么什么较高什么较低我们总要有一个界限，这个界限就是 min_sup ，support 大于这个数就叫做频繁项集，否则就叫做非平凡项集。

接下来的问题就是怎么从数据库茫茫四条数据中找到我们感兴趣的、潜在的、商品之间的联系。

整个过程可以分为两步：打开冰箱门，放入大象，关门

1. 找频繁项集：这一步是根据 support 筛选出来的。使用 Apriori 算法。
2. 根据找到的频繁项集找到我们感兴趣的关联规则：这一步是根据 confidence 筛选得到。

我觉得有必要先解释一下这两步的含义。假设我们要找的关联规则就是 根据上面的分析，首先要满足 support 高于 support_min 的条件。此时频繁项集就是 {牛奶，麦片，面包}，然后根据得到的这个集合，利用 confidence 确定这个规则到底是什么，实际上就是将 {牛奶，麦片，面包} 分成两组。

所以你此时大概已经意识到 confidence 描述的是一个 {牛奶，麦片，面包} 这个频繁项集在整个事务数据库中的情况，而 support 描述的是 {牛奶，麦片，面包} 这个集合中项之间的关联。

（下面例子中的图片来自于深度学习生态圈）

下面我们使用 Apriori 算法找到我们之前例子中的所有频繁项集，为了方便说明我们将商品使用字母代替。

最终得到的频繁二项集为{B，C，E}。找频繁二项集是一个很聪明的做法，因为我们想要的规则一定是由这些频繁二项集的两个子集组成的（当然这个两个子集是非空并且是互斥的），我们接下来只需要检查所有子集的组合是否满足 confidence 条件即可。

这里有一点值得注意：我们不会考虑诸如 {B} -> {C} 的情况，因为 {C，E} 已经包括 {C} 了。

最后给出整个过程的代码，代码来自于《机器学习实战》

from numpy import *

# 构造数据
def loadDataSet():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

# 将所有元素转换为frozenset型字典，存放到列表中
def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    # 使用frozenset是为了后面可以将这些值作为字典的键
    return list(map(frozenset, C1))  # frozenset一种不可变的集合，set可变集合

# 过滤掉不符合支持度的集合
# 返回 频繁项集列表retList 所有元素的支持度字典
def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):  # 判断can是否是tid的《子集》 （这里使用子集的方式来判断两者的关系）
                if can not in ssCnt:  # 统计该值在整个记录中满足子集的次数（以字典的形式记录，frozenset为键）
                    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  # 排除不符合支持度元素后的元素 每个元素支持度

# 生成所有可以组合的集合
# 频繁项集列表Lk 项集元素个数k  [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):  # 两层循环比较Lk中的每个元素与其它元素
        for j in range(i + 1, lenLk):
            L1 = list(Lk[i])[:k - 2]  # 将集合转为list后取值
            L2 = list(Lk[j])[:k - 2]
            L1.sort()
            L2.sort()  # 这里说明一下：该函数每次比较两个list的前k-2个元素，如果相同则求并集得到k个元素的集合
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])  # 求并集
    return retList  # 返回频繁项集列表Ck

# 封装所有步骤的函数
# 返回 所有满足大于阈值的组合 集合支持度列表
def apriori(dataSet, minSupport=0.5):
    D = list(map(set, dataSet))  # 转换列表记录为字典  [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
    C1 = createC1(
        dataSet)  # 将每个元素转会为frozenset字典    [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
    L1, supportData = scanD(D, C1, minSupport)  # 过滤数据
    L = [L1]
    k = 2
    while (len(L[k - 2]) > 0):  # 若仍有满足支持度的集合则继续做关联分析
        Ck = aprioriGen(L[k - 2], k)  # Ck候选频繁项集
        Lk, supK = scanD(D, Ck, minSupport)  # Lk频繁项集
        supportData.update(supK)  # 更新字典（把新出现的集合:支持度加入到supportData中）
        L.append(Lk)
        k += 1  # 每次新组合的元素都只增加了一个，所以k也+1（k表示元素个数）
    return L, supportData

dataSet = loadDataSet()
L, suppData = apriori(dataSet)
print(L)
print(suppData)

# 获取关联规则的封装函数
def generateRules(L, supportData, minConf=0.7):  # supportData 是一个字典
    bigRuleList = []
    for i in range(1, len(L)):  # 从为2个元素的集合开始
        for freqSet in L[i]:
            # 只包含单个元素的集合列表
            H1 = [frozenset([item]) for item in freqSet]  # frozenset({2, 3}) 转换为 [frozenset({2}), frozenset({3})]
            # 如果集合元素大于2个，则需要处理才能获得规则
            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)  # 将单个集合元素两两合并
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):  # need at least two sets to merge
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)


dataSet = loadDataSet()
L, suppData = apriori(dataSet, minSupport=0.5)
rules = generateRules(L, suppData, minConf=0.7)
# rules = generateRules(L,suppData,minConf=0.5)