基于大規(guī)模圖譜分析的移動(dòng)流量數(shù)據(jù)識(shí)別算法研究

易燦

（湖南大眾傳媒職業(yè)技術(shù)學(xué)院，湖南長(zhǎng)沙，410100）

0 引言

網(wǎng)絡(luò)中每天都會(huì)有大量的用戶數(shù)據(jù)信息產(chǎn)生，例如，移動(dòng)互聯(lián)網(wǎng)網(wǎng)頁(yè)數(shù)據(jù)、用戶交互數(shù)據(jù)、設(shè)備產(chǎn)生活動(dòng)數(shù)據(jù)等等。傳統(tǒng)的流量分析技術(shù)無法做到對(duì)如此大規(guī)模、復(fù)雜數(shù)據(jù)的分析和識(shí)別，網(wǎng)絡(luò)運(yùn)營(yíng)商為滿足用戶使用需求、提升數(shù)據(jù)挖掘能力，需要采用分布式并行算法對(duì)海量網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行處理與分析。圖譜分析是數(shù)據(jù)分析過程中較為常見的分析方法，不僅能夠直觀展現(xiàn)分析過程與結(jié)果，還能挖掘事物間深層次的關(guān)系。文章基于圖譜分析，設(shè)計(jì)了三種識(shí)別算法，對(duì)移動(dòng)網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行識(shí)別與分析。

1 網(wǎng)絡(luò)流量監(jiān)測(cè)方法與意義

■1.1 移動(dòng)流量數(shù)據(jù)監(jiān)測(cè)方法

對(duì)互聯(lián)網(wǎng)流量數(shù)據(jù)進(jìn)行監(jiān)測(cè)是了解互聯(lián)網(wǎng)特性、挖掘有效數(shù)據(jù)信息的重要方式。通常采用兩類方式進(jìn)行流量監(jiān)測(cè)，第一種為主動(dòng)流量監(jiān)測(cè)。此方式通過在監(jiān)測(cè)點(diǎn)利用網(wǎng)絡(luò)探針對(duì)網(wǎng)絡(luò)流量進(jìn)行主動(dòng)監(jiān)測(cè)。其優(yōu)點(diǎn)為能夠直接測(cè)量網(wǎng)絡(luò)，測(cè)量過程可控性較高，測(cè)量方式相對(duì)靈活，但也存在一定缺點(diǎn)，主動(dòng)測(cè)量并直接分析的方式，會(huì)有新的網(wǎng)絡(luò)流量產(chǎn)生，這些新出現(xiàn)的流量，一定程度上會(huì)改變?cè)揪W(wǎng)絡(luò)情況，降低測(cè)量結(jié)果精準(zhǔn)性，且會(huì)使得被監(jiān)測(cè)網(wǎng)絡(luò)的荷載負(fù)擔(dān)加大，反而不利于對(duì)如此大規(guī)模數(shù)據(jù)流量的主動(dòng)測(cè)量。

另一種方式為被動(dòng)流量監(jiān)測(cè)，此監(jiān)測(cè)方式需要設(shè)置監(jiān)測(cè)點(diǎn)，然后按指定的時(shí)間間隔或者長(zhǎng)時(shí)間對(duì)流經(jīng)該監(jiān)測(cè)點(diǎn)的數(shù)據(jù)流量進(jìn)行收集，并將監(jiān)測(cè)點(diǎn)收集的流量信息存儲(chǔ)，便于之后進(jìn)行數(shù)據(jù)分析、特征提取等，也可依據(jù)監(jiān)測(cè)信息對(duì)網(wǎng)絡(luò)性能進(jìn)行分析。該監(jiān)測(cè)方式理論上不會(huì)產(chǎn)生新的網(wǎng)絡(luò)流量，不會(huì)增加網(wǎng)絡(luò)運(yùn)行負(fù)擔(dān)。但其缺點(diǎn)也較為明顯，此方式只能對(duì)某一監(jiān)測(cè)點(diǎn)的流量數(shù)據(jù)進(jìn)行監(jiān)測(cè)，且使得監(jiān)測(cè)點(diǎn)數(shù)據(jù)存儲(chǔ)與分析等問題增多[1]。

