李騰飛， 馮 翔， 虞慧群

（ 1. 華東理工大學(xué)信息科學(xué)與工程學(xué)院，上海 200237；2. 上海智慧能源工程技術(shù)研究中心，上海 200237）

近年來，特征選擇技術(shù)已經(jīng)成為數(shù)據(jù)預(yù)處理特別是高維數(shù)據(jù)預(yù)處理中的一個重要技術(shù)。隨著大數(shù)據(jù)時代的到來和網(wǎng)絡(luò)技術(shù)的發(fā)展[1]，在許多機器學(xué)習(xí)應(yīng)用中收集的特征數(shù)量變得越來越大。由于“維數(shù)詛咒”[2-3]的存在，傳統(tǒng)的機器學(xué)習(xí)方法往往不能很好地處理高維數(shù)據(jù)。值得注意的是，隨著維數(shù)的增加，數(shù)據(jù)空間中可能存在的實例數(shù)量也在極速膨脹，使得可用數(shù)據(jù)變得稀疏, 而這些數(shù)據(jù)的增長通常與有限元的數(shù)量成指數(shù)關(guān)系。更重要的是，并不是所有的特征都有用，與提供有用信息的特征不同，不相關(guān)特征提供誤導(dǎo)信息，導(dǎo)致學(xué)習(xí)性能的下降。而冗余特征提供了與其他特征相同或相似的信息，浪費了大量的計算資源，嚴重影響了學(xué)習(xí)效率。因此，越來越多的學(xué)者開始探究更好的特征選擇方法，進而從高維的原始特征集中剔除不相關(guān)的冗余特征以減少數(shù)據(jù)的維數(shù)，簡化學(xué)習(xí)模型和提高算法的性能[3]。

粒子群優(yōu)化算法(PSO)[4]是一種基于群體的全局搜索能力較強的算法，是用作特征選擇的一種有效技術(shù)。目前，PSO 在特征選擇中展現(xiàn)出了良好的應(yīng)用前景[5]。然而，它的大多數(shù)應(yīng)用通常是低維的，在具有數(shù)千個或更多特征的高維數(shù)據(jù)上的性能依然有限。

Liang 等[6]提出的綜合學(xué)習(xí)粒子群算法（CLPSO）是連續(xù)粒子群優(yōu)化算法的一種變體。該算法為每個粒子維持了一個樣本池，粒子的每個維度參照樣本池中的粒子編號進行學(xué)習(xí)，保持了種群的多樣性，緩解了粒子群普遍存在的提前收斂問題。Qian 等[7]將概率模型和粗糙集嵌入標簽重要性中，根據(jù)特征依賴和粗糙集，設(shè)計了一種新的多標簽分類特征選擇算法。Zhou 等[8]對每個特征進行基于熵的切點優(yōu)先級排序，同時采用概率指導(dǎo)的局部搜索策略提升算法的性能。Huda 等[9]提出了新的初始化與更新方式，有效地提升了粒子群算法在特征選擇上的性能。

Fister 等[10]將自適應(yīng)差分算法與神經(jīng)網(wǎng)絡(luò)進行結(jié)合，取得了令人鼓舞的進展。Ji 等[11]提出了改進的PSO 算法（IBPSO），引入了局部搜索因子、全局搜索因子，同時采用變異策略維持種群多樣性，取得了較大的性能改善。Chen 等[12]將PSO 算法與差分算法（DE）結(jié)合，提出了混合粒子群算法（HPSO-DE），差分算法用于維持群體多樣性，提升算法的探索能力。Guan 等[13]提出了一種搜索歷史導(dǎo)向的差分進化算法（HGDE），該方法利用存儲在二叉空間劃分樹中的搜索歷史來增強其選擇特征組合的能力。Nguyen 等[14]提出由期望的最大特征數(shù)目確定每個粒子的維度，該方法所選出的特征子集遠遠小于典型解，不過難以確定期望的特征數(shù)量。Gu 等[15]提出的競爭粒子群算法（CSO）引入了粒子競爭行為，在大規(guī)模優(yōu)化上展現(xiàn)出了良好的效果，然而算法的計算效率還有待優(yōu)化。Tran 等[16]提出了可變維度的粒子表示方式，大大縮小了搜索空間。利用維度劃分機制令PSO 可以跳出局部最優(yōu)，取得了更小的特征子集和更高的計算效率。

