關(guān)聯(lián)分析與頻繁模式挖掘

第十一講關(guān)聯(lián)規(guī)則鄧志鴻北京大學(xué)信息科學(xué)技術(shù)學(xué)院2016年6月內(nèi)容簡(jiǎn)介基本概念關(guān)聯(lián)分析基本方法基本內(nèi)容頻繁模式挖掘關(guān)聯(lián)規(guī)則生成模式評(píng)估關(guān)聯(lián)規(guī)則1993年SIGMOD大會(huì)上Agrawal等人首次提出關(guān)聯(lián)規(guī)則挖掘(associationrulemining)目的：發(fā)現(xiàn)數(shù)據(jù)中內(nèi)在的規(guī)律性人們通常會(huì)同時(shí)購(gòu)買什么樣的商品？—Beeranddiapers?購(gòu)買微機(jī)后，接下來(lái)用戶通常會(huì)有什么購(gòu)物行為？哪種DNA對(duì)某個(gè)新藥敏感？應(yīng)用Basketdataanalysis,cross-marketing,catalogdesign,salecampaignanalysis,Weblog(clickstream)analysis,andDNAsequenceanalysis.核心任務(wù)頻繁模式(Frequentpattern)在數(shù)據(jù)集（庫(kù)）中頻繁出現(xiàn)的模式（項(xiàng)集(asetofitems)、子序列(subsequences)、子結(jié)構(gòu)(substructures)等）。內(nèi)容簡(jiǎn)介基本概念頻繁模式挖掘基本方法基本內(nèi)容頻繁模式挖掘關(guān)聯(lián)規(guī)則生成模式評(píng)估基本概念A(yù)ssociationRuleAnalysis給定事務(wù)集合，根據(jù)某些項(xiàng)的出現(xiàn)來(lái)預(yù)測(cè)其它項(xiàng)的出現(xiàn)Market-BaskettransactionsExampleofAssociationRules{Diaper}{Beer},

{Milk,Bread}{Eggs,Coke},

{Beer,Bread}{Milk},隱含著內(nèi)在關(guān)聯(lián)，而非偶然現(xiàn)象基本概念項(xiàng)(Item)最小的處理單位例如：Bread,Milk事務(wù)(Transaction)由事務(wù)號(hào)和項(xiàng)集組成例如：<1,{Bread,Milk}>事務(wù)數(shù)據(jù)庫(kù)由多個(gè)事務(wù)組成項(xiàng)集(Itemset)一個(gè)或多個(gè)項(xiàng)(item)的集例如：{Milk,Bread,Diaper}k-項(xiàng)集(k-itemset)包含k個(gè)項(xiàng)的集合基本概念包含關(guān)系令T為一事務(wù)，P為一項(xiàng)集。稱T包含P，如果P是T的子集記T

P或P

T支持度計(jì)數(shù)(Supportcount)事務(wù)數(shù)據(jù)庫(kù)中包含某個(gè)項(xiàng)集的事務(wù)的個(gè)數(shù)例如：({Milk,Bread,Diaper})=2支持度(Support)事務(wù)數(shù)據(jù)庫(kù)中包含某個(gè)項(xiàng)集的事務(wù)占事務(wù)總數(shù)的比例。例如：s({Milk,Bread,Diaper})=2/5頻繁項(xiàng)集(FrequentItemset)令P為任何一個(gè)項(xiàng)集，稱P為頻繁項(xiàng)集，如果P的支持度不小于指定的最小閾值(minsupthreshold)基本概念Example:關(guān)聯(lián)規(guī)則(AssociationRule)表達(dá)形式：XY(s,c)其中，X和Y都是項(xiàng)集，s是規(guī)則的支持度，c是置信度例子：

{Milk,Diaper}{Beer}

(0.4,0.67)規(guī)則評(píng)估度量指標(biāo)支持度－Support(s)同時(shí)包含X和Y的事務(wù)占事務(wù)總數(shù)的比例置信度－Confidence(c)在所有包含X的事務(wù)中包含Y的事務(wù)所占比例內(nèi)容簡(jiǎn)介基本概念關(guān)聯(lián)分析基本方法基本內(nèi)容頻繁模式挖掘關(guān)聯(lián)規(guī)則生成模式評(píng)估關(guān)聯(lián)規(guī)則分析－內(nèi)容給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)TD，關(guān)聯(lián)規(guī)則挖掘的目標(biāo)是要找到所有支持度和置信度都不小于指定閾值的規(guī)則。

