Apriori算法是解決頻繁項集挖掘問題的基本算法之一。新一代具有并行處理能力的廉價計算機,更容易建立計算機集群,可以為這些新系統(tǒng)開發(fā)更有效并行FIM算法。為了提高效率,筆者研究了Trie和PVM并行執(zhí)行的消息傳遞方式,并提出了一種新的消息傳遞方式與PVM并行計算機集群上推測的消息傳遞方式,希望能夠為相關(guān)研究提供借鑒。 

【文章來源】：信息與電腦(理論版). 2019,31(19)

【文章頁數(shù)】：3 頁

【部分圖文】：

Trie結(jié)構(gòu)示例

毓?Trie；從進程偵聽主進程以獲取要采取的步驟，因為主進程在對所采取的步驟進行編碼的同時遍歷自己的候選Trie。該方法如圖2中的黃色箭頭所示，具有較好的擴展性，但是只能擴展到生成和發(fā)送候選對象的特定值。PVM進程也存在問題，比如隨機終止或較長的響應(yīng)時間。（3）版本3。為了克服以前方法中存在的問題，本文提出了一種新的解決方案，并對編碼后的Trie編寫了一條消息。在這種方法中，從進程不必監(jiān)聽主進程，而是對這條消息進行解碼，以構(gòu)建候選Trie。如圖2中的紅色箭頭所示。圖2構(gòu)建候選Trie為了返回支持計數(shù)結(jié)果，在完成支持計數(shù)之后，從進程創(chuàng)建一個數(shù)組并將其發(fā)送回去。由于候選程序在每個進程中的嘗試完全相同，所以主進程算術(shù)上添加這些數(shù)組并遍歷候選程序的嘗試以插入值。2.3Apriori中的加速技術(shù)本文實現(xiàn)并評估了幾種加速技術(shù)。第1個方法是從事務(wù)中刪除不經(jīng)常出現(xiàn)的元素，Bodon[5]將此稱為過濾事務(wù)。由于每個事務(wù)及其元素在支持計數(shù)中都被訪問了很多次，因此從事務(wù)中刪除不頻繁的元素會對Apriori算法的性能產(chǎn)生很大的影響。第2個方法是對于Trie中元素的順序，可以討論基于頻率的順序和其他方法（詞典、隨機等），可以用上升和下降的頻率順序構(gòu)建Trie。上升的頻率順序有一個優(yōu)勢，即稀有元素更接近根，并在支持計數(shù)的早期步驟中從循環(huán)中斷開。降序頻率排序的優(yōu)點是Trie更小，公共元素更接近根，因此占用的內(nèi)存更少。第3個方法是對支持度計數(shù)的計算。在事務(wù)t中k個項目子集的支持計數(shù)中，假設(shè)在t中第j項后的某個深度d處，需要檢查t中第i個位置的項目，使j<i<|t|-k+d+1。這是因為至少需要這么多項來完成Trie

集。3主要結(jié)論本文采用進化的發(fā)展過程。第一個并行化試驗是將候選進程分別發(fā)送到從屬進程，讓它們構(gòu)建自己的候選進程，同時嘗試不同的頻率順序。它被稱為Ver-sion1，結(jié)果如圖3所示。在單處理器順序算法和并行算法上都采用了基于頻率的排序。緊湊并行使用一個Trie存儲候選項和頻繁項集。數(shù)據(jù)集由10000個事務(wù)組成，隨機創(chuàng)建;每個事務(wù)最多有100個元素�？梢钥闯�，隨著從程序數(shù)量的增加，版本1無法擴展其性能。相反，遞歸發(fā)送候選Trie的版本2的性能隨著從進程數(shù)量的增加而增加。圖3非遞歸（稱為版本1）和遞歸（稱為版本2）Trie傳輸選項的比較開發(fā)的版本3旨在通過創(chuàng)建由候選Trie的遞歸定義組成的單個消息來減少PVM系統(tǒng)上的消息傳遞負載。此版本的性能結(jié)果優(yōu)于前一個版本，如圖4所示。圖4支持閾值0.45的改進消息傳遞圖4中沒有顯示較低支持閾值的值，因為版本2不能生成任何可比較的時間。在支持閾值為0.4版本3時，7個從進程的響應(yīng)時間為59秒，而PVM在版本2時終止。具有支持閾值的相同數(shù)據(jù)集現(xiàn)在減少到0.4，并在版本3中應(yīng)用了額外的加速技術(shù)。各種加速技術(shù)應(yīng)用于版本3，以二進制搜索為基礎(chǔ)，結(jié)果如圖5所示，要注意Apriori檢查對候選人的影響。這大大減少了支持計數(shù)之前的搜索空間。在本例中，它還減少了通信時間，因為候選Trie被轉(zhuǎn)移到從屬進程，同時遍歷始終優(yōu)于其他支持計數(shù)技術(shù)。具有下限的反向二進制是最慢的。過濾事務(wù)不會改變響應(yīng)時間，但不應(yīng)該被誤解，因為這種技術(shù)的效果依賴于數(shù)據(jù)分布和所選的支持閾值。圖5相同數(shù)據(jù)集閾值減少4結(jié)語本文利用trie數(shù)據(jù)結(jié)構(gòu)在并行計算機集群上測試了Apriori算法的可伸縮性

【參考文獻】：
期刊論文
[1]矩陣壓縮Apriori算法分析[J]. 沈艷,張琦智,劉垠,廉春波.  計算機應(yīng)用. 2017(S2)
[2]基于Apriori和FP-growth的關(guān)聯(lián)挖掘[J]. 肖謙,梅全喜,楊麗嬌.  科技展望. 2016(27)
[3]關(guān)聯(lián)規(guī)則挖掘Apriori算法的一種改進[J]. 屈鑫乙,王迪,劉滏.  中國市場. 2016(36)
[4]關(guān)聯(lián)規(guī)則中幾種算法的研究[J]. 顧瑋.  辦公自動化. 2016(12)
[5]關(guān)聯(lián)規(guī)則挖掘綜述[J]. 崔妍,包志強.  計算機應(yīng)用研究. 2016(02)



本文編號：3442398