結合人工蜂群與K-means聚類的特征選擇

孫 林，劉夢含，薛占熬

1.天津科技大學 人工智能學院，天津 300457

2.河南師范大學 計算機與信息工程學院，河南 新鄉 453007

近年來，高維數據增大了計算機的存儲壓力，而且存在諸多不相關及冗余數據[1]。特征選擇是數據挖掘過程中預處理的一個重要步驟，其目標是從原始數據集中找到最大相關最小冗余的特征，實現降維。根據是否使用類標信息，特征選擇算法分為有監督和無監督[2]。傳統的有監督特征選擇算法通過不同的判斷準則衡量特征之間的相關度和冗余度，進而去除不相關和冗余特征。其對無標簽數據不適用。無監督特征選擇算法不需要事先知道類標，因此進行無監督特征選擇更具普適性。

聚類是數據挖掘中重要的無監督分類方法，其中K-means 聚類具有實現形式較簡單、線性計算復雜度低等優點[3]。由于其優勢而被廣泛應用于工業、醫學、軍事等領域，但也存在缺點：對初始聚類中心選擇敏感、易陷入局部最優等。Redmond 等[4]將估算出密度最大的樣本作為初始中心，實現優化K-means聚類，但其易陷入局部最優解的問題未得到解決。隋心怡等[5]將樣本分布空間分割為大小相同的子空間，統計子空間中的樣本密度優化初始聚類中心，但該算法的聚類結果受參數影響較大。邵倫等[6]將樣本集映射到虛擬的多維網格空間結構中，從中選擇包含樣本數最多且距離較遠的子網格作為初始聚類中心網格，解決容易陷入局部最優的問題，但該算法結果依賴于單一的相似性度量。廖紀勇等[7]通過定義均值相異性和總體相異性準則確定初始聚類中心，該算法改善了離群點對聚類結果的影響，但未解決易陷入局部最優的問題。因此，受上述文獻啟發，引入群智能優化算法改進K-means 聚類算法，彌補初始聚類中心的選取敏感的缺陷，并改善其全局搜索能力。

近年來，群智能優化算法由于其操作簡單、收斂速度快、全局收斂性好等優勢[8-11]而被眾多學者運用到聚類中[12]。它能解決K-means 算法對初始聚類中心過度依賴以及其易陷入局部最優解的問題。2005年，Karaboga[13]提出人工蜂群（artificial bee colony，ABC）算法，模擬蜜蜂采蜜的群體智能優化。其具有原理簡單、控制參數少、魯棒性強和全局搜索能力強等優勢[14]。一些研究[15]結果表明，ABC算法在求解連續優化問題時性能優于蟻群優化（ant colony optimization，ACO）[16]和粒子群優化（particle swarm optimization，PSO）[17]。近年來，一些學者利用ABC 的優點與K-means 聚類相結合改進算法性能。Janani 等[18]設計了一種結合ABC 和平分K-means 聚類的混合算法，但該方法在計算距離時仍采用傳統的歐氏距離未能有效提高距離計算的精確性。Jin等[19]在ABC中引入模擬退火準則，提高了算法的收斂速度，但該方法未能有效提高局部搜索能力。曹永春等[20]通過調整反向學習的初始化策略和鄰域搜索范圍改善ABC，進而提高K-means聚類算法的穩定性，但該算法中的參數需要根據經驗選取。因此，受上述文獻啟發，構造新的適應度函數，對引領蜂和跟隨蜂的食物源搜索范圍進行動態調整，改進ABC算法，以滿足不同進化時期蜂群對全局尋優能力和局部尋優能力的不同要求，加快收斂速度；同時考慮兩個空間向量之間的累積差異和對應向量之間的相似性，設計新的歐氏距離。

對特征進行聚類有助于發現特征之間的內在聯系，而且形成的特征簇通常對應一些潛在的相關特征[21]。因而，眾多學者使用聚類進行特征選擇。Du等[22]結合ABC 與K-means 算法進行特征子集選擇，提高了算法的分類精度，但該算法所選特征不能保證最小冗余。Moslehi 等[23]利用K-means 聚類算法選擇數據集中有效特征并去除不相關的特征，但該方法在進行特征選擇時未考慮特征與樣本之間的關系。Tang等[24]利用基于余弦距離的K-means聚類對特征進行聚類，選擇最優特征子集，但該算法的參數需要人工設置。胡敏杰等[25]利用譜聚類將特征進行分簇，使用鄰域互信息從每一特征簇中選擇特征子集，但該方法僅在低維數據集上進行了分類能力的測試。因此，受上述文獻的啟發，提出了特征重要度衡量特征，以選擇到最優特征子集。

為此，借助改進的ABC 和K-means 聚類的優勢，本文提出結合改進的ABC 與K-means 聚類的特征選擇算法。其主要貢獻如下：

