基于大規模圖譜分析的移動流量數據識別算法研究

易燦

（湖南大眾傳媒職業技術學院，湖南長沙，410100）

0 引言

網絡中每天都會有大量的用戶數據信息產生，例如，移動互聯網網頁數據、用戶交互數據、設備產生活動數據等等。傳統的流量分析技術無法做到對如此大規模、復雜數據的分析和識別，網絡運營商為滿足用戶使用需求、提升數據挖掘能力，需要采用分布式并行算法對海量網絡數據進行處理與分析。圖譜分析是數據分析過程中較為常見的分析方法，不僅能夠直觀展現分析過程與結果，還能挖掘事物間深層次的關系。文章基于圖譜分析，設計了三種識別算法，對移動網絡流量數據進行識別與分析。

1 網絡流量監測方法與意義

■1.1 移動流量數據監測方法

對互聯網流量數據進行監測是了解互聯網特性、挖掘有效數據信息的重要方式。通常采用兩類方式進行流量監測，第一種為主動流量監測。此方式通過在監測點利用網絡探針對網絡流量進行主動監測。其優點為能夠直接測量網絡，測量過程可控性較高，測量方式相對靈活，但也存在一定缺點，主動測量并直接分析的方式，會有新的網絡流量產生，這些新出現的流量，一定程度上會改變原本網絡情況，降低測量結果精準性，且會使得被監測網絡的荷載負擔加大，反而不利于對如此大規模數據流量的主動測量。

另一種方式為被動流量監測，此監測方式需要設置監測點，然后按指定的時間間隔或者長時間對流經該監測點的數據流量進行收集，并將監測點收集的流量信息存儲，便于之后進行數據分析、特征提取等，也可依據監測信息對網絡性能進行分析。該監測方式理論上不會產生新的網絡流量，不會增加網絡運行負擔。但其缺點也較為明顯，此方式只能對某一監測點的流量數據進行監測，且使得監測點數據存儲與分析等問題增多[1]。

■1.2 網絡流量監測意義

對網絡流量數據進行監測，可以實現互聯網的科學規劃和擴容。網絡運營過程中，運營商經常會面臨資源不足問題，導致無法滿足較高的網絡需求，需要對網絡進行擴容。但是如果沒有針對性地擴容，首先資金投入是一方面的問題，關鍵也往往并不能有效解決問題，網絡容量沒有得到顯著擴充。如果在擴容之前對網絡流量數據進行了科學監測，可結合網絡歷史數據，對流量進行控制，減少一些低附加值的流量，從根本上避免流量過載問題的發生，因此能夠減少對網絡的擴容需求，也能降低運營商維護資本。以往的流量監測數據，可對未來流量變化預測提供參考，以及時采取有效措施提前應對。

通常情況下，每天的網絡流量時間流量曲線都較為相似。假如某個節點出現了故障，那么其相對應的網絡流量也會呈現出異常現象。因此，網絡流量監測環節，可幫助網絡運維人員進行網絡故障分析和運行維護。對網絡流量的監測，有助于發現信息流量的不合理流動情況，例如，一些非常繁忙的鏈路或者經常閑置的鏈路，然后進行人工調整，以提高網絡資源的利用率，同時避免流量擁堵。網絡監測在網絡安全防護方面也有著重要作用。網絡上不可避免地存在一些大大小小的不合規合法現象，例如，惡意攻擊、垃圾郵件以及惡意病毒等，影響網絡的安全使用。這些行為通常較為隱蔽，需要專門的設備來檢查。而長期的網絡流量監測下，正常流量的基線已經建立，對一些異常流量進行監測可發現這些違法行為，維護網絡安全[2]。對網絡流量監測數據進行挖掘和分析，也有助于了解用戶的真正需求，然后利用網絡資源，實現精準市場營銷，增加用戶對網絡的依賴性，提升用戶使用滿意度。

2 基于圖譜分析的網絡流量數據分析與識別算法

依據圖譜分析，可對網絡中大規模移動流量數據進行處理與分析，對互聯網的現狀進行更加直觀、深入的掌握?；趫D譜分析方法，對海量網絡流量數據進行了三方面的分析，分別為點擊識別分析、實體連接結構分析以及網頁級精細化流量分析，并針對每一種分析都設計了相應的識別算法[3]。

■2.1 基于依賴圖的用戶點擊識別算法

智能終端的應用軟件幾乎都采用HTTP 協議實現，為了更加高效地從海量數據流量中分析出用戶的真實網絡瀏覽行為和興趣，要對Web 數據進行預處理，準確識別出用戶的網頁點擊請求[4]。其點擊識別流程算法如圖1 所示。

圖1 點擊識別算法流程圖

第一步驟為數據預處理。網絡中存在大規模的用戶點擊記錄，一些是錯誤的或者無用的請求記錄，為提升用戶點擊快速識別過程，首先要對捕獲的海量HTTP 請求記錄進行預處理,將無效記錄清除，減少數據量。一個正常、完整的HTTP 請求記錄具有多個屬性值，例如，用戶號碼標識、流開始時間、流結束時間等。其中屬性值不完整的請求記錄都視為要從記錄集中去除的目標。然后依據用戶號碼將網絡中同一用戶的請求按照流開始時間排序并聚合到一起，生成用戶請求序列。

第二個步驟為建立請求依賴圖。依賴圖中的每個點都有兩種可能，分別是主請求和內嵌請求。主請求是向網頁服務器發出的第一個請求，也就是用戶點擊請求。初始頁面會有多種內嵌實體超鏈接，用戶對這些內嵌超鏈接發出的請求即為內嵌請求。設定一個向前間隔時間τ，與用戶請求間隔作對比。如果該用戶的請求ri的起始時間和ri-1的起始時間差值大于τ，將其認定為候選主請求，如果ri與下一個請求ri+1起始時間差值小于τ，則在請求依賴圖中由ri代表的點向ri+1代表的點建立一條邊。依次類推，直到發現一個新的候選主請求為止，再計算用戶在新主請求中的內嵌請求[5]。依賴圖中用戶請求的點或兩個請求之間的邊的出現次數，當做其在請求依賴圖中的權重。