本文受Tran 等[16]提出的變長粒子維度表示思想的啟發(fā)，提出了一種基于多行為交互的變維協(xié)同進化特征選擇算法(M-CVLPSO)。針對可變維度粒子群算法（VLPSO）初始化階段的盲目性，采用連續(xù)空間上的層次初始化策略，使粒子分布更加均勻，從期望上縮短了初始解與最優(yōu)解的距離。在更新階段，根據(jù)適應(yīng)度將粒子分為領(lǐng)導(dǎo)者、追隨者與淘汰者，不同角色的粒子采用不同的更新方式，動態(tài)平衡算法各個階段的多樣性與收斂性。領(lǐng)導(dǎo)者的合作行為將群體知識從低維傳向高維，有效解決了VLPSO的信息隔離缺陷。最后，將維度縮減率加入適應(yīng)度函數(shù)中，進一步加強了M-CVLPSO 在部分數(shù)據(jù)集上的表現(xiàn)。

1 問題描述

全局優(yōu)化問題可描述為在一個有限對象構(gòu)成的解空間中找出最優(yōu)解的一類問題。根據(jù)優(yōu)化函數(shù)的優(yōu)化目標，全局優(yōu)化問題可以被分為最小值優(yōu)化問題和最大值優(yōu)化問題，而這兩類問題又可以相互轉(zhuǎn)換。

假設(shè)優(yōu)化函數(shù)f(x) 具有m維變量 (x1,x2,···,xm) ，令X1=(x11,x21,···,xm1) 為m維變量的一個可行解，S={X1,X2,···,Xn}為所有可行解構(gòu)成的解空間，則全局優(yōu)化問題可以表示為求解f(x) 的最小值。

目標是找到一個可行解X*滿足公式：

特征選擇可以被表述為如下的最小全局優(yōu)化問題：

其中， χ ∈RN表示潛在可行解集。為了表示被選擇的特征集，x采用長度為N的連續(xù)編碼，N為原始特征集中的特征總數(shù)。對于x中的每一維，如果該維度上的值大于閾值，則代表該特征被選擇，反之則為遺棄特征。這樣，特征選擇就變?yōu)榱藢ふ易罴烟卣髯蛹痻*的組合優(yōu)化問題，以最小化所選特征訓(xùn)練的分類模型的錯誤率。

2 M-CVLPSO 算法模型

2.1 VLPSO

2.1.1 粒子表示方式 VLPSO 采用基于綜合學(xué)習(xí)粒子群算法（CLPSO）的變長粒子表示方法。基于變長表示，粒子的維度可以小于原始特征數(shù)目，該表示方法依然基于向量，不同種群的粒子具有不同長度的表示。圖1 示出了VLPSO 模型的粒子表示方式。

圖1 基于CLPSO 的變長粒子表示示意圖Fig. 1 Clpso-based variable-length particle representation

2.1.2 初始維度劃分 由于不同種群的粒子具有不同的維度，因此需要對原始特征進行合理的劃分。采用對稱不確定度(SU)來計算特征與類標簽的相關(guān)程度。假設(shè)原始特征數(shù)目為D，期望劃分的種群數(shù)目為M，待初始化的粒子總數(shù)為N，從第一個維度開始依次計算特征X與類標簽Y的對稱不確定度Si。SU(X|Y)定義為

IG(X|Y) 為變量X與Y之間的依賴度，定義為

其中：H(X) 為變量X的信息熵；H(X|Y) 為變量X在給定Y下的條件熵。 S U(X|Y)∈[0,1]，X和Y的相關(guān)性與對稱不確定度成正比。

按照Si從大到小對原始特征進行排序，并根據(jù)式（6）計算第m個種群的粒子維度:

每個種群的粒子數(shù)目為

在排序后的原始特征中從前向后依次選擇Dm個特征作為第m個子種群的原始特征空間。

2.1.3 初始維度劃分 模型采用CLPSO 的更新過程，其中，粒子可以向群內(nèi)的任意粒子學(xué)習(xí)，在每個維度上通過概率p決定粒子i選擇自身還是另一個粒子作為學(xué)習(xí)樣本，計算公式為

其中：S為種群規(guī)模； r anki為該粒子在種群中的適應(yīng)度排名。

利用大小為2 的錦標賽機制為每個維度確定學(xué)習(xí)樣本，一個粒子的學(xué)習(xí)樣本將保持不變，直到該粒子連續(xù)未更新的代數(shù)超過設(shè)定的閾值。此時，將重新替換該粒子所有維度上的樣本序號。CLPSO 速度更新公式如下：

其中：rid為 [ 0,1] 上的隨機數(shù)； E xamplar為粒子i的學(xué)習(xí)樣本在d維度上的值；w為慣性權(quán)重因子；c為社會學(xué)習(xí)因子；x代表粒子i第t代在d維度上的值。

