Lw

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Lw as PDF for free.

More details

  • Words: 1,130
  • Pages: 14
基于 Web 挖掘和站点拓扑的自适应网站研究 第一 章 绪 论 1.1 研究背景 目前,Internet 己发展成为一个巨大的、蕴涵着具有潜在价值知识的分布式信息空间。 但是随之出现的网络信息泛滥,又给用户带来了许多困扰,如何从纷乱复杂的网站中快速 找到自己需要的数据和信息,如何去掉网站不必要的信息干扰成了许多用户迫切想解决的 问题。 当今,随着 Internet 的复杂性提高,各个 Web 站点的信息量及其复杂度也在迅速上升, 包含成千上万个网页与超链接是很平常的。由于以下的因素,数据密集型 Web 站点的设计与 管理工作变得越来越困难。首先,不同的用户、同一个用户在不同时间有着不同的访问目的。 其次,Web 站点随着时间的推移不断发展,内容逐渐增加,难于管理,Web 站点实际提供的 信息服务往往超出了当初设计的范围,甚至完全改变了定位。对网站经营者来说,如何充分 考虑用户的访问需求和 Web 站点自身的内容和结构,从而设计一个合适、易用、可扩展性强 的 Web 站点? 从 Web 站点管理者的角度,他们希望 Web 站点可以动态地调整页面的结构、改进服务, 开展有针对性的电子商务以便更好地满足访问者的需求。从访问者的角度来说,他们希望看 到的是个性化的、智能的、高效的,能够花费最少的时间看到自己关心的信息的网站系统。为 解决这些问题,计算机学术界开始研究自适应的 Web 站点,它能够通过复杂的学习和判断 逻辑自动地改进 Web 站点上信息的组织与显示,主动地把用户关心的信息“推”向用户, 整个过程不需要用户任何额外的配置工作。

1.2 研究意义 随着 WWW 的普及程度与复杂度的提高,自适应的 Web 站点的研究显得越来越重要。我们 相信,创建自适应 Web 站点这个任务将给计算机科学诸多领域的发展带来深远的影响。很明 显自适应网站不同于传统的网站,它充分体现了以客户为中心、为主导的经营理念。从目前 来看,研究自适应网站,特别是自适应网站的实现技术至少会给用户和网站经营者带来如 下好处。 1) 为用户提供个性化服务。对大多数的 Web 站点来说,让用户感到整个网站是完全为 他(她)自己定制的是 Web 网站充满生机的秘诀。因此可以针对不同的用户,按照其 个人的兴趣和爱好,向用户动态地推荐其感兴趣的内容。 2) 提高系统效率。通过日志挖掘,可以发现用户的需要和兴趣,对需求强烈的网页内 容提供优化,或者从用户的访问行为模式中预测下一个访问行为并且预先做好本 地缓存,从而有助于平衡服务器的负载,优化传输,减少阻塞,最终缩短用户等 待时间,提高系统效率和服务质量。 3) 提高网站结构设计。实现自适应网站通常需要考虑用户的历史访问情况,通过挖掘

用户使用网站情况的海量信息,可以帮助网站设计者对网站的修改更加有目的、有 依据,从而以用户为中心,稳步的提高用户的满意程度。

1.3 自适应网站目前的研究进展 自适应网站系统构建技术是当前的一个研究热点。国外的研究主要关注在具体流程和方 法的改进上,主要有: 1) Schechter 等提出根据用户的访问路径模式预测用户未来可能的 HTTP 请求,让代 理服务器执行预取操作,将相关 Web 页放入其缓存中,以加快访问速度。 2) Cooleyde 和 Buchner 等人利用数据挖掘技术从 Web 访问的日志文件中提取用户的访 问模式,用于市场决策和智能推荐服务。 3) Nasraol 等人采用聚类用户访问模式方法,预测用户未来的访问行为。 国外的这些典型的研究成果基本都是集中在 Web 挖掘方面,关于使用 Web 挖掘研究自 适应网站的具体分支会在第二章详细介绍。 国内自适应网站研究己成为计算机科学工作者所关注的热点问题,主要集中在算法的 改进和应用系统框架的设计。国内互联网上现在也有了专门讨论数据挖据的网站,己经开始 个性化信息方面的研究。但是我国在这方面的理论研究和应用研究还是十分薄弱的,目前国 内几乎没有关于自适应网站的实际应用。 总之,无论是国际还是国内,对自适应网站的研究还处在刚起步阶段,还没有形成比 较成熟的理论和统一的体系,特别是自适应网站的实现技术方面的研究比较欠缺。

1.4 本文的工作 自适应网站有一个指导理念:“以用户为中心,用户既是网站内容的消费者,也是网 站内容的制造者”。因此考虑自适应网站的实现方式就一定要考虑用户的历史访问信息,用 户在访问某个 Web 站点时其访问的时间,页面 URL 及很多信息被记录进相应服务器的日志, 这些日志为创建自适应的 Web 站点提供了原始数据。因为日志文件往往庞大而不直观,所以 本文对它进行自动的分析以发现其中蕴涵的知识,即进行 Web 日志挖掘。 另外站点自身的拓扑结构也是自适应网站研究的重要内容,网页结点自身所处的深度、 联通程度等信息往往体现着该结点在网站地图中的性质,研究这部分内容对于把握用户的 访问偏好、方便用户的访问都有重大的帮助。很遗憾,国内外关于网站拓扑的研究却很少提 及。针对当前自适应网站实现领域研究的不足,尤其是缺乏对网站自身拓扑结构的分析, 本文首先全面介绍自适应网站的概念用途和发展历程,站在用户的角度出发,结合 Web 日 志挖掘和站点拓扑分析提出一种有建设意义的自适应网站的实现架构。

