问题引入

在常见的超市购物数据集，或者电商的网购数据集中，如果我们找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。

Apriori 算法是常用的用于挖掘出数据关联规则的算法，它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。

频繁项集的评估标准

什么样的数据才是频繁项集

一起出现次数多的数据集就是频繁项集

评估频繁项集的标准是什么

10 条记录，里面 A 和 B 同时出现了三次，那么我们能不能说 A 和 B 一起构成频繁项集呢？

支持度

支持度是几个关联的数据在数据集中出现的次数占总数据集的概率。如果我们有两个想分析关联性的数据 X 和 Y，则对应的支持度为:

以此类推，如果我们有三个想分析关联性的数据 X，Y 和 Z，则对应的支持度为:

置信度

置信度体现了一个数据出现后，另一个数据出现的概率。如果我们有两个想分析关联性的数据 X 和 Y，X 对 Y 的置信度为

也可以以此类推到多个数据的关联置信度，比如对于三个数据X，Y，Z,则X对于Y和Z的置信度为：

提升度

提升度表示含有Y的条件下，同时含有X的概率，与X总体发生的概率之比,即:

提升度体先了 X 和 Y之间的关联关系, 提升度大于 1 则 X⇐Y 是有效的强关联规则， 提升度小于等于 1 则 X⇐Y 是无效的强关联规则。一个特殊的情况，如果 X 和 Y 独立，则有 Lift(X⇐Y)=1，因为此时 P(X|Y)=P(X)。

算法思想

对于Apriori算法，我们使用支持度来作为我们判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思，首先，我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。第二层意思就是我们要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。那么具体的，Apriori算法是如何做到挖掘K项频繁集的呢？
Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。
可见这个算法还是很简洁的，第i次的迭代过程包括扫描计算候选频繁i项集的支持度，剪枝得到真正频繁i项集和连接生成候选频繁i+1项集三步。

算法流程

输入：数据集合 D，支持度阈值
输出：最大的频繁 k 项集

• 扫描整个数据集，得到所有出现过的数据，作为候选频繁 1 项集。k=1，频繁 0 项集为空集。
• 挖掘频繁k项集
  • 扫描数据计算候选频繁k项集的支持度
  • 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。
  • 基于频繁k项集，连接生成候选频繁k+1项集。
• k=k+1，转入步骤2。

Aprior 算法总结

• Aprior 算法是一个非常经典的频繁项集的挖掘算法，很多算法都是基于 Aprior 算法而产生的，包括 FP-Tree,GSP, CBA 等。

# -*- coding: utf-8 -*-
import pandas as pd
from time import process_time
d = pd.read_csv('apriori.txt', header=None, dtype=object)

print(u'\n转换原始数据至0-1矩阵...')

start = process_time()
ct = lambda x: pd.Series(1, index=x)
b = map(ct, d.values)
d = pd.DataFrame(list(b)).fillna(0)
d = (d == 1)
end = process_time()
print(u'\n转换完毕，用时：%0.2f秒' % (end - start))
print(u'\n开始搜索关联规则...')
del b

support = 0.06  # 最小支持度
confidence = 0.75  # 最小置信度
ms = '--'  # 连接符，用来区分不同元素，如A--B。需要保证原始表格中不含有该字符


# 自定义连接函数，用于实现L_{k-1}到C_k的连接
def connect_string(x, ms):
    x = list(map(lambda i: sorted(i.split(ms)), x))
    l = len(x[0])
    r = []
    for i in range(len(x)):
        for j in range(i, len(x)):
            if x[i][:l - 1] == x[j][:l - 1] and x[i][l - 1] != x[j][l - 1]:
                r.append(x[i][:l - 1] + sorted([x[j][l - 1], x[i][l - 1]]))
    return r


# 寻找关联规则的函数
def find_rule(d, support, confidence):
    import time
    start = process_time()
    result = pd.DataFrame(index=['support', 'confidence'])  # 定义输出结果

    support_series = 1.0 * d.sum() / len(d)  # 支持度序列
    column = list(support_series[support_series > support].index)  # 初步根据支持度筛选
    k = 0

    while len(column) > 1:
        k = k + 1
        print(u'\n正在进行第%s次搜索...' % k)
        column = connect_string(column, ms)
        print(u'数目：%s...' % len(column))
        sf = lambda i: d[i].prod(axis=1, numeric_only=True)  # 新一批支持度的计算函数

        # 创建连接数据，这一步耗时、耗内存最严重。当数据集较大时，可以考虑并行运算优化。
        d_2 = pd.DataFrame(list(map(sf, column)), index=[ms.join(i) for i in column]).T

        support_series_2 = 1.0 * d_2[[ms.join(i) for i in column]].sum() / len(d)  # 计算连接后的支持度
        column = list(support_series_2[support_series_2 > support].index)  # 新一轮支持度筛选
        support_series = support_series.append(support_series_2)
        column2 = []

        for i in column:  # 遍历可能的推理，如{A,B,C}究竟是A+B-->C还是B+C-->A还是C+A-->B？
            i = i.split(ms)
            for j in range(len(i)):
                column2.append(i[:j] + i[j + 1:] + i[j:j + 1])

        cofidence_series = pd.Series(index=[ms.join(i) for i in column2])  # 定义置信度序列

        for i in column2:  # 计算置信度序列
            cofidence_series[ms.join(i)] = support_series[ms.join(sorted(i))] / support_series[ms.join(i[:len(i) - 1])]

        for i in cofidence_series[cofidence_series > confidence].index:  # 置信度筛选
            result[i] = 0.0
            result[i]['confidence'] = cofidence_series[i]
            result[i]['support'] = support_series[ms.join(sorted(i.split(ms)))]

    result = result.T.sort_values(['confidence', 'support'], ascending=False)  # 结果整理，输出
    end = process_time()
    print(u'\n搜索完成，用时：%0.2f秒' % (end - start))
    print(u'\n结果为：')
    print(result)

    return result

if __name__ == '__main__':
    result = find_rule(d, support, confidence)
    result.to_excel('rules.xls')

参考链接

• https://blog.csdn.net/weixin_42051109/article/details/89156005
• https://www.cnblogs.com/pinard/p/6293298.html