Python数据挖掘与机器学习第2版 课件 第 6 章 关联分析

Python数据挖掘与机器学习第6章关联规则挖掘OverviewFrequentItemsetsAssociationRulesSequentialPatterns2ARealExample第6章关联规则挖掘关联规则分析用于在一个数据集中找出各数据项之间的关联关系，广泛用于购物篮数据、生物信息学、医疗诊断、网页挖掘和科学数据分析中。关联规则分析又称购物篮分析，最早是为了发现超市销售数据库中不同商品之间的关联关系。采用关联模型比较典型的案例：“尿布与啤酒”的故事飓风与蛋挞10十一月20244第6章关联规则挖掘5关联规则分析通过量化的数字描述某物品的出现对其他物品的影响程度，是数据挖掘中较活跃的研究方法之一。目前，常用的关联规则分析算法如表6-1所示。频繁项集、闭项集和关联规则关联规则分析最早是为了发现超市销售数据库中不同商品间的关联关系。频繁模式（FrequentPattern）是指频繁出现在数据集中的模式（如项集，子序列或子结构）。挖掘频繁模式可以揭示数据集的内在的、重要的特性，可以作为很多重要数据挖掘任务的基础，比如：10十一月20246频繁项集、闭项集和关联规则1.关联规则的表示形式模式可以用关联规则（AssociationRule）的形式表示。例如购买计算机也趋向于同时购买打印机，可以用如下关联规则表示。规则的支持度（Support）和置信度（Confidence）是规则兴趣度的两种度量，分别反映规则的有用性和确定性。10十一月20247频繁项集、闭项集和关联规则2.频繁项集和闭项集同时满足最小支持度阈值（min_sup）和最小置信度阈值（min_conf）的规则称为强关联规则。10十一月20248频繁项集、闭项集和关联规则一般来说，关联规则的挖掘可以看作两步的过程：（1）找出所有频繁项集，该项集的每一个出现的支持度计数≥min_sup；（2）由频繁项集产生强关联规则，即满足最小支持度和最小置信度的规则。10十一月20249频繁项集、闭项集和关联规则由于第2步的开销远小于第1步，因此挖掘关联规则的总体性能由第1步决定。第1步主要是找到所有的频繁k项集，而在找频繁项集的过程中，需要对每个k项集，计算支持度计数以发现频繁项集，k项集的产生过程如图6.110十一月202410频繁项集、闭项集和关联规则因此，项集的个数太大严重影响算法的效率。为了克服这一困难，引入闭频繁项集和极大频繁项集的概念。项集X在数据集D中是闭的（Closed），如果不存在X的真超项集Y使得Y与X在D中具有相同的支持度计数。10十一月202411频繁项集挖掘方法发现频繁项集是挖掘关联规则的基础。Apriori算法通过限制候选产生发现频繁项集，FP-growth算法发现频繁模式而不产生候选。10十一月202412Apriori算法10十一月202413Apriori算法是Agrawal和Srikant于1994年提出，是布尔关联规则挖掘频繁项集的原创性算法，通过限制候选产生发现频繁项集。Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于探索（k+1）项集。具体过程描述如下：首先扫描数据库，累计每个项的计数，并收集满足最小支持度的项找出频繁1项集记为L1。然后使用L1找出频繁2项集的集合L2，使用L2找出L3，迭代直到无法再找到频繁k项集为止。找出每个Lk需要一次完整的数据库扫描。Apriori算法使用一种称为先验性质的特性进行搜索空间的压缩，即频繁项集的所有非空子集也一定是频繁的。Apriori算法Apriori算法产生k项频繁集的过程主要包括连接和剪枝两步。10十一月202414Apriori算法Apriori算法产生k项频繁集的过程主要包括连接和剪枝两步。（2）剪枝Ck是Lk的超集，Ck的成员不一定全部是频繁的，但所有频繁的k项集都包含在Ck中。为了减少计算量，可以使用Apriori性质，即如果一个k项集的（k-1）子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。这种子集测试可以使用所有频繁项集的散列树快速完成。10十一月202415Apriori算法10十一月202416由频繁项集产生关联规则10十一月202417由频繁项集产生关联规则10十一月202418提高Apriori算法的效率Apriori算法使用逐层搜索的迭代方法，随着k的递增不断寻找满足最小支持度阈值的“k项集”，第k次迭代从k-1次迭代的结果中查找频繁k项集，每一次迭代都要扫描一次数据库。而且，对候选项集的支持度计算非常繁琐。为了进一步提高Apriori算法的效率，一般采用减少对数据的扫描次数、缩小产生的候选项集以及改进对候选项集的支持度计算方法等策略。1.基于hash表的项集计数2.事务压缩（压缩进一步迭代的事务数）3.抽样（在给定数据的一个子集挖掘）4.动态项集计数10十一月202419频繁模式增长算法Apriori算法的候选产生-检查方法显著压缩了候选集的规模，但还是可能要产生大量的候选项集。而且，要重复扫描数据库，通过模式匹配检查一个很大的候选集合。频繁模式增长（FP-growth）是一种不产生候选频繁项集的算法，它采用分治策略（DivideandConquer），在经过第一遍扫描之后，把代表频繁项集的数据库压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息；然后将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，再对这些条件库分别进行挖掘（降低了I/O开销）。10十一月202420频繁模式增长算法1.FP树原理FP树采用分治策略的方法，在经过第一遍扫描之后，把代表频繁项集的数据库压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息；然后将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘（降低了I/O开销）。10十一月202421频繁模式增长算法2.FP树构建过程示例（1）从数据库构建一个FP树第一次扫描数据库，导出频繁项的集合（1-项集），并将频繁项按支持度计数降序排列10十一月202422频繁模式增长算法根据上述生成的项集，构造FP树，如图6-4所示。10十一月202423频繁模式增长算法根据上述生成的项集，构造FP树，如图6-4所示。10十一月202424频繁模式增长算法为了方便树的遍历，创建一个项头表，使每项通过一个结点链指向它在树中的位置。扫描所有的事务，得到的FP树如图6-5所示。10十一月202425频繁模式增长算法FP树挖掘（1）从FP树到条件模式基从项头表开始挖掘，由频率低的结点开始。在图6.5的FP树中，首先依据结点o在该路径上的支持度更新前缀路径上结点的支持度计数。在此基础上，得到o点的条件模式基{f,c,a,b,m,l:1}，{f,b:1}。构建条件FP树。利用o点的条件模式基得到o点的条件FP树。如果该条件FP树有多条路径，则继续迭代，构造条件FP树。否则，如果该FP树只有一条路径，则直接求以该结点结尾的频繁项集。10十一月202426频繁模式增长算法图6-5中节点m的条件模式基为{f,c,a:2}，{f,c,a,b:1}，m的条件FP树如图6-6所示，可以直接获得关于m的频繁项为m,fm,cm,am,fcm,fam,cam,fcam。11/10/2024图6-6节点m的条件FP树频繁模式增长算法FP-growth方法将发现长频繁模式的问题转换化为在较小的条件数据库中递归地搜索一些较短模式，然后连接后缀。它使用最不频繁的项做后缀，提供了较好的选择性，显著降低了搜索开销。当数据库很大时，构造基于主存的FP树是不现实的，一种有趣的选择是将数据库划分成投影数据库集合，然后在每个投影数据库上构造FP树并进行挖掘。10十一月202428使用垂直数据格式挖掘频繁项集Apriori算法和FP-growth算法都从TID项集格式（即{TID：itemset}）的事务集中挖掘频繁模式。其中TID是事务标识符，而itemset是事务TID中购买的商品。这种数据格式称为水平数据格式（HorizontalDataFormat）。使用垂直数据格式有效地挖掘频繁项集，它是等价类变换(EquivalencCLAssTransformation，Eclat)算法的要点。10十一月202429使用垂直数据格式挖掘频繁项集10十一月202430使用垂直数据格式挖掘频繁项集10十一月202431例6.3解释了通过探查垂直数据格式挖掘频繁项集的过程。首先，通过扫描一次数据集，把水平格式的数据转换成垂直格式。项集的支持度计数简单地等于项集的TID集的长度。从k=1开始，可以根据先验性质，使用频繁k项集来构造候选（k+1）项集。通过取频繁k项集的TID集的交，计算对应的（k+1）项集的TID集。重复该过程，

