（计算机软件与理论专业论文）一种基于服务器日志挖掘的自适应实时推荐网站框架.pdf

一种基于服务器i j 志挖掘的自适应实时推荐网站框架 摘要 自适应实时推荐网站是数据挖掘在w e b 日志数据中的一个应用，其目的是 方便浏览者对网站的访问。随着网站在规模和复杂度上不断增长，w e b 日志的 挖掘结果在很多领域中都变得至关重要，如站点设计、商业市场策略和网站个 性化等等。而以往的多数研究都是将w e b 日志的挖掘结果作为决策支持系统的 输入。在本论文中，我们设计了一个自动的自适应实时推荐系统框架 s a r t s ( s e l f - a d a p t i v er e a lt i m er e c o m m e n d a t i o n ) ，为在线浏览者提供可能感 兴趣的联接。这个过程是自学习、自适应、不需要浏览者和网站管理人员协作 的过程。本论文还设计了一个基于浏览者反馈的自学习推荐引擎 a d r e ( a u t o d i d a c tr e c o m m e n d a t i o ne n g ir l e ) ，可以利用浏览者行为，对各个推 荐规则的权值进行动态的调整，有效地解决了多推荐规则的权重问题。论文首 先介绍了相关领域的研究，在此基础上提出了s a r t s 框架，继而讨论了相关的 算法、实验和完善s a r t s 需要进一步研究的方向。 关键词：w e b 日志挖掘，实时推荐，关联规则，频繁项集 o 。t 7 a b s t r a c t s e l f - a d a p t i v er e a lt i m er e c o m m e n d a t i o ns y s t e mi saa p p l i c a t i o no f d a t am i n i n g t e c h n i q u e st ow e bl o gd a t ai no r d e r t om a k et h ew e bs i t ee a s yt ob r o w s e a sw e b s i t e sc o n t i n u et og r o wi ns i z ea n dc o m p l e x i t y , t h er e s u l t so fw e b l o gm i n i n gh a v e b e c o m ec r i t i c a lf o ran u m b e ro f a p p l i c a t i o n ss u c ha sw e b s i t ed e s i g n b u s i n e s sa n d m a r k e t i n gd e c i s i o ns u p p o na n dp e r s o n a l i z a t i o n m o s to fp r e v i o u ss t u d i e su s et h e r e s u l t so fw e b l o gm i n i n g a st h ei n p u to fd e c i s i o ns u p p o r ts y s t e m i nt h i st h e s i s ， w b p r e s e n tas e l f - a d a p t i v er e a lt i m er e c o m m e n d a t i o ns y s t e m i n f r a s t r u c t u r en a m e d s a r t s ( s e l f - a d a p t i v e r e a lt i m e r e c o m m e n d a t i o n ) w h i c hp r o v i d e a u t o m a t i c r e c o m m e n d a t i o nf o rc u r r e n tu s e lw ea l s o p r e s e n t a s y s t e m n a m e d a d r e ( a u t o d i d a c t r e c o m m e n d a t i o n e n g i n e ) ，w h i c hs o l v e st h ep r o b l e mo fa d j u s t i n g w e i g h tf o rm a n y r e c o m m e n d a t i o nr u l e s t h et h e s i sf i r s ti n t r o d u c e ss t u d i e sj nr e l a t i v e f i e l d s ，t h e nd e v e l o p sa l la r c h i t e c t u r ea n da l g o r i t h m sf o rp e r f o r m i n gs a r t s t h er e s t o ft h i sc h a p t e rf o c u so ns o m ep r o b l e m sm u s tb ec o n s i d e r e d ，e x p e r i m e n t sa n dt h e p o s s i b l ef u r t h e rs t u d i e st om a k es a r t sp e r f e c t k e yw o r d s ：w e bl o gm i n i n g ，r e a l t i m er e c o m m e n d a t i o n ，a s s o c i a t i o nr u l e s ， f r e q u e n ti t e m s e t 第l 页 一种雉十服势器占挖掘的自适臆实时推荐网站框架 第一章导论 近几年，随着网络技术的发展和浏览者需求的增加，因特网的规模和影响 都得到了很大的发展。根据c n n i c ( 中国互联网络信息中心) 2 0 0 2 年1 月的中 国互联网络发展状况统计报告，仅在中国，w e b 网站( 包括c n 、c o m 、n e t 、o r g 下的网站) 就约有2 7 7 ，1 0 0 个。 要建设一个好的网站，仅仅提供丰富的内容是不够的。对于一个大型的网 站，由于信息量大，往往存在一些比较“偏僻”的网页，很难被访问到。所以 了解网站浏览者的兴趣，并指导其进行方便快捷的浏览是非常重要的。 1 1 自适应实时推荐网站概述 本论文提到的自适应实时推荐w e b 网站，概括的说，就是从浏览者的历史 浏览行为中，发现浏览者的浏览模式，包括浏览者聚类，页面聚类，频繁访问 路径，频繁访问页组等。而历史的浏览模式，将被用来引导在线浏览者的浏览 行为，提供更加方便和个性化的服务。 “个性化网站”的建设，也是近几年研究比较多的一个课题。本论文研究 的自适应实时推荐网站，虽然也是要为浏览者提供个性化的服务，但是和传统 的个性化网站有所不同。传统的个性化网站，是通过动态网页技术( 如a s p 、 j s p 、p h p 等) 来实现。它首先为每一位浏览者建立一个p r o f i l e 文件，存储该 浏览者的相关信息。当浏览者登陆，或者通过其他的技术，能确认当前浏览者 身份时，w e b 服务器根据浏览者信息，执行后台脚本，动态生成浏览者的个性 化网页。这种技术确实能为浏览者提供较好的个性化服务，但是缺点也很明显。 主要表现为： 个性化网页的生成规则，一般是分散地嵌入在后台脚本里面，逻辑 相对固定，不方便修改。 浏览者的每一个页面请求，都需要w e b 服务器执行一段脚本，如果 访问量大，势必对性能造成较大的影响。 个性化的效果，很大程度上取决于浏览者的资料是否完整和准确。 浏览者在注册和使用过程中，不断将自己的兴趣爱好进行回馈，这 种协作式的方法得到的数据是主观的，也是静态的。最重要的一点， 浏览者出于保密的考虑，或者不愿意麻烦，未必愿意提供自己的个 人信息。 自适应实时推荐网站，也叫智能导航网站。它以浏览者的浏览模式来提高 第2 页 一种基于服务器f _ i 志挖掘的自适应实时推荐网站框架 网站的组织和展现。其最大特点，就是不需要浏览者的协作而提供给浏览者个 性化的服务。这是一项原理和技术相对简单，但又非常有实用价值的技术t 大 致分为四个阶段： 1 数据收集： 数据收集是数据挖掘、模式分析和自适应实时推荐的基础。理论上，凡是 能体现出浏览者在浏览网站时兴趣偏好的数据，都应该加以收集。客户端的 c o o k i e 、代理和w e b 服务器、内容服务器的各种日志，都能或多或少的反映浏 览者访问时的情况。比如：该浏览者是从哪个网站( 入口) 进入的( 或是直接 键入u r l 地址) ；他在哪些页面中停留的时间较长以及分别是多少时间，或由此 页面打开的内部链接最多；浏览者最关心的是哪些方面的新闻和消息；他在这 个网站上一共停留的时间；以及该浏览者的所在地域等。 在实际的应用系统中，不必要也不可能对所有的相关数据都加以收集。这 有技术上的原因，也有非技术的原因：浏览者的意愿。 当前w e b 的一些协议标准也限制了我们获得精确的数据。比如：w e b 服务 器的访问日志，不论是c l f ( 通用日志格式) 还是e c l f ( 扩展通用日志格式) ， 对每一次访问，都只是存储了时间、i p 地址、请求方法等有限的内容。再比如： 目前流行的浏览器只能保存总共3 0 0 个c o o k i e ，每个c o o k i e 有4 k 的容量限制， 每个域或服务器只可以在客户端放置2 0 个c o o k i e 。i n t e r n e t 上普遍存在的代 理服务器，也使得数据的收集更加复杂。这些问题将在后面的章节中做进一步 的讨论。 有一种方法可以让网站收集到更多更精确的数据：定制专用的浏览器和w e b 服务器。但是对于一个网站而言，这样的做法显然是不现实的。不少的企业和 标准化组织，也在一直试图寻找到一种最佳的方案：不侵犯浏览者隐私、不影 响性能、而同时又能保留“恰到好处”的数据。w 3 c 提出的p 3 p ( p l a t f o r mf o r p r i r a c yp r e f e r e n c e s ) 标准可让浏览者控制个人资料在网络上的暴露程度。若 浏览器和网站同时支持这一标准，浏览器将在下载页面前向用户提示该网站的 隐私保护等级。p 3 p 是一种规范，可以使用户的浏览器自动理解一个网站的隐 私保护政策，因为它要求网站把它们的隐私保护政策嵌入网站的代码中。微软 推出的i e 6 就支持p 3 p 标准。新的标准，将有利于更方便地收集更多更精确的 浏览数据。 本文中设计的s a r t r 框架，数据收集是针对w e b 服务器的日志进行的。因 为这里集中了较多的有用数据，也非常方便获得。 2 数据挖掘： 通过上一步收集到的数据是杂乱的，必须对其进行挖掘，以得到有用的信 第3 页 一种基于服务器l | 忐挖掘的自适应实时推荐捌站框架 息。这一个阶段，可以利用传统数据挖掘技术的成果。 就分析和建立模型的技术和算法而言，网站的数据挖掘和原来的数据挖掘 差别并不是特别大，很多方法和分析思想都可以运用。不同的是：网站的数据 有很大一部分来自于点击流( c 1 i c k s t r e a m ) ，这和传统的数据库格式中的结构 化数据有所区别。因而本阶段很重要的一步，就是数据的预处理，将分散的、 凌乱的数据整理成格式化的数据。预处理的相关技术，将在第四章做较为详细 的阐述。 3 模式分析： 在自适应实时推荐的领域中，模式分析利用挖掘出来的数据，并结合网站 结构，以得到有一定“语义”的浏览模式。浏览模式是浏览者兴趣的体现。 模式分析主要用到人工神经网络的相关技术。仿照生理神经网络结构的非 线形预测模型，通过学习进行模式识别。 4 自适应实时推荐： 本阶段是对上述步骤得到结果的应用。网站依据历史浏览数据的分析结果， 当该浏览者( 或者有类似兴趣的浏览者) 再次访问同一网站时，动态为他推荐可 能感兴趣的页面。当然，如果浏览者愿意的话还可以进步改进这种定制，通 过这种自动化的定制，再加上人工的配合，足以让浏览者更为省时省力的获取 所需信息。这样使得每位浏览者的页面变得非常个性化，以迎合浏览者的需要。 自适应实时推荐技术最关键的是在相对复杂的过程中，浏览者和网站工作 人员都可以做到无须对浏览过程进行任何形式的设置，整个定制过程都由计算 机自行完成。这样即便是最初级的上网浏览者也能在这样的几次访问后迅速达 到提高效率的目的。 l - 2 建设自适应实时推荐网站的意义 在电子商务早期阶段时，w e b 网站数据流分析通常不过是在主页上安装计 数器以及在一个外部日志文件上运行简单的统计程序以记录点击率。但是，业 界领导们很快意识到简单的点击计数既不准确也远未达到营销目的所需的详细 程度。因此，各公司开始寻找更先进的分析工具，这类工具可以提供谁在访问 公司w e b 网站以及访问者一旦进入网站后将做些什么的全面信息。 对于为数众多的w e b 网站而言，当前是一个“适者生存”的互联网时代。 对于商务网站尤其如此。因为它们的可以浏览者从一个电子商务网站转换到竞 争对手那边，只需点击几下鼠标即可。建立起一个电子商务网站并不困难，困 难的是如何让这个电子商务网站有效益。要想有效益就必须吸引浏览者，增加 能带来效益的浏览者忠诚度。网站的内容和层次、用词、标题、奖励方案、服 第4 页 一种攮十服务器ii 占挖掘的白适应实时推荐网站框架 务等任何一个地方都有可能成为吸引浏览者、同时也可能成为失去浏览者的因 素。而同时电子商务网站每天都可能有上百万次的在线会话，生成大量的记录 文件( l o g f i l e s ) 和登记表，如何对这些数据进行分析和挖掘，充分了解浏览 者的喜好、购买模式，设计出满足于不同浏览者群体需要的网站，进而增加其 竞争力，几乎变得势在必行。若想在竞争中生存进而获胜，就要比竞争对手更 了解浏览者，就要浏览数据进行深度挖掘和分析。 在网站的建设初期，往往是根据工程师的经验将信息分类组织。这个安排 是否合理，还需要分析浏览者的浏览行为来做出判断。比如一个商务网站，在 访问“书籍销售”的浏览者中，有5 0 也会访问“服装销售”的页面，而“书 籍销售”与“服装销售”之间并没有链接，这势必给浏览者的使用带来不便。 那么，如何知道浏览者的浏览行为呢? 这成了网站提供更好服务以吸引浏 览者的一个关键。 在对网站进行数据挖掘时，所需要的数据主要来自于两个方面：一方面是 浏览者的注册信息。但有的时候，浏览者并不愿意把自己的背景信息填写在登 记表上，这就会给数据分析和挖掘带来不便；而另外一部分数据主要来自浏览 者的点击流，此部分数据是浏览者浏览行为的体现，会存储在w e b 服务器或者 代理的日志中。 对于一个小型的网站，通常日访问量也有上万的p a g e - v i e w ，以每条日志 纪录为l o o b y t e 计算，访问同志将会有m e g a b y t e 级的数据量。手工分析如此大 量的数据不但不精确科学，而且不现实可行。引入数据挖掘技术，可以快速准 确的发现隐含在日志里的浏览者浏览模式，如频繁访问路径、频繁访问页组、 浏览者聚类等。 网站可以根据历史浏览模式，对网站的框架和内容进行调接。这些调整可 以是手工实现。由人来对挖掘的结果进行合理性分析，在此基础上调整网站的 框架和内容，可以避免可能存在的挖掘规则的不合理性。但是缺点也是很明显 的：费时费力；不能保 正调整的过程中出现这样或那样的错误；网站的改动， 对于所有的浏览者而言都是完全一样的。另外一种更为有效的办法是：让网站 根据当前浏览者的浏览模式，预测浏览者即将发生的行为，由此动态调整网站 的结构和内容，以给不同浏览者提供个性化的服务。目前的商务网站的“智能”， 一般是根据浏览者的注册信息和历史购物纪录来实现的。把日志的挖掘结果合 理加以应用，必将使网站达到更高层次的智能化，在激烈的竞争中取得优势。 1 3 网站现状分析 我们从自适应实时推荐的角度来考察一下数目繁多的w e b 网站。根据网站 第5 页 二塑苎：! 竖丝登! ! ：苎丝塑塑! 垩生壅盟堡垄鬯些堡丝 一 是否实现，或者说在多大程度上实现了自适应实时推荐，我们可以把网站分为 四个等级： i 0 级。网站根据浏览者请求的u r l 返回响应的页面。对于同一个u r l 来说，每个浏览者看到的内容都相同。 i i 1 级。网站从浏览者的请求页面中提取该页面的内容主题，自动搜 索与此主题相关的页面。服务器将搜索到的页面的超联接包含在浏 览者请求页面中，一并返回。网站可以根据同志的挖掘结果( 频繁 项集、关联规则等) 做适当的联接推荐，但是这仅仅实现了网站的 “内容相关”，没有考虑不同浏览者之间的差异。 i i l 2 级。这一级中，一个重要特点就是进行了浏览者的鉴别。网站根 据浏览者的行为特征将其进行分组，并提取各组的一些公共浏览模 式。在此基础上，根据在线浏览者的行为特征推断其所属的组，并 通过该组的公共浏览模式，指导该浏览者对网站进行快速方便地访 问。 i v 3 级。对于每一个浏览者，网站不需要利用注册信息和c o o k i e ，也 不依赖固定的i p 地址，就可以较为准确地识别该浏览者。然后根 据浏览者独有的访问纪录发现他的兴趣所在，自动推荐更新的、没 有访问过的并且将有兴趣访问的页面。 目前，大部分网站处于0 级自适应水平，少数处于1 级。2 级和3 级仅 处于实验室阶段。然而，随着网络和网络服务的发展，人们需要更多的个性 化服务，2 级和3 级是将来研究的热点。而由于除了注册信息和c o o k i e ，还 没有一种可行的方法，能准确鉴别浏览者身份，所以目前3 级自适应的实现 还相当困难。本论文将着重讨论建设2 级自适应实时推荐网站的相关技术。 1 4 相关研究的成果及本课题的创新之处 目前，“网络数据挖掘”和“个性化网站”都是研究的热点问题，也和本课 题有诸多相似之处。我们通过分析这两个问题的研究路线和成果，来说明本课 题的创新之处。 根据不同的挖掘对象，可以将网络数据挖掘分为网络内容挖掘伸e b c o n t e n tm i n i n g ) 、网络结构挖掘( w e bs t r u c t u r em i n i n g ) 以及网络用法挖掘 ( w e bu s a g em i n i n g ) 。就和本文密切相关的网络用法挖掘而言，研究的路线一 般可以表示为图1 4 1 。 第6 页 种螭十服务器j 矗挖掘的自适应实时推荐嘲站框架 图i 4 1 网络用法挖掘的一般步骤是：首先对同志文件进行清理，采用一定的算法， 鉴别浏览者s e s s i o n 文件，在此基础上挖掘出“关联规则”等信息，分析浏览 者的兴趣，并将结果可视化，由网站的管理者进行决策，调整网站的内容和结 构。这种网络用法挖掘的方案，可以根据浏览者的浏览行为，发现网站结构和 内容安排中存在的不合理性并加以克服。但是这种方案，并不是一个建设自适 应实时推荐网站的方案。因为它没有考虑到浏览者的区别，没有实现任何的个 性化( 对网站的修改是物理层面的修改，这样的修改对所有的浏览者而言足一 样的) 。 网络用法挖掘的研究相对成熟，有一套较为完善的技术和方法，并在商业 领域得以应用。i b m 公司的s p e e d t r a c e r 系统就是其中一个较为成功的例 子。s p e e d t r a c e r 从日志文件中识别会话，在此基础上，利用数据挖掘算法发 现常用路径和频繁页组，并提供基于浏览者、基于路径和基于组的统计报告。 另一个与本课题比较类似的研究是关于个性化网站的建设。其关键点是如 何收集用户的兴趣爱好。一般的思路是：为每一个用户建立一个p r o f il e 文件。 文件的格式由管理员设定。文件的内容，可以来源于用户的手工输入，也可以 根据对用户行为的分析而自动产生。 实施个性化所依据的数据来源于两个方面：用户的注册和对用户行为的分 析。而用户的注册是生成p r o f il e 文件的触发器，是对用户进行行为分析的基 础。假设一个网站需要了解用户对旅游、汽车和摄影是不是感兴趣，同时又不 第7 页 一种热十服务器il ，挖掘的自适廊虫时推荐时站框架 愿意给用户造成不便，就可以根据用户的历史行为，判断该用户是否经常访问 相关的内容，进而判断该用户的兴趣。这通常也是挖掘服务器日志来实现的。 这样的个性化以具体用户为个性化粒度。然而，不是所有的浏览者都愿意注册 成为用户，也不是所有的网站都必须要求进行注册。个性化网站的工作原理如 图1 4 2 所示。 需要指出的 足：在本节中， 我们使用的是 “用户”这个 词，而不象其他 章节中使用的 “浏览者”。因为 通常个性化网站 是针对注册者而 言的，而本 论文着重研究的 是未注册的访问图1 4 2 者( 本论文中称之为浏览者) 的行为，这样的行为是以群组为粒度的。 前面提到，自适应实时推荐网站的工作经过四个阶段：数据收集、数据挖 掘、模式分析和自适应实时推荐。前三个阶段是离线进行的，都是为实现自适 应实时推荐做准备。这和网络用法挖掘的前期步骤是基本一致的。自适应实时 推荐网站也要实现个性化的推荐，但浏览者和网蟊占工作人员都无须对浏览过程 进行任何形式的设置，个性化的定制过程是自动完成的。自适应实时推荐网站， 是未来网站的一个发展方向，它适用于诸如新闻、商务等多种类型的网站。 本论文的创新之处在于结合了“网络用法挖掘”和“个性化站点”的相关 研究，提出一个可行的自适应实时推荐网站的框架s a r t r ( s e l f a d a p t i v er e a l t i m er e c o m m e n d a t i o n ) 。根据w e b 网站的实时性特点，应用数据预处理和数据 挖掘的技术，以浏览者群组为离线挖掘的粒度，而对于实时的推荐，则依赖于 浏览者最近几次的请求，是以不同的浏览者为粒度的，充分实现了个性化的推 荐。本论文还设计了一个基于浏览者反馈的自学习推荐引擎a d r e ( a u t o d i d a c t r e c o m m e n d a t j o ne n g i n e ) ，可以利用浏览者行为，对各个推荐规则的权值进行 动态的调整，有效地解决了多推荐规则的权重问题，使得浏览的过程，就是一 个自学习、自适应的过程。关于自适应实时推荐网站的研究还处于起步阶段， 本论文提出的框架、设计以及对相关算法的研究和实验，具有较强的理论意义 第8 页 一种基于服务器f 志挖掘的自适应实时推荐网站框架 和实际意义。 1 5 论文结构 本论文共分为七章，第一章为导论，主要介绍自适应实时推荐网站的概念、 特点及其建设的必要性。交待了国内外相关的研究成果以及本论文的创新之处。 第二章是基于服务器日志挖掘技术综述。简要介绍数据挖掘的相关技术， 并介绍了网络数据挖掘的特点、难点和分类。着重讨论基于服务器日志挖掘技 术的相关问题。 第三章提出了一种基于服务器日志挖掘的自适应实时推荐w e b 网站的总体 框架s a r t r 。介绍建设一个自适应实时推荐w e b 网站，总体上需要那些构件， 这些构件分别完成什么功能。而这些构件如何实现，会在以后的章节里介绍。 第四章、第五章设计了自适应实时推荐网站s a r t r 的离线部件。其中第四 章讨论数据的来源和预处理过程，第五章讨论数据挖掘和模式分析。着重研究 为完成本领域的挖掘任务，通常采用的挖掘技术、算法和实验。 第六章设计了自适应实时推荐网站s a r t r 的在线部件。主要讨论的问题有 推荐的生成规则、直接基于频繁项集计算推荐项、固定窗口宽度的会话模拟和 基于浏览者反馈的多规则权重自学习系统。本章中还完成了直接基于频繁项集 计算推荐项的实验，作为系统的部分实现。 第七章是对将来研究方向的一个展望，提出了完善s a r t r 需要进一步研究 的若干方向。 第9 页 一种基于服务器臼志挖掘的自适应实时推荐网站框架 第二章基于服务器日志挖掘技术综述 2 1 数据挖掘技术简介 j o h nn a i s b e t t 在他的大趋势中提到：“人类正被数据淹没，但人类渴 望知识。”而数据挖掘，就是一个从数据中得到知识的过程。数据挖掘这一术语 出现在1 9 8 9 年，比较流行的定义是u f a y y a d 等给出的： 数据挖掘就是从数据集中识别有效的、新颖的、潜在有用的、并且最终可 理解的模式的非平凡过程。 这里简单解释几个概念：过程通常指多阶段的一个过程，设计数据准备、 模式搜索、知识评价、以及反复的修改求精：这个过程是非平凡的，即要求有 一定程度的智能性、自动性。有效性是指发现的模式对于新的数据仍然有一定 的可信度。新颖性要求发现的模式是前所未知的。潜在有用性是指发现的知识 将来有实际效用。最终可理解性是指发现的模式可以被人理解。有效性、新颖 性、潜在有用性、最终可理解性综合在一起可以称为兴趣性( i n t e r e s t i n g n e s s ) 。 传统的数据挖掘( d a t am i n i n g ) 技术是对数据库采取半自动的方式，寻找 特定的模式关联规则、变化规律、异常信息等具有统计意义的结构和事件。简 单的说，就是从海量数据库中挖掘有用信息的技术。 数据挖掘的前身即知识发现( k n o w l e d g ed i s c o v e r y ) ，它源自于人工智能 的机器学习领域，其实质的内涵是在一个已知状态的数据集( d a t as e t ) 上， 通过设定一定的学习算法，从数据集中获取所谓的知识。人工智能领域中的知 识发现技术已经发展到了一个很成熟的阶段，但是由于缺乏应用的土壤，它的 路越走越窄。而与此同时，数据库技术也已经发展到一定的阶段，并得到了广 泛的应用，各个企业都已经积累了无数的数据资源，迫切需要有一种技术能够 帮助他们从数据中发掘出其内在的规律，数据挖掘技术正好能满足这一需求， 它实质上就是知识发现技术在数据库领域中的应用。 2 i 1 数据挖掘的主要模型 ( 1 ) 关联规则模型 发现数据项之间的相互关系是十分重要的，根据这种关系可以从数据中找 到有意义的模式和趋势。以超级市场为例，每个记录包含了一次采购商品的列 表，其中关联关系告诉我们两件或更多商品之间的关系。如8 0 的顾客购买了 面包和牛奶，其中有6 0 的顾客在买面包的同时买了牛奶。我们把这种面包和 第l o 页 一种基于服务器口志挖掘的自适应实时推荐网站框架 牛奶之间的关联关系用下列规则方式表示为：面包一牛奶i ( 6 0 ，8 0 ) 。数据 项的关联关系也可以在多个项之间产生，例如：面包、牛奶一甜酱i ( 6 0 ， 4 0 ) 等。目前采用的典型关联算法有a p r i o i r 算法和p t t p 散列表算法等。 ( 2 ) 神经网络模型 神经网络方法是模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础 而建立的，主要有三大类多种神经网络模型。 前馈式网络：以感知机、反向传播模型、函数型网络为代表，可用二f 预测、模式识别等方面。 反馈式网络：以h o p f i e l d 的离散模型和连续模型为代表，分别用于联 想记忆和优化计算。 自组织网络：以a r t 模型、k o h o n e n 模型为代表，用于聚类。 神经网络的知识体现在网络连接的权值上，是一个分布式矩阵结构。神经 网络的学习体现在神经网络权值的逐步计算上( 包括反复迭代或累加计算) 。 ( 3 ) 粗糙集理论模型 粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家 z p a w l a k 于1 9 8 2 年首先提出。粗糙集的研究主要基于分类。分类和概念 ( c o n c e p t ) 同义，一种类别对应于一个概念( 类别一般表示为外延即集合， 而概念常以内涵的形式表示如规则描述) 。知识由概念组成，如果某知识中含有 不精确概念，则该知识不精确。粗糙集对不精确概念的描述方法是：通过上近似 概念和下近似概念这两个精确概念来表示。一个概念( 或集合) 的下近似( 1 0 w e r a p p r o x i m a t i o n ) 概念( 或集合) 指的是，其下近似中的元素肯定属于该概念； _ 个概念( 或集合) 的上近似( u p p e ra p p r o x i m a t i o n ) 概念( 或集合) 指的 是，其上近似中的元素可能属于该概念。粗糙集方法有几个优点：不需要预先知 道额外信息，如统计中要求的先验概率和模糊集中要求的隶属度、算法简单、 易于操作。 2 2 2 数据挖掘用到的相关技术 1 人工神经网络( n e u r a ln e t w o r k ) ： 测模型，通过学习进行模式识别， 种挖掘任务。 它仿照生理神经网络结构的非线形预 可以完成分类、聚类、特征挖掘等多 2 遗传算法( g e n e t i ca l g o r i t h m ) ：基于进化理论，并采用遗传结合、遗 传变异、以及自然选择等设计方法的优化技术。 3 决策树( d e c i s i o nt r e e ) ：用树形结构来表示决策集合，这些决策集合通 过对数据集的分类产生规则。典型的决策方法有分类回归树( c a r t ) ，一 第1 1 页 种撼于服务器日志挖掘的自适应实时推荐嘲站框架 般用于分类规则的挖掘。 4 近邻算法( n e a r e s tn e i g h b o r ) ：通过k 个最与之相近的历史纪录的组合 来辨别新的纪录，有时也称为k 一最近邻方法。这种技术一般用于做聚类、 偏差分析等挖掘任务。 5 规则归纳( r u l ei n d u c t i o n ) ：从统计意义上对数据中的“如果一那么”规 则进行寻找和推导。在关联规则的挖掘中应用。 2 2 基于i n t e r n e t 的数据挖掘技术分类 面向i n t e r n e t 的数据挖掘可以说是一个比较前瞻性的问题，称为i n t e r n e t m i n i n g 或者是w e bm i n i n g 。面向i n t e r n e t 的数据挖掘比面向单个数据仓库的 数据挖掘要复杂得多。因为传统数据库中的数据是结构化的，而i n t e r n e t 上的 数据其最大特点是半结构化的，这就决定了面向i n t e r n e t 的数据挖掘将是一个 颇具挑战性的课题。所谓半结构化是相对于结构化和非结构化而言的。例如传 统数据库中的数据结构性很强，我们称之为完全结构化的数据，而同时还存在 一些诸如一本书、一张图片等完全无结构的数据。但是i n t e r n e 1 上存在的数据 既不是完全结构化的也不是完全非结构化的，因为它的页面也具有一定的描述 层次的，存在一定的结构，所以我们将它称为半结构化的数据。 根据不同的网络数据挖掘对象，人们将网络数据挖掘分为网络内容挖掘( w e b c o n t e n tm i n i n g ) 、网络结构挖掘( w e bs t r u c t u r em i n i n g ) 以及网络用法挖掘 ( w e bu s a g em i n i n g ) 。 ( 1 ) 网络内容挖掘：网络信息内容是由文本、图像、音频、视频、元数据 等形式的数据组成的。网络内容挖掘就是一个从网络信息内容中发现有用信息 的过程。由于网络信息内容有很多是多媒体数据，因此网络内容挖掘也将是一 种多媒体数据挖掘形式。 ( 2 ) 网络结构挖掘：网络结构挖掘就是挖掘w e b 潜在的链接结构模式。通 过分析一个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。 这种模式可以用于网页归类，并且由此可以获得有关不同网页间相似度及关联 度的信息。网络结构挖掘有助于浏览者找到相关主题的权威网站。页内结构就 是h t m l 或x m l 文件里面t a g 的安排。页间结构是指不同页面之问的链接。 ( 3 ) 网络用法挖掘：网络内容挖掘和网络结构挖掘的挖掘对象是网上的原 始数据，而网络用法挖掘面对的则是在浏览者和网络交互的过程中抽取出来的 第二手数据，包括网络服务器访问记录、代理服务器日志记录、浏览器日志记 录、浏览者简介、注册信息、浏览者对话或会话信息等。通过网络用法挖掘， 可以了解浏览者的网络行为数据所具有的意义。 第1 2 页 一种拱于服务器l i 志挖掘的自适心实时推荐嘲站框架 2 3 基于服务器日志的数据挖掘技术简介 要建设一个自适应实时推荐的网站，首先要了解浏览者是如何访问这个网 站的，也就是要进行网络用法的挖掘。通过网络用法挖掘，可以了解浏览者的 网络行为数据所具有的意义。如前所述，挖掘的数据来源包括网络服务器访问 记录、代理服务器日志记录、浏览器日志记录、浏览者简介、注册信息、浏览 者对话或会话信息等。 本论文的研究目的，是要设计一个不需要浏览者协作的、具有自学习功能 的自适应实时推荐网站。研究的对象，是没有留下个人信息的浏览者。这决定 了数据主要 来源于服务 器端的日 志，通常是 e x t e n d e d c o m m o n l o g f o r m a t ( e c l f ) 格 式的服务器 同志。 基于服 务器日志挖 掘的高层视 图可以用图 2 3 表示，详细的过程， p s e s s i o n 文什 翼簇鬟盎 用户的兴趣 一一一1 一 图2 3 我们将在第四章和第五章中做进一步的研究。 第1 3 页 种堪于服务器f j 忠挖掘的白适心实l 寸推荐旧站框架 第三章一种自适应实时推荐网站框 架：s a r t r 概括的说，一个实用的自适应实时推荐网站，可以分为离线部件和在线部 件两部分：离线部件进行数据的收集、预处理，完成特定用法挖掘任务：频繁 项集( f r e q u e n ti t e m s e t s ) 、关联规则( a s s o c i a t i o n r u l e s ) 的发现等等。一旦 挖掘完成，在线部件将根据挖掘出来的规则，并根据浏览者的当前行为，实现 自适应的实时推荐。最简单的在线部件要包括一个推荐生成引擎和w e bs e r v e r 。 w e bs e r v e r 保持浏览者的活动s e s s i o n ，推荐生成引擎根据浏览者的s e s s i o n 、 u r lc l u s t e r s 和已经挖掘的关联规则产生一系列的推荐u r l 。把这些生成的u r l 加入到浏览者最近请求的w e b 页面中。 本论文设计了一种自适应实时推荐网站的体系框架s a r t s ( s e l f a d a p t i v e r e a lti m er e c o m m e n d a t i o n ) 。图3 是它高层工作逻辑图。 图3 中可以看出，s a r t s 的离线部件完成两个任务：数据预处理和数据挖 掘。 预处理过程分为以下五个步骤： 1 数据清理( d a t ac l e a n i n g ) 主要是把多个s e r v e r 的l o g 进行整理， 分析，去除对挖掘没有意义的项，如图片文件的请求项。 2 浏览者和会话鉴别( u s e ra n ds e s s i o ni d e n t i f i c a t i o n ) 把同志中按 时间排列的各个项，整理成多个浏览者的多个会话。 3 页面浏览确认( p a g ev i e wi d e n t i f i c a t i o n ) 4 路径整合( p a t hc o m p l e t i o n ) 5 处理结果格式化( r e s u l tf o r m a t t i n g ) 数据预处理的目的，是从日志中抽取出格式化并且对挖掘有意义的项。它 的结果将作为数据挖掘的来源。详细的处理过程和相关技术，将在第四章做较 为详细的论述。 第1 4 页 一种基于服务器f j 忠挖掘的自适应实时推荐列站框架 离线处理阶段 i 数据预处理 ii 用法挖掘 l 彭“u fl o 推荐联接生成模块i 叫规则投重修改模块l 回! j 多 “。太,e睁o,；,k73 在线处理阶段 图3 数据挖掘( d a t am i n i n g ) 主要包括： 1 频繁项集( f r e q u e n ti t e m s e t ) 和关联规则( a s s o c i a t i o nr u l e s ) 2 聚类( c l u s t e r i n g ) 3 分类( c l a s s i f i c a t i o n ) 4 序列模式( s e q u e n t i a lp a t t e r n s ) 模式发现完成对w e b 对象的建模( 如页面) 、使用角色( 如浏览者) 、对象 和角色的分类、浏览模式的发现等任务。第五章将对本阶段的处理过程和相关 技术做较为详细的论述。 在线部件主要设计的对象有浏览者、w e b 服务器( 内容服务器) 和推荐生成 第1 5 页 种牡于服务器 1 忠挖掘的自适应实时推荐网站框架 模块。推荐的生成依赖数据挖掘和分析的结果，也就是浏览模式。浏览模式的 多样性，决定了一个好的推荐系统，必须考虑多条推荐规则，这些规则的作用 度，应该是根据浏览者的反馈而进行学习和调整的，所以s a r t r 框架中，还设 计了一个规则权重修改和调整的模块，如图3 中模块虚线椭圆圈起的部分所示。 在线推荐的相关问题，将在第六章中做进一步的论述。 第1 6 页 一种基于服务器1 7 忠挖掘的自适应实时推荐刚站框架 第四章数据收集和w e b 日志数据的预处理 4 1 数据来源( d a t as o u r c e s ) w w w 的结构是基于客户服务器( c l i e n t s e r v e r ) 模式，具有平台无关性。 通常服务器对于客户而言是透明的。图4 1 1 简单描述了这种结构： 一 使用代理嘏务器时的信息眦 小使j f j 代理暇务器时的麝强沛 c p霉p ”t 理埘墙讯 f w 窖p w c - b 膈势器m 逝讯 p w 代遵，w e b 瞅务器旧地玳 图4 1 1 全局来讲，w w w 共有三个层次：客户，代理服务器和w e b 服务器( 有些网站 还有单独的内容服务器) 。每一个层次都可以收集到浏览者的访问信息。这些信 息分散于各个层次的访问日志。访问日志可以分为客户级( c l l e n tl e v e l ) 、服 务器级( s e v e rl e v e l ) 和代理级( p r o x yl e v e l ) 。图4 1 2 对此做了高层的抽 象。 画p c 一目i l e u m 一画 i s p 服务器 客户端日志 代理日志 圃一凰 - 印曩务鲁 内容服务。 - e b 服务器日志 内容服务器日志 图4 1 2 在上图中，客户级日志代表了“单浏览者一多网站”的行为。服务器级日志 第1 7 页 一种基于服务器同志挖掘的自适应实时推荐网站框架 代表了“多浏览者一单网站”的行为。代理级日志则代表了“多浏览者一多网站 的行为。 理论上讲，要想获得浏览者的行为数据，可以通过下面八种方法或途径： 1 服务器端数据收集 w e b 服务器的日志记录了每一次网页请求信息。对于网站而言，这些日志 是信息密集而且可以方便地加以利用。本论文也是以服务器日志挖掘为基础的。 2 包监测技术 监视所有到达服务器的数据，提取其中的h t t p 请求信息。 3 网站自身的内容和结构 4 客户端数据收集 5 j a v a s c r i p t s 或j a v aa p p l e t s a p p l e t 能记录浏览者所有的行为但有效率问题；j a v a s c r i t p s 虽然对效率 影响不大，但不能记录浏览者所有的动作。 6 修改过的浏览器 目前有一些开放源代码的浏览器如m o s a i c 和m o z z i1 1 a ，但是如何说服浏 览者使用这些浏览器是一个问题。 7 网络代理端数据收集 8 代理服务器 可以不仅可以收集多个浏览者的行为，还可以收集对多个网站的行为。 4 2w e b 日志数据的预处理 w e b 日志数据的预处理一般要经过以下阶段：数据清理、浏览者会话鉴别、 页面浏览鉴 别和路径整 合。为了适 应进一步的 挖掘任务， 可以对预处 理的结果加 以结构化。 整个预处理 过程，可以 用图4 2 表示。 图4 2 种罐于服务器日志挖掘的自适成实时推荐嗍站框架 数据预处理各个阶段的作用以及相关的技术和算法，将在4 5 小节中分别 加以研究。 4 3e c l f ( 扩展通用日志格式) 日志格式分析 e c l f 是目前被广泛采用的1 3 志格式。每个e c l f 日志项，包括客户i p 地址、 u s e ri d 、访问时间、请求方法、u r i 、r e f e r e n c e 、所用传输协议、状态代码、 返回字节数和使用的代理等内容。e c l f 提供了诸如跟踪引用网页和识别 c o o k i e s 的功能特性。u s e ri d 一项只有在需要浏览者登陆认证的时候才做纪录。 提供记录浏览者数据更先进的机制已经成为w e b 服务器厂商( 如m i c r o s o f t ) 的标准惯例。请求方法一般只有g e t 、p o s t 和h e a d 。g e t 是向服务器请求对象， p o s t 是向服务器发送信息，h e a d 是向服务器请求对象的头部。u r i 可能是静态 的文件，也可能是可执行文件。状态代码由w e b 服务器设置，通常2 0 0 到2 9 9 之间的数字代表成功，3 0 0 到3 9 9 代表某种形式的重定向，4 0 0