范大鵬, 張鳳斌

(1. 哈爾濱理工大學 計算機科學與技術學院, 黑龍江 哈爾濱 150080; 2. 黑龍江科技大學 計算機與信息工程學院, 黑龍江 哈爾濱 150022)

現(xiàn)今已經(jīng)進入了大數(shù)據(jù)時代,每天都會產(chǎn)生數(shù)PB的數(shù)據(jù)[1],如何挖掘大數(shù)據(jù)的內(nèi)在價值,成為大數(shù)據(jù)處理的研究熱點.由于大數(shù)據(jù)具有復雜、高維、多變等特性,如何從真實、凌亂、無模式和復雜的大數(shù)據(jù)中挖掘出人類感興趣的知識,迫切需要更深刻的機器學習理論進行指導.人工免疫作為機器學習的重要方法,能快速準確識別“自體”和“非自體”,為數(shù)據(jù)分類提供了一種有效的途徑.而作為人工免疫理論中的免疫網(wǎng)絡理論認為免疫細胞不僅受外來抗原的刺激, 抗體之間也要相互刺激和彼此協(xié)調(diào)形成一個動態(tài)的免疫網(wǎng)絡用以完成免疫功能,進而體現(xiàn)出免疫系統(tǒng)的動態(tài)性能[2].但免疫網(wǎng)絡存在收斂速度慢、訓練時間長等缺點,所以傳統(tǒng)的串行免疫網(wǎng)絡理論并不適合大數(shù)據(jù)處理.

文中借鑒免疫網(wǎng)絡理論,改進Ainet算法,設計免疫網(wǎng)絡訓練和分類模型,提出Spark[3]并行框架下并行免疫算法(P-Ainet),并將該模型應用到入侵檢測數(shù)據(jù)集分類中,以提高分類[4]的各項性能.

1 相關工作

免疫網(wǎng)絡分類方面的研究已經(jīng)有很多,其中比較有代表性的楊珺等[5]提出了基于人工免疫網(wǎng)絡聚類的過濾網(wǎng)絡取證數(shù)據(jù)的方法;張立文等[6]采用Ainet提出了2階段文本聚類算法TCBSA;DENG Z. L.等[7]設計了信用評分模型,采用免疫網(wǎng)絡算法,提高了系統(tǒng)的非線性;DENG Z. L.等[8]提出了基于免疫網(wǎng)絡的動態(tài)識別相鄰節(jié)點劃分方法.

并行免疫網(wǎng)絡的相關研究較少,而莫宏偉和徐立芳[9]都是最早研究并行免疫網(wǎng)絡的學者之一,將簡單的并行方法引入AIRS系統(tǒng),驗證了并行多核系統(tǒng)效率方面的優(yōu)越性能;蘇一丹等[10]提出了保持鄰居用戶最大多樣性的基礎上進一步提高算法實時響應速度的PINR算法;LUO R. Y.等[11]改進Ainet算法設計了一種集群優(yōu)化GPU算法.

將并行免疫算法應用于大數(shù)據(jù)分類中的研究目前還很少見,而且采用Spark并行框架實現(xiàn)并行免疫網(wǎng)絡尚未被相關的論文提及.

2 背景和算法

2.1 Spark并行框架

Spark是現(xiàn)代大數(shù)據(jù)并行處理框架之一,是以內(nèi)存計算為核心的并行計算框架,其運算速度比硬盤計算快10倍.Spark以RDD[12]作為核心數(shù)據(jù)結構,RDD以分區(qū)(patition)的形式分布在集群中的多個機器上,每個分區(qū)代表了數(shù)據(jù)集的1個子集;分區(qū)定義了Spark中數(shù)據(jù)的并行單位,Spark框架并行處理多個分區(qū),一個分區(qū)內(nèi)的數(shù)據(jù)對象是以順序處理的方式存在;RDD的抽象使得開發(fā)人員將流水處理過程中的任何點過程,映射到跨越集群節(jié)點的內(nèi)存中,極大地提高了內(nèi)存計算能力.Spark通過map和mapPatitions操作函數(shù)控制訪問分區(qū),對分區(qū)中數(shù)據(jù)的操作在分區(qū)之間并行完成,所以分區(qū)的多少直接影響Spark執(zhí)行的效率,同時加大分區(qū)的數(shù)量可以提高算法的并行效率[13-14].

