关联分析与频繁模式挖掘

第十一讲关联规则邓志鸿北京大学信息科学技术学院2016年6月内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估关联规则1993年SIGMOD大会上Agrawal等人首次提出关联规则挖掘(associationrulemining)目的：发现数据中内在的规律性人们通常会同时购买什么样的商品？—Beeranddiapers?购买微机后，接下来用户通常会有什么购物行为？哪种DNA对某个新药敏感？应用Basketdataanalysis,cross-marketing,catalogdesign,salecampaignanalysis,Weblog(clickstream)analysis,andDNAsequenceanalysis.核心任务频繁模式(Frequentpattern)在数据集（库）中频繁出现的模式（项集(asetofitems)、子序列(subsequences)、子结构(substructures)等）。内容简介基本概念频繁模式挖掘基本方法基本内容频繁模式挖掘关联规则生成模式评估基本概念AssociationRuleAnalysis给定事务集合，根据某些项的出现来预测其它项的出现Market-BaskettransactionsExampleofAssociationRules{Diaper}{Beer},

{Milk,Bread}{Eggs,Coke},

{Beer,Bread}{Milk},隐含着内在关联，而非偶然现象基本概念项(Item)最小的处理单位例如：Bread,Milk事务(Transaction)由事务号和项集组成例如：<1,{Bread,Milk}>事务数据库由多个事务组成项集(Itemset)一个或多个项(item)的集例如：{Milk,Bread,Diaper}k-项集(k-itemset)包含k个项的集合基本概念包含关系令T为一事务，P为一项集。称T包含P，如果P是T的子集记T

P或P

T支持度计数(Supportcount)事务数据库中包含某个项集的事务的个数例如：({Milk,Bread,Diaper})=2支持度(Support)事务数据库中包含某个项集的事务占事务总数的比例。例如：s({Milk,Bread,Diaper})=2/5频繁项集(FrequentItemset)令P为任何一个项集，称P为频繁项集，如果P的支持度不小于指定的最小阈值(minsupthreshold)基本概念Example:关联规则(AssociationRule)表达形式：XY(s,c)其中，X和Y都是项集，s是规则的支持度，c是置信度例子：

{Milk,Diaper}{Beer}

(0.4,0.67)规则评估度量指标支持度－Support(s)同时包含X和Y的事务占事务总数的比例置信度－Confidence(c)在所有包含X的事务中包含Y的事务所占比例内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估关联规则分析－内容给定一个事务数据库TD，关联规则挖掘的目标是要找到所有支持度和置信度都不小于指定阈值的规则。

支持度≥minsupthreshold置信度≥minconfthreshold穷举法(Brute-forceapproach)列出所有可能的规则对每条规则计算其支持度和置信度通过阈值minsup

和minconf

过滤无效规则可计算性？计算复杂性分析给定d个不同项：项集数目等于2d所有可能的关联规则总数等于：

如果d=6则R=602关联规则－分析ExampleofRules:

{Milk,Diaper}{Beer}(s=0.4,c=0.67)

{Milk,Beer}{Diaper}(s=0.4,c=1.0){Diaper,Beer}{Milk}(s=0.4,c=0.67){Beer}{Milk,Diaper}(s=0.4,c=0.67)

{Diaper}{Milk,Beer}(s=0.4,c=0.5){Milk}{Diaper,Beer}(s=0.4,c=0.5)思考

所有规则都对应于把同一项集分成两个部分

{Milk,Diaper,Beer}

源自同一项集的规则有相同的支持度，但是置信度不同因此，我们可以分别处理对支持度和置信度的要求XYs=s(XY)/|DB|,c=s(XY)/s(X)关联规则分析分两步执行：

挖掘频繁项集－生成所有支持度

minsup的项集构造规则－用每个频繁项集生成高置信度的规则－对频繁模式的每次分割（一分为二）就形成一条规则，再判断该规则是否满足最小置信度阈值条件。但是，挖掘频繁模式仍然是一个“计算昂贵”的工作。{Milk,Diaper,Beer}s=0.4{Milk}s=0.8{Milk}{Diaper,Beer}s=0.4,c=0.4/0.8=0.5关联规则分析的核心内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估频繁模式挖掘－重要性发现数据集中的有价值的重要性质是其它数据挖掘任务的基础关联分析：Associationrulesanalysis

