Python数据挖掘算法与应用 课件 第8-10章 关联规则分析、预测模型、深度学习简介

Association-rulesAnalysis第8章

关联规则分析关联规则相关概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1关联规则典型应用场景8.6学习目标1关联规则分析概述OverviewofAssociationRuleAnalysis8.1什么是关联规则分析？关联规则分析关联规则分析（Association-rulesAnalysis）是数据挖掘领域的重要挖掘任务之一，它是以某种方式分析数据源，从数据样本集中发现一些潜在有用的信息和不同数据样本之间关系的过程。关联规则分析于1993年由美国IBMAlmadenResearchCenter的RakeshAgrawal等人在进行市场购物篮分析时首先提出的，用以发现超市销售数据库中的顾客购买模式，现在已经广泛应用于许多领域。关联规则分类布尔型布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型1、基于关联规则处理的变量2、基于规则中数据的抽象层次3、基于规则中涉及到的数据的维数单层多层单维多维数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。在单层的关联规则中，所有变量都没有考虑到现实数据是具有多个不同层次的。在多层的关联规则中，对数据的多层性已经进行了充分的考虑。在单维的关联规则中，只涉及到数据的一个维。换言之，单维关联规则是处理单个属性中的一些关系。多维的关联规则中，要处理的数据将会涉及多个维。换言之，多维关联规则是处理多个属性之间的某些关系。关联规则相关概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1关联规则典型应用场景8.6学习目标2关联规则相关概念RelatedConceptsofAssociationRules8.2基本概念事务集每一个事务（Transaction）T

对应数据库的一条记录，因此事务集合对应于数据集D={T1,T2,…,Tm}。事务事务是项的集合，其中一个事务对应于一条记录Ti，项对应于属性，即Ti={Ai1，Ai2,…,Aip}，Ti

D。对应每一个事务有唯一的标识，如事务号，记为TID。⊆项项是事务中的元素，对应于记录中的字段。项集项集是指若干项的集合。假设

I={A1,A2,…,An}是数据集D中所有项的集合，I

中任何子集X都称为项集（itemset），若|X|=k，则称X为k-项集。设Ti是一个事务，X是k-项集，如果X

Ti，则称事务Ti包含项集X。⊆基本概念有了以上这些概念的定义，则可将关联规则的定义表述如下：关联规则一个关联规则是形如X=>Y的蕴涵式，X

I，Y

I，并且X∩Y=ϕ，X、Y分别称为关联规则X=>Y的前提和结论。关联规则X=>Y表示这样一种关联，如果一个事务Ti包含项集X中的所有项，那么该事务Ti与项集Y的所有项有着关联关系。⊆⊆支持度、置信度和提升度一般使用支持度（support）和置信度（confidence）两个参数来描述关联规则的项。1、支持度项集支持数：数据集D中包含项集X的事务数称为项集X的支持数，记为：项集支持度：项集X的支持度是指X在数据集D中出现的概率。规则支持度：关联规则X=>Y在数据集D中的支持度是D中同时包含X、Y的事务数与所有事务数之比，记为S_port(X=>Y)。支持度描述了X、Y这两个事务在事务集D中同时出现（记为X∪Y）的概率。支持度、置信度和提升度2、置信度规则置信度：关联规则X=>Y的置信度是指同时包含X、Y的事务数与包含X的事务数之比，它用来衡量关联规则的可信程度。记为：一般情况下，只有关联规则的置信度大于或等于预设的阈值，就说明了它们之间具有某种程度的相关性，这才是一条有价值的规则。如果关联规则置信度大于或等于用户给定的最小置信度阈值，则称关联规则是可信的。支持度、置信度和提升度3、提升度提升度（Lift）是指当销售一个商品A时，另一个商品B销售率会增加多少。计算公式为：假设关联规则’牛奶’=>’鸡蛋’的置信度为C_dence(’牛奶’=>’鸡蛋’)=2/4，牛奶的支持度S_port(’牛奶’)=3/5，则’牛奶’和’鸡蛋’的支持度Lift(’牛奶’=>’鸡蛋’)=0.83。当关联规则A=>B的提升度值大于1的时候，说明商品A卖得越多，B也会卖得越多；当提升度等于1则意味着商品A和B之间没有关联；当提升度小于1则意味着购买商品A反而会减少B的销量。频繁项集关联规则分析就是在数据集中找出所有频繁和可信的关联规则，即强关联规则，通常所说的关联规则指的就是强关联规则。设k项集X的支持度为S_port(X)，若S_port(X)不小于用户指定的最小支持度，则称X为k项频繁项集（frequentk-itemset）或频繁k项集，否则称X为k项非频繁项集或非频繁k项集。频繁项集频繁项集分析就是找出数据集中所有支持度大于或等于最小支持度阈值的项集。频繁项集分析如果X是一个频繁项集，并且X的任意一个超集都是非频繁的，则称X是最大频繁项集。最大频繁项集给定某数据集和最小支持度阈值，如果挖掘算法需要判断k项集是频繁项集还是非频繁项集，那么k项集称为候选项集。候选项集频繁项集(1)频繁项集的所有非空子集也是频繁的。(2)非频繁项集的所有超集是非频繁的。频繁项集具有两个非常重要的性质：设X、Y是D中的项集，由频繁项集的性质，若X