2.1.4 維度重劃分機制 為了使粒子群優(yōu)化算法跳出可能的局部最優(yōu)解，當全局最優(yōu)粒子 g best 在預(yù)先設(shè)定的迭代次數(shù)下沒有變化時，計算每個群體中所有粒子的平均適應(yīng)度，標記當前最優(yōu)種群為 S warmbest，保持 S warmbest粒子的維度 B estLen 不變，其余種群按照式(10)更新自身的維度：

其中：k為種群的序號，且不包括 S warmbest；M為種群數(shù)目。

若新維度小于原維度的種群，按照降序從末尾刪除指定個數(shù)的特征；若新維度大于原維度的種群，按照升序從尾部挑選指定個數(shù)的特征加入。

2.2 層次初始化策略

VLPSO 模型采用完全隨機的粒子初始化方式，導(dǎo)致初始粒子在解空間內(nèi)的分布盲目且不均勻，降低了初始種群的探索能力。由于算法的后續(xù)求解都依賴于初始粒子在高維特征空間的探索，因此，初始群體的生成策略對后續(xù)的尋優(yōu)過程有著潛在且深遠的影響。初蓓等[17]在離散空間上提出了一種二向初始化策略，但其搜索方向僅為前向和后向，仍不能保證初始點在搜索空間的多向均勻分布。其次，本文采用的是連續(xù)表示的粒子群方法，需要提出一種連續(xù)空間上的多向初始化策略。為此，本文提出了一種層次初始化策略。

在種群進行初始化時，假設(shè)每個種群粒子數(shù)目為N，當前種群粒子的特征維度為D′，預(yù)期差異群體數(shù)目為Mdiv，則依次隨機選中 「D′/Mdiv」 、 「 2D′/Mdiv」 、···、「(Mdiv-1)D′/Mdiv」維度的特征進行差異群體的粒子初始化。因為采用連續(xù)表示，不能簡單地將維度置為1 或0，而是加入選擇閾值 T hre 來幫助初始化。設(shè)某粒子待初始化維度為Di，則有

其中： R and(a,b) 表示區(qū)間 [a,b] 上的隨機數(shù)。

每個差異群體的粒子數(shù)目均為N/Mdiv。圖2 示出了層次初始化策略下的粒子分布，紅點代表理論最優(yōu)解，層次初始化策略將初始群體均勻散布在不同維度的搜索空間，增強了初始粒子群體的多樣性以及后續(xù)的探索能力，一定程度上降低了隨機帶來的盲目性。

圖2 層次初始化Fig. 2 Hierarchical initialization

2.3 多行為交互策略

VLPSO 模型在進化過程中對所有粒子采用單一的更新策略。然而，多項研究表明適應(yīng)度較差的粒子應(yīng)該加強其全局探索行為的比重，而適應(yīng)度較好的粒子應(yīng)該加強其局部探索行為的比重，因此，不同適應(yīng)度排名的粒子所需要的更新行為是不同的。本文根據(jù)適應(yīng)度排名將粒子分為領(lǐng)導(dǎo)者（排名在前20%）、追隨者（排名在20%～75%）與淘汰者（排名在后25%），提出了一種包含競爭、合作與同化的多行為更新策略。根據(jù)進化過程中粒子適應(yīng)度排名的變化，自適應(yīng)采取不同行為來完成粒子的更新。

2.3.1 競爭行為 淘汰者采用競爭行為進行更新。在每一代進化結(jié)束后，環(huán)境均會對粒子的適應(yīng)度進行評判，并淘汰部分粒子，這樣更加有利于維護進化群體的質(zhì)量，以快速尋找到最優(yōu)解。新生粒子的產(chǎn)生可以借鑒已有的知識，站在“巨人”的肩膀上能夠保證新生粒子的質(zhì)量。

因為采用變長表示，因此不同種群探索的解空間不同，粒子與粒子的競爭主要存在于單個種群的內(nèi)部。設(shè)第m個種群內(nèi)的粒子數(shù)目為Nm，在具有淘汰行為的種群中，對于淘汰粒子k的每個維度，在領(lǐng)導(dǎo)者中隨機選取兩個粒子xi,xj，設(shè) R ankxi＞Rankxj，更新公式如下：

其中：f1和f2為自適應(yīng)系數(shù)； R ankxi和 R ankxj分別為粒子xi、xj在種群中的適應(yīng)度排名。