MiningFrequentItemset因果分析：causalityanalysis序列、结构模式：Sequential,structural(e.g.,sub-graph)patterns时空、多媒体、时间序列、流数据模式分析分类聚类数据仓库语义数据压缩推荐系统等其他应用生成频繁项集给定d个项，有2d

个可能的候选项集生成频繁项集穷举法(Brute-forceapproach)网格中每个项集都是候选的频繁项集通过扫描一次数据库，可以得到每个候选项集的支持度比较每一条事务和每个候选项集计算复杂度－O(NMw)N为事务数目，M=2d

为候选项集，w为一次比较的计算代价内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估频繁项集挖掘算法Apriori算法第一个算法用了Apriori性质所有挖掘算法的基础基于事务列表的算法Eclat算法基于节点列表的算法PPV算法、Prepost算法Apriori算法候选－生成类型Apriori性质反单调性基本思想由长度为k的频繁模式生成长度为(k+1)的候选模式计算长度为(k+1)的候选模式的支持度，从而获得长度为(k+1)的频繁模式Aprioir算法Apriori性质:如果一个项集是频繁的，那么它的所有子集都是频繁的。也称为反单调性Apriori性质成立的原因如下：任何一个项集的支持度不可能超过其子集的支持度发现不频繁Apriori性质－演示裁减所有超集Apriori算法－示例1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2Supmin=2Apriori算法－（伪码）描述Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for

(k=1;Lk!=

;k++)dobegin

Ck+1=candidatesgeneratedfromLk;

foreachtransactiontindatabasedo

incrementthecountofallcandidatesinCk+1thatarecontainedint

Lk+1=candidatesinCk+1withsupport

min_support

endreturn

k

Lk;Apriori算法－重要细节如何生成候选项集？Step1:自连接(self-joining)LkStep2:裁减(pruning)如何计算候选项集的支持度？例子L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3由abc

和abd生成abcd由acd和ace生成acde

Pruning:因为ade不在L3中，所以不用处理acde（它不可能是频繁项集）C4={abcd}Apriori算法－生成候选项集SupposetheitemsinLk-1arelistedinanorderStep1:self-joiningLk-1

insertinto

Ckselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1Step2:pruningForallitemsetscinCk

doForall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCkApriori算法在构造候选k-项集的时候利用了频繁k-1项集进行裁减，有效地降低了候选项集的数量。但是这个方法对生成候选2-项集基本上没有太大作用。令频繁1-项集个数为n，则候选2-项集个数为n(n-1)/2基本方法第一次扫描事务数据库时计算2-项集的支持度，从而直接获得频繁2-项集Apriori算法－减少候选项集数目Apriori算法－直接挖掘频繁2-项集很多实验表明，在Apriori算法（或基于Apriori的算法）频繁模式挖掘过程中，频繁2-项集的查找最费时间频繁1-项集很多，所以候选2-项集就非常多方法在扫描事务数据库时，同时计算每个事务所包含2-项集的支持度。第一次扫描数据库，同时找到频繁1-项集和频繁2-项集发现频繁2-项集－示例TidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{E}3Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2A,C,D{A,C},{A,D},

{C,D}B,C,E

{B,C},{B,E},

{C,E}…频繁项集挖掘算法Apriori算法第一个算法用了Apriori性质所有挖掘算法的基础基于事务列表的算法Eclat算法基于节点列表的算法PPV算法、Prepost算法Eclat算法Apriori算法主要缺点多次扫描数据库，候选项集支持度计算代价高垂直数据表示(verticaldataformat)TidsetTidset令P为一个项集，其Tidset定义如下：Tidset(P)={t.Tid|P

t}性质1：P的支持度等于Tidset(P)势（包含元素的个数）性质2：令Sk={Tidset(P)

|

P是频繁k-项集}，则对任何C

