稀疏數(shù)據(jù)源頻繁模式挖掘并行算法

鄭曉艷，孫濟(jì)洲

(1. 天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072；2. 天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津 300222)

頻繁模式挖掘在數(shù)據(jù)挖掘中起著非常重要的作用，目前已經(jīng)提出的頻繁模式挖掘算法大致可歸結(jié)為2類．第 1類是產(chǎn)生候選集的算法，這類算法主要應(yīng)用 Apriori性質(zhì)[1]，遞歸地從 k頻繁模式中產(chǎn)生 k+1候選模式，通過(guò)掃描數(shù)據(jù)庫(kù)確定一個(gè)候選模式是否是頻繁的．第 2類是基于 FP-tree[2]的方法，該方法建立一棵前綴樹(shù)，稱為 FP-tree，只對(duì)數(shù)據(jù)庫(kù)掃描一遍，將數(shù)據(jù)庫(kù)所包含的模式信息保存在這棵樹(shù)上，從 FP-tree上挖掘頻繁模式．在以上方法的基礎(chǔ)上發(fā)展了相當(dāng)多的并行算法，影響較大的有 CD(count distribution)算法、DD(data distribution)算法[3]，PDM (parallel data mining)算法[4]．CD算法在各處理器上水平劃分?jǐn)?shù)據(jù)庫(kù)，采用冗余計(jì)算避免處理器之間的通信，所以該算法的通信量小，但是不能充分利用整個(gè)系統(tǒng)的內(nèi)存．DD算法在處理器之間劃分頻繁項(xiàng)集，解決了計(jì)算規(guī)?？梢噪S節(jié)點(diǎn)個(gè)數(shù)增加而增加的問(wèn)題，但是處理器之間的廣播帶來(lái)了很大的通信負(fù)載，在節(jié)點(diǎn)增加時(shí)也增加了通信的開(kāi)銷．CD算法和DD算法都存在對(duì)每個(gè)候選集需要掃描整個(gè)數(shù)據(jù)庫(kù)的問(wèn)題，以及每次掃描結(jié)束時(shí)各個(gè)處理器需要同步的問(wèn)題．PDM 算法和CD算法類似，用Hash表維護(hù)局部候選k項(xiàng)集．為了構(gòu)成全局候選項(xiàng)集，采用一種稱為 clue-and-poll的技術(shù)，只選取少量可能滿足支持度要求的表項(xiàng)在處理器之間交換，并且實(shí)現(xiàn)了Hash表的并行生成，算法在候選集增大的時(shí)候有較好的可擴(kuò)展性．

MLFPT(multiple local frequent pattern tree)算法[5]是在共享存儲(chǔ)結(jié)構(gòu)上提出的基于 FP-tree的頻繁項(xiàng)集挖掘算法．均勻劃分?jǐn)?shù)據(jù)庫(kù)，每個(gè)處理器生成一個(gè)局部頻繁模式樹(shù)，并在所有處理器之間共享．只對(duì)數(shù)據(jù)庫(kù)掃描 2次，而且不會(huì)產(chǎn)生大量頻繁項(xiàng)集，對(duì)長(zhǎng)規(guī)則的適應(yīng)性很強(qiáng)．但是當(dāng)處理稀疏數(shù)據(jù)時(shí)，由于FP-tree上的可共享節(jié)點(diǎn)減少，造成樹(shù)結(jié)構(gòu)過(guò)大，效率甚至低于Apriori類算法．

實(shí)際上，很多應(yīng)用數(shù)據(jù)庫(kù)呈現(xiàn)稀疏狀態(tài)，如超市的銷售數(shù)據(jù)庫(kù)．有少部分文獻(xiàn)論述了當(dāng)數(shù)據(jù)源為勻質(zhì)或非勻質(zhì)時(shí)算法的運(yùn)行效率問(wèn)題以及解決方法．但專門針對(duì)某種特殊數(shù)據(jù)源進(jìn)行的研究還不多見(jiàn)．陳惠萍等[6]針對(duì)稀疏數(shù)據(jù)源提出了 FP-tree和支持度數(shù)組相結(jié)合的方法挖掘最大頻繁項(xiàng)集，用二維數(shù)組保存所有可能的頻繁2項(xiàng)集的支持度，用于查找某個(gè)項(xiàng)目的條件模式庫(kù)中的所有頻繁項(xiàng)．文獻(xiàn)[7]中也用到了類似的二維矩陣．該方法減少了遍歷 FP-tree的次數(shù)，但是也引入了一定的時(shí)間和空間開(kāi)銷．而且仍然采用 FP-tree存儲(chǔ)數(shù)據(jù)庫(kù)信息，如果對(duì)其并行化，建立FP-tree仍然是算法的瓶頸．

