基于Hadoop的Web日志预处理的设计与实现

发布于:2021-06-11 11:04:51

东信北邮信息技术有限公司专栏
EASTCOM-BUPT I N F O R M AT I O N
TELECOM

TECHNOLOGY
ENGINEERING

CO.,

LT D .

COLUMN
S TA N D A R D I Z AT I O N

TECHNICS AND

基于Hadoop的Web日志预处理的设计与实现*
宋莹1,2,沈奇威1,2,王晶1,2 (1 北京邮电大学网络与交换技术国家重点实验室,北京 100876;2 东信北邮信息技术有限 公司,北京 100191)
摘 要  Web日志预处理是Web日志挖掘的重要步骤,是通过Web日志获得准确信息的前提,直接影响后续的挖掘 算法精确性。本文针对海量Web日志,提出并基于分布式计算*台Hadoop实现了一种改进的Web日志预处 理方法。通过Hadoop*台与单机的性能对比,证明了Hadoop进行Web日志预处理的高效性。 关键词 Web日志预处理;Web结构;map/reduce 中图分类号 TN915 文献标识码 A 文章编号 1008-5599(2011)11-0084-06

1

引言
随着 Internet 的迅猛发展, Web 上的信息急剧膨胀,

施有效挖掘算法的前提,数据预处理环节非常关键。 Web 日志包含了丰富和动态 Web 页面的访问和使 用信息,这为 Web 日志挖掘提供了丰富的资源。但是 如何对 Web 日志进行高效可靠的数据预处理具有极大 的挑战性 [4]。 Hadoop 是 Apache 下的一个开源分布式计算*台, 它提供简单的编程模型,对大量数据进行分布式处理。 Hadoop 一般运行在由大量普通计算机组成的集群上。 Hadoop 框架的核心是分布式文件系统 HDFS 和 Map/ Reduce。HDFS 创建数据块的多个副本,并将其分布存 储在集群的数据节点(Data Node)上,实现可靠而快 速的计算。Map/Reduce 是一个用于大数据量并行计算 的编程模型,同时也是一种高效的任务调度模型,它将 一个计算任务分成很多细粒度的子任务,并在空闲的处 理节点(Task Tracker)之间进行调度,使处理速度快

而其中蕴含的信息未能得到充分的挖掘和利用。因此, Web 数据挖掘成为数据挖掘技术研究的热点。Web 数 据挖掘主要分为 3 类 : Web 内 容 挖 掘(Web Content Mining) ,Web 结 构 挖 掘(Web Structure Mining) 和 Web 日志挖掘(Web Usage Mining) 。 Web 日志挖掘就是对用户访问 Web 时的访问记录 进行数据挖掘。 通过分析和研究日志的规律 , 实现聚类、 分类、关联规则、序列分析等 Web 日志挖掘算法 。 预处理阶段、 Web 日志挖掘过程一般分为 3 个阶段 [3]: 挖掘算法实施阶段、分析阶段。数据预处理的目的就是 将原始日志经过处理形成用户的会话文件,为挖掘算法 实施阶段作好数据准备。作为整个挖掘过程的基础和实
收稿日期 :2011-10-13
[2] [1]

* 基金项目: 国家自然科学基金 (No.61072057,60902051); 国家 973 计划项目 (No.2012CB315802);中央高校基本科研业务费专项资金 (BUPT2009RC0505); 国家科技重大专项(No.2011ZX03002-001-01,移动互联网总体架构研究) 。

84
万方数据

·2011年 第11期·

东信北邮信息技术有限公司专栏
EASTCOM-BUPT I N F O R M AT I O N TECHNOLOGY CO., LT D . COLUMN
电信工程技术与标准化

的节点处理更多的任务 [5]。同时 Map/Reduce 也会针对 失败的任务重新分布处理,提供其高可用性。 本文采用高可拓展性的 Hadoop 分布式计算*台, 通过对某典型书籍阅读网站的日志进行研究和分析,设 计与实现了一个基于 Hadoop 的 Web 日志预处理方法, 方便行之有效的进行后续 Web 日志挖掘工作,进而指 导页面的布局改造,优化网站的总体架构,提升网站的 流量,增加网站的收益。

