利用并行慣性權(quán)重OOL-FA的大數(shù)據(jù)分類

鐘章生，陳世爐，陳志龍

(1.南昌理工學(xué)院 計算機(jī)信息工程學(xué)院，江西 南昌 330013；2.中國船舶總公司 第六三五四研究所，江西 九江 332000；3.南昌理工學(xué)院 電子與信息學(xué)院，江西 南昌 330013)

0 引 言

在數(shù)字化時代，深入挖掘海量數(shù)據(jù)內(nèi)部蘊(yùn)藏的有用信息來指導(dǎo)具體的工程問題，而在基于MapReduce范式的技術(shù)體系中，數(shù)據(jù)特征選擇與數(shù)據(jù)分類是兩項非常重要且復(fù)雜的工作[1-3]。

針對特征選擇問題，部分文獻(xiàn)提出針對高維數(shù)據(jù)的輕量級特征選擇方法，采用加速粒子群優(yōu)化對數(shù)據(jù)特征進(jìn)行群搜索，在加快處理時間的同時提高了分析精度，但并未完全解決粒子群算法的局部最優(yōu)問題[4-7]。針對數(shù)據(jù)分類問題，部分文獻(xiàn)提出了基于在線打包集成的高效分類器，通過在訓(xùn)練實(shí)例上引入在線重采樣機(jī)制和基于糾錯輸出碼的魯棒編碼方法，減少了分類器之間相關(guān)性的影響，同時采用基于分類性能的動態(tài)更新模型減少不必要的更新操作，提高了分類效率。然而，并未解決分類精度與數(shù)據(jù)規(guī)模的矛盾，在分類精確性上仍需改進(jìn)[8-11]。

為了有效提高數(shù)據(jù)選擇與分類算法的速度與精度，在借鑒已有方法的基礎(chǔ)上，提出基于慣性權(quán)重正交反向?qū)W習(xí)(orthogonal opposition learning，OOL)——螢火蟲算法(firefly algorithm，F(xiàn)A)的數(shù)據(jù)特征選擇算法：利用螢火蟲算法實(shí)現(xiàn)數(shù)據(jù)特征的全局尋優(yōu)，通過引入慣性權(quán)重來提高收斂速度，借助正交反向?qū)W習(xí)來提高選擇精度，從而在特征選擇過程的速度與精度上實(shí)現(xiàn)有效權(quán)衡。在此基礎(chǔ)上，提出基于結(jié)構(gòu)感知卷積神經(jīng)網(wǎng)絡(luò)(structure-aware convolutional neural network，SACNN)算法的數(shù)據(jù)分類方法，利用SACNN較強(qiáng)的非線性學(xué)習(xí)能力實(shí)現(xiàn)大數(shù)據(jù)的精準(zhǔn)分類。在Spark框架下對所提方法進(jìn)行實(shí)驗(yàn)分析，結(jié)果驗(yàn)證了所提方法的有效性和優(yōu)越性。

1 利用IWOF算法的大數(shù)據(jù)特征選擇

高維數(shù)據(jù)特征選擇的目標(biāo)是通過尋找特征最小子集來建立精確的數(shù)據(jù)預(yù)測模型。隨著數(shù)據(jù)維數(shù)的指數(shù)級增長，現(xiàn)有的批量學(xué)習(xí)[12]和在線學(xué)習(xí)[13]方法已經(jīng)很難滿足特征選擇對于快速性和可伸縮性的要求。為了解決這一問題，提出一種融合正交反向?qū)W習(xí)和螢火蟲算法的新型數(shù)據(jù)特征選擇算法，并利用慣性權(quán)重技術(shù)提升算法的收斂速度。首先，在映射階段將原始大數(shù)據(jù)集分解為數(shù)據(jù)塊；其次，基于正交反向?qū)W習(xí)和螢火蟲算法選擇大數(shù)據(jù)集特征；最后，將得到的部分結(jié)果合并到歸約階段的最終特征向量中。

1.1 問題描述

(1)

為了在實(shí)現(xiàn)在線數(shù)據(jù)特征選擇的同時盡可能地減小選擇錯誤，考慮

