免规则采集器列表算法(Apriori算法(A)/B同时出现的概率占A出现概率 )

　　免规则采集器列表算法(Apriori算法(A)/B同时出现的概率占A出现概率

)

　　介绍

　　Apriori 是一种流行的算法，用于在关联规则学习中提取频繁项集。Apriori 算法旨在对收录交易的数据库进行操作，例如商店客户的购买。如果满足用户指定的支持阈值，则项集被认为是“频繁的”。例如，如果支持阈值配置文件

　　Apriori 是一种流行的算法，用于在关联规则学习中提取频繁项集。Apriori 算法旨在对收录交易的数据库进行操作，例如商店客户的购买。如果满足用户指定的支持阈值，则项集被认为是“频繁的”。例如，如果支持阈值设置为 0.5 (50%)，则频繁项集定义为在数据库中至少 50% 的所有事务中一起出现的项集。基于Apriori算法，我们可以从海量的用户行为数据中找到关联规则的频繁项集组合，例如挖掘购物行业用户的频繁购买组合。

　　定义

　　支持度（support）：support(A=>B) = P(A∪B)，表示A和B同时出现的概率。

　　confidence：confidence(A=>B)=support(A∪B)/support(A)，表示A和B同时出现的概率与A出现的概率的比值。

　　频繁项集：在项集中频繁出现且满足最小支持阈值的集合，如{牛奶、面包}、{手机、手机壳}等。

　　强关联规则：满足最小支持度和最小置信度的关联规则。

　　算法步骤从记录中计算所有候选项集，并计算频繁项集和支持。k-item 候选集是从频繁的 1-item 集生成的，k-item 频繁集是从 k-item 候选集计算出来的。用k-item频繁集生成所有关联规则，计算生成规则的置信度，过滤满足最小置信度的关联规则。先验原理

　　任何频繁项的所有非空子集也必须是频繁的。即在生成k-item候选集时，如果候选集中的元素不在k-1项频繁集中，则该元素一定不是频繁集。这时候不需要计算支持度，直接去掉即可。例如，我们有一个由 0、1、2、3 组成的集合，下面是它的所有项集组合：

　　

　　从 1 个项集计算 k 个项集的支持度，当我们计算出 {0,1} 集在 2 个项集候选集中不频繁时，那么它的所有子集都是不频繁的，即 2 个项集 {0 , 1, 2} 和​​ { 0, 1, 3} 也是不频繁的，它们的子集 {0, 1, 2, 3} 也是不频繁的，我们不需要计算不频繁集的支持度。

　　

　　当所有的频繁项都找到后，需要从频繁集中挖掘出所有的关联规则。假设频繁项集{0, 1, 2, 3}，下图显示了它生成的所有关联规则。规则，它们的子集也将是低置信度。

　　

　　Python 实现

　　网上一些Apriori算法的Python实现，其实并不符合python风格。还有一点就是有点难理解，所以实现尽量简洁。

　　1. 数据集

　　用一个列表来表示多条交易记录，每条交易记录也用一个列表来表示一个项集。

　　data = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

　　2. 创建初始候选集

　　这里使用frozenset不可变集合，用于后续以集合为key的支持字典的计算。

　　def apriori(data_set):

# 候选项1项集

c1 = set()

for items in data_set:

for item in items:

item_set = frozenset([item])

c1.add(item_set)

　　3. 从候选项集中选择频繁项集

　　如下图所示，我们需要从初始的候选项集中计算出k个频繁项集，所以这里的封装函数用于每次计算频繁项集和支持度，当候选项集中的每个元素都存在于对事务记录集进行统计并存入字典，计算出支持度后输出频繁项集和支持度。

　　def generate_freq_supports(data_set, item_set, min_support):

freq_set = set() # 保存频繁项集元素

item_count = {} # 保存元素频次，用于计算支持度

supports = {} # 保存支持度

# 如果项集中元素在数据集中则计数

for record in data_set:

for item in item_set:

if item.issubset(record):

if item not in item_count:

item_count[item] = 1

else:

item_count[item] += 1

data_len = float(len(data_set))

# 计算项集支持度

for item in item_count:

if (item_count[item] / data_len) >= min_support:

freq_set.add(item)

supports[item] = item_count[item] / data_len

return freq_set, supports

　　4.生成新组合

　　{1, 2, 3, 5}的频繁项集将从初始候选集生成，后面需要生成一个新的候选集Ck。

　　def generate_new_combinations(freq_set, k):

new_combinations = set() # 保存新组合

sets_len = len(freq_set) # 集合含有元素个数，用于遍历求得组合

freq_set_list = list(freq_set) # 集合转为列表用于索引

for i in range(sets_len):

for j in range(i + 1, sets_len):

l1 = list(freq_set_list[i])

l2 = list(freq_set_list[j])

l1.sort()

l2.sort()

# 项集若有相同的父集则合并项集

if l1[0:k-2] == l2[0:k-2]:

freq_item = freq_set_list[i] | freq_set_list[j]

new_combinations.add(freq_item)

return new_combinations

　　

　　5.循环生成候选集和频繁集

　　def apriori(data_set, min_support, max_len=None):

max_items = 2 # 初始项集元素个数

freq_sets = [] # 保存所有频繁项集

supports = {} # 保存所有支持度

# 候选项1项集

c1 = set()

for items in data_set:

for item in items:

item_set = frozenset([item])

c1.add(item_set)

# 频繁项1项集及其支持度

l1, support1 = generate_freq_supports(data_set, c1, min_support)

freq_sets.append(l1)

supports.update(support1)

if max_len is None:

max_len = float('inf')

while max_items and max_items = min_conf:

rules.append(rule)

return rules

　　7.主程序

　　if __name__ == '__main__':

data = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

L, support_data = apriori(data, min_support=0.5)

rules = association_rules(L, support_data, min_conf=0.7)

print('='*50)

print('frequent \t\tsupport')

print('='*50)

for i in L:

for j in i:

print(set(j), '\t\t', support_data[j])

print()

print('='*50)

print('antecedent consequent \t\tconf')

print('='*50)

rules = association_rules(L, support_data, min_conf=0.7)

for _rule in rules:

print('{} => {}\t\t{}'.format(set(_rule[0]), set(_rule[1]), _rule[2]))

　　

　　Mlxtend 实现

　　Mlxtend 是用于日常数据科学任务的 Python 库。这个库是google在搜索Apriori算法信息时给出的搜索结果之一。通过库的文档可以发现，库的frequent_patterns模块实现了Apriori算法，挖掘关联规则。有兴趣的可以自行搜索相关文档。当然，如果自己实现的话，整个算法的思路会更加清晰。具体实现如下：

　　import pandas as pd

from mlxtend.preprocessing import TransactionEncoder

from mlxtend.frequent_patterns import apriori

from mlxtend.frequent_patterns import association_rules

data = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

te = TransactionEncoder()

te_ary = te.fit(data).transform(data)

df = pd.DataFrame(te_ary, columns=te.columns_)

frequent_itemsets = apriori(df, min_support=0.5, use_colnames=True)

rules = association_rules(frequent_itemsets, min_threshold=0.7)

　　通过TransactionEncoder转换成正确的数据格式，然后使用apriori函数生成频繁项集，最后使用association_rules生成关联规则。可以看出，编码后的数据实际上是一个特征矩阵，每一列对应一个项集元素。