数据挖掘与知识发现(讲稿5---关联规则挖掘技术)

┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1第5章关联规则挖掘技术关联规则概念是由Agrawal、Imielinsk和Swami等人于1993年提出的，用于挖掘顾客数据库中项集间的关联规则问题。其核心方法是基于频集理论的递推方法。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用商品货架设计、货存安排以及根据购买模式对用户进行分类。问题：“什么商品组或集合顾客多半会在一次购物中同时购买？”购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。〖例〗购买计算机与购买财务管理软件的关联规则可表示为：computerfinancial_management_softwar[support=2%,confidence=60%]support为支持度，confidence为置信度。该规则表示：在所分析的全部事务中，有2％的事务同时购买计算机和财务管理软件；在购买计算机的顾客中60％也购买财务管理软件。5.1关联规则的概念关联（Associations）分析的目的是为了挖掘隐藏在数据间的相互关系，即对于给定的一组项目和一个记录集，通过对记录集的分析，得出项目集中的项目之间的相关性。项目之间的相关性用关联规则来描述，关联规则反映了一组数据项之间的密切程度或关系。关联规则发现的主要对象是事务数据库，其中针对的应用是售货数据，也称货篮数据。如，超市前端收款机中就收集存储了大量的数据。一般情况下，一个事务（记录）由如下几部分组成：事务处理时间、顾客购买的物品、物品的数量及金额，┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊2以及顾客的标识号（如信用卡号）等。定义：设},,,{21mIIIR是一组物品集，W是一组事务集。W中的每个事务T是一组物品，RT。假设有一个物品集A，一个事务T，如果TA，则称事务T支持物品集A。关联规则的描述是如下形式的一种蕴含：BA或BA其中A、B是两组物品，且BATBTA,,。记)(AP--表示事务中出现物品集A的概率。一个关联规则的属性通常采用如下的四个参数描述：1）可信度（Confidence）设W中支持物品集A的事务中，有c%的事务同时也支持物品集B，则称c%为关联规则BA的可信度。简单的说，可信度就是指在出现了物品集A的事务中，物品集B也同时出现的概率有多大。计算公式为：)|(ABP。如，购买面包A的顾客中有70%的人购买了黄油B，则其可信度为70%。2）支持度（Support）设W中有s%的事务同时支持物品集A和B，则称s%为关联规则BA的支持度。支持度描述了A和B这两个物品集并集C在所有事务中出现的概率有多大。计算公式为：)(BAP。如，某天共有1000个顾客到商场购物，其中有100个顾客同时购买了面包和黄油，则关联规则的支持度为10%。3）期望可信度（Expectedconfidence）设W中有e%的事务支持物品集B，则称e%为关联规则BA的期望可信度。期望可信度描述了在没有任何条件影响时，物品集B在所有事务中出现的概率有多大。计算公式为：)(BP。如，某天共有1000个顾客到商场购物，其中有200个顾客购买了黄油，则上述的关联规则期望可信度为20%。4）作用度（Lift）作用度是可信度与期望可信度的比值。作用度描述物品集A的出现对物品集B的出现有多大影响。计算公式为：)(/)|(BPABP。如，上述例中的作用度为70%/20%=3.5。┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊3由此知，可信度是对关联规则的准确度的衡量；支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则越重要。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。作用度描述了物品集A对物品集B的影响力的大小。作用度越大，说明物品集B受物品集A的的影响越大。一般情况，有用的关联规则的作用度均是大于1的。5.2关联规则的分类（1）基于规则中处理的变量的类别基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联规则：如果规则考虑的关联是项“在”或“不在”，则关联规则是布尔型的。例如，由购物篮分析得出的关联规则。量化型关联规则：如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。例如，以下是量化型关联规则的一个例子（其中X为表示顾客的变量，量化属性age和income已经离散化）：age(X,“30…39”)∧income(“42K…48K”)buys(X,“high_resolution_TV”)量化型关联规则中也可以包含多种变量。例如：性别=“女”=职业=“秘书”，是布尔型关联规则；性别=“女”=avg（月收入）=2300，涉及的收入是数值类型，所以是一个量化型关联规则。（2）基于规则中数据的抽象层次基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。单层的关联规则：所有的变量都不涉及不同抽象层次的项或属性。例如：buys(X,“computer”)buys(X,“printer”)顾客X购买的商品不涉及不同抽象层次（“computer”和“printer”在同一个抽象层），因此是单层关联规则。┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊4多层的关联规则：变量涉及不同抽象层次的项或属性。例如：age(X,“30…39”)buys(X,“laptopcomputer便携电脑”)age(X,“30…39”)buys(X,“computer”)顾客X购买的商品涉及不同抽象层次（“computer”在比“laptopcomputer”高的抽象层），因此是多层关联规则。（3）基于规则中涉及到的数据的维数基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。单维关联规则：处理单个维中属性间的关系，即在单维的关联规则中，只涉及到数据的一个维。例如：用户购买的物品：“咖啡=砂糖”，这条规则只涉及到用户的购买的物品。多维关联规则：处理多个维中属性之间的关系，即在多维的关联规则中，要处理的数据将会涉及多个维。例如：性别=“女”=职业=“秘书”，这条规则就涉及到两个维中字段的信息，是两个维上的一条关联规则。给出了关联规则的分类之后，就可以考虑某个具体的关联规则挖掘算法适用于哪一类规则的挖掘，某类关联规则又可以用哪些不同的方法进行处理。最简单的是单维、单层、布尔型的关联规则。Apriori算法是一种最有影响的挖掘布尔型关联规则频繁项集的算法。它的各种变形，用于提高算法的效率和可伸缩性。5.3关联规则挖掘算法关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的最小支持度minsup和最小可信度minconf的关联规则。挖掘关联规则问题可以分解为以下两个子问题：①利用支持度，找出存在于事务数据库中的所有大物品集（常用物品集或频繁集）。如果物品集X的支持度support(X)≥用户给定的最小支持度minsup，则称X为大物品集（频繁集）。②利用可信度，通过大项集生成关联规则。对于每个大项集A，若┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊5BAB,，且confidenceconfBABmin))((，则构成关联规则)(BAB1）经典的Apriori挖掘算法在众多的关联规则挖掘中，Apriori算法是最基本也是最著名的一种。算法的核心思想是基于频集理论的一种递推方法，目的是从数据库中挖掘出那些支持度和信任度都不低于给定的最小支持度阀值和最小信任度阀值的关联规则。Apriori算法通常分为两步：①基于支持度，产生频繁项集；②基于可信度，产生强关联规则。其核心是由①生成的频繁项集。Apriori算法使用的是一种称作逐层搜索的迭代方法，k-项集用于探索)1(k-项集。其主要工作在于寻找大物品集，它利用了大物品集向下封闭性，即大物品集的子集必须是大物品集，它是宽度优先算法。（属单层、布尔型、一维）即Apriori算法的频繁项集的性质：频繁项集的所有非空子集都必须是频繁的。Apriori性质基于如下事实：根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即sup（I）min_sup。如果将项A添加到I，则结果项集（即I∪A）不可能比I更频繁出现。因此，I∪A也不是频繁的，即sup（I∪A）min_sup。频繁项集的Apriori性质用于压缩搜索空间（剪枝），以提高逐层产生频繁项集的效率。大物品集（频繁项集）产生的思想步骤为：先计算所有的1-项集（k-项集是指含有k个项的项集），记为1C。找出所有常用的1-项集，记为1L；根据常用1-项集确定候选2-项集的集合，记为2C。从2C找出所有的常用2-项集，记为2L；再由常用2-项集确定候选3-项集的集合，记为3C。从3C找出所有的常用3-项集，记为3L。如此下去，直到不再有候选项集。一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直截了当的（强关联规则满足最小支持度和最小置信度）。即对于用户给定的置信度，条件概率的计算可用下式的项集支持度计数表示：┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊6)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidence关联规则可产生如下：对于每个频繁项集l，产生l的所有非空子集；对于l的每个非空子集s，如果confscountportlcountportmin_)(_sup)(_sup则输出规则“)(sls”。其中，confmin_是最小置信度阈值。【示例1】对于事务数据库D，Apriori算法产生过程如下所示。取minsup=2由此得，频繁集}{ECBl。其规则的产生为：非空子集{BC}，{BE}，{CE}，{B}，{C}，{E}{B}∧{C}{E}confidece=2/2=100%{B}∧{E}{C}confidece=2/3=66.7%{C}∧{E}{B}confidece=2/2=100%{B}{C}∧{E}confidece=2/3=66.7%┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊7{C}{B}∧{E}confidece=2/3=66.7%{E}{B}∧{C}confidece=2/3=66.7%如果最小置信度的阈值为70%，则只有1、3规则可以输出，因为只有这些是产生的强规则。算法：使用根据候选生成的逐层迭代找出频繁项集。其中kL是频繁K-项集，kC是具有K个数据项的候选项集；D是整个事务集。输入：事务集D，最小支持度阈值min_sup。输出：D中的频繁项集L。方法：（1）1L={large1-itemsets};//初始产生频繁1－项集的集合（2）for(k=2,1kL;k++)do//由频繁k-1－项集产生频繁k－项集（3）begin（4）kC=apriori_gen(1kL);//调用函数apriori_gen，由1kL产生kC（5）foralltransactionstDdo（6）begin（7）tC=subset(kC,t);//t中所包含的候选（8）forallcandiatesctCdoc.count++;（9）end;（10）kL={ckC|c.countmin_sup};（11）end;（12）returnL