另外，由于消息傳遞模型和共享存儲(chǔ)模型在計(jì)算性能上的明顯差異，大部分算法都是在消息傳遞計(jì)算模型上提出的．實(shí)際上，共享存儲(chǔ)計(jì)算模型在程序設(shè)計(jì)時(shí)由于不需考慮消息傳遞的時(shí)間、對(duì)象和內(nèi)容，編程方面具有非常大的優(yōu)勢(shì)，但在傳統(tǒng)的共享存儲(chǔ)模型上，這些程序設(shè)計(jì)方面的優(yōu)勢(shì)也正是計(jì)算性能差的主要原因．為了提高共享存儲(chǔ)計(jì)算環(huán)境的性能，Huang等[8]提出了一種面向視圖的并行編程(view oriented parallel programming，VOPP)思想，用視圖作為一致性維護(hù)的基本單元．程序員可以根據(jù)算法特點(diǎn)把數(shù)據(jù)對(duì)象劃分成多個(gè)視圖．VODCA (view-oriented，distributed，cluster-based approach)[9]是基于 VOPP 實(shí)現(xiàn)的面向視圖的分布式集群計(jì)算方法，實(shí)現(xiàn)了一致性維護(hù)中的時(shí)間選擇、處理器選擇和數(shù)據(jù)選擇，借鑒了Trademarks的內(nèi)存維護(hù)策略并進(jìn)行改進(jìn)，解決了Trademarks中 diffs積累問(wèn)題．使得其計(jì)算性能較傳統(tǒng)的共享存儲(chǔ)計(jì)算環(huán)境有了很大的提高[10]．

本文針對(duì)稀疏數(shù)據(jù)源，設(shè)計(jì)了一種鏈表結(jié)構(gòu)，提出了稀疏數(shù)據(jù)源頻繁項(xiàng)集挖掘并行算法(parallel mining frequent itemsets from sparse data source，PMFSD)，并在VODCA上實(shí)現(xiàn)．

1 FI-list設(shè)計(jì)和構(gòu)造

為了提高頻繁項(xiàng)集的計(jì)算速度，F(xiàn)I-list的設(shè)計(jì)和構(gòu)造主要從3個(gè)方面加以考慮：①減少數(shù)據(jù)庫(kù)掃描次數(shù)以降低 I/O數(shù)量；②及時(shí)有效地對(duì)數(shù)據(jù)進(jìn)行剪枝以減少候選集的數(shù)量；③避免保存大量候選項(xiàng)集以降低內(nèi)存占用量．

1.1 FI-list的設(shè)計(jì)

鏈表結(jié)構(gòu)體 FI-list的設(shè)計(jì)借鑒了稀疏矩陣的列壓縮存儲(chǔ)策略．稀疏矩陣的基本列壓縮存儲(chǔ)格式是使用 3個(gè)數(shù)組 AA、JA和 IA，數(shù)組 AA存儲(chǔ)按 1～n列排列的非零矩陣元素，整型數(shù)組JA表示AA中對(duì)應(yīng)元素所在的行號(hào)，整型數(shù)組 IA中的元素是每一列的開(kāi)始在 JA中的索引號(hào)．把源數(shù)據(jù)庫(kù)看作一個(gè)稀疏矩陣，每個(gè)事務(wù)表示一個(gè)行向量，每個(gè)項(xiàng)目代表一個(gè)列向量．如果頻繁模式挖掘中使用的輸入數(shù)據(jù)是二元的，即只要求明確項(xiàng)目是否是非零的，數(shù)據(jù)源就可以被看作一個(gè)二元稀疏矩陣，如圖1所示．