(2)

1.2 MapReduce概述

MapReduce[14]是在大數(shù)據(jù)處理中應(yīng)用最廣泛的編程范式之一，是計算機(jī)集群化應(yīng)用中的重要技術(shù)手段。MapReduce分為兩個階段：映射和歸約。映射階段的作用是對輸入數(shù)據(jù)集進(jìn)行處理，得到一些中間結(jié)果，并對這些結(jié)果進(jìn)行合并，以便在歸約階段生成最終的輸出。

MapReduce模式依賴于一個基本數(shù)據(jù)結(jié)構(gòu)，其定義為

k,v

(3)

map(k1,v1)→{(k2,v2),…,(kn,vn)}

(4)

reduce(k2,v2)→(k2,v3)

(5)

圖1描述了MapReduce的流程圖。

圖1 映射歸約MapReduce模式流程

1.3 基于慣性權(quán)重OOL-FA算法的特征選擇

螢火蟲算法(FA)全局搜索能力強(qiáng)，可用于求解多目標(biāo)優(yōu)化問題[15]。為了彌補(bǔ)FA算法在局部搜索能力和收斂速度上的不足，將正交反向?qū)W習(xí)(orthogonal opposition learning，OOL)引入FA，以深入挖掘并保存?zhèn)€體和反向個體中的有用信息。由此形成了一種新的啟發(fā)式特征選擇算法，即混合多目標(biāo)OOL-FA算法，即IWOF。

在具體介紹IWOF算法之前，需要先對經(jīng)映射、規(guī)約后的數(shù)據(jù)進(jìn)行編碼和初始化，以形成可供IWOF算法使用的輸入數(shù)據(jù)。

1.3.1 編碼與初始化

編碼方法：反映大數(shù)據(jù)集樣本矩陣特征的編碼方法可以充分保證啟發(fā)式算法的性能。采用的編碼技術(shù)由兩部分組成，首先是原始大數(shù)據(jù)集樣本矩陣的映射。Mapij矩陣表示大數(shù)據(jù)集樣本矩陣Map的對角線。TempMap表示臨時大數(shù)據(jù)集樣本矩陣，TempMapij表示矩陣對角線，通過該矩陣的每一行顯示與該行對應(yīng)的機(jī)器上的數(shù)據(jù)集樣本序列，而矩陣的每一列都顯示大數(shù)據(jù)集樣本分類或預(yù)測過程中特征的總和。

初始化：大數(shù)據(jù)集樣本矩陣Map對角線上的每個單元格取100，即Mapij=100，表示每個數(shù)據(jù)中心都在內(nèi)部維護(hù)其100%的特性選擇。

1.3.2 基于螢火蟲算法的最優(yōu)特征集選擇

在上述編碼方案的基礎(chǔ)上，利用小鄰域結(jié)構(gòu)和大鄰域結(jié)構(gòu)兩種不同的鄰域搜索結(jié)構(gòu)來尋找最優(yōu)特征集。在建立第一個搜索結(jié)構(gòu)的鄰域的同時，利用螢火蟲算法的移動算子選擇下一個最優(yōu)特征集。此外，為了建立第二個搜索結(jié)構(gòu)的鄰域，在特征選擇問題中引入交換、插入、逆3個常用運(yùn)算符。通過左移操作符，將特性集中的臨時特性Ftemp移動到當(dāng)前特性集中Fcurrent。在螢火蟲算法中，通過后續(xù)關(guān)系確定最優(yōu)特征i向最具吸引力(或更亮)的另一個特征j的方向運(yùn)動，其變化過程描述為

(6)

利用笛卡爾距離計算方法，可以得到兩個螢火蟲i和j之間的距離

(7)

式中：xik為第i個螢火蟲的第k個組成部分。

通過計算兩個特征矩陣之間的距離，即可得到TempMap，然后就可以利用分類指標(biāo)(查全率、精確度、準(zhǔn)確度)計算新的適應(yīng)度值。一般來說，準(zhǔn)確度是指正樣例和負(fù)樣例的總量占總數(shù)據(jù)量的比例，適應(yīng)度值的計算方法為

