一種改進的粒子群微學習單元特征選擇算法

馮耀武，張月琴，陳 健

(太原理工大學 信息與計算機學院，山西 晉中 030600)

1 引 言

高速度與快節奏的社會把我們推進到“微”時代，從微信、微博到微視頻，進而發展到與學習相關的微課堂，“微”己融入我們生活的方方面面.充斥于網絡的各種“微資源”的存在，讓人們可以把工作閑暇、等人、還有坐車等零碎時間用于基于微資源的自主學習.另一方面，社會的發展使知識更新周期不斷縮短，這要求人們持續更新知識來增強適應能力.在上述背景下，微學習應運而生.微學習通過提供精短的微學習單元，讓學習者可以無時無處，利用零散的時間進行學習，為學習者帶來了極大便利.為此，以MOOC(Massive Open Online Course)為代表的各種微學習教育平臺迅速發展，并在全世界得到普及.

迅速增長的微學習資源在給學習者帶來便利的同時，學習內容的更新速度也越來越快，同一時刻更新的規模也越來越大[1]，從而導致信息過載等問題.借助聚類算法對微學習單元進行處理，將幫助學習者獲得適合自己的學習資源，提高學習效率.微學習資源的多源異構特征決定了其存在維度高及冗余大等特點，對聚類帶來不利影響，從而影響聚類的準確性，同時也會對算法的性能帶來影響.為提高微學習單元聚類的準確性，對微學習資源的聚類數據進行特征選擇，以優化特征子集進而提高微學習單元的聚類準確性.特征選擇作為一種降維方法，能選擇出具有代表性的特征集合用于聚類，從而實現降低冗余和噪聲的目的.

為解決上述問題，本研究提出一種改進的粒子群微學習單元特征選擇算法.該算法具有以下特點：1)把特征冗余和特征代表性作為評價微學習單元特征子集的指標，通過剔除冗余特征屬性，選取有效的特征屬性，幫助提高微學習單元的聚類準確率；2)利用互信息構造適應度函數，以無監督方式實現在微學習單元類標記信息缺乏或者不完全的情況下的特征選取；3)通過自適應突變概率策略，改善算法早熟問題.實驗表明，與已有的特征選擇算法相比，提案算法收斂速度和求解精度都顯著提升.

2 相關理論

2.1 特征選擇

基于一定的評價準則選擇適合的特征子集是特征選擇的目的.定義D為一個m×n的數據集，其中Z為該數據集的特征屬性集合，X是D的一個候選特征子集,J(X)為評價特征子集X有效性的函數.特征選擇問題如公式(1)所示:

J(Z)=maxX?NJ(X)

(1)

換句話說，特征選擇的目的是選擇一部分能夠代表包含特征集合大部分信息的特征子集，采用該特征子集進行聚類分類等能夠獲得與原始特征集合相同或者更好的效果.特征選擇通常有4個步驟：子集生成、特征子集評價、停止準則、驗證過程.一般流程如圖1所示[2].

圖1 特征選擇流程圖Fig.1 Feature selection flow chart

對于由n個特征屬性構成的數據集，所有可能的候選特征子集總共有2n-1種情況.因此特征選擇也是一個NP困難(Non-deterministic Polynomial-Time Hardness)[3].將特征子集生成過程視為尋優過程，通過一定的搜索策略生成待評估的特征子集，然后對候選子集通過評價函數進行評估并與前面迭代中篩選出的最優特征子集作比較，如果新的子集在該評估準則上有更好表現，就把該子集作為最優的特征集合.然后在后續迭代中重復特征子生成和特征子集評估的步驟到停止條件滿足，最后在測試數據集和真實數據集上對提取的特征子集的有效性進行驗證.

特征選擇作為一種有效的降維方法，目前在數據挖掘中的分類、聚類、關聯規則和回歸等問題中已經被廣泛應用[4].經典的特征選擇方法，例如最大方差法和LapScore[5]是根據每個特征獨立計算的分數來選擇排名靠前的特征.這些方法未考慮特征間的相關性，因而在涉及相關性的源數據時，所選擇的特征子集的聚類準確性仍有待提高.Nie等提出的跟蹤比率(Trace Ratio)[6]和Yang等提出的無監督判別特征選擇(UDFS)[7]首先檢測數據的結構特征，然后直接選擇那些能夠最好地保留原始數據封閉結構的特征.Trace Ratio會包含選擇冗余特征而UDFS算法的學習模型往往過于嚴格[8].

