基于相似連接的多源數(shù)據(jù)并行預(yù)處理方法

郭方方 潮洛蒙 朱建文

摘 要：大規(guī)模網(wǎng)絡(luò)環(huán)境和大數(shù)據(jù)相關(guān)技術(shù)的發(fā)展對傳統(tǒng)數(shù)據(jù)融合分析技術(shù)提出了新的挑戰(zhàn)。針對目前多源數(shù)據(jù)融合分析過程靈活性差、處理效率低的問題，提出了一種基于相似連接的多源數(shù)據(jù)并行預(yù)處理方法，該方法采用了分治和并行的思想。首先，通過對多源數(shù)據(jù)中的相似語義進(jìn)行統(tǒng)一、對個性語義進(jìn)行保留的預(yù)處理方法提高了靈活性;其次，提出了一種改進(jìn)的并行MapReduce框架，提高了相似連接的效率。實驗結(jié)果表明，所提方法在保證數(shù)據(jù)完整性的基礎(chǔ)上，使總的數(shù)據(jù)量減小了32%。與傳統(tǒng)的MapReduce框架相比，改進(jìn)后的框架在耗費時間方面減小了43.91%，因此該方法可以有效提高多源數(shù)據(jù)融合分析的效率。

關(guān)鍵詞：網(wǎng)絡(luò)安全;多源數(shù)據(jù);數(shù)據(jù)預(yù)處理;相似連接;MapReduce

中圖分類號： TP274

文獻(xiàn)標(biāo)志碼：A

Abstract： With the development of large-scale network environments and big data-related technologies， traditional data fusion analysis technology faces new challenges. Focusing on poor flexibility and low processing efficiency in current multi-source data fusion analysis process， a multi-source data parallel preprocessing method based on similar connection was proposed， in which the idea of dividing and conquering and paralleling was adopted. Firstly， the preprocessing method was improved to increase the flexibility by unifying similar semantics in multi-source data and retaining personality semantics. Secondly， an improved parallel MapReduce framework was proposed to improve the efficiency of similar connections. The experimental results show that the proposed method reduces total data volume by 32% while ensuring data integrity. Compared with traditional MapReduce framework， the improved framework decreases 43.91% of time consumed; therefore， the proposed method can effectively improve the efficiency of multi-source data fusion analysis.

Key words： network security; multi-source data; data preprocessing; similar connection; MapReduce

0 引言

多源數(shù)據(jù)的預(yù)處理過程是網(wǎng)絡(luò)環(huán)境進(jìn)行安全分析的重要環(huán)節(jié)，根據(jù)實際的應(yīng)用采取相應(yīng)的具體措施[1]。一般性地，包括數(shù)據(jù)清理、數(shù)據(jù)格式轉(zhuǎn)換、數(shù)據(jù)簡約等過程。其中數(shù)據(jù)清洗作為一個重要的環(huán)節(jié)，通過按照一定規(guī)則篩選數(shù)據(jù)，去除數(shù)據(jù)中的冗余部分。好的數(shù)據(jù)清洗方法不僅能夠降低系統(tǒng)處理數(shù)據(jù)所需的時間，并且能夠提高數(shù)據(jù)分析結(jié)果的準(zhǔn)確度。

為了對數(shù)據(jù)源進(jìn)行靈活的數(shù)據(jù)清洗，盡量保留數(shù)據(jù)源的個性屬性，本文采用基于相似連接的數(shù)據(jù)清洗方法。相似連接在相似對象匹配問題中得到廣泛應(yīng)用，如互聯(lián)網(wǎng)、數(shù)據(jù)分析、數(shù)據(jù)庫等，匹配對象也日益多樣，如串、圖、字符串和集合等。為了適應(yīng)各種各樣的場景和對象，相似連接相關(guān)算法也得到了優(yōu)化和改進(jìn)。無論是基于單行串行數(shù)據(jù)還是集合數(shù)據(jù)，或是基于樹結(jié)構(gòu)還是圖結(jié)構(gòu)，優(yōu)化和改進(jìn)的方案主要以提高效率和靈活性或伸縮性為主。為了解決單行串行的相似連接候選集過多的問題，Li等[2]提出了一種基于劃分的傳遞性的相似連接，該相似連接的過程進(jìn)行的劃分，該方法在此句不通順，請修改相似匹配過程中利用傳遞性沒有使用全部子串，從而減少了匹配的候選集數(shù)目，提升了匹配的效率。為了提升算法的靈活性與伸縮性，Wang等[3]提出了一種快速相似連接算法，該算法既考慮到了相似的準(zhǔn)確度，又考慮到了相似連接屬性的模糊度，可以進(jìn)行靈活的篩選;然而隨著大數(shù)據(jù)與云計算等的出現(xiàn)，由于數(shù)據(jù)量的龐大導(dǎo)致算法效率低，這也是相似連接算法面臨的難題之一。