這種粒子更替策略使目標粒子不會完全被單一粒子所吸引，增強了生成粒子的多樣性和群體的全局探索能力。同時由于目標粒子對群體中優(yōu)秀粒子知識的繼承性，保證了新生粒子的質(zhì)量。

2.3.2 合作行為 領(lǐng)導(dǎo)者采用合作行為進行更新。VLPSO 采用了多種群尋優(yōu)，卻完全隔離了彼此間的信息，浪費了大量的優(yōu)秀知識。由于低維群體探索更小的特征空間，相同迭代次數(shù)內(nèi)在交叉維度上通常較高維群體能夠找到更優(yōu)的特征子集，因此，為了有效利用已有知識，讓高維群體的領(lǐng)導(dǎo)者借鑒低維群體領(lǐng)導(dǎo)者的交叉維度，將知識從低維傳向高維。

首先，將所有種群按照粒子維度從小到大排序，設(shè)待更新種群序號為i，將序號為i-1 的種群按照粒子適應(yīng)度進行排序，得到 S warm。選定待學(xué)習(xí)的高維粒子XHV，假設(shè)排名為k,將 S warm中所有適應(yīng)度高于XHV的粒子加入到樣本池中，如果這樣的低維粒子共有c個，則設(shè)樣本池ExamplarXHV={X1,X2,···,Xc-1,Xc} 。若 E xamplarXHV為空，且滿足p＜p，則按照式（14）對XHV所有維度進行更新：

其中：c1為常數(shù)；r1和r2為 [ 0,1] 之間的常數(shù)；Pbestd為粒子i歷史最優(yōu)值d維度上的值；p為利用式（8）計算的學(xué)習(xí)概率；p為 [ 0,1] 上的隨機數(shù)。

若p＜p，利用所屬種群樣本池進行更新。如式（15）所示：

其中： E xamplard為學(xué)習(xí)樣本d維度的值。

若 E xamplarXHV不為空，對XHV與低維樣本池交叉的維度利用低維度種群生成的樣本池進行更新，并且概率判斷總是成立；對XHV獨有的維度，利用所屬種群樣本池進行更新。兩種情況下的更新公式均同式（15）。

可以看出，僅當?shù)途S群體存在適應(yīng)度優(yōu)于待更新個體的粒子時，才會將交叉維度的樣本池替換為低維群體，否則，仍然利用待更新粒子在所屬種群中生成的樣本池更新所有的維度。

2.3.3 同化行為 追隨者采用同化行為進行更新。在種群進化的過程中，劣勢粒子更加傾向于向種群內(nèi)部的其他優(yōu)秀粒子學(xué)習(xí)。本文借鑒社會學(xué)習(xí)粒子群算法（SL-PSO）[18]的思想，引入社會平均影響的概念，其實驗已經(jīng)表明該因子能有效平衡粒子的多樣性和收斂性。設(shè)待更新的粒子為Xi，所屬種群為Swarmj,則該種群的社會平均影響為

其中：Nj為該種群的粒子數(shù)目。

對當前種群進行適應(yīng)度排序，序號越低的粒子適應(yīng)度越大，不同種群的序號獨立，排序后的種群為Swarmsort_j，生成Xi的樣本池ExamplarXi={X1,X2,···,XrankXi-2,XrankXi-1} ，設(shè)待更新為維度d，若滿足p＞p，則有

若p＜p，則從 E xamplarXi中隨機選擇一個學(xué)習(xí)樣本 E xamplari，粒子更新公式為

其中：r1、r2、r3為 [ 0,1] 之間的常數(shù)； P best為粒子i歷史最優(yōu)值d維度的值； ε 為引誘系數(shù)； β 為常數(shù)；ParSizei為粒子i的維度，粒子i屬于種群j；Nj為第j個種群的粒子個數(shù)。

圖3 示出了多種行為在不同維度群體間的作用方式。種群內(nèi)部進行淘汰和同化行為，種群間由領(lǐng)導(dǎo)者進行合作行為，共同完成種群的迭代更新。

圖3 多行為交互策略下的粒子更新示意圖Fig. 3 Particle update under multi-behavior interaction strategy

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

雖然分類精度可以度量特征子集的性能，但是仍有許多潛在的局限性。 Tran 等[16]提出了結(jié)合分類精度與實例間距離度量distance 的適應(yīng)度函數(shù)評估方法，考慮了特征子集區(qū)分各類別實例的程度，定義為

針對類間距離Db的計算公式，以實例到類外粒子的最小距離作為參考，取其平均值來評估該特征子集對不同類別實例的分離程度，定義為

而類內(nèi)距離Dw以實例到類內(nèi)粒子的最大距離作為參考，取其平均值來評估同一類粒子間的聚合程度：