目前因為啟發式搜索算法的自身優勢，它在特征選擇問題上收到廣泛關注.特征選擇的過程可以視作是一個求解組合優化問題的過程，因此啟發式算法可以用來解決大數據環境下特征選擇問題.遺傳算法已成功應用于嵌入式特征選擇，但其計算量大，容易過早陷入局部最優.其它算法例如蟻群優化算法、人工蜂群算法和粒子群優化算法等均被應用于特征選擇.在這些算法中粒子群算法因其求解速度快、計算成本低、尋優能力強等特點而備受青睞.Wang[9]等人提出了一種基于粗糙集的粒子群特征選擇算法來，該研究認為基于粒子群的特征選擇算法能夠有效地解決特征子集選擇問題.

2.2 互信息

對于有監督的特征選擇而言，可通過對特征和類標簽間的相關性計算進行特征選擇.然而，在無監督的問題中，沒有可以直接使用的類別標簽.因此，需要一種方法來評估特征是否滿足選擇條件.借助標準互信息構造粒子群適應度函數，可以評估兩個特征之間的相關程度.兩個特征之間的相關程度越高，它們之間的標準互信息就越大.

假設F={f1,f2,…,fd}為原始數據集下的特征集合，Y={yi1,yi2,…,yin}是第i個特征fi的對應特征值，fi的標準互信息計算如公式(2)所示.

(2)

其中MI=(f1,f2)是特征fi和fj的互信息，見公式(3)：

(3)

其中H(fi)和H(fj)分別為特征項fi和fj的信息熵，見公式(4)：

H(fi)=-∑p(yij)log2p(yij)

(4)

可知互信息在特征選擇中可看作已知特征fi的信息對于特征fj的不確定性的減少量，即兩者共有的信息量.從信息論的角度來看，互信息特征選擇方法由于其能夠量化的表示特征間的相關關系已被廣泛應用于特征選擇算法中[10].

2.3 粒子群算法

粒子群算法是Kennedy等人于1995年開發的一種基于種群的隨機優化技術，其靈感來自于鳥群覓食等動物的群體行為[11].粒子群算法通常用于解決組合優化問題.其算法描述為：

設存在一個D維的目標搜索空間，m個粒子組成一個種群，其中第i(i={1，2，…，m} )個粒子表示一個D維向量Xi={xi1，xi2，…，xid}.第i個粒子在目標搜索空間的位置是xi.每個粒子所對應的位置視為一個候選解，將xi帶入到適應度評價函數中，計算其適應度值.每個粒子i有一個速度控制其飛行的方向和距離，Vi={vi1，vi2，…，vid}也是一個D維向量.第i個粒子尋優過程中得到的最優位置記為pb，整個粒子群當前迭代為止搜索到的最佳位置記為pg粒子速度和位置的更新如公式(5)、公式(6)所示:

Vidt+1=uVidt+c1r1(pb-Xidt)+c2r2(pg-Xidt)

(5)

Xidt+1=Xidt+=Vidt

(6)

其中，d={1，2，…，D}，i={1，2，…，m}，m為種群規模;c1和c2為加速常數;r1和r2為[0,1]之間的任意隨機數,t表示粒子迭代次數.

為了優化粒子群算法在離散數據集上的處理，1997年Eberhart等人對粒子群算法進行改進并提出二進制粒子群算法(Binary Particle Swarm Optimization，BPSO)，以此來處理離散數據的全局優化問題.在BPSO算法中，粒子的位置Xi，是用二進制的字符串表示(10110011).粒子的位置更新如公式(7)所示：

(7)

其中，s(·)是s型函數，通過sigmoid函數對速度進行處理，從而確定每個粒子的二進制位置，r3為[0，1]的隨機值.

此外，Kennedy等人[12]對粒子群算法作了進一步優化，刪除傳統粒子群算法的速度向量和相應的控制參數，提出了一種基于高斯采樣的粒子位置更新方法，稱為骨干粒子群算法(Bare Bones Particle Swarm Optimization，BBPSO).具體粒子更新如公式(8)所示：