圖1 示例數(shù)據(jù)源Fig.1 Instance of data source

該矩陣采用標(biāo)準(zhǔn)列壓縮格式可以存儲(chǔ)為

因?yàn)榫仃囀嵌?，非零?shù)據(jù)即是 1，無(wú)須專門記錄，所以數(shù)組 AA可以省略．本文在此基礎(chǔ)上對(duì)以上表示方法加以改造，只保留數(shù)組JA．在其中增加每個(gè)列的開(kāi)始標(biāo)記，這里用數(shù)字0來(lái)表示．

算法實(shí)現(xiàn)中可以對(duì)以上存儲(chǔ)結(jié)果進(jìn)一步壓縮，根據(jù)設(shè)定的最小支持?jǐn)?shù)，從中去除支持?jǐn)?shù)小于最小支持?jǐn)?shù)的項(xiàng)集所對(duì)應(yīng)的列信息，例如，最小支持?jǐn)?shù)為2時(shí)，上述矩陣最終變換為

經(jīng)過(guò)對(duì)數(shù)據(jù)庫(kù)的二元映射和存儲(chǔ)變換之后，對(duì)頻繁項(xiàng)集的計(jì)數(shù)掃描就可以在一維鏈表上進(jìn)行了．

如圖 2所示，鏈表結(jié)構(gòu)體由 2部分構(gòu)成：項(xiàng)目頭表(HB)和事務(wù)鏈表(TL)．其中HB用于存放產(chǎn)生的頻繁項(xiàng)集和相應(yīng)的支持度、地址信息，每一個(gè)表項(xiàng)有3個(gè)域，內(nèi)容(Contents)域保存項(xiàng)集內(nèi)容，支持度(Sup)域保存各項(xiàng)集的支持度，地址(Add)域存放與該項(xiàng)集相關(guān)的事務(wù)鏈表頭．TL是一個(gè)線性鏈表，存放與項(xiàng)集相關(guān)的事務(wù)號(hào)(TID)序列．事務(wù)號(hào)序列T(ISi)＝Ti,k1，Ti,k2, … ,Ti,ksi(i = 1,2,… ,n )，其中 k1＜ k2＜ …＜ksi．

圖2 頻集鏈表結(jié)構(gòu)體Fig.2 Unit of frequent itemsets list

數(shù)據(jù)集越稀疏，與每個(gè)項(xiàng)目相關(guān)的事務(wù)數(shù)目越少，相關(guān)的交易鏈長(zhǎng)度越?。ǔＴ陬l繁 2-項(xiàng)集之后，隨著頻繁項(xiàng)集長(zhǎng)度增加，相關(guān)的事務(wù)數(shù)目急劇減少，整個(gè)鏈表尺寸很小，容易裝入內(nèi)存．但在非稀疏數(shù)據(jù)集情況下，由于鏈結(jié)構(gòu)的開(kāi)銷，整個(gè)鏈表實(shí)際尺寸會(huì)大于相應(yīng)的二元數(shù)據(jù)庫(kù)，需要更多的存儲(chǔ)空間．

FI-list結(jié)構(gòu)也可以在其他共享內(nèi)存編程環(huán)境和消息傳遞平臺(tái)上使用，作為稀疏數(shù)據(jù)源頻繁項(xiàng)集挖掘的數(shù)據(jù)結(jié)構(gòu)．在消息傳遞平臺(tái)上，整個(gè) k-項(xiàng)集相關(guān)信息和鏈表可以在處理器之間進(jìn)行復(fù)制，作為計(jì)算k+1項(xiàng)集的依據(jù)．另外需要一個(gè)事務(wù)長(zhǎng)度表 LB，記錄每個(gè)事務(wù)的長(zhǎng)度，用于產(chǎn)生候選集時(shí)的剪枝條件．

1.2 FI-list的構(gòu)造

構(gòu)造FI-list有如下4個(gè)步驟．

(1)對(duì)數(shù)據(jù)庫(kù)按行掃描一次，統(tǒng)計(jì)各個(gè)事務(wù)的長(zhǎng)度，生成LB．