該適應(yīng)度函數(shù)旨在最大化不同類別實例之間的距離，最小化同類別實例之間的距離。

維度縮減也是特征選擇問題中需要關(guān)注的，更少的特征意味著更小的冗余、更高的計算效率。基于此，本文提出了一種新的適應(yīng)度函數(shù)，定義如下:

其中： γ 、 α 為待設(shè)定的參數(shù)；accuracy 為分類精度；Dis(Ii,Ij)為粒子Ii和Ij距離衡量公式；class(Ii)為粒子Ii的分類結(jié)果； V Desc 為維度縮減率；Vsub為特征子集的維度；Vmax為當前所有種群中的最大特征維度。

該適應(yīng)度函數(shù)在分類精度與實例類間距離相近的狀況下，會優(yōu)先選擇維度較小的粒子。因此，在維度重劃分時，低維種群更容易成為最優(yōu)種群，從而在一定程度上更快地降低群體的平均維度，加速模型的迭代進程。但是，分類精度與類間距離仍然是主要的選擇標準，因此后期應(yīng)分配更小的權(quán)重。

2.5 收斂性證明

與大多數(shù)粒子群優(yōu)化算法理論收斂性分析相似[19-20]，本文從理論上分析M-CVLPSO 模型的收斂性。應(yīng)該指出的是，證明并不保證收斂到全局最優(yōu)。

在不失一般性的前提下，整個群體的收斂可以更具體地看作是任意粒子行為向量中各維的收斂。理論上，應(yīng)該存在一種平衡來誘導(dǎo)這種收斂[21]。考慮粒子i(1 ≤i≤m) 第d(1 ≤d≤n) 個維度的更新，一旦滿足p＜p，X(t) 將會通過式（26）進行更正：

同理，將式（18）代入式（26），并替換所有隨機參數(shù)為其期望值，可以得到：

定理1 式（27）與式（28）描述的動態(tài)系統(tǒng)收斂于平衡狀態(tài)。

證明 對式（27），令 θ =，p=Examplar(t) ，則式（27）可以被重寫為

可以發(fā)現(xiàn)，兩式的基本形式是一致的，因此可以統(tǒng)一驗證其收斂性。式（30）中描述的搜索系統(tǒng)可以看作是一個動態(tài)系統(tǒng)，因此可以利用動態(tài)系統(tǒng)穩(wěn)定性理論對系統(tǒng)進行收斂性分析。為此，將式（30）描述的系統(tǒng)重述為

其中：A在動力系統(tǒng)理論中稱為狀態(tài)矩陣；p為外部輸入，驅(qū)動粒子行為向量到達特定狀態(tài)；B為輸入矩陣，控制外部環(huán)境對粒子動力學(xué)的影響。

如果存在一個平衡y*對任意t滿足y*(t+1)=y*(t)，可以從式（31）和式（32）中計算出

收斂性取決于狀態(tài)矩陣A的特征值:

其特征值為

平衡點是一個穩(wěn)定吸引子，其收斂的充要條件是 | λ1|＜1 并且 | λ2|＜1 ，可以得到

將 ε 利用 ε =β×(ParSizei/Nj) 替換為 P arSizei，條件轉(zhuǎn)換為

2.6 M-CVLPSO 模型框架

本文針對VLPSO 隨機初始化的盲目性、更新策略的單一性問題，分別提出了層次初始化策略和多行為交互策略。M-CVLPSO 算法的偽代碼如下：

輸入：最大迭代輪數(shù)T，種群個數(shù)NbrDiv，最大未改進輪數(shù)k

輸出：特征子集向量

3 實驗與分析

實驗環(huán)境：實驗中所用編程語言為Java，JDK 版本為1.8。實驗計算機配置為CPU：Intel Core i7(2.2 GHz)，內(nèi)存大?。?6 GB，固態(tài)大?。?12 GB。

3.1 數(shù)據(jù)集

在11 個UCI 公開數(shù)據(jù)集上對M-CVLPSO 算法的性能進行測試，表1 給出了數(shù)據(jù)集的具體信息。其中，#Features 表示數(shù)據(jù)集的維度，#Ins 表示實例數(shù)量，#Class 表示類別數(shù)目，%Smallest class 和%Largest class 分別表示實例數(shù)量最少和最多的類別占總實例數(shù)的比重。對每個數(shù)據(jù)集的劃分采用10 交叉驗證方式。以測試集的分類準確率（Classification Accuracy，CA）和平均類間距離（Classification Mean-Distance，CMD）作為評價準則。CA 是正確分類的實例數(shù)占總實例數(shù)的比例，即分類精度；CMD 是兩兩分類實例間的平均間距，代表了分類模型的魯棒性及泛化能力。