（1）為了衡量蜜源質量和選擇初始聚類中心，定義簇內聚集度和簇間離散度，構造了蜜源位置的適應度函數，引導蜂群向高質量蜜源全局搜索，把蜂群每次迭代得到的最優蜜源位置作為K-means 聚類的初始聚類中心，并在此基礎上進行交替聚類，使相似性強的點聚在同一類簇中。

（2）為了加快ABC 的收斂速度，并且解決蜂群在進行鄰域搜索時，位置更新在相對固定范圍內沒有具體的搜索范圍和方向，通過對蜂群鄰域搜索范圍的動態調整，構造了新的蜜源位置更新表達式，使之更符合蜂群在蜜源搜索的實際情況。

（3）通過考慮兩個空間向量之間的累積差異以及對應向量之間的相似性，設計了新的歐氏距離；定義了特征區分度與特征代表性，并以二者之積度量特征重要性，選擇特征重要度大的特征構造最優特征子集。

1 相關基礎知識

1.1 人工蜂群算法

ABC 算法主要由4 個要素組成：蜜源、引領蜂、跟隨蜂和偵察蜂[12]。并且具有3 種基本的行為模式：搜索蜜源、招募蜜蜂和放棄蜜源[14]。其算法的主要步驟可以參照文獻[15]，主要包括4 個階段：

（1）初始化蜂群階段

設有n個蜜源的初始種群為X={X1,X2,…,Xn}，每個蜜源Xi={Xi1,Xi2,…,Xid}是一個d維向量，蜜蜂總的循環搜索次數為MCN，每個蜜源可被重復開采的次數為limit。隨機產生n個解，并計算相對應解的適應度值，將適應度由大到小的順序進行排列，其中前一半作為引領蜂，后一半作為跟隨蜂。其中蜜源Xi隨機產生的表達式為：

（2）引領蜂階段

在引領蜂階段，引領蜂在當前所在位置進行鄰域搜索，產生新的位置作為候選蜜源，并計算其適應度。引領蜂的位置搜索表達式為：

其中，表示引領蜂進行鄰域搜索產生的新位置，新蜜源Vi=(Vi1,Vi2,…,Vid)，p∈{1,2,…,n}，j∈{1,2,…,d}，p和j是從各自相應的范圍內隨機選取的兩個數，是在區間[-1,1]之間控制鄰域搜索范圍而進行隨機選取的數，同時決定擾動的幅度。通過式（2），引領蜂得到新蜜源，再利用貪婪原則選擇蜜源。其貪婪原則是：如果搜索到新蜜源Vi的適應度高于原蜜源Xi，則Vi替換Xi；反之，蜜源Xi不變。

（3）跟隨蜂階段

在引領蜂完成鄰域搜索之后，會在舞蹈區分享蜜源信息。跟隨蜂根據其分享信息，采用輪盤賭選擇策略從引領蜂搜索的蜜源中選擇跟隨蜜源，以保證適應度越高的蜜源被開采的幾率更大。在開采的過程中，跟隨蜂與引領蜂一樣通過式（2）尋找新的蜜源，留下適應度更高的蜜源。蜜源被選擇的概率為：

（4）偵察蜂階段

如果蜜源經過多次迭代后其質量沒有進行更新，并且迭代次數達到規定上限，則表明該蜜源陷入局部最優解，將拋棄蜜源。與此同時，與之對應的引領蜂轉換為偵察蜂，根據式（1）產生新蜜源代替該蜜源。當完成全部迭代后，適應度值最大的蜜源就是問題的最優解，算法結束。

1.2 K-means聚類算法

K-means 聚類是一種經典的基于劃分的聚類方法[7]。其主要思想是：在給定的數據集中，首先隨機選擇K個初始聚類中心，利用歐氏距離計算各個樣本之間的距離，根據距離最近原則將樣本分為K個簇；然后求出每一簇的平均位置，重新分配聚類中心，當迭代達到規定次數或者聚類中心不再發生變化，則聚類結束并輸出結果。其詳細步驟可以參考文獻[19]。傳統的K-means 聚類算法的初始聚類中心隨機選取，并且該算法是通過迭代獲得最優解，初始聚類中心的不同導致聚類結果也不相同，會造成聚類結果的不穩定。因此，如何選擇恰當的初始聚類中心是改進K-means 聚類算法的一個重要研究方向[20]。

假設數據集D∈Rn×d，其中n表示樣本數，d表示特征維度，{f1,f2,…,fi,…,fd} 表示d維特征向量，{x1,x2,…,xj,…,xn}表示n個樣本的集合，則該數據集也可以表示為D={x1,x2,…,xi,…,xn}，且xi∈Rd，xi=(xi1,xi2,…,xid)。若將D劃分為多個類C={C1,C2,…,CK}，K為D劃分的簇數且，則基于劃分的聚類分析目標函數為：

2 提出的特征選擇方法

2.1 適應度函數

在ABC 算法中，適應度函數直接決定蜂群進化的行為、迭代次數和蜜源的質量，同時也引導蜂群進化的方向[14]。當適應度函數不相同時，得到的蜜源質量也不相同。一般情況下，適應度函數值越大則說明蜜源含蜜量越多，也代表蜜源所處位置越好，越能吸引蜜蜂。

