鄧青,朱曉軍,楊寧

基于維度權(quán)重和遺傳因子的螢火蟲算法在聚類分析中的應(yīng)用

鄧青1,朱曉軍2,楊寧3

1. 山西輕工職業(yè)技術(shù)學(xué)院信息工程系, 山西 太原 030013 2. 太原理工大學(xué)信息與計算機學(xué)院, 山西 太原 030600 3. 山西云時代技術(shù)有限公司, 山西 太原 030600

針對傳統(tǒng)聚類算法對初始值敏感，易陷入局部最優(yōu)的問題，本文提出一種基于維度權(quán)重和遺傳因子的螢火蟲算法（AWG-FA)。該算法引入遺傳算法的交叉、變異思想，并通過計算維度權(quán)重，將群體中具有優(yōu)良維度的個體遺傳到下一代，保留種群的潛在最優(yōu)解，并對余下個體進行自適應(yīng)變異，提高了種群的多樣性。在UCI數(shù)據(jù)集上進行仿真實驗，結(jié)果表明該算法具有更好的聚類性能和魯棒性。

螢火蟲算法; 聚類分析

聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一個重要組成部分，它是根據(jù)數(shù)據(jù)之間的相關(guān)性，按照特定的準(zhǔn)則，將物理或抽象的對象集合分成若干類的過程，使得相同類內(nèi)的元素相似性較大，而不同類元素之間差異性較大[1]。對于研究對象特征數(shù)據(jù)的內(nèi)在關(guān)系，是非常有效的。許多聚類算法，如經(jīng)典的均值，雖然算法應(yīng)用較廣，但存在對初始值敏感、參數(shù)設(shè)置的問題，而且在算法迭代的后期往往無法獲得最優(yōu)解。智能算法在解決全局最優(yōu)解問題上有著獨特的優(yōu)勢，許多學(xué)者把智能算法與聚類算法進行融合，文獻[2]提出一種自適應(yīng)布谷鳥搜索的-均值聚類算法，文獻[3]提出一種基于模糊C-均值的改進人工蜂群聚類算法。文獻[4]和[5]將蟻群算法同聚類分析算法進行結(jié)合。文獻[6]將粒子群和模擬退火算法的思想應(yīng)用到聚類算法中，克服了初始化的敏感性，提高了聚類精度。

2008年英國學(xué)者模擬自然界螢火蟲的發(fā)光行為，提出一種啟發(fā)式智能優(yōu)化算法——螢火蟲算法，簡稱FA[1]。該算法具有良好的尋優(yōu)和搜索性能，已經(jīng)成功應(yīng)用于多目標(biāo)優(yōu)化[7]、調(diào)度問題[8]、圖像處理[9]及路徑規(guī)劃[10]等領(lǐng)域。但該算法和其他智能算法一樣，也容易陷入局部極值點導(dǎo)致解的精度不高。本文在螢火蟲算法中引入遺傳算法的交叉變異，根據(jù)維度權(quán)重選擇性保留較優(yōu)個體，同時變異增加了種群的多樣性。通過對多個UCI數(shù)據(jù)集進行仿真實驗對比，結(jié)果證明該算法聚類精度高，且不易陷入局部最優(yōu)。

1 螢火蟲算法

螢火蟲算法（Firefly Algorithm，簡稱FA）是模擬螢火蟲表現(xiàn)出的社會行為而設(shè)計的生物進化算法。其原理是利用螢火蟲的發(fā)光特性，在指定區(qū)域內(nèi)搜索其他個體并向亮度較大的個體移動，從而實現(xiàn)位置的尋優(yōu)[9]。螢火蟲根據(jù)亮度和吸引度，這兩個因素決定移動策略。亮度反映了螢火蟲位置的優(yōu)劣（和該位置的目標(biāo)函數(shù)有關(guān)），亮度越大的螢火蟲越能吸引其他螢火蟲向它所處位置移動；吸引度同螢火蟲之間的距離有關(guān)，同時影響螢火蟲所要移動的距離。FA正是通過螢火蟲的位置改變，來不斷更新自身亮度和吸引度，一步步向區(qū)域內(nèi)較優(yōu)的位置移動，以此來實現(xiàn)目標(biāo)優(yōu)化。

