基于相鄰請求的動態時間閾值會話識別算法

曾 令,肖如良

(1.福建師范大學 軟件學院,福州 350117; 2.福建省公共服務大數據挖掘與應用工程研究中心,福州 350117)

基于相鄰請求的動態時間閾值會話識別算法

曾 令1,2,肖如良1,2*

(1.福建師范大學 軟件學院,福州 350117; 2.福建省公共服務大數據挖掘與應用工程研究中心,福州 350117)

在大數據平臺的異常檢測分析中,為提高會話序列建模的效率,提出一種基于相鄰請求的動態調整時間間隔閾值的會話識別算法——DAITS算法。首先同時結合站點頁面因子和用戶訪問頁面時間的平均因子;然后在兩者間加入合適的權重因子對時間閾值進行動態調整;最后根據判斷是否超過該時間閾值來劃分會話。實驗結果表明,DAITS算法比傳統使用固定閾值的方法在會話識別的精確率和查全率上提高了14.8%和13.2%,比動態調整閾值的方法在精確率和查全率上提高了6.2%和3.2%。

異常檢測;會話識別;會話序列;相鄰請求;動態時間閾值

0 引言

隨著大數據技術的飛速發展,大數據平臺架構變得愈發復雜,而大數據平臺對新風險的安全需求也在持續增加。利用異常檢測技術保證大數據平臺的安全性是一種有效的解決方式,而對用戶日志進行精準的會話識別具有重要的意義：一方面可利用會話異常模型檢測出會話異常;另一方面可根據會話可疑度對用戶會話進行模式挖掘。日志挖掘的步驟主要包括數據預處理、模式識別和模式分析,其中數據預處理是首要階段。數據預處理主要包括數據清洗、用戶識別、會話識別和路徑補充。會話識別算法的好壞直接影響著后續對會話序列建模的工作,從而決定能否為異常檢測提供有意義的支持。

目前,會話識別的方法很多。按照對用戶訪問行為的不同假設,會話識別的方法可分為基于時間、基于導航、基于語義這三類方法?；趯Ш降姆椒ㄖ饕治鲇脩粽麄€訪問過程,并需要尋找訪問過程中斷開的位置,并從統一資源定位符(Uniform Resource Locator, URL)中挖掘可以反映用戶行為的信息。這類方法主要包括基于引用的方法[1]和基于網絡拓撲結構的方法[2]?；诰W絡拓撲結構的方法比基于引用的方法劃分的粒度更小,但是不同用戶在相同時間訪問相同網頁的后續行為會不同,因此這類方法不能模仿人的智能。而基于語義的方法為模擬人的智能提供了可能性。這類方法需要先構建語義本體,再建立用戶會話模型,最后將語義接近到一定程度的請求資源劃分到同一個會話中。這類方法可劃分為直接使用URL信息[3]和使用URL請求的頁面內容[4]：一方面,這類方法對URL信息要求比較完整;另一方面,雖然這種方法在模擬用戶真實網絡行為有一定的突破,但是由于存在局限性和準確率較低的問題,目前這類方法的應用并不廣泛。而最常用的基于時間的會話識別方法是以時間閾值為基準來確定會話邊界,優點是這類方法在原理和實現上相對另兩種方法簡單,關鍵的難點是如何有效合理地設置時間閾值。該方法也可大致分為以會話時長為依據和以相鄰請求時長為依據這兩類，并且以相鄰請求時長為依據的方法比以會話時長為依據的方法更加接近用戶真實行為[5]。

因此，本文在以相鄰請求時長為依據的基礎上，提出一種基于相鄰請求的動態調整時間間隔閾值的會話識別算法(session identification algorithm based on Dynamic Adjustive Interval Time threShold of adjacent requests, DAITS)。該算法同時考慮站點頁面因子和用戶訪問時間的平均因子,并加入合適的權重因子對該閾值進行動態調整。

1 相關工作

在基于時間的方法中,Fernandez等[6]使用30 min作為整個會話時長切分的時間閾值,而Jones等[7]使用25.5 min作為劃分時長依據,甚至Neelima等[8]提出使用60 min作為切分閾值。這類劃分方式認為所有會話持有相同的時間,劃分相對比較粗糙。

