基于分布式并行關(guān)聯(lián)規(guī)則的挖掘算法

《基于分布式并行關(guān)聯(lián)規(guī)則的挖掘算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、基于分布式并行關(guān)聯(lián)規(guī)則的挖掘算法摘要以往使用的分布式數(shù)據(jù)挖掘算法各有優(yōu)缺點(diǎn)，提出了一種基于星型網(wǎng)絡(luò)的分布式關(guān)聯(lián)規(guī)則挖掘算法。對其基本思想、算法描述等進(jìn)行了分析?！娟P(guān)鍵詞】并行關(guān)聯(lián)規(guī)則挖掘算法SDAM算法在因特網(wǎng)的推動(dòng)下，分布式數(shù)據(jù)庫的應(yīng)用范圍越來越廣，如超市、銀行、圖書館等領(lǐng)域都有所應(yīng)用。隨著數(shù)據(jù)量的增多，對信息安全要求的提高，數(shù)據(jù)挖掘技術(shù)備受關(guān)注，成了當(dāng)前研究的重點(diǎn)。作為數(shù)據(jù)挖掘領(lǐng)域的重要組成部分，關(guān)聯(lián)規(guī)則可發(fā)現(xiàn)不同項(xiàng)之間內(nèi)在的聯(lián)系，進(jìn)而提高更優(yōu)質(zhì)的服務(wù)。自上世紀(jì)90年代被發(fā)現(xiàn)后，相關(guān)研究日益增多，特別是分布式并行挖掘方面

2、，很多算法相繼被提出。其中，F(xiàn)DM算法得到廣泛應(yīng)用，但尚有缺陷點(diǎn)。為此，提出一種新的算法。1SDAM算法實(shí)際中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)多呈現(xiàn)星型結(jié)構(gòu)，針對roM算法的不足，對其加以改進(jìn)，介紹一種基于星型網(wǎng)絡(luò)的分布式關(guān)聯(lián)規(guī)則挖掘算法SDAM算法。SDAM算法是在Aprioi算法的基礎(chǔ)上，候選集為1項(xiàng)的項(xiàng)目長度，通過數(shù)據(jù)庫掃描分析，算出局部大項(xiàng)集。接著將此局部大項(xiàng)集發(fā)送至中心結(jié)點(diǎn)，通過判斷，檢查此項(xiàng)集能否滿足全局的大項(xiàng)集標(biāo)準(zhǔn)。在項(xiàng)目長度為k的大項(xiàng)集基礎(chǔ)上，生成項(xiàng)目長度為k+1的大項(xiàng)集，然后對數(shù)據(jù)庫進(jìn)行二次分析、掃描，最后確定項(xiàng)目的全部大項(xiàng)

3、集。SDAM算法與FDM算法不同點(diǎn)是，SDAM算法只需要一個(gè)結(jié)點(diǎn)的局部大項(xiàng)集，不需要其他結(jié)點(diǎn)，SDAM算法的局部結(jié)點(diǎn)可以和中心結(jié)點(diǎn)進(jìn)行信息交換。2SDAM算法描述設(shè)結(jié)點(diǎn)為j(1n),保證在結(jié)點(diǎn)運(yùn)行算法的基礎(chǔ)上完成局部剪枝，具體步驟是：(1)選出候選集。結(jié)點(diǎn)j經(jīng)過(k-1)次迭代后可以生成強(qiáng)項(xiàng)集，根據(jù)計(jì)算可生成CGj(k)。(2)局部剪枝。設(shè)置項(xiàng)集是Xi的數(shù)據(jù)(XiECGj(k))，通過掃描數(shù)據(jù)庫中的DBj，對局部支持度合計(jì)數(shù)進(jìn)行計(jì)算分析。若Xi在結(jié)點(diǎn)i上并非局部最大值，則Xi項(xiàng)集不為局部大項(xiàng)集，應(yīng)從候選集中刪除。(3)交換信