一個處于位置的螢火蟲，其亮度就是該位置的目標(biāo)函數(shù)，的位置越好，它的亮度就越大。吸引度大小和亮度大小成正比，與二者之間距離成反比，同時還和介質(zhì)的吸收因子有關(guān)。螢火蟲算法的相關(guān)定義如下：

定義1 螢火蟲相對亮度：一個螢火蟲對相距其處的亮度()，可以用公式（1）表示：

其中，0表示螢火蟲的最大亮度；d表示螢火蟲和在空間上的距離；表示介質(zhì)對熒光的吸收因子。

定義2 螢火蟲的吸引度，0表示螢火蟲的最大吸引度。用公式（2）表示：

定義3 螢火蟲被螢火蟲吸引的移動公式（3）為：

、為螢火蟲和在進行第次迭代前的空間位置；為移動步長因子，且?[0,1]；rand是取值在[0,1]上的隨機數(shù)，可以影響螢火蟲下一時刻位置的變化。螢火蟲算法作為智能算法之一，擁有較好的尋優(yōu)性能，但在多峰值尋優(yōu)中，因步長設(shè)置不合理，往往會陷入局部最優(yōu)，即便能跳出局部最優(yōu)卻也可能跳過精確解導(dǎo)致算法精度降低。

2 聚類問題

其中X表示第個樣本，c表示第個聚類中心，∥X-c∥表示X和聚類中心c的距離。目標(biāo)函數(shù)值越小，表明類內(nèi)個體具有越高的相似度，聚類效果越好。

3 基于維度權(quán)重和遺傳因子的螢火蟲算法（AWG-FA）

3.1 螢火蟲編碼方式

螢火蟲算法應(yīng)用于聚類問題，可以這樣抽象：用空間中一只螢火蟲代表解決問題的一組解，對應(yīng)就是一組聚類中心。假設(shè)為聚類個數(shù)，樣本維度為，第只螢火蟲的位置可以編碼為X=[c1,c2,…,c]，c表示第類樣本的中心，每類樣本中心都是一個維向量。

3.2 算法原理及關(guān)鍵操作

在螢火蟲算法中，每個螢火蟲個體都是一個維向量，它們根據(jù)自身的亮度和吸引度，按照一定的規(guī)則向最優(yōu)解的位置和方向移動，尋找最優(yōu)解。某只螢火蟲在某次迭代中某一維找到了最優(yōu)值，而該位置其他維的值可能不是最優(yōu)，受目標(biāo)函數(shù)影響，這一維的最優(yōu)值也將被舍去。受遺傳算法[13]原理的啟發(fā)，對每次螢火蟲算法尋優(yōu)中獲得的較優(yōu)解和較差解進行交叉、變異、選擇操作。有利于保留較優(yōu)個體，同時可以擴大解的搜索空間，獲取全局最優(yōu)解或近似最優(yōu)解。

3.2.1 改進的交叉方式交叉互換過程可以產(chǎn)生不同于父類的個體，提高種群的多樣性。當(dāng)交叉率比較高時，個體更新快，可達到較大的解空間，但會破壞已有的潛在最優(yōu)解。當(dāng)交叉率比較低時，搜索空間較小，很容易陷入局部最優(yōu)。為了克服這些弊端，本文提出利用維度權(quán)重來決定交叉率的方法。維度權(quán)重的計算公式如(5)所示：

W表示某個體第維的權(quán)重。維度權(quán)重標(biāo)識某一維對目標(biāo)函數(shù)的貢獻程度，值越大，這一維成為最優(yōu)解的概率越大。為了將這些潛在的較優(yōu)維度的值繼承下來，同時達到更大的解空間，將維度權(quán)重低于平均值的個體對應(yīng)位置進行交叉操作。

