关联规则（第七章）.ppt

第7章 关联规则,7.1 关联规则 7.2 关联规则的挖掘方法7.3 算法与讨论7.4 Apriori算法（操作实例）,7.1 关联规则-引言,关联：是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性关联可分为简单关联、时序关联、因果关联关联分析：目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度关联规则：是关联分析的常见结果，用于寻找在同一个事件中出现的不同项的相关性关联规则发现的主要对象是交易型数据库；关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品A的出现对物品B的出现有多大的影响,7.1 关联规则-例子,购物篮分析－引发关联规则挖掘的例子问题：什么商品组或集合顾客多半会在一次购物中同时购买？购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物（即事务）所购商品为项目全集的子集若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式，这些模式可用关联规则描述如：computerfinancial_management_software [support=2%,confidence=60%]support为支持度，confidence为可信度；该规则表示：在所分析的全部事务中，有2％的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60％也购买财务管理软件,7.1 关联规则-概念-1,关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系形式化定义：令I={i1，i2，…,in}是项的集合，即项集，包含k个项的项集为k-项集；事务T是I上的一个子集，集合TI，每个事务用唯一的标志TID来标识；D是全体事务的集合关联规则（语法）：是形如A→B的蕴含式，其中AI，BI且AB=，A称为规则的条件，B称为规则的结果,7.1 关联规则-概念-2,关联规则的支持度和可信度支持度是重要性的度量；可信度是准确度的度量规则 A→B具有支持度S，表示S是D中事务包含AUB的百分比，即联合概率P(AUB)，也可以表示为： support(A→B)= P(AUB) = (包含A和B的事务数 / 事务总数)×100%规则 A→B具有可信度C，表示C是包含A项集的同时也包含B项集，即条件概率P(B|A)，也可以表示为：confidence(A→B)＝ P(B|A) = (包含A和B的事务数 / 包含A的事务数)×100％,7.1 关联规则-概念-3,阈值：为了在事务数据库中找出有用的关联规则，需要确定两个阈值：最小支持度阈值min_sup和最小可信度阈值min_conf频繁项集：满足最小支持度min_sup的项集频繁项集中，任意子项集中各项出现的联合概率（即项集的支持频度sup(T)）都大于最小支持度min_sup关联规则（语义）：支持度和可信度均不小于给定最小支持度阈值和最小置信度阈值的规则，是有意义有价值的，即：A→B，若满足： S(A→B)>min_sup，且C(A→B)>min_conf,7.1 关联规则-概念-4,期望可信度：设事务集D中有e%的事务支持项集B，e%称为关联规则A→B的期望可信度（与A无关）；描述了在没有任何条件影响时，项集B在所有事务中出现的概率，即P(B)作用度：是可信度与期望可信度的比值；描述项集A的出现对项集B的出现有多大影响，即概率P(B|A)/P(B),7.1 关联规则-概念-小结,表：各参数的含义及计算公式,7.2 关联规则挖掘过程,可以把关联规则挖掘划分为以下两个子问题/子过程：找出所有的频繁项集项集的支持频度vs.最小支持度阈值可以从1到k递推查找k-频繁项集；是过程的核心步骤，关键技术，实现较困难由频繁项集产生关联规则，即找出满足最小支持度和最小可信度的关联规则关联规则的可信度vs.最小可信度阈值相对较容易,7.2 关联规则挖掘过程-简例,已知交易记录数据库D中有9条交易记录（事务）：T1：A，B，E T2：B，DT3：B，C T4：A，B，DT5：A，C T6：B，CT7：A，C T8：A，B，C，ET9：A，B，C设定最小支持度为20%，最小可信度为60%找到所有的频繁项集，有{A,B,C}、{A,B,E}及其全部子集；(还有哪些？)产生关联规则，举例有：A∧E→B （?， ? ） A→B （ ? ， ? ） B∧E→A （ ? ， ? ） A→C （ ? ， ? ） E→A∧B （ ? ， ? ） C→A （ ? ， ? ）,7.3 关联规则挖掘分类-1,（1）基于规则中处理的变量的类别布尔型关联规则：规则考虑的关联是项“在”或“不在”，所处理的值是离散的、种类化的如：computerfinancial_management_software [min_sup=2%,min_conf=60%]数值型关联规则：描述的是量化的项或属性之间的关联如（其中X表示顾客变量，量化属性age和income已经离散化）：age(X,“30…39”)∧income(X,“42K…48K”)→buys(X,“high_resolution_TV”),7.3 关联规则挖掘分类-2,（2）基于规则中数据的抽象层次单层关联规则：所有的变量的项或属性在同一细节层次如：buys(X, “computer”) → buys(X, “printer”)顾客X购买的商品不涉及不同抽象层次（“computer” 和“printer”在同一个抽象层）多层关联规则：变量涉及不同抽象层次的项或属性。

如：age(X,“30…39”) → buys(X, “laptop computer”)； age(X,“30…39”) → buys(X, “computer”) 顾客X购买的商品涉及不同抽象层次（“computer” 比“laptop computer”抽象层次更高）,7.3 关联规则挖掘分类-3,（3）基于规则中涉及到的数据的维数单维关联规则：关联规则只涉及数据的一个维度，处理单个维中属性间的关系如： coffee → sugar，只涉及用户购买的物品，buy属性或维度多维关联规则：关联规则涉及数据的多个维，处理多个维中属性之间的关系如：sex=“f” → occupation=“secretary”，涉及到两个维中字段的信息,7.4.1 Apriori算法概述-1,概述：最有影响的，挖掘布尔型关联规则的基本算法；根据有关频繁项集特性的先验（priori）知识而命名；采用层次顺序搜索的循环方法来产生频繁项集，其间利用Apriori性质以帮助有效缩小频繁项集的搜索空间Apriori性质：一个频繁项集的任一子集也应是频繁项集证明：非频繁项集的任意超集(母集)是非频繁项集如：项集{A}不是频繁项集，P(A)

执行连接Lk-1和Lk-1，其中Lk-1的元素是可连接，如果它们前（k-2）个项相同而且第（k-1）项不同（为简单计，设l1[k-1]