第二 章 自 适应网 站概述 2.1 可适应 (Adaptable) 网站和自适应 (Adaptive) 网站 目前的 Web 站点一般都是被动的,用户需要自己去寻找所关心的信息在哪里,操作繁

琐,非常不方便,尤其是当网站的信息量很大、网页节点层次比较多的时候,花费的时间往 往令用户难以忍受。随着 Web 技术的不断发展,尤其是服务器端脚本结合数据库技术的发展, 以及在 Web2.0 理念浪潮的推动下 Ajax、XML、Dom 等技术的广泛应用,某些网站已经具有了一 定的可适应性,例如以 Google 个性化页面为代表的某些网站提供了与用户交互的个性化功 能,可以基于用户的配置信息向用户提供个性化的内容。 图 2.1-1 是笔者配置好的 Google 个性化页面截图。

图 2.1-1 在使用这种个性化站点时,用户必须首先主动告知 Web 系统自己的兴趣爱好,才能得 到相应的个性化功能,这样的网站称为可适应(Adaptable)网站。可适应网站主要是通过 服务器端动态脚本技术来实现的,它首先要求用户的注册,填写注册信息和偏好配置信息 , 然后为每个用户建立相应的 Profile,用来存储用户的配置信息。当用户访问网站的时候, 首先登录,然后 Web 后台脚本就可以识别用户,加载用户的偏好信息,从而动态生成个性 化网页。可适应网站能够为每个注册用户提供较好的个性化服务,但是缺点也很明显,主要 体现在以下几个方面: 1) 用户必须首先了解网站结构,知道配置功能所处的位置。然而大多数情况下,用户在访 问一个网站前并不了解这个网站,基于用户配置的个性化仍然需要很大的工作量,尤 其是很容易使新用户产生反感。 2) 用户必须清楚自身的需求,主动告诉 Web 站点自己“想要什么”,这是一种单向的行 为。然而用户在上网的时候并不一定十分清楚自己的访问需求,很多的时候需要借助搜 索引擎的帮助。可适应的 Web 网站不能最大限度的了解用户的潜在访问兴趣,不能从根 本上帮助用户找到其最关心的内容。 3) 个性化网页的生成规则一般是分散地嵌在后台脚本里,逻辑相对固定,不方便修改。 4) 必须要求新用户注册。新用户的注册不仅是识别用户的基础,也是收集用户资料的手段。 然而很多浏览者不愿意填写繁琐的注册信息和偏好配置信息。 5) 浏览者的每一个页面请求都需要 Web 服务器执行一段后台脚本,如果访问量大或者访 问请求比较集中,势必会对服务器性能产生较大影响。

6)

个性化配置选项有限。由于可适应网站的个性化功能通常是提供给用户一个有限范围的 选项,用户根据自己的偏好进行选择,很可能用户最关心的内容并不在这个范围内。 自适应(Adaptive)网站与可适应网站的最大不同在于自适应网站会主动学习用户的 偏好,自动的改进 Web 站点信息的组织或显示、改进服务效率、实现有针对的个性化服务、主 动将用户感兴趣的信息“推”向用户,整个过程并不需要用户的任何额外配置工作,甚至 第一次访问该网站的用户也能从中受益。站点用户既是网站内容的消费者(浏览者),也是 网站内容的制造者。

2.2 自适应网站的分类 自适应网站关键在于主动地将用户关心的内容推荐给用户,自动地修改网站的内 容和结构,整个用户不需要用户额外的配置工作。需要强调的一点是虽然自适应网站的自适 应程度、自适应算法质量不尽相同,但从广义上说不论采取何种方式、何种策略和逻辑、何种 算法,只要能主动实现个性化的网站都可以称为自适应网站。 从网站面向的用户规模来分自适应网站可以分为面向单个用户的自适应网站、面向用户 群的自适应网站和面向所有用户的自适应网站。从自适应网站的实现方法上可以分为基于模 式学习的自适应网站和基于策略的自适应网站。所谓“基于策略的自适应网站”是指由相对 固定的后台逻辑来实现网站的自适应,用户对网站的使用情况并不影响后台逻辑。例如有一 个大学生论坛网站,它的后台程序能够识别访问者的 IP 地址从而确定该访问者所在的实际 地理范围。那么当一个同济大学的学生在图书馆访问该网站主页的时候,后台脚本首先识别 出这位访问者是同济大学的学生,接着从数据库中取出该学校近期内的热点新闻同时修改 主页,好像该网站就是为他定制的一样。 由于基于策略的自适应网站逻辑相对固定,自适应程度有限,而面向单个用户和群体 用户的自适应网站往往需要额外的后台数据库支持,需要很大的空间开销,目前网站运营 商并不愿意花费如此大的空间成本,所以本文不做研究。

