关联规则分析及应用ppt课件

2. 2 挖掘过程
第一阶段 找出所有频繁项集 (Large Itemsets) 第二阶段 由频繁项集产生强关联规则（Association Rules ）
3. 1 相关算法
Apriori算法 基于划分的算法 FP-Grow算法
3.2 Apriori算法
思想:
首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集 的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项 集被发现.每个Lk都要求对数据库作一次完全扫描.
2.1 基本概念
交易数据库（D） 交易/事务 （T）
T I
交易标识符（TID） 项集（I）
I {i1,i2,..i.m},
规则 i1 i2
支持度support: D中包含i1和 i2 的事务数与总的事务数的比值
s(A B)|{ | TD| |AD| |B|T}||
可信度 confidence: D中同时包含i1和i2的事务数与包含i1的事务数的比值
2.1 基本概念
阈值 最小支持度 – 表示规则中的所有项在事务中出现的频度 最小可信度 - 表示规则中左边的项(集)的出现暗示着右
边的项(集)出现的频度
项集 – 任意项的集合 k-项集 – 包含k个项的项集 频繁 (或大)项集 – 满足最小支持度的项集 强规则:那些满足最小支持度和最小可信度的规则.
Apriori算法
候选项集生成的示例 L3={ abc, abd, acd, ace, bcd } 自连接: L3*L3 由abc 和abd 连接得到abcd 由acd 和ace 连接得到acde 剪枝: 因为ade 不在L3中acde 被剪除
Apriori算法
挑战： 多次扫描事务数据库 巨大数量的候选项集 繁重的计算候选项集的支持度工作 改进 Apriori: 大体的思路 减少事务数据库的扫描次数 缩减候选项集的数量 使候选项集的支持度计算更加方便

关联规则及相关算法
1
主要内容
?关联规则概述 ?Apriori 算法 ?CARMA 算法 ?序列模式
2
关联规则概述
?数据关联是数据库中存在的一类重要的可被发现的 知识。若两个或多个变量的取值之间存在某种规律 性，就称为 关联。
?关联规则挖掘的一个典型例子是购物篮分析。
?啤酒与尿布的故事
3
啤酒与尿布的故事
?1. 算法组成 ?2. 算法中的符号定义 ?3. 算法的基本过程
?㈡ 实例说明 ?
?4. 用一个简单的例子说明算法原理。
?㈢ CARMA 算法描述 ?
?5. 用自然语言描述算法的实现过程。
27
已有的一些关联规则挖掘算法在运行之前要 求用户输入最小置信度和最小支持度。而对用户 来讲，确定合适的最小置信度和最小支持度比较 困难，需要运行算法多次判断最小置信度和最小 支持度是否过高或过低。
? 在这些原始交易数据的基础上，沃尔玛利用数据 挖掘方法对这些数据进行分析和挖掘。
5
啤酒与尿布的故事
? 一个意外的发现是：跟尿布一起购买最多的商品 竟是啤酒！
? 经过大量实际调查和分析，揭示了一个隐藏在“ 尿布与啤酒”背后的美国人的一种行为模式：
?在美国，一些年轻的父亲下班后经常要到超市去买婴 儿尿布，而他们中有30%～40%的人同时也为自己买 一些啤酒。产生这一现象的原因是：美国的太太们常 叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买 尿布后又随手带回了他们喜欢的啤酒。
在Clementine 中应用Apriori 算法
?应用Apriori 节点来对某超市的客户采购数据集进 行购物篮分析。该数据集包含有 21个属性（这些 属性包括： COD、pasta 、milk 、water 、 biscuits 、coffee 、brioches 、yoghurt 、frozen vegetables 、tunny 、beer 、tomato 、souce 、 coke 、rice 、juices 、crackers 、oil 、frozen fish 、ice cream 、mozzarella 、tinned meat 。 其中“COD”是记录编号，其它 20个属性代表 20 种商品），共 46243个记录。每个属性代表某种 商品，其取值为“ 0”或者“1”，“0”表示没有购 买该商品，“ 1”表示购买了该商品。

置信度评估
评估关联规则的置信度，以确定规则是否具有可信度 。
剪枝
根据规则的置信度和支持度进行剪枝，去除低置信度 和低支持度的规则。
04 Apriori算法的优化策略
基于散列的技术
散列技术
通过散列函数将数据项映射到固定大小的桶中，具有相同散列值的数据项被分配 到同一个桶中。这种方法可以减少候选项集的数量，提高算法效率。
散列函数选择
选择合适的散列函数可以减少冲突，提高散列技术的效率。需要考虑散列函数的 均匀分布性和稳定性。
基于排序的方法
排序技术
对数据项按照某种顺序进行排序，如 按照支持度降序排序，优先处理支持 度较高的数据项，减少不必要的计算 和比较。
排序算法选择
选择高效的排序算法可以提高算法效 率，如快速排序、归并排序等。
关联规则的分类
关联规则可以根据不同的标准进行分类。
根据不同的标准，关联规则可以分为多种类型。根据规则中涉及的项的数量，可以分为单维关联规则和多维关联规则。根据 规则中项的出现顺序，可以分为无序关联规则和有序关联规则。根据规则的置信度和支持度，可以分为强关联规则和弱关联 规则。
关联规则挖掘的步骤
关联规则挖掘通常包括以下步骤：数据预处理、生成 频繁项集、生成关联规则。
关联规则简介与 Apriori算法课件
目录
• 关联规则简介 • Apriori算法简介 • Apriori算法的实现过程 • Apriori算法的优化策略 • 实例分析 • 总结与展望
01 关联规则简介
关联规则的定义
关联规则是数据挖掘中的一种重要技术，用于发现数据集中 项之间的有趣关系。
关联规则是一种在数据集中发现项之间有趣关系的方法。这 些关系通常以规则的形式表示，其中包含一个或多个项集， 这些项集在数据集中同时出现的频率超过了预先设定的阈值 。

如果一个项集包含k个项 支持度计数（Support count ）() – 包含特定项集的事务个数 – 例如： ({Milk, Bread,Diaper}) = 2 支持度（Support） – 包含项集的事务数与总事务数的比值 – 例如： s({Milk, Bread, Diaper}) =
2/5 频繁项集（Frequent Itemset） – 满足最小支持度阈值（ minsup ）的
先验原理（ Apriori principle）
先验原理:
– 如果一个项集是频繁的，则它的所有子集一定也是频繁 的
相反，如果一个项集是非频繁的，则它的所有超集 也一定是非频繁的:
– 这种基于支持度度量修剪指数搜索空间的策略称为基于 支持度的剪枝（support-based pruning）
– 这种剪枝策略依赖于支持度度量的一个关键性质，即一 个项集的支持度决不会超过它的子集的支持度。这个性 质也称为支持度度量的反单调性（anti-monotone）。
4
Bread, Milk, Diaper, Beer
关联规则的强度
5
Bread, Milk, Diaper, Coke
– 支持度 Support (s) 确定项集的频繁程度
Example:
{M,iD lkia}p e Bree
– 置信度 Confidence (c) 确定Y在包含X的事 务中出现的频繁程度
Brute-force 方法:
– 把格结构中每个项集作为候选项集
– 将每个候选项集和每个事务进行比较，确定每个候选项集 的支持度计数。
Transactions
TID Items
1 Bread, Milk
2 Bread, Diaper, Beer, Eggs