网络出版时间：2011-08-04 16:03
网络出版地址：/kcms/detail/11.2127.TP.20110804.1603.005.html
2011-5-11
程苗1 陈华平2
Cheng Miao1 Chen Huaping2
1.中国科学技术大学管理学院，合肥230026
2.中国科学技术大学计算机科学与技术学院，合肥230026
1. College of Management, University of Science and Technology of China, Hefei, 23006, China
2. College of Computer Science and Technology, University of Science and Technology of China, Hefei, 23006, China
The Algorithm of Discovering Preferred Browsing Paths
based on Cloud-Computing
Abstract: Mining user preferred browsing paths from web logs is an important research topic. The
current mining algorithms are focus on users’ browsing frequency, neglect an important problem
of whether users are interested in the frequent path or not. On the analysis of the present
algorithms for mining user browsing patterns, combined with web topology structure, revise the
measures of users’ preferred browsing paths which based on browsing frequency, and present a
concept of useful preference, remove the bad impact of mining due to pages’ place and links;
Meanwhile, due to the problem of current mining system’s computational capacity on single node
is not enough, by the advantage of Cloud Computing ‘s distributed processing and virtual
technology, present a method of data processing based on Cloud Computing to mining users’
preferred browsing paths. The result shows, this algorithm is better than one which based on
frequency when mining a number of web log, whatever accuracy or efficiency
Key words: preferred browsing paths; Cloud Computing; web usage mining; web log,
摘 要：从web日志中挖掘用户浏览偏爱路径是一个重要的研究课题。目前的挖掘算法注重客观访问频度， 忽略了用户对这一频繁访问路径是否感兴趣。作者在分析目前用户偏爱路径挖掘算法存在的问题的基础上，
结合网站拓扑结构图修正基于频度的用户偏爱路径的衡量标准，提出了有用偏爱度的概念，从而剔除由于
页面放置和链接等因素对挖掘的影响；同时针对目前基于单一节点的挖掘系统的计算能力不足的问题，利
用云计算的分布式处理和虚拟化技术的优势，给出了一种基于云计算的数据处理方法，在此基础上挖掘用
户浏览偏爱路径。实验表明，该算法针对大数据量的日志进行挖掘，准确率和效率比普通基于频度进行用
户浏览偏爱路径挖掘的算法有所提高。
关键词: 浏览偏爱路径; 云计算; web使用挖掘;web日志
1.引言
Web用户浏览偏爱路径挖掘通过分析web日志记录发现用户访问规律，已成功应用到个性化推荐、系统改进以及商业智能等方面[1]。目前用于挖掘用户浏览偏爱路径的算法有最大向前序列法、参考长度法和
树型拓扑结构法等[2]。
这些算法都存在以下两方面的问题：首先是单纯地考虑浏览频度，简单地认为用户的浏览频度就反应了用户的访问兴趣，这很不精确[2]；其次，web上分布、异构、动态和海量的数据特点，使得传统集中式的
挖掘方法已经无法满足海量日志数据处理的需求。
借助云计算具有海量数据处理和存储能力的特点，本文提出了一种基于云计算的用户浏览偏爱路径挖掘算法。该算法结合网络拓扑结构图修正基于频度的用户偏爱路径的衡量标准，剔除由于页面放置和链接
等因素对挖掘的影响。本文从提出的有用偏爱度概念出发，借助MapReduce编程思想，将用户浏览偏爱路
径挖掘算法的数据预处理阶段放在分布式并行环境中进行：即在数据预处理时，将海量数据集划分成若干
基金项目：博士点基金项目（200803580024）、创新研究体科学基金（70821001）
作者简介: 程苗(1986－)，女，硕士研究生，研究方向为云计算，数据挖掘；陈华平(1965－)，男，教授，博士生导
师。E-mail:
子块，每个子块分别在网络中不同的处理机上并行处理。最后在Hadoop集框架下进行了实验，验证了云计算环境下，结合网络拓扑图修正的用户偏爱路径挖掘算法的高效性。
2.有用偏爱度定义
只使用用户访问频度来衡量用户的访问兴趣显然是很不准确的，文献[2]利用了一个适合网站浏览的相对访问率的概念，提出了支持-偏爱度，充分考虑了基于网站特殊结构约束条件下真正的强度与平均的
强度之比。但这种方法没有网站的拓扑结构，因为如果挖掘出来的一条用户偏爱路径恰好是网络拓扑图中的一条连续的路径，那么这条访问路径的频度高显然是因为用户顺着网络链接点击下来的，并没有真正的反映用户的访问兴趣，不是真正有用的信息。因此，本文结合网络拓扑图，引入了有用偏爱度的概念，它削弱了具有直接链接关系的页面之间的影响。
2.1网络拓扑图[3]
一个网站是由大量网页组成的集合，网页是一种特殊的资源，由超链接联系在一起。文献[3]用有向图表示网络拓扑结构，它极大的反映了设计者的思路。图1是一个大型门户网站的三级网络拓扑结构。
图1网络拓扑图
由图1可知，有向图由两种元素构成：结点和有向边。其中结点表示页面，有向边表示页面间的链接关系。用户由某一个页面进入（通常是主页），通过网页上的链接选择访问的下一页面。如果网络拓扑中的两个结点相距较远，表明按照网站设计者的意图这两个结点所代表的页面间的关联性是较低的，若从用户访问日志中发现了它们是一条可信度较高的频繁访问路径，显然用户的感兴趣度是非常高的。根据这个规律，网站设计者就可以在这两个页面之间增添链接或者进行网站拓扑重构，以减少用户的点击次数和等待时间，从而提高用户的满意程度。例如，E和G是相距较远的网页，E需要经过页面B、A、C才能到达G。如果我们在web日志中发现E->B->A->C->G是一条用户浏览偏爱路径，则得到的这条频繁路径是有用的，可以帮助网站设计者在E页面中添加到G页面的链接，从而方便用户，增加了用户的满意度。
2.2Web站点访问矩阵
Web日志文件是web使用挖掘中一个重要的数据来源，用户对网站的访问信息基本都记录在web日志文件中，常见的web日志一般有两种格式：CLF和ECLM，常见的web日志一般采用ECLM日志模式。Time ／Data表示Web服务器接收到用户请求的时间；URL表示用户请求访问页面的URL地址；Referer是指引用页(指向被请求文件的页面)的URL，如果用户直接输入URL进行访问或利用书签进行访问，则该栏为空；Agent是指用户浏览所用的操作系统和浏览，它的结构如表1所示[1]。
表1 ECLM日志模式结构
在Web日志中，并不是所有的原始数据对分析都是必要的，我们在挖掘用户浏览偏爱路径时，只关心请求发出的时间、访问页面以及参照页面，因此需要对原始数据进行预处理，删除与会话无关的信息以及噪音数据。对于一个大型的门户网站，每天访问量会达到几亿人次，产生的web日志文件会达到几十个GB，甚至上百个GB，因此针对海量日志文件的预处理其实也是应当重点研究的问题。本文采用了基于云计算的MapReduce机制完成对海量日志文件的并行预处理，达到了很好的效果。
参照文献[1]，预处理完的日志表示为L=( Referer，URL)的集合，其中，Referer 表示引用页，URL 表示访问的网页，每个(Referer，URL)看成是一个浏览子路径。本文采用访问矩阵+三元组的方式来存放预处理完的日志，其矩阵如表2所示，三元组如表3所示。
②其中第k (k =1，2，…，n )种选择的选择偏爱度(preference)可定义为:
i
ij
ij
S
P
/ (2)
③支持一偏爱度定义为:
ij
ij
ij
P S
P ˆ (3)
其他的很多论文中也大体采用类似的衡量标准。通过在海量的数据集上进行实验，发现这种针对用户访问兴趣度的衡量标准，在针对大型门户网站的数据挖掘时，会由于没有考虑网站的拓扑结构，而出现极大的误差。
假设图1为一个门户网站的部分主干三级拓扑结构，其他的略去。A 为网站的首页，B 为其中的新闻频道，C 为旅游频道，D 为交流频道。可以从表2的访问矩阵看出，在主干中的页面的进出访问率都是远高于其他页面的。比如(NULL,A)=38，这是因为A 为首页，大部分会话开始的用户都会首先访问A 页面；（A,B）=31，因为B 是主干，访问频率当然高。这样的由于网站拓扑造成的高频数据，虽然也反映了用户的偏爱路径，但是，也造成了奇异数据。这些数据势必会造成按照公式(1)-(3)计算出来的平均支持度、选择偏爱度、支持一偏爱度的严重偏移，给后面的挖掘过程造成误差。
因此，本文提出有用偏爱度的概念。其计算过程分成以下几步。
①权值网络拓扑图。在传统的网站网络拓扑图的边上引入权值W ij ，表征该条边的访问路径的有用度。本文认为，网络拓扑的主干路径上的边有用度低，而远离主干路径上的边有用度高。这是因为网
络拓扑是一个由链接连接起来的资源集．在网络拓扑中直接或间接相连的资源集(Web 拓扑概率较高)在用户访问时出现重复访问路径的可能性较高，显然，这些特别高频路径对于网络拓扑设计者以及商家是不大感兴趣的。而在拓扑中不相连或相距较远的资源集(We 拓扑概率较低)在用户访问时重复访问路径的可能性较低，它们的适当高频的路径恰是网络拓扑设计者所期望得到的用于改善用户服务质量和提高网络性能的有用知识，也是商家投放信息的指导。改进后的网络拓扑图如图2所示。
图2权值网络拓扑图
图中的权值可以作为一个参数，通过海量数据集训练得到。本文在这里不做详解，可以根据经验设定。总体来说，越是主干的地方，权值越低，表示该路径的有用度越低。
②有用偏爱度。
为了避免在挖掘用户浏览偏爱路径时，产生主干路径上的高频路径这类不太有趣的知识，我们给网络拓扑中的每条边都引入有用权值，从而平衡主干路径的奇异数据。
本文将平均有用支持度定义为：
n
j ij
ij
i
n
S
W
S
1
/)(
(4)
本文将有用偏爱度定义为：
i
ij
ij
ij S
S
W
P /)
(2
(5)
3. 基于云计算的数据预处理
门户网站的web 日志量很大，这种网站用户偏爱路径挖掘对挖掘模型更高的要求体现在高速的数据预
处理。因此，利用云计算的分布式处理和MapReduce编程模型[4]，提出基于云计算的数据预处理。
3.1MapReduce编程模型
MapReduce是一个用以进行大数据量计算的编程模型，同时也是一种高效的任务调度模型，它将一个任务分成很多更细粒度的子任务，这些子任务能够在空闲的处理节点之间调度，使得处理速度越快的节点处理越多的任务，从而避免处理速度慢的节点延长整个任务的完成时间。执行一个MapReduce操
作需要5个步骤：输入文件、将文件分割并分配给多个worker并行执行、本地写中间文件、合并中间文件、输出最终结果。具体流程如下[4]：
① MapReduce库将输入文件分成大小相等的M份，并在集的不同机器上执行程序的备份。
② Master节点的程序负责出空闲的worker节点并为它们分配子任务（M个Map子任务和R个Reduce 子任务）。
③被分配到Map子任务的Worker节点读入已经分割好的文件作为输入，经过处理后生成key/value对，并调用用户编写的Map函数，Map函数的中间结果缓存在内存种并周期性地写入本地磁盘。
④这些中间数据通过分区函数分成R个区，并且将它们在本地磁盘的位置信息发送给Master，然后再由Master将位置信息发送给执行Reduce子任务的节点。
⑤执行Reduce子任务的节点从Master获取子任务后，根据位置信息调用map工作节点所在的本地磁盘上的中间数据，并利用中间数据的key值进行排序，将具有相同键的对合并。
⑥执行Reduce子任务的节点遍历所有排序后的中间数据，并传递给用户定义的reduce函数。Reduce 函数的结果将被输出到一个最终的输出文件。
⑦当所有的map子任务和reduce子任务完成时，Master节点将R份Reduce结果返回给用户程序，用户程序将这些数据合并得到最终结果。
基于MapReduce编程模型编写分布式并行程序非常简单，我们只需要实现Map和Reduce函数，以及如何将问题进行分割，区分操作是Map操作还是Reduce操作，而并行编程中的其他复杂问题，如分布式存储，工作调度，负载平衡，容错处理，网络通信等，都由MapReduce框架负责处理。
3.2应用MapReduce的web日志预处理
常见的Web日志一般采用ECLM日志模式，可以看出其中包含一些对用户偏爱路径挖掘无用的信息，因此，对Web日志在提交给挖掘算法前的数据预处理应该包括数据清洗、频度扫描两部。本文充分利用MapReduce模型的高度并行，建立了如图3所示的数据处理管道。这个数据处理管道可以做成中间件，供其他挖掘系统调用。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议