一種識別用戶實際訪問網(wǎng)址的算法設計

王剛 翟欣虎 秦益飛

一.引言

隨著互聯(lián)網(wǎng)技術的飛速發(fā)展，使用終端接入運營商服務器并訪問互聯(lián)網(wǎng)網(wǎng)站的用戶數(shù)量快速增長。通常情況下運營商都需要對所接入用戶的上網(wǎng)行為進行審計，而該審計需要準確的識別出用戶實際的訪問網(wǎng)址。通常情況下記錄用戶訪問的網(wǎng)址最準確的設備是用戶使用的終端設備的瀏覽器，但運營商無法通過簡單方法拿到用戶使用的終端設備上的數(shù)據(jù)，所以最實際可行的方法是通過用戶接入運營商服務器后，通過服務器所產(chǎn)生的用戶訪問日志來進行分析。

但實際中，對于用戶使用終端設備上的瀏覽器訪問某個互聯(lián)網(wǎng)網(wǎng)站的某個頁面時，瀏覽器向網(wǎng)站發(fā)出的請求的數(shù)量遠大于用戶在瀏覽器中輸入的或者點擊某個鏈接產(chǎn)生的那一條請求。通常情況下用戶訪問一個網(wǎng)站頁面，瀏覽器會發(fā)出幾十乃至上百條數(shù)量不等的請求給網(wǎng)站服務器，比如用戶實際只打開某個新聞頁面，而瀏覽器實際會額外請求若干張網(wǎng)頁上的圖片，若干段廣告文本，甚至音樂，動畫等。對于用戶接入的運營商的服務器（網(wǎng)關代理等），服務器會把每一條請求都記錄成一條日志，服務器只是處理記錄這些請求，其本身是無法區(qū)分出用戶實際訪問的那個鏈接請求的。表1列出當某個用戶訪問百度首頁時實際產(chǎn)生的部分訪問請求。

基于上述情況，運營商在每時每刻產(chǎn)生的海量訪問記錄面前，對用戶上網(wǎng)行為的審計將會產(chǎn)生較大偏差，用戶實際訪問的網(wǎng)址被掩埋在大多數(shù)沒有價值的數(shù)據(jù)中。所以相對準確的識別出用戶實際訪問的網(wǎng)址將對運營商的用戶行為審計產(chǎn)生關鍵的作用。

從海量訪問日志中識別出用戶實際訪問最常見的是過濾合并方法，該方法將訪問日志中的URL字段中包含jpeg、mp3、js、css等關鍵字的日志過濾掉，將剩下的日志中相鄰的且URL字段相同的多條日志合并為一條，最終將這些日志的URL識別為用戶實際訪問的網(wǎng)址。但是，因為非用戶實際訪問的網(wǎng)址也就是瀏覽器根據(jù)網(wǎng)頁情況自動發(fā)送的請求，這些請求中除了一些可以被簡單通過關鍵字過濾掉的以外，還有很大一部分是和用戶實際訪問的網(wǎng)址從結構來看沒有區(qū)別，無法區(qū)分。這種情況下通過簡單過濾合并的結果會多出大量的誤報日志，嚴重影響后續(xù)審計的準確性。

二.識別用戶實際訪問網(wǎng)址的算法設計

（一）識別算法總體流程設計

當一個用戶使用瀏覽器訪問某個互聯(lián)網(wǎng)網(wǎng)站時，該用戶每一次訪問操作（例如在瀏覽器地址欄輸入網(wǎng)站地址，或者點擊了某個網(wǎng)站上的某個鏈接）都會被為其服務的網(wǎng)絡服務運營商（例如中國電信）的網(wǎng)關服務器處理并記錄下來，通常情況下每一次訪問操作都會包含數(shù)量不等的若干條請求，每一個請求都會被至少包含如下字段的日志所記錄下來，一個典型的請求日志至少包含如下字段，如表2所示。

通常情況下，網(wǎng)關服務器每時每刻都會收到從不同用戶設備發(fā)往不同互聯(lián)網(wǎng)網(wǎng)站的海量請求，網(wǎng)關服務器將這些請求生成的日志發(fā)往本發(fā)明所述的裝置，本識別算法收到這些日志后，按如下流程處理：

步驟1，算法首先需要定期收集由運營商服務器所產(chǎn)生的上述用戶訪問日志，每次收集的周期不宜太長，例如可以將收集周期定位1分鐘。收集的方式?jīng)]有特定的要求，例如可以通過將日志作為消息逐條發(fā)送給本算法，也可以通過將一段時間的若干條日志以文件的方式傳送到本算法。

步驟2，將收到的日志按用戶標識字段進行分組，即每一組內的日志都包含相同的用戶標識。

步驟3，將每一組的日志按訪問時間字段的先后順序重新排序。

步驟4，將已經(jīng)排好序的每一組日志按相鄰兩條日志的訪問時間的時間間隔的長短進行合并，當一小段時間間隔內存在大于等于設定閾值的日志條數(shù)時，則將這些日志歸并為該用戶一次訪問所產(chǎn)生的請求日志，所采用的歸并方法可以有多種，例如可以采用無監(jiān)督聚類方法中的基于層次聚類的ROCK，基于密度聚類的Dbscan，基于神經(jīng)網(wǎng)絡聚類的SOM，基于統(tǒng)計學聚類的COBWeb等，經(jīng)過分析發(fā)現(xiàn)基于密度聚類的DBScan最適合上述場景。