表1 實驗數(shù)據(jù)集Table 1 Experiment datasets

3.2 對比算法

為了驗證M-CVLPSO 算法的性能，將其與目前表現(xiàn)最好的同領(lǐng)域算法進行對比，其中，具有代表性的有原始粒子群算法(PSO)[4]、綜合學(xué)習(xí)粒子群算法(CLPSO)[6]、增強綜合學(xué)習(xí)粒子群算法(ECLPSO)[22]、可變維度粒子群算法(VLPSO)[16]等。在大規(guī)模以及超大規(guī)模的數(shù)據(jù)集上從尋優(yōu)精度、維度縮減能力以及計算效率3 個方面驗證每個算法的特征選擇能力。各個算法的公共參數(shù)保持一致，以確保實驗的公平性，詳細參數(shù)設(shè)置如表2 所示。其中，curr_iter 代表當前迭代輪數(shù)，max_iter 代表設(shè)置的最大迭代輪數(shù)。

表2 參數(shù)設(shè)置Table 2 Parameter setting

3.3 實驗結(jié)果與分析

由于粒子群優(yōu)化算法是一種隨機算法，因此針對每種方法在每個數(shù)據(jù)集上分別運行10 個10 交叉驗證。一個10 交叉驗證包含10 次完整的運行結(jié)果，取這10 次完整運行結(jié)果的均值作為該次10 交叉驗證的結(jié)果。算法單次10 交叉驗證均采用不同的隨機數(shù)種子，但不同算法間保持隨機數(shù)種子的一致，100 次實驗結(jié)果的均值如表3 所示。其中，Time 表示算法在該數(shù)據(jù)集上的單次平均運行時間，更少的時間代表更高的運算效率；Size 表示最優(yōu)特征子集的平均維度，越小的維度代表更高的維度縮減能力；Best 表示10 次10 交叉驗證中出現(xiàn)的最優(yōu)單次10 交叉驗證平均分類精度；Mean 則為10 次10 交叉驗證的平均分類精度；Full 代表原始特征集的分類結(jié)果。表4 示出了各個算法在4 個性能指標上的friedman 排名，圖4 示出了各個算法在11 個數(shù)據(jù)集上的詳細性能指標排名情況。

圖4 5 種算法在11 個數(shù)據(jù)集上的各項指標排名Fig. 4 Ranking of the five algorithms on eleven datasets

表3 平均測試結(jié)果Table 3 Average test results

表4 5 種算法在特征集上的平均Friedman 排名Table 4 Average Friedman ranking of the five algorithms on the feature set

從特征子集的維度（Size）來看，PSO、CLPSO 和ECLPSO 均高于M-CVLPSO 若干倍。在維度較低的數(shù)據(jù)集上，如LSVT、SRBCT 等，通常在20 倍以內(nèi)，而在超大規(guī)模數(shù)據(jù)集上，如Leukemia1、Leukemia2、Brain1、Brain2、DLBCL、9Tumor 等，最高可以達到170 倍。與VLPSO 相比，M-CVLPSO 在7 個數(shù)據(jù)集上的平均維度低于VLPSO，其中在GLIOMA、Lung、DLBCL、Brain2 上的縮減相當明顯，最高減少了一半以上的維度。而在剩余的5 個數(shù)據(jù)集上，M-CVLPSO與VLPSO 表現(xiàn)相當，VLPSO 的平均維度略低于MCVLPSO。

從尋優(yōu)的時間復(fù)雜度（Time）來看，M-CVLPSO模型在11 個數(shù)據(jù)集上的表現(xiàn)最好。PSO、ECLPSO和CLPSO 均高于M-CVLPSO 至少5 倍以上的時間。而與VLPSO 相比，這個倍數(shù)在1.3～2.8。分析原因，一是采用了變長維度的表示方法，而低維度粒子相對于高維度粒子擁有更高的更新計算效率；二是相對于VLPSO，多行為交互的更新方式，能夠更快地縮減種群的平均維度，減少了在高維空間探索的代數(shù)，從而降低了計算時間。圖5 示出了各個算法尋優(yōu)過程中種群平均維度的變化情況。

圖5 各種算法種群平均維度隨迭代變化曲線Fig. 5 Average particle dimension of different algorithms varies with iteration

從尋優(yōu)精度來看，在最佳尋優(yōu)精度（Best）上，MCVLPSO 在7 個數(shù)據(jù)集上取得了最好的結(jié)果，獲得了

