文章目录
  1. 1. 基本原理
  2. 2. 算法流程
  3. 3. 算法的特点
  4. 4. python代码实现
    1. 4.1. 创建简单数据集
    2. 4.2. 创建大小为1的不重复项集
    3. 4.3. 保留满足最小支持度的项集
    4. 4.4. 生成候选项集
    5. 4.5. 组织完整的Apriori算法
    6. 4.6. 关联规则生成函数
    7. 4.7. 计算规则可信度
    8. 4.8. 代码测试

基本原理

关联分析(association analysis)就是从大规模数据集中寻找物品间的隐含关系。这里的主要问题是,寻找物品的不同组合是一项十分耗时的任务,所需计算代价很高,蛮力搜索方法并不能解决这个问题,所以需要用更智能的方法在合理的时间内找到频繁项集。Apriori算法正是基于该原理得到的。

关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系分为两种形式:频繁项集和关联规则。频繁项集(frequent item sets)是经常出现在一起的物品的集合。其中频繁的概念可以用支持度来定义。支持度(support)被定义为数据集中包含该项集的记录所占的比例,保留满足最小支持度的项集。关联规则(association rules)暗示两种物品之间可能存在很强的关系。关联的概念可用置信度或可信度来定义。

我们的目标是找到经常在一起购买的物品集合,通过使用集合的支持度来度量其出现的频率。一个集合的支持度是指有多少比例的交易记录包含该集合。假如有N种物品,那么这些物品就有2^N-1种项集组合。即使只出售100种物品,它们之间的组合数对于现有的计算机也是吃不消的。为了降低这种复杂度,有人提出了Apriori算法。Apriori原理是说如果某个项集是频繁的,那么它的所有子集也是频繁的。反过来,如果某一项集是非频繁集,那么它的所有超集(包含该集的集合)也是非频繁的。

算法流程

对数据集的每条交易记录transaction
对每个候选项集can:
检查一下can是否是transaction的子集:
如果是,则增加can的计数值
对每个候选项集:
如果其支持度不低于最小值,则保留该项集
返回所有频繁项集列表

算法的特点

优点:易编码实现
缺点:在大规模数据集上可能较慢。
适用数据范围:数值型或标称型。

python代码实现

创建简单数据集

功能:创建一个简单的测试数据集
说明:数字1、2、3、4、5代表物品1、、、物品5,
每个子集代表顾客的交易记录
输入变量:空
输出变量:数据集


def load_data_set():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

创建大小为1的不重复项集

功能:构建一个大小为1的不重复候选项集
输入变量:测试数据集
输出变量:候选项集合

def create_c1(data_set):
c1 = []
for transaction in data_set: # 遍历数据集中所有的交易记录
for item in transaction: # 遍历每条记录的每一项
if [item] not in c1: # 如果该物品没有在c1中
c1.append([item])
c1.sort()
# set和frozenset皆为无序唯一值序列。
# set和frozenset最本质的区别是前者是可变的、后者是不可变的。
# frozenset的不变性,可以作为字典的键值使用。
return map(frozenset, c1)

保留满足最小支持度的项集

功能:扫描候选集集合,把支持度大于最小支持度的元素留下来,
通过去掉小于支持度的元素,可以减少后面查找的工作量。
输入变量:数据集,候选项集列表,最小支持度
data_set, ck, min_support
输出变量:大于最小支持度的元素列表,包含支持度的字典

ret_list, support_data

def scan_d(data_set, ck, min_support):
D = map(set, data_set)
ss_cnt = {}
for tid in D: # 遍历数据集中所有交易
for can in ck: # 遍历候选项集
# 判断候选集中该集合是数据集中交易记录的子集
# set().issubset()判断是否是其子集
if can.issubset(tid):
# 判断该集合是否在空字典ss_cnt
if can not in ss_cnt.keys():
ss_cnt[can] = 1
else:
ss_cnt[can] += 1
num_items = float(len(D))
ret_list = [] # 存放大于最小支持度的元素
support_data = {}
for key in ss_cnt: # 遍历字典中每个键值
support = ss_cnt[key]/num_items # 计算支持度
if support >= min_support:
ret_list.insert(0, key)
support_data[key] = support
return ret_list, support_data

生成候选项集

功能:生成候选项集 ck
输入变量:频繁项集,项集元素个数 lk, k
输出变量:每个子集个数为k的不重复集 ret_list