步驟5，對于已經(jīng)分好的一次訪問產(chǎn)生的若干條日志按URL和Referer字段構建多叉樹，其中將URL字段的內容作為子節(jié)點，Referer字段的內容作為父節(jié)點，如此遍歷這些日志，將構建出1顆或者多顆多叉樹。

步驟6，統(tǒng)計上述1顆或者多顆多叉樹的葉子節(jié)點的數(shù)量，選出其中葉子節(jié)點最多的樹的根節(jié)點作為該用戶當時實際訪問的網(wǎng)站地址。

如此反復上述步驟，即可識別出用戶實際訪問的網(wǎng)址。

（二）訪問行為時間劃分算法設計

DBScan是一種基于密度的無監(jiān)督聚類算法，可以接受一維或多維待聚類樣本數(shù)據(jù)作為輸入源，其基本思想是先計算所有樣本兩兩之間的歐式距離，然后規(guī)定在掃描半徑 （eps）內存至少存在最小包含點數(shù)（minPts）個歐式距離小于eps的樣本，則這些樣本將被聚為同一類，反之則作為噪聲樣本。即，包含在圓內的樣本聚為同一類，而圓外的樣本則當成噪聲。

本識別算法在獲取到同一用戶產(chǎn)生的一小段時間內連續(xù)的訪問記錄，將記錄的時間作為DBScan一維樣本輸入源，通過算法將樣本分為若干類，每一類中的記錄則作為該用戶一次訪問所產(chǎn)生的所有請求。根據(jù)后續(xù)URL識別需要，將時間上兩兩相鄰的類之間可能存在的噪聲樣本歸屬到時間靠后的一類中。

（三）實際訪問網(wǎng)址識別算法設計

根據(jù)HTTP協(xié)議規(guī)范，當某用戶訪問的頁面發(fā)生跳轉，或同一個頁面中的請求自動請求其他資源，HTTP請求頭中的Referer字段將記錄下發(fā)生跳轉前頁面或上一級請求的URL。據(jù)此，一次訪問行為的所有請求可構建成一顆或多顆多叉樹。

從構建的一顆或多顆多叉樹中，選出葉子節(jié)點最多的樹，該樹的根節(jié)點對應的URL可以識別為用戶實際訪問的網(wǎng)址。

三.識別用戶實際訪問網(wǎng)址的算法驗證

（一）驗證數(shù)據(jù)建立

搭建一個包含60臺PC的小型局域網(wǎng)，這60臺PC設備由60名普通用戶操作進行辦公及互聯(lián)網(wǎng)訪問活動，所有PC均接入局域網(wǎng)出口網(wǎng)關，由網(wǎng)關服務器負責處理并記錄所有用戶的互聯(lián)網(wǎng)訪問請求。

讓60名用戶在一天內進行任意互聯(lián)網(wǎng)訪問活動，從網(wǎng)關服務器收集一天內所有的原始訪問請求記錄約50萬條作為待檢測樣本。同時收集該60名用戶使用的PC瀏覽器記錄下的當天互聯(lián)網(wǎng)實際訪問記錄共約1萬條作為標簽，同時記錄標簽和用戶的對應關系，如表3。

（二）驗證方法及結果分析

從3個指標評估算法的性能：

準確率：正確識別出的網(wǎng)址數(shù) / 實際訪問的網(wǎng)址總數(shù)

漏報率：（ 實際訪問的網(wǎng)址總數(shù) - 正確識別出的網(wǎng)址數(shù) ） / 實際訪問的網(wǎng)址總數(shù)

誤報率：（ 識別出的網(wǎng)址總數(shù) - 正確識別出的網(wǎng)址數(shù)） / 實際訪問的網(wǎng)址總數(shù)

將使用本文所述算法得出的識別結果作為實驗組數(shù)據(jù)，將使用傳統(tǒng)過濾合并法（見引言部分所述）得出的識別結果作為對照組數(shù)據(jù)，其中針對實驗組分別計算上述3個評估指標，而針對對照組只計算誤報率這1個評估指標（因為過濾合并法只會去掉明顯不可能是實際訪問的網(wǎng)址記錄，導致該方法的準備率幾乎是100%，同理漏報率幾乎是0%，所以對過濾合并法計算準確率和漏報率不具備統(tǒng)計學意義）。驗證結果如表4.

結果表明，傳統(tǒng)過濾合并法只是簡單的將所有原始記錄中明顯可排除的記錄去除，除此以外并無法區(qū)分實際訪問的記錄和非實際訪問的記錄，所以其識別的結果會產(chǎn)生非常高的誤報率，甚至可以達到實際訪問網(wǎng)址數(shù)量的數(shù)倍乃至數(shù)十倍，故在這種情況下即使是100%的準確率也并不具備實用價值。而本文所述算法得出結果的準確率和誤報率兩者相對平衡，相比傳統(tǒng)方法更具備實用價值。

四.結束語

上述針對用戶實際訪問網(wǎng)址的識別算法，采用了傳統(tǒng)數(shù)理統(tǒng)計以及無監(jiān)督機器學習相結合的思路，從時間和內容兩個維度預測識別實際訪問的網(wǎng)址，相比于傳統(tǒng)簡單過濾合并的方法大幅降低了誤報率，更加具備實用價值。

作者單位：江蘇易安聯(lián)網(wǎng)絡技術有限公司