（计算数学专业论文）基于点击流分析的web日志挖掘研究.pdf

摘要 w e b 日志中包含了大量的用户浏览信息，如何有效地从其中挖掘出用户浏览 兴趣模式是一个重要的研究课题。本文咀w e b 日志中的点击流数据为基础，从统 计分析和智能分析出发，引入w e b 挖掘技术对网站上用户的浏览数据一点击流数 据进行概化分析，生成相应的量化规则；并进行浏览兴趣路径的研究，提出了用 户浏览兴趣路径挖掘算法。这种算法能准确地反映用户浏览兴趣，而且可扩展性 较好。可以应用于电子商务网站的站点优化和个性化服务等。 本文首先介绍了w e b 挖掘、w e b 日志及w e b 日志挖掘的意义和主要任务，接 着设计了对点击流数据进行实时预处理的方法和算法。在数据挖掘即数据分析部 分，研究和设计了用于数据概化分析的面向属性规约的算法，在分析目前用户浏 览模式挖掘算法存在的问题的基础上，提出了支持一兴趣度的概念，设计了网站访 问矩阵，并基于这个矩阵提出了用户浏览兴趣路径挖掘算法。 关键宇：点击流数据，数据挖掘，面向属性规约，支持一兴趣度，测览兴趣路径 a b s t r a c t w e bl o g sc o n t a i nal o to fu s e rb r o w s i n gi n f o r m a t i o n h o wt om i n e e f f e c t i v e l y u s e rb r o w s i n gi n t e r e s tp a t t e r n si so n ei m p o r t a n tr e s e a r c h t o p i cw i t hc l i c k s t r e a m d a t ao fw e ba sf o u n d a t i o n a n db e g i nw i t hs t a t i s t i c a l a n a l y s i sa n di n t e l l i g e n c e a n a l y s i s ，t h ep a p e ri n t r o d u c ew e bm i n et e c h n o l o g yf o rw e bs i t ed a t ao fb r o w s i n g u s e r , t h a ti sc l i c k s t r e a md a t at oc a r r yo r ld a t ag e n e r a l i z a t i o na n a l y s i st op r o d u c et h e c o r r e s p o n d i n gq u a n t i z a t i o nr u l e ；a n dt oc a r r yo nt h er e s e a r c ho f t h ei n t e r e s td 缸h s ，w e p r o p o s e du s e ri n t e r e s t e db r o w s i n gp a t h sm i n i n ga l g o r i t h m t h ea l g o r i t h mc a nr e f l e c t a c c u r a t e l yu s e r sb r o w s i n gi n t e r e s t ，a n dt h es y s t e m a t i ce x p a n s i b i l i t yi sb e t t e r i t c a na p p l yt ow e bs i t e o p t i m i z i n g a n dp e r s o n a l i z e ds e r v i c eo ft h ee - b u s i n e s s w e b s i t e ，e t c t h i sp a p e rh a si n t r o d u c e dw e bm i n i n g , w e bl o g sa n dt h ec l a s s i f i c a t i o na n dt h e t a s ko fw e b l o g sm i n i n ga tf i r s t t h e n t h ep a p e rh a sd e s i g n e dt h ed a t am e t h o da n d a l g o r i t h mo fc a r r y i n go nt h ；r e a l t i m ep r e t r e a t m e n to fc l i c k s t r e a md a t a i nt h ep a r t o fd a t am i n i n g ，n a m e l yd a t aa n a l y s i s ，i ta l s os t u d i e sa n dd e s i g n sa l g o r i t h mo fa t t r i b u t e - o r i e n t e di n d u c t i o nw h i c ha p p l i e st og e n e r a l i z a t i o n a n a l y f i s o nt h eb a i l so f e x i s t i n go fp r o b l e m so fa l g o r i t h m su s e rb r o w s i n gm o d e t h ep a p e rp u t sf o r w a r d s t h e c o n c e p to fs u p p e r i n t e r e s td e g r e e s ，a n dd e s i g n sw e b s i t em a t r i xo fv i s i t i n g f u r t h m o r e ，o nt h eb a s eo ft h em a t r i x , t h ep a p e rw o r k so u ta l g o r i t h mo fu s e r b r o w s i n gi n t e r e s tp a t h sm i n i n g k e yw o r d s ； c l i c k s t r e a md a t a , d a t am i n i n g ，a t t r i b u t e o r i e n t e di n d u e t i o n ， s u p p o r t i n t e r e s td e g r e e ， i n t e r e s t e d b r o w s i n gp a t h s 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 蓑的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 pz 论文作者签名：i 墨2 1 叠 i t 期：。z 竺竺：丛12 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：! ! i ! ；导师签名： f 日 期：；z 型， 1 1w e b 挖掘概述 第1 章w e b 数据挖掘 随着以数据库、数据仓库等数据仓储技术为基础的信息系统在各行各业的应 用，使海量数据不断产生。随之而来的问题是如此多的数据让人难以消化，无法 从表面上看出他们所蕴涵的有用信息，更不用说有效地指导迸一步的工作，呈现 出“数据丰富，而知识贫乏”的现象。如何从大量的数据中找到未知的有用的信 息成为人们关注的焦点，数据挖掘技术也正是伴随着这种需求从研究走向应用。 近年来，随着i n t e r n e t w e b 技术的快速普及和迅猛发展，使各种信息可 以以非常低的成本在网络上获得，由于i n t e r n e t w w w 在全球互连互通，可以 从中取得的数据量难以计算，而且i n t e r n e t w w w 的发展趋势继续看好，特别 是电子商务的蓬勃发展为网络应用提供了强大支持，如何在w w w 这个全球最大 的数据集合中发现有用信息无疑将成为数据挖掘研究的热点之一。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信 息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计 学、人工智能中的机器学习和神经网络等。 1 ，2w e b 挖掘流程 与传统数据和数据仓库相比，w e b 上的信息是非结构化或半结构化的、动态 的、并且是容易造成混淆的，所以很难直接以w e b 网页上的数据进行数据挖掘， 而必须经过必要的数据预处理。典型w e b 挖掘的处理流程如下儿 ： 1 ) 查找资源：任务是从目标w e b 文档中得到数据，值得注意的是有时信息 资源不仅限于在线w e b 文档，还包括电子邮件、电子文档、新闻组，或者网站 的日志数据甚至是通过w e b 形成的交易数据库中的数据。 ( 2 ) 信息选择和预处理：任务是从取得的w e b 资源中剔除无用信息和将信息 进行必要的整理。例如从w e b 文档中自动去除广告连接、去除多余格式标记、 1 自动识别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。 ( 3 ) 模式发现：自动进行模式发现。可以在同一个站点内部或在多个站点之 间进行。 ( 4 ) 模式分析：验证、解释上一步骤产生的模式。可以是机器自动完成，也 可阻是与分析人员进行交互来完成。 w e b 挖掘作为一个完整的技术体系，在进行挖掘之前的信息获得i r ( i n f o r m a t i o n r e t r i e v a l ) 和信息抽取i e ( i n f o r m a t i o ne x t r a c t i o n ) 相当重要。信息获得( i r ) 的目的在于找到相关w e b 文档，它只是把文档中的 数据看成未经排序的词组的集合，而信息抽取( i e ) 的目的在于从文档中找到需 要的数据项目，它对文档的结构和表达的含义感兴趣，它的一个重要任务就是对 数据进行组织整理并适当建立索引。信息获得( i r ) 和信息抽取( i e ) 技术的研 究已经有很长时间，随着w e b 技术的发展，基于w e b 技术的i r 、i e 得到了更 多的重视。由于w e b 数据量非常大，而且可能动态变化，用原来手工方式进行 信息收集早己经力不从心，目前的研究方向是用自动化、半自动化的方法在w e b 上进行i r 和i e 。在w e b 环境下既要处理非结构化文档，又要处理半结构化的 数据，最近几年在这两方面都有相应的研究成果和具体应用，特别是在大型搜索 引擎中得到了很好的应用。 13w e b 挖掘分类及各自的研究现状及发展 根据对w e b 数据的感兴趣程度不同，w e b 挖掘一般可以分为三类汪3 ：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r e m i n i n g ) 、w e b 使用记录挖掘( w e bu s a g em i n i n g ) 图i - i 给出了w e b 挖 掘的分类图 2 主要! 文本文档 ! 数据! 超文本文档； i 篝篝。： ( 1 ) w e b 内容挖掘 服务器日志 代理服务器日志 等等 图1 1w e b 挖掘的分类 链接结构 ： 内部结构 ： 等等； 指从w e b 内容、数据、文档中发现有用信息，w e b 上的信息五花a i 3 ，传 统的i n t e r n e t 由各种类型的服务和数据源组成，包括w w w 、f t p 、t e l n e t 等 现在有更多的数据和端口可以使用，比如政府信息服务、数字图书馆、电子商务 数据，以及其他各种通过w e b 可以访问的数据库。w e b 内容挖掘的对象包括文 本、图象、音频、视频、多媒体和其他各种类型的数据。其中针对无结构化文本 进行的w e b 挖掘被归类到基于文本的知识发现( k d t ) 领域，也称文本数据挖掘 或文本挖掘，是w e b 挖掘中比较重要的技术领域，也引起了许多研究者的关注。 最近在w e b 多媒体数据挖掘方面的研究成为另一个热点。 w e b 内容挖掘一般从两个不同的观点来进行研究。从资源查找( i r ) 的观 点来看，w e b 内容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助用 户过滤信息。而从d b 的角度讲w e b 内容挖掘的任务主要是试图对w e b 上的数 据进行集成、建模，以支持对w e b 数据的复杂查询。 ( 2 ) w e b 结构挖掘： w e b 结构挖掘的对象是w e b 本身的超连接，即对w e b 文档的结构进行挖掘。 对于给定的w e b 文档集合，应该能够通过算法发现他们之间连接情况的有用信 息，文档之间的超连接反映了文档之间的包含、引用或者从属关系，引用文档对 被引用文档的说明往往更客观、更概括、更准确。 w e b 结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之间 的关系分为i n c o m i n g 连接和o u t g o i n g 连接，运用引用分析方法找到同一网 站内部以及不同网站之间的连接关系。在w e b 结构挖掘领域最著名的算法是 h i t s 算法和p a g e r a n k 算法。他们的共同点是使用一定方法计算w e b 页面之 问超连接的质量，从而得到页面的权重。著名的c l e v e r 和g o o g l e 搜索引擎 就采用了该类算法。 此外，w e b 结构挖掘另一个尝试是在w e b 数据仓库环境下的挖掘，包括通 过检查同一台服务器上的本地连接衡量w e b 结构挖掘，w e b 站点的完全性，在 不同的w e b 数据仓库中检查副本以帮助定位镜像站点，通过发现针对某一特定 领域超连接的层次属性去探索信息流动如何影响w e b 站点的设计。 ( 3 ) w e b 使用记录挖掘( w e bu s a g em i n i n g ) ： 在新兴的电子商务领域有重要意义，它通过挖掘相关的w e b 日志记录，来 发现用户访问w e b 页面的模式，通过分析日志记录中的规律，可以识别用户的 忠实度、喜好、满意度，可以发现潜在用户，增强站点的服务竞争力。w e b 使用 记录数据除了服务器的曰志记录外还包括代理服务器日志、浏览器端日志、注册 信息、用户会话信息、交易信息、c o o k i e 中的信息、用户查询、鼠标点击流等 一切用户与站点之间可能的交互记录。可见w e b 使用记录的数据量是非常巨大 的，而且数据类型也相当丰富。根据对数据源的不同处理方法，w e b 日志挖掘可 以分为两类，一类是将w e b 使用记录的数据转换并传递进传统的关系表里，再 使用数据挖掘算法对关系表中的数据进行常规挖掘；另类是将w e b 使用记录 4 的数据直接预处理再进行挖掘。w e b 使用记录挖掘中的一个有趣的问题是在多 个用户使用同一个代理服务器的环境下如何标识某个用户，如何识别属丁- 该用户 的会话和使用记录，这个问题看起来不大，但却在很大程度上影响着挖掘质量， 通常来讲，经典的数据挖掘算法都可以直接用到w e b 使用记录挖掘上来，但为 了提高挖掘质量，研究人员在扩展算法上进行了努力，包括复合关联规则算法、 改进的序列发现算法等。 尽管w e b 挖掘的形式和研究方向层出不穷，但我认为随着电子商务的兴起 和迅猛发展，未来w e b 挖掘的一个重要应用方向将是电子商务系统。而与电子 商务关系最为密切的是w e b 使用记录挖掘( u s a g em i n i n g ) ，也就是说在这个 领域将会持续得到更多的重视。另外，在搜索引擎的研究方面，结构挖掘的研究 己经相对成熟，基于文本的内容挖掘也已经有许多研究，下步将会有更多的研 究者把多媒体挖掘作为研究方向 1 4 本文的研究内容及论文组织 本论文研究的主要内容是，引入w e b 挖掘技术对网站上用户的浏览数据一 点击流数据进行概化分析和兴趣路径的挖掘，生成相应的量化特征描述规则和浏 览兴趣路径，这些规则可阻为企业决荒人员在进行市场决策和开展各项商务活动 时提供一定的参照和依据，阻达到辅助企业商务智能决策的目的。 本文要做的工作： ( 1 ) 分析服务器上w e b 日志的组成及特点，在此基础上定义点击流数据的 一般格式；同时研究w e b 日志数据的一般预处理过程及日志挖掘中的的任务， 设计对点击流数据进行实时预处理的方法。 ( 2 ) 分析和研究描述性数据挖掘中进行数据概化的一般方法，对其中面向属 性规约( a t t r i b u t e o r i e n t e di n d u c t i o n a o i ) 的概化方法作比较深入的 研究和适当的扩充，实现该算法在点击流数据分析中的应用。 ( 3 ) 关联规则相关算法的分析和研究。以分析最流行a p r i o r i 算法为基础， ( 3 ) 关联规则相关算法的分析和研究。以分析最流行a p r i o r i 算法为基础， 研究并设计挖掘浏览兴趣路径的算法。 ( 4 ) 利用己实现的算法，验证算法的实现 论文组织： 第一章w e b 挖掘概述、w e b 挖掘流程、分类和研究现状，及本文的主要工 作。 第二章w e b 目志的介绍，w e b 日志挖掘的意义和主要任务。 第三章分析对点击流数据进行预处理的必要性，简述数据预处理的一般过 程，设计对点击流数据预处理的方法。 第四章分析并比较己有的数据概化方法，就其中面向属性的数据规约算法 ( a o i ) 作较深入的研究和适当的扩充，给出点击流数据概化分析中，实现该算法 的逻辑流程，最后总结对点击流数据进行概化分析的优点。 第五章阐述关联规则的基本概念，结合关联规则挖掘算法中最经典 a p r i o r i 算法，介绍关联规则的一般挖掘过程，针对点击流分析中的实际应用 问题，提出了支持一兴趣度的概念，设计了网站访问矩阵，并基于这个矩阵提出 了用户浏览兴趣路径挖掘算法。 6 第2 章w e b 日志挖掘概述 w e b 日志挖掘，它通过挖掘w e b 日志记录，来发现用户访问w e b 页面的模 式。还可以通过分析和探究w e b 日志记录中的规律，来识别电子商务的潜在用 户，增强对最终用户的互联网信息服务的质量和交互，并改进w e b 服务器系统 的性能。 2 1 w e b 日志概述 目前市面上比较流行的w e b 服务器系统，例如ii s ，a p a c h e 等，通常都 保存了对w e b 页面的每一次访问的日志项，这些记录项又叫做w e b l o g 项。它 忠实地记录了访问该w e b 服务器的数据流的信息。 日志文件的格式并不复杂，例如i i s ，它支持三种w e b 日志格式 3 1 ： m i c r o s o f ti i s 日志文件格式，n c s a 公用日志文件格式和w 3 c 扩展日志文件 格式，其中在i i s 5 0 中，w 3 c 扩展日志文件格式是缺省的日志文件格式。 目志文件记录些什么内容还可以根据客户的不同需要，来调整记录的信息。 例如i i s 5 0 中w 3 c 扩展日志文件格式中，除了时间这些日志文件肯定有的元 索外，还有多达1 9 项可以选择记录的扩展属性，比较常用的属性是所请求的u r l 资源，客户端i p 地址和时间戳。在w 3 c 扩展日志文件格式中，缺省的属性有： 时间戳，客户端i p 地址，访问方法，u r l 资源，协议状态。 w e b 服务器日志( w e bs e r v e rl o g s ) ：w e b 服务器在处理客户的请求时， 方面将客户的请求发送出去，另一方面将本次请求写入日志，因而说w e b 服 务器日志实际上就是客户访问网站时留下的踪迹。w e b 服务器日志文件格式一般 有常规日志格式( c o m m o nl o gf o r m a t c l f ) 和扩展日志格式e c l f 两种形 式，常规日志格式中的信息一般包括访问日志中所包含的内容，扩展日志格式中 7 的信息则增加了代理日志和引用日志的内容。常规日志格式见表2 1 表2 1s e r v e rl o g s 文件格式 f i e l d d e s c r i p t i o n d a t e d a t e ，t i m e ，a n dt i m e z o n eo f r e q u s t c i i a n tl pr e m o t eh o s ti pa n d o rd n se n t r y u s e td a m e r e m o t el o gn e | ：t n eo f t h eu s e r b y t e sb y t e st r a n s f e r r e d ( s e n ta n dr e c c i v e m s e r v e rs e r v e rn a m e ，i pa d d r e s sa n dp o r t r e q u e s t u r l q u e r ya n ds t e m s t a t u s h t t ps t a t u sc o d er e t u r n e dt ot h e c l i e n t s e r v i c en a m e r e q u e s t e ds e r v i c e l a m e t i m et a k e nt i m et a k e nf o rt r a n s a e t o nt oc o m p l e t e p r o t o e o l v e r s i o nv e r s i o no f u s e d t r a n s f e r p r o t o c o l u s e ra g e n t s e r v i c ep r o v i d e r c o o k i ec o o k i ei d r e f e r e r p r e v i o 岫p a g e w e b 服务器日志文件中的数据包括以下数据内容：访问的日期和时间、i p 地址、用户的域名、访问的方法( g e t 或p o s t ) 、访问结果( 成功、失败、错误) 、 引用页的u r l 、用户采取的操作系统和被访问页的文件名等等。下面是原始文件 的格式及其它的注释( 参看图2 - 1 u s e ri d f 2 1 8 6 0 1 0 1 1 - 2 0 0 5 0 3 0 5 f i p日期和时间 请求 ? g e t i n d e x h t t p ：w w w c l i c k s t r e a m c o n s u l t i n g c o m w h y c s d w 2 h t m l 引用页酾百盂 m o z i l l a 4 7 5 + ( c o m p t i b l e ；m s i e 5 0 ；w i n d o w s + 9 8 s ) 浏览器类型 图2 一lw e b 的日志格式及注释 态乏 粕一 06 2 2 w e 8 日志挖掘的分类 在挖掘中，根据数据来源、数据类型、数据集合中的用户数量、数据集合中 的服务器数量等将w e b 日志挖掘分为五类1 ： 个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基本 信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众 不同的个性化服务。 系统改进：w e b 服务( 数据库、网络等) 的性能和其他服务质量是衡量用 户满意度的关键指标，w e b 用法挖掘可以通过用户的拥塞记录发现站点的性能 瓶颈，以提示站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡机 制和数据的分布策略。此外，可以通过分析网络的非法入侵数据找到系统弱点， 提高站点安全性，这在电子商务环境下尤为重要。 站点修改：站点的结构和内容是吸引用户的关键。w e b 日志挖掘通过挖 掘用户的行为记录和反馈情况为站点设计者提供改进的依据，比如页面连接情况 应如何组织、那些页面应能够直接访问等。 商务智能：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的 重点，用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 挖掘可以通过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮助销 售商合理安排销售策略。 w e b 特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各个 用户在页面上的交互情况，对用户访问情况进行特征描述。 2 3w e b 日志挖掘的主要任务 基于w e b 日志的挖掘主要用来完成两大类任务的分析： ( 1 ) 统计查询分析 网站点击分析。如网站的哪个部分用户访问量最高? 哪个部分导致的直接 购买行为最多? 9 客户分析。根据客户的访问次数，可将客户分为新客户和老客户；根据 访问的频率，可将客户区分为规则型访问者和间或型访问者；访问的次数及逗留 时间，可将客户分为过客型客户和驻留型客户。 流量分析。网络流量随时间如何变化? w e b 站点中每个页面、目录及内容 模块的流量分配情况。统计查询分析属于基本的数据分析，是进行深层次数据分 析的基础，统计查询分析的结果对于提高系统眭能、优化站点结构以及进行市场 决策都有很大的帮助。 ( 2 ) 智能查询分析 智能查询分析主要用来发现数据库中的规则、模式和其他知识。 关联规则 关联规则挖掘发现大量数据项集之间有趣的关联或相关联系，w e b 日志挖掘 中是指在用户会话文件中挖掘经常被用户一起访问的页面集合，并且页面之间是 无序的。关联规则既可以作为站点设计人员优化站点的参照，也是在w e b 上进 行市场开发和商务活动的依据。 序列模式 序列模式是指在有时间戳的有序事务集上发现有时间先后顺序的事务项。在 w e b 日志挖掘领域中，序列模式识别指寻找用户会话中在时间上有先后关系的页 面请求。利用发现的序列模式可以预测用户即将可能请求的页面。 聚类 w e b 日志挖掘中，聚类分析的任务有两大类，一是进行页面聚类，将内容相 关的页面归类，如搜索引擎中采用页面聚类技术使用户方便快捷地定位到所要查 找的页面；二是进行用户聚类，将具有相同访问模式的用户归为一类，用户访问 信息还便于开发和执行未来的市场策略，如为某一用户聚类进行智能推荐服务。 分类 分类是指事先给出一个识别特殊群体的公共属性描述，然后根据描述将数据 项划分到不同的类别。在w e b 日志挖掘领域中，分类主要是将用户配置文件归 属既定的用户类别。针对分类后用户的不同公共属性进行相应的商务活动。 1 0 第3 章点击流数据的预处理 3 1 点击流数据预处理概述 3 1 1 点击流分析中的相关名词术语 以下首先简述与点击流分析相关的名词术语及概念。在本文后续章节的介 绍中将直接对这些术语进行引用。 请求( r e q u e s t 或h i t ) ：向w e b 服务器请求一个文件的动作。当从服务器 和客户两个不同的角度看时，它又分别对应不同的含义。对于服务器来说，一次 请求对应一条日志记录：对于客户来说，向服务器发送请求的形式则表现为点中 w e b 页面上的一个超链按，但点中一个超链接并不意味着一次请求，这是因为一 个w e b 页面中可能包含多个文件，如h t m l 文件、声音文件、图象文件等，此 时如果用户点中这样一个超链接则对应着多个请求，在w e b 日志中也就有多行 记录。 c o o k i e ：c o o k i e 最初是由n e t s c a p e 公司开发的一种用于追踪用户的 机制，它是为弥补h t t p 协议的无状态缺陷而产生的。所谓无状态是指通过h t t p 协议发送的每一次请求，它们之间是相互独立的，对于用户目前正在浏览的主页 以及在此之前浏览过的主页没有丝毫记忆和了解。但是在实际应用中，往往希望 浏览器能记住一些信息，如用户的身份信息等，以便能自动地对用户进行识别以 及更好地提供个性化服务。因而引入了c o o k i e 的概念，用户第一次访问站点时， w e b 服务器为其分配一个唯一的标识符并保存在用户的计算机中，用户再次访问 该站点时，w e b 服务器根据c o o k i e 值识别用户。 用户( u s e r ) ：指通过浏览器访问服务器的个体。h t t p 协议的无状态性、防 火墙以及代理服务器的存在，使得在实际应用中确定一个用户很难；因此，有时 需要把服务器日志、代理日志、引用日志结合起来确定一个用户哺1 。 用户会话( u s e rs e s s i o n ) ：某个用户阶段性的页面浏览所构成的点击流。 本论文中的用户会话指一段时间内用户对单个网站的访问请求。 服务器会话( s e r v e rs e s s i o n ) ：某个用户在一个服务器上阶段性的页面 浏览所构成的点击流。 点击流数据( c l i c k s t r e a md a t a ) ：w e b 服务器上一系列有序的日志记录 【6 】。顾客从进入一个电子商务站点，到离开这个站点的一个访问周期中，所浏 览的页面、滞留时间、点击的链接和广告都会被顺序地记录在网站的日志文件中。 这种有序的w e b 日志记录形成了点击流数据。点击流数据包含了与w e b 日志相 同的基本数据域，但是其中只有部分关键的数据域对分析有用。为此，根据实际 分析的需要，我们确定了点击流数据中的关键数据项，并定义了如式( 3 1 ) 所示 的一般格式： c l i c k s t t e a md a t a = l ， m ， ( 3 1 ) 其中，i p 表示用户地址，u i d 表示用户标识号，u r l 表示请求的页面， r e q u e s t t m e 表示页面请求的时间。 3 1 2 点击流数据预处理的一般过程 由于本地缓存、代理服务器以及防火墙的存在，使得w e b 曰志中收集的数 据缺乏完整性，从而也影响了w e b 日志数据的可靠性。数据预处理是在将日志 文件转换成数据库文件以后进行的，其目的是把w e b 日志转化为适合进行数据 挖掘的可靠的精确的数据。这个过程主要包括数据净化、用户识别、会话识别、 会话事务识别、事务完善等几个阶段。图3 1 是数据预处理的流程图。 辅入 曩憝麓 氇 盎1 i 琢蚺一鸯定摊l 赣 期 话搴 l 搴舟熏释 i l 鳖 户搴-黉 、 “。， _ 诤 矗 务京 i 疆产蠹舔盘件l l 站点蚺拥枘骞 化 叠 攮藿 捌 圈3 1 数据预处理的流程图 数据净化：指删除w e b 服务器日志中与挖掘算法无关的数据。 用户识别：指识别出访问网站的每一个用户。 会话事务识别：会话事务识别的目的是为每个用户建立有意义的页面组合， 将用户点击流分成多个小的访问事务或合并成大访问事务。每个事务都与一定的 主题相关，如购买产品、注册等。 事务完善：由于本地缓存和代理服务器缓存的存在，使得服务器的日志会遗 漏一些重要的页面请求。事务完善的任务就是将这些遗漏的请求补充到用户会话 中。 数据净化 数据净化是指删除w e b 服务器日志中与挖掘算法无关的数据，一般来说只 有日志中h t m l 文件与用户会话相关。用户一般不会显式地请求页面上的图形文 件，它们是根据h t m l 的超文本引用标记自动下载的。w e b 日志文件的目的是获 得用户的行为模式，并不关心那些用户没有显式请求的文件，所以通过检查u r l 的后缀删除认为不相关的数据。例如：将日志中文件的后缀名为g i f ， j p e g ， j p g 等的图形文件删除，另外，后缀名为c g i 的脚本文件也应被删除。具体到 实际的系统就使用一个缺省的后缀名列表帮助删除文件。列表可以根据正在分析 的站点类型进行修改，例如：对一个主要包含图形文档的站点，目志中g i f 和 j p e g 文件可能代表了用户的请求，此时就不能将图形文件删除。进行数据预处 理的还有一个方面，比如：有些网站的页面用户在提出请求时，w e b 服务器拒绝 该页面的请求，那么应该过滤掉非法请求的页面，对正常的页面进行数据处理是 很有价值的。但是如果考虑的是网络安全方面的问题，那就另当别论考虑非法请 求的页面的情况。 用户识别 识别用户对于会话识别特别是为提供个性化的服务非常重要，目前由于本 地缓存代理服务器和防火墙的存在、为用户动态的分配i p 地址，想要识别出每 一个用户变得很复杂。针对用户的识别有几种最可能的解决办法是基于w e b 日 志站点的方法，一些启发式规则可以帮助识别用户。 ( 1 ) 如果i p 地址相同，但是代理日志中表明用户的浏览器或操作系统改 变了，就应当认为每个不同的代理就表示不同的用户。 f 2 ) 将用户的访问目志和站点的拓扑结构结合，构造用户的浏览路径。如 果当前请求的页面同用户已浏览的页面之间没有链接关系，那么就认为存在另外 具有相同i p 地址的多个用户。 ( 3 ) 不同的i p 就认为是不同的用户。 ( 4 ) c o o k i e 是由w e b 服务器产生的记号存在于客户端( 用户的机器) ，用 于识别用户的会话。它是一种自动跟踪w e b 站点访问者的标记。当用户对w e b 资源提出请求时，将为该用户产生唯一的c o o k i e 用于识别对话。在随后的请求 中，浏览器将该唯一的c o o k i e 发送回服务器用来识别对话。c o o k i e 法划分最客 观和准确，为提高准确性，设计采用c o o k i e 进行用户识别。下面针对c o o k i e 做 讨论。c o o k i e 是在w e b 上用于存储客户系统信息的对象，所有的信息都以每行 一个c o o k i e 的形式存放在客户端的一个名为c o o k i e st x t 的文件里。c o o k i e 在 “h t t p ”头标( 客户和服务器用来标识自身的分组) 中在客户机与服务器之间传 输，c o o k i e 由w w w 网页在客户机上进行设置。比如，一个w w w 网页己在 一个用户的计算机上设置的一个c o o k i e ，其中存储的信息是该用户的身份标号 ( 随机赋予该用户的唯一标识) ，当该用户的浏览器连接这个w w w 站点时，站点 要求浏览器将c o o k i e 送回，它的身份号就通过c o o k i e 传递给该网页所在的 w w w 服务器。因此，要对每一个来访问的用户的计算机上设置c o o k i e ，作为 用户的唯一标识。 会话事务识别 ( 1 ) 用户访问会话事务的定义 1 4 在讨论用户访问会话事务识别方法之前，我们首先给出用户访问会话事务的 定义： 定义3 - 1 ：用户会话事务s 是一个二元组 ，其中u s e r i d 是用户标识，r s 是用户在一段时问内请求的带有访问时间长度的w e b 页面的集 合。r s 包含用户请求的页面的标识符p i d 、页面请求时间t i m e 及访问时间长 度l e n g t h ( 访问时间长度是指用户访问一个页面所经历的时间) 。 s = ( 3 1 ) ( 2 ) 用户访问会话事务的识别方法 服务器要并发处理多个用户的请求，要从多个相互交织的用户访问事务中 正确区分出所有用户访问事务比较困难。一般都是对用户在客户端浏览行为做不 同假设，然后再在此基础上确定用户访问事务。因此确定的用户访问事务并不能 保证完全精确。根据对用户访问行为的不同假设，有四种确定用户访问行为及访 问事务的模型；页面类型模型( ( p a g et y p em o d e l ) 、参引长度模型 ( r e f e r e n c el e n g t hm o d e l ) 、最大向前参引模型( m a x i m a l f o r w a r d r e f e r e n c em o d e l ) 、时间窗口模型 t i m ew i n d o wm o d e l ) 。如果采用时间 窗口模型对用户访问事务进行识别，时间窗口模型中，对用户浏览行为假定的方 法是认为用户一次访问的时间都有一个最大的限制。因此，一般有两种方法来划 分用户访问事务：一是以用户的访问历时作为用户访问事务的分界，则( 3 1 ) 中 的用户会话必定满足式( 3 2 ) ，其中w 是时间窗口长度，即事先假定的最大超时 阈值。 t i m e l t i m ek w ( 3 2 ) 二是采用时间间隔来区分用户访问事务，即如果相邻两个页面请求的间隔时 间超过一定的界限，就认为是开始了一次新的用户会话。此时，式( 3 1 ) 满足式 ( 3 3 ) 。 t i m e i t i m e l 一1 w l i k ( 3 3 ) 在时间窗口模型中，我们采用第二种方法划分用户访问事务。其中关键的一 步是如何确定时间窗口大小即超时阈值。因为超时阈值的确定直接影响到点击流 数据预处理结果的输出，不同的超时阂值会产生不同的用户会话文件。对于超时 阈值，我们采用对实际日志进行实验，观察超时闽值与平均用户会话长度及用户 会话个数之间的关系来确定。 定义3 - 2 ：用户会话长度指一个用户会话中所包含的页面请求个数。 利用上述介绍的方法收集了某一商务网站上2 0 0 5 年1 月份的用户访问日 志，在收集点击流数据的过程中，通过设定不同的会话超时阈值，来寻找超时阖 值与平均用户会话长度以及用户会话个数的关系。图3 - 2 表示了超时阈值与用 户会话个数之间的关系。 藏 毒 ! l 譬 如 疋 已 1 0 05 5 0 ，9 0 01 3 5 0 】8 0 02 2 5 02 7 0 03 1 5 03 6 0 04 0 5 04 5 0 04 9 5 0 翔耐( 耪) 图3 - 2 超时阈值与用户会话个数之间的关系 根据实验结果，我们可以看出，当超时闽值到达6 0 分钟时，会话个数减少 的趋势趋于平稳，因而我们可以将超时阈值设为6 0 分钟。目前，许多商业产品 将缺省超时值确定为3 0 分钟，超时的界限可以根据站点的使用统计反馈的结果 啪薹；湖嗽|毳|薹看；撇舌堇 辄8 8 7 7 8 5 s 4 进行调节，直到可以更准确地识别会话。 用户会话事务的完善 由于本地缓存、代理服务器以及防火墙的存在，使得收集到的点击流数据缺 乏一定的完整性，因而需要对点击流数据进行补充和完善。但是如果采用了在应 用服务器层收集点击数据的方法，能很好地解决了防火墙和代理服务器的问题， 在电子商务中用户访问会话事务主要是指成功发送产品购买意向的访问会话事 务，而在能成功提交发送购买意向的w e b 页面上，其客户端的浏览器中后退按 钮是被禁用的，即消除了本地缓存的现象。综合以上原因，也可以不需要进行用 户访问会话事务的完善。 32 点击流数据预处理方法的实现 收集到的点击流数据写入预定义好的关系数据库表，并且在收集数据的过程 中进行实时的预处理。因此，本节在给出数据预处理过程中相关库表结构设计的 基础上，介绍实时预处理的算法流程。 3 2 ，l 相关库表的设计 在数据预处理部分，定义以下四个数据库表： p a g ed b 页面信息表：用于记录被访问页面的相关信息，包括：页面编 号、页面的u r l 路径、页面参数、页面标题、页面访问次数。 v u s e r sd b 用户访问信息表：记录用户的相关信息，包括：用户编号、用 户标识、用户当前会话编号、用户的最近一次访问时间。 u s e rs e s s i o n sd b 用户会话表：记录用户会话信息，包括会话编号、 用户编号。 s e s s i o nt r a n s a c t i o nd b 会话事务表：又称为会话内容表，记录了 用户每次会话的详细信息，包括会话编号、页面编号、页面请求时间、页面逗留 时间。表3 一l 给出了相关库表的结构设计。 表3 1 数据预处理相关库表的结构设计 数据表名字段名类型说明 p i di n t页面编号 u r l c h a r ( 3 0 ) 页面路径 p a g e _ d b p a r a m c h ( 3 0 ) 页面参数 页面信息表 t i l 】e d l a t ( 5 0 ) 页面标题 v i e w f i m c si n t页面访问次数 u i d i n t用户编号 v l l s c r sd b s e s s i o n c h a r ( 3 0 ) 用户标识 用户访问信息表 a c t i v es i di n t用户当前会话编号 l a s t _ a c c e s s t i m e d a t e t i m e最近一次访问时间 u s e r _ s e s s i o n s d b s i d i n t会话编号 用户会话表 u i di m用户编号 s i d h a t 会话编号 s e s s i o n 且a n s a c t i o n _ p i d i n t页面编号 d b r e q u e s t t i m e d a t e t i m e页面请求时间 会话事务表 s t a y t i n l o $ i m 页面逗留时闻 3 2 2 实时预处理的算法流程 记录和预处理一个请求所基于的思想： 1 ) 判