第三個步驟為識別點擊請求。計算一個節點作為主請求的概率，來判定此用戶請求節點是否為主請求。計算方式如下。

計算出該節點是主請求的概率P 之后和門限值ρ 對比，如果P 大于門限值，則可認定其為用戶點擊主請求，如果P小于門限值，則認定該節點為內嵌請求，即用戶在主請求頁面觸發內嵌實體鏈接的請求。

■2.2 并行tNMF 算法

隨著結構化的網頁越來越復雜，對于網站設計或者管理員來說，對網頁實體間的關系進行分析也越來越重要。在采用用戶點擊識別算法以后，請求依賴圖中的每個節點被標上了點擊請求和內嵌請求的分類標簽，構成了一個二部請求依賴圖。對此設計一個并行的tNMF算法對二部請求依賴圖進行圖形分解。通過分析圖形分解結果，探究網頁實體間的依賴模式[6]。

用鄰接矩陣表示二部請求依賴圖模型，對鄰接矩陣分別進行行向量和列向量的聚類，得到具有相似特征的行向量和列向量，組成一系列子集。設計的并行tNMF 算法是對二部請求依賴圖進行分解的一種聯合聚類算法。鄰接矩陣Dm×n中m 代表主請求，n 代表內嵌請求，將m 個主請求聚類為p 個主請求組，表示為矩陣Rm×p，對應的，將n 個內嵌請求聚類為q 個內嵌請求組,表示為Cn×q，因此最終可得p×q 個聚類子圖，表示為矩陣Hp×q。所有的矩陣都為非負矩陣，并行tNMF 算法流程如圖2 所示。

圖2 tNMF 算法流程

初始輸入階段。向算法中輸入一個鄰接矩陣Dm×n，然后依據矩陣階數和p、q 參數，將上述矩陣R、C、H 隨機初始化。

迭代優化階段。計算相對平方誤差RSE,其計算公式為：

當相對平方誤差大于門限值θ 時，對R、C、H 三個矩陣進行迭代更新，直到其小于門限值θ，停止迭代更新進入下一步。矩陣R 中的元素表示第i 個元素屬于第s 組的似然度。迭代更新算法為：

輸出階段。經迭代優化以后，最終生成三個矩陣，分別為R、H、C,然后再生成聚類子圖。完成并行tNMF 算法。得到p×q 個聯合聚類，其中每一個分組都代表一個子圖結構，用小的鄰接矩陣L 表示每個子圖結構，矩陣L 的行向量表示為k，列向量為h,分別表示子圖中的主請求和內嵌請求個數。根據矩陣Lk×h的階數，對子圖的結構模型進行判斷。判斷方法為：如果子圖中主請求個數k 為1，同時內嵌請求個數h 大于1，則這種子圖結構模式為“點擊星形”；如果主請求個數k 大于1，同時內嵌請求個數h 等于1，此時子圖結構模式為“內嵌星形”；如果k 和h 都大于1，則這種子圖結構模式為“網狀”；如果k 和h 都等于1，將此子圖結構模式定義為“其他”類型。

■2.3 并行流式算法

用戶的點擊請求能夠反映出用戶的真實網絡使用意愿，為對大規模網絡數據進行精細化分析，基于Spark 計算框架設計了并行流式算法。選用Spark Streaming 并行開源框架,相對于其他流式處理框架，其對流式大規模數據處理優勢顯著，能夠從多種數據源獲得數據，也能將數據輸出到不同數據平臺。接收到數據流以后，將其分為一個個小批次數據流（Batch），供后續處理。DStream 是Spark Streaming 中特有的基礎數據類型，代表了一系列連續的RDD，每個RDD 都對應一個小批次數據流Batche，使得用戶能夠通過處理RDD 來對流式數據進行處理[7]。設計的并行流式算法流程圖如圖3 所示。

圖3 并行流式算法流程圖

由圖3 可知，首先開源流處理平臺Kafka 將捕獲的網絡流量數據以數據流形式輸送給SparkStreaming，SparkStreaming 將整個數據流切分為多個小段數據流，轉換為DStream 數據。以5 分鐘為一個時間段，將數據流分別依次存在Batchs 中。將數據流切分，可能會引起用戶訪問同一網頁的所有請求，分在不同批次Batche 中。在此需要用到SparkStreaming 的窗口函數，將窗口大小定為10分鐘，而滑動更新時間間隔為5 分鐘，這樣當用戶的網頁請求被分到不同Batch 中時，窗口進行一次滑動后，下一個Batch 內依然有上一個Batch 內網頁的所有請求，數據完整性得到保障，每個RDD 都輸入到Spark 引擎中，先對用戶在同一網頁內的所有請求構建referrer 圖，然后將RDD經Content-Type 過濾和其他轉換操作，識別出用戶的點擊請求，輸出到HDFS 內[8]。

3 結語

綜上所述，網絡數據監測對于網絡的科學規劃與擴容、網絡安全運維與防護、網絡資源合理利用等都有著重要意義。設計了用戶點擊識別算法以更深入探究用戶的使用需求和興趣；設計了并行tNMF 算法，以揭示網頁實體間的依賴模式；基于Spark 技術框架設計了并行流式算法，對流量數據進行精細化分析。分布式并行算法在網絡數據的挖掘和分析中將會發揮更重要的作用。