分布式數(shù)據(jù)挖掘

1、1分布式數(shù)據(jù)挖掘張敏靈 陳兆乾 周志華 2002.10.112提綱簡介 數(shù)據(jù)挖掘 分布式數(shù)據(jù)挖掘研究現(xiàn)狀 同構(gòu)與異構(gòu) 分布式數(shù)據(jù)挖掘算法 應(yīng)用實例進一步的工作3簡介數(shù)據(jù)挖掘什么是數(shù)據(jù)挖掘？數(shù)據(jù)挖掘是指從巨量數(shù)據(jù)中獲取有效的、新穎的、從巨量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程潛在有用的、最終可理解的模式的非平凡過程。(From U. Fayyad et al.s definition at KDD96)巨量的：對于少量數(shù)據(jù)的分析不需要使用數(shù)據(jù)挖掘。有效的：所獲得的模式必須是正確的。新穎的：對于已知知識的投資收益不大。潛在有用的：所得的模式應(yīng)能提供相關(guān)的決策支持。最終

2、可理解的：所得的模式是提交給決策制定者的。數(shù)據(jù)挖掘的研究領(lǐng)域數(shù)據(jù)挖掘是一門涉及機器學習、統(tǒng)計學、數(shù)據(jù)庫、可視化技術(shù)、高性能計算等諸多方面的交叉學科。 4數(shù)據(jù)挖掘續(xù)數(shù)據(jù)挖掘的應(yīng)用范圍 描述性規(guī)則發(fā)現(xiàn)(Characterization) 對比性規(guī)則發(fā)現(xiàn)(Discrimination) 關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(Association) 分類分析(Classification) 預(yù)測（回歸）分析(Prediction) 聚類分析(Clustering) 異常分析(Outlier analysis) 5簡介分布式數(shù)據(jù)挖掘產(chǎn)生背景 各相關(guān)學科的飛速發(fā)展，各種網(wǎng)絡(luò)尤其是Internet的廣泛使用。 實際應(yīng)用要求數(shù)據(jù)挖

3、掘系統(tǒng)具有更好的可擴展性。 實例 研究某種疾病在某地的發(fā)病情況與氣候的關(guān)系（疾病控制數(shù)據(jù)庫環(huán)境數(shù)據(jù)庫） 金融組織間通過合作防止信用卡欺詐（數(shù)據(jù)共享） 大型跨國公司營銷策略的制定（銷售點分散，數(shù)據(jù)倉庫構(gòu)造十分耗時）分布式數(shù)據(jù)挖掘正是在這一背景下產(chǎn)生的，它是數(shù)據(jù)挖掘技術(shù)與分布式計算的有機結(jié)合，主要用于分布式環(huán)境下的數(shù)據(jù)模式發(fā)現(xiàn)。 6分布式數(shù)據(jù)挖掘續(xù)分布式數(shù)據(jù)挖掘的優(yōu)點出于對安全性、容錯性、商業(yè)競爭以及法律約束等多方面因素的考慮，在許多情況下，將所有數(shù)據(jù)集中在一起進行分析往往是不可行的。分布式數(shù)據(jù)挖掘系統(tǒng)則可以充分利用分布式計算的能力對相關(guān)的數(shù)據(jù)進行分析與綜合。 在傳統(tǒng)的數(shù)據(jù)挖掘系統(tǒng)中，如果能將數(shù)據(jù)

4、合理地劃分為若干個小模塊，并由數(shù)據(jù)挖掘系統(tǒng)并行地處理，最后再將各個局部處理結(jié)果合成最終的輸出模式，則可節(jié)省大量的時間和空間開銷。面臨的問題 算法方面 數(shù)據(jù)預(yù)處理，實現(xiàn)各種數(shù)據(jù)挖掘算法。 結(jié)合系統(tǒng)所處的分布式計算環(huán)境。 系統(tǒng)方面 能在對稱多處理機(SMP)、大規(guī)模并行處理機(MPP)等具體的分布式平臺上實現(xiàn)。 結(jié)點間負載平衡、減少同步與通訊開銷、異構(gòu)數(shù)據(jù)集成等 。7分布式數(shù)據(jù)挖掘續(xù)系統(tǒng)分類根據(jù)結(jié)點間數(shù)據(jù)分布情況 同構(gòu)：結(jié)點間數(shù)據(jù)的屬性空間相同 異構(gòu)：結(jié)點間數(shù)據(jù)具有不同的屬性空間按照數(shù)據(jù)模式的生成方式 集中式：先把數(shù)據(jù)集中于中心點，再生成全局數(shù)據(jù)模式（模型精度較高，但只適合于數(shù)據(jù)量較小的情況）。

