最大可刪除項(xiàng)集快速挖掘算法

趙群禮，郭玉堂

合肥師范學(xué)院計(jì)算機(jī)學(xué)院，安徽合肥，230061

挖掘可刪除項(xiàng)集(Erasable Itemset)是Deng等人在2009年提出的[1]，用于解決在企業(yè)資金緊張的情況下，停產(chǎn)哪些產(chǎn)品損失的利潤(rùn)較小，并據(jù)此制定新的產(chǎn)品計(jì)劃。在此基礎(chǔ)上國內(nèi)外多位學(xué)者提出了多種挖掘可刪除項(xiàng)集的算法，比如Deng等人在先后提出了VME[2]算法、MERIT[3]算法，Le等[4]在2014年提出了MEI算法，這些算法都能在產(chǎn)品數(shù)據(jù)庫中有效挖掘可刪除項(xiàng)集。但是當(dāng)閾值較大時(shí)，這些算法在挖掘過程中都會(huì)產(chǎn)生大量的項(xiàng)目集，占用了較大的內(nèi)存空間和CPU計(jì)算時(shí)間。為了減少挖掘過程中產(chǎn)生的項(xiàng)目集的數(shù)量，節(jié)約占用的存儲(chǔ)空間，Deng等[5]在2013年提出了挖掘Top-rank-k可刪除項(xiàng)集的VM算法；Nguyen等[6]在2015年提出了挖掘可刪除閉項(xiàng)集的MECP算法，Vo等[7]在2017年提出了基于約束的挖掘算法pMEIC；Nguyen等[8]在2019年提出了挖掘最大可刪除項(xiàng)集的GenMax-EI、Flag-GenMax-EI和PE-GenMax-EI算法。這些算法都能有效解決可刪除項(xiàng)集的挖掘問題，而且挖掘的項(xiàng)目集數(shù)量都相對(duì)較少。但相比較而言，挖掘最大可刪除項(xiàng)集的算法產(chǎn)生的項(xiàng)目集更少[8]。另外，由于最大可刪除項(xiàng)集的所有子集都是可刪除項(xiàng)集，因此，在實(shí)際應(yīng)用中可以將挖掘可刪除項(xiàng)集問題轉(zhuǎn)化為挖掘最大可刪除項(xiàng)集問題，以減少挖掘過程中的計(jì)算量和存儲(chǔ)空間。

目前，挖掘最大可刪除項(xiàng)集的最新算法主要是Nguyen等人在文獻(xiàn)[8]中提出的三個(gè)算法：GenMax-EI、Flag-GenMax-EI和PE-GenMax-EI，其中PE-GenMax-EI算法的效率最好。PE-GenMax-EI算法采用了GenMax算法的思想，雖然在挖掘過程中也采用了剪枝技術(shù)，但該算法采用按層搜索的方式，在搜索過程中產(chǎn)生了大量的候選項(xiàng)目集，每個(gè)候選項(xiàng)集都需要計(jì)算收益值，浪費(fèi)了大量CPU的計(jì)算時(shí)間和內(nèi)存空間。本文在現(xiàn)有研究成果的基礎(chǔ)上提出了一種新的最大可刪除項(xiàng)集挖掘算法MMEIA(Mining Maximal Erasable Itemsets Algorithm)，該算法采用深度優(yōu)先的搜索方式，利用每個(gè)項(xiàng)目對(duì)應(yīng)產(chǎn)品集之間的關(guān)系和剪枝策略，使挖掘最大可刪除項(xiàng)集的搜索空間更小，產(chǎn)生的候選項(xiàng)集更少，花費(fèi)的計(jì)算量更低。從實(shí)驗(yàn)結(jié)果可以看出，本文提出的MMEIA算法具有更好的挖掘效率。

1 相關(guān)理論

1.1 可刪除項(xiàng)集和最大可刪除項(xiàng)集