(8)

與傳統的粒子群算法相比，BBPSO減少了速度分量和c1和c2為加速常數的使用，所以更緊湊、更實用.

粒子群優化是一種相對較新的進化算法，具有全局搜索、實現簡潔、收斂速度快等優點.到目前為止，研究人員已經提出了多種不同的改進算法，并將其應用于解決各種實際問題.王等[13]提出了一種帶有二維擾動和自適應學習因子的粒子群算法，改善算法容易陷入早熟的問題.Wang等人[14]提出了一種基于馬爾可夫毯和粒子群算法的無監督特征選擇算法，該算法首先利用最大熵原理剔除不相關特征，然后將粒子群算法和馬爾可夫毯相結合，去除冗余特征.Abualigah等[15]利用粒子群優化算法進行特征選擇，提高了文本聚類的有效性.

3 改進的骨干粒子群算法的特征選擇方案

針對已有研究成果及存在的問題，本研究提出一種改進的骨干粒子群算法，用于微學習單元的特征選擇.首先，利用互信息構造粒子群算法的適應度函數，以此評價粒子位置所對應的特征子集的效果.針對原算法中粒子位置在迭代過程中的變異概率為固定值，且沒有充分利用適應度函數所提供的信息，在算法后期存在收斂速度變慢，易于陷入局部最優值等問題.本研究通過粒子適應值動態調整算法變異概率大小來平衡粒子的全局尋優能力和局部尋優能力，進而提高算法的執行效率.

3.1 粒子編碼

本文所采用實數編碼的策略，而不是利用sigmoid函數進行轉換.利用特征集合中每個特征被選中的概率值進行編碼，多個編碼概率值組成一個粒子.對于d個特征的數據集而言，編碼后每個粒子的值可以表示為公式(9)：

Xi=(xi,1,xi,2,…,xi,d),i=1,2,3,…,|s|

(9)

式中|s|為粒子種群大小，xi,j表示特征集合中第j個特征被選中的概率.定義一個閾值0.5，用來區分當前粒子的位置所對應的特征是否被選擇，當xi,j≥0.5時，表示該特征被選擇；否則，該特征未被選中.

3.2 適應度函數

傳統的基于粒子群算法的特征選擇方法中的適應度函數通常是根據類別標簽計算特征子集的準確率來構造的，而利用最大平均互信息構造適應度函數作為候選特征集合的評價函數，無需用到類別標簽，適用于無監督的特征選擇，適應度值得計算分為兩個部分，分別考慮了所選特征冗余度度量fit1和特征子集的代表性度量fit2來評價粒子的適應度.冗余度如公式(10)所示：

(10)

其中，SF是當前粒子位置所確定的候選特征子集，max _NMI(fi)為SF集合中的特征fj(i≠j)與fi的最大互信息值，其中最大標準互信息如公式(11)所示：

max_NMI(fi)=max{NMI(fi,fj)|fj∈SF,f≠fj}

(11)

可知fit1的值越小，SF集合的冗余度越小.特征代表性如公式(12)所示：

(12)

其中NSF為冗余特征集合，fmin為SF集合中距離NSF中特征fi最近的特征.可知fit2越大，則SF集合的代表性越強.然后將fit1和fit2進行整合，構造粒子群的適應度函數，整合后的適應度函數fit如公式(13)所示：

(13)

α，β為縮放參數.可知fit越小，所選特征子集的代表性越強，冗余度越低.

3.3 自適應粒子群突變策略

經典的骨干粒子群算法，以固定的粒子群突變概率進行隨機搜索(公式(8)中為固定值0.5).當突變概率設定較大時粒子有較強的全局搜索能力，但是尋優過程容易出現震蕩，穩定性較差.當突變概率閾值設定太小時，粒子有較強的局部尋優搜索能力，但是容易收斂到局部最優解，此時算法的搜索速度慢、求解精度低.針對此問題，需根據不同階段的尋優效果，適應性調整粒子突變概率值大小，處理好全局搜索能力與尋優精度之間的關系.突變概率閾值的設定，對粒子群算法的執行效率有顯著影響.PSO算法具有較強的隨機性，事先確定的突變概率或者突變概率的變化都難以有效應對尋優過程中的隨機性.因此，本文提出一種適應性突變概率策略，通過迭代過程中粒子的適應度值變化信息來適應性調整突變概率mu的大小.第t代粒子的平均適應度值Mt的計算，如公式(14)所示：