4、息。將候選集項(xiàng)LLi(k)發(fā)送到中心結(jié)點(diǎn)，進(jìn)行信息交換，并且接受源于中心結(jié)點(diǎn)的全局大數(shù)據(jù)項(xiàng)集。在結(jié)點(diǎn)運(yùn)行算法的基礎(chǔ)上完成局部剪枝。設(shè)置k次迭代結(jié)束后，k的候選數(shù)據(jù)項(xiàng)集大小是X。在中心結(jié)點(diǎn)接受的數(shù)據(jù)集內(nèi)，大小為(k-1)的所有子集進(jìn)行局部支持度合計(jì)數(shù)，用maxsupi(X)來表示一個(gè)結(jié)點(diǎn)數(shù)據(jù)庫DBj中所有子集進(jìn)行局部支持度合計(jì)數(shù)，即minsupi(X)=min{Y.supi且=k—1}o所有分支數(shù)據(jù)庫中此類上界函數(shù)之和為X.supi的上界，可用maxsup(X)表示，即：X.supmaxsup(X)=maxsupi(X)，可用

5、其進(jìn)行全局剪枝。從中可知，一旦maxsup(X)比S*D小，則數(shù)據(jù)集X難以迗到候選數(shù)據(jù)集的要求，也就不能成為一個(gè)數(shù)據(jù)集。交換合計(jì)數(shù)前，要用結(jié)點(diǎn)i對剩余的候選元進(jìn)行剪枝。X.supi+maxsupi(X)為候選數(shù)據(jù)集X的全局支持度合計(jì)數(shù)上界值。X.supi值可以從在局部剪枝中得到，上界值能從中心結(jié)點(diǎn)中計(jì)算出來，用于數(shù)據(jù)集的剪枝。3分析SDAM算法3.1分析復(fù)雜度該算計(jì)算時(shí)，如果結(jié)點(diǎn)i的局部最大值是項(xiàng)集X，那么通信量的復(fù)雜性為0(n)，如果使用CD算法(一種計(jì)數(shù)分布算法)，那么需要的通訊量為0(n2)。3.2分析并行代價(jià)如果結(jié)點(diǎn)

6、的分區(qū)大小結(jié)果相同，存在D/n個(gè)事務(wù)，有m各項(xiàng)目需要挖掘，那么生成項(xiàng)集最多為2m個(gè)。假設(shè)在最惡劣的情況下，t是掃描每個(gè)數(shù)據(jù)庫D的時(shí)間，在串行情況下，復(fù)雜度為0(2m)，2mXts為算法的掃描時(shí)間。2mXts/n為所有分區(qū)的并行運(yùn)行時(shí)間。設(shè)并行代價(jià)為c，則c=t*n，式中，t表示的是并行運(yùn)算時(shí)間，n為結(jié)點(diǎn)總數(shù)量?？芍猚=2mXts，在挖掘執(zhí)行代價(jià)在階的意義關(guān)聯(lián)規(guī)則的并行算法上，在最壞情形下，串行求解此問題所需的運(yùn)行時(shí)間同SDAM算法相同，經(jīng)過比較，發(fā)現(xiàn)SDAM算法的并行代價(jià)最好。3.3分析并行伸縮性在平常的并行算法中，效率為E

7、p=Sp/n，式中的n表示并行結(jié)點(diǎn)數(shù)，Sp表示算法的加速比。并行算法的可伸縮性具體表現(xiàn)為：在處理機(jī)數(shù)目保持固定的情況下，Ep會(huì)隨著問題規(guī)模的擴(kuò)大呈現(xiàn)單調(diào)遞增的趨勢，此時(shí)，其效率為：Ep=Sp/n=1/[1+(Tr/Tc)]又因?yàn)門r=TfXm,Tc=TsX2m,可求得Ep=1/[1+(TfXm/TsX2m)]當(dāng)數(shù)據(jù)庫規(guī)模發(fā)生變化時(shí)，Ep的分母會(huì)不斷減少，則其值呈現(xiàn)出單調(diào)遞增的情形，由此可見，SDAM算法的可伸縮性能很好。3.4分析加速比中心結(jié)點(diǎn)在每次迭代結(jié)束后，向各結(jié)點(diǎn)通訊的時(shí)間就是各個(gè)結(jié)點(diǎn)需要等待的時(shí)間，從最壞的情況下進(jìn)行

8、分析，如果中心結(jié)點(diǎn)迭代結(jié)束后，發(fā)往各結(jié)點(diǎn)的時(shí)間為Tf，那么中心結(jié)點(diǎn)的總發(fā)送時(shí)間為mXTf。根據(jù)阿迗爾定律可知，Sp