5、局部式：先在各結(jié)點處生成局部數(shù)據(jù)模式，然后再將局部數(shù)據(jù)模式集中到中心結(jié)點生成全局數(shù)據(jù)模式（模型精度較低，但效率較高）。 數(shù)據(jù)重分布式 ：首先將所有數(shù)據(jù)在各個結(jié)點間重新分布，然后再按照與局部式系統(tǒng)相同的方法生成數(shù)據(jù)模式。 按系統(tǒng)功能、通訊與合作方式等情況劃分8研究現(xiàn)狀結(jié)點的同構(gòu)與異構(gòu)性 元學習(Meta-learning) CDM(Collective data mining)分布式數(shù)據(jù)挖掘算法 分布式?jīng)Q策樹生成 分布式關(guān)聯(lián)規(guī)則發(fā)現(xiàn)應(yīng)用系統(tǒng)實例9結(jié)點的同構(gòu)與異構(gòu)性元學習同構(gòu)結(jié)點間的數(shù)據(jù)挖掘在同構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)中，各個結(jié)點存儲的數(shù)據(jù)都具有相同的屬性空間。 為了實現(xiàn)同構(gòu)結(jié)點的數(shù)據(jù)挖掘，研究者們先

6、后提出了元學習 (meta-learning)、合作學習(coactive learning)等方法，其中元學習方法最具代表性。元學習的概念是由Prodromidis等人于2000年首先提出的，該方法采用集成學習 (ensemble learning) 的方式來生成最終的全局預(yù)測模型（即元分類器）。該方法的基本思想是從已經(jīng)獲得的知識中再進行學習，從而得到最終的數(shù)據(jù)模式。 10元學習續(xù)元學習的具體過程圖1 元學習的具體過程11元學習續(xù)基分類器輸出的集成方式 投票(Voting): 絕對（相對）多數(shù)投票，加權(quán)投票。 決策(Arbitration): 指定特殊的“決策者”，當各基分類器的輸出無法達成

7、一致時，采用“決策者”的輸出。 結(jié)合(Combining): 使用相關(guān)的先驗與領(lǐng)域知識指導(dǎo)各輸出的集成。元學習的優(yōu)點在基學習階段，各個結(jié)點可以自主地選擇合適的學習算法來生成局部的基分類器。與此同時，各結(jié)點間不存在任何通訊與同步開銷，因此系統(tǒng)效率較高。在元學習階段，由于系統(tǒng)可靈活采用各種集成策略，因此最終生成的元分類器具有較高的預(yù)測精度。12結(jié)點的同構(gòu)與異構(gòu)性CDM異構(gòu)結(jié)點間的數(shù)據(jù)挖掘在異構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)中，各個結(jié)點存儲的數(shù)據(jù)具有不同的屬性空間，一般而言，異構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)所要處理的數(shù)據(jù)集稱為垂直分劃數(shù)據(jù)集。 圖2 一個典型的垂直分劃數(shù)據(jù)集13CDM續(xù)CDM研究結(jié)果表明，如果簡單地將同構(gòu)

8、系統(tǒng)所采用的數(shù)據(jù)挖掘方法應(yīng)用于異構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)，那么為了得到一個精確的預(yù)測模型往往需要很大的系統(tǒng)開銷，有時甚至是不可行的。( )Ikkkf xw 為了能夠在結(jié)點異構(gòu)的情況下有效地進行數(shù)據(jù)挖掘， Kargupta等人提出了CDM (Collective Data Mining) 的概念，其基本思想是任一函數(shù)f都可以由一組基函數(shù)所表示，即 。最近，Kargupta等人結(jié)合傳統(tǒng)的ID3決策樹學習算法以及小波變換技術(shù)，成功地將CDM技術(shù)應(yīng)用于分布式?jīng)Q策樹生成以及回歸分析中，取得了令人滿意的結(jié)果。 14分布式數(shù)據(jù)挖掘算法分布式?jīng)Q策樹生成分布式?jīng)Q策樹生成決策樹是一種用于分類與回歸分析的傳統(tǒng)預(yù)測模型，

