融合特征權(quán)重與改進(jìn)粒子群優(yōu)化的特征選擇算法

劉振超,苑迎春,2,王克儉,2,何 晨

(1.河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院,河北 保定 071000;2.河北農(nóng)業(yè)大學(xué)河北省農(nóng)業(yè)大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室,河北 保定 071000)

1 引言

大數(shù)據(jù)時代,高等教育信息建設(shè)迅速發(fā)展,使得高校的教育教學(xué)數(shù)據(jù)逐年劇增,有效挖掘并合理利用高校教學(xué)數(shù)據(jù)對學(xué)校管理、教師教學(xué)及學(xué)生自我認(rèn)知的提升都具有重要價值[1]。決策樹因其分類準(zhǔn)確率高、運(yùn)算效率高,被廣泛應(yīng)用于教育教學(xué)數(shù)據(jù)挖掘中。但是,由于教育教學(xué)等數(shù)據(jù)具有維度高、冗余多等特點(diǎn),若將高維原始數(shù)據(jù)直接應(yīng)用于決策樹分類,決策樹分類的準(zhǔn)確率并不理想。特征選擇[2]是數(shù)據(jù)預(yù)處理的關(guān)鍵步驟,是從原始特征集合中篩選出對分類模型性能貢獻(xiàn)度最高的特征子集。特征選擇不但能有效降低數(shù)據(jù)集特征維度,提升分類模型的學(xué)習(xí)效率,還可以從原始數(shù)據(jù)集中選擇對分類器分類性能貢獻(xiàn)最高的特征子集,從而提高分類器的分類準(zhǔn)確率[3]。常見的特征選擇算法根據(jù)其是否包含相關(guān)學(xué)習(xí)算法可以分為過濾式(Filter)和封裝式(Wrapper)2種。

Filter特征選擇算法[4]通過數(shù)據(jù)非標(biāo)簽特征與標(biāo)簽特征之間的潛在規(guī)律以及數(shù)據(jù)本身內(nèi)在性質(zhì)判斷數(shù)據(jù)特征的優(yōu)劣,進(jìn)而篩選特征子集。常用方法有互信息法[5]、信息增益法[6]和特征權(quán)重法[7]等。該類算法具有簡單易行、效率較高和評價標(biāo)準(zhǔn)獨(dú)立于分類算法等特點(diǎn)。

Wrapper特征選擇算法由分類器和搜索算法組成,以分類器的分類準(zhǔn)確率作為性能評估標(biāo)準(zhǔn),通過對原始數(shù)據(jù)特征集進(jìn)行搜索得到特征子集。該類算法能有效篩除冗余特征,提高分類準(zhǔn)確率。已有研究人員利用粒子群優(yōu)化PSO(Particle Swarm Optimization)算法[8]、灰狼算法GWO(Grey Wolf Optimizer)[9]等元啟發(fā)式算法作為搜索策略,有效提高了所選特征質(zhì)量和數(shù)據(jù)分類準(zhǔn)確率。例如,吳曉燕等[10]利用樽海鞘群算法和粒子群優(yōu)化PSO算法進(jìn)行特征選擇,在不同UCI(University of California, Irvine)數(shù)據(jù)集上均可選出最佳特征子集,并在多項(xiàng)評估指標(biāo)上獲得了較好效果;Zhang等[11]提出利用粒子群搜索特征子集的封裝式算法,使用C4.5算法作為評估算法,實(shí)驗(yàn)結(jié)果表明該算法提取的特征子集有較高的辨識度。Wrapper算法盡管提升了分類準(zhǔn)確率,但當(dāng)數(shù)據(jù)維度較高時,仍存在計(jì)算代價高、效率低等問題。

Filter和Wrapper特征選擇算法在特征選擇方面各有優(yōu)勢和不足,因此有研究人員[12]提出了將2類算法融合使用的特征選擇策略。該策略的一般流程為：首先,使用Filter算法剔除部分冗余特征,以減小啟發(fā)式算法的特征搜索規(guī)模;然后,將Filter算法篩選出的特征子集傳遞給Wrapper算法,再進(jìn)一步搜索最優(yōu)特征子集。王金杰等[13]將粒子群優(yōu)化算法和互信息融合成混合式多目標(biāo)特征選擇方法,在15個UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,該算法能夠有效減少特征個數(shù),降低分類錯誤率。肖艷等[14]針對面向?qū)ο笸恋胤诸愔袛?shù)據(jù)特征維數(shù)過高的問題,提出了將RELIEF-F和粒子群優(yōu)化算法混合的特征選擇算法,有效降低了土地?cái)?shù)據(jù)維度,提高了面向?qū)ο笸恋胤诸惖男?。雖然上述文獻(xiàn)均使用了包含粒子群的融合式特征選擇算法,在特征選擇方面進(jìn)行了有效改進(jìn),但相關(guān)研究表明[15,16]：粒子群優(yōu)化算法可能因迭代初期種群個體多樣性的快速降低使得算法收斂過早,出現(xiàn)“早熟”現(xiàn)象,進(jìn)而影響特征選擇算法的性能。

