2016, Vol. 37
2. 沈阳工业大学 管理学院，辽宁 沈阳 110023
3. 东北大学 计算机科学与工程学院，辽宁 沈阳 110819
2. Management College, Shenyang University of Technology, Shenyang 110023, China
3. School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
Web挖掘技术[1]因为具有改善网站服务质量、提高用户满意度以及提供个人化服务等特点，而受到企业界和学术界的日益关注.目前的Web用户浏览情况挖掘就是对网站的日志记录进行分析，从而提取用户浏览网站的特征信息[2-3].目前已有一些学者提出了针对Web用户浏览行为分析的数学模型.文献[4]利用马尔科夫模型来分析预测用户下一个可能浏览的网页.文献[5]提出了两个模型来研究Web浏览行为的特征化分析，以Morse’s 模型及马尔科夫模型分别对网页访问及使用的情况予以模型化分析.文献[6-7]利用高阶马尔科夫(Markov)模型来预测用户浏览行为，然而，当所使用的阶数n越高，计算代价也越高.文献[8]提出了一种使用贝叶斯(Bayesian)分类算法和领域本体过滤中文网页的方法，该方法可以区分相同领域中的不同网页并可兼顾网页过滤的实时性.虽然上述研究在Web用户浏览行为分析和预测方面取得了一些成果，但是也存在计算代价高、数据预处理时间长、预测准确率低等问题.
针对上述问题，依据Web网站的分层结构特点[9]来进行用户浏览行为预测.首先，提出了基于Hash表的反向索引结构(inverted index structure based on Hash table，IIS-HT)，并通过IIS-HT来提升数据预处理效率.然后，针对Web网站的分层特性，并结合马尔科夫模型与贝叶斯定理，提出了基于马尔科夫模型与贝叶斯定理的分层预测模型(hierarchical prediction model based on Markov model and Bayesian theorem,HPM-MMBT).在HPM-MMBT中，将用户的浏览行为依据网站的分层特点分为网页类别(分层-1)和网页(分层-2).在网站中的每个不同的类别都会包含许多网页，而网页类别的数量一定小于网页的数量，所以相较各网页类别之间的转换概率相对稳定，因此在分层-1可以利用马尔科夫模型过滤出用户最可能浏览的网页类别.当可能的网页类别被过滤出之后，在分层-2以贝叶斯定理作为预测方法，从而找出用户最有可能浏览的网页.最后，利用网站日志文档[10]对模型进行了相关测试.
1 基于IIS-HT的数据预处理方法在数据预处理阶段，可以利用反向索引结构(如图 1所示)进行网站日志数据的预处理.在反向索引结构中，每读取一条日志记录，就会获得一个用户的IP地址，将该IP地址作为搜索关键字，在用户列表(user list)中查找与该IP地址对应的位置，然后将该网页信息加入到网页信息列表(page list)中.显然，反向索引结构易于实现；但是，当网站日志记录很大的时候，用户列表将会变得很长，进而导致查询和对比开销变得极为庞大.
|
图 1 反向索引结构 Fig.1 Inverted index structure |
为了解决上述问题，将Hash链表和反向索引结构结合，设计了基于Hash表的反向索引结构，如图 2所示.IIS-HT包括两部分：第一部分是由用户列表和与之连接的Hash表组成，每读取一条日志记录时，就会获得一个用户的IP地址，将该IP地址的每一个字符转换为ACII码并累加求和，并对该求和结果进行模运算，最后将运算结果作为Hash表的索引值；在相对应的Hash索引值之下找到用户列表，然后进入IIS-HT的第二个组成部分，即反向索引.在该反向索引结果中，搜索和比较用户IP，如果该IP已经存在于用户列表中，则在网页列表中增加该网页信息，否则将该IP地址加入到用户列表中.
|
图 2 基于Hash表的反向索引结构 Fig.2 Inverted index structure based on Hash table |
结合马尔科模型和贝叶斯定理，本文所设计的面向Web用户浏览行为的预测模型架构如图 3所示.其中S是网页相似度矩阵，P是马尔科夫转换矩阵，R是相关性矩阵.
|
图 3 HPM-MMBT模型 Fig.3 HPM-MMBT model |
首先，依据Web网站的分层属性，将其分为两类：即网页类别(如某个网站的新闻类网页、娱乐网页等类别)和网页.本文将网页类别定义为分层-1，网页定义为分层-2.在网站中，不同的网页类别会包含很多不同的网页，但是网页类别的数量是明显小于网页数据量的.因此，网页类别之间的转换是相对稳定的，所以在分层-1可以利用马尔科夫模型对用户可能浏览的网页类别进行过滤.依据t-1和t-2时刻用户浏览网页类别的情况，就可以对t时刻用户浏览网页类别的情况进行预测.在预测出用户在t时刻可能浏览的网页类别后，在分层-2可以利用贝叶斯定理并结合用户在t-1时刻的状态来预测用户在t时刻可能浏览的网页.
2.2 相关定义定义1是本文用到的相关定义的描述.
定义1
|
depth表示网页类别的深度(即网页类别目录的深度)，hierarchy表示depth的观测值，即那一层网页类别需要被观测.如果depth小于等于hierarchy，则hierarchy等于depth；否则，hierarchy为设定值.
对于某用户的日志记录集合R={Record1,Record2,…,Recordi,…,Recordm}，它保存了m条用户访问记录，每一个访问记录Record都是一个访问序列，该访问序列包含了n个被用户依时间顺序浏览的网页，即Recordi = {pagei1,pagei2,…,pagein}.Recordi代表了用户i的浏览网页的情形.当hierarchy的值为l时，根据Recordi中各网页所属的类别，给出Recordi的定义：
定义2
|
Recordi表示用户浏览网页类别和具体网页的情况，categoryil表示第l个网页的类别.
2.3 模型构建 2.3.1 网页相似度矩阵的建立首先，需要获得用户浏览网站的日志文件.之后，当hierarchy=l时，假设有k个网页类别.因此，当用户在l层网页类别浏览时，可以从m个用户浏览记录中获得m×k矩阵.在该矩阵中，行向量为：Vicol=＜C1,i,C2i,…，Chi,…,Cmi >.Vicol表示网页类别i被第m个用户浏览过.如果Vicol中网页类i被第h个用户浏览过，则Chi=1，否则Chi=0.
本文利用集合相似度式(1)和欧几里得距离式(2)来计算两个不同网页类别的相似度.
|
(1) |
|
(2) |
将式(2)进行标准化，得到式(3):
|
(3) |
为式(1)和(3)赋予不同权重值，得到式(4):
|
(4) |
其中，WSS+WD=1，WSS,WD >0.
在获得2个网页类别的相似度后，可以得到相似度矩阵S：
|
Sij是通过式(4)计算得出的.
2.3.2 马尔科夫转换矩阵的建立与相似度矩阵S的建立方法相类似，同样是利用用户的浏览行为日志记录来建立一阶和二阶马尔科夫转换矩阵.
首先建立一阶马尔科夫转换矩阵，如式(5)所示.二阶以及n阶马尔科夫转换矩阵可以通过一阶马尔科夫转换矩阵得到.
|
(5) |
在矩阵P中，元素Pij代表从一个网页类别转向另一个网页类别的概率(例如，从娱乐类网页转向体育类网页的概率).在式(5)中，分母表示从网页类别i转换到全部k个网页类别的总次数，分子表示所有从网页类别i转换到网页类别j的总次数.
2.3.3 相关性矩阵的建立将相似度矩阵S和n阶马尔科夫转换矩阵Pn中的对应位置相乘就可以获得一个相关性矩阵Rn，如式(6)所示.
|
(6) |
在相关性矩阵Rn中每一个元素都表示两个网页类别直接的相关程度.
2.3.4 用户浏览行为预测方法依据2.1节的分层预测模型，在分层-1可以过滤出用户下一步可能访问的网页类别集合；在分层-2，可以利用贝叶斯定理对网页类别集合中的网页进行预测，并获得可能被用户浏览的网页结合.
为了减少预测过程中所花费的代价开销，依据2.1节提出的分层预测模型框架，从分层-1和分层-2进行分类预测.
1) 分层-1中的网页类别预测.在分层-1中，主要是对用户浏览的网页类别进行预测.如图 4所示，利用网页类别集合Ct-1和Ct-2，可以得到Ct的预测集合θ.在分层-2中只对预测集合θ中的网页进行预测，进而减少分层-2中的相关代价开销.
|
图 4 分层-1中的网页类别预测 Fig.4 Category prediction in level one |
在分层-1中，可以通过相关矩阵获得可能的网页类别集合.RCt-nn是相关矩阵R的Ct-n列的列向量＜Ct-n,1,Ct-n,2,…,Ct-n,k >.当选择n=1和n=2时，可得RCt-11和RCt-22.取出top-r1个网页类别构成集合θ.
假设一个Web站点有3个网页类别，且n =1和n=2时，则可以得到到3×3的相关矩阵R1和R2.当Ct-1 =C2和Ct-2 = C1时,可以得到列向量RC21=＜0.13,0.18,0.27>和RC12=＜0.16,0.23,0.12>.当取出前top-r1(r1=2)个相关网页类别时,只有R1中的C3(0.27) 和R2中C2(0.23)满足要求.因此，在分层-1中的预测网页类别集合θ={C2,C3}.
2) 分层-2中的网页预测.如图 5所示，在分层-2中,利用贝叶斯定理计算下一个可能浏览的网页pageb，并获得最可能被用户浏览的前top-r2页面.预测的网页集合τ将作为分层-2的最终的输出结果.
|
图 5 分层-2中的网页预测 Fig.5 Page prediction in level two |
由于在分层-1中已经完成了网页类别的预测工作，因此pageb一定属于网页类别集合θ.下面，定义Pθ作为所有可能的候选网页集合.
Pθ={pagebj|category of pagebjmust belong to predicted category set θ,1≤j≤r}.将Pθ代入贝叶斯定理中计算,得到式(7)：
|
(7) |
同时，还可以得到候选网页集合τ:
τ={pagebj|pagebj是Pθ中通过贝叶斯定理计算得到的前top－r2个网页}.因为已有的网页类别集合θ={C2,C3}，因此在分层-2中，只需要考虑这2个网页类别集合中的网页.
在分层-2中，候选网页结合Pθ为
|
选择1995年7月NASA网站的日志文件[10]作为测试数据，该日志文件大小为205.2 MB，经过预处理后，该日志文件的具体统计信息情况如表 3所示.
|
表 1 日志文件信息 Table 1 Information of log file |
依据实际中的不同应用情况，本文将上述测试数据集分为两类：大数据集和小数据集；其中大数据集合包含1 000条日志记录，小数据集合包含100条日志记录.
在本文中，使用预测准确率(prediction accuracy，PA)来评估模型的实际应用效果.PA的计算公式为
|
(8) |
分别从大数据集合和小数据集合两个方面，对HPM-MMBT的预测准确率进行测试，并与仅采用Markov方法和仅采用Bayesian定理的方法进行对比分析.设定top-r1=10，top-r2=10.
1) 采用小数据集测试时的预测准确率分析.如表 2所示，当hierarchy=1~2时,HPM-MMBT的预测准确率PA比Bayesian方案和一阶Markov方案略高.当hierarchy= 3~5,HPM-MMBT的预测准确率PA比Bayesian方案和一阶Markov方案略低.
如表 3所示，在分层-1中获得了网页类别预测集合θ之后，随着网站层数的增加，在分层-2中的每一层待预测网页的数量远小于每一层的网页总数，特别是在层数= 3~5时,预测的集合Pθ中的网页数量分别仅占每一层网页总数量的15.49%,8.33% 和8.82%.
从表 2，表 3可知，HPM-MMBT在保证一定预测准确率的情况下，可以减少预测范围，提高预测效率.
|
|
表 2 采用小数据集测试时的预测准确率 Table 2 Hit-ratio to small data |
|
|
表 3 采用小数据集测试时的候选网页情况 Table 3 Candidate page set to small data |
2) 采用大数据集测试时的预测准确率分析.如表 4所示，当hierarchy=1~2时,HPM-MMBT的预测准确率PA比Bayesian方案和一阶Markov方案略高.当hierarchy= 3~5,HPM-MMBT的预测准确率PA比Bayesian方案和一阶Markov方案略低.
|
|
表 4 采用大数据集测试时的预测准确率 Table 4 Hit-ratio to large data |
如表 5所示，在分层-1中获得了网页类别预测集合θ之后，随着网站层数的增加，在分层-2中的每一层待预测网页的数量远小于每一层的网页总数，特别是在层数= 3~5时,预测的集合Pθ中的网页数量分别仅占每一层网页总数量的15.49%,8.33% 和8.82%.特别是在层数=3~5时,预测的集合Pθ中的网页数量分别仅占每一层网页总数量的13.91%，11.49%，11.69%.
|
|
表 5 采用大数据集测试时的候选网页情况 Table 5 Candidate page set to large data |
通过上面的实验分析可知，在适当的预测准确率前提下，模型能够有效地减少在预测时所需的候选网页数量并大幅提升预测效率.
4 结语本文首先给出了基于IIS-HT的数据预处理方法，并以此为基础构建了HPM-MMBT模型.对HPM-MMBT模型进行实验分析，结果表明，该模型的预测准确率与Bayesian方案和一阶Markov方案基本一致，但是在预测时所需的候选网页数量减少，实现了大幅度提升预测效率的目的.
| [1] |
Li M J, Yu X M, Ryu K H. MapReduce-based web mining for prediction of web-user navigation[J].
Journal of Information Science, 2014, 40 (5) : 557 –567.
( 0)
|
| [2] |
Torres S D, Hiemstra D. Analysis of search and browsing behavior of young users on the web[J].
ACM Transactions on the Web, 2014, 8 (2) : 1 –54.
(0)
|
| [3] |
刘晋佩, 曾建平. 一种基于蚁群算法的用户浏览路径推荐方法[J].
厦门大学学报(自然科学版), 2014, 53 (4) : 465 –468.
( Liu Jin-pei, Zeng Jian-ping. A recommendation approach to users’ browsing path based on ant algorithm[J]. Journal of Xiamen University(Natural Science), 2014, 53 (4) : 465 –468. ) ( 0)
|
| [4] |
Jespersen S,Pedersen T B,Thorhauge J.Evaluating the Markov assumption for web usage mining[C]// Proc of the 5th ACM International Workshop on Web Information and Data Management.New York:ACM,2003:82-89. (0)
|
| [5] |
Dhyani D,Bhowmick S S,Ng W K.Modelling and predicting web page accesses using Markov processes[C]// Proc of the 14th International Workshop on Database and Expert Systems Applications.Piscataway:IEEE,2003:332-336. (0)
|
| [6] |
Awad M A, Khalil I. Prediction of user’s web-browsing behavior[J].
IEEE Transactions on Systems,Man,and Cybernetics, 2012, 42 (4) : 1131 –1142.
(0)
|
| [7] |
Jorgensen Z, Yu T. A popularity-based prediction model for web prefetching[J].
IEEE Computer, 2003, 36 (3) : 63 –70.
(0)
|
| [8] |
刘杰, 骆力明, 吴宇航, 等. 一种中文领域网页过滤方法[J].
北京理工大学学报, 2014, 34 (5) : 533 –536.
( Liu Jie, Luo Li-ming, Wu Yu-hang, et al. A method of filtering Chinese webpage[J]. Transactions of Beijing Institute of Technology, 2014, 34 (5) : 533 –536. ) ( 0)
|
| [9] |
Liu N,Yang C C.Extracting a website’s content structure from its link structure[C] // Proc of the 14th ACM International Conference on Information and Knowledge Management.New York:ACM,2005:345-346. (0)
|
| [10] |
The Internet Traffic Archive. 2008-04-09.http://ita.ee.lbl.gov/. (0)
|