基于改進(jìn)磷蝦群算法的K-means算法

劉 唐 ，周 煒， 李志鵬，權(quán) 文

(1.空軍工程大學(xué)，陜西 西安 710051；2.西安財經(jīng)學(xué)院行知學(xué)院，陜西 西安 710038；3.中國人民解放軍75837部隊，廣東 廣州 510630)

0 引言

聚類是一種常用的無監(jiān)督學(xué)習(xí)方法[1]，廣泛應(yīng)用于入侵檢測、機(jī)器學(xué)習(xí)、圖像處理、數(shù)據(jù)挖掘等領(lǐng)域。聚類試圖將數(shù)據(jù)中的樣本劃分為若干類，使同一類的樣本盡可能彼此相似，不同類的樣本盡可能不同。通過對無標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律，為進(jìn)一步的數(shù)據(jù)分析提供基礎(chǔ)。

K-means算法作為一種基于中心的經(jīng)典聚類算法，結(jié)構(gòu)簡單、收斂速度快，但易受初始聚類中心選擇的影響，導(dǎo)致陷入局部最優(yōu)，使聚類結(jié)果不穩(wěn)定[2]，初始類別數(shù)的設(shè)定直接影響聚類結(jié)果的優(yōu)劣。而實際情況中，最佳聚類數(shù)很難預(yù)知，算法自身自動得到最佳聚類數(shù)就尤為重要。

群智能優(yōu)化算法是一種模擬自然界的生物活動以及群體智能行為的計算智能算法。常用的算法有粒子群算法、蟻群算法、遺傳算法、人工蜂群算法等。Gandomi等人在研究自然界磷蝦群覓食活動的規(guī)律后，于2012年提出了一種新型的群智能優(yōu)化算法——磷蝦群(Krill Herd，KH)算法[3]，該算法結(jié)構(gòu)簡單、需要控制的參數(shù)少、收斂速度快。群智能優(yōu)化算法因其具有極好的全局尋優(yōu)能力而常被應(yīng)用于聚類領(lǐng)域，文獻(xiàn)[4—5]提出了應(yīng)用粒子群算法來優(yōu)化聚類算法，文獻(xiàn)[6—7]提出了一種采用蟻群算法來解決聚類問題，文獻(xiàn)[8]提出了遺傳算法的聚類算法，文獻(xiàn)[9—10]采用人工蜂群算法來解決聚類問題。

針對磷蝦群算法易陷入局部最優(yōu)、搜索能力弱，及K-means算法易受初始聚類中心選擇影響的問題，提出了改進(jìn)磷蝦群算法的K-means算法。該算法先對磷蝦群算法進(jìn)行改進(jìn)，改善算法性能，再用改進(jìn)后的磷蝦群算法優(yōu)化K-means算法的聚類中心，降低初始聚類中心的影響，避免陷入局部最優(yōu)，提升算法的穩(wěn)定性，同時引入聚類綜合有效性評價函數(shù)自動得到最佳聚類數(shù)。

1 聚類與標(biāo)準(zhǔn)磷蝦群算法

1.1 聚類概述

聚類問題通常是給定一個數(shù)量為m的樣本集D={x1,x,…xm}，將其聚類劃分為k個不同類C={C1,C2,…,Ck}，這里聚類目標(biāo)函數(shù)取均方誤差：

(1)

式(1)中，zj為聚類中心，E值越小，聚類效果越好。

1.1.1K-means算法

K-means算法的主要流程具體如下：

1)從樣本集D中隨機(jī)選擇k個樣本作為初始聚類中心；

2)計算各樣本與各聚類中心的距離：dji=‖xi-zj‖2，根據(jù)距離遠(yuǎn)近把各樣本劃入相應(yīng)的聚類；

3)計算更新聚類中心：

(2)

重新轉(zhuǎn)入2)計算。

1.1.2聚類有效性評價

為了與最小化聚類間的相似度和最大化聚類內(nèi)相似度的目標(biāo)相符合，本文用聚類結(jié)果分布的自然屬性來評價聚類間的分離性和聚類內(nèi)的同一性，構(gòu)造聚類綜合有效性評價函數(shù)，利用此函數(shù)分析不同情況下的聚類效果，獲得最佳聚類數(shù)[11]。

