利用局部圖關聯信息挖掘加權頻繁模式
2008-12-31 00:00:00耿汝年董祥軍張萍須文波
計算機應用研究 2008年9期
摘 要：遍歷模式數據挖掘方法已經在多種應用中被提出，傳統的遍歷模式挖掘僅僅考慮了非加權遍歷。為解決加權遍歷模式挖掘問題，首先提出了一種從EWDG（邊加權有向圖）到VWDG（頂點加權有向圖）的變換模型；基于這種模型，提出了在具有層次特性的局部圖遍歷中，挖掘加權頻繁模式的LGTWFPMiner(局部圖遍歷加權頻繁模式挖掘法)及其支持度/權值界的局部評估方法。針對合成數據的實驗結果表明該算法能夠有效地進行基于圖遍歷的加權頻繁模式挖掘。
關鍵詞：數據挖掘；加權有向圖；遍歷模式；頻繁模式；支持度界
中圖分類號：TP311 文獻標志碼：A
文章編號：1001-3695(2008)09-2687-05
Mining weighted frequent patterns using local graph linking information
GENG Runian1，2，DONG Xiangjun2，ZHANG Ping1，3， XU Wenbo1
(1.School of Information Technology， Jiangnan University， Wuxi Jiangsu 214122， China；2.School of Information Science Technology， Shandong Institute of Light Industry， Jinan 250353， China;3.China Ship Scientific Research Center， Wuxi Jiangsu 214082， China)Abstract:Data mining for traversal patterns has been found useful in several applications. However， traditional model of traversal patterns mining only considered unweighted traversals.This paper proposed a transformable model of EWDG (edgeweighted directed graph) and VWDG (vertexweighted directed graph)to resolve the problem of weighted traversal patterns mining. Based on the model，developed a new algorithm，called LGTWFPMiner(local graph traversalsbased weighted frequent patterns miner)， and its local estimation of support/weightbound to discover weighted frequent patterns from the traversals on graph with a level property. Experimental results of synthetic data show the algorithm is effective to resolve the problem of mining weighted frequent patterns based on graph traversals.
Key words:data mining; WDG; traversal patterns; frequent patterns; support bound
近年來，基于圖遍歷(或圖訪問)的數據挖掘一直是研究熱點。與本文研究內容相關的數據挖掘方向大體可分為兩類:遍歷模式挖掘和加權挖掘。對于遍歷模式挖掘，傳統的圖遍歷模式挖掘沒有考慮加權圖遍歷[1，2];對于加權挖掘，先前的研究工作大多與挖掘加權關聯規則和它的子問題——加權頻繁項集有關[3~5]。國內文獻也有少量對加權數據挖掘的研究[6~9]，對（加權）圖遍歷的數據挖掘的相關研究，目前在相關電子數據庫中還沒有文獻記載。
1 相關基本概念
定義1 加權有向圖。一個加權有向圖是由一組有限的頂點和邊構成，每一條邊由一對有序頂點表示，每一條邊或每一個頂點都帶有一定的權值。
為便于后文中描述，定義下列表示：
G：加權有向圖；
wi:頂點vi的權值；
V：G中的頂點集，V={v1，v2，…，vn}，n為G中的頂點數；
VWDG：頂點加權有向圖；
EWDG：邊加權有向圖。
由定義1易知應當存在兩類WDG：頂點加權有向圖（VWDG）和邊加權有向圖（EWDG）。圖1(a)就是一個擁有六個頂點和八條邊的VWDG。
文中后續部分將會給出EWDG和VWDG的互換模型，因此后續部分的定義和定理的研究對象都是針對VWDG。
定義2 遍歷、遍歷長度、遍歷的權、遍歷數據庫。遍歷就是在一個G中，一組沿著邊方向的連續頂點序列。一個遍歷就是一條路徑(本文假定，在此路徑中沒有重復的頂點和邊)。本質上來說，遍歷就是一個模式。一個遍歷的長度就是遍歷中頂點的個數。遍歷的權值就是遍歷中所有頂點的權值之和。一個遍歷數據庫就是一組遍歷的集合，記為T。
本文用符號P來表示某一遍歷，用|P|表示P的長度，若|P|=m，則稱P為m-模式；圖1(b)是一個從圖1(a)中得到的一個含有六個遍歷的遍歷數據庫T。顯然，由定義1和2，既然存在兩類WDG，那么也應該存在對應的兩類遍歷——VWDG上的遍歷和EWDG上的遍歷，它們是一一對應的，因此下文中統一用VWDG和EWDG表示圖或遍歷，具體含義可根據上下文得到。圖2(a)和(b)分別描述了這兩類遍歷，(c)則是這兩類遍歷的組合。
本質上，兩類WDG可以歸結為一類，在這里本文歸結為VWDG。這是因為在EWDG中兩個頂點和連接它們的帶有權值的邊可以被抽象為在VWDG中帶有相同權值的一個頂點，而頂點之間的邊的權值為0，頂點之間的連接方向參考源EWDG。圖3描述了這種變化方法。其中(a)(c)(e)是EWDG；(b)(d)(g)(h)是VWDG。在圖3(a)(c)中每一個頂點的權值為0，(b)(d)中每一條邊的權值也為0，每一個頂點代表(a)或(c)中對應的兩個頂點及其帶有權值的連接邊區域。例如圖3(b)或(d)中頂點bd、de、ec、bc表示源，(a)(c)中的頂點和對應的邊〈B，D〉、〈D，E〉、〈E，C〉、〈B，C〉。圖3(e)~(h)描述了如何變換EWDG到VWDG。在新產生的VWDG中，每一條邊的方向按如下方法產生:例如在圖3(h)中的頂點de，因為其在(e)的對應區域與兩條名為〈B，D〉和〈E，C〉的有向邊連接，在(h)中存在兩條有向邊〈bd，de〉和〈de，ec〉，其他邊的產生類似。這樣通過這種方法，就能把EDWG變換為VWDG，這種統一有利于簡化基于圖遍歷的模式挖掘問題。實踐中，在Web環境下，圖3(a)(c)中的區域可以代表任意規模大小的子網。
定義3 子遍歷。一個子遍歷就是在一個遍歷中任何一個連續的子序列，也稱為子模式。
性質1 給定一個長度為k的遍歷，其僅存在兩個長度為k-1的子遍歷。長度為k的模式是頻繁的當且僅當其兩個子模式也是頻繁的[2]。
定義6 加權頻繁模式。如果模式P的加權支持度大于或等于給定的最小加權支持度閾值minwsup，則稱P是加權頻繁模式，也就是:
至此，本文所要研究的問題可表示如下:給定一個WDG和一組在圖上的遍歷路徑，去挖掘遍歷集中所有的加權頻繁模式。
2 加權頻繁模式挖掘算法
Apriori算法是挖掘大項集的有效算法[10]，之所以有效是因為它的向下閉合特性，即所有大項集的子集都是頻繁的。然而，對于加權模式，頻繁加權模式的子模式卻不一定是頻繁的(這可從后面的實例分析中得知)，因此不能直接應用此算法去解決加權模式挖掘問題。2.1 剪枝策略
提高挖掘性能的關鍵技術之一就是構造一種剪枝策略，使其盡可能地減少候選項的數量。本文的剪枝策略構思如下:必須剪掉那些沒有可能成為加權頻繁模式的候選模式項，而保留那些將來有可能成為加權頻繁模式的候選模式項。
定義7 可擴展模式。如果一個模式P拓展為更長的模式后，拓展后的模式有可能成為頻繁模式，則稱模式P是可擴展的。
至此，本文把剪枝問題轉換為判斷模式可擴展性問題。為了更好地解決可擴展性問題，現在修正模式的權值界。
定義8 權值/支持度界。假設可能成為加權頻繁模式的最大長度為u，對于一個包含k
推論1 如果sup_count(P)≥sup_bound(P)，(k 證明 由式(5)(7)(8) sup_bound(P)≥sup_bound(Pl)，k 又因為由題意sup_count(P)≥sup_bound(P)，結合式(12) sup_count(P)≥sup_bound(Pl)， 由定理1 模式P是可擴展的。 證畢。 根據定理1和推論1，設計一個剪切算法PSB(pruning by support bounds)。具體細節參見算法1。 算法1 PSB(pruning by support bounds)(Ck，G，u) 輸入：候選模式集Ck，加權有向圖G，u 輸出：剪枝后的模式集C′k for (PCk){//Ck是候選集 if(sup_count(P)≥sup_bound(P))then continue;//P若可擴展則保留，流程跳回到上面的for for(l=k+1;l≤u;l++){ 估計sup_bound (Pl)之值; if(sup_count(P)≥sup_bound(Pl))then break;}//P若是可擴展的則保留 if(l>u)then C′k=Ck-{P};//P若是非可擴展的則剪枝掉 2.2 候選項產生策略 如果在擴展的模式間存在一個向下閉合特性，那么新的候選項集就可以從目前的候選項集中產生。接下來，本文在可擴展的模式之間通過定義一個向下閉合特性設計一個候選項集產生算法。 定義9 部分向下閉合、完全向下閉合特性。如果一個可擴展的k模式〈p1，p2，…，pk〉的子模式(k-1)模式〈p1，p2，…，pk-1〉也是擴展的，就稱它們之間存在一個部分向下閉合特性;如果k模式〈p1，p2，…，pk〉的兩個(k-1)子模式〈p1，p2，…，pk-1〉和〈p2，p3，…，pk〉都是可擴展的，就說它們之間存在一個完全向下閉合特性。 當存在部分向下閉合特性時，可以從一個可擴展的k模式集合Ck產生一個候選(k+1)模式集Ck+1。具體細節見算法2。 算法2 GenCandidate(Ck，G) 輸入：候選模式集Ck，加權有向圖G 輸出：新的模式候選集Ck+1 Ck+1=； for (PCk){//P=〈p1，p2，…，pk〉 for（〈pk，v〉∈G） if (vP)then//保證v不是已在P中的重復點 P擴展為P′=〈p1，p2，…，pk，v〉; Ck+1=Ck+1+P′； 2.3 LGTWFPMiner算法（局部圖遍歷加權頻繁模式挖掘器） 通過將剪枝算法與候選模式產生算法結合在一起，本文得到一個LGTWFPMiner算法用來從圖的遍歷中挖掘加權頻繁模式。算法3給出了具體細節。 算法3 LGTWFPMiner(local graph traversalsbased weighted frequent patterns miner) 輸入: 加權有向圖G，遍歷數據庫T，最小加權支持度minwsup 輸出: 加權頻繁模式列表Lk //步驟a)找出加權頻繁模式的最大可能長度 u=max(length(t))，tT; //步驟b)初始化長度為1的候選模式 C1=V(G); for(k=1;k≤u Ck≠;k++){ //步驟c)計算模式的支持度計數 for tT{ for PCK if (Pt)then P.sup_count++;} //步驟d)確定加權頻繁模式 Lk={P|P∈Ck，wsupport(P)≥minwsup || sup_count(P)≥sup_bound(P)} if(k //步驟e)剪枝候選模式集 Ck=PSB(Ck，G，u); //步驟f)產生新的用于下次循環的候選模式集 Ck+1=Gen_Candidate(Ck，G); 可以看出，算法3具有層次特性。與Apriori Gen Algorithm[10]相比，算法3有很多明顯的細節不同。算法的每一步可概括如下:a)找出加權頻繁模式的最大可能長度，其受遍歷模式最大長度限制;b)用圖中的頂點初始化長度為1的候選項;c)通過掃描遍歷數據庫來獲得候選模式的支持度計數;d)通過考察是否加權支持度大于等于最小加權支持度閾值或者是否支持度計數大于等于支持度界值，來確定加權頻繁模式;e)運用剪枝算法PSB(Ck，G，u)去根據候選模式的可擴展性來實現剪枝操作，剪枝后剩下的模式都是可擴展的;f)子程序GenCandidate(Ck，G)從模式長度為k的候選模式集中產生新的模式長度為k+1候選模式集用于下一次循環中。 3 支持度/權值界值評價 在算法3中，需要評估支持度/權值界，由式(7)知： wbound(Pl)=vj∈Pwj+l-kj=1greatest(wrj) 上式右邊的第一項是k模式P的權值和，第二項是(l-k)個頂點的最大評估權值之和，本文對于第二項的計算標準是根據圖的局部拓撲結構——模式的可到達點來進行評估的，本文把此方式命名為ERV(evaluated by reachable vertices)方式。 3.1 通過圖中可到達點評價——ERV方式 定義10 頂點間距離。頂點間距離就是在WDG中源頂點到達目的頂點經過的邊/弧的數目。 定義11 k可到達頂點。給定一個加權有向圖G，其上一個頂點v的k可到達頂點就是距離頂點v的距離≤k所有的頂點。 在這里，k可到達頂點也可以被看成是以頂點v為圓心，半徑長度為k的圓區域內，v可以到達的所有頂點，顯然k可到達頂點包含所有的(k-1)可到達頂點，即具有層次性和局部特征性。 給定一個k模式P，RV(P，l)(k 算法4 GRV(genreachable vertices)(P，l) VP={tail vertex of P} X=VP;RV=Y=;//Y是一中間變量 for (t=1;t≤l-k;t++) { for（v∈X） for（〈v，w〉∈G） if（wX）then RV=RV∪{w}; X=RV; Y=Y∪RV;RV =;//RV存儲當次循環可到達點集 } RV(P，l)=Y;//Y存儲循環結束后模式的最終可到達點集 例如，對于圖1(a)，R(〈A〉，2) ={B，C}，R(〈A〉，3)={B，C，D，E}。在R(P，l)中，帶有(l-k)最大權值的頂點分別表示為:vr1，vr2，…，vr（l-k）。模式P的l權值界wbound(Pl)和l支持度界 sup_bound(Pl)分別如式(7)(8)所示，那么此時就是在ERV方式下得到的支持度/權值界。例如圖1中， 給定minwsup=5.0，則模式P=〈A〉的3支持度界為 sup_bound(P3)=「5.0×6/「2.0+(6.0+7.0)=2 模式的支持度/權值界在EVR方式評價下有如下性質： 推論2 隨著l的增長，模式P的l權值界wbound(Pl)單調增加，相應地，P的l支持度界sup_bound(Pl)單調減少。 證明 由式(7)(8)容易得證，證明過程略。 推論3 對于pk∈{P|P=〈p1，p2，…，pk〉}，wbound((P{pk})l) ≥wbound(Pl)，相應地，sup_bound((P-{pk})l)≤sup_bound(Pl)。 證明 由式(7)， 因為wbound((P-{pk})l)=vj∈(P-{pk})wj+l-k+1j=1，vrj∈RVl-k+1(P-{pk}) greatest(wrj)vj∈(P-{pk})wj+ l-k+1j=1，vrj∈RVl-k+1(P-{pk})greatest(wrj) ≥ vj∈Pwj+ l-kj=1，vrj∈RVl-k(P)greatest(wrj); 因為vj∈Pwrj+l-kj=1，vrj∈RVl-k(P)greatest(wrj)=wbound(Pl);wbound((P-{pk})l)≥wbound(Pl);進一步，由式（8）sbound((P-{pk})l)≤sbound(Pl) 證畢。 定理2 權值界在EVR評價方式下，可擴展模式與其子模式間存在部分向下閉合特性。即如果k模式是可擴展的，則它的(k-1)子模式Pa=〈p1，p2，…，pk-1〉也是可擴展的。 證明 由定理1知，若P=〈p1，p2，…，pk〉是可擴展的 sup_count(P)≥sup_bound(Pl)(此處|Pl|>|P|)(13) 又因為|Pa|<|P|，由性質2對于Pa sup_count(Pa)≥sup_count(P)，結合式(13) sup_count(Pa)≥sup_count(P)≥sup_bound(Pl)（14） 又因為Pa=P-{pk}，由推論3，結合式(14) sup_bound((Pa)l)≤sup_bound(Pl)≤sup_count(Pa) sup_count(Pa)≥sup_bound((Pa)l)，由定理1 Pa是可擴展的。 證畢 3.2 實例分析 圖4描述了在ERV評估方式下挖掘圖1中的加權頻繁模式過程，其中minwsup=3.0（圖中對于weighted frequent和scalable欄中的數字，數字“1”代表對應的候選模式是加權頻繁模式或是可擴展的模式，數字“0”表示對應的模式是非加權頻繁的或是非可擴展的;符號“×”代表不存在）。 candidatepatterns(P)sup_count(P)sup_bound(P)weightedfrequentwbound(P2)sup_bound(P2)scalable 〈A〉490921 〈B〉3401221 〈C〉4311121 〈D〉1301811 〈E〉3501621 〈F〉120××0 (a) candidatepatterns(P)sup_count(P)sup_bound(P)weightedfrequentwbound(P3)sup_bound(P3)scalable 〈A，B〉1301420 〈A，C〉2211321 〈B，C〉2211621 〈B，D〉0202310 〈C，E〉3212311 〈E，D〉1202211 〈D，F〉010××0 〈E，F〉120××0 (b) candidatepatterns(P)sup_count(P)sup_bound(P)weightedfrequentwbound(P4)sup_bound(P4)scalable 〈A，C，E〉1202511 〈B，C，E〉2212811 〈C，E，D〉1202911 〈C，E，F〉111××0 〈E，D，F〉010××0 (c) candidate patterns(P)sup_count(P)sup_bound(P)weighted frequent 〈A，C，E，D〉111 〈A，C，E，F〉010 〈B，C，E，D〉020 〈B，C，E，F〉111 〈C，E，D，F〉010 (d) 圖4 ERV方式評估支持度/權值界，挖掘圖1中的加權頻繁模式過程 從圖4(a)中可以看出，長度為1的6個模式不都是可擴展的，因此需要根據算法1進行剪枝操作(在剪枝工作過程中，判斷模式支持度/權值界值時，用到算法4)，然后根據算法2產生下一次循環所需的候選模式集，再對新產生的候選模式重復算法3的步驟，依次類推，最終得出此遍歷數據庫中的加權頻繁模式集為{〈C〉，〈A，C〉，〈B，C〉，〈C，E〉，〈B，C，E〉，〈C，E，F〉〈A，C，E，D〉，〈B，C，E，F〉}。 此外，在判斷模式是否可擴展時，是根據模式頂點所在的局部圖結構來判斷的。例如在判斷Pi是否擴展時，要求解sup_bound(Pi+1)，然后判斷sup_count(Pi)與sup_bound(Pi+1)的關系來決定是否Pi可擴展，也就是說僅僅按照圖的拓撲結構，搜索模式擁有頂點的附近局部圖區域，這樣搜索下去直到模式達到最大值。從上面實例中明顯能看出算法搜索的區域具有層次性。 4 實驗 實驗環境如下:機器采用768 MB內存，2.93 GHz P4 PC機，操作系統為Windows XP，算法實現環境為VC++ 6.0和SQL Server 2000，實驗數據是合成數據，實驗中采用hashtree數據結構[10]。 4.1 合成數據的生成 實驗中加權圖根據以下主要參數實現:頂點數目Vn和與每個頂點連接的最大邊數Emax。隨后，本文采用隨機方法給每個頂點賦予權值w。為了便于比較算法性能，生成了八組遍歷數據庫，每組都采用同樣的權值集，權重分布如圖5所示，所有測試結果都是取八組遍歷數據庫的平均值。具體參數設置如表1所示。 表1 實驗參數 參數名稱參數含義實驗采用值 Vn頂點數目100 En有向邊數400 Emax每個頂點連接的最大邊數1≤Emax≤4 w頂點權值范圍0<w≤10 minwsup最小加權支持度閾值1，2，3，4，5 |T|每組遍歷數10 000 num_TSet遍歷組數8 max_l每組遍歷中最大可遍歷模式長度5，6，7，8，9，10 4.2 算法性能評估 實驗研究了不同的最小支持度閾值、最大可遍歷模式長度、可擴展模式數與運行時間之間的關系。 圖6顯示了可擴展模式數目隨max_l的變化趨勢。圖中顯示:隨著max_l的增加，可擴展模式數越來越小。 圖7顯示了隨著minwsup的增加，執行時間減少；隨著max_l的增加，執行時間減少。這是因為隨著minwsup的增加，候選模式減少，相應的搜索和剪枝等操作隨之減少，執行時間就減少。 圖8顯示了算法針對頂點數和遍歷事務數的可擴展性，實驗中max_l=7，從圖中可以看出算法具有良好的伸縮性。圖8(a)顯示了算法針對不同頂點數和執行時間的關系：隨著頂點數的增加，執行時間增加。這是因為頂點增加，hashtree不斷增大，基于hashtree的搜索時間就不斷增加。(b)顯示了算法針對不同事務數和執行時間的關系：隨著|T|的增加，執行時間也不斷增加。 5 結束語 本文探討了通過遍歷加權有向圖來挖掘頻繁模式的問題，提出了一種從EWDG到VWDG的變換模型；基于這個模型，提出了一種全新的挖掘算法LGTWFPMiner。在算法中，用到了支持度/權值界概念，并通過局部圖遍歷方式對模式支持度/權值界進行評價，最后通過實驗對算法性能進行了驗證。實驗結果表明算法在運行性能和可伸縮性等方面具有良好的效果。 如何把文中提到的模型和算法拓展到更大范圍（如Web尺寸規模)、是否可以進一步優化算法以及如何把此算法付諸實踐將是筆者進一步研究的內容。 參考文獻： ［1］CHEN M S，PARK J S，YU P S.Efficient data mining for path traversal patterns[J].IEEE Trans on Knowledge and Data Engineering，1998，10(2):209-221. [2]NANOPOULOS A，MANOLOPOULOS Y.Mining patterns from graph traversals[J].Data and Knowledge Engineering，2001，37(3):243-266. [3]CAI C H，ADA W C，FU W C，et al.Mining association rules with weighted items[C]//Proc of International Database Engineering and Applications Symposium.Washington DC:IEEE Computer Society，1998:6877. [4]TAO Feng，MURTAGH F，FARID M.Weighted association rule mining using weighted support and significance framework[C]//Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2003:661-666. [5]YUN U.Mining lossless closed frequent patterns with weight constraints[J].KnowledgeBased Systems，2007，20(1):86-97. [6]段軍，戴居豐.基于多支持度的挖掘加權關聯規則算法[J].天津大學學報，2006，39(1):114118. [7]歐陽繼紅，王仲佳，劉大有.具有動態加權特性的關聯規則算法[J].吉林大學學報:理學版，2005，43(3):314-319. [8]陸建江.加權關聯規則挖掘算法的研究[J].計算機研究與發展，2002，39(10):12811286. [9]王運鵬，胡修林，阮幼林.一種最大頻繁模式的快速挖掘算法[J].計算機應用研究，2006，23(10):86-88. [10]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules[C]//Proc of the 20th International Conference on Very Large DataBases.San Francisco:Morgan Kaufmann Publishers Inc，1994:487-499.