綜上分析,本文提出一種融合特征權(quán)重與改進(jìn)粒子群優(yōu)化算法的混合式特征選擇算法RF- ATPSO(RELIEF-F AdaptiveT-distribution Particle Swarm Optimization)。該算法利用特征權(quán)重過濾法剔除部分冗余特征,有效降低后續(xù)改進(jìn)粒子群優(yōu)化算法的搜索規(guī)模;通過自適應(yīng)權(quán)重和T-分布擾動2種改進(jìn)策略,平衡粒子群優(yōu)化算法的全局探索和局部開發(fā)能力,提高粒子群的多樣性,進(jìn)而保證在Wrapper算法特征選擇時不易陷入局部最優(yōu),從而提高算法的特征選擇性能。

2 改進(jìn)粒子群優(yōu)化算法

搜索算法是Wrapper特征選擇算法中的關(guān)鍵組成部分;而粒子群優(yōu)化PSO算法因其優(yōu)越的全局搜索和尋優(yōu)能力在各個領(lǐng)域被廣泛應(yīng)用。因此,本文利用粒子群優(yōu)化算法在Wrapper算法中搜索最優(yōu)特征子集。但其迭代初期種群個體多樣性的快速降低會使得算法收斂過早,容易陷入局部最優(yōu),進(jìn)而影響選出的特征子集的質(zhì)量。因此,本節(jié)通過自適應(yīng)慣性權(quán)重和T-分布擾動2種策略改進(jìn)粒子群優(yōu)化算法,提高其尋優(yōu)能力,從而提高Wrapper特征選擇算法的性能。

2.1 粒子群優(yōu)化算法基本原理

粒子群優(yōu)化算法是Kennedy等[17]根據(jù)鳥群捕食行為中尋找最佳覓食區(qū)域的過程所提出的一種智能算法,具有原理簡單、參數(shù)少等優(yōu)點(diǎn)。在粒子群優(yōu)化算法中,鳥群中的每個個體都是一個粒子,每個粒子均記錄自己所找到的最佳覓食位置(局部最優(yōu)解),粒子群中所有粒子的最佳覓食位置可以看作全局最優(yōu)解,每個粒子的覓食位置擁有食物的可能性通過適應(yīng)度刻畫。

假設(shè)個體數(shù)為N的粒子群在D維空間中尋找最優(yōu)解,其中第i個粒子在N維空間中可用位置Xi=(xi,1,xi,2,…,xi,D)表示,第i個粒子的飛行速度設(shè)為Vi=(vi,1,vi,2,…,vi,D),第i個粒子的歷史最優(yōu)位置稱為個體最優(yōu)值Pi=(pi,1,pi,2,…,pi,D),整個粒子群的最優(yōu)位置稱為全局最優(yōu)值Gbest=(gbest,1,gbest,2,…,gbest,D)。根據(jù)第i個粒子、第i個粒子最優(yōu)值Pi和全局最優(yōu)值Gbest對粒子的速度和位置進(jìn)行更新,更新公式如式(1)和式(2)所示：

v′i,d=ω×vi,d+c1r1(pi,d-xi,d)+

c2r2(gbest,d-xi,d)

(1)

x′i,d=xi,d+vi,d

(2)

其中,ω表示粒子的慣性權(quán)重,該值將會影響算法的收斂性;c1和c2表示學(xué)習(xí)因子,即加速常數(shù);r1、r2表示0～1之間的隨機(jī)數(shù);1≤d≤D。

根據(jù)上述公式可以看出,粒子群優(yōu)化算法尋優(yōu)基于本身(局部最優(yōu))及周圍個體的經(jīng)驗(yàn)(全局最優(yōu))進(jìn)行決策。在迭代初期,粒子群的個體多樣性迅速降低,導(dǎo)致算法提前收斂,從而丟失一些重要的位置信息。針對以上不足,本文從2個方面對粒子群優(yōu)化算法進(jìn)行改進(jìn),平衡算法的全局探索和局部開發(fā)能力,提升粒子群優(yōu)化算法的搜索精度。