Y，如果X是非频繁项集，则Y也是非频繁项集；若X

Y，如果Y是频繁项集，则X也是频繁项集。给定一个数据集D，关联规则分析的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度和最小置信度的关联规则。关联规则分析的任务就是要挖掘出D中所有的强关联规则X=>Y。强关联规则X=>Y对应的项集X∪Y必定是频繁项集，频繁项集X∪Y导出的关联规则X=>Y的置信度可由频繁项集X和X∪Y的支持度计算。因此，可以把关联规则分析划分为两个子问题：一个是找出所有的频繁项集，即所有支持度不低于给定的最小支持度的项集；另一个是由频繁项集产生强关联规则，即从第一个子问题得到的频繁项集中找出置信度不小于用户给定的最小置信度的规则。其中，第一个子问题是关联规则分析算法的核心问题，是衡量关联规则分析算法的标准。⊆⊆关联规则相关概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1关联规则典型应用场景8.6学习目标3Apriori算法AprioriAlgorithm8.3Apriori算法思想第二阶段利用频繁项集产生所需的规则。对给定的L，如果L包含其非空子集A，假设用户给定的最小支持度和最小置信度阈值分别为minS_port和minC_dence，并满足minS_port(L)/minS_port(A)≥minC_dence，则产生形式为A=>L-A的规则。找出所有超出最小支持度的项集，形成频繁项集。首先通过扫描数据集，产生一个大的候选项集，并计算每个候选项集发生的次数，然后基于预先给定的最小支持度生成一维项集L1。再基于L1和数据集中的事务，产生二维项集L2；依此类推，直到生成N维项集LN，并且已经不可能再生成满足最小支持度的N+1维项集。这样就依此产生项集{L1,L2,…,LN}。第一阶段Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心方法是基于频繁项集理论的递推方法。在这两个阶段中，第一阶段是算法的关键。一旦找到了项集，关联规则的导出是自然的。事实上，我们一般只对满足一定的支持度和可信度的关联规则感兴趣。挖掘关联规则的问题就是产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的关联规则。例8.1包含5个事务的商品销售数据集合D如表8.1所示。表8.1销售数据集D的商品项假设用户的最小支持度minS_port=0.4，最小置信度minC_dence=0.6，用Apriori算法产生关联规则。第一阶段，找出存在于D中所有的频繁特征项集，即那些支持度大于minS_port的项集。(1)利用minS_port=0.4，创建频繁1-项集，如表8.2所示。表8.2产生频繁1-项集根据minS_port=0.4，在1-项候选集C1中，项“葱”、“蒜”、和“芹菜”不满足用户最小支持度要求，所以将这些项删除，得到频繁1-项集L1。(2)利用minS_port=0.4，创建频繁2-项集，如表8.3所示。表8.3产生频繁2-项集TID商品项

TID商品项T1鸡蛋、面包、西红柿、葱、蒜、牛奶T4鸡蛋、芹菜、牛奶T2面包、牛奶T5鸡蛋、西红柿、豆角T3鸡蛋、豆角、牛奶

候选1-项集C1

频繁1-项集L1鸡蛋4

鸡蛋4面包2

面包2西红柿2

西红柿2葱1

牛奶4蒜1

豆角2牛奶4

豆角2

芹菜1

(3)通过表8.3形成候选3-项集C3。仍然利用minS_port=0.4，可以看出C3集合中的每个项集都有非频繁子集，所以创建频繁3-项集L3为空集，项集生成过程结束。如表8.4所示。表8.4产生3-项频繁集由此可知，最大频繁项集为L2。第二阶段，在找出的频繁项集的基础上产生强关联规则。即产生那些支持度和置信度分别大于或等于用户给定的阈值的关联规则。以生成的L2为基础，生成可能的关联规则如下：(1)C_dence(鸡蛋=>牛奶)=3/4=0.75(2)C_dence(牛奶=>鸡蛋)=3/4=0.75(3)C_dence(鸡蛋=>西红柿)=2/4=0.5(4)C_dence(西红柿=>鸡蛋)=2/2=1.0(5)C_dence(鸡蛋=>豆角)=2/4=0.5(6)C_dence(豆角=>鸡蛋)=2/2=1.0(7)C_dence(牛奶=>面包)=2/4=0.5(8)C_dence(面包=>牛奶)=2/2=1.0根据用户最小置信度minC_dence=0.6，关联规则为(1)、(2)、(4)、(6)、(8)。候选3-项集C3

频繁3-项集L3鸡蛋、牛奶、西红柿1

空集

鸡蛋、牛奶、豆角1

鸡蛋、西红柿、豆角1

鸡蛋、牛奶、面包1

候选2-项集C2

频繁2-项集L2鸡蛋、面包1

鸡蛋、牛奶3鸡蛋、西红柿2

鸡蛋、西红柿2鸡蛋、牛奶3

鸡蛋、豆角2鸡蛋、豆角2

面包、牛奶2面包、西红柿1

面包、牛奶2

面包、豆角0

西红柿、牛奶1

西红柿、豆角1

牛奶、豆角1