(8)

式中：TP為正樣例，F(xiàn)N為漏報，TN為負(fù)樣例，F(xiàn)P為誤報，η為適應(yīng)度值。

更新過程為：如果新的適應(yīng)度值低于當(dāng)前適應(yīng)度值，則固定新的位置，且初始Fcurrent被更新為與當(dāng)前特征矩陣Ftemp等價；否則(即Fcurrent≥Ftemp,F∈[0,1])，在區(qū)間[0,1]內(nèi)產(chǎn)生隨機(jī)數(shù)r，當(dāng)r

為了建立第二搜索結(jié)構(gòu)的鄰域，對經(jīng)典的插入算子和逆算子進(jìn)行了改進(jìn)。在這些運(yùn)算符中，首先，隨機(jī)選擇一個特征矩陣，并使用相應(yīng)的數(shù)據(jù)集矩陣；然后，在相同的概率下，考慮數(shù)據(jù)集樣本，并在選定的特征集上實(shí)現(xiàn)算子。在交換運(yùn)算符的情況下，隨機(jī)選擇兩個位置，并相對于所有數(shù)據(jù)集樣本，將兩個現(xiàn)有數(shù)據(jù)集樣本特征矩陣的位置互換；對于插入運(yùn)算符，隨機(jī)選擇一個特征和一個位置，并將所選特征插入整個數(shù)據(jù)集矩陣中所選的位置；在逆算子的情況下，隨機(jī)選擇序列的兩個點(diǎn)，并將這兩個特征之間的數(shù)據(jù)中心位置反演到整個數(shù)據(jù)集矩陣中；如果r≥F，則否定該解。在每個迭代過程中，算法從數(shù)據(jù)集樣本矩陣、映射中任意選擇一行和一列，并臨時將選擇的單元格設(shè)置為零(如果對角線上沒有相等的單元格)。

1.3.3 螢火蟲算法的改進(jìn)

為了提高螢火蟲算法的收斂速度，引入慣性權(quán)重算法。此外，為了解決螢火蟲算法的收斂精度，引入正交反向?qū)W習(xí)算法。通過上述算法的改進(jìn)，即實(shí)現(xiàn)了螢火蟲算法在尋優(yōu)、速度和精度上的綜合優(yōu)化。

為了改善螢火蟲算法的收斂速度，需要在螢火蟲位置更新公式中引入慣性權(quán)重，其表達(dá)式為

(9)

式中：w為慣性權(quán)重。

為了避免陷入局部最優(yōu)，需要對w進(jìn)行如下設(shè)計

(10)

式中：l為實(shí)時迭代次數(shù)，L為迭代次數(shù)最大值。由上式可知，當(dāng)l<0.5L時，w取值較大，由于ε為均勻分布的隨機(jī)數(shù)，因此w服從較大的均勻分布；反之，w服從較大的均勻分布。

反向?qū)W習(xí)的核心思想是同時評估當(dāng)前點(diǎn)和其反向點(diǎn)，擇優(yōu)使用，以此來提高搜索精度，反向?qū)W習(xí)的基本定義見文獻(xiàn)[15]。

為了充分利用群體搜索信息，需要借助重心反向，并以群體重心為參考點(diǎn)計算反向點(diǎn)，具體定義如下。

定義1 設(shè)di∈R是帶有單位質(zhì)量的點(diǎn)，i=1,…,K，則K個點(diǎn)的重心Gj定義為

(11)

(12)

G為反向點(diǎn)重心，基于正交表的正交反向?qū)W習(xí)算法的具體算法流程見文獻(xiàn)[15]，此處不再贅述。

1.3.4 并行化IWOF算法

利用MapReduce模型實(shí)現(xiàn)IWOF算法的并行化。假設(shè)T是一個訓(xùn)練集，m是映射任務(wù)的數(shù)量。首先，映射歸約分割方法將T分割成m個不相交的實(shí)例子集。其次，每個子集Ti，i∈{1,…,m}由等價映射函數(shù)處理，由于這個分區(qū)是依次執(zhí)行的，每個子集的實(shí)例數(shù)量大致相同，因此T文件的隨機(jī)化保證了類的平衡。