2.2 自適應(yīng)慣性權(quán)重策略

ω為粒子的慣性權(quán)重,其取值將影響算法收斂性。在粒子群迭代過程中,算法迭代前期需要增加粒子變化步長,從而較早定位全局最優(yōu)解所在的區(qū)域;算法迭代后期則需要減小粒子變化步長,使粒子在該區(qū)域內(nèi)精細(xì)化搜索,以找到全局最優(yōu)解?；谏鲜鏊枷?本文提出自適應(yīng)慣性權(quán)重策略來平衡算法的全局探索和局部開發(fā)能力。ω的計(jì)算可用式(3)表示：

ω=0.8×e-3(t/tmax)2

(3)

其中,t表示迭代次數(shù),tmax表示最大迭代次數(shù)。ω在迭代初期盡可能取最大值,使算法步長迅速變化,方便進(jìn)行全局搜索;隨著迭代的進(jìn)行,權(quán)重不斷減小,側(cè)重進(jìn)行局部搜索。該策略有效平衡了算法的全局探索和局部開發(fā)能力。

2.3 T-分布擾動策略

在迭代初期粒子種群個體多樣性迅速下降,導(dǎo)致迭代后期種群多樣性較低。粒子群的群體最優(yōu)值遠(yuǎn)離全局最優(yōu)值時,粒子易向錯誤方向進(jìn)化和學(xué)習(xí),此情況下極易陷入局部最優(yōu)。本文提出了一種基于T-分布的擾動策略,以實(shí)現(xiàn)在算法迭代過程中增加粒子種群的多樣性并及時跳出局部最優(yōu)。即如果經(jīng)過連續(xù)幾次迭代,當(dāng)前粒子的最優(yōu)適應(yīng)度值基本沒有或不再發(fā)生變化,則認(rèn)為算法陷入局部最優(yōu),在這時加入擾動讓粒子震蕩,使其跳出局部最優(yōu),這樣也增加了種群多樣性。該策略如式(4)所示：

(4)

3 融合特征權(quán)重和ATPSO的特征選擇(RF-ATPSO)算法

在過濾式算法中,特征權(quán)重算法RELIEF-F具有運(yùn)行效率高、特征選擇結(jié)果辨識度好的優(yōu)勢。本文提出雙策略改進(jìn)粒子群優(yōu)化算法平衡了全局探索和局部開發(fā)能力,增加了粒子的多樣性,提高了粒子群優(yōu)化算法的搜索能力?；诖?提出一種將特征權(quán)重算法RELIEF-F與改進(jìn)粒子群優(yōu)化算法融合的混合特征選擇算法。該算法主要包括2部分：首先使用特征權(quán)重算法對原始特征集合進(jìn)行初步特征篩選;然后從篩選后的特征集合中利用改進(jìn)粒子群優(yōu)化算法搜索最優(yōu)特征子集,提高所選特征子集的精度及后來的分類準(zhǔn)確率。其中又包括2個關(guān)鍵步驟,分別是粒子群二進(jìn)制轉(zhuǎn)化和適應(yīng)度函數(shù)設(shè)計(jì)。

3.1 特征權(quán)重算法RELIEF-F

RELIEF-F算法是Kononenko等[18]在1994年基于RELIEF算法改進(jìn)的一種適用于多分類的特征選擇方法。

特征權(quán)重計(jì)算流程如下：

重復(fù)執(zhí)行步驟(1)～步驟(3)共m次：

(1)從數(shù)據(jù)集中隨機(jī)抽取樣本R,選擇R的猜中近鄰和猜錯近鄰各k個,分別記作集合H={h1,h2,…,hk},M={m1,m2,…,mk}。

(2)根據(jù)以下規(guī)則進(jìn)行特征權(quán)重更新：若R和H中所有樣本在某個特征上的距離小于R和M中所有樣本的距離,說明該特征對區(qū)分同類和異類樣本最近鄰有益,則增加該特征權(quán)重,反之降低該特征權(quán)重。

(3)根據(jù)式(5)和式(6)更新特征A的特征權(quán)重,直到最大迭代次數(shù)結(jié)束。

(5)

(m×k)

(6)

其中,A表示樣本的一種特征,max(A)和min(A)分別表示特征A上的最大取值和最小取值,R[A]表示樣本R的特征A上的值,hj[A]表示猜中近鄰中第j個樣本hj在特征A上的值;diff(A,R,hj)表示樣本R與樣本hj在特征A上的差;P(C)表示C類的比例;P(class(R))表示隨機(jī)抽取樣本R所屬類別的比例;mj表示C類樣本中的第j個最近鄰樣本。