示(省略部分空字段) 。 2.2 Web 日志预处理 Web 日志记录了用户对网站的每一次点击访问,但 由于种种原因,Web 日志中有很多记录是多余的、不完 整或错误的,这对数据挖掘不但无用,还会增加处理的 复杂性,甚至产生错误结果。因此在进行数据挖掘之前 必须对数据进行预处理,以消除数据的不完整性、噪声 和不一致性。 2.2.1 数据清洗

2

设计思想
Web 日志挖掘首先要对日志中的原始数据进行采集

数据清洗是指根据需求,对日志文件进行处理,删 除与挖掘任务不相关的数据并合并某些记录,对用户请 求页面时发生错误的记录进行适当的处理等等。 当用户请求一个网页时,与这个网页有关的图片、 音频等信息会自动下载,并记录在日志文件中,由于图 片、音频等不是用户显式请求的,因此可以把日志中文 件的后缀为 gif、jpg、jpeg、wav 等的记录删除。后缀 名为 cgi、js 等的脚本文件对后面的分析处理没有任何 影响,也应该删除。 常见的页面请求方法包括 GET、POST 和 HEAD。 由于只有 GET 方法反映了用户的访问行为, 因此本文 只保留 GET 方式的记录。 2.2.2 会话识别 会话就是指一个用户从进入网站到离开网站所访问 的一系列页面。会话识别的任务就是将每一个用户的每一 个会话识别出来。本文结合使用基于引用和基于页面访问
含义 用户 IP 地址(USIP) 用户 ID(USID) 请求时间 (Time) 请求方法 (Method) 请求页面 (URL) 传输协议版本 (Version) 返回的 Http 状态标识 (Status) 服务器发送字节数 (Byte) 用户浏览的上一页 (ReferURL) 浏览器操作系统 (BrowserOS)

和预处理,其任务是将原始日志数据转换成适合数据挖 掘和模式发现所需的会话文件。传统的 Web 日志预处 理主要包括数据清洗、用户识别、会话识别和路径补充。 我们的日志中含有用户 ID 字段,每个用户 ID 标识一个 用户,故而省去用户识别步骤。并结合路径补充进行适 当的会话拆分。 2.1 Web 日志采集 在进行 Web 日志预处理和挖掘之前,首先要进行 数据采集,确定合适的数据源。Web 用户访问数据可以 服务器端、客户端或代理服务器端进行收集。本文的数 据源为来自服务器端的 Apache 日志文件,它详细记录 了该书籍阅读网站用户的访问行为,日志格式如表 1 所
表1 日志内容 118.229.156.162 songying 21/Aug/2011… GET /reg_loginEnv.jsp;… HTTP/1.1 200 64 /index.jsp;… Mozilla/6.0 (…) Web 日志格式

时间间隔的方法完成会话识别,识别过程可描述如下 : (1)对同一用户,按照页面访问时间排序,依次处 理访问页面。 (2)如果用户访问的页面为网站主页,则认为这是 一个新的会话。 (3)检查访问页面的 ReferURL,如果 ReferURL 为网站主页,且用户访问的上一页不是网站主页,也认 为这是一个新的会话 ;如果 ReferURL 为空,且该记录 与上一条记录的访问时间间隔大于 10s[6],也认为该记录 为一个新的用户会话。

·2011年 第11期·

85

万方数据

东信北邮信息技术有限公司专栏
EASTCOM-BUPT I N F O R M AT I O N
TELECOM

TECHNOLOGY
ENGINEERING

CO.,

LT D .

COLUMN
S TA N D A R D I Z AT I O N

TECHNICS AND