文獻[15]指出：傳統的適應度函數僅僅考慮簇內各個樣本的特性，未考慮簇間樣本的特性，則不能全面反映數據集中各個樣本的特征。由此，在聚類簇中，為了使同一簇中樣本的相似度高而不同簇中樣本的相似度低，下面通過簇內聚集度和簇間離散度函數構建新的適應度函數。

定義1（簇內聚集度函數）設數據集D={x1,x2,…,xn}，K個聚類中心CK={m1,m2,…,mK}，則簇內聚集度函數為：

其中，xi表示任意樣本，mK表示CK的聚類中心。

定義2（簇間離散度函數）設數據集D={x1,x2,…,xn}，K個聚類中心CK={m1,m2,…,mK}，則簇間離散度函數為：

其中，mi和mj表示所有簇中任意兩個聚類中心。由此可知，簇間離散度越大則表示不同簇之間的距離越大，相似度越低，聚類效果越好，反之亦反。

由文獻[15]可知：簇內聚集度越大表示同一簇中的樣本相似度越低，反之亦反。另外，簇內聚集度函數的最優解是簇內所有樣本到其所屬簇總聚類中心的距離之和最小。由此，為了同時考慮簇內特性和簇間特性，下面設計新的適應度函數。

定義3（適應度函數）設數據集D={x1,x2,…,xn}，K個聚類中心CK={m1,m2,…,mK}，則新的適應度函數表示為：

其中，J(CK)表示簇內聚集度函數，D(CK)表示簇間離散度函數。由式（7）可知，簇間離散度越大，簇內離散度越小，適應度數越大，聚類效果越好。

定義4（基于新的適應度函數的概率表達式）設數據集D={x1,x2,…,xn}，則蜜源被選擇的新的概率表達式為：

其中，fiti表示第i個蜜源的適應度，i=1,2,…,n。

2.2 鄰域搜索范圍

在傳統的ABC 中，依據式（2）更新引領蜂和跟隨蜂的位置，使它們在一個相對固定范圍內進行蜜源隨機搜索，沒有具體范圍和方向，這樣就造成了它們進行位置搜索時具有茫然性。在實際搜索中，在不同時期蜜蜂進行蜜源搜索的范圍和方向都不盡相同，由此需要改進原始的蜜源搜索方式，以確保蜜蜂在蜜源搜索的過程中更符合實際情況。在初始階段，ABC 希望引領蜂的搜索范圍相對較大，能很快地找到最優解的大致方位；隨著迭代次數的不斷增加，ABC 進入最后階段，由于此時搜索范圍已經靠近最優解，于是希望后期蜜蜂能夠在最優解附近搜索，從而更準確地搜索到最優解位置。綜上所述，引領蜂和跟隨蜂在蜜源搜索初期，其范圍應盡量大，在搜索后期，其范圍應減小。

定義5（鄰域搜索表達式）設數據集D={x1,x2,…,xn}，則鄰域搜索表達式為：

其中，M表示非線性遞減的鄰域范圍調整系數，M=a-t，a＞1，根據文獻[26]對鄰域范圍調整系數策略進行測試，獲取最優參數值為1.1；表示引領蜂搜索后隨機產生的鄰域蜜源的位置；表示當前蜜源的位置；表示在[-1,1]之間的隨機數，同時決定擾動的幅度；t表示當前迭代次數。

由定義5 可知，在改進ABC 的迭代初期，t較小則M較大，蜜蜂在較大鄰域范圍內進行搜索，全局搜索能力比較強；在迭代后期t變大則M變小，蜜蜂在較小鄰域范圍內進行搜索，局部搜索能力較優。因此，式（9）滿足了蜜蜂在不同進化時期對其尋優能力的要求，增強了跳出局部最優值的能力，加快了算法的收斂速度?？紤]到隨著迭代次數增加而權值逐漸減小的情況，文獻[27]和文獻[20]中也對鄰域搜索表達式中的權值進行了改進，其權值依賴于經驗值，但是式（9）中的權值M是通過實驗測試獲取。因而，與文獻[27]和文獻[20]中的權值相比，上述式（9）中的權值M更加具有普適性和合理性。

2.3 加權歐氏距離

傳統的K-means 聚類樣本之間的相似程度通常是根據歐氏距離進行衡量的。在一般情況下，樣本之間的歐氏距離越小則表示樣本相似度越大[3]。但是，這種劃分準則僅僅考慮兩個樣本之間的累積差異，具有一定的局限性。為此，在計算樣本之間的距離時，既要考慮兩個向量之間的累積差異，還要充分考慮對應樣本之間的相似性。于是，下面設計了基于特征和樣本相似性的歐氏距離計算表達式。

定義6（基于特征的加權歐氏距離）設數據集D={x1,x2,…,xn}，樣本xi=(xi1,xi2,…,xid)，xj=(xj1,xj2,…,xjd)，則依據特征影響程度不同的加權歐氏距離表達式為：