2.2 免疫網(wǎng)絡

免疫網(wǎng)絡(Ainet)算法步驟可概括如下:

1) 初始化,隨機選擇少量數(shù)據(jù)以形成記憶細胞集合.

2) 抗原提呈,該過程將每個抗原做如下操作:

① 克隆,采用適應度計算方法,計算每個抗原與記憶細胞的適應度,選擇最好的n1個個體進行克隆,克隆數(shù)量采用Nc=Cr*1/Af,式中:Cr為克隆率;Af為適應度;為向下取整函數(shù).

③ 克隆選擇,計算變異后的每個個體同抗原的適應度,選擇適應度高的個體進行抑制,將抑制后的個體加入記憶細胞集合中.

④ 對記憶細胞集進行網(wǎng)絡抑制,構建新的網(wǎng)絡,形成新的記憶細胞集.

⑤ 重復步驟①-③,直到每個抗原都提呈完畢,最后形成記憶細胞.

從Ainet算法可見,進化過程中每個抗原都要同記憶細胞集進行克隆選擇,每個抗體都要依賴于上一個抗體形成的記憶細胞,所以Ainet串行過程中數(shù)據(jù)間有很強的依賴關系,并不適合并行運算.

3 并行免疫網(wǎng)絡分類算法

鑒于Ainet算法串行化的特點,將抗原進化過程中前1個抗原與后1個抗原之間的依賴關系取消,換成每個抗原在每個并行運行機器中獨立進化,當每個獨立運行機器中所有抗原進化完畢后再進行獨立的群體抑制.這樣可以大大加快Ainet的進化速度,同時也可減少不必要的抑制過程,降低Ainet的群體之間的依賴性.

3.1 模 型

針對于分類問題[15-16],首先設計訓練模型,表達式為

(1)

式中:M為生成的記憶細胞;n為并行運行機器的數(shù)量;delect為網(wǎng)絡抑制操作;AINET為免疫網(wǎng)絡操作;Sk為第k個訓練抗原;Sσ為初始記憶集合;Dr為抑制閥值;Dd為網(wǎng)絡抑制閥值;Dm為克隆速率;n為并行集群的個數(shù);m為訓練集中數(shù)據(jù)項的個數(shù);g為進化的代數(shù).

分類模型表達式為

(2)

式中:aff()為適應度函數(shù);KNN()為最近鄰判斷函數(shù)[17];tj為每個待分類數(shù)據(jù)項;M為訓練后的記憶細胞集合;n為并行集群的個數(shù);m為M中數(shù)據(jù)項的個數(shù);t為測試集中數(shù)據(jù)項的個數(shù).

3.2 Spark訓練算法

Spark框架下并行免疫網(wǎng)絡訓練算法如下:

輸入:n為選擇要克隆的記憶細胞數(shù);G為運行代數(shù);Cr為克隆速率;Dm為選擇的克隆變異百分比;Ds為對記憶細胞集合m中成員的清除閥值;Dr為對記憶細胞集合m中成員的抑制閥值;IniTest為訓練過程中用到的訓練集;IniM為初始記憶集;maxmin為數(shù)據(jù)集中列的范圍;Test為測試集.

輸出:M為訓練結果集合.

訓練步驟如下:

1)sc.broadcast(IniM)→m,廣播初始記憶集;

2)m→IniTest.mapPartitions(),對訓練集中每個分區(qū)做如下操作:

①IniTest的分區(qū)中的每個數(shù)據(jù)項xi計算歐氏距離,計算distance(xi,m)→∑Di;

②clone(∑Di,n,Cr)→clonei,克隆操作;

③mute(clonei,maxmin)→mutei,變異操作;

④select(mutei)→selecti,選擇操作;

⑤delect(selecti,Ds)→delecti,抑制操作;

⑥delecti→Mi,生成xi的記憶集;

⑦ 重復步驟①-⑥,直到迭代完成;

⑧ ∑Mi→Pmk,k為每個分區(qū)的索引;

3)delect(Pmk)→PartitionsMk,對每個分區(qū)中的所有數(shù)據(jù)抑制計算;

4)reduce(PartitionsMk)→M,合并每個分區(qū),生成總的記憶集.

從train算法可見,第3)步是區(qū)別于串行Ainet的關鍵步驟,① 到⑥ 步就是Ainet算法的集群實現(xiàn),在集群中的每個機器中獨立運行Ainet算法.