聚類密集性與聚類內(nèi)方差有關(guān)，給定樣本集D={x1,x2,…,xm}，聚類內(nèi)方差定義為：

(3)

根據(jù)聚類結(jié)果分布，聚類密集性定義為：

(4)

由此可以看出聚類內(nèi)方差越小，聚類密集性越好，數(shù)據(jù)樣本的同一性越高。特殊的某一樣本個體被單獨(dú)分為一類，則聚類密集性取值為0。

聚類鄰近性定義為：

(5)

式(5)中，d(zi,zj)表示聚類中心zi與聚類中心zj之間的歐氏距離，σ是高斯常數(shù)，聚類鄰近性與聚類間距離成反比，即鄰近性越小越好。特殊的某一樣本個體被單獨(dú)分為一類，則聚類鄰近性取值為0。

綜合以上聚類密集性與聚類鄰近性構(gòu)造出聚類綜合有效性評價函數(shù)：

Cp=1-[α×Cv+(1+α)×Prox]

(6)

式(6)中，α∈[0,1]，聚類綜合有效性評價函數(shù)Cp值越大說明聚類效果越好。

1.2 標(biāo)準(zhǔn)磷蝦群算法

磷蝦群算法[12-14](krill herd，KH)是一種模擬磷蝦群覓食行為的啟發(fā)式優(yōu)化算法，以每只磷蝦表示問題的可能解，通過模擬每只磷蝦覓食過程中位置的不斷更新來尋找最優(yōu)解。

在KH算法中，將磷蝦個體的移動主要分為以下三個部分，其第k次的移動可表示為：

(7)

(8)

(9)

(10)

(11)

式(11)中，Dmax為的最大隨機(jī)擴(kuò)散速度，Imax為最大迭代次數(shù)，δi為當(dāng)前的隨機(jī)擴(kuò)散方向向量，且為[-1,1]區(qū)間的隨機(jī)數(shù)。

每只磷蝦在上述3種因素的綜合影響下，不斷更新自身位置，直至當(dāng)前最優(yōu)磷蝦位置對應(yīng)的解符合條件要求或達(dá)到最大迭代次數(shù)后停止。

2 改進(jìn)的磷蝦群算法

作為啟發(fā)式的智能優(yōu)化算法，磷蝦群算法在周圍磷蝦的引導(dǎo)運(yùn)動和磷蝦本身的覓食運(yùn)動中都體現(xiàn)出全局尋優(yōu)能力和局部探索能力[15]。算法必須協(xié)調(diào)好兩者之間的關(guān)系，才能使得算法性能更好地發(fā)揮。

在迭代次數(shù)增加到一定后，大多數(shù)磷蝦都會向同一方向運(yùn)動，從而導(dǎo)致磷蝦群的個體特異性降低，易陷入局部最優(yōu)。迭代過程中磷蝦群的歷史最優(yōu)解信息未存儲，導(dǎo)致在最大迭代次數(shù)時得到的最優(yōu)解未必是真正最優(yōu)解，這可能造成算法的穩(wěn)定性能下降。本文提出一種動態(tài)分群策略，并在迭代過程中引入精英引領(lǐng)機(jī)制，在磷蝦本身的隨機(jī)擴(kuò)散運(yùn)動中添加一種隨機(jī)變異因子對算法進(jìn)行改進(jìn)[16-17]。

2.1 混沌初始化

在磷蝦群算法尋優(yōu)過程中，編碼形成的初始種群的聚散程度與分布關(guān)系到整個解空間的均勻程度，將影響算法的尋優(yōu)性能，導(dǎo)致聚類效果不理想。本文首先隨機(jī)生成k個混沌序列初始值Xi(0)，再利用Logistic混沌映射：

Xi(n+1)=μXi(n)[1-Xi(n)]

(12)

迭代生成若干新的混沌序列。其中μ為混沌映射參數(shù)，μ∈[1,4]，Xi(n)是第n次迭代時的位置。