3.2.2 自適應(yīng)的變異操作為提高種群多樣性，對當(dāng)前種群中余下的個體進行變異操作。為了克服變異的盲目性，本文采用文獻[13]的變異策略：若當(dāng)前個體的適應(yīng)度大于群體平均適應(yīng)度，則以小概率變異，反之，以較大概率變異。變異概率設(shè)定在[0.001，0.1]。

最后對所有個體采用精英策略進行選擇，淘汰一定數(shù)目的個體，控制種群的過度膨脹，完成種群的更新。

圖1 AWG-FA算法流程圖

3.3 算法流程 見圖1。

4 結(jié)果與分析

本實驗選取機器學(xué)習(xí)庫UCI中常用三個數(shù)據(jù)集Iris、Glass、Wine，分別進行對比實驗。這三組數(shù)據(jù)集描述如表1所示。

表1 三組數(shù)據(jù)集描述

4.1 實驗環(huán)境及參數(shù)設(shè)置

4.1.1 實驗環(huán)境及參數(shù)設(shè)置算法通過Matlab R2017a編程實現(xiàn)，實驗機器配置為：處理器：intel core i7-5500U，主頻：2.4GHz，內(nèi)存：8G，操作系統(tǒng)Windows764位。

設(shè)置三組數(shù)據(jù)集的聚類個數(shù)分別為3，3，6。

設(shè)置螢火蟲的步長因子=0.5，最大吸引度0=1，最小吸引度min=0.18，介質(zhì)吸收因子=1，變異概率=0.1，算法終止條件為最大迭代次數(shù)100次。

4.1.2 實驗設(shè)計分別采用-means、FA算法和AWG-FA算法對三組實驗數(shù)據(jù)集分別進行50次獨立實驗，求得多次實驗中的最優(yōu)值、最差值和平均值，以及平均運行時間，記錄在表2中，進行對比。圖2到圖4表示三種數(shù)據(jù)集下，幾種算法在收斂效果方面的對照。

4.2 實驗結(jié)果

表2為不同算法的聚類性能比較。從表2的數(shù)據(jù)統(tǒng)計結(jié)果可以看出，AWG-FA算法在三組測試數(shù)據(jù)集中，整體來看目標(biāo)函數(shù)值均低于其他算法，說明聚類效果更好一些。在算法的運行時間上，AWG-FA算法比其他的兩種算法運行時間稍長，主要原因在于交叉、變異過程耗時方面。但交叉、變異操作使得AWG-FA在全局最優(yōu)解的搜索過程中表現(xiàn)的更好，特別是算法后期收斂速度加快，能找到的解更好。多次實驗發(fā)現(xiàn)，AWG-FA聚類后得到的目標(biāo)函數(shù)最優(yōu)值、最差值、平均值幾乎都是三種算法中最小的，說明AWG-FA的聚類效果三者中最好，聚類的穩(wěn)定性高。

表2 三種數(shù)據(jù)集上不同算法聚類性能對比

圖2到圖4顯示三種算法分別在三個數(shù)據(jù)集上的收斂效果，可以看出-means的收斂速度最快，但是尋優(yōu)能力最差，很快就陷入局部最優(yōu)解；FA的收斂速度和AWG-FA相近，得到的最優(yōu)值介于-means和AWG-FA之間；AWG-FA的收斂速度稍慢，但是得到的最優(yōu)值最好。從收斂效果上，再次驗證AWG-FA算法跳出局部最優(yōu)解，逼近全局最優(yōu)解的收斂過程。AWG-FA相比較其他算法來說，在合理的迭代次數(shù)下能夠找到較好的目標(biāo)函數(shù)值。

圖2 Iris數(shù)據(jù)集的收斂對比

圖3 Wine數(shù)據(jù)集的收斂對比

圖4 Glass數(shù)據(jù)集的收斂對比

5 結(jié)論

