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

1、隨著Internet、AI的快速發(fā)展，互聯(lián)網(wǎng)中積累了海量的數(shù)據(jù)。這些數(shù)據(jù)蘊含巨大的商業(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)運行

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

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

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