劉　云，黃亞飛

(昆明理工大學 信息工程與自動化學院，云南 昆明　650500)

隨著智能生產(chǎn)的發(fā)展,如何有效地從海量的標準生產(chǎn)數(shù)據(jù)集[1-3]中進行模式挖掘[4-9]來優(yōu)化和指導智能生產(chǎn)已成為廣泛研究的課題。Deng[4]等人提出了通過挖掘可替代模式(EP)來優(yōu)化生產(chǎn)計劃的問題, 即生產(chǎn)商生產(chǎn)由許多項目集(組件)組成的大量產(chǎn)品,每個產(chǎn)品組件都有購買和存儲的成本，當沒有足夠的成本資金時,通過可替代模式挖掘找到可以去除的模式,減少在某些條件下對工廠利潤的損失, 管理者也可以利用可替代模式來制定新的生產(chǎn)計劃,但可替代模式在挖掘數(shù)量或設(shè)定閾值較大時會生成大量可替代封閉模式項目集,占用大量的時間和內(nèi)存,降低了使用這種模式的智能系統(tǒng)的性能。

目前有很多挖掘可替代模式的算法,如META,MERIT和MEI,META[4]是基于Apriori逐級生成候選模式的算法，算法執(zhí)行時間過長，MERIT[2，4-5]使用dNC-Sets結(jié)構(gòu)的概念減少了內(nèi)存消耗,雖然使用dNC-Sets使MERIT比META有一些優(yōu)勢,但仍然存在缺點。首先,每個元素的權(quán)重值分別存儲,導致產(chǎn)生大量重復的可替代模式；其次，MERIT使用當且僅當X?Y時,X的dNC-Sets結(jié)構(gòu)是Y的dNC-Sets結(jié)構(gòu)的子集的策略,此策略在各模式組合創(chuàng)建新節(jié)點時,占用大量內(nèi)存和執(zhí)行時間。

為了優(yōu)化可替代模式挖掘的內(nèi)存消耗和算法執(zhí)行時間,本文基于利潤參數(shù)提出了可替代封閉模式挖掘算法ECPM(Erasable closed patterns mining)。首先，根據(jù)定義的可替代規(guī)則[10]對數(shù)據(jù)進行預處理；其次，提出并證明了基于dNC-Sets結(jié)構(gòu)[11-12]的可替代封閉模式定理；最后，基于該定理使用與哈希表技術(shù)相結(jié)合的分組策略實現(xiàn)了ECPM算法。實驗結(jié)果表明,對比META算法和MERIT算法,在標準生產(chǎn)數(shù)據(jù)集中,ECPM算法在算法執(zhí)行時間和內(nèi)存消耗方面均有性能提升。

1　模型構(gòu)建

1.1　定義及定理

DB為一個標準的產(chǎn)品數(shù)據(jù)庫，P={P1,P2，…，Pn}是DB中的產(chǎn)品集合,I={i1,i2，…，in}是所有的項目集,每個產(chǎn)品以(Items,Val)的形式表示, Items表示產(chǎn)品項目集,Val表示該產(chǎn)品的利潤,表1表示一個簡單的產(chǎn)品數(shù)據(jù)庫DB。

定義1給定閥值ξ,數(shù)據(jù)庫DB,定義可替代規(guī)則如下:

g(X)≤T×ξ，

(1)

(2)

(3)

其中，X表示可替代模式,g(X)表示模式X的利潤,T表示產(chǎn)品數(shù)據(jù)庫DB的總利潤。

表1　產(chǎn)品數(shù)據(jù)庫DBTab.1　Product Database DB

基于定義1 Deng[4]提出了挖掘可替代模式(EP)的問題,即找到所有的X使得g(X)

1.2　dNCv-Set結(jié)構(gòu)