2.3 自适应网站的主要目标 自适应 Web 站点研究的主要目标有两个:服务个性化与性能最优化。用户从访问一个 站点开始到找到自己所关心的内容所花费的时间主要由两部分组成:用户寻找时间和站点 响应时间。自适应网站的两个主要目标就是要尽可能缩短这两部分时间,从而提高用户上网 效率,改善用户体验。服务个性化用来缩短用户寻找时间,而性能最优化是在其他情况(如 开发语言、服务器硬件配置、算法和数据结构的优化程度)不变的情况下缩短站点响应时间 的一种有效方法。下面详细说明这两个目标。 2.3.1 服务个性化 服务个性化是指 Web 站点为适应某一个特定的用户的需要而实时地调整数据的组织与 显示。一种实现服务个性化的方法是允许用户手工定制 Web 站点的显示选项,系统将记住每 个用户的定制,并在该用户再次进入时进行相应的调整,例如前文提到的 Google 个性化页 面允许用户只看自己所选择的新闻栏目,前文已经提到这显然不是自适应网站采用的方法。 与此相反,路径预测法试图猜测用户在寻找什么信息并帮助他 (她)更快地找到。路径预测 法至少需要回答以下几个问题: 1)预测的容是什么 预测的内容可能是用户的下一步操作,例如系统发现用户在浏览某页面时,其中页面 上的某一个超链接被用户点击的可能性最大,就可以把这个超链接加亮或者提前。预测的内 容也可能是用户的最终访问目标,例如系统发现用户在寻找某个特定的页面,就可以把这 个页面直接弹出来。 2)预测的依据是什么 预测的依据可能是单个特定用户的历史访问行为、注册信息、配置信息等,这些数据往

往存储在网站的后台数据库中。也可能是多个用户的历史访问行为,这些数据主要包括客户 端和代理服务器的 Cookie 以及 Web 服务器(包括负载均衡服务器)和 Web 镜像服务器的 Web 日志中。另外预测的依据也可能是 Web 站点的信息内容和拓扑结构。 3)预测的影响是什么 预测的影响是指预测完成的后续动作是什么。根据预测,可以做的调整包括将某个超链 接加亮、加粗、提前或者在其周围放置醒目的图片、将相似的页面合成一个新的页面、在用户 当前访问的页面中自动添加一个动态导航的网站地图、或者根据预测的结果站点后台程序自 动地修改不合理的拓扑链接等等。 显然路径预测法能够更有效地缩短用户寻找时间,它也是自适应网站研究的主要方法。 2.3.2 性能最优化 这里所指性能最优化是指 Web 站点提高对用户的整体服务性能。实现 Web 站点性能最优 化大体上可以分为两种方法,一种是技术上的,比如增加服务器的硬件配置、购买更大的网 络带宽、算法优化、数据库优化、使用 Ajax 技术实现客户端和服务器端按需传送数据、对经常 访问的静态页面(例如主页)做服务器端页面缓存、对结合数据库生成的动态页面做服务器 端依赖缓存(相关数据库中的数据变化引起缓存刷新)等等,技术上的性能最优化方法不 是我们自适应网站需要讨论的内容。另一种实现性能最优化的方法是基于访问行为预测的缓 冲预取机制,通常站点后台程序根据历史访问记录预测当前用户的下一个访问行为,从而 提前做好服务器或者客户端缓存,当用户请求下一个页面的时候直接从缓存中取出页面数 据,而不是再次请求 Web 服务器,从而大大提高响应时间,据 Microsoft 公司对网页缓存 效率的统计表明,适当的缓存可以使响应时间缩短 100 倍。 根据路径预测法预测依据的不同,缓存面向的对象也分为单个用户和所用用户。如果 缓存面向的是所有用户,即站点并不识别某个具体用户,那么即使是以前对网站一无所知 的新用户,也能够从中获益。这也是本文讨论面向所有用户的自适应网站的主要原因。 另外根据预测结果对站点拓扑结构作更合理的调整也可以改进网站的整体性能,但是 这种改变网站整体物理结构的方式开销较大,一个网站频繁的、大规模的变更其物理拓扑必 然会给网站的管理者带来额外负担,所以这种优化网站性能的方式在实际应用中较少。

2.4 自适应 Web 站点的质量评价 自适应 Web 站点的质量是一个比较难以量化的指标,但是对其进行评价对深化自适应 站点的研究具有重要意义。最基本的评价指标是看用户平均作多少“努力”才能在该 Web 站 点中找到自己需要的信息。除去站点的响应时间(响应时间往往依赖于网站服务器的硬件配 置和程序员的编码质量),用户的“努力”可以简单的定义为点击超链接的次数以及在页 面中寻找这些超链接的困难程度的函数。例如,从一个 Web 站点的首页至少要经过五、六个 超链接才能到达其最受欢迎的页面,那么例如适当地给出不同用户一个浮动的、实时的网站 导航地图,其上直接显示最受用户欢迎的页面,将显然提高该 Web 站点的质量。

2.5 自适应网站研究的主要方向 当前基于 Web 挖掘的自适应网站研究是主流方向,其中根据具体的流程和算法又分为 很多学派。Web 挖掘定义为使用数据挖掘技术在 Web 文档和服务中自动地发掘并提取信息。 基于 Web 挖掘研究自适应网站的学者认为,自适应站点属于 Web 挖掘的一个具体应用分支, 运用 Web 挖掘原理与技术挖掘站点结构的潜在模式,挖掘站点访问者的使用模式,并利用 Web 挖掘的结果对站点进行调整,帮助或改善站点内部的结构模型,建立 Web 站点与站点 访问者间的沟通、协调关系,最终实现自适应站点的目标。数据挖掘和 Web 数据挖掘是自适 应站点应用研究的理论基石。