def apriori_gen(lk, k):
print 'lk=', lk
print 'k=', k
ret_list = []
len_lk = len(lk)
for i in xrange(len_lk-1):
for j in xrange(i+1, len_lk):
if len(lk[i] | lk[j]) == k:
ret_list.append(lk[i] | lk[j]) # 各个子集进行组合
ret_list = set(ret_list) # 去除重复的组合,构建不重复的集合
return ret_list

组织完整的Apriori算法

伪代码如下:
当集合中项的个数大于0时
构建一个k个项组成的候选项集的列表
检查数据以确认每个项集都是频繁的
保留频繁项集并构建k+1项组成的候选项集的列表

功能:构建频繁项集列表
输入变量:原始数据集,最小支持度 data_set, min_support
输出变量:频繁项集列表,大于最小支持度的元素列表
l, ret_list

def apriori(data_set, min_support=0.5):
c1 = create_c1(data_set)
# #扫描数据集,由C1得到L1
l1, support_data = scan_d(data_set, c1, min_support)
l = [l1] # 构建L列表,其中第一个元素为L1列表
k = 2 # 前面已经生成L1,所以这里从2开始
while len(l[k-2]) > 0:
ck = apriori_gen(l[k-2], k) # 由L(k-1)生成Ck
print 'ck=', ck
# 扫描数据集,由Ck得到Lk
lk, support_k = scan_d(data_set, ck, min_support)
support_data.update(support_k)
l.append(lk)
k += 1
return l, support_data

关联规则生成函数

功能:生成一个包含可信度的规则列表
输入变量:
频繁项集列表 l
包含那些频繁项集支持数据的字典 support_data
最小可信度阈值 min_conf
输出变量:包含可信度的规则列表 big_rule_list

def generate_rules(l, support_data, min_conf=0.7):
big_rule_list = []
for i in xrange(1, len(l)):
for freq_set in l[i]:
h1 = [frozenset([item]) for item in freq_set]
print "h1=", h1
if i > 1:
rules_from_conseq(freq_set, h1, support_data, big_rule_list,
min_conf)
else:
calc_conf(freq_set, h1, support_data, big_rule_list, min_conf)
return big_rule_list

计算规则可信度

功能:计算规则的可信度
输入变量:
频繁项集 freq_set
每个频繁项集转换成的列表 h
包含那些频繁项集支持数据的字典 support_data
关联规则 brl
输出变量:包含可信度的规则列表 pruned_h

def calc_conf(freq_set, h, support_data, brl, min_conf=0.7):
pruned_h = []
for conseq in h:
conf = support_data[freq_set]/support_data[freq_set-conseq]
print 'freq_set:', freq_set
print 'conseq:', conseq
print 'freq_set-conseq:', freq_set-conseq
if conf >= min_conf:
print freq_set-conseq, '-->', conseq, 'conf:', conf
brl.append((freq_set-conseq, conseq, conf))
pruned_h.append(conseq)
return pruned_h

功能:频繁项集中元素多于两个用这个函数生成关联规则
输入变量:
频繁项集 freq_set
每个频繁项集转换成的列表 h
包含那些频繁项集支持数据的字典 support_data
关联规则 brl
输出变量:空

def rules_from_conseq(freq_set, h, support_data, brl, min_conf=0.7):
m = len(h[0])
if len(freq_set) > (m+1):
hmp1 = apriori_gen(h, m+1)
hmp1 = calc_conf(freq_set, hmp1, support_data, brl, min_conf)
if len(hmp1) > 1:
rules_from_conseq(freq_set, hmp1, support_data, brl, min_conf)

代码测试

def main():
data_set = load_data_set()
print 'data_set=', data_set
c1 = create_c1(data_set)
print 'c1=', c1
# l1, support_data = scan_d(data_set, c1, 0.5)
# print 'l1=', l1
# print 'support_data=', support_data
l, support_data = apriori(data_set)
print 'l=', l
print 'support_data=', support_data
rules = generate_rules(l, support_data)
print 'rules=', rules
if __name__ == '__main__':
main()
文章目录
  1. 1. 基本原理
  2. 2. 算法流程
  3. 3. 算法的特点
  4. 4. python代码实现
    1. 4.1. 创建简单数据集
    2. 4.2. 创建大小为1的不重复项集
    3. 4.3. 保留满足最小支持度的项集
    4. 4.4. 生成候选项集
    5. 4.5. 组织完整的Apriori算法
    6. 4.6. 关联规则生成函数
    7. 4.7. 计算规则可信度
    8. 4.8. 代码测试