【摘要】：近年來(lái),隨著信息技術(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)。為了解決這一問(wèn)題,研究人員將傳統(tǒng)數(shù)據(jù)挖掘算法與新興技術(shù)如云計(jì)算平臺(tái)等融合,利用分布式計(jì)算能力提高算法的性能,取得了良好效果。但是由于數(shù)據(jù)挖掘算法種類繁多,單一的數(shù)據(jù)挖掘算法需要特定的實(shí)現(xiàn)模式,沒(méi)有通用的架構(gòu)滿足數(shù)據(jù)挖掘算法的多樣性,并能同時(shí)提高算法的性能。本文在前人經(jīng)驗(yàn)的基礎(chǔ)上,提出了一種基于遺傳算法的分布式數(shù)據(jù)挖掘MapReduce架構(gòu),旨在幫助用戶更通用的處理數(shù)據(jù)挖掘算法并提升算法的性能。架構(gòu)要素之一的MapReduce提供良好的分布式計(jì)算能力,另一要素遺傳算法具有良好的全局搜索和優(yōu)化能力,通過(guò)模擬種群進(jìn)化的方式搜索到最優(yōu)解,使得用戶只需要實(shí)現(xiàn)遺傳算法而不必?fù)?dān)心算法的并行化。本文的主要貢獻(xiàn)如下,提出了一種基于遺傳算法的分布式數(shù)據(jù)挖掘MapRed uce架構(gòu),架構(gòu)分為核心層和用戶層,核心層封裝了MapReduce的操作,用戶層提供給用戶擴(kuò)展接口,通過(guò)具體問(wèn)題實(shí)現(xiàn)具體的遺傳算法,可以有效的處理數(shù)據(jù)挖掘算法在海量數(shù)據(jù)方面的應(yīng)用。架構(gòu)包括六個(gè)組件,其中Diver組件是框架的主要部分,主要功能是實(shí)現(xiàn)用戶交互并負(fù)責(zé)啟動(dòng)集群上的Jobs;Generator組件主要作用是通過(guò)調(diào)用用戶層的遺傳算法實(shí)現(xiàn),然后配合Driver啟動(dòng)Job完成種群的進(jìn)化;Terminator組件的作用是在Generator過(guò)程中判斷是否滿足終止條件;Initialiser組件負(fù)責(zé)初始化種群,該組件是可選的;Migrator組件負(fù)責(zé)種群遷移策略的實(shí)現(xiàn),由用戶層實(shí)現(xiàn);最后的SolutionFilter組件則是將符合條件的個(gè)體篩選出來(lái),每個(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ì)旅行商問(wèn)題(Traveling Salesman Problem)的遺傳算法,以個(gè)體所經(jīng)過(guò)城市距離的倒數(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)問(wèn)題的遺傳算法,以特征選擇的分類準(zhǔn)確率作為適應(yīng)度值,實(shí)驗(yàn)結(jié)果表明,運(yùn)行在架構(gòu)下的FSS算法能更快速收斂并提高了準(zhǔn)確率。綜上,本文提出的基于遺傳算法的分布是數(shù)據(jù)挖掘MapReduce架構(gòu)在處理海量數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘算法時(shí)具有良好的表現(xiàn),通過(guò)特定問(wèn)題的遺傳算法實(shí)現(xiàn),利用分布式計(jì)算提高算法性能,同時(shí)利用遺傳算法的全局搜索優(yōu)化能力快速找到最優(yōu)解,研究表明,該架構(gòu)幫助數(shù)據(jù)挖掘算法在處理海量數(shù)據(jù)時(shí)效果和性能得到提升。
[Abstract]:In recent years, with the rapid development of information technology, incalculable mass data is produced directly or indirectly, which brings new challenges to traditional data mining algorithms. How to improve the generality and performance of traditional data mining algorithms in mass data environment has become a hot research topic. In order to solve this problem, researchers combine traditional data mining algorithms with emerging technologies such as cloud computing platform, and improve the performance of the algorithm by using distributed computing power, and obtain good results. However, because there are many kinds of data mining algorithms, a single data mining algorithm needs a specific implementation pattern, there is no universal architecture to meet the diversity of data mining algorithms, and can improve the performance of the algorithm at the same time. Based on the previous experience, this paper proposes a distributed data mining MapReduce architecture based on genetic algorithm, which aims to help users process data mining algorithms more generally and improve the performance of the algorithms. MapReduce, one of the architectural elements, provides good distributed computing power, while the other element genetic algorithm has a good global search and optimization capability, and the optimal solution can be found by simulating population evolution. Users only need to implement genetic algorithm and do not have to worry about the parallelization of the algorithm. The main contributions of this paper are as follows: a distributed data mining MapRed uce architecture based on genetic algorithm is proposed. The architecture is divided into core layer and user layer. The core layer encapsulates the operation of MapReduce, and the user layer provides the user with extended interface. The application of data mining algorithm in mass data can be effectively processed by implementing specific genetic algorithm. The architecture consists of six components, in which the Diver component is the main part of the framework. The main function of the architecture is to realize user interaction and start the Jobs;Generator component on the cluster by calling the genetic algorithm in the user layer. Then the role of the evolutionary Terminator component to start the Job complete population with Driver is to determine whether the terminating condition is satisfied or not and initialize the population in the Generator process. The component is the optional Job component which is responsible for the implementation of the population migration strategy, which is implemented by the user layer. The final SolutionFilter component is to filter out qualified individuals, and each component collaborates with each other to complete the architectural functions. In this paper, three algorithms are used to verify the performance of the architecture. Firstly, the genetic algorithm for K-Medoids is designed and implemented. The clustering accuracy is taken as the individual fitness value, and the clustering calculation is strengthened by MapReduce. The experimental results show that the clustering effect is good. Secondly, a genetic algorithm for traveling salesman problem (Traveling Salesman Problem) is designed and implemented. The reciprocal of the city distance is taken as the fitness function. The shorter the distance is, the higher the fitness is. The experimental results show that, The TSP algorithm running in the architecture can deal with big data effectively and can find the optimal solution faster than the same level algorithm. Finally, a genetic algorithm for feature subset selection (Feature Subset Selection) problem is designed and implemented. The classification accuracy of feature selection is taken as the fitness value. The experimental results show that the FSS algorithm running in the framework can converge faster and improve the accuracy. In summary, the distribution based on genetic algorithm proposed in this paper is that the data mining MapReduce architecture has a good performance in dealing with the data mining algorithm under the massive data environment, which is realized by the genetic algorithm with specific problems. Distributed computing is used to improve the performance of the algorithm, and the global search optimization ability of genetic algorithm is used to quickly find the optimal solution. The research shows that the architecture can improve the efficiency and performance of the data mining algorithm in processing massive data.
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王興成,鄭紫微,賈欣樂(lè);模糊遺傳算法及其應(yīng)用研究[J];計(jì)算技術(shù)與自動(dòng)化;2000年02期

