机器学习--Apriori算法

一、基本原理

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

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

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

二、算法流程

对数据集的每条交易记录transaction

对每个候选项集can:

检查一下can是否是transaction的子集:

如果是,则增加can的计数值

对每个候选项集:

如果其支持度不低于最小值,则保留该项集

返回所有频繁项集列表

三、算法的特点

优点:易编码实现

缺点:在大规模数据集上可能较慢。

适用数据范围:数值型或标称型。

四、python代码实现

1、创建简单数据集

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

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

2、创建大小为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)

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

#################################### #功能:扫描候选集集合,把支持度大于最小支持度的元素留下来, #通过去掉小于支持度的元素,可以减少后面查找的工作量。 #输入变量:数据集,候选项集列表,最小支持度 #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

4、生成候选项集

#################################### #功能:生成候选项集 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

5、组织完整的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

6、关联规则生成函数

#################################### #功能:生成一个包含可信度的规则列表 #输入变量: # 频繁项集列表 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

7、计算规则可信度

#################################### #功能:计算规则的可信度 #输入变量: # 频繁项集 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()

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-07-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

百度 阿里 华为 腾讯 谷歌面试笔试题及解析

点评:其余题目请参见:http://blog.csdn.net/doc_sgl/article/details/11695671。 2、一个有10亿条记录...

6263
来自专栏大数据挖掘DT机器学习

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.ht...

3285
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

5029
来自专栏机器学习算法原理与实践

PrefixSpan算法原理总结

    前面我们讲到频繁项集挖掘的关联算法Apriori和FP Tree。这两个算法都是挖掘频繁项集的。而今天我们要介绍的PrefixSpan算法也是关联算法,...

771
来自专栏Python小屋

Python使用scipy进行多项式计算与符号计算

在扩展库numpy和scipy中都有poly1d,用法一样,实际上是同一个库,scipy是基于numpy的。有图为证 ? 本文代码主要演示如何使用poly1d进...

4906
来自专栏AILearning

【机器学习实战】第11章 使用 Apriori 算法进行关联分析

第 11 章 使用 Apriori 算法进行关联分析 ? 关联分析 关联分析是一种在大规模数据集中寻找有趣关系的任务。 这些关系可以有两种形式: 频繁项集(...

3276
来自专栏程序员叨叨叨

6.3 数学操作符(Math Operators)

Cg语言对向量的数学操作提供了内置的支持,Cg中的数学操作符有:*乘法、/除法、-取反、+加法、—减法、%求余、++、——、*=、/=、+=、-=。后面四种运算...

851
来自专栏常用编程思想与算法

常用编程思想与算法

本文是在阅读Aditya Bhargava先生算法图解一书所做的总结,文中部分代码引用了原文的代码,在此感谢Aditya Bhargava先生所作出的这么简单的...

2031
来自专栏数据派THU

一文解读Tensor到底是个啥玩意儿?(附代码)

本文介绍了各种数值型数据的容器(标量、向量、矩阵、张量)之间的关系,在实践中,张量特指3维及更高维度的数据容器。

1493
来自专栏落影的专栏

程序员进阶之算法练习(十八)

前言 最近在接触新知识,也是选择2017年的方向。 其他文集更新会放缓,没有学习就没有心得,肚中无墨就无从下笔。 但是算法练习还是挺好玩的,欢迎关注algo...

3525

扫码关注云+社区

领取腾讯云代金券