国内自适应网站研究己成为计算机科学工作者所关注的热点问题,主要集中在算法的 改进和应用系统框架的设计。国内互联网上现在也有了专门讨论数据挖据的网站,己经开始 个性化信息方面的研究。但是我国在这方面的理论研究和应用研究还是十分薄弱的,目前还 没有关于国内数据挖掘产品的报道。

第三章 We b 日志 挖掘 3.1 Web 挖掘概述 传统的数据挖掘 (Data Mining)技术是对数据库采取半自动的方式,寻找特定的模式 关联规则、变化规律、异常信息等具有统计意义的结构和事件。简单的说,就是从海量数据库 中挖掘有用的信息的技术。数据挖掘的前身即数据库知识发现 (Knowledge Discovery in Databases) ,它源自于人工智能的机器学习领域,其实质的内涵是在一个己知状态的数据 集(Data Set)上,通过设定一定的学习算法,从数据集中获取知识。与此同时,数据库技术 也已经发展到一定的阶段,并得到了广泛的应用,各个企业都已经积累了丰富的数据资源 , 迫切需要有一种技术能够帮助他们从数据中发掘出其内在的规律,数据挖掘技术正好能满 足这一需求。 Web 挖掘是数据挖掘的一个子领域,所以它符合一般数据挖掘的原理和研究方法,但是由 于 Internet 提供了一个海量的信息源,Web 包含大量的文本信息,动态的链接信息以及使 Web 页面的信息,Internet 数据有无序、结构化、非结构化并存和数据冗余量大的特点,传 统的基于关系数据库的数据挖掘方法不再适用 Web 挖掘,需要应用新的数据模型应用于研 究。Web 数据挖掘就是利用数据挖捆技术,自动的从 Web 文档以及服务中发现和抽取信息的 过程。Web 挖掘能够为网站运行提供深入的、准确的、详细的分析数据和有价值的、易理解的 分析知识。通过提供这些数据和信息,可以帮助设计者优化网站运行的效率、提高用户对网 站的满意程度。 一般地,可以将 Web 数据挖掘分为四个步骤: 1) 确定业务对象: Web 数据挖掘的最后结构是不可预测的,不能盲目的为了数据挖掘而 数据挖掘。在整个 Web 数据挖掘的过程中,被研究的业务对象是挖掘过程的基础,它驱 动整个 Web 数据挖掘的全过程,同时,也是检验挖掘结果和引导分析人员完成挖掘的 依据,业务对象对数据挖掘的成败至关重要。 2) 数据准备:Web 数据挖掘的数据来自两个方面:一方面是用户的背景信息主要来源于 客户登记表;而另一部分数据主要来自浏览者对网页的请求和浏览过程中的点击流 (Click stream),这部分数据主要用于考察用户的行为表现。由于客户的背景信息涉及 个人隐私,常常不愿意把个人信息如实填写在登记表上,这就给数据分析和挖掘带来 困难。在这种情况下,不得不从浏览者的表现数据中推测客户的背景信息、客户的嗜好, 进而再加以利用。数据准备首先检索所需的文档,发现资源,然后进行数据预处理,从 而发现网络资源,挑选预处理得到的信息。 3) 数据挖掘:对所得到的信息进行挖掘,发现普遍的模式。 4) 结果分析:对挖掘出的结果,即普遍模式进行确认或者解释,将分析所得到的知识和 模式用于网站的设计和改造。

将 Web 数据挖掘的过程加以改造、量化,很容易应用到自适应网站的实现研究上, Web 数据挖掘的过程同时也是自适应网站的实现过程。

3.2 Web 挖掘的分类 Web 数据挖掘根据所挖掘的对象可以分为三类。Web 内容挖掘,Web 结构挖掘,Web 日 志挖掘。图 3.2-1 给出了 Web 挖掘分类图:

Web 挖掘

Web 内容挖掘

Web 结构挖掘

Web 日志挖掘

图 3.2-1 1)

2)

3)

Web 内容挖掘,描述从 Web 文档发掘出有用的信息的行为,通常 Web 文档包括半结构 化的 HTML 文档,非结构化的文本内容和结构化的 XML 文档,也包括图形、图像、视频、 音频等多媒体信息。其中针对无结构的文本进行挖掘被归类到基于文本的知识发现 (KDT)。Web 内容挖掘一般从两个不同的角度去研究。从资源查找的观点来看,Web 挖 掘的任务是从用户的角度出发,怎样提高信息质量和帮助用户过滤信息。而从数据库的 角度讲,Web 内容挖掘主要是试图对 Web 上的数据进行集成、聚类、建模,以支持对 Web 数据的复杂查询。 Web 结构挖掘,是从 WWW 的组织结构和链接关系中推导知识。它的研究范围不仅限于当 前站点内,而是整个 WWW 世界。同时对象的研究也不仅限于文档之间的链接,还包括文 档内部的结构。每个 Web 页面并不是原子对象,其内部有或多或少的结构。由于 Web 中 包含的结构信息处理起来比较困难,因此通常的 Web 搜索引擎等工具仅将 Web 看作是 一个平面文档集合,而乎略了其中的结构信息。Web 结构挖掘的目的在于揭示蕴含在这 些文档结构信息中的有用模式。 Web 服务器日志挖掘,是用户访问模式挖掘的一种,数据来源主要是 Web 服务器日志。 由于 Web 服务器日志中存储了大量的用户访问信息,对其进行挖掘可以从中提取出感 兴趣的模式。从而帮助理解用户的行为,改进站点结构,或为用户提供个性化的服务。 接下来还会详细介绍这部分内容。