最高8%的提升。在3 個數(shù)據(jù)集上取得了第二，與第一最高相差2.5%。在GLIOMA 數(shù)據(jù)集上表現(xiàn)較差，排名第三，與CLPSO 相差3.33%。 CLPSO 在GLIOMA、Brain2、Lung、DLBCL 上的最優(yōu)精度略高于M-CVLPSO，但是特征子集的維度和尋優(yōu)的時間復(fù)雜度遠遠高于M-CVLPSO。

平均尋優(yōu)精度（Mean）方面，M-CVLPSO 依舊在7 個數(shù)據(jù)集上取得了第一，最高提升4.67%，同時在Brain2、DLBCL 上取得了第二名。而在GLIOMA、Brain2、DLBCL 數(shù)據(jù)集上，CLPSO 表現(xiàn)強勢，取得了第一。各算法在尋優(yōu)過程中的最優(yōu)粒子適應(yīng)度曲線變化情況如圖6 所示。

圖6 各種算法最優(yōu)粒子適應(yīng)度變化曲線Fig. 6 Optimal particle fitness curves of different algorithms

3.4 新適應(yīng)度函數(shù)的有效性分析

從3.3 節(jié)的實驗結(jié)果可以看出，在DLBCL、Lung、Brain2 以及GLIOMA 數(shù)據(jù)集上，M-CVLPSO 的精度沒有達到最好。從粒子的維度來分析，發(fā)現(xiàn)在這4 個數(shù)據(jù)集上M-CVLPSO 模型的平均粒子維度遠小于包括VLPSO 在內(nèi)的其他算法，可能是模型在后期仍在探索新的維度空間而在有限代數(shù)內(nèi)未能及時收斂。因此，在適應(yīng)度函數(shù)的計算中加入了維度縮減率，期望在前期更快地降低種群維度，從而使模型有更充分的代數(shù)進行低維空間上的探索。同樣，在MCVLPSO 中使用新的適應(yīng)度函數(shù)在上述4 個數(shù)據(jù)集上進行10 個10 交叉驗證，表5 示出了100 次實驗的平均值。其中，I 是未加入維度縮減因子的模型，II 是加入了維度縮減因子的模型，ALL-Best 則代表表3中所有模型在該數(shù)據(jù)集上能夠取得的最好結(jié)果?？梢钥闯?，在這4 個數(shù)據(jù)集中，其在DLBCL、Lung和Brain2 上的結(jié)果均優(yōu)于M-CVLPSO，且在最優(yōu)精度上高于原來所有模型的最優(yōu)值。不過，在平均精度上其相較于M-CVLPSO 有所提升，仍然低于原來的最優(yōu)平均精度，而在粒子維度與運算時間上則基本相當。從實驗結(jié)果來看，維度縮減率能夠影響模型分類精度，且對于大規(guī)模數(shù)據(jù)集上的提升較為明顯。

表5 加入新適應(yīng)度函數(shù)的平均測試結(jié)果Table 5 Mean test results with new fitness function

3.5 層次初始化策略的有效性分析

為了驗證層次初始化策略的有效性，使用未加入該策略的M-CVLPSO-Without 算法進行10 交叉驗證，每次實驗只進行一輪迭代，對10 次實驗結(jié)果的最優(yōu)粒子適應(yīng)度（Gbf）、最優(yōu)粒子維度（Gbs）以及平均粒子適應(yīng)度（Avf）求平均值，結(jié)果如表6 所示?？梢钥闯觯诮^大部分數(shù)據(jù)集上，加入了層次初始化策略后，在一輪迭代后最優(yōu)粒子適應(yīng)度與平均粒子適應(yīng)度取得了較大幅度的提高，提升幅度通常在0.03～0.04。而在最優(yōu)粒子的維度上表現(xiàn)與隨機初始化相當。這表明層次初始化策略能有效提高初始化粒子的適應(yīng)度，但對粒子的維度縮減無明顯提高。

表6 層次初始化單輪迭代平均測試結(jié)果Table 6 single-round iteration average test results

同時，對僅加入層次初始化模塊的模型I′進行5 次10 交叉驗證，所用的隨機數(shù)種子和公共參數(shù)與VLPSO 保持一致。對50 次實驗結(jié)果取平均值，得到的各項數(shù)據(jù)如表7 所示。

表7 層次初始化策略消融實驗結(jié)果Table 7 Ablation experiment results with hierarchical initialization strategy