每次k增加1，直到不能再找到频繁项集或候选项集。

关联模式评估方法大部分关联规则挖掘算法都使用支持度-置信度框架。尽管最小支持度和置信度阈值可以排除大量无趣规则的探查，但仍然会有一些用户不感兴趣的规则存在。当使用低支持度阈值挖掘或挖掘长模式时，这种情况尤为严重。强关联规则不一定是有趣的：例：10十一月202432从关联分析到相关分析由于支持度和置信度还不足以过滤掉无趣的关联规则，因此，可以使用相关性度量来扩展关联规则的支持度-置信度框架。相关规则框架为：10十一月202433从关联分析到相关分析10十一月202434从关联分析到相关分析10十一月202435Apriori算法应用1在Pyhton中进行关联规则挖掘时需要用到apyori包，apyori包的安装方式为：pipinstallapyori返回结果result中的属性说明：items–项集，frozenset对象，可迭代取出子集；support–支持度，float类型；confidence–置信度或可信度，float类型；ordered_statistics–存在的关联规则，可迭代，迭代后，其元素的属性：items_base–关联规则中的分母项集；confidence–上面的分母规则所对应的关联规则的可信度。10十一月202436Apriori算法应用2关联规则目前在scikit-learn中并没有实现。机器学习扩展库mlxtend：是一款高级的机器学习扩展库,可用于日常机器学习任务的主要工具,也可以作为sklearn的一个补充和辅助工具。

mlxtend提供了多种分类和回归算法api，包括多层感知机、stacking分类器、逻辑回归等。11/10/2024Apriori算法应用2安装pipinstallmlxtend数据：importpandasaspditem_list=[['牛奶','面包'],['面包','尿布','啤酒','土豆'],['牛奶','尿布','啤酒','可乐'],['面包','牛奶','尿布','啤酒'],['面包','牛奶','尿布','可乐']]item_df=pd.DataFrame(item_list)11/10/2024#frommlxtend.preprocessingimportTransactionEncodeimportmlxtendte=mlxtend.preprocessing.TransactionEncoder()df_tf=te.fit_transform(item_list)df=pd.DataFrame(df_tf,columns=te.columns_)display(df)Apriori算法应用2计算频繁项集frommlxtend.frequent_patternsimportapriori#use_colnames=True表示使用元素名字，默认的False使用列名代表元素frequent_itemsets=apriori(df,min_support=0.05,use_colnames=True)frequent_itemsets.sort_values(by='support',ascending=False,inplace=True)#选择2频繁项集print(frequent_itemsets[frequent_itemsets.itemsets.apply(lambdax:len(x))==2])11/10/2024Apriori算法应用2计算关联规则frommlxtend.frequent_patternsimportassociation_rules#metric可以有很多的度量选项，返回的表列名都可以作为参数association_rule=association_rules(frequent_itemsets,metric='confidence',min_t