通過混沌映射生成的混沌序列Xi可以覆蓋整個解空間，計算生成的混沌序列的適應(yīng)度值，選出N個適應(yīng)度較優(yōu)的混沌序列獲得規(guī)模為N的初始種群。這種生成策略既能保證種群初始化的多樣性、隨機(jī)性，又有利于通過混沌映射實現(xiàn)對整個解空間的遍歷。

2.2 動態(tài)分群

在磷蝦群算法尋優(yōu)過程中，隨著迭代次數(shù)增加，磷蝦群會向局部最優(yōu)逼近，尋優(yōu)范圍逐漸減小，可能導(dǎo)致磷蝦群個體位置更新變慢甚至停滯，算法出現(xiàn)早熟現(xiàn)象。因此，考慮每次迭代后，通過混沌映射來改變磷蝦群個體位置，遍歷解空間來避免陷入局部最優(yōu)，但這必定會造成重復(fù)搜索，計算量增大，降低算法效率。針對這種情況，本文提出一種動態(tài)分群策略，根據(jù)適應(yīng)度值的大小把磷蝦群劃分成不同的類，再對不同的類采取相應(yīng)的調(diào)整機(jī)制，使得避免早熟的同時減少重復(fù)搜索，提高算法效率。

動態(tài)分群依據(jù)磷蝦群個體適應(yīng)度將每次迭代的種群分為退化磷蝦、常規(guī)磷蝦、精英磷蝦。主要按照以下策略分群：

對不同的類采取相應(yīng)的調(diào)整機(jī)制：

1)退化磷蝦是當(dāng)前磷蝦群中適應(yīng)度值較差的個體，可能會對磷蝦群的優(yōu)化造成阻礙，使算法效率降低。因此，考慮通過混沌映射生成新的混沌序列，并將退化磷蝦用新的適應(yīng)度較好的混沌序列替換來改進(jìn)，對退化磷蝦進(jìn)行混沌映射的具體過程如下：首先，按照前面混沌初始化方法生成新的混沌序列；然后迭代計算各新的混沌序列的適應(yīng)度值并記錄最優(yōu)值；最后達(dá)到最大迭代次數(shù)后，比較當(dāng)前種群的最優(yōu)磷蝦與新的最優(yōu)混沌序列，若新的序列適應(yīng)度更好，則將退化磷蝦當(dāng)前的最優(yōu)磷蝦用新的最優(yōu)混沌序列替換，否則用此序列隨機(jī)替換當(dāng)前種群的某一磷蝦個體。

2)常規(guī)磷蝦是介于退化磷蝦與精英磷蝦之間的磷蝦個體，在迭代過程中隨機(jī)性很大，對此采用雙邊引導(dǎo)，即在基本搜索的同時進(jìn)行混沌映射，使其可以在更大范圍搜索。

3)精英磷蝦是當(dāng)前種群中適應(yīng)度值較優(yōu)的磷蝦個體，與最優(yōu)解的距離較近，因此讓其繼續(xù)按照標(biāo)準(zhǔn)磷蝦群算法進(jìn)行搜索。

2.3 精英引領(lǐng)與隨機(jī)變異

在標(biāo)準(zhǔn)磷蝦群算法迭代過程中，隨著迭代次數(shù)的增加，磷蝦種群逐漸逼近最優(yōu)，但是由于磷蝦本身的隨機(jī)擴(kuò)散運(yùn)動的不確定性，并不能保證各磷蝦都向最優(yōu)方向逼近，使得后面迭代磷蝦的最優(yōu)并不一定是歷史最優(yōu)，可能導(dǎo)致最終的最優(yōu)解不是全局最優(yōu)解。