定義7（基于樣本相似性的加權歐氏距離）設數據集D={x1,x2,…,xn}，樣本xi=(xi1,xi2,…,xid)，xj=(xj1,xj2,…,xjd)，則基于樣本相似性的加權歐氏距離表達式為：

由定義7 可知，式（11）表示數據集中各樣本之間的特性，對應樣本越相近，則其相似度的貢獻越大，在最終相似度結果中占有更大的比重。但是，式（10）和式（11）這兩個加權歐氏距離僅從數據集中樣本或特征單方面進行考慮，于是結合式（10）和式（11）構建混合的加權歐氏距離公式，使其能更全面地反映出數據集的總體特性。

定義8（基于特征和樣本相似性的加權歐氏距離）設數據集D={x1,x2,…,xn}，樣本xi=(xi1,xi2,…,xid)，xj=(xj1,xj2,…,xjd)，對任意樣本xi和xj，則依據各分量影響程度不同和樣本的相似性加權定義樣本xi和xj之間的加權歐氏距離表達式為：

2.4 特征重要度

定義9（特征區分度）設數據集D={x1,x2,…,xj,…,xn}，fi∈Rn，則特征區分度表示為：

其中，fji表示樣本xj在特征fi上的取值，i=1,2,…,d，j=1,2,…,n。

文獻[21]指出：Pearson 相關系數可以度量兩變量之間的相關性，其絕對值越小則越不相關。當它們的Pearson 相關系數為0 時，不能判定這兩個變量是獨立的，有可能是非線性相關。但是，當它們的距離相關系數是0，就可以說這兩個變量是獨立的。為解決該問題，采用距離相關系數判斷兩個特征之間的相關性[1]，利用特征與特征之間的距離系數的倒數作為特征代表性，于是該特征代表性越強則表明兩個特征相關性越弱。

為了同時考慮樣本與特征之間的關系以及特征與特征之間的關系，下面構造特征重要度。

定義11（特征重要度）設數據集D={x1,x2,…,xj,…,xn}，fi∈Rn，基于特征區分度與特征代表性之積定義特征fi的重要度scorei為：

其中，disi表示特征區分度，rei表示特征代表性。

由定義11 可知，當特征fi的特征區分度與特征代表性越大時，則特征fi的重要度值越大。文獻[21]指出：重要的特征應該使同類樣本之間的特征值相同或相近，而不同類樣本之間的特征值不同或者差別很大。也就是說，重要度大的特征應該具有較大的區分度和較大的代表性。

2.5 算法描述

結合改進的ABC 與K-means 聚類設計特征選擇算法（feature selection usingK-means clustering with artificial bee colony，FSKCA），其偽代碼描述如算法1所示。主要由3個部分組成：基于改進人工蜂群的優化算法（Improved artificial bee colony algorithm，IABC）的具體過程見步驟1～步驟28；基于改進人工蜂群的K-means 聚類算法（improved artificial bee colony-basedK-means clustering algorithm，IABCK）的具體過程見步驟1～步驟29；最后選擇最優特征子集的具體過程見步驟30～步驟34。

算法1FSKCA 算法

假設n為樣本的個數，d為特征個數，則算法1的計算復雜度分析如下：步驟2～步驟5 初始化蜜源位置和個數的計算復雜度為O(n)；步驟9 根據K-means聚類算法以蜜源為中心進行聚類劃分，計算復雜度為O(ndk)，步驟10 計算適應度函數值的復雜度為O(nk)，則步驟8～步驟15 引領蜂進行鄰域搜索的計算復雜度為O(ndk)×O(Pop)×O(nk)。步驟17～步驟20 跟隨蜂根據輪盤賭原則選擇引領蜂的計算復雜度為O(Pop)×O(nk)。于是，步驟7～步驟28 總的計算復雜度為O(MAX×Pop×n2dk2)；步驟32 計算特征區分度的復雜度為O(n2d)，計算特征代表性的復雜度為O(n2)，計算特征重要度值并根據特征重要度值進行排序的計算復雜度為O(dlbd)，其中最大更新次數MAX、Pop和k為常量。由于MAX、Pop和k均為常量，與n和d存在巨大的數據量差異，且常數可以忽略不記，因而FSKCA 算法總的計算復雜度為O(n2d)。另外，相關的比較算法的計算復雜度分析如下：MCFS（multi-cluster feature selection）[28]算法的計算復雜度為O(n2d+km3+nkm2+dlbd)，其中m表示所選擇特征子集個數，k表示聚類簇數目；LLCFS（local learning based clustering feature selection）[29]算法的計算復雜度為O(n3)；UDFS（unsupervised discriminative feature selection）[30]算法的復雜度為O(d3) ；SPFS（spectral feature selection）[31]算法的復雜度為O(dn2)；EUFSFC（efficient unsupervised feature selection method based on feature clustering）[32]算法的計算復雜度為O(d2)?？傊?，FSKCA 算法的計算復雜度略高于EUFSFC 算法[32]，略低于LLCFS 算法[29]和UDFS 算法[30]，接近于MCFS 算法[28]和SPFS 算法[31]。

