基于遺傳算法的分布式數(shù)據(jù)挖掘MapReduce架構(gòu)研究.pdf

1、近年來，隨著信息技術(shù)的快速發(fā)展，直接或間接的產(chǎn)生了難以估量的海量數(shù)據(jù)，這對(duì)傳統(tǒng)數(shù)據(jù)挖掘算法提出了新的挑戰(zhàn)，如何提高海量數(shù)據(jù)環(huán)境下傳統(tǒng)數(shù)據(jù)挖掘算法的通用性和性能成為當(dāng)前的研究熱點(diǎn)。為了解決這一問題，研究人員將傳統(tǒng)數(shù)據(jù)挖掘算法與新興技術(shù)如云計(jì)算平臺(tái)等融合，利用分布式計(jì)算能力提高算法的性能，取得了良好效果。但是由于數(shù)據(jù)挖掘算法種類繁多，單一的數(shù)據(jù)挖掘算法需要特定的實(shí)現(xiàn)模式，沒有通用的架構(gòu)滿足數(shù)據(jù)挖掘算法的多樣性，并能同時(shí)提高算法的性能。本文在

2、前人經(jīng)驗(yàn)的基礎(chǔ)上，提出了一種基于遺傳算法的分布式數(shù)據(jù)挖掘MapReduce架構(gòu)，旨在幫助用戶更通用的處理數(shù)據(jù)挖掘算法并提升算法的性能。架構(gòu)要素之一的MapReduce提供良好的分布式計(jì)算能力，另一要素遺傳算法具有良好的全局搜索和優(yōu)化能力，通過模擬種群進(jìn)化的方式搜索到最優(yōu)解，使得用戶只需要實(shí)現(xiàn)遺傳算法而不必?fù)?dān)心算法的并行化。
　　本文的主要貢獻(xiàn)如下，提出了一種基于遺傳算法的分布式數(shù)據(jù)挖掘MapReduce架構(gòu)，架構(gòu)分為核心層和用戶層

3、，核心層封裝了MapReduce的操作，用戶層提供給用戶擴(kuò)展接口，通過具體問題實(shí)現(xiàn)具體的遺傳算法，可以有效的處理數(shù)據(jù)挖掘算法在海量數(shù)據(jù)方面的應(yīng)用。架構(gòu)包括六個(gè)組件，其中Diver組件是框架的主要部分，主要功能是實(shí)現(xiàn)用戶交互并負(fù)責(zé)啟動(dòng)集群上的Jobs;Generator組件主要作用是通過調(diào)用用戶層的遺傳算法實(shí)現(xiàn)，然后配合Driver啟動(dòng)Job完成種群的進(jìn)化;Terminator組件的作用是在Generator過程中判斷是否滿足終止條件;I

4、nitialiser組件負(fù)責(zé)初始化種群，該組件是可選的;Migrator組件負(fù)責(zé)種群遷移策略的實(shí)現(xiàn)，由用戶層實(shí)現(xiàn);最后的SolutionFilter組件則是將符合條件的個(gè)體篩選出來，每個(gè)組件相互協(xié)作完成架構(gòu)的功能。
　　本文用三個(gè)算法對(duì)架構(gòu)性能進(jìn)行驗(yàn)證，首先設(shè)計(jì)實(shí)現(xiàn)了針對(duì)K-Medoids的遺傳算法，以聚類準(zhǔn)確率為個(gè)體適應(yīng)度值，利用MapReduce加強(qiáng)聚類計(jì)算，實(shí)驗(yàn)顯示得到良好的聚類效果。其次設(shè)計(jì)實(shí)現(xiàn)了針對(duì)旅行商問題(Trave

5、ling SalesmanProblem)的遺傳算法，以個(gè)體所經(jīng)過城市距離的倒數(shù)作為適應(yīng)度函數(shù)，距離越短個(gè)體的適應(yīng)度值越高，實(shí)驗(yàn)結(jié)果表明，在架構(gòu)中運(yùn)行的TSP算法能有效處理大數(shù)據(jù)并且比同等級(jí)的算法能更快發(fā)現(xiàn)最優(yōu)解。最后，設(shè)計(jì)實(shí)現(xiàn)了針對(duì)特征子集選擇(Feature Subset Selection)問題的遺傳算法，以特征選擇的分類準(zhǔn)確率作為適應(yīng)度值，實(shí)驗(yàn)結(jié)果表明，運(yùn)行在架構(gòu)下的FSS算法能更快速收斂并提高了準(zhǔn)確率。
　　綜上，本文提