特征選擇算法包含每個Ti的映射階段，因此二元向量si={si1,…,}表示IWOF算法選擇了哪些特征。每一個二進(jìn)制向量在歸約階段取平均值，得到一個式(13)所定義的向量x，其中xj被稱為在線特征選擇應(yīng)用程序在其結(jié)果中包含特征j的比率，該向量被稱為完整在線特征選擇學(xué)習(xí)的結(jié)果，用于構(gòu)造用于附加機(jī)器學(xué)習(xí)原則的縮減數(shù)據(jù)集

(13)

式中：N為特征數(shù)量。

為了在計算特征向量x時以可伸縮的方式盡快從原始數(shù)據(jù)集中消除不重要的特征，需要采用映射歸約模式。通過閾值θ實(shí)現(xiàn)矢量x的二值化，即

S={s1,…,sN}

(14)

(15)

式中：S為簡化數(shù)據(jù)集選擇的特性向量。

1.3.5 IWOF算法流程

(1) 輸入特征F從原始數(shù)據(jù)集X=(x1j,…,xnj)；

(2) 計算適應(yīng)度函數(shù)f(x)，其等于分類精度

(3) 從數(shù)據(jù)集樣本中生成螢火蟲初始種群

xi,(i=1,2,…,n)(n=100)

(4) 利用適應(yīng)度函數(shù)f(x)確定xi處的光強(qiáng)li；

(5) 定義光吸收系數(shù)γ：

(6) Whilet<100

(7) Fori=1：n

(8) Forj=1：i

(9) If (Ij>Ii) && (Fcurrent≥Ftemp)

螢火蟲I在d維方向上沿j方向前進(jìn)；

吸引力隨距離r通過e-γr發(fā)散；

(10) Else 執(zhí)行交換、插入和逆運(yùn)算符；

(11) 轉(zhuǎn)到步驟(9)；

(12) End Forj；

(13) End Fori；

(14)對螢火蟲進(jìn)行分類并定位當(dāng)前的適應(yīng)度值；

(15)如果某些特性直到t小于最大進(jìn)化代數(shù)時才被選中

執(zhí)行正交反向?qū)W習(xí)

(16) End While；

(17) 處理結(jié)果和可視化。

2 利用SACNN的數(shù)據(jù)分類

傳統(tǒng)的分類算法難以處理大量的數(shù)據(jù)。因此，采用IWOF算法進(jìn)行在線特征選擇，然后選擇分類器對所得特征進(jìn)行分類。卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network，CNN)分類精度高，是一種應(yīng)用十分廣泛的深度神經(jīng)網(wǎng)絡(luò)。它的權(quán)值共享網(wǎng)絡(luò)結(jié)構(gòu)使之更類似于生物神經(jīng)網(wǎng)絡(luò)，降低了網(wǎng)絡(luò)模型的復(fù)雜度，減少了權(quán)值的數(shù)量。

經(jīng)典的CNN算法以較小的計算量對數(shù)據(jù)進(jìn)行學(xué)習(xí)，具有穩(wěn)定的學(xué)習(xí)效果，但其非線性處理能力較弱，因此在處理復(fù)雜數(shù)據(jù)時能力稍顯不足。

針對CNN存在的問題，選擇圖2所示的結(jié)構(gòu)感知卷積神經(jīng)網(wǎng)絡(luò)[18]算法實(shí)現(xiàn)特征數(shù)據(jù)的精確分類。圖中：x∈Rn×c為輸入，y∈Rn為輸出，f(·)為功能濾波器，rji為第j個頂點(diǎn)與第i個頂點(diǎn)之間的關(guān)系值，M∈Rc×c為衡量局部頂點(diǎn)之間關(guān)系的矢量矩陣，T(·)為tanh函數(shù)，xj、xi代表輸入x的第j行、第i行的行向量。

