数据挖掘2.4——关联规则挖掘 知识点整理

简介: 数据挖掘2.4——关联规则挖掘 知识点整理

1.基本概念

1.1定义

关联分析用于发现隐藏在大型数据集中令人兴趣的联系, 所发现的模式通常用关联规则或频

繁项集的形式表示。

关联规则反映一个事物与其他事物之间的相互依存性和关联性。 如果两个或者多个事物之间存在一定的关联关系, 那么, 其中一个事物发生就能够预测与它相关联的其它事物的发生。

项集

支持度:确定项集的频繁程度

置信度:确认Y在包含X的事务中出现的频繁程度

将关联规则挖掘任务分解为如下两个主要的子任务:

  1. 频繁项集产生 ( Frequent Itemset Generation )
  • 其目标是发现满足最小支持度阈值的所有项集, 这些项集称作频繁项集。
  1. 规则的产生( RuleGeneration )
  • 其目标是从上一步发现的频繁项集中提取所有高置信度的规则, 这些规则称作强规则( strong rule) 。

2.频繁项挖掘算法

2.1降低产生频繁顷集计算复杂度的算法

  • 减少候选项集的数量
    先验原理:(Apriori)
  • 减少比较的次数
    替代将每个候选项集与每个事务相匹配, 可以使用更高级的数据结构, 或存储候选项集或压缩数据集,来减少比较次数(FPGrowth)

2.2 Apriori

先验原理

  • 如果一个项集是频繁的, 则它的所有子集一定也是频繁的;
  • 相反, 如果一个项集是非频繁的, 则它的所有超集也一定是非频繁的。

算法过程:最小支持度计数==2

注意事项

①尽管集合具有无序性, 但为了方便比较计数, 通常对所有商品做一个默认的排序 (类似于建立一个字典索引)。

②项的连接:降低候选项的生成。对于任何2个需要连接的项集,去掉第1个项集的首项、第2个项集的尾项,若剩下的一样即可连接。

特点

①多次扫描数据库

②候选项规模庞大

③计算支持度开销大

提升性能方法

Hash-based itemset counting (散列项集计数)

Transaction reduction (事务压缩)

Partitioning (划分)

Sampling (釆样)

缺点

①需要反复的生成候选项, 如果项的数目比较大, 候选项的数目将达到组合爆炸式的增长

2.3 FPGrowth

基本思想

• 只扫描数据库两遍, 构造频繁模式树 (FP-Tree)

• 自底向上递归产生频繁项集

• FP树是一种输入数据的压缩表示, 它通过逐个读入事务, 并把每个事努映射到FP树中的一条路径来构造

方法

  • 对每个项, 生成它的条件模式基, 然后生成它的条件FP-tree
  • 对每个新生成的条件 FP-tree,重复这个步骤
  • 直到结果FP-tree为, 或只含唯一的一个路径 (此路径的每个子路径对应的项集都是频繁集)

实例1

①构造FP树

  1. 扫描数据库一次, 得到频繁1-项集
  2. 把项按支持度递减排序
  3. 再一次扫描数据库, 建立FP-tree

②生成条件模式

  1. 从 FP-tree 的头表开始
  2. 按照每个频繁项的连接遍历 FP-tree
  3. 列出能够到达此项的所有前缀路径,得到条件模式基

步骤

实例2

优点

  • 完 备:
  • 不会打破交易中的任何模式
  • 包含了频繁模式挖掘所需的全部信息
  • 紧密
  • 支持度降序排列: 支持度高的项在FP-tree中共享的机会也高
  • 决不会比原数据库大

2.4 产生关联规则

针对同一个频繁项集的关联规则, 如果规则的后件满足子集关系, 那么这些规则的置信度间满足反单调性

支持度:确定项集的频繁程度

置信度:确认Y在包含X的事务中出现的频繁程度

3.关联分析的评估

lift计算提升度


目录
相关文章
|
3月前
|
算法 数据挖掘 数据库
【数据挖掘】关联规则、频繁项集、闭项集详解(图文解释 超详细)
【数据挖掘】关联规则、频繁项集、闭项集详解(图文解释 超详细)
121 1
|
5月前
|
人工智能 算法 数据挖掘
数据挖掘(3.1)--频繁项集挖掘方法
关联规则挖掘是数据挖掘领域中研究最为广泛的也最为活跃的方法之一 关联规则反应了一个事物和其他事物之间的相互依存性和关联性 如果存在一定的关联关系,其中一个事物就可以通过其他事物预测到 最小支持度:就是说当支持度达到一定的阈值后,某种数据才有被挖掘的潜力这个阈值就是最小支持度计数(min_sup)。
52 0
|
3月前
|
算法 数据挖掘 数据库
【数据挖掘】频繁项集挖掘方法中Apriori、FP-Growth算法详解(图文解释 超详细)
【数据挖掘】频繁项集挖掘方法中Apriori、FP-Growth算法详解(图文解释 超详细)
86 0
|
4月前
|
机器学习/深度学习 算法 数据挖掘
数据挖掘2.6——聚类 知识点整理
数据挖掘2.6——聚类 知识点整理
59 0
|
4月前
|
数据采集 机器学习/深度学习 算法
数据挖掘2.5——分类 知识点整理
数据挖掘2.5——分类 知识点整理
40 0
|
4月前
|
数据采集 存储 自然语言处理
数据挖掘2.3——数据预处理 知识点整理
数据挖掘2.3——数据预处理 知识点整理
59 0
|
4月前
|
自然语言处理 数据可视化 搜索推荐
数据挖掘2.2——认识数据 知识点整理
数据挖掘2.2——认识数据 知识点整理
55 0
|
4月前
|
机器学习/深度学习 数据采集 存储
数据挖掘2.1——绪论 知识点整理
数据挖掘2.1——绪论 知识点整理
53 0
|
8月前
|
机器学习/深度学习 人工智能 算法
数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘。图算法,搜索算法等
数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘。图算法,搜索算法等
|
9月前
|
算法 数据挖掘 Python
数据挖掘与关联规则:发现隐藏在数据中的模式
数据挖掘是从大规模数据集中发现有价值的信息和模式的过程。其中,关联规则是一种常用的数据挖掘技术,它可以帮助我们发现数据中的相关性和潜在规律。在本文中,我们将介绍关联规则的概念、算法以及如何使用Python实现关联规则的挖掘。
146 0

热门文章

最新文章

相关产品