可替代封閉模式對生產數據的優化分析

劉　云，黃亞飛

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

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

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

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

1　模型構建

1.1　定義及定理

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

定義1給定閥值ξ,數據庫DB,定義可替代規則如下:

g(X)≤T×ξ，

(1)

(2)

(3)

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

表1　產品數據庫DBTab.1　Product Database DB

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

1.2　dNCv-Set結構

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

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

例2針對表1中的產品數據集可知,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)中的產品標識符。

例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中的產品數據集,由于

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結構,則有以下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算法

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

2.1　確定dNC-Sets結構及模式間的關系

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

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

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

countAB=0, countBA=0;

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

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]的祖先節點//

begin if

else countBA++,j++;

end if;

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

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]的祖節點//

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　確定可替代封閉模式

輸入:標準生產數據集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//滿足可替代規則//

ifr=0 then;

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

updateEnext;

removeEv[j];

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算法,使用前面例子中的數據集DB舉例,具體步驟如下:

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

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

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

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

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

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

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

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

3　仿真分析

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

表3　仿真所用數據庫Tab.3　The simulation dataase

3.1　執行時間分析

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

3.2　內存消耗分析

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

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

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

4　結　論

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

參考文獻：

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

[2]梁珺，劉云，基于析取規則對不確定數據挖掘的優化研究[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.