Le和Vo[12]基于WPPC樹[11]提出了快速挖掘可替代封閉模式的dNC-Sets結(jié)構(gòu),WPPC樹中的每個節(jié)點用項(名稱,權(quán)值,子節(jié)點,前序遍歷節(jié)點數(shù),后序遍歷節(jié)點數(shù))來表示,在WPPC中，節(jié)點Ni的節(jié)點編碼表示為dNC=(前序遍歷節(jié)點數(shù),后序遍歷節(jié)點數(shù),權(quán)值),項目集A的dNC-Sets結(jié)構(gòu)表示為dNC(A),是與A相關(guān)聯(lián)的WPPC樹中按遞減前序遍歷方式進行遍歷的節(jié)點的編碼集合,當且僅當Ci·pre-order≤Cj·pre-order且Ci·post-order≥Cj·post-order時,節(jié)點代碼Ci是節(jié)點代碼Cj的祖先節(jié)點, dNC-Setsp(X)表示為

A是模式X中的一個項目;p(A)是包含X的產(chǎn)品集合。

例2針對表1中的產(chǎn)品數(shù)據(jù)集可知,p(e)={2,3,4,5,6},p(c)={3,5},p(f)={4,6,8},所以

p(ec)=p(e)∪p(c)=

{2,3,4,5,6}∪{2,3}={2,3,4,5,6}，

p(ef)=p(e)∪p(f)=

{2,3,4,5,6}∪{4,6,8}=

{2,3,4,5,6,8}。

定義2令XA和XB分別為將項目A和B連接X而獲得的模式,dNC(XA)，dNC(XB)和dNC(XAB)分別為XA，XB和XAB的dNC-Sets。XAB的dNC-Sets定義如下:

dNC(XAB)=dNC(XB)dNC(XA)。表示dNC(XAB)是僅存在于p(XB)中而不存在于p(XA)中的產(chǎn)品標識符。

例3由例2已知p(e)，p(c)，p(f),所以

dP(ec)=p(c)p(e)=?，

dNC(ef)=dNC(f)dNC(e)={8}，

dNC(ecf)=dNC(ef)dNC(ec)={8}。

定理1XAB的利潤可以基于XA的利潤確定為

例4對于表1中的產(chǎn)品數(shù)據(jù)集,由于

p(e)={2,3,4,5,6},p(c)={3,5},

p(f)={4,6,8},dNC(ec)=?,

dNC(ef)={8}, dNC(ecf)={8},

所以

g(e)=700＄，g(c)=250＄,g(f)=350＄，

1.3　可替代封閉模式

類似于頻繁封閉模式[4，6-7，13]的定義,利潤不等于其超集的利潤的可替代模式稱為可替代封閉模式(ECP),例如,對上述DB挖掘EP,當ξ=40%時,g(e)=g(ec)=700

定理2XA和XB分別為兩個可替代模式,dNC(XA)和dNC(XB)分別為XA和XB的dNC-Sets結(jié)構(gòu),則有以下4個屬性:

1)若dNC(XA)=dNC(XB)，則

g(XA)=g(XB)=g(XAB);

2)若dNC(XA)?dNC(XB)，則

g(XA)≠g(XB),g(XB)=g(XAB);

3)若dNC(XA)?dNC(XB)，則

g(XA)≠g(XB),g(XA)=g(XAB)；

4)若dPNC(XA)?dNC(XB),dNC(XB)?dNC(XA)，則

g(XA)≠g(XB)≠g(XAB)。

證明分別證明4個屬性:

1)已知

當dNC(XA)=dNC(XB)時，

g(XA)=g(XB)，

dNC(XAB)=dNC(XB)dNC(XA)=?，

所以

2)已知

當dNC(XA)?dNC(XB)時,

g(XA)

3)已知

當dNC(XB)?dNC(XA)時,

g(XA)>g(XB)，

dNC(XAB)=dNC(XB)dNC(XA)=?，

所以

4)已知

當dNC(XA)?dNC(XB)，dNC(XB)?dNC(XA)時,

g(XA)≠g(XB)，

所以

利用定理2,當兩個元素XA和XB與X有相同的前綴組合時,有以下3種情況:

1)如果dNC(XA)=dNC(XB),則算法將XB移除并用XAB替換XA。

2)如果dNC(XB)?dNC(XA),則算法用XAB代替XA。

3)否則,XA和XB都不會改變。

2　ECPM算法