3.3 ECLF( 扩展通用日志格式 )日志格式简介 ECLF 是目前被广泛采用的日志格式。每个 ECLF 日志项包括客户 IP 地址、User ID、访问 时间、请求方法、URI、Reference、所用传输协议、状态代码、返回字节数和使用的代理等内容。 ECLF 提供了诸如跟踪引用网页和识别 Cookies 的功能特性。User ID 一项只有在需要浏览者 登陆认证的时候才做纪录。提供记录浏览者数据更先进的机制己经成为 WEB 服务器厂商 (如 Microsoft)的标准惯例。请求方法一般只有 GET, POST 和 HEAD。GET 是向服务器请求对象, POST 是向服务器发送信息,HEAD 是向服务器请求对象的头部。URI 可能是静态的文件,也 可能是可执行文件。状态代码由 WEB 服务器设置,通常 200 到 299 之间的数字代表成功, 300 到 399 代表某种形式的重定向,400 到 499 代表请求的特定文件的错误,500 到 599 代 表 Web 服务器自身发生的错误。 表 3.3-1 是一个典型的 ECLF 格式的 Web 日志文件。 域

描述

日期 date 客户端 IP(client IP) 用户名(user name) 字节(bytes) 服务器(server) 请求(request) 状态(status) 服务名(service name) 协议版本(version) 用户代理(user-agent) 参照(reference)

请求页面的日期、时间、时区 远程主机的 IP 或 DNS 入口 远程登录的用户名 传送的字节(发送的或接受的) 服务器的 IP 地址和端口 URL 查询 返回给 http 状态标识 用户请求的服务名称 传送的 Http 协议版本 服务提供者 请求本网页的源网页(前一页)

表 3.3-1 图 3.3-2 是一段真实的 Web 服务器日志文件下的一段内容。 客户 端 IP

日期

时间

端 口 请求 方法

页面

协议 版本 状 态码 字 节

图 3.3-2 可以看到一个特定 Web 服务器的日志文件所包含的字段必定是 ECLF 日志格式的子集。

3.4 Web 日志挖掘技术

Web 日志挖掘可分为两个部分,一个是将服务器日志转化为适合的型式,这一部分是 日志的预处理,包括数据的清理、用户识别、事务识别;另一个是从已有的事务集中运用各 类算法得出用户的访问模式和偏好。 3.4.1 数据处理模块 数据处理模块关键是得到全部用户访问网站的事务数据库,这是 Web 挖掘的关键核心 数据。只要能够得到实时的访问事务数据库,再结合用户当前访问的页面结点,就可以算出 用户接下来可能访问结点的概率。数据处理模块从 Web 服务器日志出发,必须经过如下几个 过程。 数据清理 是 Web 日志挖掘的第一步,用户访问网站的时候,Web 日志会记录一些对我们数据挖 掘毫无意义的数据记录,需要我们设计算法对其进行删减和整合。 1 某些 Web 服务器软件(IIS,Apache 等)会把对每个网页的请求分解成若干个对超文本 元素的请求,那么 URL 请求后缀名 jpg,gif 等对我们进行数据挖掘就是冗余的数据。 例如一次浏览者的请求,在 Log 里面通常有如下的几种类型的文件请求: 1) .html:请求的 HTML 文件。 2) .gif 或者 filename.jpg:图片文件,或其它音频、视频文件。 3) <programX.cgi?<argument>:服务器端可执行文件。 2 用户访问的网页不存在,或者由于网络不通,域名解析错误等造成的访问失败也会 在 Web 服务器日志中产生相应的错误代码日志记录项。 3 遵循 ECLF 标准的 Web 日志记录包括用户 IP 地址、用户 ID、用户请求访问的 URL 页面、 请求方法、访问时间、传输协议、传输的字节数、错误代码等属性,而与数据挖掘相关的只有 用户 IP 地址、用户 ID、用户请求访问的 URL 页面及访问时间,其他属性可以去掉。 用户识别 本地缓存机制会使日志中的记载的用户访问频率明显低于用户实际的访问频率。而代理 服务器机制的作用正好相反,由于代理服务器机制会把多个访问用户的 IP 地址合并为一个, 因而日志中的单个用户访问频率会比实际的明显偏高。 对于以上问题,Web 的用户识别有以下几种策略:一旦发现用户的浏览器或者操作系 统改变则认为是不同的用户。借助站点拓扑,一旦发现当前用户不能从上一个访问页面到达 当前页面,则判断为新用户。 事务识别