3.2 粒子群二進(jìn)制轉(zhuǎn)化方式

基于ATPSO(AdaptiveT-distribution Particle Swarm Optimization)法對數(shù)據(jù)集進(jìn)行特征選擇,可以看作將解空間限定在{0,1}范圍內(nèi)的二進(jìn)制優(yōu)化問題。需要注意的一點(diǎn)是,進(jìn)行特征選擇時,需要將連續(xù)型優(yōu)化問題轉(zhuǎn)換為離散型優(yōu)化問題。

首先要對粒子群中的粒子進(jìn)行編碼。一個完整的特征選擇解對應(yīng)改進(jìn)粒子群優(yōu)化算法中的一個粒子,粒子的維度與原始數(shù)據(jù)集中樣本的特征屬性數(shù)量相同,且粒子群個體的某個維度值xi,j∈{0,1}。若要將離散粒子群與特征選擇問題正確對應(yīng),需定義粒子群編碼規(guī)則。編碼規(guī)則為：若xi,j=1,表明第i個粒子的第j個特征被選擇,若xi,j=0,則表明第i個粒子的第j個特征未被選擇。

除粒子編碼問題外,連續(xù)型優(yōu)化問題如何轉(zhuǎn)換為離散型優(yōu)化問題也同樣重要。本文利用Sigmoid函數(shù)將連續(xù)型變量轉(zhuǎn)換為二進(jìn)制形式。Sigmoid函數(shù)如式(7)所示：

(7)

具體到特征選擇上,需要將連續(xù)型粒子的各個維度映射到{0,1},需將xi,j帶入Sigmoid函數(shù),結(jié)果如式(8)所示：

(8)

其中,映射函數(shù)T(·)表示粒子中的元素xi,j取值為1的概率。綜上所述,粒子群的位置更新策略可以用式(9)進(jìn)行描述：

(9)

其中,rand為[0,1]的隨機(jī)數(shù)。若隨機(jī)數(shù)大于或等于元素xi,j取值為1的概率,則rand取值為1,否則取值為0。

以粒子群的某一種特征選擇解為例。假設(shè)原始數(shù)據(jù)集擁有7個特征,在ATPSO算法迭代中某個粒子位置的結(jié)果如圖1所示。由圖1可知,xi,2=xi,3=xi,5=xi,6=1,xi,1=xi,4=0,表明第i個粒子將原始數(shù)據(jù)特征2,3,5和6選中作為特征選擇的最優(yōu)特征子集,將原始數(shù)據(jù)特征1和4篩除。最終利用分類器可以基于選出來的最優(yōu)特征子集進(jìn)行模型訓(xùn)練與數(shù)據(jù)分類。

Figure 1 Feature selection solution圖1 特征選擇解

3.3 適應(yīng)度函數(shù)設(shè)計(jì)

數(shù)據(jù)集的特征選擇可以轉(zhuǎn)化成多目標(biāo)優(yōu)化問題。優(yōu)化目標(biāo)為：在滿足特征選擇數(shù)量最小化的同時,也最大化分類器的分類準(zhǔn)確率?；谏鲜?個優(yōu)化目標(biāo),本文將適應(yīng)度函數(shù)定義為式(10)：

(10)

其中,error_rate表示指定分類算法(本文采用決策樹算法)的誤分率,D表示數(shù)據(jù)集中樣本的特征總數(shù)量,RF表示特征選擇算法最終所選擇的特征子集大小,α、β分別對應(yīng)分類算法誤分率和特征子集大小在適應(yīng)度中的重要性。α、β∈[0,1],且α+β=1。

3.4 RF-ATPSO算法流程

RF-ATPSO特征選擇算法首先使用特征權(quán)重算法對原始特征集合進(jìn)行初步特征篩選,然后從篩選后的特征集合中利用改進(jìn)粒子群優(yōu)化算法搜索最優(yōu)特征子集,最終得到最優(yōu)特征子集。算法詳細(xì)步驟如下所示：

