利用并行慣性權重OOL-FA的大數據分類

鐘章生，陳世爐，陳志龍

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

0 引 言

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

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

為了有效提高數據選擇與分類算法的速度與精度，在借鑒已有方法的基礎上，提出基于慣性權重正交反向學習(orthogonal opposition learning，OOL)——螢火蟲算法(firefly algorithm，FA)的數據特征選擇算法：利用螢火蟲算法實現數據特征的全局尋優，通過引入慣性權重來提高收斂速度，借助正交反向學習來提高選擇精度，從而在特征選擇過程的速度與精度上實現有效權衡。在此基礎上，提出基于結構感知卷積神經網絡(structure-aware convolutional neural network，SACNN)算法的數據分類方法，利用SACNN較強的非線性學習能力實現大數據的精準分類。在Spark框架下對所提方法進行實驗分析，結果驗證了所提方法的有效性和優越性。

1 利用IWOF算法的大數據特征選擇

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

1.1 問題描述

(1)

為了在實現在線數據特征選擇的同時盡可能地減小選擇錯誤，考慮

(2)

1.2 MapReduce概述

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

MapReduce模式依賴于一個基本數據結構，其定義為

k,v

(3)

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

(4)

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

(5)

圖1描述了MapReduce的流程圖。

圖1 映射歸約MapReduce模式流程

1.3 基于慣性權重OOL-FA算法的特征選擇

螢火蟲算法(FA)全局搜索能力強，可用于求解多目標優化問題[15]。為了彌補FA算法在局部搜索能力和收斂速度上的不足，將正交反向學習(orthogonal opposition learning，OOL)引入FA，以深入挖掘并保存個體和反向個體中的有用信息。由此形成了一種新的啟發式特征選擇算法，即混合多目標OOL-FA算法，即IWOF。

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

1.3.1 編碼與初始化

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

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

1.3.2 基于螢火蟲算法的最優特征集選擇

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

(6)

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

(7)

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

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

(8)

式中：TP為正樣例，FN為漏報，TN為負樣例，FP為誤報，η為適應度值。

更新過程為：如果新的適應度值低于當前適應度值，則固定新的位置，且初始Fcurrent被更新為與當前特征矩陣Ftemp等價；否則(即Fcurrent≥Ftemp,F∈[0,1])，在區間[0,1]內產生隨機數r，當r

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

1.3.3 螢火蟲算法的改進

為了提高螢火蟲算法的收斂速度，引入慣性權重算法。此外，為了解決螢火蟲算法的收斂精度，引入正交反向學習算法。通過上述算法的改進，即實現了螢火蟲算法在尋優、速度和精度上的綜合優化。

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

(9)

式中：w為慣性權重。

為了避免陷入局部最優，需要對w進行如下設計

(10)

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

反向學習的核心思想是同時評估當前點和其反向點，擇優使用，以此來提高搜索精度，反向學習的基本定義見文獻[15]。

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

定義1 設di∈R是帶有單位質量的點，i=1,…,K，則K個點的重心Gj定義為

(11)

(12)

G為反向點重心，基于正交表的正交反向學習算法的具體算法流程見文獻[15]，此處不再贅述。

1.3.4 并行化IWOF算法

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

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

(13)

式中：N為特征數量。

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

S={s1,…,sN}

(14)

(15)

式中：S為簡化數據集選擇的特性向量。

1.3.5 IWOF算法流程

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

(2) 計算適應度函數f(x)，其等于分類精度

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

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

(4) 利用適應度函數f(x)確定xi處的光強li；

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

(6) Whilet<100

(7) Fori=1：n

(8) Forj=1：i

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

螢火蟲I在d維方向上沿j方向前進；

吸引力隨距離r通過e-γr發散；

(10) Else 執行交換、插入和逆運算符；

(11) 轉到步驟(9)；

(12) End Forj；

(13) End Fori；

(14)對螢火蟲進行分類并定位當前的適應度值；

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

執行正交反向學習

(16) End While；

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

2 利用SACNN的數據分類

傳統的分類算法難以處理大量的數據。因此，采用IWOF算法進行在線特征選擇，然后選擇分類器對所得特征進行分類。卷積神經網絡(convolutional neural network，CNN)分類精度高，是一種應用十分廣泛的深度神經網絡。它的權值共享網絡結構使之更類似于生物神經網絡，降低了網絡模型的復雜度，減少了權值的數量。

經典的CNN算法以較小的計算量對數據進行學習，具有穩定的學習效果，但其非線性處理能力較弱，因此在處理復雜數據時能力稍顯不足。

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

圖2 SACNN結構

SACNN的輸出為

(16)

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

通過將傳統CNN中的卷積運算替換為結構識別卷積運算，使得SACNN具有非常高的模型學習能力。當將其應用到數據分類中時，可以充分發揮其精確建模能力。圖2給出了SACNN應用的關鍵步驟及對應的算法，即：將數據集輸入SACNN后，先計算這些數據之間的關系值，然后再對這些關系值進行濾波處理，最后再利用輸入數據和濾波后的關系值計算最終的輸出值。

3 實驗結果與分析

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

表1 數據集概述

在應用映射歸約模式支持的IWOF算法后，在上述數據集上，分別使用Spark中實現的SACNN、文獻[9]和文獻[10]這3種不同的分類算法對數據集進行分類實驗驗證。

3.1 評估指標

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

表2 融合矩陣

利用表2可以推導出用于不平衡學習的性能指標，包括：精度P、查全率R、測度FM和幾何平均GM，如下所示：

(1)精度P定義為檢索到的相關實例的百分比，其表達式為

(2)查全率R定義為檢索到的相關實例的比例，其表達式為

(3)測度FM定義為準確度與查全率相結合的測度，即準確度與查全率的調和平均值，其表達式為

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

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

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

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

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

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

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

圖5 3種分類算法的準確率和錯誤率對比

表3給出了以上3個實驗的具體指標。

表3 不同分類器的評價指標%

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

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

圖6 3種分類算法的訓練運行時間對比

4 結束語

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