3.3 Spark分類算法

Spark框架下并行免疫網(wǎng)絡分類(classification)算法如下所示:

輸入:M為訓練后的記憶集.

輸出:out為分類結果集合.

分類步驟如下:

1)sc.broadcast(M)→pM,廣播生成的記憶集到pM的每個分區(qū);

2)Test.map→xi,對每個分區(qū)上測試集中的每個數(shù)據(jù)項做如下操作:

①distance(xi,pM)→∑di,計算xi和pM每條數(shù)據(jù)項的歐式距離;

②sortby(∑di)→si,按歐氏距離大小排序;

③KNN(si)→labeli,判斷xi的類別;

④ 重復①-③,直到Test每個數(shù)據(jù)項都完成;

3)reduce(labeli)→C,將Test每個數(shù)據(jù)項結果合并.

在classification算法過程中,將訓練后的記憶集合以變量共享的方式廣播到每個集群中,在每個集群中分別檢測每個測試數(shù)據(jù),待集群中每個測試項都測試完畢,統(tǒng)計出分類結果.

4 試 驗

試驗環(huán)境為DELL R720服務器、windows server 2008r2系統(tǒng)、idea14.0.2和Spark1.6.0,數(shù)據(jù)采用kddcup99的10%數(shù)據(jù)集,數(shù)據(jù)量分布如下:總數(shù)據(jù)量為494 021,檢測集為297 106,訓練集為196 915,初始記憶集為1 949.并行免疫網(wǎng)絡參數(shù)設置如下:運行代數(shù)為G=3;克隆速率為Cr=10;選擇的克隆變異百分比為Dm=0.01;記憶細胞集合m中成員的清除閥值為Dr=5.0;記憶細胞集合m中成員的抑制閥值為Dd=0.1.

4.1 串行和并行免疫網(wǎng)絡算法比較

串行和并行Ainet算法比較如表1所示.

表1 串行和并行Ainet比較

從表1可見,并行Ainet算法(P-Ainet)訓練時間快12倍以上,檢測時間快近20倍;從生成記憶檢測器個數(shù)來看2種算法差的并不是很大;而準確率、檢測率和誤報率并行Ainet算法要遠遠高于串行Ainet算法.

4.2 訓練數(shù)據(jù)集大小的影響

選取不同數(shù)據(jù)量訓練集對結果的影響如表2所示,其中40%表示訓練集的數(shù)量占總數(shù)據(jù)量的比率,這時檢測集的數(shù)據(jù)量就占總數(shù)據(jù)量的60%,其他亦同.

表2 不同數(shù)量訓練集的影響

從表2可見,增大訓練集的比率時訓練時間和生成的記憶檢測器個數(shù)都相應增加,訓練數(shù)據(jù)量達到60%時訓練時間要比40%數(shù)據(jù)量時慢3倍,由于測試集數(shù)量的減少,檢測時間相對減少.同時準確率、檢測率和誤報率都會達到更好的效果,訓練數(shù)據(jù)量達到60%時較40%時準確率提高1.279 7%,檢測率提高3.687 7%,誤報率下降0.700 4%.

4.3 不同算法比較

選取Spark mllib中提供的分類算法進行比較,包括邏輯回歸(LR)、線性支持向量機(SVM)、樸素貝葉斯(Na?ve Bayes)和K均值(K-means)幾種算法,訓練選取了60%的數(shù)據(jù)量,預測選取了40%的數(shù)據(jù)量.

不同算法比較結果如表3所示.

表3 不同算法比較

從表3可見,準確率、檢測率和誤報率3個指標并行Ainet算法都好于其他算法,而運行時間并行Ainet要遠遠高于其他算法.

5 結 論

文中提出了面向大數(shù)據(jù)分類問題的并行免疫模型及算法,具有如下優(yōu)勢: ① 訓練數(shù)據(jù)集數(shù)量要求低,用少量的個體數(shù)量,可以達到97%以上的準確率; ② 采用集群獨立進化的思想,加快了進化的速度,克服了免疫網(wǎng)絡過分抑制的缺點; ③ 并行分類過程將記憶集共享,極大提高了集群分類效率.該算法劣勢包括: ① 算法計算量大,導致訓練和分類過程緩慢; ② 對訓練集數(shù)量敏感,訓練數(shù)量增加訓練效果較好,數(shù)量減少效果就差.