(14)

式中:n表示種群中粒子數量;fiti(t)表示第i個粒子迭代到第t代的適應度值.本文是針對適應度值最小化的求解，粒子群的平均適應值的相對變化率見公式(15).

(15)

當變化率k較大時，代表粒子群還未收斂，說明此時突變概率在搜索尋優空間中搜索能力較強，對突變概率進行適應性增加，能夠增強粒子群的開發能力，減少算法迭代前期的執行次數，提升算法性能.當k變化率較小時，說明此時尋優空間相對突變概率較為復雜，難以找到更優極值，因此可以適應性地減小突變概率值，增加粒子群在尋優空間中的局部搜索能力，提高粒子的尋優精度，而不至于因為突變概率值太大而跳過最優解.這樣根據上一次的迭代結果反饋，動態調整當前迭代中的粒子突變概率，具有更好的自適應性.因此，本文提出的突變概率調整如公式(16)所示：

(16)

公式(16)中：mut表示粒子在第t代時的突變概率，γ和δ為突變概率變化大小的調節參數，γ用來調節公式中ln(1+k)的變化幅度，δ用來調節ek的變化幅度.因為在尋優過程中k值的變化幅度較大，故在增加突變概率時使用自然對數，在減小突變概率時使用e作為指數，能夠有效降低其變化幅度，從而使mut+1的變化更平滑.同時給出k的最大值與最小值，讓突變概率在一定范圍內變化，從而避免突變概率過大或者太小的問題.改進后的粒子位置更新如公式(17)所示：

(17)

從公式(16)可知，在k值比較大時，算法的粒子突變概率越大，全局搜索能力越強，從而粒子可以在較大范圍內進行粗搜索，可以較快搜索到全局最優的鄰域；當k值較小時，粒子在最優值附近移動，對應的粒子突變概率變小，局部尋優能力也越強.算法演化為局部的精確搜索，可以更精確地搜索極值.

3.4 算法流程

基于以上基本原理和改進方法，提出微學習單元特征選擇選擇算法，本文算法的流程圖如圖2所示.

圖2 基于改進粒子群算法的特征選擇模型Fig.2 Feature selection model based on improved particle swarm optimization

算法1.自適應突變概率的骨干粒子群特征選擇算法

輸入：預處理后的微學習單元數據.

輸出：微學習單元特征子集.

1.Init：粒子群種群D，大小N，迭代最大次數Maxgen，縮放參數α、β，γ、δ；，初始化粒子群的位置xij以及粒子群局部最優值Pbest；粒子群全局最優值Gbest值;

2.計算粒子群全局最優值

