主要的参考资料是，机器学习实战，就是那个扛着斧子提着水桶的男子。

这一部分其实早先一段时间我就已经学习过了，也做了一些代码的联系，好理解，代码也不复杂，而且书上也给出了现成的代码。但是这段时间，我领导给我说让我了解一下Apriori算法，说是过段时间要做这部分。我翻遍了我的简书，发现之前并没有做相关记录，于是现在决定还是做一些相关的记录。*

好了，其实上面那些都是废话，目前来说，我预备第一阶段先更新三篇文章，第一个就是Apriori，第二个就是FP-growth，第三个就是Eclat算法。

从大规模数据集中寻找物品之间的隐含关系被称为关联分析（association analysis）或者关联规则学习（association rule learning）。
关联分析有两种形式：发现频繁项集或者关联规则。

例如，示例数据如下：

交易号码	商品
0	豆奶，莴苣
1	莴苣，尿布，葡萄酒，甜菜
2	豆奶，尿布，葡萄酒，橙汁
3	莴苣，豆奶，尿布，葡萄酒
4	莴苣，豆奶，尿布，橙汁

频繁项集：{葡萄酒，尿布，豆奶}，像这样经常出现在一起的物品集合，无先后顺序。
关联规则：诸如，尿布->葡萄酒，这样的关系叫做关联规则，如果买了尿布，那么有极大的可能买葡萄酒，有先后顺序。

几个概念

1、一个项集的支持度（support）被定义为数据集中包含该相机的记录所占的比例。

例如在上面的表中，一共有5条记录，3条记录都包含了{豆奶，尿布}，因此{豆奶，尿布}的支持度为3/5.
支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。

2、可信度或置信度（confidence）是针对一条诸如{尿布}->{葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“支持度（{尿布，葡萄酒}）/支持度（{尿布}）”。

因此对于上面表格里的数据，“尿布->葡萄酒”的可信度为0.75.

支持度和可信度是用来量化关联分析是否成功的方法。

Apriori原理

Apriori原理是说，如果某个项集是频繁的，那么它的所有子集也是频繁的。这意味着如果{0,1}是频繁的，那么{0}，{1}也一定是频繁的。这个原理直观上并没有什么帮助，但是如果反过来看就有用了，也就是说，如果一个项集是非频繁集，那么它所有的超集也是非频繁的。例如，如果项集{2,3}是非频繁的，那么{0,2,3}，{1,2,3}，{0,1,2,3}也是非频繁的。换句话说，一旦计算出了{2,3}的支持度，知道它是非频繁的之后，就不需要在计算{0,2,3}，{1,2,3}，{0,1,2,3}的支持度。

关联分析的目标包括两项：发现频繁项集个发现关联规则。首先需要找到频繁项集，然后才能获得关联规则。

上面是发现频繁项集，下面讲如何获得关联规则。

关联规则是：某个元素或者某个元素集合可能推导出另一个元素。例如“豆奶->莴苣”，但是这条反推过来并不是总能成立。
对于频繁项集的量化定义是满足最小支持度，对于关联规则也有类似的量化方法，量化指标叫做可信度。

一条规则P->H的可信度定义为support（P|H）/support（P）。

这里有一点要注意的，在python里，操作符|表示集合的并操作，而数学上集合并的符号是U。P|H是指所有出现在集合P或者出现在集合H中的元素。
类似于前面介绍的频繁项集生成，我们可以为每个频繁项集产生许多关联规则，如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。

下面应该是你们最想要的：程序清单

代码用python编写，代码和实现思路来自于《机器学习实战》，但是书上的代码用的是python2，我用的python3，做了一些改写。

# -*- coding: utf-8 -*-
# 一个apriori的可用版本


# 加载数据集
def loadDataSet():
    # return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    return [['A', 'B', 'D', 'H'], ['A', 'B', 'E', 'I'], ['A', 'B', 'E', 'J'], ['A', 'C', 'F', 'G']]


# C1 是大小为1的所有候选项集的集合
# C1是set型，元素单一不重复
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)#frozen set, user can't change it.
    # map型不能打印，必须转成list才能打印
    return list(map(frozenset, C1))