2 吳瑞鏞,徐大紋;具有年齡結(jié)構(gòu)的遺傳算法[J];桂林電子工業(yè)學(xué)院學(xué)報(bào);2001年04期

3 楊艷麗,史維祥;一種新的優(yōu)化算法—遺傳算法的設(shè)計(jì)[J];液壓氣動(dòng)與密封;2001年02期

4 楊宜康,李雪,彭勤科,黃永宣;具有年齡結(jié)構(gòu)的遺傳算法[J];計(jì)算機(jī)工程與應(yīng)用;2002年11期

5 谷峰,吳勇,唐俊;遺傳算法的改進(jìn)[J];微機(jī)發(fā)展;2003年06期

6 ;遺傳算法[J];計(jì)算機(jī)教育;2004年10期

7 趙義紅,李正文,何其四;生物信息處理系統(tǒng)遺傳算法探討[J];成都理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年05期

8 劉坤,劉偉波,吳忠強(qiáng);基于模糊遺傳算法的電液位置伺服系統(tǒng)控制[J];黑龍江科技學(xué)院學(xué)報(bào);2005年04期

9 張英俐,劉弘 ,馬金剛;遺傳算法作曲系統(tǒng)研究[J];信息技術(shù)與信息化;2005年05期

10 丁發(fā)智;;淺談遺傳算法[J];烏魯木齊成人教育學(xué)院學(xué)報(bào);2005年04期

