第8章频繁模式挖掘

2019/12/191五邑大学计算机学院何国辉数据仓库与数据挖掘DataWarehouseandDataMining2019/12/192数据仓库与数据挖掘DataWarehouseandDataMining第八章频繁模式挖掘2019/12/193频繁模式(frequentpattern)是指在数据集中频繁出现的模式。现实生活中存在多种类型的频繁模式，包括频繁项集、频繁子序列（又称序列模式）和频繁子结构。8.0基本概念2019/12/194几个概念。频繁项集一般是指频繁地在事务数据集中一起出现的商品的集合，如小卖部中被许多顾客频繁地一起购买的牛奶和面包。频繁子序列，如顾客倾向于先购买便携机，再购买数码相机，然后再购买内存卡这样的模式就是一个（频繁）序列模式。8.0基本概念（续）2019/12/195频繁子结构是指从图集合中挖掘频繁子图模式。子结构可能涉及不同的结构形式（例如，图、树或格），可以与项集或子序列结合在一起。如果一个子结构频繁地出现，则称它为（频繁）子结构模式。8.0基本概念（续）2019/12/1968.0基本概念（续）频繁项集挖掘是频繁模式挖掘的基础。2019/12/197关联规则(AssociationRuleMining)挖掘是数据挖掘中最活跃的研究方法之一。关联规则挖掘的目的：找出数据库中不同数据项集之间隐藏的关联关系。8.1频繁项集和关联规则2019/12/198最早是由R.Agrawal等人在1993年提出的。其目的是为了发现超市交易数据库中不同商品之间的关联关系。一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。经典的关联规则挖掘算法：Apriori算法和FP-growth算法。8.1频繁项集和关联规则（续）2019/12/1991.购物篮分析－引发关联规则挖掘的例子问题：“什么商品组或集合顾客多半会在一次购物中同时购买？”购物篮分析：设全域为商店出售的商品的集合（即项目全集），一次购物购买（即事务）的商品为项目全集的子集，若每种商品用一个布尔变量表示该商品的有无，则每个购物篮可用一个布尔向量表示。通过对布尔向量的分析，得到反映商品频繁关联或同时购买的购买模式。这些模式可用关联规则描述。8.1频繁项集合关联规则（续）2019/12/19108.1.1问题描述现实：商店有很多商品，例如“面包”、“牛奶”、“啤酒”等。顾客将把他们需要的商品放入购物篮中。研究的目的：发现顾客通常会同时购买哪些商品。通过上述研究可以帮助零售商合理地摆放商品，引导销售。2019/12/19118.1.1问题描述（续）举例：某一个时间段内顾客购物的记录形成一个交易数据库，每一条记录代表一次交易，包含一个交易标识符（TID）和本次交易所购买的商品。一个简单交易数据库实例数据库D：TID项001A、C、D002B、C、E003A、B、C、E004B、E2019/12/19128.1.1问题描述（续）几个基本概念：数据项：设I={i1，i2，…,im}是常数的集合，其中m是任意有限的正整数常量，每个常数ik（k=1,2，...，m）称为一个数据项。项集：由I中的数据项组成的集合，即XI。K-项集：一个大小为K的项集（包含有K项，如{A、B}为2-项集，{A、C、D}为3-项集）。一个交易T：是由在I中的数据项所构成的集合，即TI。2019/12/19138.1.1问题描述（续）【定义1】以商场交易数据库为例，形式化地描述关联规则：设I={i1，i2，…,im}是项的集合，表示各种商品的集合；D={t1，t2，…,tn}为交易集，表示每笔交易的集合（是全体事务的集合）。其中每一个事务T都是项的集合，且有TI。每个事务都有一个相关的唯一标识符和它对应，也就是事务标识符或TID。2019/12/19148.1.1问题描述（续）设X为一个由多个项目构成的集合，称为项集，如001中的{A、C、D}，当且仅当XT时我们说事务T包含X。2019/12/19158.1.1问题描述（续）项集X在在事务数据库DB中出现的次数占总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。2019/12/19168.1.1问题描述（续）关联规则关联规则是形如XY的蕴含式，其中XI，YI且XY=，则X称为规则的条件，Y称为规则的结果。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%。支持度是指项集X和Y在数据库D中同时出现的概率。2019/12/19178.1.1问题描述（续）【定义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％2019/12/19188.1.1问题描述（续）【例8.1】某顾客购物的交易数据库总交易数为5。2019/12/19198.1.1问题描述（续）【例8.1】相关的支持度和置信度。support(XY)＝(包含X和Y的事务数/事务总数)×100％confidence(XY)＝(包含X和Y的事务数/包含X的事务数)×100％2019/12/19208.1.1问题描述（续）频度：由于分母相同，有时仅用分子表示，即项集在数据库中出现的次数来代表支持度。通过支持度和置信度作为评分函数，给出了对模式进行评价的一个量化标准。2019/12/19218.1.1问题描述（续）进行关联规则挖掘时，要求用户给出两个阈值：最小支持度（频度）s；最小置信度c。表示：support(XY)＝min_supconfidence(XY)＝min_conf的关联规则称为强规则；否则称为弱规则。数据挖掘主要就是对强规则的挖掘。通过设置最小支持度和最小置信度可以了解某些数据之间的关联程度。2019/12/19228.1.1问题描述（续）关联规则挖掘就是要从大量的潜在的规则库中寻找出满足支持度（频度）和置信度阈值的所有规则。2019/12/19238.1.1问题描述（续）举例：一个食品连锁店保留着每周的事务记录，其中每一条事务表示在一项收款机业务中卖出的项目。连锁店的管理会收到一个事务汇总报告，报告表明了每种项目的销售量是多少。此外，他们要定期了解哪些项目经常被顾客一起购买。他们发现顾客购买了花生酱后，100%地会购买面包。而且，顾客购买了花生酱后，有33%也购买果冻。不过，所有事务中大约只有50%包含花生酱。2019/12/19248.1.1问题描述（续）被用于在其中寻找关联规则的数据库可以看作为一个元组集合，每个元组包含一组项目。一个元组可能是：{花生酱、面包、果冻}包含三个项目：花生酱、面包、果冻每个项目表示购买的一种产品一个元组是一次购买的产品列表2019/12/19258.1.1问题描述（续）样本数据库演示关联规则的样本数据事务项目t1面包、果冻、花生酱t2面包、花生酱t3面包、牛奶、花生酱t4啤酒、面包t5啤酒、牛奶2019/12/19268.1.1问题描述（续）找出的所有项目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生酱0果冻20啤酒、果冻、牛奶0牛奶40啤酒、果冻、花生酱0花生酱60啤酒、牛奶、花生酱0啤酒、面包20面包、果冻、牛奶0啤酒、果冻0面包、果冻、花生酱20啤酒、牛奶20面包、牛奶、花生酱20啤酒、花生酱0果冻、牛奶、花生酱0面包、果冻、20啤酒、面包、果冻、牛奶0面包、果冻20啤酒、面包、果冻、花生酱0面包、花生酱60啤酒、面包、牛奶、花生酱0果冻、牛奶0啤酒、果冻、牛奶、花生酱0果冻、花生酱20面包、果冻、牛奶、花生酱0牛奶、花生酱20啤酒、面包、果冻、牛奶、花生酱0啤酒、面包、果冻02019/12/19278.1.1问题描述（续）问题发现：项目的个数成指数增长：从5个项目的集合得到31个项目集合（忽略空集）关联规则挖掘过程：第一步：寻找频繁项集。根据定义，这些项集出现的频度不小于预先定义的最小额度。---较难第二步：由频繁项集产生关联规则。根据定义，这些规则必须满足最小支持度和最小置信度。--较易2019/12/19288.1.2关联规则分类购物篮分析只是关联规则挖掘的一种形式。根据不同的分类标准，关联规则有多种分类方法：根据规则中所处理的数据类型分类根据规则中涉及的数据维数分类根据规则中数据的抽象层次分类其它2019/12/19291.根据规则中所处理的数据类型分类根据规则中所处理的数据类型，可以分为：布尔关联规则，也称为二值关联规则，处理的数据都是离散的。如：尿布啤酒。量化关联规则：在关联规则中加入数量信息得到的规则。如：职业=“学生”收入=“0...1000”。数值类型2019/12/19302.根据规则中涉及的数据维数分类根据规则中涉及的数据维数，可以分为：单维关联规则，只涉及数据表的一个字段。如：尿布啤酒。多维关联规则：涉及数据表的多个字段。如：性别=“女”职业=“护士”，是二维关联规则；又如：年龄=“20...30”∧职业=“学生”购买=“电脑”，是三维关联规则。2019/12/19313.根据规则中数据的抽象层次分类根据规则中数据的抽象层次，可以分为：单层关联规则，所有的变量都是细节数据，没有层次之分，如：IBM台式机HP打印机。多层关联规则：发生关联的数据可能位于同一层次，也可能位于不同的层次。如：台式机HP打印机。2019/12/19324.其它可以对关联规则施加语义约束，以便限制规则左部或者右部必须包含某些字段。后续章节将着重介绍布尔关联规则挖掘的两类具有代表性的算法。2019/12/19338.1.3关联规则挖掘的经典算法AprioriR.Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，给出了形式化定义和算法AIS，但该算法影响不大。R.Agrawal等人又于1994年提出了著名的Apriori算法。2019/12/19348.1.3关联规则挖掘的经典算法Apriori（续）Apriori算法是一种最有影响的挖掘布尔关联规则大（频繁）项目集的算法。它使用一种称作逐层搜索的迭代算法，通过k-项集用于探索（k+1）-项集。已经为大部分商业产品所使用。2019/12/19351.Apriori算法描述关联规则挖掘过程：第一步：寻找频繁项集。根据定义，这些项集出现的频度不小于预先定义的最小额度。---较难第二步：由频繁项集产生关联规则。根据定义，这些规则必须满足最小支持度和最小置信度。--较易找出满足定义的大项目集从大项目集（频繁项目集）生成关联规则2019/12/19361.Apriori算法描述（续）上述两步工作中第二步比较容易。目前主要研究重点：如何快速地找出所有频繁项集。--核心2019/12/1937（1）寻找频繁项集找出大项目集的算法可以很简单，但代价很高。简单的方法是：对出现在事务中的所有项目集进行计数。给定一个大小为m的项目集合，共有2m个子集，去掉空集，则潜在的大项目集数为2m-1。随着项目数的增多，潜在的大项目集数成爆炸性增长。（当m=5，为31个；当m=30，变成1073741823个）解决问题的难点：如何高效确定所有大项目集。大部分关联规则算法都利用巧妙的方法来减少要计数的项目集。2019/12/1938（1）寻找频繁项集（续）【公理1】：如果一个项集S是频繁的（项集S的出现频度大于最小频度），那么S的任意非空子集也是频繁的。反之，如果一个项集S的某个非空子集不是频繁的，则这个项集也不可能是频繁的。举例：如果