基于相似連接的多源數據并行預處理方法

郭方方 潮洛蒙 朱建文

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

關鍵詞：網絡安全;多源數據;數據預處理;相似連接;MapReduce

中圖分類號： TP274

文獻標志碼：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 引言

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

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

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

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

1 基于相似連接的數據預處理模型

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

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

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

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

2 基于改進的IAE-MapReduce數據聚合方法

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

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

2.1 測試階段

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

1）分別通過外聚合和內聚合計算出相應的結果。

2）比較兩個結果是否相同。

3）若相同則進行內聚合，若不相同則進行外聚合。

2.2 聚合階段

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

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

b）對Address建立指向Count的索引。為了在內存不足時，能夠及時地將匹配次數少的〈Key，Value〉調出內存，對Address建立匹配次數Count的索引，并對其進行匹配，將匹配成功的〈Key，Value〉進行合并。

c）在進行下次匹配之前，查看內存是否足夠，如果內存不足夠，將內存中Count值小的部分〈Key，Value〉寫回磁盤。如果內存足夠，查看是否還有未計算的〈Key，Value〉：如果有未計算的〈Key，Value〉，將未計算的〈Key，Value〉調入內存進行計算并返回a）繼續執行;如果沒有未計算的〈Key，Value〉則結束。

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

a）將〈Key，Value〉調入內存進行計算，將計算結果寫入磁盤，記為S〈Key，Value〉。

b）將磁盤中的S〈Key，Value〉重新調回內存，執行內聚合的操作。

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

3 算法實現與性能分析

3.1 基于IAE-MapReduce的相似連接預處理算法實現

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

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

3.2 實驗結果與算法性能分析

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

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

4 結語

多源數據融合分析是網絡安全領域用戶行為分析預測的基礎，而數據清洗是其重要環節。大數據網絡安全分析環境下，由于數據量的龐大，導致傳統的數據清洗技術效率低，難以滿足態勢分析實時性的需求，據此本文提出了一種基于相似連接的多源數據預處理方法，并且采用改進的IAE-MapReduce并行處理框架去實現該方法。最后通過實驗驗證本文提出的預處理方法使總的數據量減小了30%，并且相比傳統的MapReduce框架，效率提高了43.91%。

參考文獻 （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. 本文文獻列表存在重復現象，如文獻3與文獻14是同一個文獻，請作相應調整，因為在正文中的引用文獻的順序是依次進行的，所以建議將文獻3（或14）改為另外一條文獻，注意彼此間不要再重復了。

[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] 陳子軍，張娟娜，劉文遠.MapReduce框架下基于范圍的空間文本相似連接[J].小型微型計算機系統，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].計算機研究與發展，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].軟件學報，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.）