在对 Web 访问记录进行挖掘之前,必须先进行事务标识的工作。一次用户会话是指某个 用户对于一个 Web 站点的一次访问过程中所引用到的全部页面,事务标识是将一次用户会 话分成多个逻辑单元。可以将事务简单地理解为用户的一次访问目的,一个用户一次访问某 个网站可能有多个访问目的,例如某个用户访问新浪网主页,经过一系列的鼠标点击,先 是看了一篇关于 NBA 的最新战报,而后又关注了一下台海局势的最新状况,最后退出新浪 网。那么该用户访问新浪网的过程就可以划分为两个事务。 关于事务的识别目前有两种比较有效的方法,一个是超时法,另一个称为最大向前访 问路径法。 在跨越时间区段较大的 Web 服务器日志文件中,用户有可能多次访问了该网站。最简单 的识别事务的办法是利用超时,如果两个页面请求的时间差超过一定的界限就认为是一个 新事务的开始。推荐选取 20-30 分钟作为最佳超时界限。另一个事务识别方法称为最大向前 访问路径法,这种方法首先将整个网站拓扑看成树型,用户从开始访问点向下的一次最深 访问称为一个事务。 经过了事务识别后就可以得到访问事务数据库,访问事务数据库中蕴含着抽取用户偏 好所需的所有信息,它是我们进行自适应计算的数据基础。 3.4.2 用户访问模式挖掘阶段 针对不同的自适应站点实现方式,有着不同的用户访问模式挖掘方法。例如:聚类分析 把相似用户或相似内容的页面聚在一起;频繁访问模式算法找出被用户经常同时访问的页 面。而这些算法并不能预测用户的访问路径。这些算法曾经广泛的用在数据挖掘或者工农业 中,然而针对成亿上万的用户访问记录来说,我们希望在设计或者改善算法时坚持以下原 则: 1) 算法具有高效性。由于数据量比较大,而且作为日志信息,数据更新十分快,因此需要 设计能够分析如此之多数据量的算法。 2) 算法具有稳定性。由于用户访问网站时有很多不确定因素。即便预处理阶段的数据过滤 也不能够把不相关的页面全部排除在外,因此算法应考虑到这些不确定因素,并不让 他们影响最后结果。 3) 算法具有可适应性。例如:用户浏览网站页面时因为网站的结构的不同有着不同的浏览 顺序。因此,算法设计需要考虑到这些不同因素。 由于目前各种模式挖掘算法都处在理论研究阶段,很难加以量化,投入应用,故本文 只做简单介绍。下文将继续事务识别后得到的访问事务数据库,进行自适应算法的介绍。

第四 章 网 站拓扑 分析 这章所强调的网站拓扑分析不同于 Web 结构挖掘,两者有以下不同。 1) Web 结构挖掘强调单个网页文件内部也是有结构的,研究粒度更细。而网站拓扑分 析将单个网页文件看成原子结构。 2) Web 结构挖掘关注的是站点所处的整个 WWW 的结构,其研究的结构信息常常跨越 多个站点,而网站拓扑分析将网页看成结点,网页间的链接视为线,并且双向联 通,研究对象仅限于站点内部。 3) Web 结构挖掘的数据对象格式复杂,形式多样,具有高度可变性。而站点拓扑信息 对于站点管理员来说是相对固定的、可知的。 绝大部分网站在设计之初基本上都是树型拓扑结构,虽然后来可能为了方便用户的访

问而添加一些相关结点的链接从而形成网状拓扑,例如在下载站点经常见到的“相关下载 ”链接区。然而这些链接通常是单向的,数量也相对较少,对网站总的拓扑影响不大,故这 里仍然将网站拓扑视为树型。 Web 服务器日志挖掘充分考虑了用户的使用偏好,将用户访问事务数据库和用户访问 网站的当前节点结合起来,和容易判断出用户的下一个访问行为。然而为了用户的访问方便 只是高亮显示用户接下来最可能访问的节点还远远不够。有两个主要原因可以说明这一点: 1) 我们姑且简单的把网站结点的拓扑结构当作树形结构。用户在访问网站的时候可能会希 望了解自己在整个网站的相对位置。举个例子,我们看地图的时候为了清楚的知道自己 所处的位置或为了更方便的到达目的地,总是会去寻找离自己比较近的标志性建筑。同 样的道理我们可以把网站中相对重要的结点抽取出来,并以适当的方式展示给用户, 就可以帮助用户认知自己所处的大环境。本文形象地称这些网页为“地标性结点”或“ 骨架结点”,这些结点可以由网站管理员根据管理的经验手工抽取,但是这样做的工 作量比较大,可以通过本文提出的算法自动获得。 2) 为了简单起见,我们可以把网页分为内容页和导航页。那么显然根据用户访问事务数据 库得到的用户下一个访问结点不一定是用户访问的最终目的结点,用户访问它的目的 可能只是为了导航作用。我们希望适当的向用户推荐访问事务链(用户点击流)上的内 容结点。 可以设计一种周边网页的展示方法,将那些离用户比较近的网页清晰地展示出来。比如, 有些网页结点虽然属于网站的地标性结点,但是由于离当前用户访问的结点距离较远,可 以隐藏起来。在讨论这一章时我们将在 Web 日志挖掘的基础上确定应该向用户推荐哪些网页 结点的自适应网站核心问题。

4.1 地标性结点概述 地标性结点是整个网页地图的地理标志性结点,它应该是相对重要的结点,并满足下 面两个个属性:与其他网页具有较好的连通性、距离主页较近。