支持度≥minsupthreshold置信度≥minconfthreshold窮舉法(Brute-forceapproach)列出所有可能的規(guī)則對(duì)每條規(guī)則計(jì)算其支持度和置信度通過(guò)閾值minsup

和minconf

過(guò)濾無(wú)效規(guī)則可計(jì)算性？計(jì)算復(fù)雜性分析給定d個(gè)不同項(xiàng)：項(xiàng)集數(shù)目等于2d所有可能的關(guān)聯(lián)規(guī)則總數(shù)等于：

如果d=6則R=602關(guān)聯(lián)規(guī)則－分析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)思考

所有規(guī)則都對(duì)應(yīng)于把同一項(xiàng)集分成兩個(gè)部分

{Milk,Diaper,Beer}

源自同一項(xiàng)集的規(guī)則有相同的支持度，但是置信度不同因此，我們可以分別處理對(duì)支持度和置信度的要求XYs=s(XY)/|DB|,c=s(XY)/s(X)關(guān)聯(lián)規(guī)則分析分兩步執(zhí)行：

挖掘頻繁項(xiàng)集－生成所有支持度

minsup的項(xiàng)集構(gòu)造規(guī)則－用每個(gè)頻繁項(xiàng)集生成高置信度的規(guī)則－對(duì)頻繁模式的每次分割（一分為二）就形成一條規(guī)則，再判斷該規(guī)則是否滿足最小置信度閾值條件。但是，挖掘頻繁模式仍然是一個(gè)“計(jì)算昂貴”的工作。{Milk,Diaper,Beer}s=0.4{Milk}s=0.8{Milk}{Diaper,Beer}s=0.4,c=0.4/0.8=0.5關(guān)聯(lián)規(guī)則分析的核心內(nèi)容簡(jiǎn)介基本概念關(guān)聯(lián)分析基本方法基本內(nèi)容頻繁模式挖掘關(guān)聯(lián)規(guī)則生成模式評(píng)估頻繁模式挖掘－重要性發(fā)現(xiàn)數(shù)據(jù)集中的有價(jià)值的重要性質(zhì)是其它數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)關(guān)聯(lián)分析：Associationrulesanalysis

MiningFrequentItemset因果分析：causalityanalysis序列、結(jié)構(gòu)模式：Sequential,structural(e.g.,sub-graph)patterns時(shí)空、多媒體、時(shí)間序列、流數(shù)據(jù)模式分析分類聚類數(shù)據(jù)倉(cāng)庫(kù)語(yǔ)義數(shù)據(jù)壓縮推薦系統(tǒng)等其他應(yīng)用生成頻繁項(xiàng)集給定d個(gè)項(xiàng)，有2d

個(gè)可能的候選項(xiàng)集生成頻繁項(xiàng)集窮舉法(Brute-forceapproach)網(wǎng)格中每個(gè)項(xiàng)集都是候選的頻繁項(xiàng)集通過(guò)掃描一次數(shù)據(jù)庫(kù)，可以得到每個(gè)候選項(xiàng)集的支持度比較每一條事務(wù)和每個(gè)候選項(xiàng)集計(jì)算復(fù)雜度－O(NMw)N為事務(wù)數(shù)目，M=2d