(4)设定相邻页面的访问时间阈值 δ 。对于一个用 户访问序列中的两条相邻访问记录,只有当 t i +1-t i <δ i 的时候,才认为两次访问属于同一个会话。现有的会话 识别方法一般将 δ 设为 10min。由于本文的实验数据 来自一个书籍阅读网站,导航页与书籍阅读页的信息 含量差别很大,鉴于正常人的阅读速度*均为每分钟 200 ? 240 字 ,而该书籍阅读网站书籍阅读页页面字 数为 1000 ? 6000 不等,故而提出一种基于页面包含字 数的时间阈值设定方法,假设页面 i 包含字数为 C i,其 阈值设定为 δ i =C i /200。 2.2.3 路径补充与会话拆分 Taucher 和 Greenberg 证 明 超 过 50% 的 页 面 访 问 是通过 Backward 按钮进行的 [8]。由于代理服务器和浏 览器缓存的存在,在 Backward 时,不会访问 Web 服务 器,服务器上没有任何该页面的日志文件,路径补充重 点是把用户通过 Backward 按钮访问的路径记录补全。 本文采用基于引用和网络*私峁沟姆椒ń 路 径 补 充, 并 据 此 进 行 会 话 拆 分。 如 果 一 条 记 录 的 referURL 不是上一条记录的 URL, 则假定用户使用 回退按钮访问了缓存中的页面,需要进行路径补充。根 据 referURL 和网络*私峁沟穆肪恫钩渥裱韵鹿嬖颍 如果某条用户会话的访问路径为 a-b-c-d-e,而页面 d 的 ReferURL 不 等 于 c 的 URL, 则 依 次 查 找 d 与 页 面 c、b、a 之间的超链接关系,直到发现存在超链接关 系的最*页面, 假设 d 与 c、 之间均不存在超链接关系, b 而和 a 之间存在超链接关系,那么认为这个用户是通过 Backward 按妞,从本地 Cache 中调出页面 a,从而访 问页面 d,将该会话拆分为 a-b-c 和 a-d-e ;否则若 页面 d 和 a、b、c 均无超链接关系,则认为用户是从绝 对地址到达页面 d,将该会话拆分为 a-b-c 和 d-e。
[7]

网站的*私峁梗范切┯捎诒淮矸衿骱弯榔 缓存,而在服务器日志中没有记录且被用户重复访问的 网页 ;会话识别需要根据具体网页包含字数确定时间阈 值 δ ,故而我们采用网络爬虫爬取网络*私峁埂 网络爬虫的爬取策略一般分为深度优先、广度优先 和最佳优先 3 种。广度优先搜索策略是指在抓取过程中, 在完成当前层次的搜索后,才进行下一层次的搜索,算 法的设计和实现相对简单。本文使用广度优先搜索方法, 多线程爬取网络*私峁梗钡剿邢叱倘砍薄 将网站的*私峁共捎糜邢蛲急硎尽S邢蛲际且桓 即 E 其中 V 是一个非空集合, 二元组, D 。 D =<V , >, 记为

E 称为顶点集, 其元素称为顶点或结点。 是 V ×V 的子集,
称为边集,其元素称为有向边。有向边(u ,v )表示从 顶点 u 到顶点 v 存在超链接。 经过爬取、清洗、去重,得到该网站的 149265 个 顶点、4825319 条有向边,*均页面出度为 32.33。 在爬取网络*私峁沟耐保 计算所有页面的字数。 字的定义为 :页面 HTML 标签页,即“<”及“>”之 间的字符不计算在内 ;每个中文字、每个标点符号、每 个英文单词、每个数字均记为一个字。 根据 2.2.2 节提出的方法,得出页面访问时间阈值

δ ,对应的页面数统计如表 2 所示。
表2 总页面数 149265 页面访问时间阈值δ 对应的页面数统计(min)

δ >30
1674

10<δ

≤ 30

1<δ

≤ 10 δ ≤ 1
17294

78563

42734

