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