第六章-挖掘大型数据库中的关联规则

《数据挖掘》主讲：王名扬信息与计算机工程学院2引言—要挖掘知识的类型概念描述：特征化和比较；关联规则；分类/预测；聚类分析；其他的数据挖掘任务。第6章挖掘大型数据库中的关联规则引言关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。从大量商业事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析等。2引言如何从事务DB或关系DB的大量数据中挖掘出关联规则知识？什么样的关联规则才是最有意义的？如何才能使挖掘过程尽快发现有价值的关联规则知识？这是本章要讨论的内容。2第6章6.1关联规则挖掘6.2由事务数据库挖掘单维布尔关联规则6.3由事务数据库挖掘多层关联规则6.4由事务数据库和数据仓库挖掘多维关联规则7学习目的掌握关联规则挖掘算法--Apriori算法。理解多层关联规则挖掘及其方法；理解多维关联规则挖掘及其方法。6.1关联规则挖掘关联规则挖掘(Associationrulemining)：关联规则挖掘的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号组成。关联规则挖掘用以挖掘一次交易中，物品之间同时出现的规律的知识模式，以反映顾客的购买行为。更确切的说，关联规则是通过量化的数字来描述物品X的出现对物品Y的出现有多大的影响。以零售业为例，通过对销售数据的关联分析，体育用品商店可以发现隐含在数据中的规律：“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服”等等。关联规则挖掘购物篮分析购物篮分析是关联规则挖掘的最初形式。如，某商店经理可能更想了解如下的购物习惯：“顾客多半会在购物时同时购买什么商品组或集合？”为解答这个问题，可以在商店顾客事务零售数据库上进行购物篮分析。分析的结果可用于市场规划、广告策划和分类设计。45设商店中所有销售商品为一个集合，每个商品均为一个布尔变量，布尔变量用来表示该商品是否被(一个)顾客购买。则，每个购物篮（事务数据库）可以用一个布尔向量表示。分析该布尔向量，得到反映商品频繁关联或同时购买的购买模式。购物篮分析computer=financial_management_software[support=2%,confidence=60%]关联规则的支持度(support)2%表示：全部事务中，有2%的交易同时购买计算机和财务管理软件。关联规则的置信度(confidence)60%表示：购买计算机的顾客中，有60%也同时购买了财务管理软件。6购物篮分析例如，在购买计算机的同时购买财务管理软件，可用如下关联规则表示：1.关联规则的基本概念？关联规则挖掘的基本概念1）事务数据库：设I={i1，i2，…，im}是一个项目集合，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。示例：购物记录I是全部物品集合，如商场现有的所有商品；D是购物清单，如顾客的购物清单；D中的每个元组ti代表一次事务（商业行为），是一次购买物品的集合（I的一个子集）。基本概念2）支持度(support)：支持度是模式为真的任务相关的元组（或事务）所占的百分比。对于形如“”的关联规则，支持度定义为：其中，A、B是项目的集合。示例：假定任务相关数据由AllElectronics的计算机部的事务数组成，一个支持度为30%的关联规则：意味着在计算机部的所有顾客中，有30%同时购买了计算机（A）和软件（B）。BA元组总数的元组数和包含）支持度（BABA=),(),(softwareXbuyscomputerXbuys基本概念3）置信度(certainty)：每个发现的模式都有一个表示其有效性或值得信赖性的度量。对于形如“”的关联规则，其有效性度量为置信度，定义为：其中，A、B是项目的集合。示例：假定任务相关数据由AllElectronics的计算机部购买物品的事务数组成，一个置信度为85%的关联规则：意味着买计算机（A）的顾客中，有85%也同时购买了软件（B）。BA的元组数包含的元组数和包含）置信度（ABABA=),(),(softwareXbuyscomputerXbuys基本概念4）强关联规则：置信度表示规则的可信度；置信度小：规则无意义支持度表示模式在事务数据库中的出现频率；支持度小：规则使用面窄同时满足用户定义的最小置信度和最小支持度阈值的关联规则，称为强关联规则（strongassociationrule），并被认为是有趣的。2.关联规则的分类？（1）基于规则中处理的变量类别布尔型：离散的、可枚举的、种类化的如：性别=“男”=职业=“网络工程师”数值型：含有定量的数据项如，性别=“男”=收入=“3500”关联规则的分类：（2）基于规则中数据的抽象层次单层关联规则：所有的变量都不考虑层次如：性别=“男”=职业=“网络工程师”多层关联规则：考虑变量的不同层次性如，数码相机=三星手机，（数码相机是三星数码相机的较高层抽象）再如，数码相机=手机（数码相机、手机是三星数码相机和三星手机的较高层抽象）。关联规则的分类：多层关联规则又可以分为：同层关联规则：如果一个关联规则对应的项目是同一个粒度层次，那么它是同层关联规则如，数码相机=手机。层间关联规则：如果在不同的粒度层次上考虑问题，那么得到的是层间关联规则。如，数码相机=三星手机关联规则的分类：（3）基于规则中涉及的数据维数单维关联规则：只涉及一个属性（维），处理单个属性（维）中的一些关系如：啤酒=尿布，只涉及到用户购买的物品一个维；多维关联规则：处理多个属性（维）上的关系如，性别“女”=职业“秘书”，此规则涉及到两个属性（维）的关系。关联规则的分类：6.2由事务数据库挖掘单维布尔关联规则关联规则挖掘的两步过程：1）找出所有的频繁项集：这些项集出现的频繁性要满足最小支持度原则。2）由频繁项集产生强关联规则：满足最小支持度和最小置信度。常用方法：Apriori算法频繁项集项的集合称为项集（itemset），项的项集称为k-项集，如集合{computer,software}是一个2-项集。项集的频率：即包含项集的事务数，也称为项集的支持计数(support_count)。Min_sup:设定的支持率阈值如果项集的出现频率大于或等于min_sup与D中事务总数的乘积，就称该项集满足最小支持度min_sup。频繁项集：满足最小支持度的项集，频繁k-项集通常记做：Lk。基本概念频繁项集：频繁项集是频繁出现在数据集中的项集；有助于发现数据中蕴含的内在规律哪些产品经常被一起购买？---啤酒和尿布？买了PC之后接着都会买些什么？哪种DNA对这种新药敏感？能揭示数据集内在的、重要的特性。Apriori算法Apriori算法原理：任何一个频繁项集的子集必定是频繁项集；如，如果{A,B}是频繁项集，则{A}、{B}都是频繁项集。任何非频繁项集的超集都为非频繁项集如，如果{A}、{B}是非频繁项集，则{A,B}是非频繁项集Apriori算法算法的关键步骤：找出频繁项集：满足最小支持度的项目集；方法：使用从1到k的候选集逐层递归的产生频繁项集。由频繁项集产生关联规则。APRIORI算法过程Apriori算法利用逐层迭代来计算数据库中的频繁项集。第i次迭代计算出所有频繁i项集(包含i个元素的项集)。每一次迭代有两个步骤：产生候选集；计算和选择候选集。原理是：如果一个项集是频繁的，那么它的所有子集也是频繁的。在第一次迭代中，产生的候选集包含所有1-项集，并计算其支持度s，s大于阈值的1-项集被选为频繁1-项集。第二次迭代时，Apriori算法首先去除非频繁1-项集，在频繁1-项集的基础上产生候选二项集，继而结合设定的最小支持度阈值，产生频繁2-项集。如，以表6-1中的数据为例。假设smin=50%。6APRIORI算法过程在第一次迭代中，所有单项集都作为候选集，产生一个候选集列表；图5-1给出第一次迭代的结果在下一步中，计算每一项的支持度，然后在smin的基础上选择频繁项集。APRIORI算法过程图5-1Apriori算法第一次迭代的结果在挖掘2-项集时，因为2-项集的任何子集都是频繁项集，所以Apriori算法使用L1*L1来产生候选集。{*}运算通常定义为：Lk*Lk={X∪Y其中X,Y∈Lk,|X∪Y|=k+1}注:|X∪Y|=k+1，即X和Y合取容量为k+1因此，第二次迭代中的候选集C2由运算|L1|·|L1-1|/2所产生，其个数为：4·3/2=6。用该列表来扫描DB，计算每一个候选集的支持度，并与smin进行比较，产生2-项频繁集L2。图5-2给出了所有这些步骤和第二次迭代的结果。APRIORI算法过程APRIORI算法过程63_项集C3{ABC}{ACE}{BCE}3_项集{ABC}{ACE}{BCE}计数S(%)0020050频繁3_项集BCE计数S(%)250候选集C3运用L2*L2来产生，运算结果得到{A,B,C},{A,C,E},{B,C,E}，但只有{B,C,E}的所有子集是频繁项集，成为候选的3-项集。然后扫描DB，根据最小支持计数，挖掘出频繁3-项集，见图5-3所示:因为本例的L3无法产生候选的4-项集，所以算法停止迭代过程。图5-3Apriori算法第三次迭代的结果APRIORI算法过程该算法不仅计算所有频繁集的支持度，也计算那些没有被删除的非频繁候选集的支持度。所有非频繁但被算法计算支持度的候选项集的集合被称为负边界。因此，如果项集是非频繁的，但它的子集都是频繁的，那么它就在负边界之中。APRIORI算法过程36Apriori算法源代码算法：Apriori使用根据候选生成的逐层迭代找出频繁项集输入：事务数据库D；最小支持度阈值min_sup输出：D中的频繁项集L（1）L1={large1-itemsets};//所有1-项目频集（2）FOR（k=2;Lk-1;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候选集（4）FORalltransactionstDDOBEGIN（5）Ct=subset（Ck，t）;//Ct是所有t包含的候选集元素（6）FORallcandidatescCtDO（7）c.count++;（8）END（9）Lk={cCk|c.countminsup_count}（10）END（11）L=Lk;38示例：对于前面的例子，基于事务数据库D，在假定最小支持度阈值为50%的前提下，我们得到了频繁项集{2,3,5}。问，由该频繁项集可以产生哪些关联规则？分析：频繁项集L={2,3,5}的非空子集有{2,3},{2,5},{3,5},{2},{3},{5}。则由这些子集可以产生如下关联规则：由频繁项集产生关联规则%673/2,325)6(%673/2,523)5(%673/2,532)4(%1002/2,253)3(%673/2,352)2(%1002/2,532)1(============confidenceconfidenceconfidenceconfidenceconfidenceconfidence如果限定最小置信度阈值为80%，则只有规则（1），（3）为强关联规则。Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。Apriori算法有两个致命的性能瓶颈:–1．多次扫描事务数据库，需要很大的I/O负载•对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。–2．可能产生庞大的侯选集•由Lk-1产生k-侯选集Ck是指数增长的。Apriori算法的性能瓶颈如何提高Apriori算法的效率一些算法虽