Ck+1(候选k+1项集)，Tidset(C)可由Sk中的两个元素Tidset(X)和Tidset(Y)得到，并且Tidset(C)＝Tidset(X)

Tidset(Y)X＝C[1]C[2]…C[k-1]C[k]

Y＝C[1]C[2]…C[k-1]C[k+1]

Eclat算法思想与Apriori基本一致，只不过在获取候选项集的Tidset直接用两个频繁项集的Tidset的交。而候选项集的支持度就直接等于|Tidset|垂直数据表示Eclat算法–

示例1234561345AC2456D1356TW123451345451351345ACADATAW245613561234556245135CDCTCWDTDWTW1351345135135245135ACTACWATWCDWCTWACTWMinsup=3频繁项集挖掘算法Apriori算法第一个算法用了Apriori性质所有挖掘算法的基础基于事务列表的算法Eclat算法基于节点列表的算法PPV算法、Prepost算法基于节点列表的频繁模式挖掘算法垂直算法（如Eclat）简单、易实现时间效率对稠密数据而言，较差对稀疏数据而言，较好FP-Growth算法复杂、不易实现时间效率高对稠密数据而言，好对稀疏数据而言，一般Question是否可以设计一个算法，同时具有垂直算法简单、易实现，而又具有较高效率的特点。分析Eclat优点采用垂直数据格式，使得计算项集的支持度变得简单。候选项集的Tidset直接由两个频繁项集的Tidset的交获取。而候选项集的支持度就等于|Tidset|。问题Tidset是否足够简洁和压缩。在分布不变的情况下，与数据库的大小呈线性关系。FP-Growth优点采用压缩的FP-tree结构，使得搜索空间极大地缩小问题重复递归构造FP-tree费时费力复杂，对编程技能要求高分析－示例－TidsetTrans-idItemsbought1C,A2B,C,E3B,C,E,A4B,E5D,FTidsetA:1,3B:2,3,4C:1,2,3D:5E:2,3,4F:5表1分析－示例－TidsetTrans-idItemsbought1C,A2B,C,E3B,C,E,A4B,E5D,F6C,A7B,C,E8B,C,E,A9B,E10D,F……500D,FTidsetA:1,3,6,8,…,496,498B:2,3,4,7,8,9,…,497,498,499C:1,2,3,6,7,8…,496,497,498D:5,10,…,500F:5,10,…500表1数据重复100次表2E:2,3,4,7,8,9,…,497,498,499分析－示例－Tidset显然，对给定的阈值，表1和表2所包含的频繁项集是一样的，且这些频繁项集的支持度是一样的。但是，如果采用Eclat算法，挖掘表2中频繁项集的时间是挖掘表1中频繁项集的时间的100倍似乎很不合理分析－示例－FP-TreeTrans-idItemsbought1C,A2B,C,E3B,C,E,A4B,E5D,F表1{}C:1B:3C:2E:2A:1A:1E:1D:1F:1BCEADF分析－示例－FP-Tree表2{}C:100B:300C:200E:200A:100A:100E:100D:100F:100BCEADFTrans-idItemsbought1C,A2B,C,E3B,C,E,A4B,E5D,F6C,A7B,C,E8B,C,E,A9B,E10D,F……500D,FFP-Tree的结构基本上没有变化，只不过每个节点上的计数值增加了100倍分析－发现{}C:1B:3C:2E:2A:1A:1E:1D:1F:1BCEADFN2

N1

N3

N4

N5

N6

N7

N8

N9

A.support=2CA.support=2N2.count=1N6.count=1C.support=3N1.count=1N4.count=2N2.count=1N6.count=1CA的support等于所有如下节点的count值之和：(1)该节点的lable为A(2)该节点的祖先节点中有标签为C的节点是一个普遍的结论，是节点编码的基础基于节点列表的算法每个项或项集都由节点列表表示。为了有效表达节点之间的包含关系，需要对节点进行编码杜威编码前后序编码CA

N2,N6

