机器学习_规则与关联规则模型Apriori、FP-Growth
机器学习 _ 规则与关联规则模型 Apriori、FP-Growth
#机器学习 #关系规则
1. 何时使用规则模型
机器学习时常遇到一个问题:当数据并不完全可分时,分类器得分不高。真实世界中的数据经常是这样:各种无意义数据和少量有意义数据混在一起,无意义数据又没什么规律,无法统一去除。比如说,对股票外汇市场受各种因素影响,预测次日涨跌一般各算法效果都不好。虽然找不到通用的规则,却能在数据中探索到一些模式,比如十字星,孕线,三只乌鸦等组合还是具有一定的预测性。
之前使用决策树时,就遇到过这种情况,虽然整体得分不高,但某些叶节点上纯度高(全是正例或全是反例)并且实例多,可以把该分枝拿出来当规则使用。虽然不能用它预测任意数据,但可以作为一个过滤器使用。
2. 规则模型是什么
规则模型和决策树同属逻辑模型,不同的是决策树对正例反例同样重视,而规则只重视正例/反例其中一项。因此决策树呈现的是互斥关系,而规则模型允许重叠,结果也相对零散的规则列表。规则更像是在大量数据中挑选有意义的数据。
如果说树是精确模型,规则模型则是启发式策略(虽然经过修改也能覆盖所有实例,但一般不这么用)。它可以找到数据集中的一个子集,相对于全部数据,该子集有明显的意义。
规则模型多用于处理离散数据,如文本中查找频繁单词,提取摘要,分析购物信息等等。
3. 具体实现
在实现上,我们可以把规则当成树的变种,稍加修改,便是规则模型。具体有两种做法:一种是找规则,使其覆盖同质(全真或全假)的样本集(和树类似);另一种是选定类别,找覆盖该类别实例样本的规则集。
4. 关联规则
规则是一个用途很多的算法,关于规则模型的文章不多,有的书把它归入逻辑推理中,而非机器学习。我们最常见的是关联规则,比如用 Apriori 实现的频繁项集挖掘算法。
最经典的是购物篮分析中啤酒、尿布的故事,即通过对购物清单的分析,发现看似毫无关系的啤酒和尿布经常在用户的购物篮中一起出现,通过挖掘出啤酒、尿布这个频繁项集,则当一个用户买了啤酒的时候可以为他推荐尿布,从而达到组合营销的目的。
下面将介绍两种基于关联规则的无监督学习算算法 Apriori 和 FP-growth
5. Apriori
(1) 介绍
Apriori 这个单词在拉丁语中的意思是“来自以前”,也可拆开为 a priori,即一次先验。算法的目标是找到出现频率高的简单规则。
(2) 原理
如果某个项是频繁的,那么它的所有子集也是频繁的。反之,如果一个项集是非频繁的,那么它的超集也是非频的。比如啤酒和尿布常常同时出现,则啤酒单独出现的机率也很高;如果这个地区的人极少喝啤酒,啤酒和尿布的组合也不会常常出现。
(3) 算法
生成单个物品列表,去掉频率低于支持度的,再组合两个物品,去掉低于支持度的,以此类推,求出频繁项集,在频繁项集中抽取关联规则。
算法的输入是大量可能相关的数据组合,支持度,置信度。输出是频率项集或关联规则。
(4) 优缺点
Apriori 的优点是易于理解,缺点是算得慢,如果共有 N 件物品,计算量是 2^N-1。在属性过多,或属性的状态过多时都会导致大量计算。
(5) 相关概念
支持度:数据集中包含该项集的记录所占的比例
置信度:同时支持度/部分支持度(纯度)
频繁项集:经常同时出现的物品的集合
关联规则:两种物品间可能存在很强的关系,比如 A,B 同时出现,如果 A->B,则 A 称为前件,B 称为后件。如果 A 发生概率 50%,而 AB 概率 25%,则 A 不一定引发 B,但如果 AB 发生概率为 49%,则说明 A->B。
(6) 例程
- 功能
从多次购物数据中取频率项集,并显示各组合的支持度
- 代码
1 | # -*- coding: utf-8 -*- |
- 结果
1 | [[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []] |
6. FP-growth
(1) 介绍
FP 是 Frequent Pattern 的缩写,代表频繁模式。FP-growth 比 Apriori 快,性能提高在两个数量级以上,在大数据集上表现更佳。
和 Apriori 多次扫描原始数据相比,FP-Growth 算法则只需扫描原始数据两遍,把数据存储在 FP-Tree 结构中。
(2) FP-Tree
与搜索树不同的是,一个元素项可以在 FP 树中出现多次,FP 树会存储项集的出现频率。每个项集会以路径的方式存储在树中,存在相似元素的集合会共享树的一部分,只当集合之间完全不同时,树才会分叉。
除了树,还有个索引表(Header table),把所有含相同元素的组织起来 (link list),以便查找。
(3) 算法
先构建 FP 树,然后从 FP 树中挖掘频繁项集
- 收集数据
数据是五次购物的清单(记录),a,b,c,d…分别代表物品(item)
- 去除非频繁项 l, i, o 等,并排序
- 将记录依次加入树,并建立索引表(左侧框),粉色为添加第一次购物数据。
- 从下往上构造每个 item 的条件模式基 CPB(conditional pattern base)
顺着 header table 中 item 的链表,找出所有包含该 item 的前缀路径,这些前缀路径就是该 item 的条件模式基(CPB)
所有这些 CPB 的频繁度(计数)为该路径上 item 的频繁度(计数)
如包含 p 的其中一条路径是 fcamp,该路径中 p 的频繁度为 2,则该 CPB fcam 的频繁度为 2
- 构造条件 FP-tree(conditional FP-tree)
累加每个 CPB 上的 item 的频繁度(计数),过滤低于阈值的 item,构建 FP-tree
如 m 的 CPB{
递归的挖掘每个条件 FP-tree,累加后缀频繁项集,直到找到 FP-tree 为空或者 FP-tree 只有一条路径。