2. 福建省公共服务大数据挖掘与应用工程研究中心, 福州 350117
2. Fujian Provincial Engineering Research Center of Public Service Big Data Mining and Application, Fuzhou Fujian 350117, China
随着大数据技术的飞速发展, 大数据平台架构变得愈发复杂, 而大数据平台对新风险的安全需求也在持续增加。利用异常检测技术保证大数据平台的安全性是一种有效的解决方式, 而对用户日志进行精准的会话识别具有重要的意义:一方面可利用会话异常模型检测出会话异常; 另一方面可根据会话可疑度对用户会话进行模式挖掘。日志挖掘的步骤主要包括数据预处理、模式识别和模式分析, 其中数据预处理是首要阶段。数据预处理主要包括数据清洗、用户识别、会话识别和路径补充。会话识别算法的好坏直接影响着后续对会话序列建模的工作, 从而决定能否为异常检测提供有意义的支持。
目前, 会话识别的方法很多。按照对用户访问行为的不同假设, 会话识别的方法可分为基于时间、基于导航、基于语义这三类方法。基于导航的方法主要分析用户整个访问过程, 并需要寻找访问过程中断开的位置, 并从统一资源定位符(Uniform Resource Locator, URL)中挖掘可以反映用户行为的信息。这类方法主要包括基于引用的方法[1]和基于网络拓扑结构的方法[2]。基于网络拓扑结构的方法比基于引用的方法划分的粒度更小, 但是不同用户在相同时间访问相同网页的后续行为会不同, 因此这类方法不能模仿人的智能。而基于语义的方法为模拟人的智能提供了可能性。这类方法需要先构建语义本体, 再建立用户会话模型, 最后将语义接近到一定程度的请求资源划分到同一个会话中。这类方法可划分为直接使用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(session Identification)表示会话标识;userID(user Identification)表示用户标识;RS(Requests Set)表示和用户在一段时内请求记录的页面集合,RS包含用户请求页面标识符(Page Identification, PID)和请求时间t。用户会话序列S表示为:
$ S = \left\langle {sessionID,userID,\{ (PI{D_1},{t_1}),(PI{D_2},{t_2}),...,(PID_n,t_n)\} } \right\rangle $ | (1) |
对于上述提到的基于时间的两类会话识别方法, 在以会话时长为划分方法中, 设定整个会话时长:
$ Time_{[k]} - Time_{[i]} \leqslant T $ | (2) |
其中T为设定的时间阈值。
在以相邻请求时长为依据的方法中, 根据判断相邻两次请求的时间是否超过这一阈值确定同一用户相邻两次的请求是否属于同一会话:
$ Time_{[t]} - Time_{[t-1]} \leqslant \Delta T $ | (3) |
其中ΔT为设定的时间间隔阈值。
2.4 路径补充路径补充是对识别出的用户会话进行优化的步骤, 目的是使其更加准确地描述用户的浏览请求。由于缓存导致页面缺失的问题, 借助站点信息构建完整的路径。通常可以采用网络拓扑结构和用户的访问顺序进行路径补充。
3 DAITS算法DAITS算法是基于大数据平台的页面访问时间和用户访问时间阈值的会话识别算法。一方面由于每个用户存在个体差异性, 如用户网络速度、阅读速度、上网习惯等一系列因素会导致不同的用户会话时间是不相同的。但是, 如果针对同一个用户来讲其所属的网络环境、个人兴趣及习惯等因素对不同用户来说是相对稳定的。另一方面除去用户个体差异对会话阈值的影响, 会话阈值与页面内容及站点结构也是有关系的。也就是说同一个用户浏览不同的页面所需的时间也是不相同的。所以此算法将同时考虑页面内容和用户差异性并在两者间加入合适的权重, 探究权重因子对会话识别精确率和查全率的影响。
3.1 页面访问时间阈值通常使用页面的链入数和链出数来衡量页面的重要程度。令L1表示链入数即链接到某页面的页面个数, L0表示链出数即某页面包含的链接个数, S表示页面大小。链接内容比RLCR的计算公式表示为:
$ RLCR = ({L_1} + {L_0})/S $ | (4) |
一般情况下, 一个页面的链入比链出重要, 根据文献[13]对它们赋予不同的权值。将公式调整为:
$ RLCR = (0.7{L_1} + 0.3{L_0})/({L_1} + {L_0}) $ | (5) |
为了将RLCR值用于对页面访问时间阈值δ′的调整, 需要将RLCR值映射到区间(0, 1)内, 采用如下方式进行映射, β为RLCR值对阈值δ′的影响因子:
$ \beta = 1-\exp (RLCR) $ | (6) |
根据文献[10], α为平滑系数, α取1.2为经验值, t为页面的实际访问时间。综合上述的调整过程, 页面访问时间阈值δ′表达式为:
$ \delta ' = \alpha t(1 + \beta ) $ | (7) |
由于用户阅读习惯、阅读速度等不同会导致不同的用户访问页面的时间不同。一般来讲, 阅读速度慢的用户被识别的会话个数会更多。因此, 本文提出的这种动态调整时间间隔阈值的方法所设定的时间阈值并不是固定的。对同一用户进行会话识别时, 只需要关注那些时间间隔较大的记录。
设t0为初始的页面时间阈值, tnew代表将新页面添加到当前会话中的时间阈值。平均时间t′表达式为:
$ t' = ({t_0} + {t_{{\text{new}}}})/2 $ | (8) |
为了将这种调整同样适用于其他页面, 定义调整因子η表达式为:
$ \eta = (t' - {t_0})/{t_0} = ({t_{{\text{new}}}} - {t_0})/(2{t_0}) $ | (9) |
将调整因子适用于所有页面, δ0表示上次调整后的时间阈值, 则调整后的用户访问时间阈值δ"表达式为:
$ \delta '' = {\delta _0}(1 + \eta ) = ({\delta _0}({t_{{\text{new}}}} + {t_0})/(2{t_0}) $ | (10) |
当有新的请求记录加入到当前会话中就按照权重公式重新对时间阈值进行调整。设置时间间隔阈值δ的公式为:
$ \delta = a\delta ' + (1-a)\delta '' $ | (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所示。
实验数据集采用美国国家航空航天局(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 = \left( {A \cap B} \right)/B $ | (12) |
$ recall = \left( {A \cap B} \right)/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所示。
实验结果表明, 本文DAITS算法提出的加入合适权重因子的动态调整时间间隔阈值的方法比传统使用固定阈值的方法在精确率和查全率上分别提高了14.8%和13.2%, 比已有的动态调整阈值的方法在精确率和查全率上分别提高了6.2%和3.2%。这也意味着使用这种算法识别会话将更有效率, 有利于之后的会话序列建模工作, 为大数据平台的异常检测提供更有意义的支持。
5 结语本文所提出的会话识别DAITS算法在一定程度上有助于提高会话识别的效率, 其核心原理是基于用户相邻请求动态调整时间间隔阈值, 能在大数据平台的异常检测分析过程中提供可靠的支撑。不足之处在于仅使用一个时间维度还是难以模拟出用户真实的网络行为。在模拟用户会话真实网络行为这一方面有进一步提升的空间, 需要更多的探讨与研究, 这将是下一步需要开展的工作。
[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-935. (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.) http://cdmd.cnki.com.cn/Article/CDMD-10013-1013241499.htm |
[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. DOI:10.1287/ijoc.15.2.171.14445 |
[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. |