為候選項(xiàng)集，w為一次比較的計(jì)算代價(jià)內(nèi)容簡(jiǎn)介基本概念關(guān)聯(lián)分析基本方法基本內(nèi)容頻繁模式挖掘關(guān)聯(lián)規(guī)則生成模式評(píng)估頻繁項(xiàng)集挖掘算法Apriori算法第一個(gè)算法用了Apriori性質(zhì)所有挖掘算法的基礎(chǔ)基于事務(wù)列表的算法Eclat算法基于節(jié)點(diǎn)列表的算法PPV算法、Prepost算法Apriori算法候選－生成類型Apriori性質(zhì)反單調(diào)性基本思想由長(zhǎng)度為k的頻繁模式生成長(zhǎng)度為(k+1)的候選模式計(jì)算長(zhǎng)度為(k+1)的候選模式的支持度，從而獲得長(zhǎng)度為(k+1)的頻繁模式Aprioir算法Apriori性質(zhì):如果一個(gè)項(xiàng)集是頻繁的，那么它的所有子集都是頻繁的。也稱為反單調(diào)性Apriori性質(zhì)成立的原因如下：任何一個(gè)項(xiàng)集的支持度不可能超過(guò)其子集的支持度發(fā)現(xiàn)不頻繁Apriori性質(zhì)－演示裁減所有超集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算法－重要細(xì)節(jié)如何生成候選項(xiàng)集？Step1:自連接(self-joining)LkStep2:裁減(pruning)如何計(jì)算候選項(xiàng)集的支持度？例子L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3由abc

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

Pruning:因?yàn)閍de不在L3中，所以不用處理acde（它不可能是頻繁項(xiàng)集）C4={abcd}Apriori算法－生成候選項(xiàng)集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算法在構(gòu)造候選k-項(xiàng)集的時(shí)候利用了頻繁k-1項(xiàng)集進(jìn)行裁減，有效地降低了候選項(xiàng)集的數(shù)量。但是這個(gè)方法對(duì)生成候選2-項(xiàng)集基本上沒(méi)有太大作用。令頻繁1-項(xiàng)集個(gè)數(shù)為n，則候選2-項(xiàng)集個(gè)數(shù)為n(n-1)/2基本方法第一次掃描事務(wù)數(shù)據(jù)庫(kù)時(shí)計(jì)算2-項(xiàng)集的支持度，從而直接獲得頻繁2-項(xiàng)集Apriori算法－減少候選項(xiàng)集數(shù)目Apriori算法－直接挖掘頻繁2-項(xiàng)集很多實(shí)驗(yàn)表明，在Apriori算法（或基于Apriori的算法）頻繁模式挖掘過(guò)程中，頻繁2-項(xiàng)集的查找最費(fèi)時(shí)間頻繁1-項(xiàng)集很多，所以候選2-項(xiàng)集就非常多方法在掃描事務(wù)數(shù)據(jù)庫(kù)時(shí)，同時(shí)計(jì)算每個(gè)事務(wù)所包含2-項(xiàng)集的支持度。第一次掃描數(shù)據(jù)庫(kù)，同時(shí)找到頻繁1-項(xiàng)集和頻繁2-項(xiàng)集發(fā)現(xiàn)頻繁2-項(xiàng)集－示例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}…頻繁項(xiàng)集挖掘算法Apriori算法第一個(gè)算法用了Apriori性質(zhì)所有挖掘算法的基礎(chǔ)基于事務(wù)列表的算法Eclat算法基于節(jié)點(diǎn)列表的算法PPV算法、Prepost算法Eclat算法Apriori算法主要缺點(diǎn)多次掃描數(shù)據(jù)庫(kù)，候選項(xiàng)集支持度計(jì)算代價(jià)高垂直數(shù)據(jù)表示(verticaldataformat)TidsetTidset令P為一個(gè)項(xiàng)集，其Tidset定義如下：Tidset(P)={t.Tid|P

t}性質(zhì)1：P的支持度等于Tidset(P)勢(shì)（包含元素的個(gè)數(shù)）性質(zhì)2：令Sk={Tidset(P)

|

P是頻繁k-項(xiàng)集}，則對(duì)任何C

Ck+1(候選k+1項(xiàng)集)，Tidset(C)可由Sk中的兩個(gè)元素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基本一致，只不過(guò)在獲取候選項(xiàng)集的Tidset直接用兩個(gè)頻繁項(xiàng)集的Tidset的交。而候選項(xiàng)集的支持度就直接等于|Tidset|垂直數(shù)據(jù)表示Eclat算法–