MapReduce作為一種并行框架，由于其擴(kuò)展性好、易實現(xiàn)等特點，被廣泛使用在數(shù)據(jù)并行處理中。陳一帆等[4]提出一種基于MapReduce的圖相似連接的處理方法，使用“過濾驗證”框架下的MGSJion與Bloom Filter相結(jié)合，并使用MapReduce框架提升了算法整體的效率。陳子軍等[5]提出基于MapReduce框架的相似連接算法，該算法應(yīng)用對象是空間文本，在MapReduce框架實現(xiàn)了相應(yīng)的劃分和裁剪工作，提升了算法效率;然而MapReduce框架在被普遍應(yīng)用的同時，MapReduce框架本身的缺點也顯現(xiàn)出來，如：迭代計算比較乏力，計算中產(chǎn)生的Mapper數(shù)量過多，裝載和卸載較頻繁等問題。據(jù)此，Bu等[6]提出一種HaLoop可擴(kuò)展框架，通過添加循環(huán)控制模塊來解決迭代乏力的問題。為了進(jìn)一步提升效率，Zhang等[7]提出一種基于內(nèi)存的iMapReduce框架，通過Map和Reduce階段長期駐留內(nèi)存和適時的中斷迭代次數(shù)來提升框架的計算效率;然而現(xiàn)有的基于內(nèi)存的框架處理方式比較粗糙，浪費內(nèi)存空間比較嚴(yán)重。

據(jù)此，為了提高數(shù)據(jù)清洗的效率，本文提出了一種基于相似連接的數(shù)據(jù)預(yù)處理方法，并且采用改進(jìn)的MapReduce框架實現(xiàn)該算法。該框架基于內(nèi)存的思想來提升框架的并行效率，能夠高效地完成相似連接操作。

1 基于相似連接的數(shù)據(jù)預(yù)處理模型

為保障分析的全面性，傳統(tǒng)的安全分析方法盡可能多地獲取數(shù)據(jù)特征，構(gòu)建分析模型;然而大數(shù)據(jù)環(huán)境中數(shù)據(jù)源的特點致使數(shù)據(jù)量太大，并且會包含大量無用的、冗余的數(shù)據(jù)。若將這些多源數(shù)據(jù)直接導(dǎo)入作為源數(shù)據(jù)進(jìn)行分析，則會出現(xiàn)數(shù)據(jù)不完整、數(shù)據(jù)冗余等問題，從而影響系統(tǒng)效率和準(zhǔn)確率，因此，在進(jìn)行數(shù)據(jù)分析前，需要增設(shè)一個數(shù)據(jù)預(yù)處理過程，從中提取有用的數(shù)據(jù)，進(jìn)而提高數(shù)據(jù)挖掘結(jié)果的準(zhǔn)確性。數(shù)據(jù)預(yù)處理是很有必要的環(huán)節(jié)。

多源數(shù)據(jù)的清洗工作需要充分利用數(shù)據(jù)源之間的互補(bǔ)性，融合多方面的數(shù)據(jù)源信息。為了保留數(shù)據(jù)源的個性信息，并且最大化壓縮數(shù)據(jù)量，本文提出了多源數(shù)據(jù)預(yù)處理模型。主要環(huán)節(jié)包括以下幾個方面：首先，通過選取各自屬性特征模式對數(shù)據(jù)源進(jìn)行獨立篩選;其次，對于不同數(shù)據(jù)源的屬性中的相似語義進(jìn)行統(tǒng)一，對個性語義予以保留;最后將各個數(shù)據(jù)源的處理結(jié)果進(jìn)行連接合并。如圖1所示，本文提出的方法可以對不同的數(shù)據(jù)源進(jìn)行個性、靈活的處理，最后形成一個多維度的數(shù)據(jù)源。其中在連接合并環(huán)節(jié)本文采用了基于相似連接的數(shù)據(jù)預(yù)處理方法[8]，本文采用Jaccard系數(shù)來度量數(shù)據(jù)之間的相似性，Jaccard系數(shù)定義如（1）所示：

