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