為了方便讀者更好地理解FSKCA 算法，以鸞尾花卉數據集Iris 為例來進行解釋。首先，從Iris 數據集中隨機選取50 個樣本作為蜜源，初始化算法最大迭代次數500，蜜源最大迭代次數20，計算Iris 數據集中的各個蜜源的適應度值，并按照從大到小的順序排列，前一半設置為引領蜂，后一半設置為跟隨蜂。在引領蜂階段，搜索最佳蜜源并更新。在跟隨蜂階段，跟隨蜂根據輪盤賭原則選擇引領蜂，選擇完成后對Iris 數據集進行K-means 聚類，更新得到新的聚類中心，用新的聚類中心再更新蜂群。如果引領蜂迭代20 次后位置沒有變化，引領蜂變為偵察蜂，隨機選取蜜源進行更新。重復上述步驟直到達到最大迭代次數500，輸出Iris 數據集完成聚類的3 個簇。其次，計算Iris 數據集中3 個簇各特征的特征區分度與特征代表性。最后，計算特征重要度，選出特征重要度最大的3 個特征作為最優特征子集輸出，則算法結束。

3 實驗結果與分析

3.1 IABC 算法的優化性能分析

本節從文獻[19]中選擇9 種基準測試函數對IABC 算法與PSO 算法[17]、ABC 算法[13]、結合食物源位置更新的ABC 算法（ABC algorithm combined with food source location update，ABCL）[27]、結合鄰域搜索范圍動態調整的ABC 算法（ABC algorithm combined with dynamic adjustment of neighborhood search range，ABCC）[20]、IABC1 算法（結合2.2 節中定義5 鄰域搜索策略的ABC 算法）、IABC2 算法（結合2.1 節中定義3新的適應度函數策略的ABC 算法）進行優化性能測試。其中f1～f5為單峰函數，主要測試算法的尋優精度；f6～f9為多峰函數，具有多個局部最優點，通常檢驗算法的全局搜索性能和避免局部收斂能力。為了保證實驗的公正性，在50 維和100 維上設置最大迭代次數分別為500 和1 000，種群數量為50。為了防止隨機實驗影響算法的評估，每種算法均獨立運行30 次。9 種基準測試函數在2 種不同維度的運行結果如表1 所示，使用最優值(best)、最差值(worst)、平均值(mean)和標準差(std)來評價算法優化性能，其中mean和std越小表明算法的搜索能力和穩定性越好。實驗硬件配置為Windows10 操作系統、16.00 GB RAM 和Intel?1.60 GHz CPU，軟件為MatlabR2016b，實驗結果表中粗體表示最優結果。

從表1 中的50 維測試結果可知，在f1～f6、f9這7個函數上，IABC 的4 個指標值均最優；IABC1 的4 個指標值均優于ABCL 和ABCC；IABC2 的4 個指標值在f4～f6、f9函數上均優于ABC，在f1～f3函數上的std值比ABC 差，但它的best、worst和mean優于ABC。在f7～f8函數上，IABC 在best、worst和mean上明顯最優，在std上略差于IABC1，但優于其余算法；IABC1 在4 個指標值均優于ABCL 和ABCC；IABC2的std值 比ABC 差，但 在best、worst和mean優 于ABC。由100 維上的實驗結果可知，在f3～f5和f7～f9這6 個函數上，IABC 的best、worst、mean和std均最優；IABC1 在f3～f5和f7、f9函數上的4 個指標均優于ABCL 和ABCC，在f8函數上std值略低于ABCC，但best、worst和mean表現最優；IABC2 在這6 個函數上的4 個指標值均優于ABC。在f1函數上，IABC 的stdIABC1 在4 個指標上的運行結果均優于ABCL 和ABCC；IABC2在這4個指標上運行結果均優于ABC。在f2函數上，IABC 的best略低于IABC1，但worst、mean和std均高于其余算法；IABC1在4個指標上的運行結果均優于ABCL和ABCC；IABC2在這4個指標上運行結果均優于ABC。在f6函數上，IABC 的worst略低于IABC1，但best、mean和std高于其余算法；IABC1 在4 個指標上的運行結果均優于ABCL 和ABCC；IABC2 的std略低于ABC，在best、mean和worst上與ABC相同。

