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

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

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

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

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