一種基于改進果蠅優(yōu)化的K-mediods聚類算法

王全民，楊 晶，張帥帥

(北京工業(yè)大學(xué) 信息學(xué)部，北京 100124)

0 引 言

K-mediods算法是一種基于劃分的聚類算法，改進了K-means算法對噪聲和孤立點數(shù)據(jù)敏感的缺點，收斂速度較快且局部搜索能力較強[1]。但該算法聚類效率和精度較低、全局搜索能力較差等缺點仍需要改進[2]。文獻[3]針對K-medoids算法對初始聚類中心敏感的缺陷，提出了有效的解決方案，提高了算法的性能。文獻[4]提出了一種基于改進人工蜂群的K-mediods算法，由于結(jié)合粒計算和最大最小距離初始化蜂群降低了對噪聲的敏感性，聚類效果較穩(wěn)定。文獻[5]提出了基于核的自適應(yīng)聚類，該算法降低了K-medoids對初始值的敏感性。

針對K-mediods算法易陷入局部最優(yōu)的缺點，提出了一種基于改進果蠅優(yōu)化算法的 K-mediods聚類算法。將混沌映射思想應(yīng)用在果蠅群體的初始位置生成，保證初始位置能夠在全局更均勻的分布，算法后期根據(jù)群體適應(yīng)度方差判斷果蠅優(yōu)化算法是否處于局部收斂狀態(tài)，若是，利用禁忌搜索思想在最優(yōu)值鄰域內(nèi)尋求更優(yōu)解。將融入了混沌映射與禁忌搜索的果蠅優(yōu)化算法與傳統(tǒng)的K-mediods算法相結(jié)合，對每次聚類迭代中的簇中心進行尋優(yōu)，以提高K-mediods算法的全局搜索能力和聚類精度。

1 基于Logistic映射的混沌技術(shù)

混沌映射的基本思想是：將優(yōu)化變量(一個在[0，1]區(qū)間波動的變量)通過混沌映射規(guī)則映射到混沌變量空間的取值區(qū)間內(nèi)，利用混沌變量的遍歷性和規(guī)律性尋優(yōu)搜索，最后將獲得的優(yōu)化解線性轉(zhuǎn)化到優(yōu)化空間[6]。通常其系統(tǒng)方程為：

x(t+1)=μx(t)(1-x(t))

(1)

其中，μ為控制參數(shù)；t為迭代次數(shù)，x(t)∈[0,1]。當(dāng)μ=4時，系統(tǒng)出現(xiàn)混沌狀態(tài)，即不重復(fù)地隨機訪問系統(tǒng)解空間。

式2為混沌變量Cxi的一種變換算式。

Cx(t+1)i=4Cx(t)i(1-Cx(t)i),

i=1,2,…,N

(2)

其中，Cx(t)i為第i個混沌變量經(jīng)歷i次混沌映射之后得到的變量值。當(dāng)Cxi∈[0,1]，μ=4且Cxi≠{0．25,0.5,0.75}時，系統(tǒng)出現(xiàn)混沌狀態(tài)。優(yōu)化變量xi∈[xmin,xmax]，式3、式4為xi與Cxi∈[0,1]進行往返映射的過程。

Cxi=(xi-xmin)/(xmax-xmin)

(3)

(4)

2 禁忌搜索算法

禁忌(Tabu search，TS)算法是一種啟發(fā)式搜索算法，首先確定初始解，然后按照一定方向移動進行搜索試探。為了避免陷入局部最優(yōu)的狀況，在搜索過程中，禁忌搜索算法采用兩個策略：禁忌準(zhǔn)則和特赦準(zhǔn)則[7]。禁忌搜索建立一個禁忌表，它有一定的長度，儲存近期遍歷過的最優(yōu)解。根據(jù)鄰域計算函數(shù)計算鄰域內(nèi)的最優(yōu)值，查看禁忌表，以防近期遍歷過的最優(yōu)值重復(fù)遍歷陷入局部最優(yōu)，但若該解擴大了解空間的搜索范圍，則特赦保留。