為了從消融實驗角度分析算法性能，依據表1中IABC、IABC1 和IABC2 這3 種算法的實驗結果，進一步分析并突出改進算法的優勢。在50 維上，在f1～f6、f9這7 個函數上關于4 個指標的運行結果IABC 均優于IABC1 和IABC2 算法；在f7函數上，IABC 的std略低 于IABC1，但高于IABC2，同時，IABC 的best、worst和mean均高于IABC1 和IABC2；在f8函數上，IABC 的std略低于IABC1 和IABC2，但IABC 的best、worst和mean均高于IABC1與IABC2。在100 維上，f3～f5和f7～f9這6 個函數上關于4 個指標的運行結果，IABC 均優于IABC1 和IABC2 算法；在f1函數上，IABC 的std略低于IABC1，但高于IABC2，同時，IABC 的best、worst和mean均高于IABC1 與IABC2；在f6函數上，IABC 的best略低于IABC1，但高于IABC2，同時，IABC 的worst、mean和std均高于IABC1 與IABC2。從表1 的9 個測試函數實驗結果看出，IABC 在50維的7個函數上表現最佳，在100維的6個函數上表現最佳。相比于IABC1和IABC2，結合IABC1 和IABC2 之后的IABC 的優化性能在各測試函數上均有所提升，特別是在50 維的f1～f6和f9，100 維的f3～f5和f7～f9，IABC 都較IABC1 和IABC2 有所提升，在其他測試函數上，這3 種算法的尋優精度相當。綜上分析可知，IABC 中各策略的改進效果良好，但所有策略組合的性能是最佳的。

從表1 測試結果可知，在選擇的9 個基準測試函數上，IABC 相對于其余6 種算法具備良好的優化性能，充分證明了IABC 的普適性。但是IABC 在這9個函數上的4 個指標上表現不是全優，究其原因是：IABC 一方面通過自適應概率表達式提高了最佳蜜源被選擇的概率，另一方面對蜂群鄰域搜索范圍進行動態調整，提升了IABC 尋優能力。盡管這些策略有效提升了IABC 在處理單峰和多峰函數時的尋優精度和收斂能力，但也會在一定程度上減弱其自身的全局搜索能力?？偟膩碚f，IABC 不僅在單峰函數上具有較好的尋優能力，而且在多峰函數上顯示了更好的全局搜索能力。因而對ABC 的改進是有效可行的。

為了更清楚地說明IABC的收斂性能，以50維函數為代表性來展示上述7種算法的收斂曲線圖（如圖1 所示）。從圖1 可以直觀看出，IABC 在9 個基準函數上優化的收斂速度均領先于其他6 種對比算法?？偟膩碚f，IABC 在50 維9 個基準測試函數上的收斂性能是最優的。綜合表1 和圖1 來看，IABC 在函數優化的問題上表現較優，不僅收斂速度快，而且結果相比其余6 種算法更加優秀。因此，對ABC 的改進是切實有效的。

圖1 7種算法在9個基準函數上的收斂曲線（維度為50）Fig.1 Convergence curves of 7 algorithms on 9 benchmark functions(50 dimensions)

3.2 IABCK算法的聚類分析結果

為了驗證IABCK算法在不同數據集上的聚類分析效果，本節首先在7個合成數據集上對IABCK算法與K均值聚類算法（K-means）[4]、近鄰傳播算法（affinity propagation algorithm，AP）[33]、基于密度的含噪聲空間數據庫聚類發現算法（density-based algorithm for discovering clusters in large spatial databases with noise，DBSCAN）[34]、排序點識別聚類結構算法（ordering points to identify clustering structure algorithm，OPTICS）[35]、基于優化初始聚類中心和輪廓系數的K-means聚類算法（K-means clustering algorithm using optimal initial clustering center and contour coefficient，KCOIC）[36]進行對比分析。這7 種合成數據集（http://cs.uef.fi/sipu/datasets）的具體信息描述可見文獻[36]。參照文獻[36]，選用4 個指標：調整互信息（adjusted mutual information，AMI）、歸一化互信息（normalized mutual information，NMI）、蘭德系數（Rand index，RI）和調整蘭德系數（adjusted Rand index，ARI）。具體實驗結果見表2 所示。為了更直觀地說明這些算法的聚類性能，考慮到版面空間受限，僅在3 個代表性合成數據集上給出K-means、AP、DBSCAN、OPTICS、KCOIC 和IABCK 這6 種算法的聚類效果圖，如圖2至圖4所示，其中不同的顏色代表不同 的簇。

圖2 6種算法在Flame數據集上的聚類效果Fig.2 Clustering effect of 6 algorithms on Flame dataset

表2 6種算法在7個合成數據集上的實驗結果Table 2 Experimental results of 6 algorithms on 7 synthesis datasets

由表2 可以得出：在Zelnik3、Aggregation 和R15這3 個數據集上，IABCK 在這4 個指標上的運行結果均優于其他5種對比算法，分別高出0.011 6～0.419 3、0.021 5～0.309 1、0.007 7～0.211 9 和0.010 3～0.507 4；在Flame數據集上，IABCK 在AMI和ARI指標上達到次優，其原因在于IABCK 對于形狀復雜的簇識別能力相比KCOIC 較弱，但在NMI和RI指標上優于其他5 種算法；在Compound 數據集上，IABCK 在NMI、RI和ARI指標上低于最優的DBSCAN，其原因在于IABCK 在該數據集上未能實現正確的聚類劃分，但在AMI指標上運行效果最佳；在Path-based 數據集上，IABCK 在AMI和ARI指標上略低于KCOIC，在NMI和RI指標上僅低于最佳的DBSCAN，達到了次優，究其原因在于IABCK 在處理一些簇邊界難以分類的樣本時效果并不優異，但優于另外5 種算法；在Jain 數據集上，IABCK 在AMI和ARI指標上次優，究其原因在于IABCK對于簇間密度差別較大的數據集聚類效果次于KCOIC，但在NMI和RI指標上達到最優?？偟膩碚f，在7種合成數據集上，IABCK在AMI、NMI、RI和ARI這4個指標下的表現效果優異。

