一種基于改進果蠅優化的K-mediods聚類算法

王全民，楊 晶，張帥帥

(北京工業大學 信息學部，北京 100124)

0 引 言

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

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

1 基于Logistic映射的混沌技術

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

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

(1)

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

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

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

i=1,2,…,N

(2)

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

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

(3)

(4)

2 禁忌搜索算法

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

TS算法步驟如下：

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

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

(3)尋找鄰域內最優值best(f(x))的對應點x'。

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

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

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

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

3 果蠅優化算法(FOA)

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

果蠅優化算法的一般步驟為：

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

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

Xi=X_axis+Random Value

(5)

Yi=Y_axis+Random Value

(6)

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

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

Disti=sqrt(Xi2+Yi2)

(7)

Si=1/Disti

(8)

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

Smelli=Function(Si)

(9)

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

[bestSmell bestIndex]=max(Smell)

(10)

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

(11)

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

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

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

4.1 LGTS-FOA算法

LGTS-FOA算法步驟如下：

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

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

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

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

(12)

(13)

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

(6)如果當前迭代得出的bestSmell優于Smellbest，保存最佳濃度和最優位置坐標。判斷是否達到最大迭代次數，若是結束算法，否則，轉入步驟3。

4.2 有效性測試

文中采用4個經典標準函數進行有效性測試：

(1)Sphere函數：

(2)Rosenbrock函數：

(3)Griewank函數：

(4)Rastrigin函數：

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

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

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

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

5 K-mediods聚類算法

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

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

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

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

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

6 基于改進果蠅優化算法的K-mediods聚類算法

6.1 適應度函數

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

(14)

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

文中將類內距離的倒數作為適應度值。當類內距離最小時聚類效果最優，此時適應度值最大，表示如下：

fiti=1/Di

(15)

6.2 新聚類中心

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

(16)

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

6.3 算法步驟

6.3.1 果蠅編碼

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

6.3.2 具體步驟

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

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

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

(4)執行LGTS-FOA算法步驟3～6，適應度函數如式15所示。

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

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

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

7 實驗結果與分析

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

7.1 人工數據集實驗

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

圖1 人工數據集分布

圖2 K-mediods聚類結果

圖3 文獻[14]算法的聚類結果

圖4 文獻[15]算法的聚類結果

圖5 文中算法的聚類結果

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

7.2 UCI標準數據集實驗

采用UCI標準數據集中的Iris、Wine和Seeds。各類算法在上述幾種標準數據集中得到的平均正確率以及迭代次數如表2所示。

表2 不同算法對UCI數據集聚類結果的比較

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

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

8 結束語

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