从表 2 可以看出,页面的时间阈值虽然经过调整。 但在一些字数较少的导航页可能过小,当 δ <1min 时 将 δ 设置为 1min。 使用目前常用的评价标准 [9] :会话被算法完整重 建的程度。使用精确度和查全度这 2 个指标来衡量重 建 程 度。 设 Rh 为 算 法 h 生 成 的 会 话 集 合,R 是 真 正 的会话集合,则精确度 p (h )=|Rh ∩ R |/|Rh |,查全度

3

分布式预处理模型的实现

r (h )=|Rh ∩ R |/|R |。在对各种算法进行比较时,以基
3.1 网站*私峁沟呐廊『痛娲 Web 日志预处理中的路径补充和会话拆分需要根据 于引用的方法得到的会话集合作为基准 R ,实验数据如 表 3 所示。

86
万方数据

·2011年 第11期·

东信北邮信息技术有限公司专栏
EASTCOM-BUPT I N F O R M AT I O N TECHNOLOGY CO., LT D . COLUMN
电信工程技术与标准化

表3 会话 构造方法 基于引用 固定阈值 页面字数确 定阈值

会话识别方法的比较结果 会话 交集数 38946 23025 30349 精确度 (%) 100 43.2 47.4 查全度 (%) 100 59.1 77.9

2. if input[5] = "GET" and input[6] 不以 {gif、jpg、 jpeg、wav、rm、css、cgi、js} 结尾 and 200 <= input[8] <= 299 3. 4. 5. mapKey ← input[0] mapValue ← input[5]|input[6]| input[8] collect {mapKey,mapValue}

会话数 38946 53304 64036

6. end if

可以看到,相对于传统的固定阈值 10min,基于页 面字数确定页面时间阈值的会话识别算法精确度与查全 度都有提高。改进的值更能反映用户的浏览*惯,使得 划分的会话更为准确。 3.2 Map/Reduce 程序的设计与实现 Map/Reduce 提供了一个在大数据集上的并行计 算框架。Mapper 将输入记录打散,按照用户要求形成 <key,value> 的键值对,并将相同 key 的记录映射为 一个分组发送给 Combiner ; Combiner 在单个节点上 简单聚合相同 key 的数据,发送给 Reducer ; Reducer 对于每个 key 的所有 values 进行计算,形成最终结果。 选择 MapReduce 进行 Web 日志的预处理,是因为以下 原因 : (1) 随 着 Web 日 志 的 大 规 模 增 长, 每 天 的 日 增 量上亿,单一节点的计算能力已经不能满足要求,而 MapReduce 支持大规模集群操作,在集群上可以方便 地增加多至上千个节点并行计算,其计算速度会随集群 数量相应增加。 (2)Web 日志的预处理,需要针对每个用户处理其 全部访问, 非常适合 MapReduce 的 <key, value> 模型, 选取用户 ID 作为 key,可以方便的将同一用户的 Web 日志聚合在一起。 3.2.1 Mapper 操作 Mapper 操作的输入为 Web 日志记录,对于每条记 录, 进 行 数 据 清 洗 工 作, 并 选 择 key 为 USID,value 为 <URL|ReferURL|Time>,发送给 Combiner。
功能 : 清洗每条输入日志记录,形成 <USID, <URL|ReferURL|Time>> 的键值对输出给 Combiner 1. input[] ← 以 " " 分隔的输入记录

