基于混合PSO的K-means算法及并行化研究.pdf

1、數(shù)據(jù)挖掘有四種主要任務：關聯(lián)分析、聚類分析、預測建模、異常檢測。其中聚類分析是最重要的使用最廣泛的任務之一。高效率和高精度結果一直是數(shù)據(jù)挖掘追求的目標。為了實現(xiàn)這一目標，人們進行了多種研究，其中一種就是將其它算法應用到數(shù)據(jù)挖掘中，這些算法包括智能算法、啟發(fā)式算法，神經(jīng)網(wǎng)絡，模糊理論，粗糙集理論等等。論文中將禁忌搜索思想和粒子群優(yōu)化算法引入到K-me~s聚類算法中，以此來提高K-means聚類算法的效率和聚類結果的精度。 禁忌搜索

2、(Tabu Search)是一種智能啟發(fā)式的全局性鄰域搜索算法，它通過局部鄰域搜索機制和相應的禁忌準則來避免迂回搜索，并通過特赦準則來釋放一些被禁忌的優(yōu)良對象，從而保證搜索的多樣化和有效性，研究表明它可以克服演化算法容易陷入早熟的缺陷，最終實現(xiàn)全局優(yōu)化。粒子群優(yōu)化算法(Pmicle SwarmOpfimiz~on)是一種演化計算技術，它具有簡單、有效、收斂速度較快、全局搜索能力較強等特點，近年來受到學術界的高度關注，但是該算法也具有可能

3、陷入局部最優(yōu)進而導致結果精度低和收斂速度慢的缺點，因此在論文中使用禁忌搜索和控制參數(shù)等方法來改進粒子群優(yōu)化算法，從而提高該算法的效率和解的精度。K-means是基于劃分的聚類方法。它在目前的聚類分析中應用很廣泛。但是該算法的缺點是易陷入局部最優(yōu)，效率不高。而且聚類個數(shù)K常常是依據(jù)經(jīng)驗來確定，這將影響聚類結果。針對K-means算法的不足，把禁忌搜索思想和粒子群優(yōu)化算法引入到K-means聚類算法中，以提高K-means算法的效率和結果精

4、度。論文中研究了禁忌對象和禁忌表結構的選取、個體編碼方式的選取、慣性權重的改進、罰函數(shù)的方式及表達式的選取和構造、適應度函數(shù)的構造。實驗證明改進后的K-means算法的效率和結果精度都得到了提高。 為了進一步提高算法的執(zhí)行效率，論文中研究了K-means算法的并行化。通過種群或者子種群之間的等價關系來確定等價類，按等價類初步劃分種群，然后把劃分好的種群分配到Slave結點上，實現(xiàn)數(shù)據(jù)并行，最后由Master結點機進行匯總給出結果