算法1 RF-ATPSO特征選擇算法輸入：基準(zhǔn)數(shù)據(jù)集。輸出：最優(yōu)特征子集以及分類算法的準(zhǔn)確率。步驟1 輸入基準(zhǔn)數(shù)據(jù)集,將其按照7∶3的比例劃分為訓(xùn)練集和測試集,設(shè)置C4.5為評估算法。步驟2 使用RELIEF-F算法計(jì)算各個特征權(quán)重并按照權(quán)重對特征排序。步驟3 根據(jù)設(shè)定閾值對有序的特征集進(jìn)行篩選。步驟4 初始化粒子群優(yōu)化算法參數(shù),初始化粒子初始位置并利用式(9)實(shí)現(xiàn)粒子位置和特征集的映射。步驟5 利用式(10)計(jì)算粒子適應(yīng)度值。步驟6 比較每個粒子的適應(yīng)度值,更新全局和局部最優(yōu)解。步驟7 利用自適應(yīng)慣性權(quán)重策略(式(1)和式(2)所示),更新粒子位置。步驟8 執(zhí)行T-分布策略。步驟9 若未達(dá)到最大迭代次數(shù)則跳轉(zhuǎn)至步驟5。步驟10 輸出最優(yōu)特征子集和分類準(zhǔn)確率。

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

4.1 數(shù)據(jù)集介紹與實(shí)驗(yàn)設(shè)置

4.1.1 數(shù)據(jù)集介紹

為充分驗(yàn)證本文提出的RF-ATPSO算法的有效性,本文基于加州大學(xué)UCI機(jī)器學(xué)習(xí)庫中的6個標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。這些數(shù)據(jù)集分別來自不同領(lǐng)域,如Spambase主要用于冗余郵件的識別分類,Arrhythmia心率失常數(shù)據(jù)集和Cancer癌癥數(shù)據(jù)集為醫(yī)學(xué)數(shù)據(jù)集。

表1簡要介紹了上述6個UCI數(shù)據(jù)集和學(xué)生畫像指標(biāo)數(shù)據(jù)集的樣本數(shù)量、特征數(shù)量和類別數(shù)量。

Table 1 Datasets introduction

為進(jìn)一步驗(yàn)證本文算法的魯棒性,實(shí)驗(yàn)選用本研究團(tuán)隊(duì)構(gòu)建的某高校學(xué)生學(xué)業(yè)成績畫像指標(biāo)數(shù)據(jù)集。該數(shù)據(jù)集從學(xué)分體系模塊、成績體系模塊和課程指標(biāo)體系模塊3個方面構(gòu)建學(xué)業(yè)指標(biāo)體系,全方位刻畫學(xué)期、學(xué)年和課程類別等方面的學(xué)生學(xué)業(yè)成績情況。

構(gòu)建的學(xué)生學(xué)業(yè)成績畫像指標(biāo)具體如表2所示。在表2中,學(xué)分指標(biāo)體系擁有1個一級指標(biāo),二級指標(biāo)按照課程類別、課程屬性進(jìn)行劃分;成績指標(biāo)體系擁有3個一級指標(biāo),當(dāng)前總績點(diǎn)排名二級指標(biāo)按照課程類別進(jìn)行劃分,成績波動程度二級指標(biāo)按照學(xué)期學(xué)年時間線進(jìn)行劃分,總掛科率二級指標(biāo)按照課程類別進(jìn)行劃分;課程指標(biāo)體系擁有5個一級指標(biāo),共將學(xué)生課程分為3段,總優(yōu)秀課程學(xué)分率是對總課程優(yōu)秀率的補(bǔ)充,其次是低于課程均分率,最后為及格率,二級指標(biāo)均按照課程種類或時間線進(jìn)行劃分。

本文使用分類算法的分類準(zhǔn)確率來評估特征選擇算法所選特征子集的優(yōu)劣。因此,本文實(shí)驗(yàn)中對原始數(shù)據(jù)集與經(jīng)過特征選擇后的數(shù)據(jù)集使用C4.5決策樹算法的分類準(zhǔn)確率和最終選擇特征的數(shù)量進(jìn)行評估。本文實(shí)驗(yàn)包括基于UCI公共數(shù)據(jù)集實(shí)驗(yàn)和應(yīng)用實(shí)驗(yàn),之后再在學(xué)生畫像指標(biāo)數(shù)據(jù)集上進(jìn)一步評估算法的應(yīng)用能力。

4.1.2 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)的機(jī)器配置參數(shù)如下：基于Intel?CoreTMi56300HQ、2.6 GHz主頻、16 GB內(nèi)存以及Windows 10操作系統(tǒng),實(shí)驗(yàn)仿真軟件采用PyCharm, 2020.2版本。

