基于維度權重和遺傳因子的螢火蟲算法在聚類分析中的應用

鄧青,朱曉軍,楊寧

基于維度權重和遺傳因子的螢火蟲算法在聚類分析中的應用

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

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

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

螢火蟲算法; 聚類分析

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

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

1 螢火蟲算法

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

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

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

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

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

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

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

2 聚類問題

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

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

3.1 螢火蟲編碼方式

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

3.2 算法原理及關鍵操作

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

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

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

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

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

圖1 AWG-FA算法流程圖

3.3 算法流程 見圖1。

4 結果與分析

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

表1 三組數據集描述

4.1 實驗環境及參數設置

4.1.1 實驗環境及參數設置算法通過Matlab R2017a編程實現，實驗機器配置為：處理器：intel core i7-5500U，主頻：2.4GHz，內存：8G，操作系統Windows764位。

設置三組數據集的聚類個數分別為3，3，6。

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

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

4.2 實驗結果

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

表2 三種數據集上不同算法聚類性能對比

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

圖2 Iris數據集的收斂對比

圖3 Wine數據集的收斂對比

圖4 Glass數據集的收斂對比

5 結論

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

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

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

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

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

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

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

[7] 袁際軍.基于多目標螢火蟲算法的可調節產品族優化設計[J].計算機集成制造系統,2012,18(8):1801-1809

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

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

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

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

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

[13] 陳闖,Ryad Chellali,邢尹.改進遺傳算法優化BP神經網絡的語音情感識別[J].計算機應用研究,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

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

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