圖2 SACNN結(jié)構(gòu)

SACNN的輸出為

(16)

式中：εji代表第i個頂點(diǎn)的第j個臨近點(diǎn)；E為這些點(diǎn)組成的集合；hk(·)為切比雪夫多項式；vk為多項式中的系數(shù)；K為多項式的階數(shù)。

通過將傳統(tǒng)CNN中的卷積運(yùn)算替換為結(jié)構(gòu)識別卷積運(yùn)算，使得SACNN具有非常高的模型學(xué)習(xí)能力。當(dāng)將其應(yīng)用到數(shù)據(jù)分類中時，可以充分發(fā)揮其精確建模能力。圖2給出了SACNN應(yīng)用的關(guān)鍵步驟及對應(yīng)的算法，即：將數(shù)據(jù)集輸入SACNN后，先計算這些數(shù)據(jù)之間的關(guān)系值，然后再對這些關(guān)系值進(jìn)行濾波處理，最后再利用輸入數(shù)據(jù)和濾波后的關(guān)系值計算最終的輸出值。

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

在Spark框架下，為了檢驗(yàn)IWOF算法的有效性，使用二分類數(shù)據(jù)集進(jìn)行數(shù)據(jù)特征選擇與分類實(shí)驗(yàn)。數(shù)據(jù)集選為包含2000個數(shù)值特征的，數(shù)據(jù)量為50萬個樣本集合的Epsilon。此外，包含631個特征，數(shù)據(jù)量為6600萬個樣本的ECBDL14數(shù)據(jù)集。表1概述了這些數(shù)據(jù)集的主要特征。除了屬性的數(shù)量外，用于訓(xùn)練和測試集的樣本數(shù)量也在驗(yàn)證IWOF算法時進(jìn)行了描述。在數(shù)據(jù)樣本中，75%的樣本用于培訓(xùn)，25%的樣本用于測試。

表1 數(shù)據(jù)集概述

在應(yīng)用映射歸約模式支持的IWOF算法后，在上述數(shù)據(jù)集上，分別使用Spark中實(shí)現(xiàn)的SACNN、文獻(xiàn)[9]和文獻(xiàn)[10]這3種不同的分類算法對數(shù)據(jù)集進(jìn)行分類實(shí)驗(yàn)驗(yàn)證。

3.1 評估指標(biāo)

在處理分類問題時，必須將一個類標(biāo)記為正類，另一個類標(biāo)記為負(fù)類，分別考慮p個陽性樣本和n個陰性樣本的測試集。任何分類器的任務(wù)都是為每個樣本分配一個類，此外，某些任務(wù)可能是不正確的。為了評估分類器的性能，在正樣例、負(fù)樣例、誤報和漏報樣品的基礎(chǔ)上，統(tǒng)計并設(shè)計了一個融合矩陣，見表2。

表2 融合矩陣

利用表2可以推導(dǎo)出用于不平衡學(xué)習(xí)的性能指標(biāo)，包括：精度P、查全率R、測度FM和幾何平均GM，如下所示：

(1)精度P定義為檢索到的相關(guān)實(shí)例的百分比，其表達(dá)式為

(2)查全率R定義為檢索到的相關(guān)實(shí)例的比例，其表達(dá)式為

(3)測度FM定義為準(zhǔn)確度與查全率相結(jié)合的測度，即準(zhǔn)確度與查全率的調(diào)和平均值，其表達(dá)式為

(4)幾何平均GM用來評估不平衡數(shù)據(jù)集上的分類器，幾何平均指定了主流和少數(shù)類的分類性能之間的平衡，該指標(biāo)考慮了敏感性和特異性，敏感性即為查全率，特異性SP和幾何平均的表達(dá)式分別為

3.2 與其它方法的對比和分析