杜威编码方法缺点编码的大小与树的深度成正比，且与树的宽度有关系。存储代价高包含关系的判断与树深度相关，效率不高能否解决呢？可以，采用树的前后序编码{}C:100B:300C:200E:200A:100A:100E:100D:100F:1001.1.11.11.2.11.21.311.2.21.3.1.11.2.1是.1的前缀，所以编码为1.2.1的节点是编码为.1的节点的祖先树的前后序编码给定一个树，每个节点N对应一个二元组（Npre,Npost）。Npre代表按前序遍历树（深度优先）时访问到节点N时的编号（序号），Npost代表按后序遍历（深度优先）树时访问到节点N时的编号（序号）。前后序编码的性质性质0：X,Y是两个节点，X是Y的祖先节点，当且仅当Xpre<Ypre

并且Xpost>Ypost前后序编码－例子RACDFBERACDFBERACDFBE前序次序先根次序后序次序后根次序RABCDFE11234567BAFDECR1234567RACDFBE(1,7)(2,2)(3,1)(4,6)(5,5)(6,3)(7,5)基本概念－PPC-treePPC-tree类似与FP-tree的一棵前缀树（项按照支持度排序）每个节点都有一对<前序编号,后序编号>{}C:1B:3C:2E:2A:1A:1E:1D:1F:1(1,10)(2,2)(3,1)(4,7)(5,5)(6,4)(7,3)(8,6)(10,8)(9,9)N2

N1

N3

N4

N5

N6

N7

N8

N9

Trans-idItemsbought1C,A2B,C,E3B,C,E,A4B,E5D,F表1基本概念－PP-code对PPC-tree中的每个节点N，称<(N.pre-order,N.post-order):count>为节点N的PP-code。例如：节点N1的PP-code是<(2,2):1>节点N2的PP-code是<(3,1):1>Node-list定义Node-list：一种节点列表的表示形式1-itemset(1-项集)的Node-list给定PPC-tree树，1-itemseti

的Node-list定义为序列序列由PPC-tree树中节点标签(label)为i的所有节点的PP-code组成。PP-code在序列中的位置按照节点前序序号排列C的Node-list为{<(2,2):1>,<(5,5):2>}A的Node-list为{<(3,1):1>,<(7,3):1>}Node-list定义约定：所有项的总集I={i1,i2,…,iN}按照项的支持度降序排列的序列。对任何0

s

tN，记is

it。约定：任何项集中的项按其在I中的序排列2-itemset(2-项集)的Node-list给定两个1项集i1andi2(i1

i2)，他们的Node-list分别为{<(x11,y11):z11>,<(x12,y12):z12>,…,<(x1m,y1m):z1m>}和{<(x21,y21):z21>,<(x22,y22):z22>,…,<(x2n,y2n):z2n>}。2项集i1i2的Node-list定义如下令<(x2q,y2q):z2q>是i2的Node-list中的一个元素，如果存在<(x1p,y1p):z1p>∈i1的Node-list，满足<(x1p,y1p):z1p>是<(x2q,y2q):z2q>的祖先，则<(x2q,y2q):z2q>属于i1i2的Node-list.i1i2的Node-list中的元素按照节点的前序序号排列。Node-list定义C的Node-list为{<(2,2):1>,<(5,5):2>}A的Node-list为{<(3,1):1>,<(7,3):1>}故，CA的Node-list为{<(3,1):1>,<(7,3):1>}2<3

2>1，故<(2,2):1>是<(3,1):1>的祖先节点，故<(3,1):1>属于CA的Node-list5<7

5>3，故<(5,5):2>是<(7,3):1>的祖先节点，故<(7,3):1>属于CA的Node-listNode-list定义k-itemset(k-项集)的Node-list令P

=i1

i2…i(k-2)

ixiy

(k

3)是一k-项集，P1=i1

i2…i(k-2)ix的Node-list是{<(xP11,yP11):z

P11>,<(x

P12,y

P12):z

P12>,…,<(x

P1m,y

P1m):z

P1m>}，P2=i1

i2…i(k-2)iy的Node-list是{<(xP21,y

P21):z

P21>,<(x

P22,y

P22):z

P22>,…,<(x

P2n,y

P2n):z

P2n>}，则P