■1.2 網(wǎng)絡(luò)流量監(jiān)測(cè)意義

對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行監(jiān)測(cè)，可以實(shí)現(xiàn)互聯(lián)網(wǎng)的科學(xué)規(guī)劃和擴(kuò)容。網(wǎng)絡(luò)運(yùn)營(yíng)過程中，運(yùn)營(yíng)商經(jīng)常會(huì)面臨資源不足問題，導(dǎo)致無法滿足較高的網(wǎng)絡(luò)需求，需要對(duì)網(wǎng)絡(luò)進(jìn)行擴(kuò)容。但是如果沒有針對(duì)性地?cái)U(kuò)容，首先資金投入是一方面的問題，關(guān)鍵也往往并不能有效解決問題，網(wǎng)絡(luò)容量沒有得到顯著擴(kuò)充。如果在擴(kuò)容之前對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行了科學(xué)監(jiān)測(cè)，可結(jié)合網(wǎng)絡(luò)歷史數(shù)據(jù)，對(duì)流量進(jìn)行控制，減少一些低附加值的流量，從根本上避免流量過載問題的發(fā)生，因此能夠減少對(duì)網(wǎng)絡(luò)的擴(kuò)容需求，也能降低運(yùn)營(yíng)商維護(hù)資本。以往的流量監(jiān)測(cè)數(shù)據(jù)，可對(duì)未來流量變化預(yù)測(cè)提供參考，以及時(shí)采取有效措施提前應(yīng)對(duì)。

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

2 基于圖譜分析的網(wǎng)絡(luò)流量數(shù)據(jù)分析與識(shí)別算法

依據(jù)圖譜分析，可對(duì)網(wǎng)絡(luò)中大規(guī)模移動(dòng)流量數(shù)據(jù)進(jìn)行處理與分析，對(duì)互聯(lián)網(wǎng)的現(xiàn)狀進(jìn)行更加直觀、深入的掌握?；趫D譜分析方法，對(duì)海量網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行了三方面的分析，分別為點(diǎn)擊識(shí)別分析、實(shí)體連接結(jié)構(gòu)分析以及網(wǎng)頁(yè)級(jí)精細(xì)化流量分析，并針對(duì)每一種分析都設(shè)計(jì)了相應(yīng)的識(shí)別算法[3]。

■2.1 基于依賴圖的用戶點(diǎn)擊識(shí)別算法

智能終端的應(yīng)用軟件幾乎都采用HTTP 協(xié)議實(shí)現(xiàn)，為了更加高效地從海量數(shù)據(jù)流量中分析出用戶的真實(shí)網(wǎng)絡(luò)瀏覽行為和興趣，要對(duì)Web 數(shù)據(jù)進(jìn)行預(yù)處理，準(zhǔn)確識(shí)別出用戶的網(wǎng)頁(yè)點(diǎn)擊請(qǐng)求[4]。其點(diǎn)擊識(shí)別流程算法如圖1 所示。

圖1 點(diǎn)擊識(shí)別算法流程圖

第一步驟為數(shù)據(jù)預(yù)處理。網(wǎng)絡(luò)中存在大規(guī)模的用戶點(diǎn)擊記錄，一些是錯(cuò)誤的或者無用的請(qǐng)求記錄，為提升用戶點(diǎn)擊快速識(shí)別過程，首先要對(duì)捕獲的海量HTTP 請(qǐng)求記錄進(jìn)行預(yù)處理,將無效記錄清除，減少數(shù)據(jù)量。一個(gè)正常、完整的HTTP 請(qǐng)求記錄具有多個(gè)屬性值，例如，用戶號(hào)碼標(biāo)識(shí)、流開始時(shí)間、流結(jié)束時(shí)間等。其中屬性值不完整的請(qǐng)求記錄都視為要從記錄集中去除的目標(biāo)。然后依據(jù)用戶號(hào)碼將網(wǎng)絡(luò)中同一用戶的請(qǐng)求按照流開始時(shí)間排序并聚合到一起，生成用戶請(qǐng)求序列。

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