依據(jù)dNC-Sets結(jié)構(gòu)可知當且僅當dNC(X)中的所有節(jié)點的祖先節(jié)點都在dNC(Y)中時，dNC(X)?dNC(Y),所以，首先確定dNC-Sets結(jié)構(gòu)及dNC(X)與 dNC(Y)的關(guān)系,其次,根據(jù)定理3和dNC(X)與 dNC(Y)的關(guān)系分析出可替代封閉模式(ECP),ECPM算法在Microsoft Visual Studio 2012中的C#和.Net Framework(版本4.5.50709)中編碼。

2.1　確定dNC-Sets結(jié)構(gòu)及模式間的關(guān)系

輸入:dNC(X)和dNC(Y)。

輸出:dNC(XY)，dNC(X)與dNC(Y)的關(guān)系。

r=3,i=0,j=0, dNC(XY)=?,equal=0,

countAB=0, countBA=0;

whilei<|dNC(X)|,j<|dNC(Y)| do//兩個數(shù)據(jù)集不為空//

begin while

if dNC(X)[i].PreOrder≤dNC(Y)[j].PreOrder then;

if dNC(X)[i].PostOrder≥dNC(Y)[j].PostOrder then;

//(X)[i]是(Y)[j]的祖先節(jié)點//

begin if

else countBA++,j++;

end if;

elsei++;//判斷數(shù)據(jù)集(X)[i]與(Y)[j]的關(guān)系//

else

if dNC(X)[i].PreOrder>dNC(Y)[j].PreOrder and

dNC(X)[i].PostOrder

countAB++;

add dNC(Y)[j]to dNC(XY);

j++;//(Y)[j]是 (X)[i]的祖節(jié)點//

end while;

whilei<|dNC(X)| do

if |dNC(Y)|>0 and

dNC(X)[i].PreOrder>

dNC(Y) [|dNC(Y)|-1].PreOrder and

dNC(X)[i].PostOrder<

dNC(Y) [|dNC(Y)|-1].PreOrder then

countAB++,i++;

whilej<|dNC(Y)| do

if |dNC(X)|>0 and

dNC(X) [|dNC(X)|-1].PreOrder>

dNC(Y)[j].PreOrder and

dNC(X) [|dNC(X)|-1].PostOrder<

countBA++;

add dNC(Y)[j]to dNC(XY);

j++;

if equal=|dNC(X)| and equal=|dNC(Y)| then

r=0;//dNC(X)=dNC(Y)//

else if countAB=|dNC(X)| then

r=1;//dNC(X) ?dNC(Y)//

else if countBA=|dP(Y)| then

r=2;//dNC(X) ?dNC(Y)//

return dNC(XY);

2.2　確定可替代封閉模式

輸入:標準生產(chǎn)數(shù)據(jù)集DB 和閾值ξ。

輸出:可替代封閉模式(ECP)。

Scan DB to construct WPPC-tree with thresholdξand determineE1;

Generate dPidset ofE1;

Let Hashtabe=?

be a hashtable for storing the indexes of ECP;

ifE1has more than element,call dP-expand-E(E1);

Procedure dP-expand-E(Ev);

fori←0 to |Ev|do

begin for

Enext←?;

forj←i+1 to|Ev|do

begin for

(dNC-Set(ECP)andr)←NC-Diff(dNC-Set (Ev[j]),dNC-Set (Ev[i]))

if g(ECP)≤ξ×T then//滿足可替代規(guī)則//

ifr=0 then;

Ev[i]=Ev[i]∪Ev[j];

updateEnext;

removeEv[j];

j--;//兩個數(shù)據(jù)集項目集相同,求交集后去除Ev[j]

else ifr=2 then

Ev[i]=Ev[i]∪Ev[j];

updateEnext

else ifr=1 then//Ev[i]是Ev[j]的子集//

ECP=Ev[i]∪Ev[j];

add ECP toEnext;

removeEv[j];

else ECP=Ev[i]∪Ev[j];

add ECP toEnext;

end for;

if dP-check-closed-property (Ev[i])

then

Eresult←Ev[i];//檢查封閉性

addEv[i]to hashtable withg(Ev[i]) asthe key;

