《数据仓库与数据挖掘》第8章(关联规则)

第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1第8章关联规则挖掘主要内容关联规则挖掘的基本概念关联规则挖掘的过程Apriori算法Apriori算法的变形频繁模式增长（FP－增长）算法其他关联规则挖掘算法关联规则价值衡量的方法关联规则挖掘的应用第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊28.1关联规则挖掘的基本概念1.购物篮分析－引发关联规则挖掘的例子问题：“什么商品组或集合顾客多半会在一次购物中同时购买？”购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。〖例〗购买计算机与购买财务管理软件的关联规则可表示为：computerfinancial_management_softwar[support=2%,confidence=60%]support为支持度，confidence为置信度。该规则表示：在所分析的全部事务中，有2％的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60％也购买财务管理软件。2.关联规则关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性。项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系。第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊3〖定义8－1〗令I={i1，i2，…,in}是项目集，D是全体事务的集合。事务T是I上的一个子集，集合TI，每个事务用唯一的标志TID来标识。关联规则是形如XY的蕴含式，其中XI，YI且XY=，X称为规则的条件，Y称为规则的结果。2.置信度和支持度〖定义8－2〗关联规则XY对事物集D的支持度（support，）定义为D中包含有事务X和Y的百分比。关联规则XY对事务集合D的置信度（confidence）定义为D中包含有X的事务数与同时包含Y的百分比。即：support(XY)＝(包含X和Y的事务数/事务总数)×100％confidence(XY)＝(包含X和Y的事务数/包含X的事务数)×100％〖定义8－3〗置信度和支持度均大于给定阈值（即最小置信度阈值和最小支持度阈值）。即：support(XY)＝min_supconfidence(XY)＝min_conf的关联规则称为强规则；否则称为弱规则。数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。强规则XY对应的项集（X∪Y）必定是频繁集。因此，可以把关联规则挖掘划分为以下两个子问题：（1）根据最小支持度找出事务集D中的所有频繁项集。――核心（2）根据频繁项集和最小置信度产生关联规则。――较易3.关联规则挖掘第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊4关联规则挖掘：给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和、最小支持度。〖例〗购买商品事务如下表所示，设最小支持度为50%,最小可信度为50%,则可得到以下关联规则：AC(50%,66.6%)CA(50%,100%)4.关联规则挖掘的分类（1）基于规则中处理的变量的类别基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联规则：如果规则考虑的关联是项“在”或“不在”，则关联规则是布尔型的。例如，由购物篮分析得出的关联规则。量化型关联规则：如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。例如，以下是量化型关联规则的一个例子（其中X为表示顾客的变量，量化属性age和income已经离散化）：age(X,“30…39”)∧income(“42K…48K”)buys(X,“high_resolution_TV”)量化型关联规则中也可以包含多种变量。例如：性别=“女”=职业=“秘书”，是布尔型关联规则；性别=“女”=avg（月收入）=2300，涉及的收入是数值类型，所以是一个量化型关联规则。（2）基于规则中数据的抽象层次交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊5基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。单层的关联规则：所有的变量都不涉及不同抽象层次的项或属性。例如：buys(X,“computer”)buys(X,“printer”)顾客X购买的商品不涉及不同抽象层次（“computer”和“printer”在同一个抽象层），因此是单层关联规则。多层的关联规则：变量涉及不同抽象层次的项或属性。例如：age(X,“30…39”)buys(X,“laptopcomputer”)age(X,“30…39”)buys(X,“computer”)顾客X购买的商品涉及不同抽象层次（“computer”在比“laptopcomputer”高的抽象层），因此是多层关联规则。（3）基于规则中涉及到的数据的维数基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。单维关联规则：处理单个维中属性间的关系，即在单维的关联规则中，只涉及到数据的一个维。例如：用户购买的物品：“咖啡=砂糖”，这条规则只涉及到用户的购买的物品。多维关联规则：处理多个维中属性之间的关系，即在多维的关联规则中，要处理的数据将会涉及多个维。例如：性别=“女”=职业=“秘书”，这条规则就涉及到两个维中字段的信息，是两个维上的一条关联规则。给出了关联规则的分类之后，就可以考虑某个具体的关联规则挖掘算法适用于哪一类规则的挖掘，某类关联规则又可以用哪些不同的方法进行处理。最简单的是单维、单层、布尔型的关联规则。Apriori算法是一种最有影响的挖掘布尔型关联规则频繁项集的算法。它的各种变形，用于提高算法的效率和可伸缩性。8.2关联规则挖掘的过程第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊61.术语关联规则挖掘即给定一组Item和记录集合，挖掘出Item间的相关性，使其置信度和支持度分别大于用户给定的最小置信度和最小支持度。〖定义8－4〗在关联规则挖掘算法中，把项目的集合称为项集（itemset），包含有k个项目的项集称为k-项集。包含项集的事务数称为项集的出现频率，简称为项集的频率或支持度计数。如果项集的出现频率大于或等于最小支持度s与D中事务总数的乘积，则称该项集满足最小支持度s。如果项集满足最小支持度，则称该项集为频繁项集（frequentitemset）。2．关联规则的挖掘过程关联规则的挖掘主要被分解为下面两步：第1步：找出所有的频繁项集，即找出支持度大于或等于给定的最小支持度阈值的所有项集。可以从1到k递归查找k-频繁项集。第2步：由频繁项集产生强关联规则，即找出满足最小支持度和最小置信度的关联规则。对给定的L，如果其非空子集AL，sup(L)为L的支持度，sup(A)为A的支持度，则产生形式为AL-A的规则。3.频繁项集的性质Apriori性质：频繁项集的所有非空子集都必须是频繁的。第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊7Apriori性质基于如下事实：根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即sup（I）min_sup。如果将项A添加到I，则结果项集（即I∪A）不可能比I更频繁出现。因此，I∪A也不是频繁的，即sup（I∪A）min_sup。频繁项集的Apriori性质用于压缩搜索空间（剪枝），以提高逐层产生频繁项集的效率。8.4关联规则挖掘的Apriori算法8.4.1Apriori算法的基本思想Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。它使用一种称作逐层搜索的迭代算法，k-项集用于探索（k+1）-项集。Apriori算法的基本思想是：首先，通过扫描数据集，产生一个大的候选数据项集,并计算每个候选数据项发生的次数，然后基于预先给定的最小支持度生成频繁1-项集的集合，该集合记作1L；然后基于1L和数据集中的数据，产生频繁2-项集2L；用同样的方法，直到生成频繁n-项集nL，其中已不再可能生成满足最小支持度的（N+1）－项集。最后，从大数据项集中导出规则。2.Apriori算法中的关键步骤Apriori算法中的关键步骤是由Lk-1找Lk，该步骤可分为两步：第1步（连接）：为找Lk，通过Lk-1与自己连接产生候选K-项第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊8集的集合。将该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集，记号li[j]表示li的第j项。执行连接Lk-1和Lk-1，其中Lk-1的元素是可连接，如果它们前（k-2）个项相同而且第（k-2）项不同（为简单计，设l1[k-1]l2[k-1]），即：l1[1]=l2[1]∧l1[2]=l2[2]∧……∧l1[k-2]=l2[k-2]∧l1[k-1]l2[k-1]则Lk-1的元素l1和l2是可连接的。连接l1和l2产生的结果的项集是l1[1]l1[2]……l1[k-1]l2[k-1]。第2步（剪枝）：Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，可以用以下办法使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。〖例〗Apriori算法的执行过程。TID项ID的列表T100T200I1，I2，I5I2，I4第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊9T300T400T500T600T700T800T900I2，I3I1，I2，I4I1，I3I2，I3I1，I3I1，I2，I3，I5I1，I2，I31.在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法简单地描述所有的事务，对每个项的出现次数计数。2.假定最小事务支持计数为2（即min_sup=2/9=22%）。可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。3.为发现频繁2-项集的集合L2，算法使用L1和L1的连接产生候选2-项集的集合C2。C2由C2L1个2-项集组成。4.下一步，扫描D中的事务，计算C2中每个候选项集的支持计数。5.确定频繁2-项集的集合L2，它由最小支持度的C2中的候选2-项集组成。6.类似地，产生候选3-项集的集合C3，并利用Apriori性质对C3中的项集进行剪枝，即删除其中不可能是频繁的项集。7.扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成。8.使用L3和L3的连接产生候选4-项集的集合C4，而所得到的项集利用Apriori性质被剪去（因为它的子集不是频繁的），得到C4=φ，至此算法终止，找出了所有的频繁项集。第8章关联规则挖掘┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊103.Apriori算法的描述算法：使用根据候选生成的逐层迭代找出频繁项集。其中kL是频繁K-项项集支持度{I1}{