的Node-list定义如下：令<(x2q,y2q):z2q>是P2的Node-list中的一个元素，如果存在<(x1p,y1p):z1p>∈P1的Node-list，满足<(x1p,y1p):z1p>是<(x2q,y2q):z2q>的祖先，则<(x2q,y2q):z2q>属于P的Node-list.P的Node-list中的元素按照节点的前序序号排列。Node-list定义CA的Node-list为{<(3,1):1>,<(7,3):1>}CE的Node-list为{<(6,4):2>}CEA的Node-list为{<(7,3):1>}6<7

4>3，故<(6,4):2>是<(7,3):1>的祖先节点，故<(7,3):1>属于CEA的N-list3<6，故<(6,4):2>不是<(3,1):1>的祖先节点，CE中只有一个元素<(6,4):2>，所以不存在元素是<(3,1):1>的祖先节点，故<(3,1):1>不属于CEA的N-listNode-list－现象C的Node-list为{<(2,2):1>,<(5,5):2>}1+2=3=C.supportE的Node-list为{<(6,4):2>,<(8,6):1>}2+1=3=E.supportA的Node-list为{<(3,1):1>,<(7,3):1>}1+1=2=A.supportCA的Node-list为{<(3,1):1>,<(7,3):1>}1+1=2=CA.supportCE的Node-list为{<(6,4):2>}2=CE.supportCEA的Node-list为{<(7,3):1>}1=CEA.supportNode-list的重要性质－1性质1：令k-项集P=i1