(2)對(duì)數(shù)據(jù)庫(kù)按列掃描一次，按設(shè)定的最小支持度，生成頻繁 1-項(xiàng)集；每生成一個(gè)頻繁 1-項(xiàng)集，按第1.1節(jié)中TM所示的順序向事務(wù)細(xì)節(jié)表TL寫入與該項(xiàng)目相關(guān)的事務(wù)號(hào)序列，同時(shí)向頭表HB中寫入該列對(duì)應(yīng)的項(xiàng)目?jī)?nèi)容和支持度，并且使地址域指向TL．

(3)按照 Apriori性質(zhì)，從(k-1)-項(xiàng)集生成 k-項(xiàng)集，同時(shí)根據(jù) LB表進(jìn)行剪枝．此過(guò)程由函數(shù) Gen()遞歸實(shí)現(xiàn)．

(4)直到不能生成更高維頻繁項(xiàng)集，F(xiàn)I-list構(gòu)造結(jié)束．此時(shí)FI-list中保存了所有頻繁項(xiàng)集及其支持度．

Gen函數(shù)所包含的算法如下：

2 VODCA環(huán)境下PMFSD算法實(shí)現(xiàn)

2.1 VODCA編程環(huán)境的特點(diǎn)

VODCA程序編譯使用標(biāo)準(zhǔn)C或者C++編譯器，程序中只須包含其提供的頭文件，即可調(diào)用并行計(jì)算所需的相關(guān)系統(tǒng)常數(shù)和視圖操作原語(yǔ)．程序員的主要工作是根據(jù)算法和數(shù)據(jù)結(jié)構(gòu)的特征，把共享數(shù)據(jù)劃分成視圖，并且在程序中正確使用視圖．對(duì)視圖的劃分和使用要考慮4個(gè)特點(diǎn)：①視圖的內(nèi)容可以根據(jù)算法和數(shù)據(jù)的特點(diǎn)任意劃分；②視圖一旦確定，在整個(gè)程序中不能改變；③每次只能對(duì)一個(gè)視圖進(jìn)行排他訪問(wèn)，但是允許對(duì)一個(gè)或多個(gè)視圖嵌套使用只讀訪問(wèn)；④無(wú)論算法中對(duì)共享數(shù)據(jù)的訪問(wèn)是否存在爭(zhēng)用，任何對(duì)共享數(shù)據(jù)的操作(包括只讀訪問(wèn)和讀寫訪問(wèn))都必須調(diào)用視圖訪問(wèn)原語(yǔ)(只讀訪問(wèn)原語(yǔ)或者排他訪問(wèn)原語(yǔ))．

2.2 問(wèn)題中的視圖定義

由于共享內(nèi)存結(jié)構(gòu)上編程的方便性，算法實(shí)現(xiàn)不必考慮數(shù)據(jù)的分布．根據(jù) VOPP的特點(diǎn)，劃分視圖成為了算法實(shí)現(xiàn)的焦點(diǎn)問(wèn)題．算法中涉及到的共享數(shù)據(jù)包括：數(shù)據(jù)源 DB、事務(wù)長(zhǎng)度表 LB和 FI-list．其中對(duì)DB的共享訪問(wèn)是只讀的，整個(gè)DB可以定義為一個(gè)視圖．生成 LB時(shí)需要進(jìn)行寫訪問(wèn)，可以按任務(wù)劃分定義視圖，例如有 n個(gè)處理器，則對(duì)事務(wù)長(zhǎng)度的統(tǒng)計(jì)就劃分成n個(gè)任務(wù)，每個(gè)任務(wù)相關(guān)的LB部分定義為一個(gè)視圖．FI-list要保存所有的頻繁項(xiàng)集，每次產(chǎn)生一個(gè)新的頻繁項(xiàng)集，都會(huì)發(fā)生對(duì)它的寫操作，所以對(duì)FI-list相關(guān)視圖的劃分是程序設(shè)計(jì)的重點(diǎn)．