圖3給出了3種分類算法在實(shí)驗(yàn)數(shù)據(jù)集分類實(shí)驗(yàn)中的精度和查全率結(jié)果。與文獻(xiàn)[9]和文獻(xiàn)[10]中的兩類分類算法相比，提出的基于IWOF算法的SACNN分類算法的分類精度是最高的，其準(zhǔn)確率約為94%，與文獻(xiàn)[9]和文獻(xiàn)[10]相比，提出的SACNN分類算法的準(zhǔn)確率分別提高了5%和8%。由此可見，提出的算法很好地解決了高維數(shù)據(jù)集問題，這表明所采用的映射歸約模式解決了并行處理的需求。然而，在查全率方面，提出的基于IWOF的SACNN分類算法雖然高于文獻(xiàn)[9]，但明顯低于文獻(xiàn)[10]，這表明所提算法很難保證數(shù)據(jù)的學(xué)習(xí)覆蓋率，即其在算法的通用性方面略差于文獻(xiàn)[10]。

圖3 3種分類算法的精度與查全率對比

圖4給出了3種分類算法在實(shí)驗(yàn)數(shù)據(jù)集分類實(shí)驗(yàn)中的測度和幾何平均結(jié)果。與文獻(xiàn)[9]和文獻(xiàn)[10]中的兩類分類算法相比，提出的基于IWOF算法的SACNN分類算法的測度和幾何平均結(jié)果均是最大的，這表明所提算法在大數(shù)據(jù)分類中的平均化性能指標(biāo)方面具有明顯的優(yōu)勢，且所提算法在收斂精度上高于文獻(xiàn)[9]，但略低于文獻(xiàn)[10]。

圖4 3種分類算法的測度與幾何平均對比

圖5給出了3種分類算法在實(shí)驗(yàn)數(shù)據(jù)集分類實(shí)驗(yàn)中的準(zhǔn)確率和錯誤率結(jié)果。與文獻(xiàn)[9]和文獻(xiàn)[10]中的兩類分類算法相比，提出的基于IWOF算法的SACNN分類算法的精度是最高的，相應(yīng)的其錯誤率則是三者中最低的。由此可見，提出的分類算法的分類準(zhǔn)確率是可以得到充分保證的。

圖5 3種分類算法的準(zhǔn)確率和錯誤率對比

表3給出了以上3個實(shí)驗(yàn)的具體指標(biāo)。

表3 不同分類器的評價指標(biāo)%

為了進(jìn)一步驗(yàn)證所提算法與文獻(xiàn)[9]、文獻(xiàn)[10]中的分類算法在大數(shù)據(jù)分類速度上的對比結(jié)果，圖6給出了大數(shù)據(jù)集的訓(xùn)練運(yùn)行時間，訓(xùn)練運(yùn)行時間定義為用于訓(xùn)練或構(gòu)造分類器的時間(以秒為單位)。

圖6顯示了針對3個不同分類器繪制的訓(xùn)練運(yùn)行時間比較結(jié)果。文獻(xiàn)[9]和文獻(xiàn)[10]中的兩類分類算法相比，提出的基于IWOF算法的SACNN分類算法的訓(xùn)練運(yùn)行時間并不是最低的，即提出的IWOF算法的收斂速度介于文獻(xiàn)[9]、文獻(xiàn)[10]中的算法之間。由此可見，本文所提算法是以犧牲一部分快速性來換取分類準(zhǔn)確率的。

圖6 3種分類算法的訓(xùn)練運(yùn)行時間對比

4 結(jié)束語

高維數(shù)據(jù)的特征選擇與分類對于很多實(shí)際的工程問題來說非常重要，提出一種基于慣性權(quán)重OOL-FA算法的大數(shù)據(jù)特征選擇算法，在此基礎(chǔ)上利用SACNN算法實(shí)現(xiàn)了大數(shù)據(jù)的精確分類。在實(shí)際數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)結(jié)果表明了所提算法在準(zhǔn)確率、測度、幾何平均等方面的優(yōu)越性。但實(shí)驗(yàn)結(jié)果也表明，所提大數(shù)據(jù)分類算法在動態(tài)性能和查全率上并不是最優(yōu)的，這說明所提算法還有一定的提升空間。下一步的研究應(yīng)該在保證分類精度的基礎(chǔ)上，進(jìn)一步提升分類算法的快速性。