文档介绍：大数据应用人才培养系列教材
数据挖掘基础
刘鹏张燕总主编
陶建辉主编姜才康副主编
第四章　关联规则
　关联规则的基本概念
　关联规则的挖掘过程
　关联规则的Apriori算法
　关联规则的FP-Growth算法
习题
大数据应用人才培养系列教材
关联规则的基本概念
第四章关联规则
关联规则概念最早是由Agrawal等人在1993年首先提出的，最初的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。Agrawal等人于1993年提出了关联规则挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。
关联规则的基本概念
第四章关联规则
More
应用市场：市场货篮分析、交叉销售（Crossing Sale）、部分分类（Partial Classification）、金融服务（Financial Service），以及通信、互联网、电子商务 ······
关联规则的基本概念
第四章关联规则
基本概念
1）项（Item）、项集（Itemset）、k-项集与事务
项：是指数据库中不可分割的最小单位。
项集：是指多个项的集合，其中，空集是指不包含任何项的项集。
k-项集：是指由k个项构成的项集组合。
事务：是指用户定义的一个数据库操作序列，这些操作序列是一个不可分割的工作单位。
2）频繁项集（Frequent Itemset）
频繁项集：是指在所有训练元组中同时出现的次数，超过人工定义的阈值的项集。在关联规则的挖掘过程中，一般只保留候选项集中满足支持度条件的项集，不满足条件的舍弃。
关联规则的基本概念
第四章关联规则
基本概念
3）极大频繁项集（Frequent Large Itemset）
极大频繁项集：不存在包含当前频繁项集的频繁超集，则当前频繁项集就是极大频繁项集。
4）支持度（Support）
支持度：是指项集在所有训练元组中同时出现的次数，因此，支持度可以表述为Support(X->Y) = |X U Y|/ |N|。其中，X，YN，X∩Y=Ф，|X U Y|表示集合X与Y在一个事务中同时出现的次数，|N|表示数据记录的总个数。
5）置信度（Confidence）
置信度可以表述为：Confidence (X->Y)= |X U Y|/ |X| = Support(X->Y) / Support（X），其中，X，YN，X∩Y=Ф，|X U Y|表示集合X与Y在一个事务中同时出现的次数，|X|表示X出现的总次数。
关联规则的基本概念
第四章关联规则
关联规则定义
关联规则（Association rule）：指从事务数据库、关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。
关联分析（Association analysis）：用于发现隐藏在大型数据集中的令人感兴趣的联系。所发现的联系可以用关联规则或者频繁项集的形式表示。关联规则挖掘就是从大量的数据中挖掘出描述数据项之间相互联系的有价值的有关知识。
关联规则的基本概念
第四章关联规则
关联规则定义
一般地，关联规则挖掘问题可以划分成两个子问题：
1）发现频繁项目集
通过用户给定的Minsupport，寻找所有频繁项目集，即满足Support不小于Minsupport的项目集。事实上，这些频繁项目集可能具有包含关系。一般地，我们只关心那些不被其它频繁项目集所包含的所谓频繁大项集的集合。这些频繁大项集是形成关联规则基础。
2）生成关联规则
通过用户给定的Minconfidence，在每个最大频繁项目项目集中，寻找Confidence不小于Minconfidence的关联规则。。
关联规则的基本概念
第四章关联规则
关联规则分类
1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数