王全民，楊 晶，張帥帥

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

0 引 言

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

針對(duì)K-mediods算法易陷入局部最優(yōu)的缺點(diǎn)，提出了一種基于改進(jìn)果蠅優(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é)合，對(duì)每次聚類迭代中的簇中心進(jìn)行尋優(yōu)，以提高K-mediods算法的全局搜索能力和聚類精度。

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

混沌映射的基本思想是：將優(yōu)化變量(一個(gè)在[0，1]區(qū)間波動(dòng)的變量)通過(guò)混沌映射規(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時(shí)，系統(tǒng)出現(xiàn)混沌狀態(tài)，即不重復(fù)地隨機(jī)訪問(wèn)系統(tǒng)解空間。

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

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

i=1,2,…,N

(2)

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

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

(3)

(4)

2 禁忌搜索算法

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

TS算法步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

Xi=X_axis+Random Value

(5)

Yi=Y_axis+Random Value

(6)

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

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

Disti=sqrt(Xi2+Yi2)

(7)

Si=1/Disti

(8)

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

Smelli=Function(Si)

(9)

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

[bestSmell bestIndex]=max(Smell)

(10)

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

(11)

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

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

混沌映射思想保證在解空間范圍不重復(fù)地訪問(wèn)所有狀態(tài)，因此利用這一系統(tǒng)構(gòu)造果蠅群體初始位置可以很好地使果蠅群體較為均勻地分布在解空間。而禁忌搜索思想對(duì)于初值有很高的要求，因此考慮在FOA算法的后期引入該算法。將后期收斂解作為TS算法的初始解，采用果蠅群體的適應(yīng)度方差σ2來(lái)判斷后期收斂情況[10]，當(dāng)算法進(jìn)入后期局部收斂狀態(tài)時(shí)，利用禁忌搜索算法跳出局部最優(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<δ，說(shuō)明算法已進(jìn)入后期收斂狀態(tài)，則執(zhí)行禁忌搜索算法的步驟2～6。否則執(zhí)行步驟6。

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

4.2 有效性測(cè)試

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

(1)Sphere函數(shù)：

(2)Rosenbrock函數(shù)：

(3)Griewank函數(shù)：

(4)Rastrigin函數(shù)：

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

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

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

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

5 K-mediods聚類算法

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

(1)隨機(jī)選取k個(gè)樣本作為初始聚類中心點(diǎn)集。

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

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

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

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

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

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

(14)

其中，zij表示第i個(gè)蜜蜂所表示的第j個(gè)聚類Cj的中心點(diǎn)；p表示類Cj中的非聚類中心點(diǎn)。

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

fiti=1/Di

(15)

6.2 新聚類中心

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

(16)

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

6.3 算法步驟

6.3.1 果蠅編碼

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

6.3.2 具體步驟

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

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

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

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

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

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

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

7 實(shí)驗(yàn)結(jié)果與分析

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

7.1 人工數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

8 結(jié)束語(yǔ)

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