設(shè)產(chǎn)品數(shù)據(jù)庫PDB表示為{P1,P2,…,Pm}，Pi為一種產(chǎn)品，該產(chǎn)品中包含的項(xiàng)目表示為Pi.items，該產(chǎn)品具有的價(jià)值用Pi.Val表示，數(shù)據(jù)庫的大小表示為|PDB|。設(shè)I為PDB中項(xiàng)目的集合，表示為I={i1,i2,…in}，Pi可以表示為{ik1,ik2,…,ikx|ki∈[1…n]}，如表1所示。對(duì)于某個(gè)項(xiàng)目集S，S?I，S的價(jià)值表示為Gain(S)，可以用PDB中產(chǎn)品的價(jià)值來計(jì)算，公式如下：

表1 產(chǎn)品數(shù)據(jù)庫PDB

(1)

例如,項(xiàng)目集S={i6,i7,i8}，Gain(S) =P7.Val+P8.Val+P9.Val+P10.Val+P11.Val= 250 + 150 + 100 + 200 + 150 = 850。

定義1設(shè)PDB中所有產(chǎn)品的價(jià)值總和用Sum(PDB)表示，δ為設(shè)定的閾值，若S滿足如下條件：

Gain(S)≤Sum(PDB)×δ

則稱S為可刪除項(xiàng)集，表示為EI(ErasableItemsets)。

定義2設(shè)T是PDB中所有可刪除項(xiàng)集的集合，S∈T，若S不是T中任意項(xiàng)集的子集，則稱S為最大可刪除項(xiàng)集，表示為MaxEI(Maximal Erasable Itemsets)，最大可刪除項(xiàng)集的集合表示為MES(Maximal Erasable Set)。

根據(jù)定義1和2，可以計(jì)算出表1的產(chǎn)品數(shù)據(jù)庫在δ=15%時(shí)的可刪除項(xiàng)集和最大可刪除項(xiàng)集，如表2所示。從表中所列的挖掘結(jié)果可以看出，挖掘的最大可刪除項(xiàng)集的數(shù)量要遠(yuǎn)少于可刪除項(xiàng)集的數(shù)量。

表2 δ=15%的可刪除項(xiàng)集和最大可刪項(xiàng)除

性質(zhì)1可刪除項(xiàng)集中只包含可刪除項(xiàng)目，不會(huì)包含非可刪除項(xiàng)目。

性質(zhì)2最大可刪除項(xiàng)集的所有子集都是可刪除項(xiàng)集。

證明根據(jù)最大可刪除項(xiàng)集的定義可知，其所有子集必為可刪除項(xiàng)集，故證略。

推論1若X為最大可刪除項(xiàng)集Y的子集，則Gain(X)≤Gain(Y)。

證明假設(shè)計(jì)算Gain(X)的產(chǎn)品集合為{Pi,Pj,…，Pm}，計(jì)算Gain(Y)的產(chǎn)品集合為{Pc,Pd,…，Pi,Pj,…，Pn}，由于X?Y，所以{Pi,Pj,…，Pm}?{Pc,Pd,…，Pi,Pj,…，Pn}，根據(jù)公式(1)，Gain(X)≤Gain(Y)，推論成立，證畢。

1.2 產(chǎn)品集

設(shè)ik為PDB中的某個(gè)項(xiàng)目，則在PDB中包含ik的所有產(chǎn)品的集合為{Pk1,Pk2,……,Pkm|ik∈Pki.items,1≤ki≤|PDB|}，簡(jiǎn)稱ik的產(chǎn)品集，用P(ik)表示。為了表示方便，產(chǎn)品集中的每個(gè)產(chǎn)品都用該產(chǎn)品的id表示，例如在表1中包含i4的產(chǎn)品集為P(i4)={7,8,9}。

(2)

例如,在表1中項(xiàng)集{i4,i5}對(duì)應(yīng)的產(chǎn)品集為：P(i4)∪P(i5)={7,8,9}∪{4,5,6,7,8}={4,5,6,7,8,9}，其收益是P4,P5,P6,P7,P8,P9的價(jià)值之和。

性質(zhì)3設(shè)X和Y為兩個(gè)項(xiàng)目集，它們的產(chǎn)品集為P(X)和P(Y)，則P(XY)=P(X)∪P(Y)。

證明根據(jù)項(xiàng)目集對(duì)應(yīng)產(chǎn)品集的定義和示例，可知該性質(zhì)必然成立，故證略。

