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

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

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

2、，很多算法相繼被提出。其中，F(xiàn)DM算法得到廣泛應(yīng)用，但尚有缺陷點。為此，提出一種新的算法。1SDAM算法實際中，網(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項的項目長度，通過數(shù)據(jù)庫掃描分析，算出局部大項集。接著將此局部大項集發(fā)送至中心結(jié)點，通過判斷，檢查此項集能否滿足全局的大項集標(biāo)準(zhǔn)。在項目長度為k的大項集基礎(chǔ)上，生成項目長度為k+1的大項集，然后對數(shù)據(jù)庫進(jìn)行二次分析、掃描，最后確定項目的全部大項

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

4、息。將候選集項LLi(k)發(fā)送到中心結(jié)點，進(jìn)行信息交換，并且接受源于中心結(jié)點的全局大數(shù)據(jù)項集。在結(jié)點運(yùn)行算法的基礎(chǔ)上完成局部剪枝。設(shè)置k次迭代結(jié)束后，k的候選數(shù)據(jù)項集大小是X。在中心結(jié)點接受的數(shù)據(jù)集內(nèi)，大小為(k-1)的所有子集進(jìn)行局部支持度合計數(shù)，用maxsupi(X)來表示一個結(jié)點數(shù)據(jù)庫DBj中所有子集進(jìn)行局部支持度合計數(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ù)集的要求，也就不能成為一個數(shù)據(jù)集。交換合計數(shù)前，要用結(jié)點i對剩余的候選元進(jìn)行剪枝。X.supi+maxsupi(X)為候選數(shù)據(jù)集X的全局支持度合計數(shù)上界值。X.supi值可以從在局部剪枝中得到，上界值能從中心結(jié)點中計算出來，用于數(shù)據(jù)集的剪枝。3分析SDAM算法3.1分析復(fù)雜度該算計算時，如果結(jié)點i的局部最大值是項集X，那么通信量的復(fù)雜性為0(n)，如果使用CD算法(一種計數(shù)分布算法)，那么需要的通訊量為0(n2)。3.2分析并行代價如果結(jié)點

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

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

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