相關(guān)會(huì)議論文 前10條

1 陳家照;廖海濤;張中位;羅寅生;;一種改進(jìn)的遺傳算法及其在路徑規(guī)劃中的應(yīng)用[A];2009系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2009年

2 李國(guó)云;劉穎;薛梅;鄔志敏;;遺傳算法在高溫空冷冷凝器優(yōu)化設(shè)計(jì)中的應(yīng)用[A];第五屆全國(guó)制冷空調(diào)新技術(shù)研討會(huì)論文集[C];2008年

3 王志軍;李守春;張爽;;改進(jìn)的遺傳算法在反演問(wèn)題中的應(yīng)用[A];新世紀(jì) 新機(jī)遇 新挑戰(zhàn)——知識(shí)創(chuàng)新和高新技術(shù)產(chǎn)業(yè)發(fā)展（上冊(cè)）[C];2001年

4 任燕翔;姜立;劉連民;從滋慶;;改進(jìn)遺傳算法在三維日照方案優(yōu)化中的應(yīng)用[A];工程三維模型與虛擬現(xiàn)實(shí)表現(xiàn)——第二屆工程建設(shè)計(jì)算機(jī)應(yīng)用創(chuàng)新論壇論文集[C];2009年

5 韓娟;;遺傳算法概述[A];第三屆河南省汽車(chē)工程科技學(xué)術(shù)研討會(huì)論文集[C];2006年

6 龐國(guó)仲;王元西;;基于遺傳算法控制步長(zhǎng)的定性仿真方法[A];'2000系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文集[C];2000年

7 張忠華;楊淑瑩;;基于遺傳算法的聚類設(shè)計(jì)[A];全國(guó)第二屆信號(hào)處理與應(yīng)用學(xué)術(shù)會(huì)議�？痆C];2008年

8 何翠紅;區(qū)益善;;遺傳算法及其在計(jì)算機(jī)編程中的應(yīng)用[A];1995年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議暨智能自動(dòng)化專業(yè)委員會(huì)成立大會(huì)論文集（下冊(cè)）[C];1995年

9 靳開(kāi)巖;張乃堯;;幾種實(shí)用遺傳算法及其比較[A];1996年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];1996年

10 王宏剛;曾建潮;李志宏;;攝動(dòng)遺傳算法[A];1996年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];1996年

相關(guān)重要報(bào)紙文章 前10條

1 林京;《神經(jīng)網(wǎng)絡(luò)和遺傳算法在水科學(xué)領(lǐng)域的應(yīng)用》將面市[N];中國(guó)水利報(bào);2002年

2 本報(bào)記者褚寧;數(shù)據(jù)挖掘如“挖金”[N];解放日?qǐng)?bào);2002年

3 周蓉蓉;數(shù)據(jù)挖掘需要點(diǎn)想像力[N];計(jì)算機(jī)世界;2004年

4 □中國(guó)電信股份有限公司北京研究院 張舒博 □北京郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 牛琨;走出數(shù)據(jù)挖掘的誤區(qū)[N];人民郵電;2006年

5 《網(wǎng)絡(luò)世界》記者 王瑩;數(shù)據(jù)挖掘保險(xiǎn)業(yè)的新藍(lán)海[N];網(wǎng)絡(luò)世界;2012年

6 劉俊麗;基于地理化的網(wǎng)絡(luò)數(shù)據(jù)挖掘與分析提升投資有效性[N];人民郵電;2014年