i2…ik的Node-list为{<(x1,y1):z1>,{<(x2,y2):z2>,…,<({<(xm,ym):zm>},有P.support=

z1+z2+…+zm证明按照前缀树PPC-tree的构造，P

的Node-list中的节点记录了项集i1

i2…ik在数据库中出现的次数。详细证明见：ZhihongDengandZhonghuiWang.ANewFastVerticalMethodforMiningFrequentPatterns.InternationalJournalofComputationalIntelligenceSystems,3(6):733–744,2010.下载网址：/faculty/system/dengzhihong/dengzhihong.htm基于Node-list的挖掘算法Scantransactiondatabaseandidentifyallfrequent1-items.Then,ConstructPPC-tree.BasedonPPC-tree,constructtheN-listofeachfrequent1-itemsDothealmostsameproceduresasApriorialgorithmObtaintheNode-listsofcandidate(k+1)-itemsetsbyintersectingfrequentk-itemsetsbythedefinitionofNode-lists.BasedontheNode-listsofcandidate(k+1)-itemsets,Obtaintheirsupports.Getthefrequent(k+1)-itemsetsbyfilteringthosecandidate(k+1)-itemsetswhosesupportislessthanthegivensupportthreshold.基于Node-list的挖掘算法－效率由算法描述可知，由k-项集的Node-list生成(k+1)-项集的Node-list的时间是决定算法效率的关键所。令P1=i1

i2…i(k-2)ix的Node-list是{<(xP11,yP11):z

P11>,<(x

P12,y

P12):z

P12>,…,<(x

P1m,y

P1m):z

P1m>}，P2=i1

i2…i(k-2)iy的Node-list是{<(xP21,y

P21):z

P21>,<(x

P22,y

P22):z

P22>,…,<(x

P2n,y

P2n):z

P2n>}，其中ix

iy。我们要生成P

=i1

i2…i(k-2)

ixiy

的Node-list根据定义，对P2的Node-list中的每一个元素<(x

P2i,y

P2i):z

P2i>,，必须检查P1的Node-list中是否存在某个元素，该元素是<(x

P2i,y

P2i):z

P2i>,的祖先。如果存在，则把<(x

P2i,y

P2i):z

P2i>加入到P的Node-list中，否则不加入。一个直观的做法：对P2的Node-list中每个元素，都与P1的Node-list中元素进行祖先－后代关系的检查，其算法复杂都为O(m*n)是否有更为高效的方法呢？Yes,有O(m+n)的方法Node-list的重要性质－2设P为1-项集，令其Node-list为：{<(xP1,yP1):z

P1>,<(x

P2,y

P2):z

P2>,…,<(x

Pk,y

Pk):z

Pk>}，性质2对任何i,j

{1,2,…k)，且i

j有xPi

xPj

yPi

yPjC的Node-list为{<(2,2):1>,<(5,5):2>}E的Node-list为{<(6,4):2>,<(8,6):1>}A的Node-list为{<(3,1):1>,<(7,3):1>}Node-list的重要性质－3性质3：令P1=i1

i2…i(k-2)ix的Node-list是{<(xP11,yP11):z

P11>,<(x

P12,y

P12):z

P12>,…,<(x

P1m,y

P1m):z

P1m>}，P2=i1

i2…i(k-2)iy的Node-list是{<(xP21,y

P21):z

P21>,<(x

P22,y

P22):z

P22>,…,<(x

P2n,y

P2n):z

P2n>}，其中ix

iy。如果xP1s

x

P2t，则对任何s

k

m，1

v

t成立x

P1k

x

P2v

x

P1k

xP1s

x

P2t

x

P2v

性质3说明<(x

P2v,y

P2v):z

P2v>不可能{<(xP1k,yP1k):z

P1k>的子孙节点。Node-list的高效生成算法简记P1的Node-list为{p11,p12,…,p1m}，P2的Node-list为{p21,p22,…,p2n}。其中p1i=<(xP1i,yP1i):z

P1i>,p2j=<(xP2j,yP2j):z

P2j>，由

P1和P2的生成的k-项集记为P先看p11如果对所有的p2i

{p21,p22,,…,p2v}都成立

xP11

xP2i，则由性质0可知，P2中的所有元素都不可能是p11的子孙。另外，由性质2可知xP1k

xP11(1<k)。可知P2中的所有元素都不可能是p1k的子孙。因此终止处理，输出P的Node-list。否则存在p2k，满足xP11

<

xP2k，又分以下两种情况yP11

>

yP2k

：表明p2k是p11的子孙，把p2k插入P的Node-list中。继续比较p11和p2(k+1)。yP11

<

yP2k：表明p2k不是p11的子孙。由性质2可知对任何j>k,yP11

<

yP2k

<yP2j，因此p2j也不可能是p11的子孙。因此，不需要继续比较p11和p2j(j>k)。这时，对p11处理结束，转而比较p12和P2中的元素。因为对任何s<k,p2s

要么是p11的子孙，要么其前序序号xP2s<xP11。对第一中情况，p2s

不可能是p12的子孙。否则p11和p12有祖孙关系，因为p11和p12的标签一样，所以根据树的构造算法这是不可能。对第二种情况，xP2s<xP11，而xP11<

xP12。有xP2s<xP12。故p2s

不可能是p12的子孙。由上分析，p2s不可能是p12的子孙。所以对p12的比较，从p2k开始。对p12的处理同p11。这样处理的方式避免了p12与P2中已经和p11比较过的元素（p2k除外）再进行比较，从而实现线性时间复杂度O(n+m)。Node-list的高效生成算法－示例(1,25)(2,12)(3,4)(4,2)(6,3)(5,1)(7,8)(11,11)(8,5)(9,7)(10,6)(12,9)(13,10)(14,24)(15,15)(16,13)(17,14)(18,19)(22,23)(19,17)(21,18)(23,21)(25,22)(20,16)(24,20)Thenode-listofi1i2Thenode-listofi1i3Node-list的高效合并算法－示例i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}假设i2>i3第1步检测祖孙关系7>5,所以节点(7,8)不可能是节点(5,1)的祖先。因此第2步就要考察(7,8)和(8,5)的关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}i1i2i3={}Node-list的高效合并算法－示例第2步检测祖孙关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}7<8,8>5。所以节点(7,8)

是节点(8,5)的祖先。故把<(8,5):

2>输入到i1i2i3

的Node-list中。第三步，检测(7,8)

与节点(10,6)的祖孙关系i1i2i3={<(8,5):

2>}添加Node-list的高效合并算法－示例第3步检测祖孙关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}7<10,8>6。所以节点(7,8)

是节点(10,6)的祖先。故把<(10,6):

2>输入到i1i2i3

