范大鵬, 張鳳斌

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

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

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

1 相關(guān)工作

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

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

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

2 背景和算法

2.1 Spark并行框架

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

2.2 免疫網(wǎng)絡(luò)

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

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

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

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

③ 克隆選擇,計(jì)算變異后的每個(gè)個(gè)體同抗原的適應(yīng)度,選擇適應(yīng)度高的個(gè)體進(jìn)行抑制,將抑制后的個(gè)體加入記憶細(xì)胞集合中.

④ 對記憶細(xì)胞集進(jìn)行網(wǎng)絡(luò)抑制,構(gòu)建新的網(wǎng)絡(luò),形成新的記憶細(xì)胞集.

⑤ 重復(fù)步驟①-③,直到每個(gè)抗原都提呈完畢,最后形成記憶細(xì)胞.

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

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

鑒于Ainet算法串行化的特點(diǎn),將抗原進(jìn)化過程中前1個(gè)抗原與后1個(gè)抗原之間的依賴關(guān)系取消,換成每個(gè)抗原在每個(gè)并行運(yùn)行機(jī)器中獨(dú)立進(jìn)化,當(dāng)每個(gè)獨(dú)立運(yùn)行機(jī)器中所有抗原進(jìn)化完畢后再進(jìn)行獨(dú)立的群體抑制.這樣可以大大加快Ainet的進(jìn)化速度,同時(shí)也可減少不必要的抑制過程,降低Ainet的群體之間的依賴性.

3.1 模 型

針對于分類問題[15-16],首先設(shè)計(jì)訓(xùn)練模型,表達(dá)式為

(1)

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

分類模型表達(dá)式為

(2)

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

3.2 Spark訓(xùn)練算法

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

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

輸出:M為訓(xùn)練結(jié)果集合.

訓(xùn)練步驟如下:

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

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

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

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

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

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

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

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

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

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

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

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

從train算法可見,第3)步是區(qū)別于串行Ainet的關(guān)鍵步驟,① 到⑥ 步就是Ainet算法的集群實(shí)現(xiàn),在集群中的每個(gè)機(jī)器中獨(dú)立運(yùn)行Ainet算法.

3.3 Spark分類算法

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

輸入:M為訓(xùn)練后的記憶集.

輸出:out為分類結(jié)果集合.

分類步驟如下:

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

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

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

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

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

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

3)reduce(labeli)→C,將Test每個(gè)數(shù)據(jù)項(xiàng)結(jié)果合并.

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

4 試 驗(yàn)

試驗(yàn)環(huán)境為DELL R720服務(wù)器、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,訓(xùn)練集為196 915,初始記憶集為1 949.并行免疫網(wǎng)絡(luò)參數(shù)設(shè)置如下:運(yùn)行代數(shù)為G=3;克隆速率為Cr=10;選擇的克隆變異百分比為Dm=0.01;記憶細(xì)胞集合m中成員的清除閥值為Dr=5.0;記憶細(xì)胞集合m中成員的抑制閥值為Dd=0.1.

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

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

表1 串行和并行Ainet比較

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

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

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

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

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

4.3 不同算法比較

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

不同算法比較結(jié)果如表3所示.

表3 不同算法比較

從表3可見,準(zhǔn)確率、檢測率和誤報(bào)率3個(gè)指標(biāo)并行Ainet算法都好于其他算法,而運(yùn)行時(shí)間并行Ainet要遠(yuǎn)遠(yuǎn)高于其他算法.

5 結(jié) 論

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