Apriori算法Apriori算法是一种深度优先算法，它使用频繁项集性质的先验知识，利用逐层搜索的迭代方法完成频繁项集的挖掘工作：即k-项集用于搜索产生(k+1)-项集。其具体做法是首先产生候选1-项集C1，再根据C1产生频繁1-项集L1，然后利用L1产生候选2-项集C2，再从C2中找出频繁2-项集L2，而L2可以进一步找出L3，这样如此不断地循环继续下去，直到不能找到频繁k-项集为止。由于从候选项集中产生频繁项集的过程需要遍历数据集，因此如何正确地产生数目最少的候选项集十分关键。候选项集产生的过程被分为两个部分：联合与剪枝。采用这两种方式，使得所有的频繁项集既不会遗漏又不会重复。剪枝的目的是减少扫描数据集时需要比较的候选项集数量。剪枝的原则是：候选项集c的k个长度为k-1的子集都在Lk-1中，则保留c；否则c被剪枝。Apriori算法用apriori_gen函数来生成候选项集，该函数从频繁项集Lk-1中派生出候选项集Ck。apriori_gen函数分为两步，第一步用Lk-1自连接生成Ck；第二步剪掉无效的项集。生成候选k-项集函数apriori_gen()算法描述如下：(1)生成候选k-项集CkinsertintoCkselectp.Item1,p.Item2,…,p.Itemk-1,q.Itemk-1fromLk-1p,Lk-1qWherep.Item1=q.Item1,p.Item2=q.Item2,…,p.Itemk-2=q.Itemk-2,p.Itemk-1<q.Itemk-1//这里是对两个具有k-1个共同项的频繁集Lk-1进行链接(2)剪枝对于项集c∈Ck，如果存在c的子集s，|s|=k-1，且s∉Lk-1，则剪掉c。

forall项集集c∈Ckdoforall(k-1)-项集c的子集sdoifs∉Lk-1thenCk=Ck-{c}Apriori算法描述输出产生关联规则处理流程：step1：L1={1-项集}

//扫描所有项，计算每个项出现的次数，产生频繁1-项集step2：for(k=2;Lk-1≠Φ;k++)dobegin

//进行迭代循环，根据前一次的Lk-1得到频繁k-项集Lkstep3：Ck=apriori_gen(Lk-1)

//产生k项候选集step4：forallDi∈Ddo

//扫描一遍数据集Dstep5：beginstep6：Ci=subset(Ck,Di)

//确定每个Di所含候选k-项集的subset(Ck,Di)输入数据集D，最小支持度阈值minS_port，最小置信度minC_dencestep7：forallc∈Cidoc.count++

//对候选集的计数step8：Lk={c∈Ci|c.count≥minS_port}

//删除候选项集中小于最小支持度的，得到频繁k-项集step9：endstep10：endstep11：forallsubsets⊆Lk

//对每个频繁项集Lk，产生Lk的所有非空子集sstep12：ifC_dence(s=>Lk-s)≥minC_dence

//可信度大于等于最小可信度step13：则输出s=>Lk-s

//由频繁集产生关联规则

Apriori算法的python实现L,suppData=apriori(df,min_support=0.5,use_colnames=False,max_len=None)Apriori()函数常用形式为：参数说明：(1)df：表示给定的数据集。(2)min_support：表示给定的最小支持度。(3)use_colnames：默认False，表示返回的项集，用编号显示。如果值为True则直接显示项名称。(4)max_len：默认是None，表示最大项组合数，不做限制。如果只需要计算两个项集，可将这个值设置为2。返回值：(1)L：返回频繁项集。(2)suppData：返回频繁项集的相应支持度。Sklearn库中没有Apriori算法。但是可以采用Python的第三方库实现Aprior算法发掘关联规则。相关的库有mlxtend机器学习包等，首先需要导入包含Apriori算法的mlxtend包：pipinstallmlxtend。例8.2用Python实现Apriori算法示例。importnumpyasnpdata_set=np.array([['鸡蛋','面包','西红柿','葱','蒜','牛奶'],['面包','牛奶'],['鸡蛋','牛奶','豆角'],['鸡蛋','牛奶','芹菜'],['鸡蛋','西红柿','豆角']])defget_C1(data_set):C1=set()foritemindata_set:forlinitem:C1.add(frozenset([l]))returnC1#data_set--数据集；C--候选集；min_support--最小支持度defgetLByC(data_set,C,min_support):L={}#频繁项集和支持数forcinC:fordataindata_set:ifc.issubset(data):ifcnotinL:L[c]=1else:L[c]+=1errorKeys=[]forkeyinL:support=L[key]/float(len(data_set))ifsupport<min_support:#未达到最小支持数errorKeys.append(key)else:L[key]=supportforkeyinerrorKeys:L.pop(key)returnL'''根据频繁(k-1)项集自身连接产生候选K项集Ck并剪去不符合条件的候选L—频繁K-1项集'''defgetCByL(L,k):len_L=len(L)#获取L的频繁项集数量L_keys=list(L.keys())#获取L的键值C=set()foriinrange(len_L):forjinrange(1,len_L):l1=list(L_keys[i])l1.sort()l2=list(L_keys[j])l2.sort()if(l1[0:k-2]==l2[0:k-2]):