示例1234561345AC2456D1356TW123451345451351345ACADATAW245613561234556245135CDCTCWDTDWTW1351345135135245135ACTACWATWCDWCTWACTWMinsup=3頻繁項(xiàng)集挖掘算法Apriori算法第一個(gè)算法用了Apriori性質(zhì)所有挖掘算法的基礎(chǔ)基于事務(wù)列表的算法Eclat算法基于節(jié)點(diǎn)列表的算法PPV算法、Prepost算法基于節(jié)點(diǎn)列表的頻繁模式挖掘算法垂直算法（如Eclat）簡(jiǎn)單、易實(shí)現(xiàn)時(shí)間效率對(duì)稠密數(shù)據(jù)而言，較差對(duì)稀疏數(shù)據(jù)而言，較好FP-Growth算法復(fù)雜、不易實(shí)現(xiàn)時(shí)間效率高對(duì)稠密數(shù)據(jù)而言，好對(duì)稀疏數(shù)據(jù)而言，一般Question是否可以設(shè)計(jì)一個(gè)算法，同時(shí)具有垂直算法簡(jiǎn)單、易實(shí)現(xiàn)，而又具有較高效率的特點(diǎn)。分析Eclat優(yōu)點(diǎn)采用垂直數(shù)據(jù)格式，使得計(jì)算項(xiàng)集的支持度變得簡(jiǎn)單。候選項(xiàng)集的Tidset直接由兩個(gè)頻繁項(xiàng)集的Tidset的交獲取。而候選項(xiàng)集的支持度就等于|Tidset|。問(wèn)題Tidset是否足夠簡(jiǎn)潔和壓縮。在分布不變的情況下，與數(shù)據(jù)庫(kù)的大小呈線性關(guān)系。FP-Growth優(yōu)點(diǎn)采用壓縮的FP-tree結(jié)構(gòu)，使得搜索空間極大地縮小問(wèn)題重復(fù)遞歸構(gòu)造FP-tree費(fèi)時(shí)費(fèi)力復(fù)雜，對(duì)編程技能要求高分析－示例－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數(shù)據(jù)重復(fù)100次表2E:2,3,4,7,8,9,…,497,498,499分析－示例－Tidset顯然，對(duì)給定的閾值，表1和表2所包含的頻繁項(xiàng)集是一樣的，且這些頻繁項(xiàng)集的支持度是一樣的。但是，如果采用Eclat算法，挖掘表2中頻繁項(xiàng)集的時(shí)間是挖掘表1中頻繁項(xiàng)集的時(shí)間的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的結(jié)構(gòu)基本上沒(méi)有變化，只不過(guò)每個(gè)節(jié)點(diǎn)上的計(jì)數(shù)值增加了100倍分析－發(fā)現(xiàn){}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等于所有如下節(jié)點(diǎn)的count值之和：(1)該節(jié)點(diǎn)的lable為A(2)該節(jié)點(diǎn)的祖先節(jié)點(diǎn)中有標(biāo)簽為C的節(jié)點(diǎn)是一個(gè)普遍的結(jié)論，是節(jié)點(diǎn)編碼的基礎(chǔ)基于節(jié)點(diǎn)列表的算法每個(gè)項(xiàng)或項(xiàng)集都由節(jié)點(diǎn)列表表示。為了有效表達(dá)節(jié)點(diǎn)之間的包含關(guān)系，需要對(duì)節(jié)點(diǎn)進(jìn)行編碼杜威編碼前后序編碼CA

N2,N6