視圖劃分結(jié)果如圖 3表示．對(duì)項(xiàng)目頭表 HB，每個(gè) k-項(xiàng)集(k＝1，2，…，m)的全體劃分為一個(gè)視圖，而對(duì)事務(wù)鏈表 TL，每個(gè)鏈劃分為一個(gè)視圖．這些視圖都是在算法運(yùn)行過(guò)程中動(dòng)態(tài)產(chǎn)生的，每個(gè)視圖可以通過(guò)編程獲得唯一的編號(hào)．這樣劃分視圖主要依據(jù)以下3個(gè)方面．

(1) 每個(gè) k-項(xiàng)集的相關(guān)信息只在生成 k-項(xiàng)集時(shí)要求讀寫訪問(wèn)，在使用 k-項(xiàng)集生成(k+1)-項(xiàng)集時(shí)，k-項(xiàng)集的相關(guān)信息是只讀共享的．所以只需考慮在生成k-項(xiàng)集時(shí)對(duì)數(shù)據(jù)對(duì)象訪問(wèn)的特點(diǎn)．

(2) 每個(gè)處理器每次向 HB寫入一個(gè) k-項(xiàng)集信息時(shí)，首先必須互斥地獲得一個(gè)表項(xiàng)地址，所以對(duì)HB表尾的一次排他訪問(wèn)是不可避免的，將 k-項(xiàng)集的全體定義為一個(gè)視圖，可以直接保證這個(gè)排他訪問(wèn)．另外由于向 HB中寫入的信息相對(duì)較少，只有 3個(gè)數(shù)據(jù)，所以不會(huì)形成嚴(yán)重的計(jì)算瓶頸．

(3) 每個(gè)項(xiàng)集相關(guān)的事務(wù)數(shù)目相對(duì)較多，特別是在 k值較小時(shí)更是如此，為了提高算法的并行度，應(yīng)該允許多個(gè)處理器同時(shí)生成各自的事務(wù)鏈．所以每個(gè)事務(wù)鏈定義為一個(gè)視圖．

圖3 視圖劃分結(jié)果Fig.3 Division of views

2.3 任務(wù)分配方案

算法的執(zhí)行分成 2個(gè)階段：第 1階段，2次掃描數(shù)據(jù)庫(kù)，第1次生成事務(wù)長(zhǎng)度表LB，第2次生成頻繁1-項(xiàng)集和對(duì)應(yīng)的事務(wù)細(xì)節(jié)表；第 2階段，生成頻繁 k-項(xiàng)集．第1階段采用靜態(tài)任務(wù)分配策略，設(shè)有n個(gè)處理器，則把任務(wù)平均劃分成 n個(gè)，各處理器各自生成一部分頻繁 1-項(xiàng)集．在算法的第 2階段，設(shè)系統(tǒng)中有n個(gè)處理器，m 個(gè)(k-1)-項(xiàng)集．則每次生成 k-項(xiàng)集的任務(wù)劃分成 m-1個(gè)，任務(wù) i(i＝1，2，…，m-1)對(duì)應(yīng)第 i個(gè)(k-1)-項(xiàng)集與第 j個(gè)(k-1)-項(xiàng)集的連接，其中j＝i+1，i+2，…，m．所有處理器在生成 k-項(xiàng)集開(kāi)始之前同步，并將全部(k-1)-項(xiàng)集放到本地的局部數(shù)據(jù)對(duì)象上，每次處理器 p取到一個(gè)任務(wù)并完成之后，將本次得到的k-項(xiàng)集加入HB．

顯然，隨著 i的增加，第 i個(gè)(k-1)-項(xiàng)集的連接對(duì)象有 m-i個(gè)，任務(wù)的計(jì)算量逐漸減少．另外由于一個(gè)任務(wù)連接生成的項(xiàng)集不一定是頻繁的，即一個(gè)任務(wù)中是否包含支持度計(jì)數(shù)和寫回全局 FI-list是不確定的，所以任務(wù)的大小是未知的．在任務(wù)數(shù)量和每個(gè)任務(wù)的大小都是動(dòng)態(tài)確定的情況下，為了保持各個(gè)進(jìn)程之間的負(fù)載平衡，這個(gè)階段采用動(dòng)態(tài)任務(wù)分配．采用任務(wù)池模型，定義一個(gè)讀寫視圖 V，用于控制任務(wù)分配．V的值對(duì)應(yīng)當(dāng)前任務(wù)編號(hào)，取值范圍[1，m-1]．處理器在取到一個(gè)任務(wù)之后，對(duì)V執(zhí)行增1操作．

