第8章-频繁模式挖掘课件

五邑大学计算机学院五邑大学计算机学院何国辉何国辉数据数据数据数据仓库与数据挖掘仓库与数据挖掘仓库与数据挖掘仓库与数据挖掘 Data Data Warehouse and Data MiningWarehouse and Data Mining7/14/20241数据数据仓库与数据挖掘仓库与数据挖掘 Data Warehouse and Data Mining第第八八章章 频繁模式挖掘频繁模式挖掘7/14/20242v频频繁繁模模式式(frequent pattern)是是指指在在数数据据集集中中频频繁繁出出现的模式。现的模式。v现现实实生生活活中中存存在在多多种种类类型型的的频频繁繁模模式式，包包括括频频繁繁项项集集、频繁子序列频繁子序列（又称序列模式）和（又称序列模式）和频繁子结构频繁子结构。8.0 基本概念基本概念7/14/20243v几个概念。几个概念。频频繁繁项项集集一一般般是是指指频频繁繁地地在在事事务务数数据据集集中中一一起起出出现现的的商商品品的的集集合合，如如小小卖卖部部中中被被许许多多顾顾客客频频繁繁地地一一起起购买的牛奶和面包。购买的牛奶和面包。频频繁繁子子序序列列，如如顾顾客客倾倾向向于于先先购购买买便便携携机机，再再购购买买数数码码相相机机，然然后后再再购购买买内内存存卡卡这这样样的的模模式式就就是是一一个个（频繁）序列模式。（频繁）序列模式。8.0 基本概念（续）基本概念（续）7/14/20244频频繁繁子子结结构构是是指指从从图图集集合合中中挖挖掘掘频频繁繁子子图图模模式式。子子结结构构可可能能涉涉及及不不同同的的结结构构形形式式（例例如如，图图、树树或或格格），可可以以与与项项集集或或子子序序列列结结合合在在一一起起。如如果果一一个个子子结结构频繁地出现，则称它为（频繁）子结构模式。构频繁地出现，则称它为（频繁）子结构模式。8.0 基本概念（续）基本概念（续）7/14/202458.0 基本概念（续）基本概念（续）v频繁项集挖掘是频繁模式挖掘的基础。频繁项集挖掘是频繁模式挖掘的基础。7/14/20246v关关联联规规则则(Association Rule Mining)挖挖掘掘是是数数据据挖挖掘掘中最活跃的研究方法之一中最活跃的研究方法之一。v关关联联规规则则挖挖掘掘的的目目的的：找找出出数数据据库库中中不不同同数数据据项项集集之间隐藏的关联关系。之间隐藏的关联关系。8.1 频繁项集和关联规则频繁项集和关联规则7/14/20247v最早是由最早是由R.Agrawal等人等人在在1993年年提出的提出的。v其其目目的的是是为为了了发发现现超超市市交交易易数数据据库库中中不不同同商商品品之之间间的关联关系。的关联关系。v一一个个典典型型的的关关联联规规则则的的例例子子是是：70%购购买买了了牛牛奶奶的的顾客将倾向于同时购买面包。顾客将倾向于同时购买面包。v经经典典的的关关联联规规则则挖挖掘掘算算法法：Apriori算算法法和和FP-growth算法算法。8.1 频繁项集和关联规则（续）频繁项集和关联规则（续）7/14/202481.1.购物篮分析引发关联规则挖掘的例子购物篮分析引发关联规则挖掘的例子 v问问题题：“什什么么商商品品组组或或集集合合顾顾客客多多半半会会在在一一次次购购物物中同时购买？中同时购买？”v购购物物篮篮分分析析：设设全全域域为为商商店店出出售售的的商商品品的的集集合合（即即项项目目全全集集），一一次次购购物物购购买买（即即事事务务）的的商商品品为为项项目目全全集集的的子子集集，若若每每种种商商品品用用一一个个布布尔尔变变量量表表示示该该商商品品的的有有无无，则则每每个个购购物物篮篮可可用用一一个个布布尔尔向向量量表表示示。通通过过对对布布尔尔向向量量的的分分析析，得得到到反反映映商商品品频频繁繁关关联联或或同时购买的购买模式同时购买的购买模式。这些模式可用关联规则描述。这些模式可用关联规则描述。8.1 频繁项集合关联规则（续）频繁项集合关联规则（续）7/14/202498.1.1 问题描述问题描述v现现实实：商商店店有有很很多多商商品品，例例如如“面面包包”、“牛牛奶奶”、“啤啤酒酒”等等。顾顾客客将将把把他他们们需需要要的的商商品品放放入入购购物物篮篮中。中。v研研究究的的目目的的：发发现现顾顾客客通通常常会会同同时时购购买买哪哪些些商商品品。通通过过上上述述研研究究可可以以帮帮助助零零售售商商合合理理地地摆摆放放商商品品，引引导销售。导销售。7/14/2024108.1.1 问题描述（续）问题描述（续）v举举例例：某某一一个个时时间间段段内内顾顾客客购购物物的的记记录录形形成成一一个个交交易易数数据据库库，每每一一条条记记录录代代表表一一次次交交易易，包包含含一一个个交交易标识符（易标识符（TID）和本次交易所购买的商品。）和本次交易所购买的商品。一个简单一个简单交易交易数据库数据库实例实例数据库D：TID项001A、C、D002B、C、E003A、B、C、E004B、E7/14/2024118.1.1 问题描述（续）问题描述（续）v几个基本概念：几个基本概念：数数据据项项：设设I=iI=i1 1，i i2 2，,i,im m 是是常常数数的的集集合合，其其中中m m是是任任意意有有限限的的正正整整数数常常量量，每每个个常常数数i ik k（k=1,2k=1,2，.，m m）称为一个数据项。）称为一个数据项。项集：项集：由由I I中的数据项组成的集合，即中的数据项组成的集合，即X X I I。K-K-项项集集：一一个个大大小小为为K K的的项项集集（包包含含有有K K项项，如如AA、BB为为2-2-项集，项集，AA、C C、DD为为3-3-项集）。项集）。一一个个交交易易T：是是由由在在I I中中的的数数据据项项所所构构成成的的集集合合，即即T I I。7/14/2024128.1.1 问题描述（续）问题描述（续）v【定定义义1 1】以以商商场场交交易易数数据据库库为为例例，形形式式化化地地描描述述关联规则关联规则：设设I=i1，i2，,im是是项项的的集集合合，表表示示各各种种商商品品的的集集合合；D=t1，t2，,tn为为交交易易集集，表表示示每每笔笔交交易易的的集集合合（是是全全体体事事务务的的集集合合）。其其中中每每一一个个事事务务T都都是是项项的的集集合合，且且有有T I。每每个个事事务务都都有有一一个个相相关关的的唯唯一一标标识识符符和和它它对对应应，也也就就是是事事务务标标识识符符或或TID。7/14/2024138.1.1 问题描述（续）问题描述（续）设设X为为一一个个由由多多个个项项目目构构成成的的集集合合，称称为为项项集集，如如001中中的的A、C、D，当当且且仅仅当当X T时时我我们们说说事事务务T包含包含X。7/14/2024148.1.1 问题描述（续）问题描述（续）项项集集X在在在在事事务务数数据据库库DB中中出出现现的的次次数数占占总总事事务务的的百分比叫做项集的百分比叫做项集的支持度支持度。如如果果项项集集的的支支持持度度超超过过用用户户给给定定的的最最小小支支持持度度阈阈值值，就称该项集是就称该项集是频繁项集频繁项集（或大项集）。（或大项集）。7/14/2024158.1.1 问题描述（续）问题描述（续）v关联规则关联规则关联规则是形如关联规则是形如X XY Y的蕴含式，其中的蕴含式，其中X X I I，Y Y I I且且X X Y=Y=，则，则X X称为规则的条件，称为规则的条件，Y Y称为规则的结果。称为规则的结果。如果事务数据库如果事务数据库D D中有中有s%s%的事务包含的事务包含X X Y Y，则称关，则称关联规则联规则X XY Y的支持度为的支持度为s%s%。支持度支持度是是指项集指项集X X和和Y Y在数据库在数据库D D中同时出现的中同时出现的概率概率。7/14/2024168.1.1 问题描述（续）问题描述（续）v【定定义义2 2】关关联联规规则则 X XY Y对对事事务务集集D D的的支支持持度度（supportsupport）定定义义为为D D中中包包含含有有事事务务X X和和Y Y的的百百分分比比。关关联联规规则则X XY Y对对事事务务集集合合D D的的置置信信度度（confidenceconfidence）定定义义为为D D中中包包含含有有X X的的事事务务数数与与同同时时包包含含Y Y的的百百分分比比。即：即：support(Xsupport(XY)Y)(包含包含X X和和Y Y的事务数的事务数/事务总数事务总数)100100confidence(Xconfidence(XY)Y)(包包含含X X和和Y Y的的事事务务数数/包包含含X X的的事事务务数数)1001007/14/2024178.1.1 问题描述（续）问题描述（续）v【例【例8.18.1】某顾客购物的交易数据库总交易数为某顾客购物的交易数据库总交易数为5 5。7/14/2024188.1.1 问题描述（续）问题描述（续）v【例【例8.18.1】相关的支持度和置信度。相关的支持度和置信度。support(Xsupport(XY)Y)(包含包含X X和和Y Y的事务数的事务数/事务总数事务总数)100100confidence(Xconfidence(XY)Y)(包含包含X X和和Y Y的事务数的事务数/包含包含X X的事务数的事务数)1001007/14/2024198.1.1 问题描述（续）问题描述（续）v频频度度：由由于于分分母母相相同同，有有时时仅仅用用分分子子表表示示，即即项项集集在数据库中出现的次数来代表支持度。在数据库中出现的次数来代表支持度。v通通过过支支持持度度和和置置信信度度作作为为评评分分函函数数，给给出出了了对模式进行评价的一个量化标准。对模式进行评价的一个量化标准。7/14/2024208.1.1 问题描述（续）问题描述（续）v进行关联规则挖掘时，要求用户给出进行关联规则挖掘时，要求用户给出两个阈值：两个阈值：最小支持度（频度）最小支持度（频度）s s；最小置信度最小置信度c c。v表示：表示：support(Xsupport(XY)Y)min_sup min_supconfidence(Xconfidence(XY)Y)min_conf min_conf的关联规则称为的关联规则称为强规则强规则；否则称为；否则称为弱规则弱规则。v数数据据挖挖掘掘主主要要就就是是对对强强规规则则的的挖挖掘掘。通通过过设设置置最最小小支支持持度度和和最最小小置置信信度度可可以以了了解解某某些些数数据据之之间间的的关关联联程度。程度。7/14/2024218.1.1 问题描述（续）问题描述（续）v关关联联规规则则挖挖掘掘就就是是要要从从大大量量的的潜潜在在的的规规则则库库中中寻寻找找出出满满足足支支持持度度（频频度度）和和置置信信度度阈阈值值的的所有规则所有规则。7/14/2024228.1.1 问题描述（续）问题描述（续）v举举例例：一一个个食食品品连连锁锁店店保保留留着着每每周周的的事事务务记记录录，其其中中每每一一条条事事务务表表示示在在一一项项收收款款机机业业务务中中卖卖出出的的项项目目。连连锁锁店店的的管管理理会会收收到到一一个个事事务务汇汇总总报报告告，报报告告表表明明了了每每种种项项目目的的销销售售量量是是多多少少。此此外外，他他们们要要定定期期了了解解哪哪些些项项目目经经常常被被顾顾客客一一起起购购买买。他他们们发发现现顾顾客客购购买买了了花花生生酱酱后后，100%100%地地会会购购买买面面包包。而而且且，顾顾客客购购买买了了花花生生酱酱后后，有有33%33%也也购购买买果果冻冻。不不过过，所所有有事事务中大约只有务中大约只有50%50%包含花生酱。包含花生酱。7/14/2024238.1.1 问题描述（续）问题描述（续）v被被用用于于在在其其中中寻寻找找关关联联规规则则的的数数据据库库可可以以看看作作为为一一个个元元组组集集合合，每每个个元元组组包包含含一一组组项项目目。一一个个元元组组可可能是：能是：花生酱、面包、果冻花生酱、面包、果冻 包含三个项目：花生酱、面包、果冻包含三个项目：花生酱、面包、果冻包含三个项目：花生酱、面包、果冻包含三个项目：花生酱、面包、果冻每个项目表示购买的一种产品每个项目表示购买的一种产品每个项目表示购买的一种产品每个项目表示购买的一种产品一个元组是一次购买的产品列表一个元组是一次购买的产品列表一个元组是一次购买的产品列表一个元组是一次购买的产品列表7/14/2024248.1.1 问题描述（续）问题描述（续）vv样本数据库样本数据库样本数据库样本数据库演示关联规则的样本数据演示关联规则的样本数据事务事务项目项目t1面包、果冻、花生酱面包、果冻、花生酱t2面包、花生酱面包、花生酱t3面包、牛奶、花生酱面包、牛奶、花生酱t4啤酒、面包啤酒、面包t5啤酒、牛奶啤酒、牛奶7/14/2024258.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啤酒、面包、果冻啤酒、面包、果冻07/14/2024268.1.1 问题描述（续）问题描述（续）v问问题题发发现现：项项项项目目目目的的的的个个个个数数数数成成成成指指指指数数数数增增增增长长长长：从从从从5 5个个个个项项项项目目目目的的的的集合得到集合得到集合得到集合得到3131个项目集合（个项目集合（个项目集合（个项目集合（忽略空集忽略空集忽略空集忽略空集）vv关联规则挖掘过程：关联规则挖掘过程：关联规则挖掘过程：关联规则挖掘过程：第第第第一一一一步步步步：寻寻寻寻找找找找频频频频繁繁繁繁项项项项集集集集。根根根根据据据据定定定定义义义义，这这这这些些些些项项项项集集集集出出出出现现现现的频度不小于预先定义的最小额度。的频度不小于预先定义的最小额度。的频度不小于预先定义的最小额度。的频度不小于预先定义的最小额度。-较难较难较难较难第第第第二二二二步步步步：由由由由频频频频繁繁繁繁项项项项集集集集产产产产生生生生关关关关联联联联规规规规则则则则。根根根根据据据据定定定定义义义义，这这这这些规则必须满足最小支持度和最小置信度。些规则必须满足最小支持度和最小置信度。些规则必须满足最小支持度和最小置信度。些规则必须满足最小支持度和最小置信度。-较易较易较易较易7/14/2024278.1.2 关联规则分类关联规则分类v购物篮分析只是关联规则挖掘的一种形式。购物篮分析只是关联规则挖掘的一种形式。v根据不同的分类标准，关联规则有多种分类方法：根据不同的分类标准，关联规则有多种分类方法：根据规则中所处理的数据类型分类根据规则中所处理的数据类型分类根据规则中涉及的数据维数分类根据规则中涉及的数据维数分类根据规则中数据的抽象层次分类根据规则中数据的抽象层次分类其它其它7/14/2024281.根据规则中所处理的数据类型分类根据规则中所处理的数据类型分类v根据规则中所处理的数据类型，可以分为：根据规则中所处理的数据类型，可以分为：布布尔尔关关联联规规则则，也也称称为为二二值值关关联联规规则则，处处理理的的数数据据都是离散的。如：尿布都是离散的。如：尿布啤酒。啤酒。量量化化关关联联规规则则：在在关关联联规规则则中中加加入入数数量量信信息息得得到到的的规则。如：职业规则。如：职业=“学生学生”收入收入=“0.10000.1000”。数值类型数值类型7/14/2024292.根据规则中涉及的数据维数分类根据规则中涉及的数据维数分类v根据规则中涉及的数据维数，可以分为：根据规则中涉及的数据维数，可以分为：单单维维关关联联规规则则，只只涉涉及及数数据据表表的的一一个个字字段段。如如：尿尿布布啤酒。啤酒。多多维维关关联联规规则则：涉涉及及数数据据表表的的多多个个字字段段。如如：性性别别=“女女”职职业业=“护护士士”，是是二二维维关关联联规规则则；又又如如：年年龄龄=“20.30”职职业业=“=“学学生生”购购买买=“电电脑脑”，是三维关联规则。是三维关联规则。7/14/2024303.根据规则中数据的抽象层次分类根据规则中数据的抽象层次分类v根据规则中数据的抽象层次，可以分为：根据规则中数据的抽象层次，可以分为：单单层层关关联联规规则则，所所有有的的变变量量都都是是细细节节数数据据，没没有有层层次之分，如：次之分，如：IBM台式机台式机HPHP打印机。打印机。多多层层关关联联规规则则：发发生生关关联联的的数数据据可可能能位位于于同同一一层层次次，也可能位于不同的层次。如：台式机也可能位于不同的层次。如：台式机HPHP打印机。打印机。7/14/2024314.其它其它v可可以以对对关关联联规规则则施施加加语语义义约约束束，以以便便限限制制规规则则左左部部或者右部必须包含某些字段。或者右部必须包含某些字段。v后后续续章章节节将将着着重重介介绍绍布布尔尔关关联联规规则则挖挖掘掘的的两两类具有代表性的算法。类具有代表性的算法。7/14/2024328.1.3 关联规则挖掘的经典算法关联规则挖掘的经典算法ApriorivR.Agrawal等等人人于于1993年年首首先先提提出出了了挖挖掘掘顾顾客客交交易易数数据据库库中中项项集集间间的的关关联联规规则则问问题题，给给出出了了形形式式化化定定义和算法义和算法AIS，但该算法影响不大但该算法影响不大。vR.Agrawal等等人人又又于于1994年年提提出出了了著著名名的的Apriori算算法法。7/14/2024338.1.3 关联规则挖掘的经典算法关联规则挖掘的经典算法Apriori（续）（续）vAprioriApriori算算法法是是一一种种最最有有影影响响的的挖挖掘掘布布尔尔关关联联规规则则大大（频频繁繁）项项目目集集的的算算法法。它它使使用用一一种种称称作作逐逐层层搜搜索索的的迭迭代代算算法法，通通过过k-k-项项集集用用于于探探索索（k+1k+1）-项项集集。已经为大部分商业产品所使用。已经为大部分商业产品所使用。7/14/2024341.Apriori算法描述算法描述v关联规则挖掘过程：关联规则挖掘过程：第第一一步步：寻寻找找频频繁繁项项集集。根根据据定定义义，这这些些项项集集出出现现的频度不小于预先定义的最小额度。的频度不小于预先定义的最小额度。-较难较难第第二二步步：由由频频繁繁项项集集产产生生关关联联规规则则。根根据据定定义义，这这些规则必须满足最小支持度和最小置信度。些规则必须满足最小支持度和最小置信度。-较易较易找出满足定义的大项目集找出满足定义的大项目集从大项目集（频繁项目集）生成关联规则从大项目集（频繁项目集）生成关联规则7/14/2024351.Apriori算法描述（续）算法描述（续）v上述两步工作中第二步比较容易。上述两步工作中第二步比较容易。v目目前前主主要要研研究究重重点点：如如何何快快速速地地找找出出所所有有频频繁项集。繁项集。-核心核心7/14/202436（1）寻找频繁项集寻找频繁项集v找出大项目集的算法可以很简单，但代价很高。找出大项目集的算法可以很简单，但代价很高。v简简单单的的方方法法是是：对对出出现现在在事事务务中中的的所所有有项项目目集集进进行行计数。计数。v给给定定一一个个大大小小为为m m的的项项目目集集合合，共共有有2 2m m个个子子集集，去去掉掉空空集集，则则潜潜在在的的大大项项目目集集数数为为2 2m m -1 1。随随着着项项目目数数的的增增多多，潜潜在在的的大大项项目目集集数数成成爆爆炸炸性性增增长长。（当当m=5m=5，为，为3131个；当个；当m=30m=30，变成，变成10737418231073741823个）个）v解决问题的难点：解决问题的难点：如何高效确定所有大项目集。如何高效确定所有大项目集。大部分关联规则算法都利用巧妙的方法来减少大部分关联规则算法都利用巧妙的方法来减少大部分关联规则算法都利用巧妙的方法来减少大部分关联规则算法都利用巧妙的方法来减少要计数的项目集。要计数的项目集。要计数的项目集。要计数的项目集。7/14/202437（1）寻找频繁项集（续）寻找频繁项集（续）v【公公理理1】：如如果果一一个个项项集集S是是频频繁繁的的（项项集集S的的出出现现频频度度大大于于最最小小频频度度），那那么么S的的任任意意非非空空子子集集也也是是频频繁繁的的。反反之之，如如果果一一个个项项集集S的的某某个个非非空空子子集集不是频繁的，则这个项集也不可能是频繁的。不是频繁的，则这个项集也不可能是频繁的。v举举例例：如如果果一一个个交交易易包包含含A、B，则则它它必必然然也也包包含含A、B的的所所有有子子集集；反反过过来来，如如果果A或或B不不是是频频繁繁项项集集，即即A或或B的的出出现现频频度度小小于于最最小小频频度度，则则A、B的的出出现现频频度度也也一一定定小小于于最最小小频频度度，因因此此A、B也不可能是频繁项集。也不可能是频繁项集。7/14/202438（1）寻找频繁项集（续）寻找频繁项集（续）v【结结论论一一】：假假设设项项集集A、B具具有有一一个个非非频频繁繁子子集集A，则则根根据据【公公理理1】可可知知，A、B不不可可能能是是频频繁繁项集。项集。v【频繁项集（大项目集）的性质】【频繁项集（大项目集）的性质】：大项目集的任一子集也一定是大的。大项目集的任一子集也一定是大的。大大项项目目集集也也称称作作是是向向下下封封闭闭的的，如如果果一一个个项项目目集集满满足足最最小小支支持持度度的的要要求求，其其所所有有的的子子集集也也满满足足这这一一要要求。求。7/14/202439（1）寻找频繁项集（续）寻找频繁项集（续）其其逆逆命命题题：如如果果知知道道一一个个项项目目集集是是小小的的，就就不不需需要要生生成成它它的的任任何何超超集集来来作作为为它它的的候候选选集集，因因为为它它们们也也一定是小的。一定是小的。AprioriApriori性性质质基基于于如如下下事事实实：根根据据定定义义，如如果果项项集集I I不不满满足足最最小小支支持持度度阈阈值值min_supmin_sup，则则I I不不是是频频繁繁的的，即即supsup（I I）min_supmin_sup。如如果果将将项项A A添添加加到到I I，则则结结果果项项集集（即即IAIA）不不可可能能比比I I更更频频繁繁出出现现。因因此此，IAIA也不是频繁的，即也不是频繁的，即supsup（IAIA）min_sup min_sup。频频繁繁项项集集的的AprioriApriori性性质质用用于于压压缩缩搜搜索索空空间间（剪剪枝枝），以提高逐层产生频繁项集的效率。，以提高逐层产生频繁项集的效率。7/14/202440（1）寻找频繁项集（续）寻找频繁项集（续）v用用图图表表示示上上述述性性质质，例例子子中中有有四四个个项项目目AA，B B，C C，DD，格格中中的的线线表表示示子子集集关关系系，大大项项目目集集的的性性质质表表明明：如如果果原原来来的的项项目目集集是是大大的的，则则在在路路径径中中位位于于其其上上的的任何集合也一定是大的。任何集合也一定是大的。ABDCABACADBCBDCDABCABDBCDACDABCD项目项目项目项目ACDACDACDACD的非的非的非的非空子集是：空子集是：空子集是：空子集是：ACACACAC，ADADADAD，CDCDCDCD，A A A A，C C C C，DDDDAAAA，B B B B，C C C C，DDDD项目集的格结构项目集的格结构项目集的格结构项目集的格结构7/14/202441（1）寻找频繁项集（续）寻找频繁项集（续）v如如果果AA，C C，DD是是大大（频频繁繁）的的，则则其其每每一一个个子子集集也也是是大大的的，如如果果其其任任何何一一个个子子集集是是小小的，则的，则 A A，C C，DD也是小的。也是小的。ABDCABACADBCBDCDABCABDBCDACDABCD项目项目项目项目ACDACDACDACD的非的非的非的非空子集是：空子集是：空子集是：空子集是：ACACACAC，ADADADAD，CDCDCDCD，A A A A，C C C C，DDDDAAAA，C C C C，DDDD的子集的子集的子集的子集7/14/202442（1）寻找频繁项集（续）寻找频繁项集（续）v【思思路路】：先先找找出出所所有有的的频频繁繁1-项项集集，以以此此为为基基础础，由由它它们们来来产产生生候候选选的的2-项项集集，通通过过观观察察数数据据（扫扫描描数数据据库库）来来计计算算它它们们的的频频度度，从从而而找找出出真真正正的的频频繁繁2-项集。以此类推，得到其它项集。以此类推，得到其它K-项集。项集。7/14/202443（1）寻找频繁项集（续）寻找频繁项集（续）v【AprioriApriori算算法法的的基基本本思思想想】：它它使使用用一一种种称称作作逐逐层层搜搜索索的的迭迭代代算算法法，通通过过k-k-项项集集用用于于探探索索（k+1k+1）-项集。项集。7/14/202444（1）寻找频繁项集（续）寻找频繁项集（续）v【AprioriApriori算法算法描述描述】：】：首首先先，通通过过扫扫描描数数据据集集，产产生生一一个个大大的的候候选选数数据据项项集集,并并计计算算每每个个候候选选数数据据项项C C发发生生的的次次数数，然然后后基基于于预预先先给给定定的的最最小小支支持持度度生生成成频频繁繁1-1-项项集集的的集集合合，该该集集合合记记作作 ；然然 后后 基基 于于 和和 数数 据据 集集 中中 的的 数数 据据，产产 生生 频频 繁繁 2-2-项项 集集 ；用用同同样样的的方方法法，直直到到生生成成频频繁繁n-n-项项集集，其其中中已已不不再再可可能生成满足最小支持度的（能生成满足最小支持度的（N+1N+1）项集）项集 。最后，从大数据项集中导出规则。最后，从大数据项集中导出规则。vv在在在在第第第第一一一一次次次次迭迭迭迭代代代代的的的的第第第第一一一一步步步步中中中中，产产产产生生生生的的的的候候候候选选选选集集集集包包包包含含含含所所所所有有有有1-1-1-1-项集，实为数据库中所有的项，再计算各自的支持度。项集，实为数据库中所有的项，再计算各自的支持度。项集，实为数据库中所有的项，再计算各自的支持度。项集，实为数据库中所有的项，再计算各自的支持度。7/14/202445（1）寻找频繁项集（续）寻找频繁项集（续）v【AprioriApriori算法算法】：】：在在第第i趟趟扫扫描描的的过过程程中中，对对C Ci i进进行行计计数数，通通过过对对数数据据库库的的一一次次扫扫描描得得到到每每个个候候选选项项集集的的频频度度，只只有有那那些些大大的的候候选选集集被被用用于于生生成成下下一一趟趟扫扫描描的的候候选选集集，即即用用L Li i生成生成C Ci+1i+1。为为了了生生成成大大小小为为i+1i+1的的候候选选，要要对对前前一一趟趟扫扫描描发发现现的大项目集进行连接运算。的大项目集进行连接运算。表表示示：L Lk k*L*Lk k =XX Y Y 其其中中 X X，Y Y L Lk k，|X X Y Y|=k|=k 1 17/14/202446（1）寻找频繁项集（续）寻找频繁项集（续）vAprioriApriori算算法法中中的的关关键键步步骤骤是是由由L Lk-1k-1找找L Lk k，该该步步骤骤可可分为两步：分为两步：第第1 1步步（连连接接）：为为找找L Lk k，通通过过L Lk-1k-1与与自自己己连连接接产产生生候候选选K-K-项项集集的的集集合合。将将该该候候选选项项集集的的集集合合记记作作C Ck k。设设l l1 1和和l l2 2是是L Lk-1k-1中中的的项项集集，记记号号l li ijj表表示示l li i的的第第j j项项。执执行行连连接接L Lk-1k-1和和L Lk-1k-1，其其中中L Lk-1k-1的的元元素素是是可可连连接接，如如果果它它们们前前（k-2k-2）个个项项相相同同而而且且第第（k-k-2 2）项不同（为简单计，设）项不同（为简单计，设l l1 1k-1lk-1l2 2k-1k-1），即：），即：l l1 11=1=l l2 21l1l1 12=l2=l2 222ll1 1k-2=lk-2=l2 2k-2lk-2l1 1k-k-1l1l2 2k-1k-1 则则L Lk-1k-1的的元元素素l l1 1和和l l2 2是是可可连连接接的的。连连接接l l1 1和和l l2 2产产生生的的结结果果的的项项集集是是l l1 11l1l1 122l l1 1k-1lk-1l2 2k-1k-1。7/14/202447（1）寻找频繁项集（续）寻找频繁项集（续）第第2 2步步（剪剪枝枝）：C Ck k是是L Lk k的的超超集集，即即它它的的成成员员可可以以是是也也可可以以不不是是频频繁繁的的，但但所所有有的的频频繁繁k-k-项项集集都都包包含含在在C Ck k中中。扫扫描描数数据据库库，确确定定C Ck k中中每每个个候候选选的的计计数数，从从而而确确定定L Lk k。然然而而，C Ck k可可能能很很大大，这这样样所所涉涉及及的的计计算算量量就就很很大大。为为压压缩缩C Ck k，可可以以用用以以下下办办法法使使用用AprioriApriori性性质质：任任何何非非频频繁繁的的（k-1k-1）-项项集集都都不不可可能能是是频频繁繁k-k-项项集集的的子子集集。因因此此，如如果果一一个个候候选选k-k-项项集集的的（k-k-1 1）-子子集集不不在在L Lk-1k-1中中，则则该该候候选选也也不不可可能能是是频频繁繁的的，从而可以由从而可以由C Ck k中删除。中删除。7/14/202448（1）寻找频繁项集（续）寻找频繁项集（续）v【AprioriApriori算算法法举举例例】：假假设设事事务务数数据据库库D中中有有4个个事务，最小频度是事务，最小频度是2，则算法的主要步骤如图所示。，则算法的主要步骤如图所示。7/14/202449（1）寻找频繁项集（续）寻找频繁项集（续）vAprioriApriori算法算法是一种是一种自底向上宽度优先搜素自底向上宽度优先搜素过程过程。7/14/202450（2）由频繁项集产生关联规则由频繁项集产生关联规则v一一旦旦找找出出所所有有的的频频繁繁项项集集，就就可可以以由由它它们们来来产产生生关关联规则。联规则。v关联规则产生的步骤：关联规则产生的步骤：对于每个频繁项集对于每个频繁项集r r，产生，产生r r的所有非空子集。的所有非空子集。对对 于于 r r的的 每每 个个 非非 空空 子子 集集 s s，如如 果果support_count(r)/support_count(s)support_count(r)/support_count(s)min_confmin_conf，则则输输出出规规则则s s（r-sr-s）。其其中中，support_countsupport_count为为支持度，支持度，min_confmin_conf为置信度。为置信度。7/14/202451（2）由频繁项集产生关联规则（续）由频繁项集产生关联规则（续）v结合下图数据库举例，产生关联规则方法。结合下图数据库举例，产生关联规则方法。根据前述计算得到的频繁项集为根据前述计算得到的频繁项集为bb、c c、ee。获获得得所所有有非非空空子子集集bb、cc、bb、ee、cc、ee、bb、cc、ee。演示关联规则的样本数据演示关联规则的样本数据TID项目项目01a、b、d02b、c、e03a、b、c、e04b、e7/14/202452（2）由频繁项集产生关联规则（续）由频繁项集产生关联规则（续）产生的关联规则：产生的关联规则：规则规则置信度置信度b bc ce e2/2=100%2/2=100%b be ec c2/3=66%2/3=66%c ce eb b2/2=100%2/2=100%b bc ce e2/4=50%2/4=50%c cb be e2/2=100%2/2=100%e eb bc c2/3=66%2/3=66%7/14/2024532.对对Apriori算法的改进算法的改进vAprioriApriori算法算法的的主要缺点主要缺点：每处理一层就要读一次数据库。每处理一层就要读一次数据库。对对于于一一个个有有n n个个项项目目的的数数据据集集，最最坏坏的的情情况况需需要要读读n n次数据库。次数据库。v为了提高算法效率，需要对为了提高算法效率，需要对AprioriApriori算法算法改进。改进。v人人们们相相继继提提出出了了一一些些方方法法，从从不不同同角角度度对对AprioriApriori算法算法进行改进进行改进。7/14/202454（1 1）减少必须分析的候选项集数量）减少必须分析的候选项集数量vAprioriApriori算算法法通通过过在在内内存存中中为为每每一一个个候候选选项项集集设设置置一个计数器来计算频度。一个计数器来计算频度。v当当候候选选项项集集很很多多时时将将占占据据大大量量内内存存，导导致致内内存存不不够够用，需要用，需要尽量减少候选项集数量尽量减少候选项集数量。vAprioriApriori算算法法在在构构造造C Ck k+1+1时时利利用用L Lk k进进行行消消减减，一一定定程程度降低了候选项集数量，度降低了候选项集数量，但是对但是对C C2 2作用不大作用不大。7/14/202455（1 1）减少必须分析的候选项集数量（续）减少必须分析的候选项集数量（续）vPCYPCY算算法法：通通过过一一种种基基于于哈哈希希的的技技术术来来减减少少候候选选集集（尤其是（尤其是C C2 2）的大小。）的大小。vPCYPCY算算法法思思路路：整整体体流流程程和和AprioriApriori算算法法一一样样，但但是是在在计计算算每每个个1-1-项项集集频频度度生生成成L L1 1时时，PCYPCY算算法法顺顺便便生生成成一个哈希表。一个哈希表。v哈哈希希表表由由若若干干桶桶组组成成，每每个个桶桶存存放放一一组组项项集集和和一一个个计计数数器器，用用来来记记录录通通过过哈哈希希函函数数映映射射到到该该桶桶的的项项集集及其频度，函数值相同的项集存放在同一个桶中。及其频度，函数值相同的项集存放在同一个桶中。v在在计计算算C C2 2时时，PCYPCY算算法法利利用用该该哈哈希希表表的的信信息息对对C C2 2做做进进一步消减。一步消减。7/14/202456（1 1）减少必须分析的候选项集数量（续）减少必须分析的候选项集数量（续）vPCYPCY算法步骤实现过程：算法步骤实现过程：第一趟扫描数据库第一趟扫描数据库时计算所有时计算所有1-1-项集的频度。项集的频度。对对每每个个交交易易，将将其其中中的的数数据据项项进进行行两两两两组组合合，然然后后哈希到一个桶中，桶计数加哈希到一个桶中，桶计数加1.1.扫扫描描结结束束时时，将将频频度度大大于于最最小小频频度度的的1-1-项项集集放放入入L L1 1中。中。进进行行第第二二趟趟扫扫描描数数据据库库，完完成成由由L L1 1生生成成C C2 2。每每一一个个候候选选2-2-项项集集（i i，j j）必必须须满满足足两两个个条条件件：第第一一，i i在在L L1 1中中，j j在在L L1 1中中；第第二二，2-2-项项集集（i i，j j）必必须须哈哈希希到一个计数值大于最小频度的桶中。到一个计数值大于最小频度的桶中。7/14/202457（1 1）减少必须分析的候选项集数量（续）减少必须分析的候选项集数量（续）vPCYPCY算算法法举举例例：假假设设哈哈希希是是h(h(i i，j j)=(order)=(order of of i i）*10+*10+（order order of of j j）mod mod 7,7,。数数据据项项a a、b b、c c、d d、e e的次序（的次序（orderorder）分别设为）分别设为1 1、2 2、3 3、4 4、5 5。7/14/202458（1 1）减少必须分析的候选项集数量（续）减少必须分析的候选项集数量（续）vPCYPCY算法算法优点：优点：减少了候选集减少了候选集C C2 2的大小。的大小。7/14/202459（2 2）减少数据库扫描的次数）减少数据库扫描的次数vAprioriApriori算算法法要要求求多多次次扫扫描描数数据据库库。如如果果大大项项集集的的最大长度是最大长度是k k，则需要最多扫描，则需要最多扫描k+1k+1遍数据库。遍数据库。v人人们们提提出出了了多多种种方方法法，通通过过两两次次或或一一次次扫扫描描数数据据库库来获得所有的频繁项目集。来获得所有的频繁项目集。v有关方法：有关方法：基于采样的方法基于采样的方法基于划分的方法基于划分的方法7/14/202460（2 2）减少数据库扫描的次数（续）减少数据库扫描的次数（续）v基于采样的方法基于采样的方法取取主主存存大大小小的的一一个个数数据据库库样样本本，运运用用AprioriApriori算算法法，并且按比例伸缩最小支持度（频度）并且按比例伸缩最小支持度（频度）s s。再再对对数数据据库库进进行行一一次次完完整整扫扫描描，对对由由样样本本数数据据库库求求得的频繁项集进行验证。得的频繁项集进行验证。7/14/202461（2 2）减少数据库扫描的次数（续）减少数据库扫描的次数（续）v基于划分的方法基于划分的方法将将交交易易数数据据库库D D划划分分为为n n块块不不想想交交的的部部分分D D1 1，D D2 2，.D.Dn n（要要求求每每一一块块都都能能够够放放在在内内存存中中），用用AprioriApriori算算法法求求出出每每一一块块D Di i中中的的所所有有频频繁繁项项集集L Li i；然然后合并所有的后合并所有的L Li i。再再次次完完整整扫扫描描一一遍遍数数据据库库，对对L L中中的的每每一一项项集集进进行行验证。验证。7/14/2024628.1.4 关联规则挖掘的重要算法关联规则挖掘的重要算法FP-GrowthvAprioriApriori算算法法的的特特点点是是要要产产生生候候选选项项集集。然然后后对对候候选项集进行计数，以判断它们是不是频繁项集。选项集进行计数，以判断它们是不是频繁项集。v在在某某些些情情况况下下，这这类类算算法法可可能能会会产产生生大大量量候候选选项项集集，代价非常大。代价非常大。vAprioriApriori算算法法的的变变形形虽虽然然使使其其得得到到一一定定程程度度的的改改善善，但并未根本改观。但并未根本改观。v迫切需要寻找新的算法。迫切需要寻找新的算法。7/14/2024638.1.4 关联规则挖掘的重要算法关联规则挖掘的重要算法FP-Growth（续）（续）vHanHan等等人人引引入入“频频繁繁模模式式增增长长”（简简称称FP-FP-增增长长）的的概念，可以不产生候选就能够找出所有的频繁项集。概念，可以不产生候选就能够找出所有的频繁项集。v韩韩家家炜炜现现为为美美国国伊伊利利诺诺伊伊大大学学计计算算机机系系正正教教授授。韩韩教教授授于于20032003年年获获选选美美国国计计算算机机协协会会院院士士（ACM ACM FellowFellow）（Citation:Citation:“For For contributions contributions in in knowledge knowledge discovery discovery and and data data miningmining”，汉汉译译：“对知识发现和数据挖掘做出贡献对知识发现和数据挖掘做出贡献”）。）。v韩韩教教授授19781978毕毕业业于于郑郑州州大大学学计计算算机机科科学学系系，同同年年考考入入中中科科院院研研究究生生，19851985年年美美国国威威斯斯康康辛辛大大学学计计算算机机系博士毕业。系博士毕业。7/14/2024648.1.4 关联规则挖掘的重要算法关联规则挖掘的重要算法FP-Growth（续）（续）vFP-GrowthFP-Growth算法算法的特点的特点把把数数据据D D压压缩缩映映射射到到一一个个小小而而紧紧凑凑的的数数据据结结构构FP-FP-TreeTree，即频繁模式树中，避免了多次扫描数据库，即频繁模式树中，避免了多次扫描数据库D D。利用利用“模式分段增长模式分段增长”法避免产生大量的候选集。法避免产生大量的候选集。采采用用分分而而治治之之的的方方法法将将数数据据挖挖掘掘任任务务分分解解成成许许多多小小任务，从而极大地缩小了搜素空间。任务，从而极大地缩小了搜素空间。7/14/2024658.1.4 关联规则挖掘的重要算法关联规则挖掘的重要算法FP-Growth（续）（续）v【举举例例】使使用用FP-GrowthFP-Growth算算法法重重新新对对例例8.48.4中中图图8.38.3所所示示的的事事务务数数据据库库进进行行关关联联规规则则挖挖掘掘，具具体体步步骤骤分分为：为：构造构造FP-TreeFP-Tree挖掘挖掘FP-TreeFP-Tree7/14/2024661.构造构造FP-Treev对对数数据据库库的的第第一一次次扫扫描描与与AprioriApriori算算法法相相同同，扫扫描描结束后得到一个频繁项（结束后得到一个频繁项（1-1-项集）集合，以及频度。项集）集合，以及频度。v设设最最小小频频度度为为2 2（与与例例8.48.4相相同同）。将将所所有有的的频频繁繁1-1-项项集集按按频频度度降降序序排排序序，结结果果集集记记作作L L。则则L=b:4L=b:4，e:3e:3，a:2a:2，c:2c:2。v构造构造FP-TreeFP-Tree：首先创建树的根节点，用首先创建树的根节点，用“nullnull”标记。标记。对对数数据据库库做做第第二二次次扫扫描描。数数据据库库中中每每条条交交易易中中的的数数据据项项按按L L中中的的次次序序依依次次处处理理（即即根根据据递递减减频频度度排排序序），并对每个交易创建一个分枝。，并对每个交易创建一个分枝。7/14/2024671.构造构造FP-Tree（续）（续）v所生成的所生成的FP-TreeFP-Tree为：为：7/14/2024681.构造构造FP-Tree（续）（续）v所生成的所生成的FP-TreeFP-Tree为：为：v将将对对交交易易数数据据库库的的而而频频繁繁模模式式挖挖掘掘问问题题转转换换成针对该成针对该FP-TreeFP-Tree进行挖掘的问题。进行挖掘的问题。nullnullc:1b:4a:1e:3c:1a:17/14/2024692.挖掘挖掘FP-Treev构构造造FP-TreeFP-Tree时时是是按按照照1-1-项项集集频频度度的的降降序序进进行行的的，对对构构造造后后的的FP-FP-reeree进进行行挖挖掘掘时时，需需要要按按照照1-1-项项集集频度的升序进行频度的升序进行。v对于每一个对于每一个1-1-项集，首先构造它的项集，首先构造它的条件数据库条件数据库。v所所谓谓条条件件数数据据库库，是是一一个个“子子数数据据库库”，由由FP-FP-TreeTree中与该中与该1-1-项集一起出现的前项集一起出现的前缀路径组成。路径组成。v具具体体实实现现：从从数数据据项项头头表表中中首首先先找找到到该该1-1-项项集集，然然后后顺顺着着链链表表找找到到它它在在树树中中出出现现的的位位置置，每每找找到到一一个个位位置置，则则得得到到从从树树根根到到该该位位置置的的一一条条路路径径，该该路路径径就构成了条件数据库中的一部分。就构成了条件数据库中的一部分。7/14/2024702.挖掘挖掘FP-Tree（续）（续）v针对图针对图8.68.6构造的构造的FP-TreeFP-Tree树进行挖掘过程：树进行挖掘过程：先先从从L L中中的的最最后后一一个个数数据据项项c c（按按频频度度的的升升序序）开开始始，沿沿着着c c的的节节点点链链表表，首首先先发发现现C C出出现现在在FP-TreeFP-Tree的的一一条条分分枝枝b:1 c:1上上，则则将将该该路路径径的的前前缀缀b:1 e:1放到放到c c的条件数据库中；的条件数据库中；再再顺顺着着c c的的链链表表走走下下去去，发发现现c c出出现现在在FP-TreeFP-Tree的的另另一一条条分分枝枝b:1 c:1上上，则则将将该该路路径径前前缀缀放到放到c c的条件数据库中；的条件数据库中；得得到到c c的的条条件件数数据据库库为为b:1 e:1，b:1 a:1，构构造造出出的的FP-TreeFP-Tree有有两两个个节节点点b:2 e:2，b b和和e e的频度均不小于的频度均不小于2 2，是频繁的。，是频繁的。7/14/2024712.挖掘挖掘FP-Tree（续）（续）得到该子数据库生成的频繁模式得到该子数据库生成的频繁模式bb，e e，bebe。将将其其与与生生成成该该子子数数据据库库的的项项目目c c连连接接后后（称称为为增增长长模模式式），生生成成所所有有包包含含c c的的频频繁繁模模式式，即即bcbc：22，ecec：22，becbec：22。依次类推依次类推.7/14/2024728.1.5 其它关联规则挖掘方法其它关联规则挖掘方法v前前面面介介绍绍的的关关联联规规则则没没有有考考虑虑数数据据对对象象的的概概念念层层次次和和蕴蕴含含多多个个谓谓词词，实实际际生生活活中中往往往往并并非非如如此此。如如：惠惠普普牌牌打打印印机机-打打印印机机-电电子子产产品品；或或者者数数据据库库中中不不但但记记录录了了顾顾客客购购买买商商品品的的名名称称，而而且且还还记记录录了了数数量、单价等，需要体现多种维度的关联关系。量、单价等，需要体现多种维度的关联关系。v多层关联规则多层关联规则多维关联规则多维关联规则7/14/2024731.多层关联规则多层关联规则v挖挖掘掘方方法法：一一般般采采用用自自顶顶向向下下的的策策略略，从从最最一一般般的的概概念念层层（第第0 0层层）开开始始，到到较较具具体体的的某某特特定定概概念念层层，在在每每个个概概念念层层上上寻寻找找频频繁繁项项集集，直直到到不不能能找找到到频频繁繁项集为止。项集为止。v最最小小支支持持度度的的设设置置：采采用用逐逐层层递递减减的的支支持持度度设设置置策策略。略。7/14/2024742.多维关联规则多维关联规则v涉及数据表的多个字段。涉及数据表的多个字段。二维关联规则二维关联规则：如：性别：如：性别=“女女”职业职业=“护士护士”。三三维维关关联联规规则则：如如：年年龄龄=“20.3020.30”职职业业=“学生学生”购买购买=“电脑电脑”。7/14/202