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

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

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

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

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

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

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

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

8、系統(tǒng)所采用的數(shù)據(jù)挖掘方法應(yīng)用于異構(gòu)分布式數(shù)據(jù)挖掘系統(tǒng)，那么為了得到一個(gè)精確的預(yù)測(cè)模型往往需要很大的系統(tǒng)開銷，有時(shí)甚至是不可行的。( )Ikkkf xw 為了能夠在結(jié)點(diǎn)異構(gòu)的情況下有效地進(jìn)行數(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é)果。 14分布式數(shù)據(jù)挖掘算法分布式?jīng)Q策樹生成分布式?jīng)Q策樹生成決策樹是一種用于分類與回歸分析的傳統(tǒng)預(yù)測(cè)模型，

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

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

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

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

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