2.4 算法描述

算法的第 1階段比較簡(jiǎn)單，這里不再詳細(xì)描述，下面給出算法第2階段的描述．

對(duì)于系統(tǒng)中的第i個(gè)節(jié)點(diǎn)，

輸入：FI-list中的(k-1)-項(xiàng)集以及相關(guān)事務(wù)鏈表；最小支持度min_sup；

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)所用的集群由16臺(tái)運(yùn)行Red Hat Linux9.0的個(gè)人計(jì)算機(jī)構(gòu)成，通過(guò)100,Mb/s交換機(jī)連接．每臺(tái)計(jì)算機(jī)帶有 650,MHz的處理器和 128 M 內(nèi)存，硬盤16,G，虛擬頁(yè)面大小為4,kB．實(shí)驗(yàn)所用的數(shù)據(jù)庫(kù)是某超市的銷售數(shù)據(jù)庫(kù)，共 250,850條事務(wù)，所賣商品劃分為107個(gè)類別，有用數(shù)據(jù)量約為20%，實(shí)驗(yàn)用來(lái)發(fā)現(xiàn)這些商品類別在銷售中的關(guān)系．

實(shí)驗(yàn)分別做了3個(gè)方面的研究：①為了考察PMFSD在處理節(jié)點(diǎn)增加情況下的可擴(kuò)展性能，在數(shù)據(jù)量和最小支持度不變、節(jié)點(diǎn)個(gè)數(shù)變化情況下計(jì)算算法的加速比；②為了觀察PMFSD算法對(duì)數(shù)據(jù)量的可擴(kuò)展能力，在節(jié)點(diǎn)數(shù)量確定為8、支持度確定為1%，事務(wù)數(shù)量變化情況下計(jì)算算法的運(yùn)行時(shí)間；③為了觀察PMFSD算法對(duì)數(shù)據(jù)源稀疏程度的適應(yīng)能力，采用隨機(jī)生成的二元矩陣(事務(wù)200,000條，項(xiàng)目50個(gè))，在支持度確定為1%，數(shù)據(jù)稀疏程度不同情況下比較PMFSD算法的運(yùn)行時(shí)間．為了對(duì)比算法的性能，選擇了MLFPT算法[5]，MLFPT也是在共享存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)的，在系統(tǒng)結(jié)構(gòu)上具有可比性．實(shí)驗(yàn)結(jié)果見(jiàn)圖4～圖6．

圖4 PMFSD的加速比Fig.4 Speedup of PMFSD on VODCA

圖5 事務(wù)量變化運(yùn)行時(shí)間Fig.5 Running time on different number of transactions

圖6 稀疏度變化運(yùn)行時(shí)間Fig.6 Running time on different sparse data sources

3.2 結(jié)果分析