第三個(gè)步驟為識(shí)別點(diǎn)擊請(qǐng)求。計(jì)算一個(gè)節(jié)點(diǎn)作為主請(qǐng)求的概率，來判定此用戶請(qǐng)求節(jié)點(diǎn)是否為主請(qǐng)求。計(jì)算方式如下。

計(jì)算出該節(jié)點(diǎn)是主請(qǐng)求的概率P 之后和門限值ρ 對(duì)比，如果P 大于門限值，則可認(rèn)定其為用戶點(diǎn)擊主請(qǐng)求，如果P小于門限值，則認(rèn)定該節(jié)點(diǎn)為內(nèi)嵌請(qǐng)求，即用戶在主請(qǐng)求頁(yè)面觸發(fā)內(nèi)嵌實(shí)體鏈接的請(qǐng)求。

■2.2 并行tNMF 算法

隨著結(jié)構(gòu)化的網(wǎng)頁(yè)越來越復(fù)雜，對(duì)于網(wǎng)站設(shè)計(jì)或者管理員來說，對(duì)網(wǎng)頁(yè)實(shí)體間的關(guān)系進(jìn)行分析也越來越重要。在采用用戶點(diǎn)擊識(shí)別算法以后，請(qǐng)求依賴圖中的每個(gè)節(jié)點(diǎn)被標(biāo)上了點(diǎn)擊請(qǐng)求和內(nèi)嵌請(qǐng)求的分類標(biāo)簽，構(gòu)成了一個(gè)二部請(qǐng)求依賴圖。對(duì)此設(shè)計(jì)一個(gè)并行的tNMF算法對(duì)二部請(qǐng)求依賴圖進(jìn)行圖形分解。通過分析圖形分解結(jié)果，探究網(wǎng)頁(yè)實(shí)體間的依賴模式[6]。

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

圖2 tNMF 算法流程

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

迭代優(yōu)化階段。計(jì)算相對(duì)平方誤差RSE,其計(jì)算公式為：

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

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

■2.3 并行流式算法

用戶的點(diǎn)擊請(qǐng)求能夠反映出用戶的真實(shí)網(wǎng)絡(luò)使用意愿，為對(duì)大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行精細(xì)化分析，基于Spark 計(jì)算框架設(shè)計(jì)了并行流式算法。選用Spark Streaming 并行開源框架,相對(duì)于其他流式處理框架，其對(duì)流式大規(guī)模數(shù)據(jù)處理優(yōu)勢(shì)顯著，能夠從多種數(shù)據(jù)源獲得數(shù)據(jù)，也能將數(shù)據(jù)輸出到不同數(shù)據(jù)平臺(tái)。接收到數(shù)據(jù)流以后，將其分為一個(gè)個(gè)小批次數(shù)據(jù)流（Batch），供后續(xù)處理。DStream 是Spark Streaming 中特有的基礎(chǔ)數(shù)據(jù)類型，代表了一系列連續(xù)的RDD，每個(gè)RDD 都對(duì)應(yīng)一個(gè)小批次數(shù)據(jù)流Batche，使得用戶能夠通過處理RDD 來對(duì)流式數(shù)據(jù)進(jìn)行處理[7]。設(shè)計(jì)的并行流式算法流程圖如圖3 所示。

圖3 并行流式算法流程圖

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

3 結(jié)語

綜上所述，網(wǎng)絡(luò)數(shù)據(jù)監(jiān)測(cè)對(duì)于網(wǎng)絡(luò)的科學(xué)規(guī)劃與擴(kuò)容、網(wǎng)絡(luò)安全運(yùn)維與防護(hù)、網(wǎng)絡(luò)資源合理利用等都有著重要意義。設(shè)計(jì)了用戶點(diǎn)擊識(shí)別算法以更深入探究用戶的使用需求和興趣；設(shè)計(jì)了并行tNMF 算法，以揭示網(wǎng)頁(yè)實(shí)體間的依賴模式；基于Spark 技術(shù)框架設(shè)計(jì)了并行流式算法，對(duì)流量數(shù)據(jù)進(jìn)行精細(xì)化分析。分布式并行算法在網(wǎng)絡(luò)數(shù)據(jù)的挖掘和分析中將會(huì)發(fā)揮更重要的作用。