杜威編碼方法缺點(diǎn)編碼的大小與樹(shù)的深度成正比，且與樹(shù)的寬度有關(guān)系。存儲(chǔ)代價(jià)高包含關(guān)系的判斷與樹(shù)深度相關(guān)，效率不高能否解決呢？可以，采用樹(shù)的前后序編碼{}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的節(jié)點(diǎn)是編碼為.1的節(jié)點(diǎn)的祖先樹(shù)的前后序編碼給定一個(gè)樹(shù)，每個(gè)節(jié)點(diǎn)N對(duì)應(yīng)一個(gè)二元組（Npre,Npost）。Npre代表按前序遍歷樹(shù)（深度優(yōu)先）時(shí)訪問(wèn)到節(jié)點(diǎn)N時(shí)的編號(hào)（序號(hào)），Npost代表按后序遍歷（深度優(yōu)先）樹(shù)時(shí)訪問(wèn)到節(jié)點(diǎn)N時(shí)的編號(hào)（序號(hào)）。前后序編碼的性質(zhì)性質(zhì)0：X,Y是兩個(gè)節(jié)點(diǎn)，X是Y的祖先節(jié)點(diǎn)，當(dāng)且僅當(dāng)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的一棵前綴樹(shù)（項(xiàng)按照支持度排序）每個(gè)節(jié)點(diǎn)都有一對(duì)<前序編號(hào),后序編號(hào)>{}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對(duì)PPC-tree中的每個(gè)節(jié)點(diǎn)N，稱<(N.pre-order,N.post-order):count>為節(jié)點(diǎn)N的PP-code。例如：節(jié)點(diǎn)N1的PP-code是<(2,2):1>節(jié)點(diǎn)N2的PP-code是<(3,1):1>Node-list定義Node-list：一種節(jié)點(diǎn)列表的表示形式1-itemset(1-項(xiàng)集)的Node-list給定PPC-tree樹(shù)，1-itemseti

的Node-list定義為序列序列由PPC-tree樹(shù)中節(jié)點(diǎn)標(biāo)簽(label)為i的所有節(jié)點(diǎn)的PP-code組成。PP-code在序列中的位置按照節(jié)點(diǎn)前序序號(hào)排列C的Node-list為{<(2,2):1>,<(5,5):2>}A的Node-list為{<(3,1):1>,<(7,3):1>}Node-list定義約定：所有項(xiàng)的總集I={i1,i2,…,iN}按照項(xiàng)的支持度降序排列的序列。對(duì)任何0

s

tN，記is

it。約定：任何項(xiàng)集中的項(xiàng)按其在I中的序排列2-itemset(2-項(xiàng)集)的Node-list給定兩個(gè)1項(xiàng)集i1andi2(i1

i2)，他們的Node-list分別為{<(x11,y11):z11>,<(x12,y12):z12>,…,<(x1m,y1m):z1m>}和{<(x21,y21):z21>,<(x22,y22):z22>,…,<(x2n,y2n):z2n>}。2項(xiàng)集i1i2的Node-list定義如下令<(x2q,y2q):z2q>是i2的Node-list中的一個(gè)元素，如果存在<(x1p,y1p):z1p>∈i1的Node-list，滿足<(x1p,y1p):z1p>是<(x2q,y2q):z2q>的祖先，則<(x2q,y2q):z2q>屬于i1i2的Node-list.i1i2的Node-list中的元素按照節(jié)點(diǎn)的前序序號(hào)排列。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>的祖先節(jié)點(diǎn)，故<(3,1):1>屬于CA的Node-list5<7

5>3，故<(5,5):2>是<(7,3):1>的祖先節(jié)點(diǎn)，故<(7,3):1>屬于CA的Node-listNode-list定義k-itemset(k-項(xiàng)集)的Node-list令P

=i1

i2…i(k-2)

ixiy

(k

3)是一k-項(xiàng)集，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中的一個(gè)元素，如果存在<(x1p,y1p):z1p>∈P1的Node-list，滿足<(x1p,y1p):z1p>是<(x2q,y2q):z2q>的祖先，則<(x2q,y2q):z2q>屬于P的Node-list.P的Node-list中的元素按照節(jié)點(diǎn)的前序序號(hào)排列。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>的祖先節(jié)點(diǎn)，故<(7,3):1>屬于CEA的N-list3<6，故<(6,4):2>不是<(3,1):1>的祖先節(jié)點(diǎn)，CE中只有一個(gè)元素<(6,4):2>，所以不存在元素是<(3,1):1>的祖先節(jié)點(diǎn)，故<(3,1):1>不屬于CEA的N-listNode-list－現(xiàn)象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的重要性質(zhì)－1性質(zhì)1：令k-項(xiàng)集P=i1

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

z1+z2+…+zm證明按照前綴樹(shù)PPC-tree的構(gòu)造，P

的Node-list中的節(jié)點(diǎn)記錄了項(xiàng)集i1