推論2若AX和AY為兩個(gè)項(xiàng)目集，它們具有相同的前綴A，P(AX)和P(AY)分別是它們的產(chǎn)品集，則P(AXY)=P(AX)∪P(AY)。

1.3 產(chǎn)品集之間的包含關(guān)系

根據(jù)2.2中產(chǎn)品集的定義，若P(X)?P(Y)，則X的產(chǎn)品集包含于Y的產(chǎn)品集中，這種包含關(guān)系定義如下：

近年來，受哥倫比亞建筑工藝的影響，同時(shí)引進(jìn)了瓜多竹等竹種，墨西哥正在開發(fā)更為先進(jìn)的原竹建筑，但整體的竹建筑行業(yè)仍然較為落后。目前，墨西哥至少有4個(gè)為建筑配送竹材的中心，同時(shí)為竹建筑的開發(fā)提供技術(shù)支持。這為建筑師和工程師了解竹材用做建材的良好性能提供了便利[11]。

C(Y) = {X|X∈I,P(X)?P(Y)}

例如,在表1中，P(i4)= {7,8,9}，P(i6)= {7,8,9,10,11}，P(i7)= {7}，P(i8)= {8,10}，由于P(i4)?P(i6)，P(i7)?P(i6)，P(i8)?P(i6)，可得C(i6)={i4,i7,i8}，同理可得C(i4)={i7}。

性質(zhì)4對(duì)于項(xiàng)目集X、Y、Z，若X∈C(Y)，Y∈C(Z)，則X∈C(Z)。

證明由于X∈C(Y)、Y∈C(Z)，可知P(X)?P(Y)，P(Y)?P(Z)，由此得到P(X)?P(Z)，根據(jù)包含關(guān)系的定義可得X∈C(Z)，此性質(zhì)成立，證畢。

2 MMEIA算法

2.1 算法思想

設(shè)L1為所有可刪除項(xiàng)目的集合，用一維數(shù)組表示，L1中的第i個(gè)元素表示為L(zhǎng)1[i]，其中包含的可刪除項(xiàng)目表示為L(zhǎng)1[i].items，該項(xiàng)目對(duì)應(yīng)的產(chǎn)品集用L1[i].P表示，項(xiàng)目的收益放入L1[i].val中，L1中的各元素按照每個(gè)項(xiàng)目對(duì)應(yīng)產(chǎn)品集由大到小的順序排列，L1中包含的可刪除項(xiàng)目個(gè)數(shù)用|L1|表示。

性質(zhì)5設(shè)X和Y為可刪除項(xiàng)集，若P(X)?P(Y)，則Gain(X∪Y)等于Gain(Y)，X和Y都不是最大可刪除項(xiàng)集。

證明由于P(X)?P(Y)，所以P(X∪Y)等于P(Y)，根據(jù)公式(1)可得Gain(X∪Y)等于Gain(Y)，X∪Y也是可刪除項(xiàng)集，由于X和Y都是X∪Y的子集，所以都不可能是最大可刪除集，性質(zhì)成立，證畢。

推論3設(shè)X為某個(gè)可刪除項(xiàng)集，X∩(ik∪ik+1∪…∪i|L1|) = ?，ik,ik+1,…,i|L1|是L1中最后|L1|-k+1個(gè)項(xiàng)目，Y=X∪ik∪ik+1∪…∪i|L1|，若(P(ik)∪P(ik+1)∪…∪P(i|L1|)) ?P(X)，且MES中沒有長(zhǎng)度大于Y的項(xiàng)集，則Y一定為最大可刪除項(xiàng)集。

證明假設(shè)Y不是最大可刪除項(xiàng)集，最大可刪除項(xiàng)集Z是Y的超集，則Z中包含的項(xiàng)目個(gè)數(shù)必然多于Y中包含的項(xiàng)目個(gè)數(shù)，與推論中的條件相矛盾，推論成立。

證明根據(jù)可刪除項(xiàng)集的定義和性質(zhì)1可知，X∪ik不是可刪除項(xiàng)集，則其超集一定不是可刪除項(xiàng)集。

