王栓杰 李華 陳智博

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

【關(guān)鍵詞】 全局圖遍歷 加權(quán)頻繁模式

一、圖遍歷分析

這里以WWW站點(diǎn)訪問和在線服務(wù)系統(tǒng)為例，對(duì)圖遍歷進(jìn)行分析：在該過程中，用戶需要通過超級(jí)鏈接等有效形式搜索所需內(nèi)容或感興趣內(nèi)容，這個(gè)過程是由兩個(gè)不同數(shù)據(jù)點(diǎn)之間的轉(zhuǎn)換完成的，可將該結(jié)構(gòu)模擬成一個(gè)圖，將用戶所訪問的Web頁(yè)面中的超級(jí)鏈接看成是圖的邊，將Web頁(yè)面看成是圖的各個(gè)頂點(diǎn)，將用戶的訪問過程看成是該圖中的遍歷。

二、基于全局圖遍歷的加權(quán)頻繁模式

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

2、產(chǎn)生候選項(xiàng)策略。為了獲得新的候選模式項(xiàng)，可以使得原本的擴(kuò)展模式中存在一個(gè)向下閉合特性，進(jìn)而從該模式的候選模式中獲得新候選模式向。

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

三、基于全局圖遍歷的加權(quán)頻繁模式的實(shí)驗(yàn)分析

1、基于全局圖遍歷的加權(quán)頻繁模式的實(shí)驗(yàn)環(huán)境。計(jì)算機(jī)為3.03GHz Pentium IV PC，Windows XP Professonal操作系統(tǒng)，內(nèi)存為812M。上述設(shè)備能夠?yàn)榧訖?quán)頻繁模式實(shí)驗(yàn)提供SQL Server2000的軟環(huán)境，該環(huán)境的作用是對(duì)WDG和WDG遍歷進(jìn)行模擬。除此之外，設(shè)備還能為實(shí)驗(yàn)提供VC++6.0的軟環(huán)境，該環(huán)境的作用是實(shí)現(xiàn)基于全局圖遍歷的加權(quán)頻繁模式挖掘算法。

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

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

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

結(jié)論：加權(quán)遍歷模式應(yīng)用存在的主要問題是其無(wú)法實(shí)現(xiàn)目標(biāo)數(shù)據(jù)的有效挖掘。對(duì)此，這里通過成為加權(quán)頻繁模式可能性較低的候選模式項(xiàng)的剪掉策略以及候選項(xiàng)產(chǎn)生策略的基礎(chǔ)上，得出一種基于全局圖遍歷的加權(quán)頻繁模式，該模式挖掘算法具有良好的可擴(kuò)展性和性能。

參 考 文 獻(xiàn)

[1]耿汝年. 加權(quán)頻繁模式挖掘算法研究[D].江南大學(xué)，2008.

[2]肖港松，陳曉云. 基于加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)的頻繁模式挖掘研究[J]. 微型機(jī)與應(yīng)用，2011，19：7-10.