i2…ik在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)。詳細(xì)證明見(jiàn)：ZhihongDengandZhonghuiWang.ANewFastVerticalMethodforMiningFrequentPatterns.InternationalJournalofComputationalIntelligenceSystems,3(6):733–744,2010.下載網(wǎng)址：/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-項(xiàng)集的Node-list生成(k+1)-項(xiàng)集的Node-list的時(shí)間是決定算法效率的關(guān)鍵所。令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根據(jù)定義，對(duì)P2的Node-list中的每一個(gè)元素<(x

P2i,y

P2i):z

P2i>,，必須檢查P1的Node-list中是否存在某個(gè)元素，該元素是<(x

P2i,y

P2i):z

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

P2i,y

P2i):z

P2i>加入到P的Node-list中，否則不加入。一個(gè)直觀的做法：對(duì)P2的Node-list中每個(gè)元素，都與P1的Node-list中元素進(jìn)行祖先－后代關(guān)系的檢查，其算法復(fù)雜都為O(m*n)是否有更為高效的方法呢？Yes,有O(m+n)的方法Node-list的重要性質(zhì)－2設(shè)P為1-項(xiàng)集，令其Node-list為：{<(xP1,yP1):z

P1>,<(x

P2,y

P2):z

P2>,…,<(x

Pk,y

Pk):z

Pk>}，性質(zhì)2對(duì)任何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的重要性質(zhì)－3性質(zhì)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，則對(duì)任何s

k

m，1

v

t成立x

P1k

x

P2v

x

P1k

xP1s

x

P2t

x

P2v

性質(zhì)3說(shuō)明<(x

P2v,y

P2v):z

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

P1k>的子孫節(jié)點(diǎn)。Node-list的高效生成算法簡(jiǎn)記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-項(xiàng)集記為P先看p11如果對(duì)所有的p2i

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

xP11

xP2i，則由性質(zhì)0可知，P2中的所有元素都不可能是p11的子孫。另外，由性質(zhì)2可知xP1k

xP11(1<k)。可知P2中的所有元素都不可能是p1k的子孫。因此終止處理，輸出P的Node-list。否則存在p2k，滿足xP11

<

xP2k，又分以下兩種情況yP11

>

yP2k

：表明p2k是p11的子孫，把p2k插入P的Node-list中。繼續(xù)比較p11和p2(k+1)。yP11

<

yP2k：表明p2k不是p11的子孫。由性質(zhì)2可知對(duì)任何j>k,yP11

<

yP2k

<yP2j，因此p2j也不可能是p11的子孫。因此，不需要繼續(xù)比較p11和p2j(j>k)。這時(shí)，對(duì)p11處理結(jié)束，轉(zhuǎn)而比較p12和P2中的元素。因?yàn)閷?duì)任何s<k,p2s

要么是p11的子孫，要么其前序序號(hào)xP2s<xP11。對(duì)第一中情況，p2s

不可能是p12的子孫。否則p11和p12有祖孫關(guān)系，因?yàn)閜11和p12的標(biāo)簽一樣，所以根據(jù)樹(shù)的構(gòu)造算法這是不可能。對(duì)第二種情況，xP2s<xP11，而xP11<

xP12。有xP2s<xP12。故p2s

不可能是p12的子孫。由上分析，p2s不可能是p12的子孫。所以對(duì)p12的比較，從p2k開(kāi)始。對(duì)p12的處理同p11。這樣處理的方式避免了p12與P2中已經(jīng)和p11比較過(guò)的元素（p2k除外）再進(jìn)行比較，從而實(shí)現(xiàn)線性時(shí)間復(fù)雜度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>}假設(shè)i2>i3第1步檢測(cè)祖孫關(guān)系7>5,所以節(jié)點(diǎn)(7,8)不可能是節(jié)點(diǎn)(5,1)的祖先。因此第2步就要考察(7,8)和(8,5)的關(guān)系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步檢測(cè)祖孫關(guān)系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。所以節(jié)點(diǎn)(7,8)

是節(jié)點(diǎn)(8,5)的祖先。故把<(8,5):

2>輸入到i1i2i3