其中X和Y分別代表兩個集合。

對于安全分析數(shù)據(jù)而言，上述預(yù)處理模型可以通過動態(tài)調(diào)整閾值將信息不完整、缺失嚴(yán)重、無分析價值的日志條目清洗掉，從而保證數(shù)據(jù)源的可分析性和可靠性，但由于大數(shù)據(jù)環(huán)境數(shù)據(jù)量的龐大導(dǎo)致對每一條數(shù)據(jù)據(jù)計算其Jaccard系數(shù)將耗費大量的時間，因此在本文的第2章將重點介紹如何通過MapReduce框架實現(xiàn)上述預(yù)處理模型，從而提高其效率。關(guān)于相似連接算法也將在第3章設(shè)計Map函數(shù)和Reduce函數(shù)時進(jìn)行詳細(xì)介紹。

2 基于改進(jìn)的IAE-MapReduce數(shù)據(jù)聚合方法

MapReduce框架作為一個并行計算框架，能夠大幅度提高預(yù)處理算法的效率，但對網(wǎng)絡(luò)數(shù)據(jù)源的互補(bǔ)性分析而言，MapReduce框架計算過程中會產(chǎn)生大量相似的鍵值對。為了解決Map端計算結(jié)果中的鍵值對過多的問題，目前有兩種方法：一種方法是引入Combine[9]組件，將中間結(jié)果聚合，相當(dāng)于做了一小的Reduce，但這樣做將會進(jìn)行兩次I/O，系統(tǒng)開銷較大;另一種方法將Map端計算結(jié)果中的鍵值對在內(nèi)存中聚合，一次計算，一次I/O，這種方法的優(yōu)點是速度快，但由于Map端聚合的不足容易導(dǎo)致最終的計算結(jié)果可能和外聚合的結(jié)果不同。

針對上述問題，本文提出了一種改進(jìn)的IAE（Internal And External）-MapReduce數(shù)據(jù)聚合方法，將聚合分為兩個階段，第一個階段為測試階段;第二個階段為聚合階段。兩個階段的具體步驟如下。

2.1 測試階段

測試階段的任務(wù)是測試Map端計算后的數(shù)據(jù)是否能夠進(jìn)行內(nèi)聚合，具體做法是將要進(jìn)行計算的部分?jǐn)?shù)據(jù)通過內(nèi)聚合方法和外聚合方法計算后，比較得到的結(jié)果是否相同。因為使用的數(shù)據(jù)少，所以時間測試階段使用的時間將很短，相對于整個MapReduce的計算總時間，可以忽略不計。如圖2所示，具體步驟如下：

1）分別通過外聚合和內(nèi)聚合計算出相應(yīng)的結(jié)果。

2）比較兩個結(jié)果是否相同。

3）若相同則進(jìn)行內(nèi)聚合，若不相同則進(jìn)行外聚合。

2.2 聚合階段

1）內(nèi)聚合方法。內(nèi)聚合方法的作用是將聚合操作放置到內(nèi)存中進(jìn)行。具體步驟如下：

a）建立〈Key，Value〉倒排索引。根據(jù)讀入的〈Key，Value〉中Key值建立倒排索引，在索引中記錄〈Key，Address〉，Address為〈Key，Value〉在內(nèi)存中的地址值。

b）對Address建立指向Count的索引。為了在內(nèi)存不足時，能夠及時地將匹配次數(shù)少的〈Key，Value〉調(diào)出內(nèi)存，對Address建立匹配次數(shù)Count的索引，并對其進(jìn)行匹配，將匹配成功的〈Key，Value〉進(jìn)行合并。

c）在進(jìn)行下次匹配之前，查看內(nèi)存是否足夠，如果內(nèi)存不足夠，將內(nèi)存中Count值小的部分〈Key，Value〉寫回磁盤。如果內(nèi)存足夠，查看是否還有未計算的〈Key，Value〉：如果有未計算的〈Key，Value〉，將未計算的〈Key，Value〉調(diào)入內(nèi)存進(jìn)行計算并返回a）繼續(xù)執(zhí)行;如果沒有未計算的〈Key，Value〉則結(jié)束。