針對這個問題，首先在迭代過程中引入精英引領(lǐng)機(jī)制：在更新當(dāng)前磷蝦個體位置前，對比各磷蝦個體的適應(yīng)度值，取適應(yīng)度最優(yōu)的磷蝦個體為精英并記錄，在迭代更新當(dāng)前磷蝦個體位置后，再將當(dāng)前磷蝦個體與精英對比，選擇適應(yīng)度更優(yōu)的作為新的精英并記錄。從而確保算法迭代結(jié)束時，得到的最優(yōu)解是歷史最優(yōu)解。其次，再對磷蝦本身的隨機(jī)擴(kuò)散運(yùn)動添加一種隨機(jī)變異因子進(jìn)行改進(jìn)。本文引入的隨機(jī)變異因子λ，如下：

λ=μ·fit

(13)

(14)

易知，磷蝦本身的隨機(jī)擴(kuò)散幅度由μ和fit一起決定。在算法迭代的前期，μ值較大，能產(chǎn)生較大幅度的變異，使求參數(shù)最優(yōu)解的全局遍歷能力增加，隨著迭代次數(shù)的增加，μ值逐漸減小，全局磷蝦本身的隨機(jī)擴(kuò)散幅度減小，而磷蝦個體在自身周邊搜索較精確，此時算法就有較好的局部探索能力，加快了收斂速度。在算法迭代的后期，磷蝦個體都會向全局最優(yōu)的位置逼近，易陷入局部最優(yōu)。而此時較大fit值的磷蝦就擁有較強(qiáng)的隨機(jī)變異能力，這些磷蝦能有更大隨機(jī)擴(kuò)散幅度，這樣就增加了磷蝦個體的特異性，使得算法尋優(yōu)范圍擴(kuò)大，避免陷入局部最優(yōu)。

精英引領(lǐng)機(jī)制和隨機(jī)變異因子λ的引入綜合考慮了迭代過程和磷蝦個體的具體情況，使得磷蝦的變異具有目的性和多樣性，加快了收斂速度，同時更好地避免了算法陷入局部最優(yōu)，增加了算法的穩(wěn)定性。

3 改進(jìn)磷蝦群算法的K-means算法

遵循K-means算法的基本聚類準(zhǔn)則，用改進(jìn)后的磷蝦群算法優(yōu)化K-means算法的聚類中心，降低初始聚類中心的影響，獲得在不同聚類數(shù)下的聚類情況，同時引入聚類綜合有效性評價函數(shù)自動得到最佳聚類數(shù)。

這里選取均方誤差E為適度函數(shù)fit，即

(15)

用改進(jìn)后的磷蝦群算法優(yōu)化K-means算法的聚類中心，主要是因為磷蝦群算法是一種不受初始值影響的隨機(jī)優(yōu)化算法，同時擁有全局尋優(yōu)能力和局部探索能力，可以避免陷入局部最優(yōu)，使得可以在全局尋優(yōu)空間中獲得的聚類中心有較小的均方誤差，并通過改進(jìn)磷蝦群算法使得結(jié)果盡可能向最優(yōu)逼近。而且由于對數(shù)據(jù)劃分是按照與聚類中心的歐氏距離最小準(zhǔn)則，則聚類中心的細(xì)微差別對結(jié)果不會有太大的影響，那么用改進(jìn)后的磷蝦群算法優(yōu)化K-means算法的聚類中心得到的結(jié)果就可以當(dāng)作最佳聚類結(jié)果。再通過聚類綜合有效性評價函數(shù)可以自動得到對應(yīng)情況下的最佳聚類數(shù)。

算法的主要流程：

1)規(guī)定聚類數(shù)的取值范圍，令初始聚類數(shù)k=2；

2)根據(jù)當(dāng)前聚類數(shù)對樣本數(shù)據(jù)進(jìn)行混沌初始化，再計算聚類目標(biāo)函數(shù)獲得并記錄當(dāng)前最優(yōu)解；

3)循環(huán)迭代進(jìn)行改進(jìn)磷蝦群算法的三個運(yùn)動，循環(huán)迭代結(jié)束得到本次操作的最優(yōu)聚類結(jié)果，并計算聚類綜合有效性評價函數(shù)Cp；

4)令k=k+1，當(dāng)k

5)按照聚類綜合有效性評價函數(shù)Cp計算最佳聚類數(shù)，然后獲得對應(yīng)的聚類結(jié)果。

4 實驗結(jié)果與分析