如圖2的實驗結果所示，對于簇間沒有明確界限的Flame 數據集，K-means、OPTICS 和IABCK 這3種算法均得到了正確的聚類結果，其余3種算法對于形狀復雜的簇識別能力較弱。如圖3所示，對于簇間密度差別較大的Jain 數據集，K-means、OPTICS 和IABCK這3種算法均實現了正確的聚類劃分，而其他3 種算法在對簇間密度差別較大的數據集進行聚類時效果并不優異，究其原因是這3種聚類算法未能有效聚類簇間密度差別較大的數據集。如圖4所示，對于簇間聯系時而緊密時而疏松的R15 數據集，IABCK相比其他5種對比算法聚類效果最優，實現了正確的聚類劃分，這表明IABCK 善于處理簇間時而緊密時而疏松的數據集。

圖3 6種算法在Jain數據集上的聚類效果Fig.3 Clustering effect of 6 algorithms on Jain dataset

圖4 6種算法在R15數據集上的聚類效果Fig.4 Clustering effect of 6 algorithms on R15 dataset

本節第二部分是在10個UCI數據集上將IABCK算法與6 種結合K-means 聚類的群智能優化算法進行實驗比較，主要包括結合人工蜂群與K-means 聚類算法（ABC algorithm[13]combined withK-means[4]，ABC+K-means）、結合粒子群與K-means 聚類（PSO algorithm[17]combined withK-means[4]，PSO+K-means）、PAM（partial around medoids algorithm）[37]算法、自適應折疊混沌優化（adaptive iterative chaos optimization algorithm，GPAM）[38]算 法、CAABC+K-means 算 法（chaotic adaptive ABC algorithm[19]combined withK-means[4]）和結合人工蜂群優化的粗糙K-means 聚類算法（rough ABC algorithm[15]combined withK-means[4]，RABC+K-means）。這10 個UCI 數據集（http://www.ics.uci.edu）的具體信息描述可見文獻[19]。參照文獻[19]，采用3 個評價指標：歸一化互信息（NMI）、準確率（accuracy，ACC）和召回率（recall，R）。具體實驗結果見表3。

表3 7種算法在10個UCI數據集上的實驗結果Table 3 Experimental results of 7 algorithms on 10 UCI datasets

由表3 可以得出：在Iris、Balance-scale、Wine、Musk 和Cancer 這5 個數據集上，IABCK 在3 個評價指標上的結果均優于6種對比算法，分別高出0.000 4～0.227 5、0.001 5～0.163 1 和0～0.490 0；在Glass 數據集上，IABCK 在R指標上的結果低于表現最佳的CAABC+K-means，究其原因在于IABCK 在聚類過程中對于真實情況下兩個樣本在同一個簇中，聚類后兩個樣本不在同一個簇中，但高出另外5 種算法0.010 0～0.223 3，同時該算法在NMI和ACC兩個指標上的運行最優，分別高出其余算法0.022 1～0.182 6和0.017 1～0.130 9；在ECOLI 數據集上，IABCK 在ACC指標上低于表現最佳的CAABC+K-means，原因是CAABC+K-means 在該數據集上的聚類效果優于IABCK，但是在NMI和R指標上結果最優，分別高出其余算法0.011 2～0.082 8 和0.110 0～0.160 0；在Abalone和Skin Seg 數據集上，IABCK 在NMI和ACC指標上不是最優算法，究其原因是IABCK 在這2 個數據集上的聚類數目與真實情況存在差別，但R指標上的運行結果最優，優于其余算法0～0.760 0和0.150 0～0.370 0；在CMC 數據集上，IABCK 在NMI指標上的運行效果較差，究其原因在于IABCK 在該數據集上由聚類結果所得劃分的熵值較小，但在ACC和R這兩個指標上運行效果達到最優，分別高出其余算法0.015 1～0.051 7和0.060 0～0.260 0?？偟膩碚f，IABCK對于文中所選的10 個UCI 數據集在NMI、ACC和R這3 個指標上的運行效果優異。

3.3 FSKCA算法的特征選擇結果