參數(shù)設(shè)置會影響算法的全局收斂性能?？刂茀?shù)實(shí)驗(yàn)被廣泛用于調(diào)度優(yōu)化、組合優(yōu)化和函數(shù)優(yōu)化等問題,具有易于理解、便于實(shí)現(xiàn)等優(yōu)點(diǎn)[19,20]。因此,本文將控制參數(shù)實(shí)驗(yàn)用于算法參數(shù)的設(shè)定。通過實(shí)驗(yàn)設(shè)計(jì),對粒子群優(yōu)化算法的2個學(xué)習(xí)因子(c1和c2)進(jìn)行設(shè)定。本文給出了參數(shù)選擇表,如表3所示,共選取9組參數(shù)組合,并將式(10)作為適應(yīng)度函數(shù)。由于算法的隨機(jī)性等特點(diǎn),本文將每組參數(shù)運(yùn)行10次的結(jié)果取平均值作為最終適應(yīng)度值。通過9組實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn),學(xué)習(xí)因子c1和c2值為2時,算法的適應(yīng)度值最低,算法的性能最好。為保證實(shí)驗(yàn)的公平性,最大迭代次數(shù)和種群規(guī)模均與對比算法的一致。

Table 3 Parameter selection table

因此,所用粒子群優(yōu)化算法的參數(shù)設(shè)置如下：學(xué)習(xí)因子c1和c2值為2,粒子個數(shù)N值為30,最大迭代次數(shù)tmax值為100。

4.2 UCI公共數(shù)據(jù)集實(shí)驗(yàn)

4.2.1 UCI公共數(shù)據(jù)集實(shí)驗(yàn)數(shù)據(jù)集介紹

為了檢驗(yàn)提出的RF-ATPSO算法的性能及穩(wěn)定性,本文基于UCI公共數(shù)據(jù)集,將RF- ATPSO算法與傳統(tǒng)特征選擇算法(包括RELIEF-F、PSO、GWO、RFGWO和RFPSO算法)進(jìn)行對比實(shí)驗(yàn)。

實(shí)驗(yàn)分別在6個UCI公共數(shù)據(jù)集上進(jìn)行,通過計(jì)算各算法選出的特征子集的準(zhǔn)確率來評估算法的性能。在每個數(shù)據(jù)集上取20次實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果,分別選取最優(yōu)準(zhǔn)確率(Best)和平均準(zhǔn)確率(Avg)2個指標(biāo)來度量不同算法的性能。表4展示了RF-ATPSO算法與傳統(tǒng)特征選擇算法在6個數(shù)據(jù)集上取得的分類準(zhǔn)確率。

由表4可知,C4.5算法在其原始特征集合上的準(zhǔn)確率均比經(jīng)過特征選擇后的準(zhǔn)確率低,出現(xiàn)這種現(xiàn)象主要因?yàn)樵紨?shù)據(jù)高維特征空間和特征高度冗余對C4.5的分類結(jié)果產(chǎn)生了較大影響,但是也存在經(jīng)過特征選擇后的特征子集辨識度變差的情況。

表5給出了RF-ATPSO算法與傳統(tǒng)特征選擇算法從6個數(shù)據(jù)集中提取的平均特征子集規(guī)模。由表5可知,基于RF-ATPSO算法對數(shù)據(jù)集進(jìn)行特征選擇后,特征空間維度明顯減小。觀察表4和表5可知,RF-ATPSO算法在Meu、Scadi、Can- cer、Arrhythmia和HillValley 5個數(shù)據(jù)集上所選的特征子集規(guī)模最小且準(zhǔn)確率最高,即能以最低的特征空間維度取得最高的準(zhǔn)確率?？傊?本文提出的RF-ATPSO算法在保證準(zhǔn)確率的情況下,可以有效提高C4.5算法的運(yùn)行效率。

Table 5 Average sizes of feature subsets extracted by RF-ATPSO algorithm and traditional feature selection algorithms from 6 datasets

進(jìn)一步分析表4中的實(shí)驗(yàn)結(jié)果,可以發(fā)現(xiàn)：對比3種傳統(tǒng)的Filter和Wrapper算法RELIEF-F、GWO、PSO可知,經(jīng)過特征選擇后,C4.5算法分類準(zhǔn)確率均有不同程度的提高。2種Wrapper算法在不同數(shù)據(jù)集上的性能表現(xiàn)不同,在Meu、Scadi、Spambase和HillValley數(shù)據(jù)集上,PSO算法的結(jié)果最優(yōu),在Cancer和Arrhythmia數(shù)據(jù)集上,GWO算法的結(jié)果最優(yōu)。整體而言,PSO算法要優(yōu)于RELIEF-F和GWO算法,平均分類準(zhǔn)確率較2種算法分別提高了7.68%和0.70%。在所選特征子集規(guī)模上,PSO算法在6個數(shù)據(jù)集上均優(yōu)于GWO算法,平均特征子集規(guī)模比GWO算法的低8.63?？傮w而言,PSO的特征選擇結(jié)果較GWO具有一定優(yōu)勢。