9、由于其簡單易用，并且具有很好的可理解性與較強的可擴展性，因此被數(shù)據(jù)挖掘領(lǐng)域所廣泛使用。 早期的分布式?jīng)Q策樹生成算法主要基于對傳統(tǒng)算法(例如ID3算法)的并行實現(xiàn)，這些算法假設(shè)所需的數(shù)據(jù)都位于主存之中，并且沒有考慮磁盤讀寫、負載平衡等實際問題，因此具有很大的局限性。 針對上述的情況，Mehta等人提出了一種新的決策樹生成算法SLIQ(Supervised Learning In Quest)。該方法定義了類列表（常駐內(nèi)存）和屬性列表（位于內(nèi)存或磁盤中）兩種數(shù)據(jù)結(jié)構(gòu)，在一定程度上克服了內(nèi)存大小對訓練集規(guī)模的限制，且易于實現(xiàn)并行處理(SLIQ/R、SLIQ/D)。15分布式?jīng)Q策樹生成續(xù)其他算法 SL

10、IQ算法中使用的類列表是隨著數(shù)據(jù)規(guī)模的增大而線性增長的，由于類列表在運行時刻常駐于內(nèi)存中，這就限制了SLIQ算法所能處理的問題的規(guī)模。 Shafer等人在SLIQ算法的基礎(chǔ)上設(shè)計出了SPRINT (Scalable PaRallelizable INduction of decision Trees) 算法，并且給出了SPRINT算法在分布式計算環(huán)境下的具體實現(xiàn)。實驗結(jié)果表明，SPRINT算法很好地解決了內(nèi)存大小對于問題數(shù)據(jù)規(guī)模的限制問題，并且在系統(tǒng)運行時間、規(guī)?？蓴U展性、應(yīng)用可擴展性等方面均優(yōu)于SLIQ算法。 Arguello等人基于對決策樹增量學習算法的研究，針對共享存儲器和無共享兩種多處

11、理器結(jié)構(gòu)，分別提出了DSD(Distributed Subtree Derivation)和DTD(Distributed Tree Derivation)兩種分布式?jīng)Q策樹生成算法。這兩種算法具有很強的靈活性，生成的決策樹規(guī)模也較小，但是算法運行過程中需要較大的通訊與同步開銷。 16分布式數(shù)據(jù)挖掘算法分布式關(guān)聯(lián)規(guī)則發(fā)現(xiàn)分布式關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 隨著大規(guī)模事務(wù)數(shù)據(jù)庫的廣泛使用以及企業(yè)數(shù)據(jù)分布范圍的逐步擴大，使得設(shè)計高效的分布式關(guān)聯(lián)規(guī)則挖掘算法變得越來越重要。 Agrawal等人在 Apriori 這一傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法基礎(chǔ)之上，設(shè)計了計數(shù)分布 (Count Distribution) 、數(shù)據(jù)分布

12、(Data Distribution) 以及候選分布 (Candidate Distribution) 三種分布式關(guān)聯(lián)規(guī)則挖掘算法。 在計數(shù)分布算法中，各個結(jié)點都含有完整的頻繁項目集，減少了系統(tǒng)的通訊與同步開銷；另一方面，頻繁項目集在系統(tǒng)各結(jié)點處的冗余存儲也降低了系統(tǒng)資源的利用率。 在數(shù)據(jù)分布算法中，整個頻繁項目集均勻地分散于各個結(jié)點，系統(tǒng)的資源利用率較高，但增加了結(jié)點間的通訊和同步開銷。 在候選分布算法中，算法將根據(jù)問題領(lǐng)域所提供的語義信息把整個頻繁項目集在各個結(jié)點中重新分布，從而達到平衡各結(jié)點負載的目的，同時減少了結(jié)點間的同步開銷。 同樣基于Apriori算法，Cheung等人提出了另一種

13、分布式關(guān)聯(lián)規(guī)則挖掘算法FDM (Fast Distributed Mining of association rules)。FDM算法產(chǎn)生的候選頻繁項目集規(guī)模要小于計數(shù)分布算法，并且降低了結(jié)點間的通訊開銷以及算法的運行時間。17應(yīng)用系統(tǒng)實例JAM：該系統(tǒng)基于元學習方法，利用從各個稀疏的數(shù)據(jù)源處收集的信息來構(gòu)造最終的全局分類模式。PADMA：該系統(tǒng)采用了合作Agent技術(shù)，主要用于分布式計算環(huán)境下的文檔分析。Papyrus：該系統(tǒng)基于與JAM系統(tǒng)相似的理論基礎(chǔ)，主要用于對分部在廣域網(wǎng)內(nèi)的數(shù)據(jù)進行有效的分布式數(shù)據(jù)挖掘。Kensington：該系統(tǒng)采用了分布式組件技術(shù)，主要用于Internet上的分布式數(shù)據(jù)挖掘。 18進一步的工作目前，雖然有關(guān)異構(gòu)結(jié)點的分布式數(shù)據(jù)挖掘已經(jīng)做