2）外聚合方法。〈Key，Value〉外聚合模塊的作用是將聚合操作放在Map端的Map函數(shù)計算完成后統(tǒng)一進(jìn)行。具體步驟如下：

a）將〈Key，Value〉調(diào)入內(nèi)存進(jìn)行計算，將計算結(jié)果寫入磁盤，記為S〈Key，Value〉。

b）將磁盤中的S〈Key，Value〉重新調(diào)回內(nèi)存，執(zhí)行內(nèi)聚合的操作。

本文提出的方法通過對Map端數(shù)據(jù)在內(nèi)存中建立索引，根據(jù)數(shù)據(jù)特點選擇不同的Map端數(shù)據(jù)聚合方法，減少I/O次數(shù)，同時減少了生成Mapper的數(shù)量，減少了傳輸?shù)耐ㄐ帕亢蚆apper裝載和卸載所消耗的時間。在下一部分，本文將介紹如何通過本文提出的IAE-MapReduce框架實現(xiàn)基于相似連接的預(yù)處理方法。

3 算法實現(xiàn)與性能分析

3.1 基于IAE-MapReduce的相似連接預(yù)處理算法實現(xiàn)

IAE-MapReduce框架的聚合過程中需要三個階段：測試階段、內(nèi)聚合階段、外聚合階段。其中內(nèi)聚合算法的核心部分如算法1所示。為了提升算法的效率，在進(jìn)行相似連接算法的實現(xiàn)時，使用多重集合的相似連接算法，該算法需迭代三次得出結(jié)果：第一階段得出集合中各個元素的出現(xiàn)次數(shù);第二階段分別將兩個集合聯(lián)合得出所含元素的次數(shù);最后階段根據(jù)Jaccard相似度計算公式，分別計算集合之間的相似度。其中相似連接算法的第二階段的核心部分如算法2所示。

多重集合相似連接第二階段主要完成的是對兩個集合共有特征數(shù)量的統(tǒng)計，〈〈M1，M2，c1，c2〉，〈count1，count2〉〉表示集合M1和集合M2分別有c1、c2個屬性值，而它們共有的某個屬性的個數(shù)分別為count1、count2。

3.2 實驗結(jié)果與算法性能分析

為了驗證本文所提出的基于IAE-MapReduce框架的相似連接預(yù)處理算法的性能，實驗首先將預(yù)處理前后的數(shù)據(jù)集大小進(jìn)行比較，其次針對算法的效率，將本文方法與傳統(tǒng)的MapReduce方法進(jìn)行比較。

圖3顯示的是對防火墻（iptables）日志、域名系統(tǒng)（Domain Name System， DNS）日志和Snort日志進(jìn)行預(yù)處理后數(shù)據(jù)量的變化。本實驗共采用3GB數(shù)據(jù)進(jìn)行預(yù)處理，其中約800MB為防火墻日志，約1150MB為DNS日志，約1050MB為Snort日志。使用相似連接算法對數(shù)據(jù)源進(jìn)行處理時，根據(jù)相似度的不同約簡出的結(jié)果略有不同，但總體上是相似的。實驗結(jié)果表明本文所提出的基于相似連接的預(yù)處理方法使總的數(shù)據(jù)量減小了30%左右。

4 結(jié)語

多源數(shù)據(jù)融合分析是網(wǎng)絡(luò)安全領(lǐng)域用戶行為分析預(yù)測的基礎(chǔ)，而數(shù)據(jù)清洗是其重要環(huán)節(jié)。大數(shù)據(jù)網(wǎng)絡(luò)安全分析環(huán)境下，由于數(shù)據(jù)量的龐大，導(dǎo)致傳統(tǒng)的數(shù)據(jù)清洗技術(shù)效率低，難以滿足態(tài)勢分析實時性的需求，據(jù)此本文提出了一種基于相似連接的多源數(shù)據(jù)預(yù)處理方法，并且采用改進(jìn)的IAE-MapReduce并行處理框架去實現(xiàn)該方法。最后通過實驗驗證本文提出的預(yù)處理方法使總的數(shù)據(jù)量減小了30%，并且相比傳統(tǒng)的MapReduce框架，效率提高了43.91%。

參考文獻(xiàn) （References）

[1] MAJIDI M， OSKUOEE M. Improving pattern recognition accuracy of partial discharges by new data preprocessing methods [J]. Electric Power Systems Research， 2015， 119： 100-110.