可以看出加入了層次初始化后，相較于VLPSO，模型I'在9 個數(shù)據(jù)集上取得了更好的最優(yōu)精度，最高提升4.53%，平均提升1.63%；在8 個數(shù)據(jù)集上取得了更好的平均精度，最高提升6.58%。而在LSVT、Leukemia2 和SRBCT 數(shù)據(jù)集上則是小幅度低于原算法。從時間和維度來看，與原算法基本一致，表明層次初始化能整體上提升粒子適應(yīng)度，更容易在有限次迭代內(nèi)找到更好的特征子集，而在維度縮減性能上并無提升。

3.6 多行為交互策略的有效性分析

對僅加入多行為交互模塊的模型II'進行5 次10 交叉驗證，所用的隨機數(shù)種子和公共參數(shù)與VLPSO保持一致。對50 次實驗結(jié)果取平均值，得到的各項數(shù)據(jù)如表8 所示。

表8 多行為交互策略消融實驗結(jié)果Table 8 Ablation experiment results with multi-behavior interactive strategy

可以看出加入了多行為交互策略后，相較于VLPSO，模型II'在9 個數(shù)據(jù)集上取得了最優(yōu)精度，最高提升5.42%，平均提升2.60%，而在9Tumor 與Brain1 數(shù)據(jù)集上略低于原模型。從時間上看，新的更新方式大大減少了運行時間，提高了計算效率。從維度上看，在DLBCL、Lung 和GLIOMA 數(shù)據(jù)集上模型II'取得了較大幅度的提升，在其他數(shù)據(jù)集上則基本相當。

同時，對5 種算法在每個數(shù)據(jù)集上100 次實驗的迭代過程進行分析。因為迭代過程取決于所使用的更新方式，因此可以探究多行為交互策略的有效性。將100 次實驗過程中每輪迭代的種群平均維度、最優(yōu)粒子適應(yīng)度橫向求平均值，迭代曲線如圖5、圖6 所示。取特征數(shù)目差異較大的6 個數(shù)據(jù)集進行展示，更好地探究算法在不同規(guī)模數(shù)據(jù)集上的性能。

可以看出，相對于VLPSO，M-CVLPSO 能更快地降低種群的平均維度，有效地提高了計算效率，因此大大縮減了尋優(yōu)的時間。而在最優(yōu)粒子的適應(yīng)度上，M-CVLPSO 也在4 個數(shù)據(jù)集上取得了更好的平均結(jié)果，僅在DLBCL 數(shù)據(jù)集上弱于VLPSO。而表3的實驗數(shù)據(jù)也表明，M-CVLPSO 最優(yōu)粒子代表的特征子集在多數(shù)數(shù)據(jù)集的分類中取得了更高的精度。與其他模型相比，M-CVLPSO 在種群維度縮減性能上大幅度領(lǐng)先于PSO、ECLPSO 與CLPSO，而在最優(yōu)粒子適應(yīng)度上大幅度領(lǐng)先于PSO、ECLPSO，低于

CLPSO。不過由CLPSO 最優(yōu)粒子的曲線和表3 的尋優(yōu)結(jié)果可以看出，該算法出現(xiàn)了PSO 算法的過早收斂問題，導(dǎo)致過擬合現(xiàn)象的產(chǎn)生，從而影響了在測試集上的泛化能力。

4 結(jié)束語

針對大規(guī)模數(shù)據(jù)集上的特征選擇問題，提出了一種基于多行為交互的變維協(xié)同進化特征選擇方法。首先，提出了連續(xù)空間上的層次初始化策略，從期望上縮短了初始解與最優(yōu)解的距離，一定程度上克服了因隨機帶來的盲目性。在更新階段，通過適應(yīng)度將粒子分為領(lǐng)導(dǎo)者、追隨者與淘汰者，不同角色的粒子采用不同的更新方式，動態(tài)平衡算法各個階段的多樣性與收斂性。領(lǐng)導(dǎo)者的合作行為將群體知識從低維傳向高維，有效解決了VLPSO 的信息隔離缺陷。最后，將維度縮減率加入適應(yīng)度函數(shù)中，進一步加強了M-CVLPSO 在部分數(shù)據(jù)集上的表現(xiàn)?；?1 個大規(guī)模特征選擇數(shù)據(jù)集在分類精度、維度縮減和計算時間上進行實驗分析，相比于4 種對比算法，M-CVLPSO 具有更好的綜合表現(xiàn)。本文主要探究了該方法在大規(guī)模數(shù)據(jù)集上的綜合特征選擇性能，針對具有特定特征，如非平衡大規(guī)模數(shù)據(jù)集上的探索將是下一步的研究方向。