的Node-list中。第四步，检测(7,8)

与节点(18,19)的祖孙关系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}添加Node-list的高效合并算法－示例第4步检测祖孙关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}7<18,但8<19。所以节点(7,8)

不是节点(18,19)的祖先。由于节点(18,19)后面的节点后序编码都大于19，所以节点(7,8)

也不可能是(18,19)后面节点的祖先。因此，不需要检测(7,8)

与(18,19)后面节点的祖孙关系。即i1i3节点列表中所有是节点(7,8)

子孙的节点都已经找到。所以停止节点(7,8)与其它节点祖孙关系的检测。故第五步，检测(7,8)后续节点<(15,15):

6>是否与i1i3节点列表中的元素有祖孙关系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}Node-list的高效合并算法－示例第5步检测祖孙关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}其实不需要检测(15,15)与(18,19)前面节点的祖孙关系。因为(18,19)前面节点要么是(7,8)的子孙，要么其前序序号小于7。如果是(7,8)的子孙，就不可能是(15,15)的子孙（否则(7，8)和(15,15)之间有祖孙关系。这是可能的，因为它们的标签一样）。如果前序序号小于7，则必然小于(7,8)后续节点的前序序号，故也不可能是(15,15)的子孙。这就意味着(18,19)前面的节点不可能是(15,15)的子孙。因此第5步直接比较(15,15)与(18,19)的祖孙关系。虽然15<

18

，但15<

19。故(15,15)不是(18,19)的祖先。由于(18,19)后续节点的后序编码均大于19。所以(15,15)也不可是(18,19)后续节点的祖先。故，终止(15,15)与其它节点的祖孙关系的检测。第6步检测检测(15,15)后续节点<(23,21):

6>是否与i1i3节点列表中的元素有祖孙关系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}Node-list的高效合并算法－示例第6步检测祖孙关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}与第五步一样，不需要检测(23,21)与(18,19)前面节点的祖孙关系，而是直接比较(23,21)与(18,19)的祖孙关系。因为23>

18

，所以(23,21)不是(18,19)的祖先。第7步要继续检测(23,21)与(18,19)后续节点(24,20)的祖孙关系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}Node-list的高效合并算法－示例第7步检测祖孙关系i1i2={<(7,8):10>,<(15,15):

6>,<(23,21):

7>}i1i3={<(5,1):3>,<(8,5):

2>,<(10,6):

2>,<(18,19):

6>,<(24,20):

5>}因为23<

24,21>

20，故(23,21)是

(24,20)的祖先。把<(24,20):

5>输入到i1i2i3

的Node-list中。i1i3节点链表没有可处理的节点，整个操作结束，得到了i1i2i3

的Node-list。i1i2i3={<(8,5):

2>,<(10,6):

2>,<(24,20):

5>

}添加PPV性能比较在稠密数据库上与FP-growth相当在稀疏数据库上表现优秀仍然受制于候选-生成模式的限制基于节点列表方法－N-list约定：所有项的总集I={i1,i2,…,iN}按照项的支持度降序排列的序列。对任何0

s

tN，记is

it。约定：任何项集中的项按其在I中的序排列1-itemset(1-项集)的N-list同其Node-list2-itemset(2-项集)的N-list定义如下给定两个1项集i1andi2(i1

i2)，他们的N-list分别为{<(x11,y11):z11>,<(x12,y12):z12>,…,<(x1m,y1m):z1m>}和{<(x21,y21):z21>,<(x22,y22):z22>,…,<(x2n,y2n):z2n>}。2项集i1i2的Node-list定义如下令<(x2q,y2q):z2q>是i2的Node-list中的一个元素，如果存在<(x1p,y1p):z1p>∈i1的Node-list，满足<(x1p,y1p):z1p>是<(x2q,y2q):z2q>的祖先，则<(x1p,y1p):z2q>属于i1i2的Node-list.i1i2的Node-list中的元素按照节点的前序序号排列。基于节点列表方法－N-listtheN-listofk-itemset

LetP=ixiyik-2

…i2i1beaitemset(k

3),theN-listofP1=ixik-2