#取并集C_item=frozenset(l1).union(frozenset(l2))flag=True#判断C_item的子集是否在L_keys中foriteminC_item:

#获取C_item的子集subC=C_item-frozenset([item])ifsubCnotinL_keys:#不在flag=Falseifflag==True:C.add(C_item)returnCdefget_L(data_set,k,min_support):#C1较为特殊，先求C1=get_C1(data_set)L1=getLByC(data_set,C1,min_support)support_data={}L=[]L.append(L1)tempL=L1foriinrange(2,k+1):Ci=getCByL(tempL,i)tempL=getLByC(data_set,Ci,min_support)L.append(tempL)forlinL:forkeyinl:support_data[key]=l[key]returnL,support_data#获取关联规则defget_rule(L,support_data,min_support,min_conf):big_rules=[]sub_sets=[]foriinrange(0,len(L)):forfsetinL[i]:forsub_setinsub_sets:ifsub_set.issubset(fset):conf=support_data[fset]/support_data[fset-sub_set]big_rule=(fset-sub_set,sub_set,conf)ifconf>=min_confandbig_rulenotinbig_rules:big_rules.append(big_rule)sub_sets.append(fset)returnbig_rulesif__name__=="__main__":min_support=0.4#最小支持度min_conf=0.6#最小置信度

#获取所有的频繁项集L,support_data=get_L(data_set,3,min_support)

#获取强关联规则big_rule=get_rule(L,support_data,min_support,min_conf)获取强关联规则print('==========所有的频繁项集如下===========')forlinL:forl_iteminl:print(l_item,end='')print('支持度为：%f'%l[l_item])print('===========================================')forruleinbig_rule:print(rule[0],'==>',rule[1],'\t\tconf=',rule[2])程序运行结果如图8.1所示。图8.1例8.2程序运行结果例8.3Apriori算法的Python实现示例。frommlxtend.preprocessingimportTransactionEncoderfrommlxtend.frequent_patternsimportapriorifrommlxtend.frequent_patternsimportassociation_rulesimportpandasaspddf_arr=[['鸡蛋','面包','西红柿','葱','蒜','牛奶'],['面包','牛奶'],['鸡蛋','牛奶','豆角'],['鸡蛋','牛奶','芹菜'],['鸡蛋','西红柿','豆角']]#转换为算法可接受模型(布尔值)te=TransactionEncoder()df_tf=te.fit_transform(df_arr)df=pd.DataFrame(df_tf,columns=te.columns_)#设置支持度求频繁项集frequent_itemsets=apriori(df,min_support=0.4,use_colnames=True)#求关联规则,设置最小置信度为0.15rules=association_rules(frequent_itemsets,metric='confidence',min_threshold=0.6)#设置最小提升度rules=rules.drop(rules[rules.lift<0.6].index)#设置标题索引并打印结果rules.rename(columns={'antecedents':'from','consequents':'to','support':'sup','confidence':'conf'},inplace=True)rules=rules[['from','to','sup','conf','lift']]print(rules)关联规则相关概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1关联规则典型应用场景8.6学习目标4FP-Growth算法FP-GrowthAlgorithm8.4FP-Growth算法Apriori算法在产生频繁项集前需要对事务集进行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大。但是Apriori算法中有一个很重要的性质：频繁项集的所有非空子集都必须也是频繁的。但是Apriori算法在挖掘长频繁模式的时候性能往往低下，韩嘉炜等人在2000年提出了一种称为频繁模式增长（Frequent-PatternGrowth，FP-Growth）方法，将数据集存储在一个特定的称作FP-Tree的结构之后发现频繁项集或频繁项对，即常在一块出现的项的集合FP-Tree。FP-Growth算法比Apriori算法效率更高，在整个算法执行过程中，只需遍历事务集2次，就能够完成频繁模式发现。其发现频繁项集的基本过程如下：(1)构建FP树；(2)从FP树中挖掘频繁项集。FP-Growth算法采用的策略FP-Growth算法采取如下分治策略：将提供频繁项集的事务集压缩到一棵频繁模式树，但仍保留项集关联信息；然后，将这种压缩后的事务集分成一组条件事务集，每个关联一个频繁项，并分别挖掘每个事务集。在算法中使用了一种称为频繁模式树（FrequentPatternTree，FP-Tree）的数据结构。FP-Tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。FP-Growth算法基于以上的结构加快了整个挖掘过程。FP-Tree是将事务集中的各个项按照支持度排序后，把每个事务中的项按降序依次插入到一棵以null为根结点的树中，同时在每个结点处记录该结点出现的支持度。构建FP-TreeFP-growth算法通过构建FP-Tree来压缩事务集中的信息，从而更加有效地产生频繁项集。FP-Tree其实是一棵前缀树，按支持度降序排列，支持度越高的频繁项离根节点越近，从而使得更多的频繁项可以共享前缀。表8.5事务集表8.5表示用于购物篮分析的事务集。其中，a，b，...，p分别表示事务集的项。首先，对该事务集进行一次扫描，计算每一行记录中各个项的支持度，然后按照支持度降序排列，仅保留频繁项集，剔除那些低于支持度阈值的项，这里支持度阈值取3，从而得到<(f:4)，(c:4)，(a:3)，(b:3)，(m:3)，(p:3)>（由于支持度计算公式中的分母|D|是不变的，所以仅需要比较公式中的分子）。表8.5中的第3列展示了排序后的结果。通过下面例子说明FP-Tree的构建过程。事务集如表8.5所示。编号项频繁项集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p构建FP-Tree第一条记录<f，c，a，m，p>对应于FP-Tree中的第一条分支<(f:1)，(c:1)，(a:1)，(m:1)，(p:1)>，如图8.2所示。由于第二条记录<f，c，a，b，m>与第一条记录有相同的前缀<f，c，a>，因此<f，c，a>的支持度分别加1，同时在(a:2)节点下添加节点(b:1)，(m:1)。所以，FP-Tree中的第二条分支是<(f:2)，(c:2)，(a:2)，(h:1)，(m:1)>，如图8.3所示。第三条记录<f，b>与前两条记录相比，只有一个共同前缀<f>，因此，只需要在(f:3)下添加节点<b:1>，如图8.4所示。