[2] LI G， DENG D， WANG J， et al. Pass-join： a partition-based method for similarity joins[J]. Proceedings of the VLDB Endowment， 2011， 5（3）： 253-264.

[3] WANG J， LI G， FE J. Fast-join： an efficient method for fuzzy token matching based string similarity join[C]// Proceedings of the 2011 International Conference on Data Engineering. Piscataway， NJ： IEEE， 2011： 458-469. 本文文獻(xiàn)列表存在重復(fù)現(xiàn)象，如文獻(xiàn)3與文獻(xiàn)14是同一個文獻(xiàn)，請作相應(yīng)調(diào)整，因為在正文中的引用文獻(xiàn)的順序是依次進(jìn)行的，所以建議將文獻(xiàn)3（或14）改為另外一條文獻(xiàn)，注意彼此間不要再重復(fù)了。

[4] 陳一帆，趙翔，何培俊，等.BMGSJoin：一種基于MapReduce的圖相似度連接算法[J].模式識別與人工智能，2015，28（5）：472-480.（CHEN Y F， ZHAO X， HE P J， et al. BMGSJoin： a MapReduce based graph similarity join algorithm [J]. Pattern Recognition & Artificial Intelligence， 2015， 28（5）： 472-480.）

[5] 陳子軍，張娟娜，劉文遠(yuǎn).MapReduce框架下基于范圍的空間文本相似連接[J].小型微型計算機(jī)系統(tǒng)，2015，36（10）：2245-2251.（CHEN Z J， ZHANG J N， LIU W Y. Range-based spatial text similarity connection under MapReduce framework[J]. Journal of Chinese Computer Systems， 2015， 36（10）： 2245-2251.）

[6] BU Y， HOWE B， BALAZINSKA M， et al. HaLoop： efficient iterative data processing on large clusters[J]. Proceedings of the VLDB Endowment， 2010， 3（1/2）： 285-296.

[7] ZHANG Y， GAO Q， GAO L， et al. iMapReduce： a distributed computing framework for iterative computation [J]. Journal of Grid Computing， 2012， 10（1）： 47-68.

[8] 榮垂田，徐天任，杜小勇.基于劃分的集合相似連接[J].計算機(jī)研究與發(fā)展，2012，49（10）：2066-2076.（RONG C T， XU T R， DU X Y. Partition-based set similarity join [J]. Journal of Computer Research and Development， 2012， 49（10）： 2066-2076.）

[9] STUART J A， OWENS J D. Multi-GPU MapReduce on GPU clusters[C]// Proceedings of the 2011 International Conference on Parallel & Distributed Processing Symposium. Piscataway， NJ： IEEE， 2011： 1068-1079.

[10] LIN F， SONG C， XU X， et al. Sensing from the bottom： smart insole enabled patient handling activity recognition through manifold learning[C]// Proceedings of the 2016 International Conference on Connected Health： Applications， Systems and Engineering Technologies. Piscataway， NJ： IEEE， 2016： 254-263.

[11] LU J， WANG G， DENG W， et al. Multi-manifold deep metric learning for image set classification[C]// Proceedings of the 2015 International Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2015： 1137-1145.

[12-7] ZHANG Y， GAO Q， GAO L， et al. iMapReduce： a distributed computing framework for iterative computation [J]. Journal of Grid Computing， 2012， 10（1）： 47-68.

[13-4] 陳一帆，趙翔，何培俊，等.BMGSJoin：一種基于MapReduce的圖相似度連接算法[J].模式識別與人工智能，2015，28（5）：472-480.（Chen Y， Zhao X， He P， et al. BMGSJoin： a MapReduce based graph similarity join algorithm [J]. Pattern Recognition & Artificial Intelligence， 2015， 28（5）： 472-480.）

[14-3] WANG J， LI G， FE J. Fast-join： an efficient method for fuzzy token matching based string similarity join[C]// Proceedings of the 2011 International Conference on Data Engineering. Piscataway， NJ： IEEE， 2011： 458-469.

[12] 劉雪莉，王宏志，李建中，等.基于實體的相似性連接算法[J].軟件學(xué)報，2015，26（6）：1421-1437.（LIU X L， WANG H Z， LI J Z， et al. Entity-based similarity join algorithm[J]. Journal of Software， 2015， 26（6）： 1421-1437.）