對比3種混合式算法可知,算法針對不同的數(shù)據(jù)集,性能可能也會有所區(qū)別。由表4可知,在Scadi、Cancer、Arrhythmia和HillValley數(shù)據(jù)集上,RF-ATPSO平均分類準(zhǔn)確率最高,較RFGWO和RFPSO算法的均有小幅度提升,分別為1.51%,1.29%;在Meu數(shù)據(jù)集上,平均準(zhǔn)確率最高,但其最高分類準(zhǔn)確率表現(xiàn)并非最優(yōu);在所選特征子集規(guī)模上,RT-ATPSO算法在除Meu外的5個數(shù)據(jù)集上,特征子集規(guī)模最小;對比本文提出的RF- ATPSO和其他特征選擇算法可知,RF-ATPSO算法在Spambase數(shù)據(jù)集上分類準(zhǔn)確率未達(dá)到最優(yōu),但整體而言RF-ATPSO的平均分類準(zhǔn)確率達(dá)到81.54%,在所有數(shù)據(jù)集上均表現(xiàn)最優(yōu)。

4.2.2 UCI公共數(shù)據(jù)集收斂性對比

本節(jié)實(shí)驗(yàn)將GWO、PSO、RFGWO、RFPSO和RF-ATPSO算法進(jìn)行對比分析,圖2為3種封裝式特征選擇算法在6個數(shù)據(jù)集上的錯誤率收斂曲線。

Figure 2 Error rate convergence curves圖2 錯誤率收斂曲線

從圖2可以看出,在Cancer、Arrhythmia和HillValley數(shù)據(jù)集上,RF-ATPSO算法的收斂曲線均在GWO、PSO、RFGWO和RFPSO算法的之下;在Cancer和HillValley數(shù)據(jù)集上,RF-ATPSO算法擁有較低的初始適應(yīng)度值,并且能快速收斂至全局最優(yōu)解,在所有算法中收斂速度最快;在Arrhythmia數(shù)據(jù)集上,RF-ATPSO算法在迭代前期收斂速度低于RFPSO和RFGWO算法的,但在第30次迭代時,可迅速跳出局部最優(yōu)解,向全局最優(yōu)解收斂;在Scadi數(shù)據(jù)集上,沒有經(jīng)初步特征選擇的PSO算法收斂速度較慢,但其優(yōu)于GWO和RFGWO算法,RF-ATPSO算法初始和最終收斂值最低,具有較快的收斂速度;在Meu和Spambase數(shù)據(jù)集上,盡管RF-ATPSO算法沒有取得最優(yōu)的收斂效果,但RF-ATPSO算法的收斂曲線在RFPSO的之下,因此本文提出的改進(jìn)策略有效,并且利用PSO算法進(jìn)行特征選擇后均優(yōu)于使用GWO算法的。經(jīng)過RELIEF-F算法初步篩選特征后的RFPSO和RF-ATPSO算法收斂速度和收斂適應(yīng)度值均不如PSO算法的,說明在上述2個數(shù)據(jù)集上RELIEF-F算法篩選過的特征子集本身辨識度差,在原特征空間中搜尋效果更佳。

4.3 學(xué)生學(xué)業(yè)成績畫像指標(biāo)數(shù)據(jù)集實(shí)驗(yàn)

4.3.1 分類準(zhǔn)確率和收斂性分析

為進(jìn)一步驗(yàn)證RF-ATPSO算法的有效性,在表2所示的某高校學(xué)生學(xué)業(yè)成績畫像指標(biāo)數(shù)據(jù)集上進(jìn)行對比實(shí)驗(yàn)。選取計(jì)算機(jī)專業(yè)四年學(xué)業(yè)成績數(shù)據(jù),按照本文設(shè)計(jì)的特征指標(biāo)體系,構(gòu)建出的學(xué)生學(xué)業(yè)成績畫像擁有227維特征。實(shí)驗(yàn)中RELIEF-F、GWO、PSO、RFGWO、RFPSO和RF-ATPSO算法分別運(yùn)行20次,分類準(zhǔn)確率均值計(jì)算結(jié)果如表6所示。

Table 6 Classification accuracies of feature selection for the portrait index dataset

由表6可以看出,C4.5算法在原始數(shù)據(jù)集上的分類準(zhǔn)確率較差,平均準(zhǔn)確率僅為88.51%,比用RF-ATPSO算法進(jìn)行特征選擇后的平均準(zhǔn)確率低6.26%。RF-ATPSO算法在學(xué)生類別1、2及所有類別平均值上的準(zhǔn)確率最高,尤其在類別2上準(zhǔn)確率達(dá)到94.82%,比原始數(shù)據(jù)集的準(zhǔn)確率高6.96%。

