基于全局圖遍歷的加權頻繁模式研究

王栓杰 李華 陳智博

【摘要】 在以往的加權遍歷模式應用過程中，挖掘是影響最終應用效果的主要問題。相比之下，在全局圖遍歷基礎上加權頻繁模式的應用能夠有效解決挖掘問題。本文從圖遍歷分析入手，對基于全局圖遍歷的加權頻繁模式進行研究和分析。

【關鍵詞】 全局圖遍歷 加權頻繁模式

一、圖遍歷分析

這里以WWW站點訪問和在線服務系統為例，對圖遍歷進行分析：在該過程中，用戶需要通過超級鏈接等有效形式搜索所需內容或感興趣內容，這個過程是由兩個不同數據點之間的轉換完成的，可將該結構模擬成一個圖，將用戶所訪問的Web頁面中的超級鏈接看成是圖的邊，將Web頁面看成是圖的各個頂點，將用戶的訪問過程看成是該圖中的遍歷。

二、基于全局圖遍歷的加權頻繁模式

1、剪枝策略。數據挖掘是傳統加權遍歷模式應用過程中存在的主要問題之一。剪枝策略的應用則可以有效提升模式的挖掘性能。在剪枝策略中，需要將成為加權頻繁模式可能性較低的候選模式項逐漸減掉，從保留的可能性較高的候選模式項中獲得最終的加權頻繁模式。

2、產生候選項策略。為了獲得新的候選模式項，可以使得原本的擴展模式中存在一個向下閉合特性，進而從該模式的候選模式中獲得新候選模式向。

3、基于全局圖遍歷的加權頻繁模式。這里在結合剪枝策略與產生候選項策略的基礎上，達到從全局圖遍歷中娃聚加權頻繁模式的目的。該目的是通過以下算法步驟實現的：首先，將加權支持度的最小值、遍歷數據庫Q以及加權有向圖W輸入。當上述數據輸入完成后，會獲得加權頻繁模式列表L1的輸出。在后續的計算過程中，首先要將加權頻繁模式可能長度的max找出來，然后將初始化長度設置為1，得出相應的候選模式。第三，需要對當前候選模式的支持度計數進行計算。第四，完成相應加權頻繁模式的確定。第五，從上述操作的數據中得到剪枝候選模式集。

三、基于全局圖遍歷的加權頻繁模式的實驗分析

1、基于全局圖遍歷的加權頻繁模式的實驗環境。計算機為3.03GHz Pentium IV PC，Windows XP Professonal操作系統，內存為812M。上述設備能夠為加權頻繁模式實驗提供SQL Server2000的軟環境，該環境的作用是對WDG和WDG遍歷進行模擬。除此之外，設備還能為實驗提供VC++6.0的軟環境，該環境的作用是實現基于全局圖遍歷的加權頻繁模式挖掘算法。

2、生成合成數據方面。在實驗過程中，全局圖中所含頂點數目Bn以及各個頂點能夠連接邊數量的最大值Ymax是實現DG的兩項主要參數。頂點數目的范圍為100-400；一個頂點連接邊數量的最大值取值范圍為[1，4]。當DG生成過程結束之后，對其中頂點進行隨機賦值，權值Wi的賦值過程完成之后即生成WDG。為了保證后續算法性能比較的有效性，共計生成八組不同的遍歷數據，并將其組成一個數據庫。 將各族遍歷中可遍歷模式長度的最大值變化范圍控制在5-10之間，并對其應用相同的權值集進行計算。

3、性能方面。這里對基于全局遍歷圖的加權頻繁模式挖掘算法與Apriori算法在性能方面的差別進行比較。這里主要講算法的性能比較對象確定為運行執行時間以及可擴展模式數量。就運行執行時間而言，在Max-L為7的情況下，基于全局圖遍歷的加權頻繁模式挖掘算法與Apriori算法的實際運行執行時間會隨著加權支持度最小值的不斷降低而逐漸增加。如果加權支持度最小值越小，二者之間的性能差別則表現得更加明顯。從加權支持度最小值的變化過程中可以發現，由于基于全局圖遍歷的加權頻繁模式挖掘算法的頻繁模式挖掘操作具有權值約束特點，這種特點可以實現對候選集搜索空間的有效控制，且該過程中涉及的剪枝操作較少，進而使得該算法產生較好的性能。相比之下，另一種算法的頻繁模式挖掘不帶權值約束，其搜索模式空間相對較大，因此性能相對較差。就可擴展模式數量而言，在Max-L逐漸減少的情況下，基于全局圖遍歷的加權頻繁模式挖掘算法的可擴展模式數量逐漸增加。

4、可擴展性方面。就基于全局圖遍歷的加權頻繁模式挖掘算法的可擴展性實驗而言，在Max-L為7的情況下，當遍歷圖中頂點數發生減少變化時（其變化范圍為100-400），基于全局圖遍歷的加權頻繁模式挖掘算法的執行時間也會相應地減少。當遍歷圖中包含頂點數增加時，該算法的實際執行時間會發生相應的增加。除了執行時間之外，頂點數量的增加變化還會造成候選集的增大，進而引發其搜索時間的延長。從實驗中可以看出，在EGTG方式下，基于全局遍歷圖的加權頻繁模式挖掘算法的可擴展性較好，其數據集尺寸與實際執行時間之間的關系為分段線性關系。

結論：加權遍歷模式應用存在的主要問題是其無法實現目標數據的有效挖掘。對此，這里通過成為加權頻繁模式可能性較低的候選模式項的剪掉策略以及候選項產生策略的基礎上，得出一種基于全局圖遍歷的加權頻繁模式，該模式挖掘算法具有良好的可擴展性和性能。

參 考 文 獻

[1]耿汝年. 加權頻繁模式挖掘算法研究[D].江南大學，2008.

[2]肖港松，陳曉云. 基于加權動態網絡的頻繁模式挖掘研究[J]. 微型機與應用，2011，19：7-10.