TS算法步驟如下：

(1)給定初始解x0，計算f(x0)，令當(dāng)前點x=x0，最優(yōu)點xbest=x0，最優(yōu)值f(x)best=f(x0)。

(2)計算點x鄰域內(nèi)所有點的f(x)。

(3)尋找鄰域內(nèi)最優(yōu)值best(f(x))的對應(yīng)點x'。

(4)檢查是否滿足特赦準(zhǔn)則，若是，則令x=x'，xbest=x'，f(x)best=f(x')，執(zhí)行步驟6；否則轉(zhuǎn)入步驟5。

(5)判斷禁忌準(zhǔn)則：遍歷禁忌表，若沒有點x'，則x=x'，執(zhí)行轉(zhuǎn)入步驟6，否則在鄰域中刪除x'。轉(zhuǎn)入步驟3。

(6)更新禁忌表。判斷是否滿足終止條件，若滿足，則終止計算，否則轉(zhuǎn)入步驟2。

算法中禁忌準(zhǔn)則是指通過建立“禁忌表”模擬記憶，設(shè)定合適的禁忌長度，將近期遍歷過的解存放進去，將搜索到的最優(yōu)解與之比較，以防搜索陷入循環(huán)，從而避免局部最優(yōu)。特赦準(zhǔn)則是指在禁忌搜索算法的迭代過程中，若被訪問的解再次出現(xiàn)在禁忌長度內(nèi)，但搜索范圍可以得到很大的優(yōu)化時，為了保障全局最優(yōu)，可以接觸對該最優(yōu)值的禁止，進行重新選擇。

3 果蠅優(yōu)化算法(FOA)

果蠅優(yōu)化算法是一種群智能全局優(yōu)化搜索算法[8]。果蠅能夠通過特殊的嗅覺和視覺搜集空氣中的各種氣味以鎖定食物的位置，飛到食物位置附近后亦可使用敏銳的視覺發(fā)現(xiàn)食物和同伴聚集的位置，并且向該方向飛去[9]。

果蠅優(yōu)化算法的一般步驟為：

(1)初始化參數(shù)：最大迭代次數(shù)maxgen，種群規(guī)模sizepop，果蠅群體位置X_axis、Y_axis。

(2)根據(jù)式5、式6，果蠅個體通過敏銳的嗅覺搜尋食物，并向隨機方向移動。

Xi=X_axis+Random Value

(5)

Yi=Y_axis+Random Value

(6)

其中，Xi和Yi分別為果蠅個體飛向的橫縱坐標(biāo)。

(3)根據(jù)式7計算與原點的距離(Dist)，根據(jù)式8計算得到味道濃度判定值Si。

Disti=sqrt(Xi2+Yi2)

(7)

Si=1/Disti

(8)

(4)將味道濃度判定值Si代入味道濃度判定函數(shù)即適應(yīng)度函數(shù)，計算該果蠅個體位置處的味道濃度Smelli。

Smelli=Function(Si)

(9)

(5)找出該果蠅群體中的最佳味道濃度值bestSmell。

[bestSmell bestIndex]=max(Smell)

(10)

(6)保留最優(yōu)位置坐標(biāo)和最優(yōu)味道濃度值，果蠅群體利用視覺向該位置方向飛去。

(11)

(7)進入迭代尋優(yōu)，重復(fù)執(zhí)行步驟2～5，判斷味道濃度是否優(yōu)于最佳味道濃度值，若是則執(zhí)行步驟6，直至當(dāng)前迭代次數(shù)達到最大迭代數(shù)maxgen或已達到精度要求，則停止迭代。

4 基于混沌映射與禁忌搜索的果蠅混合優(yōu)化算法(LGTS-FOA)

混沌映射思想保證在解空間范圍不重復(fù)地訪問所有狀態(tài)，因此利用這一系統(tǒng)構(gòu)造果蠅群體初始位置可以很好地使果蠅群體較為均勻地分布在解空間。而禁忌搜索思想對于初值有很高的要求，因此考慮在FOA算法的后期引入該算法。將后期收斂解作為TS算法的初始解，采用果蠅群體的適應(yīng)度方差σ2來判斷后期收斂情況[10]，當(dāng)算法進入后期局部收斂狀態(tài)時，利用禁忌搜索算法跳出局部最優(yōu)。

4.1 LGTS-FOA算法

LGTS-FOA算法步驟如下：

(1)設(shè)置種群規(guī)模sizepop、最大迭代次數(shù)MCN和適應(yīng)度方差閾值δ。

(2)利用logistics多次映射的結(jié)果作為果蠅種群的初始位置。

(3)執(zhí)行FOA算法中的步驟2～5。

(4)利用式13得到當(dāng)前迭代中種群的適應(yīng)度方差。

(12)

(13)

(5)若σ2<δ，說明算法已進入后期收斂狀態(tài)，則執(zhí)行禁忌搜索算法的步驟2～6。否則執(zhí)行步驟6。

(6)如果當(dāng)前迭代得出的bestSmell優(yōu)于Smellbest，保存最佳濃度和最優(yōu)位置坐標(biāo)。判斷是否達到最大迭代次數(shù)，若是結(jié)束算法，否則，轉(zhuǎn)入步驟3。

4.2 有效性測試

文中采用4個經(jīng)典標(biāo)準(zhǔn)函數(shù)進行有效性測試：

(1)Sphere函數(shù)：

(2)Rosenbrock函數(shù)：

(3)Griewank函數(shù)：

(4)Rastrigin函數(shù)：

實驗參數(shù)設(shè)置：群體規(guī)模sizepop=30，最大迭代次數(shù)maxgen=1 000，適應(yīng)度方差δ=0.000 01。用4個經(jīng)典標(biāo)準(zhǔn)函數(shù)分別對改進的LGTS-FOA算法和經(jīng)典FOA算法進行測試，在相同的實驗條件下，各運行50次，比較二者的最優(yōu)值(best)、優(yōu)化均值(median)和標(biāo)準(zhǔn)差(std)，結(jié)果見表1。

表1 FOA與LGTS-FOA算法性能比較

從表1可以得出，在同等條件下，對于單峰函數(shù)(f1、f2)和多峰函數(shù)(f3、f4)來說，LGTS-FOA算法在均值和標(biāo)準(zhǔn)差上較經(jīng)典FOA算法都不同程度的改善，優(yōu)化均值精度提高了8～9個數(shù)量級，其中f1函數(shù)甚至提高30個數(shù)量級，說明LGTS-FOA在尋優(yōu)精度上有顯著提高；標(biāo)準(zhǔn)差的降低，說明LGTS-FOA比FOA的穩(wěn)定性要強；計算多峰函數(shù)Griewank函數(shù)和Rastrigin函數(shù)最優(yōu)值上LGTS-FOA算法的尋優(yōu)精度數(shù)量級提高了10個左右，說明其在高維多峰函數(shù)上的效果顯著。

觀察4個經(jīng)典標(biāo)準(zhǔn)函數(shù)迭代1 000次的果蠅群體適應(yīng)度進化過程。為方便顯示，縱坐標(biāo)選取以10為底適應(yīng)度的對數(shù)。在4個標(biāo)準(zhǔn)函數(shù)上經(jīng)典FOA算法表現(xiàn)為迭代前期收斂速度較快，之后陷入局部最優(yōu)，從而導(dǎo)致尋優(yōu)精度不夠高，而LGTS-FOA在保證了收斂速度的情況下，在陷入局部最優(yōu)時能夠迅速跳出，繼續(xù)尋優(yōu)，精度數(shù)量級有大幅提高。在Rosenbrock函數(shù)的優(yōu)化過程中雖然兩者精度都不高，但是FOA迭代初期就陷入局部最優(yōu)，尋優(yōu)速度減緩；而LGTS-FOA在迭代過程中，尋優(yōu)速度較快，LGTS-FOA性能總體優(yōu)于FOA。在Griewank函數(shù)、Rastrigin函數(shù)優(yōu)化過程中，由于初始位置采用混沌映射生成，因此適應(yīng)度的起始值要優(yōu)于FOA，有利于幫助LGTS-FOA更快速精確的尋優(yōu)。綜上所述，LGTS-FOA的適應(yīng)度收斂速度和精度均優(yōu)于FOA。

5 K-mediods聚類算法

K-mediods聚類算法的出現(xiàn)是對經(jīng)典K-means算法的一種改進，避免了K-means算法對噪聲和孤立點的敏感程度[11]。典型的K-mediods算法步驟如下[2]：

(1)隨機選取k個樣本作為初始聚類中心點集。

(2)依次計算數(shù)據(jù)集中所有樣本點到中心點的距離(歐幾里德距離)，將樣本點放入距離最近的中心點代表的簇中。

(3)在各簇中，計算與簇內(nèi)各樣本點距離的絕對誤差最小的點，替代舊中心點。

(4)如果聚類中心點集保持不變，算法終止；否則，更新中心點，重復(fù)執(zhí)行步驟2～4。

6 基于改進果蠅優(yōu)化算法的K-mediods聚類算法

6.1 適應(yīng)度函數(shù)

采用類內(nèi)距離衡量聚類的內(nèi)聚程度[12]，公式如下：

(14)

其中，zij表示第i個蜜蜂所表示的第j個聚類Cj的中心點；p表示類Cj中的非聚類中心點。

文中將類內(nèi)距離的倒數(shù)作為適應(yīng)度值。當(dāng)類內(nèi)距離最小時聚類效果最優(yōu)，此時適應(yīng)度值最大，表示如下：

fiti=1/Di

(15)

6.2 新聚類中心

每次迭代果蠅群體尋找出的最優(yōu)解并不能保證落到某個樣本坐標(biāo)上，因此需要確定新的聚類中心vij，表示距離聚類中心最近的樣本[13]，如式(16)。

(16)

其中，i=1,2,…,SN，j=1,2,…,k；n表示數(shù)據(jù)集個數(shù)；xt表示果蠅個體；zij表示第i只果蠅的第j維(聚類中心)。

6.3 算法步驟

6.3.1 果蠅編碼

初始化種群每一個體對應(yīng)一組聚類中心向量Zi=(zi1,zi2,…,zik)，其中zik表示第i個果蠅表示的第k簇的中心向量。

6.3.2 具體步驟

(1)初始化聚類個數(shù)k，群體規(guī)模sizepop，迭代數(shù)maxgen，味道濃度方差閾值δ。

(2)利用Logistic映射產(chǎn)生的混沌序列作為初始果蠅群體的位置編碼，利用式16將分別距離序列最近的k個樣本作為初始聚類中心點。

(3)根據(jù)歐幾里得距離計算，將剩余樣本加入到距離最近的聚類中心所代表的簇中。

(4)執(zhí)行LGTS-FOA算法步驟3～6，適應(yīng)度函數(shù)如式15所示。

(5)將此時最佳適應(yīng)度位置編碼利用式16得出新的聚類中心。

(6)對數(shù)據(jù)集進行一次K-mediods聚類，得到新的聚類中心，更新果蠅位置。

(7)若達到最大次數(shù)Maxgen或者聚類中心收斂，則停止算法；否則轉(zhuǎn)入步驟3，M=M+1。

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

為了驗證文中算法的有效性和可行性，分別采用K-mediods、文獻[14-15]提出的算法及文中算法，分別在隨機生成的人工數(shù)據(jù)集、Iris、Wine和Seeds數(shù)據(jù)集上進行測試。在10次實驗中，參數(shù)設(shè)置分別為：蜂群個數(shù)sizepop=30，最大循環(huán)次數(shù)Maxgen=100,δ=0.000 01。

7.1 人工數(shù)據(jù)集實驗

隨機生成的人工數(shù)據(jù)集屬性維度為2，樣本個數(shù)為300，類個數(shù)為3。人工數(shù)據(jù)集的樣本分布如圖1所示，算法在人工數(shù)據(jù)集上的聚類結(jié)果分別為圖1～5所示。

圖1 人工數(shù)據(jù)集分布

圖2 K-mediods聚類結(jié)果

圖3 文獻[14]算法的聚類結(jié)果

圖4 文獻[15]算法的聚類結(jié)果

圖5 文中算法的聚類結(jié)果

實驗結(jié)果表明，K-mediods、文獻[14-15]的算法及文中算法在人工數(shù)據(jù)集上的聚類準(zhǔn)確率分別為79.13%、82.56%、89.41%、93.79%。相比其他幾種算法，文中算法有較好的聚類效果，不但聚類準(zhǔn)確率較高而且聚類效果穩(wěn)定。通過比較圖2～5可知，文中算法對類邊界的處理最為精確。其他算法在邊界處理上出現(xiàn)較大偏差導(dǎo)致聚類準(zhǔn)確度不夠高，與原始數(shù)據(jù)樣本分布有較大偏差。

7.2 UCI標(biāo)準(zhǔn)數(shù)據(jù)集實驗

采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的Iris、Wine和Seeds。各類算法在上述幾種標(biāo)準(zhǔn)數(shù)據(jù)集中得到的平均正確率以及迭代次數(shù)如表2所示。

表2 不同算法對UCI數(shù)據(jù)集聚類結(jié)果的比較

通過比較表2發(fā)現(xiàn)，文中算法在迭代次數(shù)上與其他幾種算法相比有所減少，說明了采用映射思想初始化果蠅群體時，能夠?qū)⒊跏贾递^為均勻地分散在解空間，避免了初始聚類中心分布不理想對K-mediods算法的影響，改善了K-mediods算法對初始值敏感的缺點，從而減少了迭代次數(shù)；使用禁忌思想能夠避免陷入局部最優(yōu)解，提高聚類正確率；在Iris數(shù)據(jù)集上表現(xiàn)尤為明顯，聚類最高正確率達到97%，平均準(zhǔn)確率比K-mediods提高20%。相比Iris，文中算法在Wine和 Seeds數(shù)據(jù)集上的平均準(zhǔn)確率相對較低，但其平均正確率和平均迭代次數(shù)仍然優(yōu)于其他幾種算法，同時實驗數(shù)據(jù)也表明基于LGTS-FOA的K-mediods算法同樣適用于高維數(shù)據(jù)集的聚類研究?？梢?，文中算法在聚類準(zhǔn)確率、效率以及穩(wěn)定性等方面有明顯的改進。

綜上所述，對不同的數(shù)據(jù)集，在相同的實驗條件下，相比其他幾種算法，文中將改進的果蠅算法和 K-mediods相結(jié)合，改善了傳統(tǒng)K-mediods算法易陷入局部最優(yōu)的缺點，緩解了其對初始值的敏感，在聚類準(zhǔn)確度和效率上均有所提高，對于高維數(shù)據(jù)集同樣具有較好的適應(yīng)性。

8 結(jié)束語

提出一種基于改進果蠅優(yōu)化算法的K-mediods聚類算法，將融合了混沌映射與禁忌搜索思想的果蠅優(yōu)化算法與K-mediods算法相結(jié)合，使用類內(nèi)距離的倒數(shù)作為適應(yīng)度函數(shù)，在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上進行實驗，結(jié)果表明文中算法既能保證聚類準(zhǔn)確度又能有效提高效率，且對于高維數(shù)據(jù)集具有較好的適應(yīng)性。