7 本報(bào)記者 連曉東;數(shù)據(jù)挖掘：金融信息化新熱點(diǎn)[N];中國(guó)電子報(bào);2002年

8 本報(bào)記者 鳳小華 朱仁康;“數(shù)字挖掘軟件”引領(lǐng)中國(guó)信息化新浪潮[N];中國(guó)電子報(bào);2003年

9 本報(bào)記者　史延廷;“成功企業(yè)數(shù)據(jù)挖掘暨數(shù)量化管理論壇”在京舉辦[N];中國(guó)旅游報(bào);2002年

10 朱小寧;數(shù)據(jù)挖掘：信息化戰(zhàn)爭(zhēng)的基礎(chǔ)工程[N];解放軍報(bào);2005年

相關(guān)博士學(xué)位論文 前10條

1 Amjad Mahmood;半監(jiān)督進(jìn)化集成及其在網(wǎng)絡(luò)視頻分類中的應(yīng)用[D];西南交通大學(xué);2015年

2 李險(xiǎn)峰;基于改進(jìn)遺傳算法的汽車(chē)裝配生產(chǎn)線平衡問(wèn)題研究[D];北京科技大學(xué);2017年

3 周輝仁;遞階遺傳算法理論及其應(yīng)用研究[D];天津大學(xué);2008年

4 郝國(guó)生;交互式遺傳算法中用戶的認(rèn)知規(guī)律及其應(yīng)用[D];中國(guó)礦業(yè)大學(xué);2009年

5 侯格賢;遺傳算法及其在跟蹤系統(tǒng)中的應(yīng)用研究[D];西安電子科技大學(xué);1998年

6 馬國(guó)田;遺傳算法及其在電磁工程中的應(yīng)用[D];西安電子科技大學(xué);1998年

7 唐文艷;結(jié)構(gòu)優(yōu)化中的遺傳算法研究和應(yīng)用[D];大連理工大學(xué);2002年

8 周激流;遺傳算法理論及其在水問(wèn)題中應(yīng)用的研究[D];四川大學(xué);2000年

9 劉冀成;基于改進(jìn)遺傳算法的生物電磁成像與磁場(chǎng)聚焦應(yīng)用研究[D];四川大學(xué);2005年

10 袁麗華;基于物種進(jìn)化的遺傳算法研究[D];南京航空航天大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 韓來(lái)明;基于遺傳算法的分布式數(shù)據(jù)挖掘MapReduce架構(gòu)研究[D];天津大學(xué);2016年

2 張英俐;基于遺傳算法的作曲系統(tǒng)研究[D];山東師范大學(xué);2006年

3 鐘海萍;原對(duì)偶遺傳算法與蟻群算法的一種融合算法[D];暨南大學(xué);2013年

4 李志添;模糊遺傳算法與資源優(yōu)化配置的預(yù)測(cè)控制[D];華南理工大學(xué);2015年

5 王琳琳;新型雙層液壓轎運(yùn)車(chē)車(chē)廂的設(shè)計(jì)研究[D];上海工程技術(shù)大學(xué);2015年

6 李海全;基于遺傳算法的建筑體形系數(shù)及迎風(fēng)面積比優(yōu)化方法研究[D];華南理工大學(xué);2015年

7 彭騫;基于遺傳算法的山區(qū)高等級(jí)公路縱斷面智能優(yōu)化方法研究[D];昆明理工大學(xué);2015年

8 周玉林;基于小波分析和遺傳算法的配電網(wǎng)故障檢測(cè)[D];昆明理工大學(xué);2015年

9 郭頌;基于粗糙集和遺傳算法的數(shù)字管道生產(chǎn)管理系統(tǒng)研究[D];昆明理工大學(xué);2015年

10 吳南;數(shù)值逼近遺傳算法的研究應(yīng)用[D];華南理工大學(xué);2015年

，

本文編號(hào)：2231191