RF-ATPSO算法相較于其他5種特征選擇算法不僅總體準(zhǔn)確率分別提高了4.66%,2.64%,2.19%,2.15%和1.98%,而且在3個類別上也均有不同程度的提高。在類別1和類別2上,RF-ATPSO算法所求得的特征子集準(zhǔn)確率最高,分別達(dá)到了93.68%和96.71%。

學(xué)生學(xué)業(yè)成績畫像指標(biāo)數(shù)據(jù)收斂曲線如圖3所示。從圖3可知,RF-ATPSO算法在收斂速度和收斂值方面,均優(yōu)于其余4種特征選擇算法;

Figure 3 Convergence curves of student profile indicator data圖3 學(xué)生畫像指標(biāo)數(shù)據(jù)收斂曲線

RF-ATPSO算法在第15次已尋找到全局最優(yōu)解,證明其收斂速度較快,可及時跳出局部最優(yōu)解;GWO、PSO分別在第50次和第19次尋找到全局最優(yōu)值;RFGWO、RFPSO分別在第18次和第17次尋找到全局最優(yōu)值。因此,RF-ATPSO不僅迭代次數(shù)少且最優(yōu)解適應(yīng)度值更低,擁有較高的尋優(yōu)效率。

4.3.2 RF-ATPSO特征選擇結(jié)果分析

如前所述,本文構(gòu)建的學(xué)生學(xué)業(yè)成績畫像經(jīng)過RF-ATPSO算法特征選擇后降到了82維,包括44個成績指標(biāo)(含8個課程排名指標(biāo)、14個成績波動指標(biāo)、3個平均排名指標(biāo)、18個績點(diǎn)排名指標(biāo)和1個掛科總學(xué)分指標(biāo));37個課程指標(biāo)(含22個優(yōu)秀課程指標(biāo)、5個優(yōu)秀課程學(xué)分率指標(biāo)、6個低于均分課程率指標(biāo)和4個優(yōu)秀課程率指標(biāo))。

在實(shí)際數(shù)據(jù)中,學(xué)生出現(xiàn)掛科(不及格)的情況較少,因此,學(xué)分指標(biāo)體系下各學(xué)生的各項(xiàng)指標(biāo)值,大多接近于1,因此學(xué)分率的區(qū)分度不高,在特征選擇結(jié)果中也基本沒有學(xué)分率指標(biāo)體系中的指標(biāo),可見該特征選擇結(jié)果符合實(shí)際情況。在選擇出的37個課程指標(biāo)中,所有及格率相關(guān)指標(biāo)的值均接近1,因此區(qū)分度不高,實(shí)際特征選擇結(jié)果中,也沒有及格率相關(guān)指標(biāo),可見該特征選擇結(jié)果也符合實(shí)際情況。

5 結(jié)束語

針對高校教務(wù)領(lǐng)域數(shù)據(jù)固有的高維特征空間和高度冗余問題,本文提出了一種融合特征權(quán)重和改進(jìn)粒子群優(yōu)化算法的混合式特征選擇算法(RF-ATPSO)。該算法主要分為2個步驟,首先使用RELIEF-F算法計(jì)算各個特征的權(quán)重,篩除冗余特征;然后從篩選出的特征集合中利用改進(jìn)粒子群優(yōu)化算法搜索最優(yōu)特征子集。

實(shí)驗(yàn)方面,首先在6個UCI公共數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。結(jié)果表明,C4.5算法在經(jīng)過RF-ATPSO算法特征篩選后的數(shù)據(jù)集上不僅準(zhǔn)確率優(yōu)于其他特征選擇算法的,而且算法所選特征子集規(guī)模最小,在保證準(zhǔn)確率的同時提高了C4.5算法的運(yùn)行效率。在學(xué)生學(xué)業(yè)成績畫像指標(biāo)數(shù)據(jù)集上的結(jié)果表明,C4.5算法在經(jīng)過RF-ATPSO算法特征篩選后的數(shù)據(jù)集上準(zhǔn)確率達(dá)到94.77%,優(yōu)于其他傳統(tǒng)特征選擇算法。盡管本文提出的RF-ATPSO特征選擇算法在大部分?jǐn)?shù)據(jù)集上取得了較好效果,但還存在經(jīng)RELIEF-F特征選擇后特征子集辨識度變差的問題,未來將重點(diǎn)研究提高特征子集辨識度的最優(yōu)方法。