While(i

if(1≥k≥0.01)

按照國家要求劃定了生態保護紅線，對東洞庭、西洞庭、南洞庭3處國際重要濕地，4處國家級自然保護區，22個國家濕地公園，11處國家級水產種質資源保護區等實施了最嚴格的保護，濕地保護率達76.04%，重點推進了自然保護區楊樹清理、違規采砂打擊、內湖保護等工作。通過努力，洞庭湖區濕地自然保護區核心區7.99萬畝楊樹全面清理到位，清理采砂運砂船800多只，所有采砂船集中停放，自然保護區全面實施禁采。同時，堅持“活水”“清水”相結合，實施了四口水系、沅江片區等六大片區河湖聯通工程，使江、湖、河自然水力聯系恢復暢通，有效提升了區域環境容量。

突變概率mu保持不變(公式(16));

else if(k>1‖k≤0.01)

get縮放參數γ、δ;

根據公式(16)更新突變概率mut;

calculate:xij粒子位置(公式(17)),

get縮放參數α、β；

每個粒子的適應度值fit(i)(公式(13));

Gbest′=Pbestmin;//Gbest′為當前迭代中的全局最優值

if(Gbest′

Gbest=Gbest′;

else

Gbest值保持不變;

End While

3.通過Gbest求得對應的特征子集.

4.output:被選擇的特征子集

5.結束處理

4 實驗與結果分析

在本節中，通過一系列實驗來驗證提案算法的有效性.本文首先在5個測試數據集進行特征選擇，并進行聚類測試，然后，通過在真實的微學習單元數數據集下進行對比實驗，進一步驗證提案算法的有效性和準確性.所有實驗在主頻為2.8GHz CPU和8G內存的工作站上完成，實驗環境所在操作系統為Windows7，用Matlab語言在MATLAB2018a環境下實現本文特征選擇算法.

4.1 數據介紹

本文先在5個測試數據集上驗證本文特征選擇算法的有效性，測試數據集為Wine數據集、人臉圖像數據集Jaff和Orl，聲吶數據集Sonar，心臟數據集Statlog.其中包括多種類型的數據集，特征數目最少13，最多為1024.這些數據集的詳細信息如表1所示.

表1 數據集信息Table 1 Data set information

表2 微學習單元數據Table 2 Micro-learning unit data

然后，在3個微學習單元數據集上選擇進行聚類測，實驗數據集為自主搭建的edx學習平臺中搜集的數據集.將一個視頻對應題目，簡介等元數據作為一個微學習單元數據集.本文采用向量空間模型來表示微學習單元，用TF-IDF權重計算方法計算特征項的權重.表2為不同領域的3個微學習單元數據集預處理后的數據信息.

4.2 微學習單元數據預處理

本文采用的微學習單元數據集為英文文本，是基于Python3.6利用NLTK庫進行微學習單元數據集的預處理的過程.通過預處理將微學習單元數據集規范化,主要過程為：

1)文本分詞.本文利用Python已有工具NLTK庫中的word_tokenize()方法，將文本中的每個詞獨立的提取出來從而將文本拆解成詞語單元，分詞通過NLTK正則表達式實現.

2)停用詞去除.文本經過分詞處理之后，針對微學習單元中每一個單詞，對照停用詞表，過濾停用詞表中的單詞.同時去除非英文字符，消除冠詞、連詞等一些無意義無作用的詞，減少數據占用空間，也避免為后續特征選擇帶來的干擾.停用詞庫使用NTLK自帶的停用詞庫.

3)詞形還原.通過詞形還原把數據集中任意形式的詞匯還原為一般形式.獲得的詞的原型，能夠承載一定意義.詞形還原是通過NLTK庫中的lemmatization()算法實現.

4)微學習單元表示.通過向量空間模型對微學習單元進行表示.在表示模型中，首先用m×n的關鍵詞矩陣表示微學習單元.m表示微學習單元個數，n表示特征項出現的頻次.然后通過TF-IDF權重計算方法重新計算特征項的權重.通過CountVectorizer方法將微學習單元中的詞語轉換為詞頻矩陣.通過TfidfTransformer統計每個詞語的TF-IDF值.

對數據集D1進行預處理后的數據如表3所示，在此基礎上進行特征選擇實驗.

4.3 實驗設置

為了驗證本文所提出的算法的有效性和優越性，將本文算法產生的特征子集與原始特征集合、其它4中無監督特征選擇方法所確定的特征子集進行聚類比較.其它無監督特征選擇算法有：

a)多聚類特征選擇(MCFS)，該方法首先使用譜嵌入對數據進行聚類分析，然后通過l1范數正則回歸模型進行特征選擇，選擇的特征盡可能地保持數據的多聚類結構.

b)無監督判別特征選擇方法(UDFS)同時利用了局部判別信息和特征相關性進行特征選擇圖.

c)魯棒非監督特征選擇(RUFS)，該方法通過局部學習正則化正交非負矩陣分解并聯合l2，1范數最小化進行魯棒的特征學習.

d)LapScore，它選擇那些最能保持局部流形結構的特征.

這些算法表現出較好的特征選擇性能，將提案算法與之進行比較，能夠在一定程度上說明本文所提出的算法有效性和相對于其他特征選擇算法優越性.

對比算法中的近鄰參數k均設置為5，算法聚類數目設置為各數據集的類別數.MCFS聚類迭代次數是20次.RUFS算法中向量之間的相似性采用余弦相似性，UDFS算法的正則化參數設置為0.1.記錄不同類型算法的聚類準確率.

表3 預處理后部分數據Table 3 Partial data after preprocessing