3.2.2 Combiner 操作 为了优化 MapReduce 操作,我们增加一个可选的 Combiner 操 作。Combiner 在 Mapper 之 后、Reducer 之前运行,它会在每一个运行 map 任务的节点上运行 ; 接收节点上的 Mapper 的输出作为输入,对 Mapper 的 输 出 进 行 聚 合, 同 时 聚 合 的 结 果 也 会 作 为 Combiner 的输入进一步进行数据聚合,直到在该节点上的每个 key 聚 合 为 一 条 记 录。Combiner 的 输 出 会 被 发 送 到 Reducer。 本文的 Combiner 操作将 Mapper 操作的输出键值 对聚合为 <USID,<<URL1|ReferURL1|Time1>;… <URLn|ReferURLn|Timen>>> 的 键 值 对, 输 出 给 Reducer。 3.2.3 Reducer 操作 将 USID 定义为 Combiner 的输出 key,将 URLIt 定义为包含 Combiner 输出 value 的迭代器,将 US 定 义为格式为 <URL,ReferURL,Time> 的三元组,将 USIt 定 义 为 包 含 US 的 迭 代 器, 将 USL 定 义 为 包 含 US 的队列。 Reducer 接收一系列 <USID,URLIt>,对每个用 户访问页面的记录集合,按时间顺序排序,并按照之前 提出的会话识别、路径补充和会话拆分方法,输出全部 用户会话。
功能 : Combiner 输出的访问记录聚合为用户会话 将 1. for each urls 2. 3. 4. 5. 6. end for each for each url end for each URLIt urlArray urlArray[] ← 以 ";”分隔的 urls USIt ← USIt + {url}

·2011年 第11期·

87

万方数据

东信北邮信息技术有限公司专栏
EASTCOM-BUPT I N F O R M AT I O N
TELECOM

TECHNOLOGY
ENGINEERING

CO.,

LT D .

COLUMN
S TA N D A R D I Z AT I O N

TECHNICS AND

7. 将 USIt 按照 Time 字段升序排列 8. us1 ← USIt.next() 9. USL ← {us1} 10. reduceValue ← null 11. while 12. 13. USIt.hasnext() do us2 ← USIt.next() if (us2 = "index.jsp") or (us2.referURL = “index.jsp”and us1.URL ≠“index.jsp”) or (us2.referURL = null and us2.Time us1.Time < 10s) or (us2.Time us1.Time > δus1.URL) then 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. end while end if end if reduceKey ← USL 中全部记录中的 URL 字段依序以 "|" 连接 collect {reduceKey,reduceValue} us1 ← us2 USL ← {us1} else if us2.referURL = us1.URL then USL ← USL + {us2} us1 ← us2 else if us2.referURL ≠ us1.URL then reduceKey ← USL 中全部记录中的 URL 字段依序以 "|" 连接 collect {reduceKey,reduceValue} us1 ← us2 倒序扫描 USL 直到列表头,until find usk,其中 usk.URL = us2.referURL USL ← USL – {us1…usk} + {us1} if none usk.URL = us2.referURL USL ← {us1} 图1 编号 ① ②-④ ⑤ ⑥-⑨

表4

集群DataNode配置表 处理器 双核 1.8GHZ 双核 2.8GHZ 双核 3GHZ 双核 3.2GHZ 内存 4GB 4GB 4GB 4GB

效性,我们在单机和 Hadoop 集群上分别用 Java 语言 实现了前面相同的 Web 日志预处理方法(单机的配置 为双核 3.2GHz 处理器,4GB 内存) ,并在两个*台上 分别对文件大小不同的 Web 日志文件分别进行处理, 计算执行时间,其结果如图 1 所示。

单机系统与Hadoop集群执行时间的对比

同时在 Hadoop 集群上针对更大量数据进行测试, 其结果如图 2 所示。

4

结果分析
实验运行在一个 Hadoop 集群上,这个集群由 10

台服务器组成。其中的一台服务器作为分布式文件系 统 HDFS 的 NameNode 及 MapReduce 运 行 过 程 中 的 JobTracker,这台机器称为主节点。另外 9 台机器作 为 HDFS 的 DataNode 和 MapReduce 运 行 过 程 中 的 TaskTracker,这些节点称为从节点。9 台从节点的配 置如表 4 所示。 为验证 Hadoop 对 Web 日志预处理的有效性及高 由以上测试过程可以看出,采用 Hadoop *台处 理 Web 日 志 是 一 个 行 之 有 效 的 方 法。 当 处 理 数 据 量 较小时,由于 Hadoop *台的启动耗时和中间文件的 传输耗时,并行运算的总时间反而大于单机执行的时
图2 大量数据在Hadoop集群执行时间

88
万方数据

·2011年 第11期·