本文提出一種新穎的螢火蟲算法，對基本的螢火蟲算法進行了如下改進：（1）計算維度權(quán)重并保留優(yōu)勢屬性的個體；（2）對位置不好的個體引入遺傳算法中的雜交、變異算子，增強種群多樣性。將改進的螢火蟲算法（AWG-FA）同經(jīng)典的-means算法、FA在UCI數(shù)據(jù)上進行聚類，并在聚類準(zhǔn)確性、收斂速度及穩(wěn)定性方面作出比較，實驗結(jié)果證明改進算法的尋優(yōu)能力遠優(yōu)于其他兩種算法，穩(wěn)定性方面更好。

[1] 莫愿斌,馬彥追,鄭巧燕.一種協(xié)作的螢火蟲算法在聚類問題上的應(yīng)用[J].化工自動化及儀表,2014,41(3):238-242

[2] 楊輝華,王克.基于自適應(yīng)布谷鳥搜索算法的-means聚類算法及其應(yīng)用[J].計算機應(yīng)用,2016,36(8):2066-2070

[3] 何嘉婧,王晉東,于智勇.基于模糊C-均值的改進人工蜂群聚類算法[J].計算機應(yīng)用研究,2015,33(5):1342-1345

[4] 鮑義東,周改云,趙偉艇.自適應(yīng)蟻群和模糊聚類的SAR圖像分割[J].測繪科學(xué),2016,41(8):121-124

[5] 李振,賈瑞玉.一種改進的-means蟻群聚類算法[J].計算機技術(shù)與發(fā)展,2015,25(12):34-37

[6] 蔣君,徐蔚鴻,潘楚.基于粒計算和模擬退火的-medoids聚類算法[J].計算機仿真,2015,32(12):214-217

[7] 袁際軍.基于多目標(biāo)螢火蟲算法的可調(diào)節(jié)產(chǎn)品族優(yōu)化設(shè)計[J].計算機集成制造系統(tǒng),2012,18(8):1801-1809

[8] 郭麗萍,李向濤,谷文祥,等.改進的螢火蟲算法求解阻塞流水線調(diào)度問題[J].智能系統(tǒng)學(xué)報,2013,8(1):33-38

[9] 周晨航,田力威,趙宏偉.基于改進螢火蟲算法的二維Otsu圖像分割法[J].沈陽大學(xué)學(xué)報:自然科學(xué)版,2016,28(1):45-50

[10] 徐曉光,胡楠,徐禹翔,等.改進螢火蟲算法在路徑規(guī)劃中的應(yīng)用[J].電子測量與儀器學(xué)報,2016,30(11):1735-1742

[11] 程美英,倪志偉,朱旭輝.螢火蟲優(yōu)化算法理論研究綜述[J].計算機科學(xué),2015,42(4):19-24

[12] 王琦,樸燕.基于改進遺傳算法的深度圖像獲取技術(shù)[J].激光與光電子學(xué)進展,2018,55(2):170-176

[13] 陳闖,Ryad Chellali,邢尹.改進遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的語音情感識別[J].計算機應(yīng)用研究,2019(2):1-5

Application of Firefly Algorithm Based on Attribute Weights and Genetic Factors in Clustering Analysis

DENG Qing1, ZHU Xiao-jun2, YANG Ning3

1.030013,2.030600,3.030600,

Aiming at the problem that the traditional clustering algorithm is sensitive to the initial value and easily falls into the local optimum, a firefly algorithm (AWG-FA) based on attribute weights and genetic factors is proposed. This algorithm introduces the crossover and mutation ideas of genetic algorithm, and calculates the attribute weights, then it inherits the individuals with excellent attributes from the population to the next generation, and mutates the poor individuals, which improves the diversity of the population. Simulation experiments on UCI datasets show that the algorithm has better clustering performance and robustness.

Firefly algorithm; cluster analysis

TP301.6

A

1000-2324(2019)05-0889-04

10.3969/j.issn.1000-2324.2019.05.034

2018-04-22

2018-05-26

基于新型素數(shù)篩法的素性檢測和素數(shù)生成機制研究(201701D11100202)

鄧青(1983-),女,碩士,主要從事網(wǎng)絡(luò)技術(shù)、大數(shù)據(jù)方向研究. E-mail:yndengqing@126.com