4.2 连通性 连通性可以定义为从当前结点可到达的结点数与可以到达当前结点的节点数之和。 Valdez 和 Chignell 认为“与非地标性结点相比,地标性结点与更多的对象相连接,就像 航空系统中的交通枢纽一样”,并提出了“间接联通”的概念。所谓“间接联通”是从当前 结点通过至多两个超链接可以到达的结点个数。在本文中我们假设所有的站点都是树型拓扑 结构,并且不考虑“间接联通”现象。 定义如下符号: I=直接联通入度(in degree) O=直接联通出度(out degree) Connectivity=I+O 具体测算结点联通度的算法可以通过遍历整个树型拓扑,计算每个结点超链接数的方 式获得。当前结点所含有的超链接数在数量上等于直接联通出度,其他所有结点含有的指向 该节点的超链接之和在数量上等于该结点的直接联通入度。 Relative-Connectivity=Connectivity/(Total Connectivity of all Notes)

4.3 结点深度 因为网站通常按照层次结构来设计,处于较高层次的网页(比如主页)通常代表较高 的概念层次,而叶子结点则是比较具体的内容或者服务信息,因此结点的相对深度也是衡 量其重要性的一个重要指标。本文中全局结点的深度指的是某个网页在网站服务器的文件系 统中的层次。显然在网站地图中深度越深的结点重要性越低。 定义如下符号:

D=结点深度(depth) Relative-Depth=1/D 于是,引入综合指标 Importance 来衡量某个具体结点的重要性程度: Importance=Relative-Connectivity*wa + Relative-Depth*wb,其中 wa+wb=1。 显然,重要性大的结点在网站中应该处于相对突出的位置,可以作为浏览者在网站中 的参考坐标。通过设定一个重要程度的阀值,就可以简单的将地标性结点甄别出来。阀值的 大小还可以由网站用户根据其对网站的熟悉程度来动态调节,阀值越大,地标性结点的数 量越少。通过反复调节,地标性结点的数量可以做到既不会因为太多从而使用户必须浏览太 多无关信息,也不会因为太少而对用户无法起到真正的帮助作用。这里我们将 Importance 指标称为“地标系数”。

第五章 自适 应网站 表示层 策略 在这一章中我们要探讨的是自适应网站与用户的交互,即网站向用户提供怎样的服务 的问题。

5.1 智能推荐 5.1.1 高亮 高亮是针对现有网页结点上已存在的链接而言的,通常情况下一个网页上会有数以百 计的链接,如果链接的组织不够合理,层次不够清晰,用户想要迅速找到自己关心的内容 将会非常麻烦。 我们应用 Web 日志挖掘可以得到一个网站所有用户的访问事务数据库,举一个简单的 例子,假定用户当前访问 A 结点,那么我们就可以设计程序从事务数据库中找到含有 A 结 点的所有事务(含有 A 结点的访问链),假设找到了 100 条这样事务,其中下一个结点为 B 的有 50 条,为 C 的有 20 条,为 D 的有 10 条… …显然当前用户接下来访问 B 网页的概率很 高,那么相应地把目标为 B 的链接高亮显示将有助于用户使用网站。 上述例子只是一个简单的策略,站点管理员可以根据实际情况设定一个概率阀值来控 制高亮链接的数量,还可以根据不同结点的访问概率用不同的颜色或其他方法进行不同程 度的推荐等等。 5.1.2 动态地图 动态地图也是一种智能推荐策略,与高亮策略不同的是,动态地图中推荐的链接通常 不能由当前结点直接访问到,即物理拓扑上两点之间无连接。动态地图是根据每个用户自动 地实时生成的,它一般来说会占用相对大的服务器资源,而且还可能打破原有网站的拓扑 结构。动态地图上推荐的链接通常有以下几种: 1) 从当前结点开始,后 N 步可能访问的链接。结合高亮策略的推荐算法,很容易推算 出用户后 N 步可能访问的结点的概率。 2) 当前结点上无法直接连接的地标性骨干结点。这需要管理员设定地标系数阀值。 3) 事务末结点。为了说明这个情况,我们暂时假定网站的结点可以分为两类:起联通 作用的结点和提供内容的结点。很多情况下我们访问网站的目的是了解信息,也就 是要访问自己关心的内容结点。实际情况中大多数用户从访问一个网站开始总是经 过一系列联通结点一直到内容结点为止。也就是说处于访问事务链中的最后一个结 点很可能是用户最终希望看到的内容。只要将高亮策略算法中的下一个结点换成事 务链最后一个结点就很容易生成事务末结点的推荐算法。 4) 访问事务链上符合一定地标系数的结点。在这种情况下,结点不再简单的分为联通 结点和内容结点。我们可以用拓扑分析算出访问事务链上每个结点精确的地标系数,

可由管理员设定符合一定系数范围的结点才有可能成为推荐的候选结点。例如管理 员可以设定一个比较小的地标系数阀值,规定访问事务链上只有小于该值的结点 才可作为候选结点进入下一步计算。从而使最终推荐的结点内容度较高(含有较多 的内容信息)。

