基于MapReduce和遺傳算法的粗糙集屬性約簡(jiǎn)研究.pdf

1、隨著互聯(lián)網(wǎng)時(shí)代的蓬勃發(fā)展，以及物聯(lián)網(wǎng)、云計(jì)算等新興技術(shù)的涌現(xiàn)，大數(shù)據(jù)時(shí)代已經(jīng)到來。如何有效地從大數(shù)據(jù)中挖掘知識(shí)，釋放數(shù)據(jù)中隱含的巨大經(jīng)濟(jì)價(jià)值、科研價(jià)值和社會(huì)價(jià)值，成為當(dāng)今學(xué)術(shù)界和產(chǎn)業(yè)界研究的重大課題。粗糙集理論是由波蘭數(shù)學(xué)家Pawlak Z.提出的一種數(shù)據(jù)推理方法，這個(gè)理論工具在研究不精確知識(shí)表達(dá)、不完整數(shù)據(jù)、學(xué)習(xí)、歸納等方面非常強(qiáng)大，尤其在知識(shí)分類和知識(shí)發(fā)現(xiàn)方面的數(shù)據(jù)挖掘具有強(qiáng)大的能力。屬性約簡(jiǎn)是粗糙集理論的一個(gè)核心問題之一，國(guó)內(nèi)外學(xué)

2、者在這方面都有大量研究，提出了不少算法，其中大多數(shù)是啟發(fā)式屬性約簡(jiǎn)算法。它是以屬性重要度作為一個(gè)指引來對(duì)屬性進(jìn)行選擇或刪減，但這種算法并不能正確求解某些信息系統(tǒng)，有學(xué)者提出了遺傳約簡(jiǎn)算法，這種生物智能算法能有效解決啟發(fā)式算法無法覆蓋的部分信息系統(tǒng)。但遺傳約簡(jiǎn)算法由于遺傳算法本身具有的未成熟局部收斂這一缺陷，而導(dǎo)致遺傳約簡(jiǎn)算法可能出現(xiàn)未成熟局部收斂，所獲得的并非最小約簡(jiǎn)。
　　針對(duì)以上這些問題，本論文研究提出了并行化遺傳約簡(jiǎn)算法。將

3、多種群并行化于簡(jiǎn)單而強(qiáng)大的分布式并行處理系統(tǒng)MapReduce編程架構(gòu)，既能保留生物智能算法的優(yōu)勢(shì)，解決傳統(tǒng)算法所不能覆蓋的系統(tǒng)，又能解決遺傳算法未成熟局部收斂這一問題。本論文主要的研究工作如下:
　　在學(xué)習(xí)和研究了粗糙集、遺傳算法的理論概念、設(shè)計(jì)思想、算法步驟和工作原理等相關(guān)知識(shí)后。又系統(tǒng)學(xué)習(xí)了一種智能化的粗糙集屬性約簡(jiǎn)算法:遺傳約簡(jiǎn)算法。在這些經(jīng)典理論和算法模型的基礎(chǔ)上，又引入了新興的MapReduce理論及它的實(shí)現(xiàn)平臺(tái)Had

4、oop，提出了基于MapReduce的遺傳算法解決粗糙集屬性約簡(jiǎn)方案，簡(jiǎn)稱并行化遺傳約簡(jiǎn)算法。它的主要思想是，在遺傳約簡(jiǎn)算法的基礎(chǔ)上，進(jìn)行多種群并行化遺傳。傳統(tǒng)遺傳約簡(jiǎn)算法是單一種群的進(jìn)化遺傳以尋求最優(yōu)個(gè)體，這可能會(huì)出現(xiàn)未成熟局部收斂現(xiàn)象。若能多種群同時(shí)相對(duì)獨(dú)立進(jìn)化，從概率統(tǒng)計(jì)上而言，最終結(jié)果就不會(huì)出現(xiàn)未成熟局部收斂的結(jié)果。而且由于是并行化多種群進(jìn)化，所以在時(shí)效上不會(huì)太差?；谶@樣的想法，本論文設(shè)計(jì)了并行化遺傳約簡(jiǎn)算法的實(shí)驗(yàn)，并在論文中