在以相鄰請求時長為依據的方法中需要預先設置一時間間隔閾值,根據判斷相鄰兩次請求的時間是否超過這一閾值確定同一用戶相鄰兩次的請求是否屬于同一會話,而時間間隔閾值通常設置為10 min[9]。這種設置固定閾值方法的不足在于一方面可能使原本在同一會話中的記錄被劃分到不同的會話中,另一方面也可能使原本不在同一會話中的記錄劃分到同一會話中。殷賢亮等[10]提出了一種改進的基于時間間隔的方法,考慮到不同頁面的差異性,通過根據頁面內容及站點結構引入鏈接內容比作為因變量對該閾值進行調整;而文獻[11]也提出一種將過濾框架網頁與頁面訪問時間閾值相結合的方法構造出相對合理的時間閾值來進行用戶的會話識別;文獻[12]中提到對根據網頁訪問時間閾值生成的會話候選集進行二次識別可以提高識別效率。

但是不同的用戶會有不同的興趣和習慣,這樣的差異也將會導致訪問時間的不同,上述這幾種方法并沒有考慮到這個層面。因此He等[13]考慮到用戶差異性提出了一種動態調整訪問時間閾值的算法,引入調整因子，即當有新頁面加入當前會話便重新計算時間閾值的方法。同樣地,Sengottuvelan等[14]基于此提出通過計算用戶會話中的平均間隔時間動態調整該用戶的時間閾值。

綜上所述,DAITS算法是基于相鄰請求時長并在兼顧頁面差異性和用戶差異性的同時,考慮在兩者間加入合適的權重因子,探究權重因子對會話識別的影響程度。

2 數據預處理

2.1 數據清理

數據預處理中首先需要進行數據清理,無論對何種形式的數據進行分析的過程中,清洗服務器中不相關數據這一技術對整個數據分析有著重要的作用。也就是說,只有當服務器中的數據能夠準確地反映用戶真實訪問網站的情況時,經過挖掘得到的結果才具有可靠性。刪除與挖掘算法無關的數據包括:1)刪除圖片、音頻、腳本和樣式等多媒體文件,保留html文件;2)刪除狀態碼不為200的記錄;3)刪除請求方式不為get的記錄;4)清洗除用戶IP地址、訪問時間和請求資源與算法不相關的屬性記錄。

2.2 用戶識別

用戶識別需要從日志中的每一條記錄識別出相對應的用戶。基于文獻[15],按照三種標準來識別用戶:1)新的IP地址視為新用戶;2)相同IP地址,但是訪問軟件不同,或不同操作系統,或者其他的不同版本的軟件均視為新用戶;3)當相同IP地址訪問的網址之間沒有拓撲關聯時視為新用戶。

2.3 會話識別

會話被認為是一個用戶進入站點時刻至他離開時刻止所請求的一系列鏈接的結合。會話識別是在用戶識別之后,把每個用戶在一段時間內的訪問序列進行分解,從而得到相應的會話。會話是指同一用戶在一次瀏覽過程中連續請求的頁面序列,它代表了用戶對服務器的一次有效訪問。

用戶會話是一個三元組〈sessionID,userID,RS〉。其中：sessionID(sessionIdentification)表示會話標識；userID(userIdentification)表示用戶標識；RS(RequestsSet)表示和用戶在一段時內請求記錄的頁面集合，RS包含用戶請求頁面標識符(PageIdentification,PID)和請求時間t。用戶會話序列S表示為:

S=〈sessionID,userID,{(PID1,t1),(PID2,t2),…,

(PIDn,tn)}〉

(1)

對于上述提到的基于時間的兩類會話識別方法,在以會話時長為劃分方法中,設定整個會話時長:

Time[k]-Time[i]≤T

(2)

其中T為設定的時間閾值。

在以相鄰請求時長為依據的方法中,根據判斷相鄰兩次請求的時間是否超過這一閾值確定同一用戶相鄰兩次的請求是否屬于同一會話:

Time[t]-Time[t-1]≤ΔT

(3)

其中ΔT為設定的時間間隔閾值。

2.4 路徑補充

路徑補充是對識別出的用戶會話進行優化的步驟,目的是使其更加準確地描述用戶的瀏覽請求。由于緩存導致頁面缺失的問題,借助站點信息構建完整的路徑。通常可以采用網絡拓撲結構和用戶的訪問順序進行路徑補充。

3 DAITS算法

DAITS算法是基于大數據平臺的頁面訪問時間和用戶訪問時間閾值的會話識別算法。一方面由于每個用戶存在個體差異性,如用戶網絡速度、閱讀速度、上網習慣等一系列因素會導致不同的用戶會話時間是不相同的。但是,如果針對同一個用戶來講其所屬的網絡環境、個人興趣及習慣等因素對不同用戶來說是相對穩定的。另一方面除去用戶個體差異對會話閾值的影響,會話閾值與頁面內容及站點結構也是有關系的。也就是說同一個用戶瀏覽不同的頁面所需的時間也是不相同的。所以此算法將同時考慮頁面內容和用戶差異性并在兩者間加入合適的權重,探究權重因子對會話識別精確率和查全率的影響。