圖 4的實(shí)驗(yàn)結(jié)果顯示加速比在處理器數(shù)目小于8時(shí)基本保持線性增長(zhǎng)，但是在 16個(gè)處理器時(shí)增加幅度減?。@是因?yàn)樘幚砥髟龆鄷r(shí)系統(tǒng)中存在的同步消息增多，對(duì)共享數(shù)據(jù)的競(jìng)爭(zhēng)加劇，這個(gè)情況可能會(huì)隨著問(wèn)題規(guī)模的變化而有所變化．圖5顯示當(dāng)處理的事務(wù)數(shù)量增加時(shí)，2種算法的運(yùn)行時(shí)間比較．PMFSD運(yùn)算效率呈先增加后降低的趨勢(shì)，在150,000條數(shù)據(jù)左右，效率最高，之后開(kāi)始下降．開(kāi)始效率增加是因?yàn)殡S著計(jì)算量的增大，計(jì)算/通信比增加．而數(shù)據(jù)量增大的同時(shí)，每個(gè)節(jié)點(diǎn)上的內(nèi)存需求增大，特別是在支持度較小時(shí)，頻繁 1-項(xiàng)集和頻繁 2-項(xiàng)集的數(shù)量都很大，可能由于缺頁(yè)中斷，而使得計(jì)算速度下降．同樣，數(shù)據(jù)稀疏程度的變化也會(huì)產(chǎn)生類似情況．這種情況也能從圖 6所示的實(shí)驗(yàn)結(jié)果中得到驗(yàn)證，數(shù)據(jù)集越稀疏，與每個(gè)項(xiàng)目相關(guān)的事務(wù)數(shù)目越少，相關(guān)的交易鏈長(zhǎng)度越?。ǔＴ陬l繁2-項(xiàng)集之后，隨著頻繁項(xiàng)集長(zhǎng)度的增加，相關(guān)的事務(wù)數(shù)目急劇減少，整個(gè)鏈表的尺寸很小，容易裝入內(nèi)存，所以計(jì)算速度很快．當(dāng)非零數(shù)據(jù)增多時(shí)，由于鏈結(jié)構(gòu)的開(kāi)銷，整個(gè)鏈表尺寸實(shí)際上會(huì)大于相應(yīng)的二元數(shù)據(jù)庫(kù)，需要駐留本地內(nèi)存的數(shù)據(jù)增多，處理?yè)Q頁(yè)的開(kāi)銷達(dá)到一定比例，就會(huì)致使計(jì)算速度下降．采用MLFPT算法時(shí)，數(shù)據(jù)源越稀疏，F(xiàn)P-tree上的共享前綴越少，產(chǎn)生的 FP-tree也就越大，在生成 FP-tree和計(jì)算條件模式庫(kù)時(shí)會(huì)明顯增加掃描時(shí)間，從圖 6可以看出，2種算法隨數(shù)據(jù)源稀疏度變化的運(yùn)算時(shí)間對(duì)比非常顯著．

算法的執(zhí)行時(shí)間由4個(gè)部分組成：系統(tǒng)啟動(dòng)時(shí)間tstart，掃描數(shù)據(jù)庫(kù)所需時(shí)間 tscan，連接和依照單調(diào)性剪枝時(shí)間 tconn，計(jì)算支持?jǐn)?shù)和寫入鏈表信息所需時(shí)間tlist．其中 tstart由系統(tǒng)確定．掃描數(shù)據(jù)庫(kù)時(shí)間 tscan涉及到實(shí)際計(jì)算時(shí)間和數(shù)據(jù)裝入本地所需的通信時(shí)間，可以描述為數(shù)據(jù)規(guī)模的線性函數(shù)，不對(duì)性能評(píng)價(jià)產(chǎn)生影響．頻繁 k-項(xiàng)集的數(shù)目與最小支持度和項(xiàng)目數(shù)有關(guān)，當(dāng)數(shù)據(jù)源為稀疏數(shù)據(jù)源時(shí)，頻繁2-項(xiàng)集之后的頻繁項(xiàng)集數(shù)目會(huì)急劇減少，tconn主要發(fā)生在頻繁 3-項(xiàng)集產(chǎn)生之前，當(dāng)頻繁項(xiàng)集數(shù)目增加時(shí)，HB的尺寸增大，連接和剪枝操作會(huì)導(dǎo)致更多的換頁(yè)，換頁(yè)概率正比于頻繁項(xiàng)集數(shù)目．項(xiàng)集的支持?jǐn)?shù)計(jì)數(shù)和寫入事務(wù)細(xì)節(jié)的時(shí)間 tlist與事務(wù)數(shù)目和數(shù)據(jù)稀疏度有關(guān)，當(dāng)與一個(gè)頻繁項(xiàng)集相關(guān)的事務(wù)數(shù)目較大時(shí)，tlist中的缺頁(yè)處理時(shí)間比例上升．以上4部分中影響算法效率的主要因素是 tconn和 tlist．若處理器數(shù)目確定，頁(yè)面尺寸為 M，處理缺頁(yè)中斷所需時(shí)間用 tf表示，事務(wù)數(shù)目為 N，最小支持度閾值為S，這2部分時(shí)間描述為