本節是在9 個UCI 數據集上對FSKCA 算法與文獻[32]中 的LSFS、MCFS、LLCFS、UDFS、NDFS、SPFS、EUFSFC 這7 種算法以及文獻[39]中的基于自適應鄰域互信息與譜聚類的特征選擇算法（feature selection algorithm based on adaptive neighborhood mutual information and spectral clustering，FSANS）進行比較。這9 個UCI 數據集（http://www.ics.uci.edu）的具體信息描述可見文獻[32]。采用決策樹（C4.5 decision tree，C4.5-DT）和多層感知器（multi-layer perceptron，MLP）這兩種分類器，通過十折交叉驗證計算特征子集誘導出來的分類精度，具體實驗結果表現如表4所示。

表4 9種特征選擇算法在2種分類器上的分類精度Table 4 Classification accuracy of 9 feature selection algorithms on 2 classifiers

通過表4 的C4.5-DT 分類器的實驗結果可以看出：在WDBC、SPECTF、Sonar、Lung-discrete、Isolet和Leukemia1這6個數據集上，FSKCA的分類精度達到最優，高出其余算法0.000 2～0.215 3；在Multiple features數據集上，FSKCA 的分類精度雖然低于LLCFS 和EUFSFC 這2 種算法，但高于另外6 種算法0.006 2～0.170 9；在Colon 數據集上，FSKCA 算法相比其余7種算法分類精度較差，但在warpAR10P 數據集上，FSKCA 的分類精度略低于MCFS 和EUFSFC 這2 種算法，但高于其他6 種算法0.097 8～0.228 6。FSKCA并未能在全部數據集上實現最優的分類精度，究其原因是：FSKCA 在Multiple features、Colon 和warpAR10P 這3 個數據集上未選擇出具有最小冗余最大相關的最佳特征子集。在MLP 分類器下：在WDBC、Sonar、Lung-discrete、Isolet、Multiple features和Colon這6個數據集上，FSKCA 的分類精度均達到最優，優于其余算法；在SPECTF 數據集上，FSKCA的分類精度雖然比EUFSFC 低了0.005 3，但高于另外7 種算法0.010 0～0.025 6；在warpAR10P 數據集上，FSKCA 的分類精度不如最優的EUFSFC，但比LSFS 高0.070 6；在Leukemia1 數據集上，FSKCA 的分類精度僅比最優的LSFS 低了0.001 8，但優于其余7 種算法0.002 2～0.131 9。FSKCA 并未在全部數據集上關于MLP 分類器上實現最優的分類精度，原因在于：FSKCA 在SPECTF、warpAR10P 和Leukemia1這3 個數據集上未選擇最優特征子集?？偟膩碚f，FSKCA 在C4.5-DT 和MLP 這2 種分類器下的9 個數據集的分類精度方面表現出很大的優勢。

3.4 統計分析

為了評估對比算法的統計性能，采用Friedman檢驗和Nemenyi檢驗[1]進行測試。Friedman統計量表達式為：

其中，k表示算法的個數，N表示數據集的個數，Ri表示k個算法在N個數據集上的平均排名。如果平均距離水平超出臨界距離，則兩種算法性能將有顯著差異。臨界距離表達式為，其中qα表示臨界列表值，α表示Nemenyi檢驗的重要度。

參照文獻[1]，使用CD圖直觀地顯示比較算法之間的差異性，每個算法的性能平均排名沿軸繪制，最好的排名值在軸的左側；當2種算法平均排名在一個誤差之內時，用粗線將它們連接起來；否則認為它們之間具有顯著的差異。依據表4中的分類精度結果，表5給出了9種特征選擇算法在2種分類器下的統計結果，相應的CD圖如圖5 所示。在顯著水平α=0.1時，qα=2.45，CD=2.83，其中k=9且N=9。通過以上實驗可以看出，FSKCA 算法明顯優于其他8 種算法，在統計分析方面表現出更好的優勢，并且表現出較優的泛化性能。

圖5 9種算法在2種分類器下Nemenyi測試結果Fig.5 Nemenyi test results of 9 algorithms under 2 classifiers

表5 9種特征選擇算法在2種分類器下的統計結果Table 5 Statistical results of 9 feature selection algorithms under 2 classifiers

4 結束語

本文提出了一種結合人工蜂群與K-means聚類算法的特征選擇方法。首先，引入權重，改進了食物源的位置更新表達式，增強了人工蜂群的局部尋優能力；設計了同時考慮簇間和簇內性質的適應度函數，以使其計算更加合理。然后，構造了同時考慮樣本之間相似性和特征之間的差異性的混合歐氏距離，解決了K-means 算法在進行距離計算時將不同樣本和不同特征之間的差異同等對待問題。最后，設計特征重要度的表達式，用特征重要度來衡量特征，以選取最優特征子集。在9個基準函數上驗證了IABC 算法的優化性能；在7 個合成數據集和10 個UCI 數據集上驗證了IABCK 算法能有效提高聚類的全局搜索能力和準確率；2 個分類器上9 個UCI 數據集的特征選擇結果驗證了FSKCA算法的有效性。但是，所提算法進行K-means 聚類時聚類數目未實現自適應計算得到，存在一定的偶然性。因此，在今后的研究工作中，在提高聚類精度的情況下實現自適應計算聚類數目，尋求更加高效的聚類效果。