3.1 頁面訪問時間閾值

通常使用頁面的鏈入數和鏈出數來衡量頁面的重要程度。令L1表示鏈入數即鏈接到某頁面的頁面個數,L0表示鏈出數即某頁面包含的鏈接個數,S表示頁面大小。鏈接內容比RLCR的計算公式表示為:

RLCR=(L1+L0)/S

(4)

一般情況下,一個頁面的鏈入比鏈出重要,根據文獻[13]對它們賦予不同的權值。將公式調整為:

RLCR=(0.7L1+0.3L0)/(L1+L0)

(5)

為了將RLCR值用于對頁面訪問時間閾值δ′的調整,需要將RLCR值映射到區間(0,1)內,采用如下方式進行映射,β為RLCR值對閾值δ′的影響因子:

β=1-exp(RLCR)

(6)

根據文獻[10],α為平滑系數,α取1.2為經驗值,t為頁面的實際訪問時間。綜合上述的調整過程,頁面訪問時間閾值δ′表達式為:

δ′=αt(1+β)

(7)

3.2 用戶訪問時間閾值

由于用戶閱讀習慣、閱讀速度等不同會導致不同的用戶訪問頁面的時間不同。一般來講,閱讀速度慢的用戶被識別的會話個數會更多。因此,本文提出的這種動態調整時間間隔閾值的方法所設定的時間閾值并不是固定的。對同一用戶進行會話識別時,只需要關注那些時間間隔較大的記錄。

設t0為初始的頁面時間閾值,tnew代表將新頁面添加到當前會話中的時間閾值。平均時間t′表達式為:

t′=(t0+tnew)/2

(8)

為了將這種調整同樣適用于其他頁面,定義調整因子η表達式為:

η=(t′-t0)/t0=(tnew-t0)/(2t0)

(9)

將調整因子適用于所有頁面,δ0表示上次調整后的時間閾值,則調整后的用戶訪問時間閾值δ"表達式為:

δ"=δ0(1+η)=(δ0(tnew+t0)/(2t0)

(10)

3.3 設置時間間隔閾值

當有新的請求記錄加入到當前會話中就按照權重公式重新對時間閾值進行調整。設置時間間隔閾值δ的公式為:

δ=aδ′+(1-a)δ"

(11)

其中系數a表示兩時間閾值間的權重因子。

3.4 DAITS算法

經過數據清理和用戶識別后進行會話識別。由于在之前清洗日志數據的同時將日志記錄按照用戶排序,而且相同的用戶按照訪問時間遞增排序。如果相鄰請求的用戶不同,則認為前一個請求記錄屬于前一個會話且該會話已結束,后一個請求記錄添加到新會話中。對于相同用戶的相鄰請求記錄,首先按照頁面訪問時間閾值的定義計算每個頁面初始的時間閾值,然后根據相鄰請求時長是否滿足訪問時間需不大于當前時間閾值這一條件來判斷是否將其劃分到同一會話中,同時滿足時間閾值調整條件即當前訪問時間超過較大間隔時間則需要根據用戶訪問時間閾值和設置權重公式動態調整當前時間間隔閾值。集合Γ={δ1,δ2,…,δn}表示頁面時間閾值;H={h1,h2,…,hm}集合表示某一用戶請求記錄的集合;S={S1,S2,…,Sk}表示生成的會話集合。DAITS步驟如下:

1)計算初始的頁面時間閾值δ′并初始化集合Γ。

2)從集合H中取出請求hi,如果hi為空則取出下一請求繼續進行下面的判斷，否則進行下一步。

3)計算請求hi的訪問時間tnew,如果tnew≤δj,則將記錄劃分到當前會話Sc中并進行下一步；否則將記錄劃分到新的會話Sc+1中，更新集合Γ并取出下一請求繼續進行判斷。

4)如果tnew滿足時間閾值調整的條件，則按照用戶訪問時間閾值和設置權重公式對集合Γ更新并跳轉到步驟2)取出下一請求繼續進行判斷；不滿足調整條件直接跳轉到步驟2)取出下一請求進行判斷。

由于在清洗日志數據的同時已經將日志記錄按照用戶排序,算法需要將每條記錄取出與上一條記錄進行比較判斷,所以該算法時間復雜度為O(n),其中n為用戶日志訪問記錄長度。DAITS算法流程如圖1所示。

圖1 DAITS算法流程Fig. 1 Flow chart of DAITS

4 實驗與分析

