您的位置: 首页  >  文章  >  1.6关联规则（fpm）

1.6关联规则（fpm）

分类: 文章 • 2024-11-12 22:30:58

1.6 关联规则（fpm）

1.6.1 关联规则（FPGrowth(Frequent Pattern Growth)）

关联规则挖掘的一个典型例子是购物篮分析。关联规则的研究有助于发现交易数据库中不同商品（项）之间的关系，找出顾客购买行为模式，如{啤酒，尿布}。

首先弄清楚几个概念：

  1. 项（item）：即商品；项集：若干项的集合。
  2. 关联规则：关联规则用于表示数据内隐含的关联性。一般记X为先决条件、Y为相应的关联结果。关联性强度如何由3个概念控制和评价：支持度、置信度和提升度。
  3. 支持度（support）：支持度是指在所有项集中{X, Y}出现的可能性，即项集中同时含有X和Y的概率。通过设定最小阈值（minsup），剔除“出镜率”较低的无意义规则，保留出现较为频繁的项集所隐含的规则。（类TF-IDF词频-逆向文件频率）
  4. 置信度（confidence）：置信度表示在先决条件X发生的条件下，关联结果Y发生的概率，需要对置信度设定阈值（mincon）来实现进一步筛选。
  5. 提升度：提升度表示在含有X的条件下同时含有Y的可能性与没有X这个条件下项集中含有Y的可能性之比；公式为confidence（artichok=>cracker）/support(cracker)。该指标与置信度同样衡量规则的可靠性，可以看作是置信度的一种互补指标。

FPGrowth算法核心是构造GPTree树，FPTree树实现了：增加事务、合并树、取后缀树、取节点事物集、提取频繁项集（频繁项集，同时出现{尿布，啤酒}的项集）等方法，这些方法都是实现频繁项集挖掘的核心方法。FPGrowth算法分为两个过程：构造FP树和挖掘FP树。

构造FP树：

  1. 扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。
  2. 创建FP-树的根结点，以“null”标记它。对于D 中每个事务Trans，执行：选择 Trans 中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p | P]，其中，p 是第一个元素，而P 是剩余元素的表。调用insert_tree([p | P], T)。该过程执行情况如下。如果T有子女N使得N.item-name = p.item-name，则N 的计数增加1；否则创建一个新结点N将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name的结点。如果P非空，递归地调用insert_tree(P, N)。

挖掘FP树：

通过调用FP_growth(FP_tree, null)实现。该过程实现如下：

FP_growth(Tree, α)

  1. if Tree 含单个路径P then {
  2. for 路径 P 中结点的每个组合（记作β）
  3. 产生模式β ∪ α，其支持度support = β中结点的最小支持度；
  4. else for each ai在Tree的头部(按照支持度由低到高顺序进行扫描) {
  5. 产生一个模式β = ai ∪ α，其支持度support = ai .support；
  6. 构造β的条件模式基，然后构造β的条件FP-树Treeβ；
  7. if Treeβ ≠ ∅ then
  8. 调用 FP_growth (Treeβ, β)；}

注：Apriori算法：

Apriori算法是常用的关联规则挖掘算法，基本思想是：

(1) 先搜索出1项集及其对应的支持度，删除低于支持度的项集，得到频繁1项集L1；

(2) 对L1中的项集进行连接，得到一个候选集，删除其中低于支持度的项集，得到频繁1项集L2；

...

迭代下去，一直到无法找到L(k+1)为止，对应的频繁k项集集合就是最后的结果。

Apriori算法的缺点是对于候选项集里面的每一项都要扫描一次数据，从而需要多次扫描数据，I/O操作多，效率低。为了提高效率，提出了一些基于Apriori的算法，比如FPGrowth算法。FPGrowth算法采取分治策略：将提供频繁项集的数据库压缩到一颗频繁模式树（FP树），但仍保留项集关联信息。该算法和Apriori算法最大的不同有两点：不产生候选集，只需要两次遍历数据库。这大大提高了效率。

1.6.2 前缀投影的模式挖掘（Prefix Span(Prefix-Projected Pattern Growth)）

FPTree和Apriori算法是挖掘频繁项集的，而Prefix Span算法是挖掘频繁序列模式的。

Prefix Span相关概念：

首先，项集数据和序列数据是有区别的：每个项集有若干项组成，这些项没有时间上的先后关系；而序列数据是由若干项集数据组成的序列，并且这些项有时间上的先后关系。其次，子序列与数学上子集概念类似，而频繁序列跟频繁项集类似，也就是频繁出现的子序列。再者，Prefix Span算法全称是Prefix-Projected Pattern Growth，即前缀投影的模式挖掘。前缀prefix就是序列数据前面部分的子序列，后缀即为序列里前缀后面剩下的子序列。在Prefix Span算法中，相同前缀对应的所有后缀的结合成为前缀对应的投影数据库。

Prefix Span算法的思想：

Prefix Span算法的目标是挖掘出满足最小支持度的频繁序列。Apriori算法是从频繁1项集出发，一步步挖掘频繁2项集，直到最大的K项集。Prefix Span算法类似，它从长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库得到长度为1的前缀对应的频繁序列，然后递归的挖掘长度为2的前缀所对应的频繁序列......以此类推，直到递归不能挖掘到更长的前缀为止。

Prefix Span算法流程：

输入：序列数据集S和支持度阈值α，输出：所有满足支持度要求的频繁序列集。

  1. 找出所有长度为1的前缀和对应的投影数据库。
  2. 对长度为1的前缀进行技术，将支持度低于阈值α的前缀对应项从数据集S中删除，同事得到所有的频繁1项序列，i = 1.
  3. 对于每个长度为i满足支持度要求的前缀进行递归挖掘：
  1. 找出前缀对应的投影数据库。如果投影数据库为空，则递归返回。
  2. 统计对应投影数据库中各项的支持度计数。如果所有想的支持度技术都低于阈值α，则递归返回。
  3. 将满足支持度计数的各个单项和当前的前缀进行合并，得到若干新的前缀。
  4. 令i = i + 1，前缀为合并单项后的各个前缀，分别递归执行第3步。

Prefix Span算法总结：

Prefix Span算法由于不用产生候选序列，且投影数据库缩小的很快，内存消耗比较稳定，做频繁序列模式挖掘的时候效果很好。Prefix Span运行时最大的消耗在递归的构造投影数据库。如果序列数据集较大，项数种类较多时，算法运行速度会有明显下降。当然使用大数据平台的分布式计算能力也是加快Prefix Span运行速度的一个好办法。

 

返回主目录（Spark MLlib算法思想总结）

 

1.6关联规则（fpm）

相关推荐