根據(jù)上述產(chǎn)品集的包含關(guān)系和相關(guān)性質(zhì)，MMEIA算法采用的挖掘策略如下：(1)掃描一遍PDB，計(jì)算出滿足閾值δ要求的所有可刪除項(xiàng)目和對(duì)應(yīng)的產(chǎn)品集，按照產(chǎn)品集由大到小的順序?qū)㈨?xiàng)目放入L1[i].items中，將項(xiàng)目對(duì)應(yīng)的產(chǎn)品集放入L1[i].P中；(2)按照深度優(yōu)先的搜索方式，對(duì)L1中的項(xiàng)目進(jìn)行合并，搜索以L1[i].items為前綴的最大可刪除項(xiàng)集，如果L1[i].items∪L1[j].items(i

2.2 剪枝策略

在挖掘最大可刪除項(xiàng)集的過程中，根據(jù)性質(zhì)6，如果L1[i].items∪L1[j].items的收益值不滿足閾值要求，則不用再搜索以L1[i].items∪L1[j].items為前綴的所有項(xiàng)集，減少了最大可刪除項(xiàng)集的搜索空間。根據(jù)推論3，如果L1中第k、k+1、…、|L1|個(gè)項(xiàng)目對(duì)應(yīng)的產(chǎn)品集都包含在某個(gè)項(xiàng)集對(duì)應(yīng)的產(chǎn)品集中，則不用再搜索以ik、ik+1、…、i|L1|為前綴的最大可刪除項(xiàng)集，減少了候選項(xiàng)集的數(shù)量。

根據(jù)性質(zhì)4和性質(zhì)5，在對(duì)項(xiàng)集進(jìn)行合并時(shí)，如果有多個(gè)可刪除項(xiàng)集對(duì)應(yīng)的產(chǎn)品集都包含在某個(gè)可刪除項(xiàng)目集A對(duì)應(yīng)的產(chǎn)品集中，則可以直接將這些項(xiàng)集合并到一起，并將A的收益和產(chǎn)品集作為合并后的項(xiàng)集的收益和產(chǎn)品集，不用再重新計(jì)算收益值，減少了候選項(xiàng)集的數(shù)量和計(jì)算候選項(xiàng)集收益所花費(fèi)的時(shí)間。

例如，如果X∈C(Z)，Y∈C(Z)，Z是可刪除項(xiàng)集，則P(XYZ)=P(X)∪P(Y)∪P(Z)=P(Z)，因此可以得到Gain(Z)=Gain(XYZ)，所以XYZ也是可刪除項(xiàng)集，其收益值可由Z的收益值直接得到，不需要再進(jìn)行計(jì)算，其子集XY、XZ、YZ等不需再產(chǎn)生和計(jì)算收益，可以直接從搜索空間中刪除。

2.3 算法描述

根據(jù)上面的算法思想和剪枝策略，將MMEIA算法描述如下：

輸入：PDB、閾值δ、MES={ }

輸出：MES

(1)掃描PDB，找出滿足δ的所有可刪除項(xiàng)目放入L1[i].item中，相應(yīng)的產(chǎn)品集放入L1[i].P中;

(2)按照每個(gè)L1[i].P中產(chǎn)品集大小的降序?qū)1進(jìn)行排序;

(3)fori←1to|L1| -1do{

(4)X=L1[i];

(5)if(FindMaxEI(X,L1,i+1) =1)break;//X之后的所有項(xiàng)目都已合并，挖掘結(jié)束

(6) }

(7) 輸出MES

FindMaxEI過程如下：