图8.2

第一条记录

图8.3

第二条记录

图8.4

第三条记录FP-Tree的根节点为null，不表示任何项。接下来，对事务集进行第二次扫描，从而开始构建FP-Tree：nullf:1c:1a:1m:1p:1f:2a:2m:1p:1c:2b:1m:1nullf:3a:2m:1p:1c:2b:1m:1b:1null构建FP-Tree第四条记录<c，b，p>与之前所有记录都没有共同前缀，因此在根节点下添加节点(c:1)，(b:1)，(p:1)，如图8.5所示。类似地，将第五条记录<f，c，a，m，p>作为FP-Tree的一个分支，更新相关节点的支持度，如图8.6所示。为了便于对整棵树进行遍历，建立一张项的头表（AnItemHeaderTable）。这张表的第一列是按照降序排列的频繁项。第二列是指向该频繁项在FP-Tree中节点位置的指针。FP-Tree中每一个节点还有一个指针，用于指向相同名称的节点，如图8.7所示。

图8.5

第四条记录

图8.6

第五条记录图8.7FP-Tree构建FP-Tree过程：f:3a:2m:1p:1c:2b:1m:1b:1nullc:1p:1b:1f:4a:3m:2p:2c:3b:1m:1b:1nullc:1p:1b:1项头表项结点链f

c

a

b

m

p构建FP-Tree第一遍扫描数据，统计事务集中各项的出现次数，剔除不满足要求的项，剩下的项加入频繁1-项集L，并建立项头表，按出现次数由高到低的顺序排列元素。第二遍扫描数据，对事务集的每个事务，从中选出包含在项头表中的项，将这些项按L的顺序排序。将事务集中每个事务的频繁-1项集插入到FP-Tree中。在插入节点的同时，将各节点索引到项头表，把FP-Tree中相同的节点通过索引链接起来。综上，FP-Tree建立的流程如下：FP-Tree算法描述处理流程：step1：遍历D，得到频繁项候选集L和L中每个项的支持度并删除小于最小支持度的项。对L中的所有频繁项依照支持度的高低降序排列，得到最终的频繁-1项集L；step2：创建一个FP-Tree的根节点Tree，标记为“null”；step3：foreach事务inDdostep4：sortbyorderofL；step5：for频繁项Astep6：调用函数insert_tree(A,Tree)；step7：Endfor输入事务集D，最小支持度SUPmin函数insert_tree()定义如下：insert_tree(A,root)ifroot有孩子节点N且属性与A相等thenN.count++；else创建新节点N；设置各属性；N.node-link索引项头表中对应节点；endif

输出FP-Tree从FP-Tree中挖掘频繁模式在FP-Tree中以

p

结尾的节点链共有两条，分别是<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>和<(c:1)，(b:1)，(p:1)>。其中，第一条节点链表表示项清单<f，c，a，m，p>在事务集中共出现了两次。需要注意到是，尽管<f，c，a>在第一条节点链中出现了3次，单个项<f>出现了4次，但是它们与p一起出现只有2次，所以在条件FP-Tree中将<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>记为<(f:2)，(c:2)，(a:2)，(m:2)，(p:2)>。同理，第二条节点链表示项清单<c，b，p>在事务集中只出现了一次。将p的前缀节点链<(f:2)，(c:2)，(a:2)，(m:2)>和<(c:1)，(b:1)>称为p的条件模式基（conditionalpatternbase）。将p的条件模式基作为新的事务集，每一行存储p的一个前缀节点链，根据前面构建FP-Tree的过程，计算每一行记录中各种项的支持度，然后按照支持度降序排列，仅保留频繁项集，剔除那些低于支持度阈值的项，建立一棵新的FP-Tree，这棵树被称之为p的条件FP-Tree。如图8.8所示。图8.8

p的条件FP-Tree从图8.8可以看到p的条件FP-Tree中满足支持度阈值的只剩下一个节点(c:3)，所以以p结尾的频繁项集有(p:3)，(c:3)。由于c的条件模式基为空，所以不需要构建c的条件FP-Tree。从头表的底部开始挖掘FP-Tree中的频繁模式。nullc:3从FP-Tree中挖掘频繁模式在FP-Tree中以