东信北邮信息技术有限公司专栏
EASTCOM-BUPT I N F O R M AT I O N TECHNOLOGY CO., LT D . COLUMN
电信工程技术与标准化

间。但随着数据量的增大,Hadoop *台将数据分割 后分派给多个计算节点并行处理,使并行运算速度增 长 缓 慢, 而 单 机 处 理 时 间 基 本 呈 现 线 性 增 长 的 趋 势。 随 着 输 入 数 据 的 增 加, 两 者 执 行 效 率 的 差 距 也 越 来 越 大。 另 外,Web 日 志 条 数 在 104 的 数 量 级 上 由 于 集群的计算节点一直未满,故而时间增长非常缓慢 ; 在 106 的数量级上,集群的计算节点基本已满,此时 Hadoop 的处理时间呈现略小于线性的增长,而在这 样的数据集上,由于内存、处理器能力等诸多条件的 限制,单机运算还可能出现内存溢出等现象,需要进 行数据拆分。

实 了 Hadoop * 台 对 于 Web 日 志 预 处 理 的 有 效 及 高 效性。

参考文献
[1] 杨清莲,周庆敏,常志玲. Web挖掘技术及其在网络教学评价 中的应用[J]. 南京工业大学学报, 2005(05):100. [2] Ni P,Liao J X,Wang C,Ren K Y. Web information recommendation based on user behaviors[A]. 2009 WRI World Congress on Computer Science and Information Engineering[C]. March 31, 2009-April 2, 2009:426. [3] 杨怡玲,管旭东,陆丽娜. 一个简单的日志挖掘系统[J]. 上 海交通大学学报, 2000(7):35- 37. [4] 朱鹤祥. Web日志挖掘中数据预处理算法的研究[D]. 大连:大 连交通大学, 2010:11. [5] 程苗,陈华*. 基于Hadoop的Web日志挖掘[J]. 计算机工程. 2011,06(11):37. [6] Rosenbium M, Garfinkel T. Virtual machine monitors: current technology and future trends[J]. IEEE Computer Magazine, 2005, 38(5): 39-47. [7] 东尼?博赞(Tony Buzan). 博赞学*技巧[M]. 北京:中信出版 社, 2009.41-42. [8] Taucher L,Greenberg S.Revisitation patterns in world wide web navigation[A]. Proc of Int Conf CHI’97[C]. 1997 Atlanta. [9] Cooley R,Mobasher B,Srivastava J. Data preparation for mining world wide web browsing patterns[J]. Knowledge and Information System. 1999,1(1):32-40. [10] 赵莹莹,韩元杰. Web日志数据挖掘中数据预处理模型的研 究与建立[J]. 现代电子技术, 2007(4):103-105.

5

结论
Web 日志挖掘中的一个重要的前提和基础就是数

据 准 确 性。 高 质 量 的 Web 日 志 挖 掘 必 须 依 赖 高 质 量 的 数 据 [10] 。 本 文 针 对 海 量 的 Web 日 志, 基 于 现 有 的 Web 日志预处理方法,提出一种改进的会话识别、路 径 补 充 和 会 话 拆 分 方 法, 并 基 于 Hadoop * 台 实 现。 同时针对 Hadoop 与单机的处理效率进行了对比,证

Design and implementation of Web log preprocessing based on Hadoop
SONG Ying1,2, SHEN Qi-wei1,2, WANG Jing1,2 (1 State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2 EBUPT Information Technology Co., Ltd., Beijing 100191, China) Abstract Web log preprocessing is an important step in Web log mining, Web log is a prerequisite to obtain accurate information, directly affect the accuracy of the follow mining algorithms. Base on the massive Web log, this paper advanced an optimized Web log preprocessing method and implements it via distributed computing platform Hadoop. We compared the Hadoop platform’s performance with the stand-alone’s, thus proved the efficiency of Web log preprocessing on Hadoop. Keywords Web log preprocessing; Web structure; map/reduce
·2011年 第11期·

89

万方数据


相关推荐

最新更新

猜你喜欢