Apriori算法和FP-Tree算法简介

  • 内容
  • 评论
  • 相关

本节主要描述了基于 Apriori 算法的关联分析方法。为了克服 Apriori 算法在复杂度和效率方面的缺陷,本节还进一步的介绍了基于 FP-Tree 的频繁模式挖掘方法。

Apriori关联分析算法

Apriori 算法是挖掘产生关联规则所需频繁项集的基本算法,也是最著名的关联分析算法之一。

1. Apriori 算法

Apriori 算法使用了逐层搜索的迭代方法,即用 k-项集探索(k+1)-项集。为提高按层次搜索并产生相应频繁项集的处理效率,Apriori 算法利用了一个重要性质,该性质还能有效缩小频繁项集的搜索空间。

Apriori 性质:一个频繁项集的所有非空子集也必须是频繁项集。即假如项集 A 不满足最小支持度阈值,即 A 不是频繁的,则如果将项集 B 添加到项集 A 中,那么新项集(AUB)也不可能是频繁的。

Apriori 算法简单来说主要有以下几个步骤。

1)通过单遍扫描数据集,确定每个项的支持度。一旦完成这一步,就可得到所有频繁 1-项集的集合 F1。

2)使用上一次迭代发现的频繁(k-1)-项集,产生新的候选k-项集。

3)为了对候选项集的支持度计数,再次扫描一遍数据库,使用子集函数确定包含在每一个交易 t 中的所有候选 k-项集。

4)计算候选项集的支持度计数后,算法将删除支持度计数小于支持度阈值的所有候选项集。

5)重复步骤(2)、(3)、(4),当没有新的频繁项集产生时,算法结束。

Apriori 算法是个逐层算法,它使用“产生——测试”策略来发现频繁项集。在由(k-1)-项集产生 k-项集的过程中“新产生的 k-项集先要确定它的所有的(k-1)-项真子集都是频繁的,如果有一个不是频繁的,那么它可以从当前的候选项集中去掉。

产生候选项集的方法有以下几种。

1)蛮力法

从 2-项集开始以后所有的项集都是从 1-项集完全拼出来的。例如,3- 项集由 3 个 1-项集拼出,要列出所有的可能性。然后再按照剪枝算法剪枝,即确定当前的项集的所有(k-1)-项集是否都是频繁的。

2)

由 1-项集和(k-1)-项集生成 k-项集,然后再剪枝。这种方法是完全的,因为每一个频繁 k-项集都是由一个频繁(k-1)-项集和一个频繁 1-项集产生的。由于顺序的关系,这种方法会产生大量重复的频繁 k-项集。

3)

由两个频繁(k-1 )-项集生成候选 k-项集,但是两个频繁(k-1)-项集的前 k-2 项必须相同,最后一项必须相异。由于每个候选项集都是由一对频繁(k-1)-项集合并而成的,所以需要附加的候选剪枝步骤来确保该候选的其余 k-2 个子集是频繁的。

2. 由频繁项集产生关联规则

一旦从事务数据集中找出频繁项集,就可以直接由它们产生强关联规则,即满足最小支持度和最小置信度的规则。计算关联规则的置信度并不需要再次扫描事物数据集,因为这两个项集的支持度计数已经在频繁项集产生时得到。

假设有频繁项集 Y,X 是 Y 的一个子集,那么如果规则 X→Y→X 不满足置信度阈值,则形如 X1→Y1→X1 的规则一定也不满足置信度阈值,其中,X1 是 X 的子集。根据该性质,假设由频繁项集 {a,b,c,d}产生关联规则,关联规则{b,c,d}→{a} 具有低置信度,则可以丢弃后件包含 a 的所有关联规则,如{c,d}→{a,b},{b,d}→{a,c} 等。

3. 算法优缺点

Apriori 算法作为经典的频繁项集产生算法,使用先验性质,大大提高了频繁项集逐层产生的效率,它简单易理解,数据集要求低。但是随着应用的深入,它的缺点也逐渐暴露出来,主要的性能瓶颈有以下两点。

  • 多次扫描事务数据集,需要很大的 I/O 负载。对每次 k 循环,对候选集 ck 中的每个元素都必须通过扫描数据集一次来验证其是否加入 lk。
  • 可能产生庞大的候选集。候选项集的数量是呈指数级增长的,如此庞大的候选项集对时间和空间都是一种挑战。

FP-Tree关联分析算法

2000 年,Han Jiawei 等人提出了基于频繁模式树(Frequent Pattern Tree, FP—Tree)的发现频繁模式的算法 FP-Growth。其思想是构造一棵 FP-Tree,把数据集中的数据映射到树上,再根据这棵 FP-Tree 找出所有频繁项集。

FP-Growth 算法是指,通过两次扫描事务数据集,把每个事务所包含的频繁项目按其支持度降序压缩存储到 FP-Tree 中。

在以后发现频繁模式的过程中,不需要再扫描事务数据集,而仅在 FP-Tree 中进行查找即可。通过递归调用 FP-Growth 的方法可直接产生频繁模式,因此在整个发现过程中也不需产生候选模式。由于只对数据集扫描两次,因此 FP-Growth 算法克服了 Apriori 算法中存在的问题,在执行效率上也明显好于 Apriori 算法。

1. FP—Tree 的构造

为了减少 I/O 次数,FP-Tree 算法引入了一些数据结构来临时存储数据。这个数据结构包括 3 部分:项头表、FP-Tree 和结点链接,如图 1 所示。

FP-Tree数据结构
图 1  FP-Tree数据结构

本文标题:Apriori算法和FP-Tree算法简介

本文地址:https://www.hosteonscn.com/5495.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注