m

结尾的节点链共有两条，分别是<(f:4)，(c:3)，(a:3)，(m:2)>和<(f:4)，(c:3)，(a:3)，(b:1)，(m:1)>。所以m的条件模式基是<(f:2)，(c:2)，(a:2)>和<(f:1)，(c:1)，(a:1)，(b:1)>。我们将m的条件模式基作为新的事务集，每一行存储m的一个前缀节点链，计算每一行记录中各种项的支持度，然后按照支持度降序排列，仅保留频繁项集，剔除那些低于支持度阈值的项，建立m的条件FP-Tree，如图8.9所示。图8.9

m的条件FP-Tree与p不同，m的条件FP-Tree中有3个节点，所以需要多次递归地挖掘频繁项集mine(<(f:3),(c:3),(a:3)|(m:3)>)。按照<(a:3),(c:3),(f:3)>的顺序递归调用mine(<(f:3),(c:3)|a，m>)，mine(<(f:3)|c,m>)，mine(null|f,m)。由于(m:3)满足支持度阈值要求，所以以m结尾的频繁项集有{(m:3)}。从头表的底部开始挖掘FP-Tree中的频繁模式。项头表项结点链f

c

af:4a:3c:3root从FP-Tree中挖掘频繁模式基于(a,m)的条件模式如图8.10所示。图8.10

节点(a,m)的条件FP-Tree从图8.10可以看出，节点(a,m)的条件FP-Tree有2个节点，需要进一步递归调用mine(<(f:3)|c,a,m>)和mine(<null|f,a,m>)。进一步递归mine(<(f:3)|c,a,m>)生成mine(<null|f,c,a,m>)。因此，以(a,m)结尾的频繁项集有{(am:3)，(fam:3)，(cam:3)，(fcam:3)}。从头表的底部开始挖掘FP-Tree中的频繁模式。c:3f:3root基于(c,m)条件模式如图8.11所示。图8.11节点(c,m)的条件FP-Tree从图8.11可以看出，节点(c,m)的条件FP-Tree只有1个节点，所以只需要递归调用mine(<null|f,c,m>)。因此，以(c,m)结尾的频繁项集有{(cm:3),(fcm:3)}。同理，以(f,m)结尾的频繁项集有{(fm:3)}。f:3root从FP-Tree中挖掘频繁模式在FP-Tree中以

b

结尾的节点链共有三条，分别是<(f:4),(c:3),(a:3),(b:1)>，<(f:4),(b:1)>和<(c:1),(b:1)>。由于节点b的条件模式基<(f:1),(c:1),(a:1)>，<(f:1)>和<(c:1)>都不满足支持度阈值，所以不需要再递归。因此，以b结尾的频繁项集只有(b:3)。同理可得，以a结尾的频繁项集{(fa:3),(ca:3)，(fca:3)，(a:3)}，以c结尾的频繁项集{(fc:3)，(c:4)}，以f结尾的频繁项集{(f:4)}。频繁项的挖掘采用自底向上的顺序，先由项头表的最后的一个节点开始，寻找每一项的条件模式基。根据项头表中各项索引，找出全部含有这个项的前缀路径，对应前缀路径即为这个项的条件模式基。然后依照找出的条件模式基建立条件FP-Tree，对于每一个新建立的条件FP-Tree树，重复上述步骤，直到建立的条件FP-Tree为空，或者只存在唯一路径。若新建立的条件FP-Tree是一个空树，它的前缀就是频繁项；若新建立的条件FP-Tree只存在唯一路径，通过例举全部有可能的组合，然后将这些组合和该树的前缀连接就得到了我们需要的频繁项。从头表的底部开始挖掘FP-Tree中的频繁模式。FP-Tree算法描述处理流程：step1：L=null；step2：if(FP-Tree只包含单个路径P)thenstep3：

foreachX∈Pdostep4：

ComputeX∪L，support(X∪L)=support(X)；step5：

returnL=L∪support>SUPmin的项目集X∪Lstep6：else//包含多个路径step7：

foreach频繁项Yin项头表dostep8：

ComputeX=Y∪L，support(Y∪L)=support(X)；输入FP-Tree，项集L（初值为空），最小支持度SUPminstep9：

ResearPCBofXandcreateFP-Treestep10：

ifTreeX≠Φthenstep11：

递归调用FP-Growth(TreeX,X)step12：

endifstep13：

endforstep14：endif输出LFP-Growth算法的Python实现Sklearn库中没有FP-Growth算法。例8.4FP-Growth算法的Python实现。importreimportcollectionsimportitertoolsdata=[]data=[['a','b','c','d','e','f','g','h'],['a','f','g'],['b','d','e','f','j'],['a','b','d','i','k'],['a','b','e','g'],['g','b']]data=datasupport=3CountItem=collections.defaultdict(int)forlineindata:#统计item的频率foriteminline:CountItem[item]+=1#将dict按照频率从大到小排序,并且删除掉频率过小的项a=sorted(CountItem.items(),key=lambdax:x[1],reverse=True)foriinrange(len(a)):ifa[i][1]<support:a=a[:i]breakforiinrange(len(data)):#更新data中每一笔交易的商品顺序data[i]=[charforcharindata[i]ifCountItem[char]>=support]data[i]=sorted(data[i],key=lambdax:CountItem[x],reverse=True)classnode:#定义节点def__init__(self,val,char):#定义当前的计数self.val=val#定义当前的字符是多少self.char=char#存储孩子self.children={}#链表，链接到另一个孩子处self.next=None#构建条件树时向上搜索