(1)ProcedureFindMaxEI(X,L1,position) {

(2)temp= 0,supersetFlag= 0;//若X的超集是最大可刪除項(xiàng)集，則supersetFlag為1

(3)forj←positionto|L1|do{

(4)if(X.P?L1[j].P) {

(5)X.items=X.items∪L1[j].items;

(6)if(j=|L1| ) {

(7)if(|L1| -X在L1中的位置+1 =X中包含的項(xiàng)目數(shù)){

(8)MES=MES∪X;return1;}//X之后的所有項(xiàng)目都已合并，挖掘結(jié)束

(9)elseif(X?{ik,ik+1,…,i|L1||k∈[1,|L1|]}) {

(10)MES=MES∪X;return3;}//結(jié)束以X為前綴的最大可刪除項(xiàng)集挖掘

(11)else{MES=MES∪X;return2;}

(12) }

(13) }

(14)else{

(15)Y.items=X.items∪L1[j].items;

(16)Y.val=X.val+ ∑PiL1[j].P∧PiX.PPi.val;

(17)if(Y.val≤Sum(PDB)×δ) {

(18)Y.P=X.P∪L1[j].P;

(19)if(j<|L1| ) {

(20)temp=FindMaxEI(Y,L1,i+1);

(21)if(temp= 1){return1;}//Y之后的所有項(xiàng)目都已合并，挖掘結(jié)束

(22)elseif(temp=2) {supersetFlag= 1;}//X的超集是最大可刪除項(xiàng)集

(23)elseif(temp= 3) {return3;} }//結(jié)束以X為前綴的最大可刪除項(xiàng)集挖掘

(24)elseif(j=|L1|andsupersetFlag= 0) {

(25)if(|L1| -Y在L1中的起始位置+1 =Y中包含的項(xiàng)目數(shù)){

(26)MES=MES∪Y;return1;}//Y之后的所有項(xiàng)目都已合并，挖掘結(jié)束

(27)elseif(Y?{ik,ik+1,…,i|L1||k∈[1,|L1|]}) {

(28)MES=MES∪Y;return3;}

(29)else{MES=MES∪Y;return2;} }

(30) }

(31)elseif(j=|L1|andsupersetFlag= 0){MES=MES∪X;}

(32) }

(33) }//endfor

(34) }//endprocedure

2.4 算法示例

為了說明算法的執(zhí)行過程，將MMEIA算法用于表1的產(chǎn)品數(shù)據(jù)庫，在δ=15%(閾值為885)時(shí)其挖掘最大可刪除項(xiàng)集的過程如圖1所示。算法首先執(zhí)行第(1)(2)行，找出可刪除項(xiàng)目的集合L1={i5,i6,i4,i8,i7}，并按照每個(gè)項(xiàng)目的產(chǎn)品集由大到小排序，每個(gè)項(xiàng)目的產(chǎn)品集和收益值都已在圖1中列出。算法從第(3)行開始挖掘最大可刪除項(xiàng)集，在第(5)行調(diào)用FindMaxEI過程，先挖掘以i5為前綴的所有最大可刪除項(xiàng)集。在FindMaxEI過程中，先判斷i5的產(chǎn)品集P(i5)是否包含i6的產(chǎn)品集P(i6) (執(zhí)行第(4)行)，因P(i5)不包含P(i6)，執(zhí)行流程跳轉(zhuǎn)到第(14)行，合并i5和i6，計(jì)算Gain(i5∪i6)，由于Gain(i5∪i6) =1 300，大于閾值885，所以{i5,i6}不是最大可刪除項(xiàng)集，執(zhí)行流程再跳轉(zhuǎn)到第(31)行。由于此時(shí)的j不等于|L1|，本次循環(huán)結(jié)束，執(zhí)行流程轉(zhuǎn)入下一次循環(huán)，求解i5∪i4。由于Gain(i5∪i4) 和Gain(i5∪i8)都大于閾值，所以{i5,i4}和{i5,i8}都不是最大可刪除項(xiàng)集。在計(jì)算i5∪i7時(shí)，因P(i5)不包含P(i7)，執(zhí)行流程跳轉(zhuǎn)到第(14)行，計(jì)算Gain(i5∪i7)=850，小于閾值，又因i7是L1中最后一個(gè)項(xiàng)目，此時(shí)j等于|L1|，執(zhí)行流程跳轉(zhuǎn)到第(24)行。由于{i5,i7}包含L1中最后一個(gè)剩余項(xiàng)目i7，第(27)行的條件滿足，將{i5,i7}放入MES中，結(jié)束以i5為前綴的挖掘過程并從FindMaxEI過程中返回。

圖1 MMEIA算法在表1中的挖掘結(jié)果(δ=15%)