if |Enext| ≥ 1 then

expand-E(Enext)

end for;

function dP-check-closed-property(EP);

ECP←hashtable[g(EP)];//ECP儲存可替代封閉模式//

if ECP is not null then

for each ECP in ECPsdo

if EP?ECP then//可替代模式集屬于可替代封閉模式集。

return false;

return ture;

為了更好地理解ECPM算法,使用前面例子中的數(shù)據(jù)集DB舉例,具體步驟如下:

1)掃描DB一次,找出ξ=40%時的所有可替代項目及其dNC-Setst結(jié)構(gòu)。

2)項目e依次與d,f,h和c組合。ed,eh和ef將由于閾值而被消除,由于dNC(c)?dNC(e),e根據(jù)定理3替換為ec。

3)項目d反復與h,f和c組合。 由于dNC(f)?dNC(d)及dNC(h)?dNC(d),d被替換為dfh,再考慮與c組合，由于g(dfhc)= 750，小于給定閾值時的利潤,所以算法為ECP創(chuàng)建新節(jié)點dfhc。

4)f與h和c組合,分別產(chǎn)生fh和fc。 使用fh和fc來創(chuàng)建fhc,然而,因為dfhc是fhc的超集且具有相同的利潤(750),所以fhc被排除,h與c結(jié)合創(chuàng)建hc。

圖1表示上述4個步驟的具體過程。

圖1　算法具體步驟Fig.1　Algorithm specific step

對表1的標準生產(chǎn)數(shù)據(jù)集DB進行可替代封閉模式算法(ECPM)分析,得出當ξ=40%時，DB中所有的可替代封閉模式及各模式的利潤如表2所示。

表2　DB中當ξ=40%所有可替代封閉模式Tab.2　All ECP for DB with ξ=40%

3　仿真分析

為了驗證本文所提算法的性能,將算法ECPM與常規(guī)類似算法MERIT和Na-MEI在4個曾被大量的關(guān)聯(lián)規(guī)則挖掘算法用于仿真比較的標準生產(chǎn)數(shù)據(jù)庫中進行實驗, 其中兩個是稀疏型數(shù)據(jù)庫Accidents和Pumsb[13-15],另外兩個是來自IBM的密集型數(shù)據(jù)庫T10I4D100K和Connect[14，9],實驗中對算法執(zhí)行時間和內(nèi)存消耗兩個指標進行了分析算法運行環(huán)境:Windows10系統(tǒng),2.3GHz CPU,8G內(nèi)存,表3是仿真數(shù)據(jù)庫的數(shù)據(jù)特征。

表3　仿真所用數(shù)據(jù)庫Tab.3　The simulation dataase

3.1　執(zhí)行時間分析

圖2顯示了不同閾值下ECPM算法、MERIT算法與META算法在標準生產(chǎn)數(shù)據(jù)庫Accidents，Pumsb，T10I4D100K和Connect中的算法執(zhí)行時間，由圖2可知，在這些標準生產(chǎn)數(shù)據(jù)庫中，ECPM算法的執(zhí)行時間明顯優(yōu)于META和MERIT算法，且當ξ= 0.0007，0.0045，0.07，1.5時，META算法的執(zhí)行時間遠遠大于ECPM算法的執(zhí)行時間，雖然META是Apriori算法的升級算法，依然會產(chǎn)生大量的候選項集，由于內(nèi)存限制，當閾值較大時META 算法將無法運行。

3.2　內(nèi)存消耗分析

圖3顯示了在標準生產(chǎn)數(shù)據(jù)集Accidents，Pumsb，T10I4D100K和Connect中，ECPM算法、MERIT算法與META算法關(guān)于內(nèi)存消耗的分析。隨著規(guī)定閾值的增大,內(nèi)存消耗也隨之增加,當閾值較大時,MERIT和META算法占用存幾乎ECPM算法的兩倍。

圖2　Accidents,Rumsb,T10I4D100K和Connect中ECPM算法與其他算法的執(zhí)行時間Fig.2　Execution time of ECPM and other algorithms for Accidents,Rumsb,T10I4D100K and Connect