self.father=None#用于链表的时候观察是否已经被访问过了self.visit=0self.nodelink=collections.defaultdict()self.nodelink1=collections.defaultdict()classFPTree():def__init__(self):self.root=node(-1,'root')self.FrequentItem=collections.defaultdict(int)#用来存储频繁项集self.res=[]defBuildTree(self,data):#建立FP树的函数,data以list[list[]]的形式，其中内部的list包含了商品的名称，以字符串表示forlineindata:#取出第一个list，用line来表示root=self.rootforiteminline:#对于列表中的每一项ifitemnotinroot.children.keys():#如果item不在dict中root.children[item]=node(1,item)#创建一个新的节点root.children[item].father=root#用于从下往上寻找else:root.children[item].val+=1#否则，计数加1root=root.children[item]#往下走一步#根据这个root创建链表ifiteminself.root.nodelink.keys():#如果这个item在nodelink中已经存在了ifroot.visit==0:#如果这个点没有被访问过self.root.nodelink1[item].next=rootself.root.nodelink1[item]=self.root.nodelink1[item].nextroot.visit=1#被访问了else:#如果这个item在nodelink中不存在self.root.nodelink[item]=rootself.root.nodelink1[item]=rootroot.visit=1print('树建立完成')returnself.rootdefIsSinglePath(self,root):ifnotroot:returnTrueifnotroot.children:returnTruea=list(root.children.values())iflen(a)>1:returnFalseelse:forvalueinroot.children.values():ifself.IsSinglePath(value)==False:returnFalsereturnTrueFP-Growth算法的Python实现defFP_growth(self,Tree,a,HeadTable):#Tree表示树的根节点，a用列表表示的频繁项集,HeadTable用来表示头表#首先需要判断这个树是不是单路径的，创建一个单路径函数IsSinglePath(root)ifself.IsSinglePath(Tree):#如果是单路径的#对于路径中的每个组合，记作b，产生模式，b并a，support=b中节点的最小支持度root,temp=Tree,[]#创建一个空列表来存储whileroot.children:forchildinroot.children.values():temp.append((child.char,child.val))root=childans=[]#产生每个组合foriinrange(1,len(temp)+1):ans+=list(binations(temp,i))foriteminans:mychar=[char[0]forcharinitem]+amycount=min([count[1]forcountinitem])ifmycount>=support:self.res.append([mychar,mycount])else:#不是单路径，存在多个路径root=Tree#对于root头表中的每一项进行操作HeadTable.reverse()#首先将头表逆序for(child,count)inHeadTable:#child表示字符，count表示支持度b=[child]+a#新的频繁模式#构造b的条件模式基self.res.append([b,count])tmp=Tree.nodelink[child]#此时为第一个节点从这个节点开始找,tmp一直保持在链表当中data=[]#用来保存条件模式基whiletmp:#当tmp一直存在的时候tmpup=tmp#准备向上走res=[[],tmpup.val]#用来保存条件模式whiletmpup.father:res[0].append(tmpup.char)tmpup=tmpup.fatherres[0]=res[0][::-1]#逆序data.append(res)#条件模式基保存完毕tmp=tmp.nextFP-Growth算法的Python实现#条件模式基构造完毕，储存在data中，下一步是建立b的fp-TreeCountItem=collections.defaultdict(int)#统计词频for[tmp,count]indata:foriintmp[:-1]:CountItem[i]+=countforiinrange(len(data)):data[i][0]=[charforcharindata[i][0]ifCountItem[char]>=support]#删除掉不符合的项data[i][0]=sorted(data[i][0],key=lambdax:CountItem[x],reverse=True)#排序#此时数据已经准备好了，我们需要做的就是构造条件树root=node(-1,'root')#创建根节点，值为-1，字符为rootfor[tmp,count]indata:#item是[list[],count]的形式tmproot=root#定位到根节点foritemintmp:#对于tmp中的每一个商品ifitemintmproot.children.keys():#如果这个商品已经在tmproot的孩子中了tmproot.children[item].val+=count#更新值else:#如果这个商品没有在tmproot的孩子中tmproot.children[item]=node(count,item)#创建一个新的节点tmproot.children[item].father=tmproot#方便从下往上找tmproot=tmproot.children[item]#往下走一步#根据这个root创建链表ifiteminroot.nodelink.keys():#这个item在nodelink中存在iftmproot.visit==0:root.nodelink1[item].next=tmprootroot.nodelink1[item]=root.nodelink1[item].nexttmproot.visit=1else:#这个item在nodelink中不存在root.nodelink[item]=tmprootroot.nodelink1[item]=tmproottmproot.visit=1ifroot:#如果新的条件树不为空NewHeadTable=sorted(CountItem.items(),key=lambdax:x[1],reverse=True)foriinrange(len(NewHeadTable)):ifNewHeadTable[i][1]<support:NewHeadTable=NewHeadTable[:i]breakself.FP_growth(root,b,NewHeadTable)#我们需要创建新的headtable#成功返回条件树FP-Growth算法的Python实现defPrintTree(self,root):#层次遍历打印树ifnotroot:returnres=[]ifroot.children:for(name,child)inroot.children.items():res+=[name+''+str(child.val),self.PrintTree(child)]returnreselse:returnobj=FPTree()root=obj.BuildTree(data)obj.FP_growth(root,[],a)print(obj.res)程序运行结果如图8.12所示。图8.12