算法再挖掘以i6為前綴的所有最大可刪除項(xiàng)集，在調(diào)用FindMaxEI過程以后，由于P(i6)包含P(i4)，執(zhí)行第(5)行，合并i6和i4。又由于P(i6)也包含P(i8)和P(i7)，所以算法連續(xù)將i8和i7將與i6合并，在合并i7以后，此時(shí)j=5，等于|L1|，i6在L1中的位置是2，合并后的項(xiàng)集{i6,i4,i8,i7}中包含有4個(gè)項(xiàng)目，所以第(7)行的條件滿足，將{i6,i4,i8,i7}放入MES中。由于i6以后的所有項(xiàng)目都已合并，所以算法終止，挖掘得到兩個(gè)最大可刪除項(xiàng)集{i5,i7}和{i6,i4,i8,i7}。

3 實(shí)驗(yàn)驗(yàn)證和分析

3.1 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證算法的性能，在Window10系統(tǒng)、酷睿i5四代處理器、內(nèi)存8GB的臺(tái)式機(jī)上用C++語言實(shí)現(xiàn)了MMEIA算法和文獻(xiàn)[8]中的GenMax-EI、Flag-GenMax-EI和PE-GenMax-EI算法，并采用了與文獻(xiàn)[8]相同的實(shí)驗(yàn)數(shù)據(jù)集，如表3所示。在實(shí)驗(yàn)中分別運(yùn)行本文算法和對(duì)比算法，記錄它們的運(yùn)行時(shí)間，如圖2、圖3和圖4所示。通過算法的實(shí)驗(yàn)對(duì)比結(jié)果可以看出，MMEIA算法在挖掘最大可刪除項(xiàng)集時(shí)的效率要高于GenMax-EI、Flag-GenMax-EI和PE-GenMax-EI算法。

圖2 Mushroom數(shù)據(jù)集測(cè)試

圖3 Connect數(shù)據(jù)集測(cè)試

圖4 Chess數(shù)據(jù)集測(cè)試結(jié)果

表3 實(shí)驗(yàn)數(shù)據(jù)集

3.2 結(jié)果分析

MMEIA算法充分利用了產(chǎn)品集之間的包含關(guān)系，結(jié)合深度優(yōu)先搜索過程中的剪枝策略，在挖掘過程中減少了候選項(xiàng)集的產(chǎn)生數(shù)量和計(jì)算候選項(xiàng)集收益的花費(fèi)，從而節(jié)省了存儲(chǔ)空間和時(shí)間開銷。算法通過一次掃描產(chǎn)品數(shù)據(jù)庫，計(jì)算出可刪除項(xiàng)目和相關(guān)信息，后續(xù)挖掘過程中，不需要再掃描產(chǎn)品數(shù)據(jù)庫，因而節(jié)約了算法的執(zhí)行時(shí)間。根據(jù)產(chǎn)品集之間的包含關(guān)系，算法在最好情況下的時(shí)間復(fù)雜度可以達(dá)到○(n)(n為可刪除項(xiàng)目的個(gè)數(shù)，即|L1|)，最壞情況下的時(shí)間復(fù)雜度可達(dá)到○(n2)。由于算法中設(shè)置了supersetFlag標(biāo)記，當(dāng)某個(gè)可刪除項(xiàng)集X的超集是最大可刪除集且已搜索到L1中最后一個(gè)項(xiàng)目時(shí)，則可以直接返回到遞歸的第一層，進(jìn)一步減少了候選項(xiàng)集產(chǎn)生的數(shù)量和計(jì)算項(xiàng)集收益的時(shí)間，從而提高了算法的效率。在PE-GenMax-EI算法中，由于采用了按層搜索的策略，挖掘過程中會(huì)產(chǎn)生大量的候選項(xiàng)集，而計(jì)算候選項(xiàng)集的收益要花費(fèi)大量的時(shí)間，因此相對(duì)MMEIA算法來說，PE-GenMax-EI算法的整體性能相對(duì)較低。

4 結(jié) 語

本文提出的挖掘最大可刪除項(xiàng)集的MMEIA算法，利用了項(xiàng)目集對(duì)應(yīng)產(chǎn)品集之間的包含關(guān)系和可刪除項(xiàng)集的相關(guān)性質(zhì)，大量的減少了候選項(xiàng)集的數(shù)量，節(jié)省計(jì)算候選項(xiàng)集收益所需的花費(fèi)，根據(jù)實(shí)驗(yàn)結(jié)果和性能分析可以看出，該算法能夠有效解決最大可刪除項(xiàng)集挖掘問題。