5.2 缓冲预取 缓冲预取将的到的可能访问结点预先放到缓存中。例如可以缓存用户下一个最有可能访 问的结点,从而当用户进行下一个访问动作时不是从 Web 服务器中请求网页,而是直接从 缓存中取出,明显减少响应时间。 缓冲可分为单缓冲和多缓冲。单缓冲是指只缓存一个网页,或者是下一个可能访问的网 页或者是符合一定地标系数的内容网页。多缓冲是指同时缓存多个网页,多缓冲会明显提高 访问命中率,但是需要更多的资源开销。 这一章提到的多种实现策略各有优缺点,彼此之间也可能存在冲突。一般网站管理员通 常需要考虑资源和管理成本,建议根据实际情况,选取一到两个策略加以实现。

第六 章 总 结和展 望 6.1 自适应网站研究的新方法 近几年以 XML 为基础的新一代 Web 环境正在得到长足的发展。XML 不仅可以直接面对 Web 数据,很好地兼容原有的 Web 应用,而且可以更好地实现 Web 中的信息共享的交换。XML 可 以看作是一种半结构化的数据模型,可以很容易地将 XML 文档的描述与关系型数据库中的 字段对应起来,实施精确的查询与模型抽取。 •

XML 通过使 用一个可 扩展标记 集提供文 档内容的 更准确描 述。 可以定义您自己的标记集来描述文档内容。描述的精度由您来决定。例如,您可以使 用 标记,而其他人可能发现使用 标记更有用。此功能比 HTML 更优越的地方在于,您有固定的标记集可供选择。



XMl 支持高 级搜索。 查找 XML 文档内的内容更容易,因为文档内容的结构和含义是在它的语法中定义 的。 XML 文档的一个要求是它们必须具有严谨的格式。严谨的格式的一个特点是每 个起始标记都必须具有结束标记。另一个要求是标记必须以特定的次序嵌套。这些要 求是为了便于对文件进行语法分析和操作。 语法定义了 XML 文档的结构和内容,并可用于执行更有效的搜索。例如,用户代理 程序可以支持搜索使用特定语法编写的文档的集合。另一个示例就是搜索由 Ralph Higglebrewer 编写的书籍。根据标记名、标记属性、数据内容和文档中的位置进行搜 索是 XML 文档简化搜索的其他策略。



XMl 将文档 结构与显 示内容分 开。

将文档内容和文档结构分开在必须动态生成 Web 文档的内容时尤为重要。这种分离 允许 Web 小组成员(Web 页面编程人员、商业逻辑程序员和图形设计者)同时工作, 并只是有限地影响其他人的工作。 可以包含直接插入的 XSL 样式表,意味着它在 XML 文档内进行格式化。也可以将 它作为单独的文件来创建,并从 XML 文档内或者它格式化的文档内与它进行链接。 将 XSL 显示与 XML 内容隔开通常会减少基于 XML 的应用程序内的维护。此方法还 允许您为 XML 文档创建多个视图或显示格式。 除了格式化之外,还可以使用 XSL 来过滤为不同用户组提供的数据。例如,可以将 一个包括价格、描述和订单号码的汽车零件目录作为视图显示给购物者看。显示给汽 车修理工人看的目录视图可能包括购物者可用的信息以及用于显示安装零件位置的 图解。而显示给制造商看的视图可能包括有关子部件和材料的信息。 •

XML 改进用 户响应、 网络负载 和服务器 负载。 可以让 Web 服务器一次将 XML 文档及其相关联的 XSL 样式表发送给客户机。每个 样式表可以提供部分或所有文档数据的不同视图。选择要应用的样式表。从一个视图 (样式表)更改为下一个视图不会导致向服务器发送另一个请求。

正式由于 XML 的诸多有点,使它能够在数据挖掘和自适应网站研究方面带来新的契机。 XML 有着以下几个明显的广泛应用:多个异质数据库之间通讯、将 Web 服务器负载转到客户 端、同样的数据提供给不同用户不同的视图、智能代理按需剪裁信息内容。显然这些应用与 Web 数据挖掘有密切的联系,XML 的出现必将使 Web 数据挖掘更加高效、准确。

6.2 需要进一步研究的内容 本文对于自适应网站的实现流程和建议方法进行了研究,但仍然有许多工作亟待进一步加 深和加强。主要有以下几个方面: 1)

2)

3)

分布式 Web 挖掘的研究。目前许多的 Web 服务器使用的负载均衡技术,Web 服务器的日 志分布在不同的地理位置。进一步的研究将涉及整合多个分布日志的数据,处理不同服 务器间的日志格式等内容。 跨站点的研究。近几年 XML、Web Service 等技术的产生和发展,使每个 Web 站点不再是 一个个的信息孤岛,跨站点的信息交换与流通必将日益频繁,如果能够结合站点所处 的 WWW 环境去研究自适应站点必将得到更加广泛的数据支持。 多数据分析与整合。本文中主要关注的是 Web 服务器日志,但是 Web 世界中与一个站点 相关的数据不仅限于 Web 服务器日志,还可能有客户端的 Cookie,用户的注册信息, 代理服务器日志,Web 内容信息,甚至是相似站点的 Web 服务器日志等。如何将这些数 据进行有效的整合与应用将是自适应网站研究未来要面对的问题。

参考文献

Related Documents

Lw
November 2019 22
Lw Basic
December 2019 13
Lw Sailing
December 2019 15
Tools Lw Flashcards
December 2019 43