《频繁模式挖掘ppt课件》由会员分享，可在线阅读，更多相关《频繁模式挖掘ppt课件（92页珍藏版）》请在金锄头文库上搜索。
1、病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程五邑大学计算机学院五邑大学计算机学院何国辉何国辉数据仓库与数据挖掘数据仓库与数据挖掘数据仓库与数据挖掘数据仓库与数据挖掘 Data Warehouse and Data MiningData Warehouse and Data Mining2022/4/291病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程数据仓库与数据挖掘数据仓库与数据挖掘 Data Warehouse and Data Mining第八章第八章 频繁模
2、式挖掘频繁模式挖掘2022/4/292病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程v频频繁繁模模式式(frequent pattern)是是指指在在数数据据集集中中频频繁繁出出现的模式。现的模式。v现现实实生生活活中中存存在在多多种种类类型型的的频频繁繁模模式式，包包括括频频繁繁项项集集、频繁子序列频繁子序列（又称序列模式）和（又称序列模式）和频繁子结构频繁子结构。8.0 基本概念基本概念2022/4/293病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程v几个概念。
3、几个概念。频频繁繁项项集集一一般般是是指指频频繁繁地地在在事事务务数数据据集集中中一一起起出出现现的的商商品品的的集集合合，如如小小卖卖部部中中被被许许多多顾顾客客频频繁繁地地一一起起购买的牛奶和面包。购买的牛奶和面包。频频繁繁子子序序列列，如如顾顾客客倾倾向向于于先先购购买买便便携携机机，再再购购买买数数码码相相机机，然然后后再再购购买买内内存存卡卡这这样样的的模模式式就就是是一一个个（频繁）序列模式。（频繁）序列模式。8.0 基本概念（续）基本概念（续）2022/4/294病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程频频繁繁
4、子子结结构构是是指指从从图图集集合合中中挖挖掘掘频频繁繁子子图图模模式式。子子结结构构可可能能涉涉及及不不同同的的结结构构形形式式（例例如如，图图、树树或或格格），可可以以与与项项集集或或子子序序列列结结合合在在一一起起。如如果果一一个个子子结结构频繁地出现，则称它为（频繁）子结构模式。构频繁地出现，则称它为（频繁）子结构模式。8.0 基本概念（续）基本概念（续）2022/4/295病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.0 基本概念（续）基本概念（续）v频繁项集挖掘是频繁模式挖掘的基础。频繁项集挖掘是频繁模式挖掘的基础
5、。2022/4/296病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程v关关联联规规则则(Association Rule Mining)挖挖掘掘是是数数据据挖挖掘中最活跃的研究方法之一。掘中最活跃的研究方法之一。v关关联联规规则则挖挖掘掘的的目目的的：找找出出数数据据库库中中不不同同数数据据项项集集之间隐藏的关联关系。之间隐藏的关联关系。 8.1 频繁项集和关联规则频繁项集和关联规则2022/4/297病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程v最早是由最早是由R
6、.Agrawal等人在等人在1993年提出的。年提出的。v其其目目的的是是为为了了发发现现超超市市交交易易数数据据库库中中不不同同商商品品之之间间的关联关系。的关联关系。v一一个个典典型型的的关关联联规规则则的的例例子子是是：70%购购买买了了牛牛奶奶的的顾客将倾向于同时购买面包。顾客将倾向于同时购买面包。v经经典典的的关关联联规规则则挖挖掘掘算算法法：Apriori算算法法和和FP-growth算法算法 。 8.1 频繁项集和关联规则（续）频繁项集和关联规则（续）2022/4/298病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程
7、1. 1. 购物篮分析引发关联规则挖掘的例子购物篮分析引发关联规则挖掘的例子 v问问题题：“什什么么商商品品组组或或集集合合顾顾客客多多半半会会在在一一次次购购物物中同时购买？中同时购买？”v购购物物篮篮分分析析：设设全全域域为为商商店店出出售售的的商商品品的的集集合合（即即项项目目全全集集），一一次次购购物物购购买买（即即事事务务）的的商商品品为为项项目目全全集集的的子子集集，若若每每种种商商品品用用一一个个布布尔尔变变量量表表示示该该商商品品的的有有无无，则则每每个个购购物物篮篮可可用用一一个个布布尔尔向向量量表表示示。通通过过对对布布尔尔向向量量的的分分析析，得得到到反反映映商商品品频频
8、繁繁关关联联或或同时购买的购买模式同时购买的购买模式。这些模式可用关联规则描述。这些模式可用关联规则描述。 8.1 频繁项集合关联规则（续）频繁项集合关联规则（续）2022/4/299病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述问题描述v现现实实：商商店店有有很很多多商商品品，例例如如“面面包包”、“牛牛奶奶”、“啤啤酒酒”等等。顾顾客客将将把把他他们们需需要要的的商商品品放放入入购购物物篮篮中。中。v研研究究的的目目的的：发发现现顾顾客客通通常常会会同同时时购购买买哪哪些些商商品品。通通过过上上述述研研究究
9、可可以以帮帮助助零零售售商商合合理理地地摆摆放放商商品品，引引导销售。导销售。2022/4/2910病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述（续）问题描述（续）v举举例例：某某一一个个时时间间段段内内顾顾客客购购物物的的记记录录形形成成一一个个交交易易数数据据库库，每每一一条条记记录录代代表表一一次次交交易易，包包含含一一个个交交易标识符（易标识符（TID）和本次交易所购买的商品。）和本次交易所购买的商品。一个简单交易数据库实例一个简单交易数据库实例数据库D：TID项001A、C、D002B、C、E003
10、A、B、C、E004B、E2022/4/2911病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.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-项项集集：一一个个大大小小
11、为为K K的的项项集集（包包含含有有K K项项，如如AA、BB为为2-2-项集，项集，AA、C C、DD为为3-3-项集）。项集）。一一个个交交易易T：是是由由在在I I中中的的数数据据项项所所构构成成的的集集合合，即即T I I。2022/4/2912病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述（续）问题描述（续）v【定定义义1 1】以以商商场场交交易易数数据据库库为为例例，形形式式化化地地描描述述关联规则关联规则：设设I=i1，i2，,im是是项项的的集集合合，表表示示各各种种商商品品的的集集合合；D=
12、t1，t2，,tn为为交交易易集集，表表示示每每笔笔交交易易的的集集合合（是是全全体体事事务务的的集集合合）。其其中中每每一一个个事事务务T都都是是项项的的集集合合，且且有有T I。每每个个事事务务都都有有一一个个相相关关的的唯唯一一标标识识符符和和它它对对应应，也也就就是是事事务务标标识识符符或或TID。2022/4/2913病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述（续）问题描述（续）设设X为为一一个个由由多多个个项项目目构构成成的的集集合合，称称为为项项集集，如如001中中的的A、C、D，当当且且仅仅
13、当当X T时时我我们们说说事事务务T包含包含X。2022/4/2914病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述（续）问题描述（续）项项集集X在在在在事事务务数数据据库库DB中中出出现现的的次次数数占占总总事事务务的的百分比叫做项集的百分比叫做项集的支持度支持度。如如果果项项集集的的支支持持度度超超过过用用户户给给定定的的最最小小支支持持度度阈阈值值，就称该项集是就称该项集是频繁项集频繁项集（或大项集）。（或大项集）。2022/4/2915病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一
14、定部位生长繁殖，引起不同程度的病理生理过程8.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中同时出现的概率中同时出现的概率。2022/4/2916病原体侵入机体，消弱机
15、体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.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)( (包含
16、包含X X和和Y Y的事务数的事务数/ /事务总数事务总数)100)100confidence(Xconfidence(XY)Y)( (包包含含X X和和Y Y的的事事务务数数/ /包包含含X X的的事事务务数数)100)1002022/4/2917病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述（续）问题描述（续）v【例【例8.18.1】某顾客购物的交易数据库总交易数为某顾客购物的交易数据库总交易数为5 5。2022/4/2918病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程8.1.1 问题描述（续）问题描述（续）v【例【例8.18.1】相关的支持度和置信度。相关的支持度和置信度。support(Xsupport(XY)Y)( (包含包含X X和和Y Y的事务数的事务数/ /事务总数事务总数)100)100confidence(Xconfidence(XY)Y)( (包含包含X X和和Y Y的事务数的事务数/ /包含包含X X的事务数的事务