實驗數據集采用美國國家航空航天局(National Aeronautics and Space Administration, NASA)的Web服務器日志。它作為公開的數據集具有易獲取性,可供任何人學習和研究; 而且該數據集的真實可靠性已被許多專業研究人員認可。該數據集記錄了1995年7月— 8月兩個月的訪問日志記錄。由于日志文件數量非常之大,因此選擇每個月份中的一天來進行測試本文算法。

本文DAITS算法將與最常用的基于會話時長(固定閾值30 min)[6]、基于相鄰請求時長(固定閾值10 min)[9]、基于時間間隔[10]和動態調整訪問時間閾值[13]這四種算法進行對比,并探究本文算法中權重因子對精確率和查全率的影響。

DAITS算法將引入精確率和查全率作為評判指標。令A表示真實的會話個數,通過人工標識得出;B表示通過會話識別算法識別出的會話個數;A∩B表示上述兩者共同的部分,即通過算法識別出的真實會話個數, 則算法的精確率和查全率計算公式如下:

precision=(A∩B)/B

(12)

recall=(A∩B)/A

(13)

在第一組實驗中,由于7月12日前后訪問請求數量較平穩同時也比較接近整個月日平均訪問量,具有一定典型性。所以本文將對該天的日志進行分析。7月12日這一天共有92 536條訪問記錄,經清洗后有19 637條記錄。本文算法中平滑系數α取值1.2,較大間隔時間為15 min,A=4 594,不同權重因子下會話識別情況如圖2所示。

從圖2可看出：權重因子a=0.6時精確率和查全率最高; 當進一步精確權重因子取值時,發現在a=0.6附近波動,算法識別出的會話個數并沒有明顯地改變。當權重因子a=0.6時,比較五種會話識別算法的識別結果如表1所示。

在第二組實驗中,用同樣的原理選取8月10日這天的日志記錄。這一天共有61 248條訪問記錄,經數據清洗后有13 169條記錄,A=3 743。比較五種會話識別算法的識別結果如表2所示。

圖2 不同權重因子下的會話精確率和查全率Fig. 2 Precision and recall under different weighting factors表1 第一組實驗下五種算法的比較Tab. 1 Comparison of five algorithms in first group experiment

算法BA∩B精確率/%查全率/%基于會話時長[6]4748357575.2977.82基于相鄰請求時長[9]5240401276.5687.33基于時間間隔[10]5165406078.6188.38動態調整訪問時間閾值[13]4995414282.9290.16DAITS算法4890420185.9191.45

表2 第二組實驗下五種算法的比較Tab. 2 Comparison of five algorithms in second group experiment

實驗結果表明,本文DAITS算法提出的加入合適權重因子的動態調整時間間隔閾值的方法比傳統使用固定閾值的方法在精確率和查全率上分別提高了14.8%和13.2%,比已有的動態調整閾值的方法在精確率和查全率上分別提高了6.2%和3.2%。這也意味著使用這種算法識別會話將更有效率,有利于之后的會話序列建模工作,為大數據平臺的異常檢測提供更有意義的支持。

5 結語

本文所提出的會話識別DAITS算法在一定程度上有助于提高會話識別的效率,其核心原理是基于用戶相鄰請求動態調整時間間隔閾值,能在大數據平臺的異常檢測分析過程中提供可靠的支撐。不足之處在于僅使用一個時間維度還是難以模擬出用戶真實的網絡行為。在模擬用戶會話真實網絡行為這一方面有進一步提升的空間,需要更多的探討與研究,這將是下一步需要開展的工作。

References)

[1] QIN C Y, LIAO C. Session identification based on linked referrers and Web log indexing[J]. Computer Systems Science & Engineering, 2015, 30(2): 141-154.

[2] 周愛武, 程博, 李孫長, 等. Web日志挖掘中的會話識別方法[J]. 計算機工程與設計, 2010, 31(5): 936-938. (ZHOU A W, CHENG B, LI S Z, et al. Method of session identification in Web log mining[J]. Computer Engineering & Design, 2010, 31(5): 936-935.)

[3] SADAGOPAN N, LI J. Characterizing typical and atypical user sessions in clickstreams[C]// WWW 2008: Proceedings of the 17th International Conference on World Wide Web. New York: ACM, 2008: 885-894.

[4] 盧先寧. Web日志挖掘數據預處理算法研究、實現及應用[D]. 北京: 北京郵電大學, 2013. (LU X N. Research, implementation and application of Web log mining data preprocessing algorithm [D]. Beijing: Beijing University of Posts and Telecommunications, 2013.)

[5] ARUN P, IYAKUTTI K. Ontology generation from session data for Web personalization[J]. International Journal of Advanced Networking & Applications, 2010, 1(4): 241-245.

