基于遺傳算法的并行化K--means聚類算法研究.pdf

1、隨著Internet、AI的快速發(fā)展，互聯(lián)網(wǎng)中積累了海量的數(shù)據(jù)。這些數(shù)據(jù)蘊(yùn)含巨大的商業(yè)價值，對于降低企業(yè)成本、提高企業(yè)收入具有重要作用，越來越受到企業(yè)的重視。但是，這些數(shù)據(jù)價值密度低、結(jié)構(gòu)復(fù)雜，如何從這些海量數(shù)據(jù)中快速、準(zhǔn)確地挖掘出這些有價值的信息是我們面臨的難題。利用數(shù)據(jù)挖掘技術(shù)可以幫助我們從這些海量數(shù)據(jù)中挖掘出有用信息。但是，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)在處理海量數(shù)據(jù)或者高維數(shù)據(jù)時存在準(zhǔn)確率偏低、分析時間過長等問題。而且，數(shù)據(jù)挖掘算法傳統(tǒng)運(yùn)行

2、模式大多在單機(jī)上執(zhí)行，數(shù)據(jù)量更大時，運(yùn)行時間會更長。目前，將傳統(tǒng)數(shù)據(jù)挖掘算法進(jìn)行改進(jìn)，然后結(jié)合分布式計算平臺Spark，將改進(jìn)后的聚類算法并行化并部署到集群上是解決上述問題的一個可行方案。為此，本文進(jìn)行了以下幾個方面的研究:
　　(1)研究了K-means算法，針對算法對初始聚類中心敏感、K值不確定、容易過早陷入局部最優(yōu)解的缺陷，提出使用遺傳算法(Genetic Algorithm，簡稱GA)對其進(jìn)行改進(jìn)。針對經(jīng)典GA算法求解全局

3、最優(yōu)解易過早收斂的缺點(diǎn)，本文對經(jīng)典GA算法進(jìn)行了兩方面的改進(jìn):一方面，對遺傳算法的適應(yīng)度函數(shù)進(jìn)行了線性變換，使其隨著環(huán)境的變化實(shí)時調(diào)整，設(shè)計了GA-K-means-L算法。另一方面，改進(jìn)傳統(tǒng)單一變異算子為并行選擇變異算子，解決了易陷入局部最優(yōu)解的缺陷，設(shè)計了GA-K-means-M算法。最后將這兩種算法進(jìn)行整合，設(shè)計了本文研究的GA-K-means算法。
　　(2)針對GA-K-means算法在單機(jī)環(huán)境下處理海量數(shù)據(jù)時性能過低的問

4、題，利用云計算平臺Spark對GA-K-means算法進(jìn)行并行化設(shè)計與實(shí)現(xiàn)。
　　(3)搭建Spark+YARN集群，對上述改進(jìn)進(jìn)行驗證。在單機(jī)環(huán)境下分別部署K-means算法、GA-K-means-L算法、GA-K-means-M算法以及GA-K-means算法。然后，對不同數(shù)據(jù)量、不同維度的數(shù)據(jù)集進(jìn)行聚類分析，最后，統(tǒng)計分析各個算法的平均準(zhǔn)確率、平均迭代次數(shù)以及平均耗時。在Spark+YARN集群環(huán)境下部署GA-K-means