机器学习--apriori算法

上传人:F****n 文档编号:100404051 上传时间:2019-09-23 格式:DOC 页数:10 大小:30KB
返回 下载 相关 举报
机器学习--apriori算法_第1页
第1页 / 共10页
机器学习--apriori算法_第2页
第2页 / 共10页
机器学习--apriori算法_第3页
第3页 / 共10页
机器学习--apriori算法_第4页
第4页 / 共10页
机器学习--apriori算法_第5页
第5页 / 共10页
点击查看更多>>
资源描述

《机器学习--apriori算法》由会员分享,可在线阅读,更多相关《机器学习--apriori算法(10页珍藏版)》请在金锄头文库上搜索。

1、机器学习-Apriori算法一、基本原理 手机微信关注公众号: datadw 学习数据挖掘,研究大数据,关注你想了解的,分享你需要的。关联分析(association analysis)就是从大规模数据集中寻找物品间的隐含关系。这里的主要问题是,寻找物品的不同组合是一项十分耗时的任务,所需计算代价很高,蛮力搜索方法并不能解决这个问题,所以需要用更智能的方法在合理的时间内找到频繁项集。Apriori算法正是基于该原理得到的。 关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系分为两种形式:频繁项集和关联规则。频繁项集(frequent item sets)是经常出现在一起的物品的集合。其

2、中频繁的概念可以用支持度来定义。支持度(support)被定义为数据集中包含该项集的记录所占的比例,保留满足最小支持度的项集。关联规则(association rules)暗示两种物品之间可能存在很强的关系。关联的概念可用置信度或可信度来定义。 我们的目标是找到经常在一起购买的物品集合,通过使用集合的支持度来度量其出现的频率。一个集合的支持度是指有多少比例的交易记录包含该集合。假如有N种物品,那么这些物品就有2N-1种项集组合。即使只出售100种物品,它们之间的组合数对于现有的计算机也是吃不消的。为了降低这种复杂度,有人提出了Apriori算法。Apriori原理是说如果某个项集是频繁的,那么

3、它的所有子集也是频繁的。反过来,如果某一项集是非频繁集,那么它的所有超集(包含该集的集合)也是非频繁的。二、算法流程 对数据集的每条交易记录transaction 对每个候选项集can: 检查一下can是否是transaction的子集:如果是,则增加can的计数值对每个候选项集:如果其支持度不低于最小值,则保留该项集 返回所有频繁项集列表三、算法的特点 优点:易编码实现缺点:在大规模数据集上可能较慢。适用数据范围:数值型或标称型。四、python代码实现1、创建简单数据集#功能:创建一个简单的测试数据集#说明:数字1、2、3、4、5代表物品1、物品5,# 每个子集代表顾客的交易记录#输入变量

4、:空#输出变量:数据集#def load_data_set(): return 1, 3, 4, 2, 3, 5, 1, 2, 3, 5, 2, 52、创建大小为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

5、() # set和frozenset皆为无序唯一值序列。 # set和frozenset最本质的区别是前者是可变的、后者是不可变的。 # frozenset的不变性,可以作为字典的键值使用。 return map(frozenset, c1)3、保留满足最小支持度的项集#功能:扫描候选集集合,把支持度大于最小支持度的元素留下来,#通过去掉小于支持度的元素,可以减少后面查找的工作量。#输入变量:数据集,候选项集列表,最小支持度#data_set, ck, min_support#输出变量:大于最小支持度的元素列表,包含支持度的字典#ret_list, support_data#def scan_

6、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_cntcan = 1 else: ss_cntcan += 1 num_items = float(len(D) ret_l

7、ist = # 存放大于最小支持度的元素 support_data = for key in ss_cnt: # 遍历字典中每个键值 support = ss_cntkey/num_items # 计算支持度 if support = min_support: ret_list.insert(0, key) support_datakey = support return ret_list, support_data4、生成候选项集#功能:生成候选项集 ck#输入变量:频繁项集,项集元素个数 lk, k#输出变量:每个子集个数为k的不重复集 ret_list#def apriori_gen(l

8、k, 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(lki | lkj) = k: ret_list.append(lki | lkj) # 各个子集进行组合 ret_list = set(ret_list) # 去除重复的组合,构建不重复的集合 return ret_list5、组织完整的Apriori算法#伪代码如下:#当集合中项的个数大于0时# 构建一个k个项组成的候选项集的列表# 检查数据以

9、确认每个项集都是频繁的#保留频繁项集并构建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 # 前面已经生

10、成L1,所以这里从2开始 while len(lk-2) 0: ck = apriori_gen(lk-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_data6、关联规则生成函数#功能:生成一个包含可信度的规则列表#输入变量:# 频繁项集列表 l# 包含那些频繁项集支持数据的字典 support_data#

11、 最小可信度阈值 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 li: 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_list7、计算规则可信度#功能:计算规则的可信度#输入变量:# 频繁项集 freq_set# 每个频繁项集转换成的列表 h# 包含那些频繁项集支持数据的字典 support_data# 关联规则 brl#输出变量:包含可信度的规则列表 pruned_h#def calc_conf(freq_set, h, s

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 教学/培训

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号