的Node-list中。第三步，檢測(cè)(7,8)

與節(jié)點(diǎn)(10,6)的祖孫關(guān)系i1i2i3={<(8,5):

2>}添加Node-list的高效合并算法－示例第3步檢測(cè)祖孫關(guān)系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。所以節(jié)點(diǎn)(7,8)

是節(jié)點(diǎn)(10,6)的祖先。故把<(10,6):

2>輸入到i1i2i3

的Node-list中。第四步，檢測(cè)(7,8)

與節(jié)點(diǎn)(18,19)的祖孫關(guān)系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}添加Node-list的高效合并算法－示例第4步檢測(cè)祖孫關(guān)系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。所以節(jié)點(diǎn)(7,8)

不是節(jié)點(diǎn)(18,19)的祖先。由于節(jié)點(diǎn)(18,19)后面的節(jié)點(diǎn)后序編碼都大于19，所以節(jié)點(diǎn)(7,8)

也不可能是(18,19)后面節(jié)點(diǎn)的祖先。因此，不需要檢測(cè)(7,8)

與(18,19)后面節(jié)點(diǎn)的祖孫關(guān)系。即i1i3節(jié)點(diǎn)列表中所有是節(jié)點(diǎn)(7,8)

子孫的節(jié)點(diǎn)都已經(jīng)找到。所以停止節(jié)點(diǎn)(7,8)與其它節(jié)點(diǎn)祖孫關(guān)系的檢測(cè)。故第五步，檢測(cè)(7,8)后續(xù)節(jié)點(diǎn)<(15,15):

6>是否與i1i3節(jié)點(diǎn)列表中的元素有祖孫關(guān)系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}Node-list的高效合并算法－示例第5步檢測(cè)祖孫關(guān)系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>}其實(shí)不需要檢測(cè)(15,15)與(18,19)前面節(jié)點(diǎn)的祖孫關(guān)系。因?yàn)?18,19)前面節(jié)點(diǎn)要么是(7,8)的子孫，要么其前序序號(hào)小于7。如果是(7,8)的子孫，就不可能是(15,15)的子孫（否則(7，8)和(15,15)之間有祖孫關(guān)系。這是可能的，因?yàn)樗鼈兊臉?biāo)簽一樣）。如果前序序號(hào)小于7，則必然小于(7,8)后續(xù)節(jié)點(diǎn)的前序序號(hào)，故也不可能是(15,15)的子孫。這就意味著(18,19)前面的節(jié)點(diǎn)不可能是(15,15)的子孫。因此第5步直接比較(15,15)與(18,19)的祖孫關(guān)系。雖然15<

18

，但15<

19。故(15,15)不是(18,19)的祖先。由于(18,19)后續(xù)節(jié)點(diǎn)的后序編碼均大于19。所以(15,15)也不可是(18,19)后續(xù)節(jié)點(diǎn)的祖先。故，終止(15,15)與其它節(jié)點(diǎn)的祖孫關(guān)系的檢測(cè)。第6步檢測(cè)檢測(cè)(15,15)后續(xù)節(jié)點(diǎn)<(23,21):

6>是否與i1i3節(jié)點(diǎn)列表中的元素有祖孫關(guān)系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}Node-list的高效合并算法－示例第6步檢測(cè)祖孫關(guān)系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>}與第五步一樣，不需要檢測(cè)(23,21)與(18,19)前面節(jié)點(diǎn)的祖孫關(guān)系，而是直接比較(23,21)與(18,19)的祖孫關(guān)系。因?yàn)?3>

18

，所以(23,21)不是(18,19)的祖先。第7步要繼續(xù)檢測(cè)(23,21)與(18,19)后續(xù)節(jié)點(diǎn)(24,20)的祖孫關(guān)系。i1i2i3={<(8,5):

2>,<(10,6):

2>

}Node-list的高效合并算法－示例第7步檢測(cè)祖孫關(guān)系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>}因?yàn)?3<

24,21>

20，故(23,21)是

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

5>輸入到i1i2i3

的Node-list中。i1i3節(jié)點(diǎn)鏈表沒(méi)有可處理的節(jié)點(diǎn)，整個(gè)操作結(jié)束，得到了i1i2i3

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