式中：hi是頻繁 i-項(xiàng)集的數(shù)目；ti為產(chǎn)生一個(gè) i-項(xiàng)集所需的連接和依照單調(diào)性剪枝時(shí)間；tij是對(duì)第 j個(gè) i-項(xiàng)集進(jìn)行統(tǒng)計(jì)支持度和寫入鏈表時(shí)間；B1、B2是與編程有關(guān)的數(shù)據(jù)長(zhǎng)度．

在只增加挖掘數(shù)據(jù)源中事務(wù)數(shù)量 N的情況下，式(1)的值是固定不變的，圖 5中性能下降的因素是式(2)．而圖 6性能下降的因素則包括式(1)和式(2)2部分，在支持度不變的情況下，有用數(shù)據(jù)量的增加，使得產(chǎn)生的頻繁項(xiàng)集數(shù)目顯著增加，從而大幅地提高了運(yùn)算時(shí)間．

4 結(jié) 語(yǔ)

本文在一個(gè)新的分布式共享內(nèi)存編程環(huán)境VODCA上，針對(duì)稀疏數(shù)據(jù)源上的頻繁項(xiàng)集搜索問(wèn)題，提出和實(shí)現(xiàn)了一個(gè)新的算法PMFSD，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性．PMFSD算法同樣可以在消息傳遞平臺(tái)上實(shí)現(xiàn)，實(shí)現(xiàn)的關(guān)鍵是FI-list的構(gòu)建．

［1］ Agrawal R，Srikant R. Fast algorithms for mining association rules in large databases[C]//Proceedings of20th International Conference on Very Large Data Bases(VLDB'94)．Santiago de Chile，Chile：Morgan Kaufmann，1994：489-499.

［2］ Han Jiawei，Pei Jian，Yin Yiwen. Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD Conference on Management ofData(SIGMOD'00)．New York：ACM Press，2000：1-12．

［3］ Agrawal R，Shafer J C．Parallel mining of association rules[J].IEEE Trans on Knowledge and Data Engineering，1996，8(6)：962-969.

［4］ Park J S，Chen M，Yu P S. Efficient parallel data mining for association rules[C]//ACM Intl Conf of Information and Knowledge Management．New York：ACM Press，1995：31-36．

［5］ Za?ane O R，El-Hajj M，Lu P. Fast parallel association rule mining without candidacy generation[C]//Proceedings of the2001IEEE International Conference on Data Mining. San Jose，USA：IEEE Computer Society，2001：665-668.

［6］ 陳惠萍，王建東，葉飛躍，等. 基于 FP-tree和支持度數(shù)組的最大頻繁項(xiàng)集挖掘算法[J]. 系統(tǒng)工程與電子技術(shù)，2005，27(9)：1631-1635.

Chen Huiping，Wang Jiandong，Ye Feiyue，et al. Efficient mining maximal frequent itemsets by using FP-tree and support array[J].Systems Engineering and Electronics，2005，27(9)：1631-1635(in Chinese).

［7］ 徐維祥，蘇曉軍. 基于頻繁模式樹(shù)的一種關(guān)聯(lián)規(guī)則挖掘算法及其在鐵路隧道安全管理中的應(yīng)用[J]. 中國(guó)安全科學(xué)學(xué)報(bào)，2007，17(3)：25-32.

Xu Weixiang，Su Xiaojun. A high-performance association rule mining algorithm based on FP-tree and its application in railway tunnel safety management[J].China Safety Science Journal(CSSJ)，2007，17(3)：25-32(in Chinese)．

［8］ Huang Z，Purvis M，Werstein P. View-Oriented Parallel Programming and View-Based Consistency[R]. Technical Report(OUCS-2004-09)，Dept of Computer Science，Univ of Otago，2004.

［9］ Huang Z，Chen W，Purvis M，et al. VODCA：Vieworiented，distributed，cluster-based approach to parallel computing[C]//Proc of the IEEE/ACM Symposium on Cluster Computing and Grid2006(CCGrid06)．Singapore：IEEE Computer Society，2006：15-28.

［10］ Huang Z，Purvis M，Werstein P. View oriented update protocol with integrated diff for view-based consistency[C]//Proc of the Fifth IEEE International Symposium on Cluster Computing and Grid2005(CCGrid′05)．Cardiff，UK：IEEE Computer Society，2005(2)：873-880．