关联规则 (Association Rules) 即一组事物之间的关联关系。此处举一个常见例子进行说明，某超市将面包和黄油放在相近的位置，其原因是在其历史订单中，这两个商品经常被同时购买。
那么关联规则挖掘考虑的问题为：如何在历史数据中，挖掘出一组经常同时出现的事物集合？这种关系可以看作是 IF-THEN 关系，即当商品 A 被挑选时，商品 B 也大概率同时会被选中。
关联规则-相关概念
在具体介绍算法前，需要定义三个相关指标，分别为置信度、支持度和提升度。
置信度 (Confidence)
「置信度」表示已购买 A 商品的情况下，购买 B 商品的概率，即条件概率 $P(B\mid A)$，具体定义如下：
其中 $\text{freq}(A,B)$ 表示商品 $(A,B)$ 同时被购买的次数。
支持度 (Support)
「支持度」表示某组商品（例如 A、B 商品）出现的概率，即 $P(A,B)$，具体定义如下：
其中 $N$ 表示购买总次数。
提升度 (Lift)
「提升度」表示商品 A 的出现，对商品 B 的出现概率提升的程度，即 $\frac{P(B\mid A)}{P(B)}$，具体定义如下：
此处可以发现 $\text{Lift}(A\rightarrow B)=\text{Lift}(B\rightarrow A)$.
Apriori 算法
该算法的核心想法为：频繁项集的子集也是频繁项集，即 $P(A,B,C)\leq P(A,B)$。
- 频繁项集 (Frequent Itemset) 定义：支持度大于某阈值的集合。
对于一个数据集，如果暴力计算频繁项集，将遍历所有 item 集合。假设 item 总数为 $M$，则 item 集合一共有 $2^{|M|}$ 个，依次遍历的时间开销与 $M$ 呈指数关系，现实中无法执行。
为减少遍历次数，Apriori 算法按集合大小从小到大的方式进行遍历，如果 $(A,B)$ 非频繁项集，则包含 $(A,B)$ 的所有 item 集合均非频繁项集，进而实现对整个搜索空间的剪枝。
具体算法
-
得到候选 $1$ 项集（集合大小为 $1$），令 $k=1$;
-
不断循环直至候选 $k$ 项集为空:
- 根据候选 $k$ 项集得到频繁 $k$ 项集（判断支撑度是否大于一个给定的阈值）;
- 在频繁 $k$ 项集上扩展得到候选 $k+1$ 项集;
- $k=k+1$.
此处需注意，从频繁 $k$ 项集 $F_k$ 扩展得到候选 $k+1$ 项集 $F_{k+1}$，并非遍历 $F_k$ 内所有 itemset 并添加一个新元素，而是对 $F_k$ 内所有 itemset 两两求并，判断并集大小是否为 $k+1$，即：
当得到频繁项集后，可以通过下述方法导出相应的关联规则：
- 遍历所有频繁项集，通过枚举子集将其分裂为两部分，然后计算其中一部分作为条件时另一部分的概率，以此完成关联规则的求解。
FP-Growth 算法
Apriori 算法需要不断生成候选 $k$ 项集，这个过程需要反复遍历数据，由此造成了一定程度上的低效。为了进一步改进该算法，FP-Growth 算法以树的形式表示所有数据，实现求解频繁项集而无需生成候选项集。
为了快速求解频繁项集，FP-Growth 将交易记录视作字符串，利用类似字典树的结构，将不同的 Item 组织成了一棵 FP-Tree，并基于这颗树实现了频繁项集的快速求解。
具体算法
以下述交易记录为例进行算法说明（例子来源）：
| Transaction ID | Item |
|---|---|
| T100 | I1, I2, I5 |
| T200 | I2, I4 |
| T300 | I2, I3 |
| T400 | I1, I2, I4 |
| T500 | I1, I3 |
| T600 | I2, I3 |
| T700 | I1, I3 |
| T800 | I1, I2, I3, I5 |
| T900 | I1, I2, I3, I6 |
第一步：统计所有的频繁 $1$ 项集（假设最小支持度计数为 $2$），并按出现总次数降序排列。
| Item | I2 | I1 | I3 | I4 | I5 |
|---|---|---|---|---|---|
| Frequency | 7 | 6 | 6 | 2 | 2 |
随后对每个 Transaction 中的 Item 按上述顺序排列，例如 T100 将重排为 I2, I1, I5。
第二步：根据重新排序过的 Transaction，构建 FP-Tree，其原理与字典树的构建一致，树中每个节点由 {Item: 节点统计次数} 组成。
举例说明，首先插入 T100-(I2, I1, I5)，对应下述结构（图片来源）：
随后再次插入 T200-(I2, I4)，对应下图：
FP-Tree 的维护原理为：从 root 出发按层深入，插入新的序列，对于第 $i$ 个 Item，如果当前第 $i$ 层不存在 Item 这个节点，则新建该节点；如果存在，则将已有节点的次数$+1$。
最终得到的 FP-Tree 如下所示（非频繁 $1$ 项集的节点自动滤去，例如 I6）：
第三步：根据 FP-Tree，记录每个 Item 出现的位置，便于后续统计频繁项集。
仍旧以上述内容为例，生成的 FP-Tree 项头表如下：
第四步：根据 FP-Tree 生成频繁项集。此处的算法为根据 Item 的 Frequency，从低到高开始枚举。
首先枚举 I5，并按照 Head Table 中记录的 I5 出现的节点位置，向上回溯至 null，可以得到如下两条 I5 的前缀路径：
1
2
{I2, I1}: 1
{I2, I1, I3}: 1
此时根据上述两条前缀路径再次构建 FP-Tree，得到条件 FP-Tree。此时对于该条件 FP-Tree 中所有的频繁项集，在其上加入 I5 即可得到包含 I5 的频繁项集。这是一个递归过程，具体可参考文末的代码。
枚举完 I5 后，再按顺序枚举 I4，并按照上述 I5 的操作，构建 I4 下的条件 FP-Tree，并利用递归的方式求得包含 I4 的频繁项集。
由于我们按照 Frequency 由小到大的顺序遍历，因此遍历到 Item X 时，实际求取的是所有包含 Item X 且 Item X 在集合中 Frequency 最小的所有频繁项集，由此可以避免重复计数。
代码实现
下述代码分别实现了 Apriori 和 FP-Growth 算法，其中算法输入的 min_sup 代表计算频繁项集时的最小支持度，min_conf 代表计算关联规则时的最小置信度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
import numpy as np
class FPTree:
def __init__(self, transaction_list, count_list, n, min_sup):
self.n, self.min_sup = n, min_sup
self.transaction_list, self.count_list = transaction_list, count_list
self.item1_cnt, self.f_list = self.acquire_flist()
if self.f_list != []:
self.fa, self.son, self.cnt, self.idx, self.tot, self.rt, self.node_list = self.construct_fptree()
def acquire_flist(self):
# frequent 1-itemset
item1_cnt = {}
for transaction, count in zip(self.transaction_list, self.count_list):
for item in transaction:
item1_cnt[item] = item1_cnt.get(item, 0) + count
f_list = [item for item in item1_cnt if item1_cnt[item] >= self.min_sup]
return item1_cnt, f_list
def construct_fptree(self):
# initialization
node_sum = 1
for transaction in self.transaction_list:
node_sum += len(transaction)
tot, rt, node_list = 0, 0, {}
son = [{} for i in range(node_sum)]
fa, cnt, idx = [0 for i in range(node_sum)], [0 for i in range(node_sum)], [0 for i in range(node_sum)]
# construct fp-tree
for transaction, count in zip(self.transaction_list, self.count_list):
# process transaction
# transaction need to be sorted, otherwise the order in list_now may be a problem
list_now = [item for item in transaction if self.item1_cnt[item] >= self.min_sup]
if list_now == []:
continue
list_now = sorted(list_now, key=lambda item: self.item1_cnt[item], reverse=True)
# insert to the tree
now = rt
for item in list_now:
if son[now].get(item, 0) != 0:
now = son[now].get(item)
else:
tot += 1
fa[tot], idx[tot], son[now][item] = now, item, tot
now = tot
if item in node_list:
node_list[item].append(now)
else:
node_list[item] = [now]
cnt[now] += count
return fa, son, cnt, idx, tot, rt, node_list
def find_chain(self):
if self.f_list != []:
for item in self.f_list:
# find the chain for item
transaction_list, count_list = [], []
transaction_list_append, count_list_append = transaction_list.append, count_list.append
for i in self.node_list[item]:
transaction, now = [], self.fa[i]
transaction_append = transaction.append
while now != 0:
transaction_append(self.idx[now])
now = self.fa[now]
transaction_list_append(sorted(transaction))
count_list_append(self.cnt[i])
yield item, transaction_list, count_list
class AssociationRules:
"""
item_dict: {0: 'str', 1: 'str', ..., n: 'str'}
transaction_list: [[...], [...], ..., [...]]
"""
def __init__(self, item_dict, transaction_list, min_sup, min_conf, method="apriori"):
self.n, self.m = len(item_dict), len(transaction_list)
self.min_sup, self.min_conf, self.method = min_sup * self.m, min_conf, method
self.item_dict = item_dict
self.transaction_list = [sorted(set(transaction)) for transaction in transaction_list]
if method == "apriori":
self.frequent_itemsets = self.run_apriori()
elif method == "fp-growth":
count_list = [1 for i in range(len(self.transaction_list))]
self.frequent_itemsets = self.run_fpgrowth(self.transaction_list, count_list)
def count(self, item_set):
num = 0
for transaction in self.transaction_list:
if item_set.issubset(transaction):
num += 1
return num
def run_apriori(self):
item_list = []
item_list_append = item_list.append
frequent_itemsets = {}
for i in range(self.n):
if i == 0:
for item in self.item_dict:
num = self.count(set([item]))
if num >= self.min_sup:
item_list_append([item])
frequent_itemsets[tuple([item])] = num
else:
new_list = []
new_list_append = new_list.append
for k1 in range(len(item_list) - 1):
for k2 in range(k1 + 1, len(item_list)):
k3 = set(item_list[k1]).union(item_list[k2])
if len(k3) == i + 1 and frequent_itemsets.get(tuple(sorted(k3)), 0) == 0:
num = self.count(k3)
if num >= self.min_sup:
new_list_append(list(k3))
frequent_itemsets[tuple(sorted(k3))] = num
if new_list == []:
break
item_list = new_list
return frequent_itemsets
def run_fpgrowth(self, raw_transaction_list, raw_count_list):
itemsets_sum = {}
fptree = FPTree(raw_transaction_list, raw_count_list, self.n, self.min_sup)
for item, transaction_list, count_list in fptree.find_chain():
itemsets_sum[tuple([item])] = fptree.item1_cnt[item]
itemsets_new = self.run_fpgrowth(transaction_list, count_list)
for itemset, cnt_itemset in itemsets_new.items():
itemsets_sum[tuple(sorted(list(itemset) + [item]))] = cnt_itemset
return itemsets_sum
def convert2name(self, item_set):
item_name = set()
for item in item_set:
item_name.add(self.item_dict[item])
return item_name
def output_frequent_itemsets(self):
frequent_itemsets = []
for itemset, value in reversed(sorted(self.frequent_itemsets.items(), key=lambda x: x[1])):
value = "%.2f%%" % (value * 100 / self.m)
frequent_itemsets.append(str(self.convert2name(sorted(itemset))) + f" \t {value}")
min_sup = "%.2f%%" % (self.min_sup * 100 / self.m)
print(f"frequent itemsets: ({len(frequent_itemsets)} in total, min_sup = {min_sup})")
for itemset in frequent_itemsets:
print("\t", itemset)
def association_rules(self):
def _powerset(item_list):
num = len(item_list)
masks = [1 << i for i in range(num)]
# notice: no empty set and full set
for i in range(1, (1 << num) - 1):
yield [item for mask, item in zip(masks, item_list) if i & mask]
rules = []
for frequent_itemset, num in self.frequent_itemsets.items():
for subset in _powerset(frequent_itemset):
A = set(subset)
B = set(frequent_itemset).difference(A)
conf = num / self.frequent_itemsets[tuple(sorted(A))]
if conf >= self.min_conf:
sup = "%.2f%%" % (num * 100 / self.m)
conf = "%.2f%%" % (conf * 100)
A_name, B_name = self.convert2name(A), self.convert2name(B)
rules.append((sup, conf, f"{A_name} -> {B_name} \t [{sup}, {conf}]"))
rules.sort()
min_sup = "%.2f%%" % (self.min_sup * 100 / self.m)
min_conf = "%.2f%%" % (self.min_conf * 100)
print(f"association rules: ({len(rules)} in total, min_sup = {min_sup}, min_conf = {min_conf})")
for rule in rules:
print("\t", rule[2])
if __name__ == "__main__":
min_sup, min_conf = 2/9, 0.5
item_dict = {0: "I1", 1: "I2", 2: "I3", 3: "I4", 4: "I5", 5: "I6"}
transaction_list = [[0, 1, 4], [1, 3], [1, 2], [0, 1, 3], [0, 2], [1, 2], [0, 2], [0, 1, 2, 4], [0, 1, 2, 5]]
for method in ["apriori", "fp-growth"]:
print(f"method: {method}")
association_model = AssociationRules(item_dict, transaction_list, min_sup, min_conf, method)
association_model.output_frequent_itemsets()
association_model.association_rules()