例8.4程序运行结果

FP-Growth算法的Python实现关联规则相关概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1关联规则典型应用场景8.6学习目标5Eclat算法EclatAlgorithm8.5Eclat

算法概述Eclat算法是由Zaki博士2000年提出的，它利用数据库和垂直数据格式，采用前缀等价关系划分搜索空间，该算法只需要1次扫描数据库，利用数据垂直表示形式的优势通过交叉计数来计算支持度，能够高效地挖掘出频繁集。Apriori算法和FP-Growth算法都是从项集格式{TID:itemset}的事务集中挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品。这种数据格式称为水平数据格式。数据也可以用项-TID集格式{item:TID_set}表示，其中item是项的名称，而TID_set是包含item的事务标识符的集合，这种数据格式称为垂直数据格式。Eclat算法是一种深度优先算法,采用垂直数据表示形式。例8.5假设事务集合D如表8.6所示。假设用户的最小支持数为2。表8.6事务集合DEclat算法生成频繁项集。(1)水平格式转换成垂直格式，并通过转换后的倒排表可以加快频繁集生成速度。如表8.7所示。表8.7D垂直格式倒排表(2)候选1-项集如表8.8所示。表8.8候选-1项集由于最小支持数为2，则候选-1项集中都是频繁-1项集。(3)由频繁-1项集生成的候选-2项集。通过取每对频繁项的TID集的交，可以在该数据集上进行挖掘。设最小支持度计数为2。由于表8.8中的每个项都是频繁的，因此总共进行10次交运算，导致8个非空2项集，如表8.9所示。表8.9候选-2项集注意，项集｛A,D｝和{C,E}都只包含一个事务，因此它们都不属于频繁2项集的集合。(4)由频繁-2项集生成的候选3-项集。根据先验性质，一个给定的3项集是候选3项集，仅当它的每一个2项集子集都是频繁的。这里候选产生过程将产生3个候选3-项集：｛A，B,C｝，｛A,B,D｝和{A,B,E}。通过取这些候选3项集任意对应2项集的TID集的交，得到表8.10，其中只有两个频繁3项集：｛A,B,C:2｝和｛A,B,E:2｝。表8.10候选3-项集TIDItem

TIDItemT1A,E,BT6C,BT2D,BT7A,CT3C,BT8A,E,C,BT4A,D,B

T9A,C,BT5A,C

ItemTID

ItemTIDAT1,T4,T5,T7,T8,T9DT2,T4BT1,T2,T3,T4,T6,T8,T9ET1,T8CT3,T5,T6,T7,T8,T9

ItemFreq

ItemFreqA6D2B7E2C6

Item子事务集Freq

Item子事务集FreqAB{T1,T4,T8,T9}4BD{T2,T4}2AC{T5,T7,T8,T9}4BE{T1,T8}2AD{T4}1CD{}0AE{T1,T8}2CE{T8}1BC{T3,T6,T8,T9}4DE{}0Item子事务集Freq

Item子事务集FreqABC{T8,T9}2ABE{T1,T8}2ABD{T4}1

Eclat

算法描述处理流程：step1：通过扫描一次数据集D，把水平格式的数据转换成垂直格式的TID集；step2：项集的支持度计数简单地等于项集的TID集长度；step3：从k=1开始，可以根据先验性质，使用频繁k-项集来构造候选(k+1)-项集；step4：通过取频繁k项集的TID集的交，计算对应的(k+1)-项集的TID集；step5：重复该过程，每次k增加1，直到不能再找到频繁项集或候选项集。输入数据集D，最小支持度阈值minS_port输出频繁项集Eclat算法除了在产生候选(k+1)-项集时利用先验性质外，另一个优点是不需要扫描数据库来确定(k+1)-项集的支持度（k≥1），这是因为每个k项集的TID集携带了计算支持度的完整信息。然而，TID集可能很长，需要大量的内存空间，长集合的交运算还需要大量的计算时间。例8.6Eclat算法的Python实现。importnumpyasnpfromitertoolsimportcombinationsdefread_data():dataset=[['牛奶','葱','豆角','土豆','鸡蛋','芹菜'],['苹果','葱','豆角','土豆','鸡蛋','芹菜'],['牛奶','苹果','土豆','鸡蛋'],['牛奶','芒果','白菜','土豆','芹菜'],['白菜','葱','芹菜','土豆','芒果','鸡蛋']]returndatasetEclat

算法的Python实现#eclat算法defeclat(transactions,min_support=0.35):combos_to_counts={}fortransactionintransactions:#变量交易记录goods=list(np.unique(transaction))#获取商品列表length=len(goods)forkinrange(2,length+1):k_combos=list(combinations(goods,k))