# D是数据集的集合表示形式
# 去掉不满足最小支持度的项集（单一元素），L1
def scanD(D, CK, minSupport):
    ssCnt = {}
    numItems = 0
    cklist = list(CK)
    for tid in D:
        numItems += 1
        for can in cklist:
            if can.issubset(tid):
                if can not in ssCnt.keys(): ssCnt[can] = 1
                else: ssCnt[can] += 1
                # print(ssCnt[can])
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData


# 构建候选项集Ck
# total apriori
def aprioriGen(Lk, k):  # 组合，向上合并
    # creates Ck 参数：频繁项集列表 Lk 与项集元素个数 k
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk):  # 两两组合遍历
            L1 = list(Lk[i])[:k-2]
            L2 = list(Lk[j])[:k-2]
            L1.sort()
            L2.sort()
            if L1 == L2:  # 若两个集合的前k-2个项相同时,则将两个集合合并
                retList.append(Lk[i] | Lk[j])  # set union
    return retList


# 如果仅想找到频繁集，不想知道推导顺序，到这里就可以了，调用apriori就可以了
# 从Ck中找到满足最小支持度的项集即Lk
# apriori
def apriori(dataSet, minSupport=0.5):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet))  # python3
    L1, supportData = scanD(D, C1, minSupport)  # 单项最小支持度判断 0.5，生成L1
    L = [L1]
    k = 2
    while len(L[k-2]) > 0:  # 创建包含更大项集的更大列表,直到下一个大的项集为空
        Ck = aprioriGen(L[k-2], k)  # Ck
        Lk, supK = scanD(D, Ck, minSupport)  # get Lk
        supportData.update(supK)
        L.append(Lk)
        k += 1   # 继续向上合并 生成项集个数更多的
    return L, supportData


# 下面这一部分是在找到频繁集的基础上找到关联规则，也就是某元素可以推导出另一元素的规则。

# 生成关联规则
def generateRules(L, supportData, minConf=0.7):
    # 频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值
    bigRuleList = []  # 存储所有的关联规则
    for i in range(1, len(L)):  # 只获取有两个或者更多集合的项目，从1,即第二个元素开始，L[0]是单个元素的
        # 两个及以上的才可能有关联一说，单个元素的项集不存在关联问题
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            # 该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1
            if i > 1:
                # 如果频繁项集元素数目超过2,那么会考虑对它做进一步的合并
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:  # 第一层时，后件数为1
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)  # 调用函数2
    return bigRuleList


# 生成候选规则集合：计算规则的可信度以及找到满足最小可信度要求的规则
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    # 针对项集中只有两个元素时，计算可信度
    prunedH = []  # 返回一个满足最小可信度要求的规则列表
    for conseq in H:  # 后件，遍历 H中的所有项集并计算它们的可信度值
        conf = supportData[freqSet]/supportData[freqSet-conseq]  # 可信度计算，结合支持度数据
        if conf >= minConf:
            print(freqSet-conseq, '-->', conseq, 'conf:', conf)
            # 如果某条规则满足最小可信度值,那么将这些规则输出到屏幕显示
            brl.append((freqSet-conseq, conseq, conf))  # 添加到规则里，brl 是前面通过检查的 bigRuleList
            prunedH.append(conseq)  # 同样需要放入列表到后面检查
    return prunedH


# 合并生成的候选集
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    # 参数:一个是频繁项集,另一个是可以出现在规则右部的元素列表 H
    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:  # 满足最小可信度要求的规则列表多于1,则递归
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)


dataSet = loadDataSet()
# print(dataSet)
C1 = createC1(dataSet)
# print(C1)
D = map(set, dataSet)
# print(list(D))
L1, suppData0 = scanD(D, C1, 0.5)
# print(L1)
# print(suppData0)
L, suppData = apriori(dataSet)
# print(L)
# print(L[0])
# print(aprioriGen(L[0], 2))
# L, suppData = apriori(dataSet, minSupport=0.7)
# print(L)
# print(suppData)
# 想得到最终结果仅需调用这两个即可。
L, suppData = apriori(dataSet, minSupport=0.5)
rules = generateRules(L, suppData, minConf=0.7)