[6] FERNANDEZ F M H, PONNUSAMY R. Data preprocessing and cleansing in Web log on ontology for enhanced decision making[J]. Indian Journal of Science & Technology, 2016, 9(10): 1-9.

[7] JONES R, KLINKNER K L. Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs[C]// Proceedings of the 17th ACM Conference on Information and Knowledge Management. New York: ACM, 2008: 699-708.

[8] NEELIMA G, RODDA S. Predicting user behavior through sessions using the Web log mining[C]// Proceedings of the 2016 International Conference on Advances in Human Machine Interaction. Piscataway, NJ: IEEE, 2016: 1-5.

[9] SPILIOPOULOU M, MOBASHER B, BERENDT B, et al. A framework for the evaluation of session reconstruction heuristics in Web-usage analysis[J]. INFORMS Journal on Computing, 2003, 15(2): 171-190.

[10] 殷賢亮, 張為. Web使用挖掘中的一種改進的會話識別方法[J]. 華中科技大學學報 (自然科學版), 2006, 34(7): 33-35. (YIN X L, ZHANG W. An improved method for session identification in Web usage mining[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2006, 34(7): 33-35.)

[11] 方元康, 胡學鋼, 夏啟壽.Web日志預處理中優化的會話識別方法[J]. 計算機工程, 2009, 35(7): 49-51. (FANG Y K, HU X G, XIA Q S. Improved method for session identification in Web log preprocessing[J]. Computer Engineering, 2009, 35(7): 49-51.)

[12] FANG Y, HUANG Z. An improved algorithm for session identification on Web log[C]// WISM 2010: Proceedings of the 2010 International Conference on Web Information Systems and Mining. Berlin: Springer, 2010: 53-60.

[13] HE X H, WANG Q. Dynamic timeout-based a session identification algorithm[C]// Proceedings of the 2011 International Conference on Electric Information and Control Engineering. Piscataway, NJ: IEEE, 2011: 346-349.

[14] SENGOTTUVELAN P, LOKESHKUMAR R, GOPALAKRISHNAN T. An improved session identification approach in Web log mining for Web personalization[J]. Journal of Internet Technology, 2015, 18(4): 1-7.

[15] YUNG C. Mining massive Web log data of an official tourism Web site as a step towards big data analysis in tourism[C]// ASE BD&SI 2015: Proceedings of the 2015 ASE Big Data & Social Informatics. New York: ACM, 2015: Article No. 62.

This work is partially supported by the Key Project of Fujian Scientific and Technolgical Plan (2016H6007), the City School Cooperation Project of Fuzhou (2016-G-40).

ZENGLing, born in 1993, M. S. candidate. Her research interests include machine learning.

XIAORuliang, born in 1966, Ph. D., professor. His research interests include Web intelligent recommendation system, software engineering, system virtualization.

Sessionidentificationalgorithmbasedondynamictimethresholdofadjacentrequests

ZENG Ling1,2, XIAO Ruliang1,2*

(1.FacultyofSoftware,FujianNormalUniversity,FuzhouFujian350117,China;2.FujianProvincialEngineeringResearchCenterofPublicServiceBigDataMiningandApplication,FuzhouFujian350117,China)

Focusing on the issue of improving the efficiency of session sequence modeling in the anomaly detection analysis of big data platform, a session identification algorithm based on Dynamic Adjustive Interval Time threShold of adjacent requests (DAITS) was proposed. Firstly, the factor of website pages and the average factor of users access time to the page were combined. Then, the appropriate weighting factor was used to dynamically adjust the time threshold. Finally, the session was divided according to whether the time threshold was exceeded. The experimental results show that compared with the traditional methods of using fixed thresholds, the precision of session identification was increased by 14.8% and the recall was increased by 13.2%; compared with the existing methods with dynamic adjustive thresholds, the precision of session identification was increased by 6.2% and the recall was increased by 3.2%.

anomaly detection; session identification; session sequence; adjacent request; dynamic time threshold

2017- 05- 19;

2017- 07- 28。

福建省科技計劃重大項目(2016H6007);福州市市校合作項目(2016-G-40)。

曾令(1993—),女,湖北孝感人,碩士研究生,主要研究方向:機器學習; 肖如良(1966—),男,湖南婁底人,教授,博士,CCF高級會員,主要研究方向:Web智能推薦系統、軟件工程、系統虛擬化。

1001- 9081(2017)11- 3335- 04

10.11772/j.issn.1001- 9081.2017.11.3335

(*通信作者電子郵箱xiaoruliang@163.com)

TP311.1

A