2>,<(10,6):

2>,<(24,20):

5>

}添加PPV性能比較在稠密數(shù)據(jù)庫(kù)上與FP-growth相當(dāng)在稀疏數(shù)據(jù)庫(kù)上表現(xiàn)優(yōu)秀仍然受制于候選-生成模式的限制基于節(jié)點(diǎn)列表方法－N-list約定：所有項(xiàng)的總集I={i1,i2,…,iN}按照項(xiàng)的支持度降序排列的序列。對(duì)任何0

s

tN，記is

it。約定：任何項(xiàng)集中的項(xiàng)按其在I中的序排列1-itemset(1-項(xiàng)集)的N-list同其Node-list2-itemset(2-項(xiàng)集)的N-list定義如下給定兩個(gè)1項(xiàng)集i1andi2(i1

i2)，他們的N-list分別為{<(x11,y11):z11>,<(x12,y12):z12>,…,<(x1m,y1m):z1m>}和{<(x21,y21):z21>,<(x22,y22):z22>,…,<(x2n,y2n):z2n>}。2項(xiàng)集i1i2的Node-list定義如下令<(x2q,y2q):z2q>是i2的Node-list中的一個(gè)元素，如果存在<(x1p,y1p):z1p>∈i1的Node-list，滿足<(x1p,y1p):z1p>是<(x2q,y2q):z2q>的祖先，則<(x1p,y1p):z2q>屬于i1i2的Node-list.i1i2的Node-list中的元素按照節(jié)點(diǎn)的前序序號(hào)排列?；诠?jié)點(diǎn)列表方法－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性質(zhì)N-list具有Node-list的所有性質(zhì)。除此之外，N-list還具有單路徑性質(zhì)(singlepathproperty)，從而使得基于N-list的算法PrePost能在局部實(shí)現(xiàn)直接挖掘頻繁模式而不用生成候選項(xiàng)集，從而有效克服了基于Node-list算法的缺點(diǎn)，極大提升了挖掘速度。單路徑性質(zhì)(singlepathproperty)LetP1=j1i1i2…iv,P2=j2i1i2…iv,…,Pn=jni1i2…iv,(j1

>j2

>

…>jn>i1>i2

…

>iv)是n個(gè)項(xiàng)集，記Pa

Pb=jajbi1i2…iv(1

a<b

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

s1<s2<…<s2

<n)滿足Pm

Pn(m

S)的N-list不為空，則成立：對(duì)任意m

S,Pm

Pn

的N-list只包含一個(gè)PP-code，并且其支持度等于Pn的支持度。令Nodem代表PPC-tree中對(duì)應(yīng)Pm

Pn

的節(jié)點(diǎn)，對(duì)S中任何sx和sy，如果

sx<

sy，則Nodesx是Nodesy的祖先。項(xiàng)集jx1jx2…jxk

jni1i2…iv

(1

x1<x2<…<xk

<n,且x1,x2,…,xk

S)的支持度等于Pn的支持度。N-list性質(zhì){}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>}無(wú)須通過(guò)交BEA和CEA的N-list形成BCEA的N-list來(lái)獲取BCEA的支持度。利用單路徑屬性可直接知道BCEA的支持度為1，即EA的支持度?；贜-list的PrePost性質(zhì)除了采用單鏈性質(zhì)進(jìn)行局部無(wú)候選生成直接獲取頻繁項(xiàng)集的挖掘策略外，PrePost基本上與PPV相同。具體請(qǐng)參見(jiàn)如下文獻(xiàn)DengZhiHong,WangZhongHui，andJiangJiaJian.ANewAlgorithmforFastMiningFrequentItemsetsUsingN-Lists.SCIENCECHINAInformationSciences55(9):2008-2030,2012.

下載地址：/faculty/system/dengzhihong/dengzhihong.htmPrePost性能比較在真實(shí)稠密數(shù)據(jù)庫(kù)（Accidents）和人造稀疏數(shù)據(jù)庫(kù)（T25I10D100K）上均略勝FP-Growth和FP-Growth*(最好的FP-Growt