…i2i1be{<(x11,y11):z11>,<(x12,y12):z12>,…,<(x1m,y1m):z1m>},andtheN-listofP2=iyik-2

…i2i1be{<(x21,y21):z21>,<(x22,y22):z22>,…,<(x2n,y2n):z2n>}.TheN-listofPisasequenceofPP-codesaccordingtopre-orderascendingorderandgeneratedbyintersectingtheN-listsofP1andP2,whichfollowstherulebelow:First,forany<(x1p,y1p):z1p>∈theN-listofP1

(1≤p≤m)and<(x2q,y2q):z2q>∈theN-listofP2

(1≤q≤n),if<(x1p,y1p):z1p>isanancestorof<(x2q,y2q):z2q>,then<(x1p,y1p):z2q>isaddedtotheN-listofP.Afterthat,wegetaninitialN-listofP.Second,wechecktheinitialN-listofPagainandmergethenodeswiththeformof<(x1b,y1b):z1b><(x1b,y1b):z2b><(x1b,y1b):zrb>togetanewnode<(x1b,y1b):

(z1b+z2b...+zrb)>.N-list示例B的N-list为{<(4,7):1>,A的N-list为{<(3,1):1>,<(7,3):1>}C的N-list为{<(2,2):1>,<(5,5):2>}A的N-list为{<(3,1):1>,<(7,3):1>}BA的N-list为{<(4,7):1>CA的N-list为{<(2,2):1>,<(5,5):1>}BCA的N-list为{<(4,7):1>N-list性质N-list具有Node-list的所有性质。除此之外，N-list还具有单路径性质(singlepathproperty)，从而使得基于N-list的算法PrePost能在局部实现直接挖掘频繁模式而不用生成候选项集，从而有效克服了基于Node-list算法的缺点，极大提升了挖掘速度。单路径性质(singlepathproperty)LetP1=j1i1i2…iv,P2=j2i1i2…iv,…,Pn=jni1i2…iv,(j1

>j2

>

…>jn>i1>i2

…

>iv)是n个项集，记Pa

Pb=jajbi1i2…iv(1

a<b

n).如果Pn的N-list只包含一个PP-code，并且存在集合S={s1,s2,…,st}(1

s1<s2<…<s2

<n)满足Pm

Pn(m

S)的N-list不为空，则成立：对任意m

S,Pm

Pn

的N-list只包含一个PP-code，并且其支持度等于Pn的支持度。令Nodem代表PPC-tree中对应Pm

Pn

的节点，对S中任何sx和sy，如果

sx<

sy，则Nodesx是Nodesy的祖先。项集jx1jx2…jxk

jni1i2…iv

(1

x1<x2<…<xk

<n,且x1,x2,…,xk

S)的支持度等于Pn的支持度。N-list性质{}C:1B:3C:2E:2A:1A:1E:1D:1F:1(1,10)(2,2)(3,1)(4,7)(5,5)(6,4)(7,3)(8,6)(10,8)(9,9)N2

N1

N3

N4

N5

N6

N7

N8

N9

EA的N-list为{<(6,4):1>}CA的N-list为{<(5,5):1>}BA的N-list为{<(4,7):1>}BA

EA=BEA的N-list为{<(4,7):1>}CA

EA=CEA的N-list为{<(5,5):1>}无须通过交BEA和CEA的N-list形成BCEA的N-list来获取BCEA的支持度。利用单路径属性可直接知道BCEA的支持度为1，即EA的支持度。基于N-list的PrePost性质除了采用单链性质进行局部无候选生成直接获取频繁项集的挖掘策略外，PrePost基本上与PPV相同。具体请参见如下文献DengZhiHong,WangZhongHui，andJiangJiaJian.ANewAlgorithmforFastMiningFrequentItemsetsUsingN-Lists.SCIENCECHINAInformationSciences55(9):2008-2030,2012.

下载地址：/faculty/system/dengzhihong/dengzhihong.htmPrePost性能比较在真实稠密数据库（Accidents）和人造稀疏数据库（T25I10D100K）上均略胜FP-Growth和FP-Growth*(最好的FP-Growt