圖3　Accidents,Pumsb,T10I4D100K和Connect中ECPM算法與其他算法的內(nèi)存消耗Fig.3　Memory consumption of ECPM algorithms and other algorithms for Accidents,Pumsb,T10I4D100K and Connect

4　結(jié)　論

從海量的標準生產(chǎn)數(shù)據(jù)集中分析可替代封閉模式來指導和優(yōu)化智能生產(chǎn)是重要的研究領(lǐng)域,為了降低算法執(zhí)行時間和內(nèi)存消耗,本文提出一種可替代封閉模式挖掘算法(ECPM)，首先，通過定義的可替代規(guī)則對生產(chǎn)數(shù)據(jù)集進行預處理,其次,依據(jù)標準dNC-Sets數(shù)據(jù)結(jié)構(gòu)特性確定各模式的dNC-Sets結(jié)構(gòu)及各模式間的關(guān)系,最后根據(jù)已證明的可替代封閉模式定理基于利潤參數(shù)挖掘出可替代封閉模式,與傳統(tǒng)的META算法和MERIT算法對比，ECPM算法在保證獲得產(chǎn)品部件的最優(yōu)組合的同時，在執(zhí)行時間和內(nèi)存占用方面均有性能提升。

參考文獻：

[1]劉云，向禪.基于虛構(gòu)理論對不平衡數(shù)據(jù)集中少數(shù)類關(guān)聯(lián)規(guī)則挖掘的研究[J].云南大學學報(自然科學版)，2017,39(4):33-38.

[2]梁珺，劉云，基于析取規(guī)則對不確定數(shù)據(jù)挖掘的優(yōu)化研究[J].四川大學學報(自然科學版)，2016,53(4):788-792.

[3]NGUYEN G, LE T, VO B, et al. EIFDD: An efficient approach for erasable itemset mining of very dense datasets[J].Applied Intelligence, 2015, 43(1):85-94.

[4]DENG Z H, FANG G D, WANG Z H, et al. Mining erasable itemsets[C]∥International Conference on Machine Learning and Cybernetics. IEEE, 2009:67-73.

[5]VO B, LE T, COENEN F, et al. Mining frequent itemsets using the N-list and subsume concepts[J].International Journal of Machine Learning & Cybernetics, 2016, 7(2):253-265.

[6]HUYNH-THI-LE Q, LE T, VO B, et al. An efficient and effective algorithm for mining top-rank-k, frequent patterns[J].Expert Systems with Applications, 2015, 42(1):156-164.

[7]VRANIC M, PINTAR D, BANEK M. Towards better understanding of frequent itemset relationships through tree-like data structures[J].Expert Systems with Applications, 2015, 42(3):1717-1729.

[8]DENG Z. Mining top-rank-k, erasable itemsets by PID_lists[J].International Journal of Intelligent Systems, 2013, 28(4):366-379.

[9]DAM T L, LI K, FOURNIER-VIGER P, et al. An efficient algorithm for mining top-rank-k, frequent patterns[J].Applied Intelligence, 2016, 45(1):96-111.

[10] NGUYEN G, LE T, VO B, et al. Discovering erasable closed patterns[C]∥Asian Conference on Intelligent Information and Database Systems. Springer, 2015:368-376.

[11] YUN U, LEE G. Sliding window based weighted erasable stream pattern mining for stream data applications[J].Future Generation Computer Systems, 2016,59:1-20.

[12] LE T, VO B, COENEN F. An efficient algorithm for mining erasable itemsets using the difference of NC-Sets[C]∥IEEE International Conference on Systems, Man, and Cybernetics. IEEE, 2014:2270-2274.

[13] 趙官寶，劉云.一種基于位表的有效頻繁項集挖掘算法[J].山東大學學報(理學版)，2015(5)：23-29.

[14] NGUYEN L T T, NGUYEN N T. An improved algorithm for mining class association rules using the difference of Obidsets[J].Expert Systems with Applications, 2015,42(9):4361-4369.

[15] NGUYEN L T T, NGUYEN N T. Updating mined class association rules for record insertion[J].Applied Intelligence, 2015, 42(4):707-721.