資源描述：
《基于分布式并行關聯(lián)規(guī)則的挖掘算法》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、基于分布式并行關聯(lián)規(guī)則的挖掘算法摘要以往使用的分布式數(shù)據(jù)挖掘算法各有優(yōu)缺點，提出了一種基于星型網(wǎng)絡的分布式關聯(lián)規(guī)則挖掘算法。對其基本思想、算法描述等進行了分析?！娟P鍵詞】并行關聯(lián)規(guī)則挖掘算法SDAM算法在因特網(wǎng)的推動下，分布式數(shù)據(jù)庫的應用范圍越來越廣，如超市、銀行、圖書館等領域都有所應用。隨著數(shù)據(jù)量的增多，對信息安全要求的提高，數(shù)據(jù)挖掘技術備受關注，成了當前研究的重點。作為數(shù)據(jù)挖掘領域的重要組成部分，關聯(lián)規(guī)則可發(fā)現(xiàn)不同項之間內在的聯(lián)系，進而提高更優(yōu)質的服務。自上世紀90年代被發(fā)現(xiàn)后，相關研究日益增多，特別是分布式并行挖掘方面
2、，很多算法相繼被提出。其中，F(xiàn)DM算法得到廣泛應用，但尚有缺陷點。為此，提出一種新的算法。1SDAM算法實際中，網(wǎng)絡拓撲結構多呈現(xiàn)星型結構，針對roM算法的不足，對其加以改進，介紹一種基于星型網(wǎng)絡的分布式關聯(lián)規(guī)則挖掘算法SDAM算法。SDAM算法是在Aprioi算法的基礎上，候選集為1項的項目長度，通過數(shù)據(jù)庫掃描分析，算出局部大項集。接著將此局部大項集發(fā)送至中心結點，通過判斷，檢查此項集能否滿足全局的大項集標準。在項目長度為k的大項集基礎上，生成項目長度為k+1的大項集，然后對數(shù)據(jù)庫進行二次分析、掃描，最后確定項目的全部大項
3、集。SDAM算法與FDM算法不同點是，SDAM算法只需要一個結點的局部大項集，不需要其他結點，SDAM算法的局部結點可以和中心結點進行信息交換。2SDAM算法描述設結點為j(1n),保證在結點運行算法的基礎上完成局部剪枝，具體步驟是：(1)選出候選集。結點j經(jīng)過(k-1)次迭代后可以生成強項集，根據(jù)計算可生成CGj(k)。(2)局部剪枝。設置項集是Xi的數(shù)據(jù)(XiECGj(k))，通過掃描數(shù)據(jù)庫中的DBj，對局部支持度合計數(shù)進行計算分析。若Xi在結點i上并非局部最大值，則Xi項集不為局部大項集，應從候選集中刪除。(3)交換信
4、息。將候選集項LLi(k)發(fā)送到中心結點，進行信息交換，并且接受源于中心結點的全局大數(shù)據(jù)項集。在結點運行算法的基礎上完成局部剪枝。設置k次迭代結束后，k的候選數(shù)據(jù)項集大小是X。在中心結點接受的數(shù)據(jù)集內，大小為(k-1)的所有子集進行局部支持度合計數(shù)，用maxsupi(X)來表示一個結點數(shù)據(jù)庫DBj中所有子集進行局部支持度合計數(shù)，即minsupi(X)=min{Y.supi且=k—1}o所有分支數(shù)據(jù)庫中此類上界函數(shù)之和為X.supi的上界，可用maxsup(X)表示，即：X.supmaxsup(X)=maxsupi(X)，可用
5、其進行全局剪枝。從中可知，一旦maxsup(X)比S*D小，則數(shù)據(jù)集X難以迗到候選數(shù)據(jù)集的要求，也就不能成為一個數(shù)據(jù)集。交換合計數(shù)前，要用結點i對剩余的候選元進行剪枝。X.supi+maxsupi(X)為候選數(shù)據(jù)集X的全局支持度合計數(shù)上界值。X.supi值可以從在局部剪枝中得到，上界值能從中心結點中計算出來，用于數(shù)據(jù)集的剪枝。3分析SDAM算法3.1分析復雜度該算計算時，如果結點i的局部最大值是項集X，那么通信量的復雜性為0(n)，如果使用CD算法(一種計數(shù)分布算法)，那么需要的通訊量為0(n2)。3.2分析并行代價如果結點
6、的分區(qū)大小結果相同，存在D/n個事務，有m各項目需要挖掘，那么生成項集最多為2m個。假設在最惡劣的情況下，t是掃描每個數(shù)據(jù)庫D的時間，在串行情況下，復雜度為0(2m)，2mXts為算法的掃描時間。2mXts/n為所有分區(qū)的并行運行時間。設并行代價為c，則c=t*n，式中，t表示的是并行運算時間，n為結點總數(shù)量?？芍猚=2mXts，在挖掘執(zhí)行代價在階的意義關聯(lián)規(guī)則的并行算法上，在最壞情形下，串行求解此問題所需的運行時間同SDAM算法相同，經(jīng)過比較，發(fā)現(xiàn)SDAM算法的并行代價最好。3.3分析并行伸縮性在平常的并行算法中，效率為E
7、p=Sp/n，式中的n表示并行結點數(shù)，Sp表示算法的加速比。并行算法的可伸縮性具體表現(xiàn)為：在處理機數(shù)目保持固定的情況下，Ep會隨著問題規(guī)模的擴大呈現(xiàn)單調遞增的趨勢，此時，其效率為：Ep=Sp/n=1/[1+(Tr/Tc)]又因為Tr=TfXm,Tc=TsX2m,可求得Ep=1/[1+(TfXm/TsX2m)]當數(shù)據(jù)庫規(guī)模發(fā)生變化時，Ep的分母會不斷減少，則其值呈現(xiàn)出單調遞增的情形，由此可見，SDAM算法的可伸縮性能很好。3.4分析加速比中心結點在每次迭代結束后，向各結點通訊的時間就是各個結點需要等待的時間，從最壞的情況下進行
8、分析，如果中心結點迭代結束后，發(fā)往各結點的時間為Tf，那么中心結點的總發(fā)送時間為mXTf。根據(jù)阿迗爾定律可知，Sp