本文算法的具體參數設置為：參考文獻[16]中，種群規模應設置為特征數/20且不超過300，本文中種群規模N=50.通過多次實驗，種群初始突變概率mu=0.7，mumax=0.7，最小mumin=0.1時，提案算法可以獲得較好的實驗效果，最大迭代數Maxgen=500可以保證算法收斂.通過分析迭代過程中適應度值的變化過程，并參考文獻[17]中相關參數設置，其實驗表明設置參數α=0.8、β=0.2、γ=1、δ=0.3時在基準測試函數上有良好的收斂性能.

4.4 結果分析與比較

表4是5個測試數據集下的實驗結果.本文從聚類準確率和特征個數兩個方面對不同算法進行評價.表中記錄了了不同特征選擇算法通過k-means聚類，效果最好的特征子集中的特征個數及相應特征子集下的聚類準確率值.用粗體標出了不同算法對應的表現最佳的聚類準確率.用下劃線標出不同算法中特征個數最少的特征.在Orl數據集上，可以看到，對于所有的5個不同類型的數據集，本文所提出的改進算法在Orl、Wine、Statlog、Sonar數據集上都有最高的準確率，在Jaffe數據上的表現，RUFS算法略優于提案算法，但是提案算法所確定的特征個數在122時可以得到與RUFS算法所提取的300個特征相當的聚類準確率.另外且在Orl、Jaffe、Sonar數據集上提案算法得到的特征個數最少.因此，本文算法能夠選擇較少的特征，但對應的聚類性能并未大幅度地下降，反而在大部分數據集上的聚類精度獲得顯著提升.MCFS、UDFS、RUFS使用所有的特征估計數據的基本結構.但是在現實世界中，冗余和噪聲特性是不可避免的，這也是我們需要特征選擇的原因，使用所有特征進行學習數據的結構也會受到這些冗余和噪聲特征的污染，從而降低特征選擇的性能.

表5為不同算法在D1、D2、D3為不同領域的3個微學習單元數據集下的對比，每個數據集中有5類樣本對不同算法得到的微學習單元特征子集通過k-means算法進行聚類.可以直觀的觀察到，本文算法得到的3個微學習單元特征子集進行聚類都有最高的準確率，并且在D1和D2數據集上，提案算法所確定的特征個數也最少；在D3 數據集下提取算法所確定的特征個數雖然略高于UDFS算法，但是本文算法的聚類準確率明顯高于UDFS算法.因此，在微學習單元數據集上的實驗結果表明本文算法能夠選出對微學習單元聚類有效的特征.

表4 測試數據集準確率對比Table 4 Accuracy comparison of test data sets

表5 微學習單元數據集下準確率對比Table 5 Comparison of accuracy in microlearning unit dataset

圖3是本文添加自適應突變概率前后算法在微學習單元數據集D1、D2、D3上的適應度值曲線，其虛線fitness′表示添加適應性策略前，實線fitness表示添加策略后.由圖3可看出，添加自適應突變概率策略后，算法能夠成功跳出局部最優解，收斂到更小的適應度值.在算法迭代前期，適應度值下降較快，算法迭代到后期時曲線時相對平滑.說明迭代前期本文算法對搜索空間有較高的開發率，在迭代后期本文算法有較高的搜索精度.

圖3 微學習單元數據集上適應度值變化曲線Fig.3 Change curve of fitness value on micro-learning unit dataset

5 結 語

為提高微學習單元聚類效果，本文提出了一種基于適應性突變概率的骨干粒子群特征選擇算法，從適應函數構造，適應性突變概率策略等兩個方面進行改進.通過對5個公開測試數據集和3個微學習單元數據集進行實驗對比，可發現本文所提出的算法在對微學習單元進行特征選擇后聚類效果與原始特征集相比有明顯提高，且優與LapScore、MCFS、UDFS、RUFS等特征選擇算法.其中加入適應性突變概率策略后能夠擺脫局部最優值的干擾，收斂到更小的適應度值，可以獲得更好的特征子集.然而，本文提出的適應調整突變概率的粒子群優化算法尚未完全解決算法會陷入局部最優的問題，如何更有效地平衡算法的全局尋優能力和局部尋優能力還有待于進一步的研究.