實驗主要驗證了算法以下兩方面性能：改進(jìn)的磷蝦群算法的尋優(yōu)能力；改進(jìn)磷蝦群算法的K-means算法獲取最佳聚類數(shù)的性能。

4.1 改進(jìn)磷蝦群算法尋優(yōu)性能分析

本文將改進(jìn)磷蝦群算法(IKH)與標(biāo)準(zhǔn)磷蝦群(KH)、協(xié)同人工蜂群算法(CABC)、混合遺傳算法(HGA)、協(xié)同粒子群算法(CPSO)進(jìn)行比較，通過多種基準(zhǔn)函數(shù)[10,18]來測試算法的性能。

種群規(guī)模設(shè)定為100，limit=100，所有樣本變量維數(shù)設(shè)定為30，以函數(shù)評估次數(shù)FEs(function evalutions)為評測標(biāo)準(zhǔn) (FEs≤100,000)。表1是IKH與幾種算法在基準(zhǔn)函數(shù)下的均值和標(biāo)準(zhǔn)差(算法運(yùn)行30次，部分算法結(jié)果來自文獻(xiàn)[10,18])。

表1 IKH與幾種算法性能對比

由表1可知，對于實驗的6種基準(zhǔn)函數(shù)，KH算法在2種基準(zhǔn)函數(shù)的結(jié)果為性能最優(yōu)，CPSO算法在基準(zhǔn)函數(shù)Schwefel的結(jié)果表現(xiàn)最優(yōu)，而IKH算法在其中5種基準(zhǔn)函數(shù)的結(jié)果表現(xiàn)性能最優(yōu)，其他算法性能略差。IKH算法與KH算法單獨(dú)相比，IKH算法在4種基準(zhǔn)函數(shù)上性能更優(yōu)。縱觀全局，IKH算法在實驗中更好地避免陷入局部最優(yōu)，整體性能表現(xiàn)最優(yōu)。

4.2 最佳聚類數(shù)尋找性能分析

實驗通過人造數(shù)據(jù)和UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集來測試驗證算法在最佳聚類數(shù)尋找的效果。實驗數(shù)據(jù)有人造數(shù)據(jù)S及Iris、Wine、Glass、Synthetic，如表2所示。

驗證算法的聚類正確率時，根據(jù)數(shù)據(jù)集資料先給出其標(biāo)準(zhǔn)聚類數(shù)，驗證算法最佳聚類數(shù)尋找性能時，記錄運(yùn)行20次得到正確的最佳聚類數(shù)的次數(shù)，具體情況見表3。

表2 數(shù)據(jù)集描述

表3 各類數(shù)據(jù)集運(yùn)行20次的情況

由表3可知，本文算法在人造數(shù)據(jù)集和UCI真實數(shù)據(jù)都有較好的聚類正確率，而對于最佳聚類數(shù)尋找，本文算法對分離性能較好的人造數(shù)據(jù)集S和真實數(shù)據(jù)集Iris效果良好，對于其他數(shù)據(jù)集，也能找到標(biāo)準(zhǔn)最佳聚類數(shù)，效果較好，但有待進(jìn)一步提高?？傮w來看本文算法性能較好，能夠適用各類數(shù)據(jù)集。

5 結(jié)論

本文提出了基于改進(jìn)磷蝦群算法的K-means算法，該算法通過混沌初始化、動態(tài)分群、精英引領(lǐng)和隨機(jī)變異策略對磷蝦群算法進(jìn)行改進(jìn)，協(xié)調(diào)好算法的全局尋優(yōu)能力和局部探索能力，提高了算法的綜合尋優(yōu)能力。實驗驗證表明，改進(jìn)磷蝦群算法在保證較快收斂速度的基礎(chǔ)上提升了全局尋優(yōu)能力，與其他算法進(jìn)行性能對比分析，該算法各方面性能優(yōu)勢明顯。再針對K-means算法的缺點(diǎn)提出改進(jìn)磷蝦群算法的K-means算法，并引入最佳聚類數(shù)自適應(yīng)機(jī)制，通過實驗測試驗證了算法的有效性。