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

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

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

【部分圖文】：

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

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

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

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



本文編號(hào)：3442398