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

1、分布式數(shù)據(jù)挖掘張敏靈 陳兆乾 周志華 南京大學(xué)軟件新技術(shù)國家重點實驗室2002.10.11提綱簡介數(shù)據(jù)挖掘分布式數(shù)據(jù)挖掘研究現(xiàn)狀同構(gòu)與異構(gòu)分布式數(shù)據(jù)挖掘算法應(yīng)用實例進一步的工作簡介數(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)的決策支持。最終可理解的：所得的模式是提交給決策制定者的。數(shù)據(jù)挖掘的研究

2、領(lǐng)域數(shù)據(jù)挖掘是一門涉及機器學(xué)習(xí)、統(tǒng)計學(xué)、數(shù)據(jù)庫、可視化技術(shù)、高性能計算等諸多方面的交叉學(xué)科。 數(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)分布式數(shù)據(jù)挖掘續(xù)分布式數(shù)據(jù)挖掘的優(yōu)點出于對安全性、容錯性、商業(yè)競爭以及法律約束等多方面因素的考慮，在許多情況下，將所有數(shù)據(jù)集中在一起進行分析往往是不可行的。分布式數(shù)據(jù)挖掘系統(tǒng)則可以充分利用

3、分布式計算的能力對相關(guān)的數(shù)據(jù)進行分析與綜合。在傳統(tǒng)的數(shù)據(jù)挖掘系統(tǒng)中，如果能將數(shù)據(jù)合理地劃分為若干個小模塊，并由數(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ù)集成等 。分布式數(shù)據(jù)挖掘續(xù)系統(tǒng)分類根據(jù)結(jié)點間數(shù)據(jù)分布情況同構(gòu)：結(jié)點間數(shù)據(jù)的屬性空間相同異構(gòu)：結(jié)點間數(shù)據(jù)具有不同的屬性空間按照數(shù)據(jù)模式的生成方式 集中式：先把數(shù)據(jù)集中于中心點，再生

4、成全局數(shù)據(jù)模式（模型精度較高，但只適合于數(shù)據(jù)量較小的情況）。局部式：先在各結(jié)點處生成局部數(shù)據(jù)模式，然后再將局部數(shù)據(jù)模式集中到中心結(jié)點生成全局數(shù)據(jù)模式（模型精度較低，但效率較高）。數(shù)據(jù)重分布式 ：首先將所有數(shù)據(jù)在各個結(jié)點間重新分布，然后再按照與局部式系統(tǒng)相同的方法生成數(shù)據(jù)模式。按系統(tǒng)功能、通訊與合作方式等情況劃分結(jié)點的同構(gòu)與異構(gòu)性元學(xué)習(xí)同構(gòu)結(jié)點間的數(shù)據(jù)挖掘在同構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)中，各個結(jié)點存儲的數(shù)據(jù)都具有相同的屬性空間。為了實現(xiàn)同構(gòu)結(jié)點的數(shù)據(jù)挖掘，研究者們先后提出了元學(xué)習(xí) (meta-learning)、合作學(xué)習(xí)(coactive learning)等方法，其中元學(xué)習(xí)方法最具代表性。元學(xué)習(xí)的概

5、念是由Prodromidis等人于2000年首先提出的，該方法采用集成學(xué)習(xí) (ensemble learning) 的方式來生成最終的全局預(yù)測模型（即元分類器）。該方法的基本思想是從已經(jīng)獲得的知識中再進行學(xué)習(xí)，從而得到最終的數(shù)據(jù)模式。 元學(xué)習(xí)續(xù)元學(xué)習(xí)的具體過程圖1 元學(xué)習(xí)的具體過程元學(xué)習(xí)續(xù)基分類器輸出的集成方式投票(Voting): 絕對（相對）多數(shù)投票，加權(quán)投票。決策(Arbitration): 指定特殊的“決策者”，當(dāng)各基分類器的輸出無法達成一致時，采用“決策者”的輸出。結(jié)合(Combining): 使用相關(guān)的先驗與領(lǐng)域知識指導(dǎo)各輸出的集成。元學(xué)習(xí)的優(yōu)點在基學(xué)習(xí)階段，各個結(jié)點可以自主地選擇

6、合適的學(xué)習(xí)算法來生成局部的基分類器。與此同時，各結(jié)點間不存在任何通訊與同步開銷，因此系統(tǒng)效率較高。在元學(xué)習(xí)階段，由于系統(tǒng)可靈活采用各種集成策略，因此最終生成的元分類器具有較高的預(yù)測精度。結(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ù)集CDM續(xù)CDM研究結(jié)果表明，如果簡單地將同構(gòu)系統(tǒng)所采用的數(shù)據(jù)挖掘方法應(yīng)用于異構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)，那么為了得到一個精確的預(yù)測模型往往需要很大的系統(tǒng)開銷，有時甚至是不可行的。為了能夠在結(jié)點異構(gòu)的情況下有效地

7、進行數(shù)據(jù)挖掘， Kargupta等人提出了CDM (Collective Data Mining) 的概念，其基本思想是任一函數(shù)f都可以由一組基函數(shù)所表示，即 。最近，Kargupta等人結(jié)合傳統(tǒng)的ID3決策樹學(xué)習(xí)算法以及小波變換技術(shù)，成功地將CDM技術(shù)應(yīng)用于分布式?jīng)Q策樹生成以及回歸分析中，取得了令人滿意的結(jié)果。 分布式數(shù)據(jù)挖掘算法分布式?jīng)Q策樹生成分布式?jīng)Q策樹生成決策樹是一種用于分類與回歸分析的傳統(tǒng)預(yù)測模型，由于其簡單易用，并且具有很好的可理解性與較強的可擴展性，因此被數(shù)據(jù)挖掘領(lǐng)域所廣泛使用。 早期的分布式?jīng)Q策樹生成算法主要基于對傳統(tǒng)算法(例如ID3算法)的并行實現(xiàn)，這些算法假設(shè)所需的數(shù)據(jù)都位

8、于主存之中，并且沒有考慮磁盤讀寫、負載平衡等實際問題，因此具有很大的局限性。 針對上述的情況，Mehta等人提出了一種新的決策樹生成算法SLIQ(Supervised Learning In Quest)。該方法定義了類列表（常駐內(nèi)存）和屬性列表（位于內(nèi)存或磁盤中）兩種數(shù)據(jù)結(jié)構(gòu)，在一定程度上克服了內(nèi)存大小對訓(xùn)練集規(guī)模的限制，且易于實現(xiàn)并行處理(SLIQ/R、SLIQ/D)。分布式數(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ī)則

9、挖掘算法基礎(chǔ)之上，設(shè)計了計數(shù)分布 (Count Distribution) 、數(shù)據(jù)分布 (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等人提出了另一種分布式關(guān)聯(lián)規(guī)則挖掘算法FDM (Fast Distributed Mining of association rules)。FDM算法產(chǎn)生的候選頻繁項目集規(guī)模要小于計數(shù)分布算法，并且降低了結(jié)點間的通訊開銷以及算法的運行時間。應(yīng)用系統(tǒng)實例JAM：該系統(tǒng)基于元學(xué)習(xí)方法，利用從各個稀疏的數(shù)據(jù)源處收集的信息來構(gòu)造最終的全局分類