（计算机应用技术专业论文）基于web挖掘的自适应站点研究.pdf

摘要 基于w e b 挖掘的自适应站点研究 摘要 随着互连网技术和电子商务的迅猛发展，i n t e m e t 正在前所未有地改变着我们的生 活。越来越多的商品交易和服务通过w e b 来进行，如何更好地适应市场的变化、更好 地为顾客服务成为各个网站关注的热点。为了更好地解决经营者和顾客的关系，自适应 站点成为当前研究的热点。 用户访问站点的日志文件为我们提供了一个观察用户与站点交互的机会。本文就是 通过对w e b 日志文件的分析和挖掘来研究和构建自适应站点。 本文对构建自适应站点的基础理论和算法进行了全面的研究：分析了网站的类型和 用户的浏览习惯；提出了全新的基于含弹出式页面的树形站点的会话识别和路径补充算 法；给出了改进的最大向前频繁路径挖掘算法和目标页关联算法。 为了应用和验证以上算法，实现了基于j 2 e e 的自适应站点系统m a w s s 。该系统 由数据预处理、站点调整、页面推荐和目标页关联四个模块组成，数据预处理是基础， 站点调整是核心。 关键字：自适应站点，w e b 日志挖掘，路径补充算法，m f f p + ，m a w s s a b s t r a c t t h er e s e a r c ho fa d a p tlv ew e bsit e sb a s e do nw e bm inln g a b s t r a c t w i t ht h es w i f ta n dv i o l e n td e v e l o p m e n to fi n t e r n e tt e c h n o l o g ya n de - c o m m e r c e ，w e bi s d r a m a t i c a l l yc h a n g i n go u tl i v e su n p r e c e d e n t e d b e c a u s em o r eb u s i n e s st r a n s a c t i o n sa n d s e r v i e sa r ec a r r i e do u tt h r o u g ht h ew e b ，b e t t e rs e r v i c e sf o r t h en e e do fw e b b a s e da p p l i c a t i o n s a n du n d e r s t a n d i n gt h ea c t i o no fc u s t o m e r sb e c o m et h ef o c u so fa t t e n t i o nt o d a y i no r d e rt o s o l v et h ep r o b l e m so fr e l a t i o n s h i pb e t w e e nc u s t o m e r sa n dp r o v i d e r s ，a d a p t i v ew e bs i t e s b e c o m et ot h ef o c u so fs t u d ya tp r e s e n t l o g so fu s e ra c c e s s e st oas i t ep r o v i d ea no p p o r t u n i t yt oo b s e r v eu s e r si n t e r a c t i n gw i t h t h a ts i t e t h r o u g hw e bu s a g em i n i n gt h i sp a p e ra i m st or e s e a r c ha n db u i l dt h ea d a p t i v ew e b s i t e s t h i sa r t i c l ea i m st op r o v i d ea c o m p r e h e n s i v er e s e a r c ho nt h ep r i n c i p l e sa n da l g o r i t h mo f b u i l d i n ga d a p t i v es i t e s t h r o u g ha n a l y z i n gt h et y p e so fw e b s i t e sa n du s e r s b r o w s i n gh a b i t s ，i t p r o p o s e saf u l l yn e ws e s s i o ni d e n t i f i c a t i o na l g o r i t h ma n dt r a i lp a t hc o m p l e m e n t a r ya l g o r i t h m f o rt r e es i t e sc o n t a i n i n gp o p _ u pp a g e s ，a n da l s op r o v i d e st h ei m p r o v e dm a x i m u mf o r w a r d f r e q u e n tt r a i lp a t ha l g o r i t h ma n do b j e c tp a g ea s s o c i a t i o na l g o r i t h m t op r a c t i c ea n dv e r i f yt h ep r o p o s e da l g o r i t h ma n dr e a l i z et h ej 2 e eb a s e da d a p t i v es i t e m a w s s ，w h i c hc o n s i s t so ff o u rm o d u l e s ：d a t ap r e t r e a t m e n t ，s i t ea d a p t a t i o n ，p a g e r e c o m m e n d a t i o na n do b j e c tp a g ea s s o c i a t i o n a m o n gt h ef o u rm o d u l e s ，t h ed a t ap r e t r e a t m e n t a n dt h es i t ea d a p t a t i o np l a yab a s i ca n dc e n t r a lr o l er e s p e c t i v e l y k e yw o r d s ：a d a p t i v ew e bs i t e s ，w e bu s a g em i n i n g ，p a t hc o m p l e m e n t a r ya l g o r i t h m ，m f f p + ， m ，a w s s l l 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华 东交通大学或其他教育机构的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢 意。 本人签名左垒至竺日期三! ：! ：竺：! f 关于论文使用授权的说明 本人完全了解华东交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅。学校可以公布论 文的全部或部分内容，可以采, n 影e r j 、缩印或其他复制手段保存论文。 保密的论文在解密后遵守此规定，本论文保密期一年。 日期 第一章绪论 第一章绪论 1 1引言 随着互联网技术在深度和广度的飞速发展，w e b 站点设计、w e b 服务设计、以及电 子商务等工作变得越来越复杂、繁重。从站点的经营方来说，他们需要好的自动辅助设 计工具，可以根据用户的访问兴趣、访问频率、访问时间动态地调整页面的结构、改进 服务，开展有针对性的电子商务以便更好地满足访问者的需求。从访问者的角度来说， 他们希望看到的是个性化的页面，希望得到更好地满足各自需求的服务。 而现实中大部分w e b 站点的组织设计都是基于假定的大多数用户的访问模式。错误 的假定可能使网站结构不合理，给访问者的访问带来不便。如果能够利用相关技术获得 大多数访问者的实际访问模式，网站系统就可以根据访问者动态更改网站的组织结构和 外观表现形式。 为了获得访问者实际的访问模式，就需要从大量访问者的访问记录中找出规律。9 0 年代初发展起来的数据挖掘技术为这种需求提供了可能。数据挖掘( 或数据库中的知识 发现) 是识别数据中正确的、新颖的、潜在有用的且最终可被理解的非平凡过程。最早 的数据挖掘的方法都是应用于关系数据库，随着i n t e m e t 的发展，数据挖掘的方法不仅 应用于传统的关系数据库，而且也应用于互连网上的各种有价值的信息。数据挖掘技术 在i n t e m e t 上的一个很重要的应用领域就是w e bu s a g em i n i n g 。w e bu s a g em i n i n g 就是一 个或多个i n t e m e ts e r v e r 中自动发现访问者的访问模式的二种i n t e r n e t 上的数据挖掘方 法。自适应网站系统( a d a p t i v ew 曲s i t e ss y s t e m ，简称a w s s ) 就是采用这种方法。 自适应网站的研究与发展已经有一段时间，自适应网站概念的提出主要是为方便网 站的访问者，为他们提供个性化服务，从而吸引他们不断访问网站。不同的网站和研究 人员采取的自适应方法不同。从用户的角度划分，自适应方法主要分为以下两方面： 1 ) 基于内容的方法：在基于内容的方法中，主要是通过分析用户过去对网站的访问情 况，获取用户感兴趣的内容，向用户推荐有关该方面内容的资源。 2 ) 基于协同过滤的方法：在协同过滤的方法中，主要是根据用户的过去访问记录，向 用户推荐与之有相同兴趣爱好的用户所喜欢的页面。 本论文所研究的自适应网站系统构建主要是采用第一种方法来实现自适应特性。系 统通过综合分析用户访问日志来获得用户的访问模式，根据这些信息重组该用户的网 页，达到自适应的目的。 1 2 研究问题的现状及存在的问题 人们发展了许多个性化信息推荐服务系统以及相关技术，以提高站点的组织结构及 第一章绪论 外观表现形式。目前已出现了一些相关的系统，主要有： 1 ) s e t a t l 】是一个s h e l l ，通过它可以辅助创建自适应网上商店，动态创建基于当前用 户访问模式的商品页面。最初的用户模型是根据网站设计者的经验，即以假定用户经常 使用的访问模式来创建模型，以后该模型就会根据用户的访问行为和用户选择的产品动 态更新。 2 ) w e b w a t c h e r 系统：采用跟踪用户浏览w e b 站点的行为或者访问路径方法学习用户 的访问模式，将用户可能感兴趣的w e b 页在线推荐给用户。 3 ) s i t e h e l p e r 系统：采用分析每一个用户已经访问的w e b 页，学习用户的兴趣模式， 从用户感兴趣的w e b 中提取关键词，然后提供给用户，系统基于用户相关反馈技术为用 户推荐其它的相关w e b 页。 4 ) a v a n t i 1 0 】系统：利用自适应规则为每一组相同的用户访问模式实现定制化。 5 ) a h s 系统：利用用户的访问模型，改变页面的内容和表现形式。该系统的自适应 性主要表现在两个方面：链接自适应( l i n ka d a p t a t i o n ) 、内容自适应( c o n t e n ta d a p t a t i o n ) 。 其中链接自适应是系统通过操纵链接结构和链接表现形式引导用户访问：用户感兴趣的 信息、用户关心却与当前的访问没有关系的信息、与用户的兴趣度有关用户却不知道的 信息：链接自适应是系统通过提供额外的或替代的信息提供给用户，以保证用户访问的信 息是用户关心的并且是可以理解的。 基于w e b 数据挖掘的自适应网站系统构建技术是当前的一个研究热点。主要的研究 有： 1 ) s c h e c h t e r 等人根据用户的访问路径模式预测用户未来可能的唧请求，让代理 服务器执行预取操作，将相关w e b 页放入其c a c h e 中，以加快访问速度。 2 ) c o o l e y d e 等人和b u c h n e r 等人利用数据挖掘技术从w e b 访问的l o g 文件中提取用 户的访问模式，用于市场决策和智能推荐服务。 3 ) n a s r a o u i 等人采用聚类用户访问模式方法，预测用户未来的访问行为。 4 ) e r i cs c h w a r z k o p f 采用b a y e s 网络的方法构建了u m 2 0 0 1 系统，预测用户的访问 行为，并据此更改用户的p r o f i l e s ，从而动态更改用户的访问页面依此达到自适应的目 的。 5 ) p e r k o w i t ze ta 1 等人提出了自适应网站的概念，并讨论了创建自适应网站各方面的 问题。 目前己经存在许多自适应网站系统和相关研究，但是仍然存在一些问题，主要包括： 1 ) 大多数自适应网站系统或个性化系统针对的是注册用户，较少考虑非注册用户访 问网站的自适应情况。 2 ) 大多数自适应网站系统或个性化系统对新用户和访问站点较少的用户的访问模 型考虑不够，因为新用户和浏览站点较少的用户被系统收集的用户信息较少，采用某些 聚类算法并不合适。 2 第一章绪论 3 ) 大多数自适应网站系统或个性化系统没有考虑用户是否有新颖信息需求的偏好。 4 ) 大多数自适应网站系统都是基于特殊的领域进行的，没有考虑大部分的领域。 5 ) 大多数自适应网站系统对于建立用户的访问模型没有采用在线学习的方式，用户 访问模型的更新不是动态进行的。 通过对当前自适应网站系统的构建及相关技术的分析，我们发现在构建自适应网站 系统中必须要着重解决以下几个方面的问题： 1 1 站点结构的分析和用户访问习惯的分析 网站作为一种数据结构，有很多类型，对网站的结构进行正确的分析和归类是自适 应的前提；对用户的访问习惯和访问模式的分析是构建自适应站点的基础。 2 ) w e b 访问日志的数据预处理 进行w e b 访问日志挖掘时，对l o g 文件进行有效地预处理很重要。w e b 日志挖掘 预处理包括：数据清洗、用户与会话识别和路径补充等。w e b 日志挖掘的分析对象是服 务器的访问l o g 文件记录、站点文件和其它统计信息。由于l o g 文件包含很多“噪声 ， 必须过滤掉这些“噪声”或冗余数据，然后进行预处理的各个步骤。 3 ) 用户模式的生成、学习及进一步处理 在构建自适应网站系统中，用户模式的生成、学习及进一步的处理很重要，它是构 建自适应网站的依据和基础。 钔站点结构调整算法的设计 要达到自适应的目的，必须有相应的站点调整算法，用来变化站点，以适应用户的 需要和喜好，相关算法的选择和设计是关键。 1 3 论文研究的内容和意义 本论文研究内容是基于w e b 数据挖掘的自适应网站系统，文中讨论了自适应网站系 统构建过程中的各个步骤和关键算法，针对树形含弹出式页面的站点提出了改进的会话 识别算法、路径补充算法、站点调整算法、最大向前频繁路径算法和目标页关联挖掘算 法，最后应用j 2 e e 技术实现了一个自适应站点系统m a w s s ( m ya d a p t i v ew 曲s i t e s s y s t e m ) 用来验证提出的算法。 本论文的研究内容主要分为以下两个部分：， ， 1 ) 基础理论及算法研究 基础理论及算法研究主要包括：用户访问习惯和模式的分析，网站结构的分类，会 话识别算法，路径补充算法，站点调整算法，最大向前频繁路径挖掘算法，目标页关联 挖掘算法。 2 ) 自适应站点系统m a w s s 的设计及实现 采用w e b l o g i c + j b u i l d e r 的j 2 e e 开发环境实现了一个基于树形( 含弹出式页面) 结构的自适应站点系统，以此来验证提出的算法。 3 第一章绪论 随着i n t e m e t 复杂性的提高，自适应站点的研究显得越来越重要。不同层次、使用 目的和爱好的浏览者需要个性化信息服务，网站经营管理者需要构建智能化网站，开展 个性化的电子商务活动，提高网站的声誉和效益。自适应站点的研究可以使企业获得大 量的客户行为信息，使电子商务网站达到更高的客户满意度，大大提高企业网络经营的 效率，提高市场竞争力。 自适应站点的基础是具有强大数据分析处理功能的w e b 挖掘。而在当前的信息分 析技术中w e b 挖掘是最具有应用前景的技术之一，所以自适应站点研究不仅具有广阔 的商业前景，而且将给计算机科学诸多领域的发展带来深远的影响。随着知识经济的发 展，自适应站点最终将成为一种向用户提供自适应服务的有效手段，必将在人们的经济 生活中有着更广泛的应用，扮演着更重要的角色，因此对w e b 挖掘和自适应站点的研 究具有重要意义。 1 4 论文组织结构安排 全文共分为五章，具体章节安排如下： 第一章：绪论，介绍本论文的由来以及研究的目的和意义。 第二章：数据挖掘和w e b 挖掘，介绍了数据挖掘和w e b 挖掘的基本概念。 第三章：构建自适应站点的理论基础和算法研究，讨论了构建自适应站点的各个步 骤及其相关算法。 第四章：自适应站点系统m a w s s 的设计与实现，给出了m a w s s 系统的开发环 境，站点结构以及实现流程。 第五章：总结。 4 第二章数据挖掘和w e b 挖掘 第二章数据挖掘和w e b 挖掘 2 1 数据挖掘概述 2 1 1 数据挖掘与知识发现 数据挖掘( d m ，d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程。可以简单的说，数据挖掘就是从大量的数据中提取或者“挖掘”知识的过 程。 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用 户感兴趣的知识；发现的知识应该可接受、可理解、可运用；并不要求发现放之四海皆 准的知识，也不是要去发现新的自然科学定理和纯数学公式，更不是什么机器定理证明。 数据挖掘所得到的知识应具有先前未知这个特征，先前未知的知识是指预先未曾预料到 的，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值。在 商业应用中最典型的例子就是w a l m a r t 公司通过数据挖掘发现了小孩尿布和啤酒之间有 着惊人的联系( 后面称之为关联规则) 。 对于数据挖掘( d m ) 和知识发现【2 ( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的确切定 义，特别是两者之间的关系，一直在许多学者中有混淆。有学者认为数据挖掘和知识发 现是等价的概念，人工智能( 越) 领域习惯称知识发现，而数据库领域习惯称数据挖掘， 有的甚至将两个概念视为同义词。也有学者把知识发现看作发现知识的完整过程，而数 据挖掘只是这个过程中的一个部分。 2 1 2 数据挖掘的形式化定义 数据挖掘的形式化定义如下： 数据挖掘( d m ) 是一个七元组( d ，f ，m ，t ，a ，r ，s ) 。d 是数据的集合，可以看 成是数据( 仓) 库中( 也可以是其它的数据源) 全体的数据。f 是面向主题预操作的集合 南， 最，嫡一1 ) 。f 的元素由问题的定义所决定，f i 是面向主题i 的预处理序列。m = m 0 ，m 1 ， m l r 1 ) ，其中m n = = f n ( d ) e d ，f e f 表示面向主题n 的挖掘数据，m 。可能不是d 的子 集，n = o ，l ，2 ，i f i 1 。a 是算法集合即从数据库中抽取信息时所用到的全体算法。 t 是数据表示转换操作的集合。t ( m ) 是算法a 的输入，a a ，t t ，m m n 。对任意a c a ，a ： t ( m ) l m m 。，存在t q r 是从算法到挖掘结果的映射，n = o ，1 ，i f i - 1 。 其中r 是全体算法的输出集合。s 是对算法的输出集r o 进行的选择操作，凡是r 的子 集。 s ( r o ) l r o er o 是挖掘的结果集，可以看作是发现“知识。 5 第二章数据挖掘和w e b 挖掘 几f 仁呻几f p q 卜n s l ，一j l jl - - - - - j 图2 - 1 数据挖掘形式化过程 f i 9 2 1 f o r m a l i z a t i o np r o c e s so fd a t am i n i n g 2 1 3 数据挖掘的分类 数据挖掘的应用环境千变万化，数据挖掘的任务也是多种多样的。从数据分析的角 度来看，数据挖掘任务可以分两类：描述和预测。 描述性挖掘任务以简洁概要的方式描述数据，并提供数据的有趣的一般性质。描述 性挖掘的任务是提取当前数据的特征。描述性挖掘分为概念描述、类比较、关联规则等。 预测性挖掘任务分析数据，建立一个或一组模型，并试图预测新数据集的行为。预 测性挖掘任务一般分为两步，一是根据积累数据建立模型，二是根据这个模型对新数据 进行预测。例如客户流失分析，它是先根据已有数据建立客户流失模型，根据这个模型 来预测当前客户流失的可能性。 另外，还可以根据其它的标准对数据挖掘进行分类。根据所挖掘的知识类型分类， 可以将数据挖掘分为关联挖掘、分类挖掘、聚类挖掘等。 2 1 。4 数据挖掘过程模型 1 定义问题 任何软件项目在实施之前都必须要进行需求分析，即确定希望达到的目的。同样， 在开始进行数据挖掘之前也需要确定希望解决的问题。这个阶段叫做定义问题。 虽然挖掘最后的结果是不确定的，但是要探索的问题应该是有预见性的。这一个阶 段需要更多的用户领域知识。这个阶段的执行者是分析员，他必须要广泛深入的了解应 用背景和用户领域知识。这样才能准确的把握用户的最终目标。这个目标的定义必须清 晰明确。比如想提高电子邮箱的利用率时，想做的可能是“提高用户使用率”，也可能 是“提高一次用户使用的价值 。确定目标以后，领域专家对这个目标进行评价，以确 认其有效性。 另外，有效的问题定义还应该包含一个对结果进行衡量的标准，即所要达到目标的 量化指标。 2 准备数据 确定了挖掘目标以后，就要开始为挖掘准备数据了。准备数据就是根据挖掘需求， 收集数据，并建立好可挖掘的数据库。准备数据所占的时间比例在整个数据挖掘过程中 是最大的。 这一阶段主要分为两步：第一步根据挖掘目标建立合理的数据库模式。第二步是对数 据进行预处理，以得到完整的、不含噪声的、一致的数据，将这些数据装载到建立好的 数据库模式中去。 6 第二章数据挖掘和w e b 挖掘 ( 1 ) 建立可挖掘的数据库 在挖掘之前，我们需要建立一个可挖掘的数据库，操作型的数据库和其它原始的数 据来源是不可用的。该数据库模式是根据实际的挖掘目标和挖掘算法来确定的。设计人 员通过对挖掘目的和背景知识的深入了解，根据挖掘任务的具体算法，来建立可挖掘的 数据库模式。该数据库的组织形式既可以是数据仓库，也可以是关系数据库。其中的数 据必须是完整的、不含噪声的和一致的，为了得到这样的数据，我们必须对数据进行预 处理。 ( 2 ) 数据预处理与数据载入 现实世界中的大型数据库存在不完整的、含噪声的和不一致的数据是非常普遍的事 情。出现这种情况的原因是多种多样的，同样也是不可避免的。这样的数据不能够直接 载入可挖掘数据库，为挖掘引擎所用。数据预处理就是要把这些不完整的、含噪声的和 不一致的数据转化为完整的、不含噪声的、一致的数据。 数据预处理技术包括数据清理、数据集成与变换、数据归约。 ( 1 ) 数据清理 数据清理技术用来填充遗漏的值，识别孤立点、消除噪声，并纠正数据中的不一致 这里分别介绍对于遗漏值、有噪声和数据不一致的情况的处理技术。 遗漏值。遗漏值是指我们关心的属性值空缺。解决这个问题的方法分为两类：忽略该 元组和填写空缺值。填写空缺值的关键是这个填入的值如何确定。 有噪声。噪声是测量变量的随机错误或偏差。我们需要去掉噪声，平滑数据。通常 的解决办法有分箱、聚类、计算机和人工检查结合的方法、回归。 不一致数据。对于有些事务，所记录的数据可能存在不一致。有些数据不一致可以 使用其它材料人工地加以更正，也可以使用知识工程工具来检测违反限制的数据。 ( 2 ) 数据集成与变换 数据挖掘经常需要数据集成。因为将多个数据源中的数据集成起来，能够减少或避 免结果数据集中数据的冗余和不一致性。这有助于提高其后挖掘的精度和速度。数据还 可能需要转换成适于挖掘的形式。 数据集成。数据的来源可能包括多个数据库、数据方或者普通文件。数据集成将多 个数据源中的数据结合成、存放在一个一致的数据存储。其中可能会遇到模式集中的错 误、数据冗余和重复、数据值冲突的问题。使用元数据可以帮助避免模式集中的错误， 而使用相关性分析技术可以检测到冗余。 数据变换。数据变换将数据转换成适合于挖掘的形式。数据变换的内容涉及平滑、 聚集、数据泛化、规范化、属性构造等技术。 ( 3 ) 数据归约 在海量数据上进行复杂的数据分析和挖掘将需要很长时间，这种分析是不现实或不 可行的。使用数据归约技术可以得到数据集的归约表示，它小得多，但仍接近地保持原 7 第二章数据挖掘和w e b 挖掘 数据的完整性。这样，在归约后的数据集上挖掘将更有效，并产生相同或者几乎相同的 分析结果。 3 实施挖掘 有了可挖掘的数据库以后，就可以开始实施挖掘了。实施挖掘阶段主要有两步：第一 步，根据数据挖掘的任务和拥有的数据情况，确定数据挖掘算法及参数等。第二步，根 据确定的挖掘算法及参数开始实施挖掘。这一阶段需要在人的指导下完成。确定数据挖 掘的算法及参数的过程是设计人员根据数据挖掘的任务来进行的。由于能够完成某任 务的方法可能有多种，设计人员需要对各种方法进行综合评价，挑选出能够完成挖掘目 标的最优算法。某些技术对数据的形式有具体的要求，因此，确定算法以后常常需要重 新修改数据，退回到数据准备阶段，甚至改变最初对问题的定义。确定算法之后，就开 始实施挖掘了，这一过程由挖掘引擎完成。 4 表示与评价 实施挖掘并得到结果以后，必须要将这些结果输出并表示出来，这样才能为用户所 用。数据挖掘系统应当能够以多种形式显示所发现的模式，如规则、表、交叉表、饼图 或条图、树、数据方或其它可视化表示，允许发现的模式以多种形式表示可以帮助不同 背景的用户识别有趣的模式，并与系统交互或指导进一步的发现。 数据挖掘建立模型或者导出规则集之后，必须对它们进行评价。其主要工作是筛选 和评价挖掘结果中有用的部分，查找可接受的结果。可以通过定义兴趣度指标，考虑结 果的正确度、新颖度、有用性和简单性，把符合条件的知识从中挑选出来。 2 2w e b 挖掘概述 2 2 1 w e b 挖掘的定义 6 0 年代，大的物理流伴随着大信息流。传统的文件方式不能适应信息处理的需求， 因此出现了数据库技术。9 0 年代，人类积累的数据量以高于每月1 5 ( 或每年5 1 3 倍) 的速 度增加，数据海洋不能产生决策意志，为了进行决策，人们不断地扩大数据库能力，搜 集海量数据，但这使得决策者更难于决策，因此出现了数据挖掘技术，以便从数据库中 发现知识。数据挖掘技术包括特征、分类、关联、聚类、偏差、时间序列、趋势分析等。 近年来，i n t e m e t 正以令人难以置信的速度在飞速发展，越来越多的机构、团体和个 人在i n t e m e t 上发布信息、查找信息。虽然i n t e m e t 上有海量的数据，但由于w e b 是无结构 的、动态的，并且w e b 页面的复杂程度远远超过了文本文档，人们要想找到自己想要的 数据犹如大海捞针一般。信息检索界开发了许多搜索引擎，但其覆盖率有限，因此查全 率低，一般的搜索引擎是基于关键字的查询，命中率较低，另外不能针对特定的用户给 出特殊的服务，因为每个人感兴趣的东西是不一样的，因此不具有个性化。 解决这些问题的一个途径，就是将传统的数据挖掘技术和w e b 结合起来，进行w e b 8 第二章数据挖掘和w e b 挖掘 挖掘。w e b 挖掘【3 】就是从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用模式和隐藏的 信息。w e b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行挖掘，确定权威页 面，w e b 文档分类，w e bl o g 挖掘、智能查询、建立m e t a w e b 数据仓库等。 2 2 2w e b 挖掘的困难 万维网目前是一个巨大、分布广泛、全球性的信息服务中心，它涉及新闻、广告、 消费信息、金融管理、教育、政府、电子商务和许多其它信息服务。w e b 还包含了丰富 和动态的超链接信息，以及w e b 页面的访问和使用信息，这为数据挖掘提供了丰富的资 源。然而从以下的分析可以看出，对w e b 进行有效的资源和知识发现具有极大的挑战性。 ( 1 ) 对有效的数据仓库和数据挖掘而言，w e b 似乎太庞大了。w e b 的数据量目前以兆 兆字节( t e r a b y t e s ) 计算，而且仍然在迅速地增长。许多机构和社团都在把各自大量的可访 问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制、存储或集成w e b 上的 所有数据。最近，有一些工作在致力于存储或集成w e b 上的所有数据。例如，在 h t t p ：w w w a r c h i v e o r g i n d e x l h t m l 下，可访问到一个巨大的数十兆兆字节的因特网存档。 ( 2 ) w e b 页面的复杂性高于任何传统的文本文档。w e b 页面缺乏同一的结构，它包含 了远比任何一组书籍或其它文本文档多得多的风格和内容。w e b 可以看作一个巨大的数 字图书馆；然而，这一图书馆中的大量文档并不根据任何有关排列次序加以组织。它没 有分类索引，更没有按标题、作者、扉页、目次等的索引。在这样一个图书馆中搜索希 望得到的信息是极具挑战性的。 ( 3 ) w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信息还在 不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断地更新着各自 的页面。链接信息和访问记录也在频繁地更新之中。 ( 4 ) w e b 面对的是一个广泛的形形色色的用户群体。目前因特网上连接有约5 千万台 工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、兴趣和使用目的。 大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极容易在“黑暗 的网络 中迷失方向，也极容易在“跳跃式”访问中烦乱不已和在等待信息中失去耐心。 ( 5 ) w e b _ 1 2 的信息只有很小的一部分是相关的或有用的。据说9 9 的w e b 信息相对 9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关, l 二, w e b 上的很小很小 一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴趣的，而且会淹没所 希望得到的搜索结果。这些挑战已经推动了如何高效且有效地发现和利用因特网上资源 的研究工作。w e b 挖掘是一个更具挑战性的课题，它实现对w e b 存取模式、w e b 结构、 规则和动态的w e b 内容的查找。 2 2 3w e b 挖掘流程 与传统数据和数据仓库相比，w e b 上的信息是非结构化或半结构化的、动态的、并 且是容易造成混淆的，所以很难直接以w e b 网页上的数据进行数据挖掘，而必须经过必 9 第二章数据挖掘和w e b 挖掘 要的数据处理。典型w e b 挖掘的处理流程如下： 1 查找资源：任务是从目标w e b 文档中得到数据，值得注意的是有时信息资源不仅 限于在线w e b 文档，还包括电子邮件、电子文档、新闻组，或者网站的日志数据甚至是 通过w e b 形成的交易数据库中的数据。 2 信息选择和预处理：任务是从取得的w e b 资源中剔除无用信息和将信息进行必要 的整理。例如从w e b 文档中自动去除广告连接、去除多余格式标记、自动识别段落或者 字段并将数据组织成规整的逻辑形式甚至是关系表。 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 ) 相当重要。信息检索( m ) 的目的在于 找到相关w e b 文档，它只是把文档中的数据看成未经排序的词组的集合，而信息抽取( 1 的目的在于从文档中找到需要的数据项目，它对文档的结构和表达的含义感兴趣，它的 一个重要任务就是对数据进行组织整理并适当建立索引。 信息获得( 氓) 和信息抽取( i e ) 技术的研究已经有很长时间，随着w e b 技术的发 展，基于w e b 技术的承、正得到了更多的重视。由于w e b 数据量非常大，而且可能动态 变化，用原来手工方式进行信息收集早己经力不从心，目前的研究方向是用自动化、半 自动化的方法在w e b 上进行m 和m 。在w e b 环境下既要处理非结构化文档，又要处理半 结构化的数据，最近几年在这两方面都有相应的研究成果和具体应用，特别是在大型搜 索引擎中得到了很好的应用。 2 2 4w e b 挖掘的分类 我们可以将w e b 挖掘一般地定义为：从与w w w 相关的资源和行为中抽取感兴趣的、 有用的模式和隐含信息。一般地，w e b 挖掘可分为3 类【4 】：w e b 内容挖掘( w e bc o n t e n t m i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) $ f f l w e b 使用记录的挖掘( w e bu s a g em i n i n g ) 。 图2 2 给出了w e b 挖掘的分类图。 ( 1 ) w e bl 为容挖掘 w e b l 勾容挖掘是从文档内容或其描述中抽取知识的过程。w e b 文档文本内容的挖掘， 基于概念索引的资源发现，以及基于代理的技术都属于这一类。w e b l 为容挖掘有两种策 略：直接挖掘文档的内容，或在其它工具搜索的基础上进行改进。采用第1 种策略的有 针对w e b 的查询语言w e bl o g ，w e bo q l 等，利用启发式规则来寻找个人主页信息的 a h o y ，等等。采用第2 种策略的方法主要是对搜索引擎的查询结果进行进一步的处理， 得到更为精确和有用的信息。属于该类的有w e bs q l ，及对搜索引擎的返回结果进行聚 类的技术等。 ( 2 ) w e b 结构挖掘 1 0 第二章数据挖掘和w e b 挖掘 w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识。由于文档之间的互连， w w w 能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发 现重要的页面。这方面工作的代表有p a g e r a n k 禾l l c l e v e r 。此外，在多层次w e b 数据仓 库( m l d b ) 也利用了页面的链接结构。 ( 3 ) w e b 使用记录的挖掘 w e b 使用记录挖掘的主要目标则是从w e b 的访问记录中抽取感兴趣的模式。w w w 中的每个服务器都保留了访问日志( w e ba c c e s sl c 曲，记录了关于用户访问和交互的信 息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性 化的服务。这方面的研究主要有两个方向：一般的访问模式追踪和个性化的使用记录追 踪。一般的访问模式追踪通过分析使用记录来了解用户的访问模式和倾向，以改进站点 的组织结构。而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不 同用户的访问模式，为每个用户提供定制的站点。 图2 - 2w e b 挖掘的分类 f i 9 2 - 2 c l a s s i f i c a t i o no fw e bm i n i n g 2 3w e b 使用挖掘综述 网站的所有访问者都会留下浏览的踪迹，这些信息自动存贮在w e b 服务器的日志文 件内。w e b 分析工具可以通过分析和处理w e b 服务器的日志文件生成有意义的信息。例 如有多少人访问了该页面，他们从嗖j p ) l 来，哪些页面最受欢迎等。当前经济模式的变化， 从传统的实体的商店到i n t e m e t 上的电子交易同时也改变了销售商和顾客的关系。现在， 网上顾客的流动性很大，他们关注的主要因素是商品的价值，而不象以前注意品牌和地 理因素。因此，电子销售商一个主要的挑战是需要了解到顾客尽可能多的爱好，价值取 向，以保证在电子商务时代的竞争力。数据挖掘是用来发现不明显的，有潜在价值的数 据。w e b 上数据挖掘的潜力在于应用最新的数据挖掘算法，分析i n t e r a c t 服务器上的日 志以及应用系统记录的其它外部数据，从中抽取感兴趣的、有用的模式和隐含信息。 第二章数据挖掘和w e b 挖掘 w e b 使用挖掘【5 1 就是利用数据挖掘技术对网站大量的用户访问数据及其他相关数据 所组成的数据集进行分析挖掘，并从中获得有价值的有关网站访问使用情况的模式知 识。w e b 使用挖掘的过程的总体描述如图2 3 所示。 规则，模式，汇总 ( 蓐兴趣的) 规则样式汇总 图2 3w e b 使用挖掘过程 f i 9 2 - 3 p r o c e s so fw e bu s i n gm i n i n g 2 3 1w e b 使用挖掘的应用 如图2 4 所示，从w e b 中挖掘出的使用模式可以应用到更广阔的领域。以下介绍几 种主要的应用。 图2 - 4w e b 使用挖掘的应用 f i 醇- 4a p p l i c a t i o no fw e bu s i n gm i n i n g 1 ) 个性化服务：根据网站用户的访问情况，为用户提供个性化信息服务，这是许多互 联网应用，尤其是互联网信息服务或电子商务( 网站) 所追求的目标。根据用户本身情况 以及网站的访问情况，为用户提供动态建议是许多( 基于互联网) 市场营销中极为重要的 功能。w e b 使用挖掘就是实现这一目标的最好方法。 例女i ：i ：s i t e h e l p e r 可以通过分析每个用户的网页访问情况，了解用户的爱好，并从用 1 2 第二章数据挖掘和w e b 挖掘 户浏览时间较长的网页中抽取出相应关键字，汇总后提交给用户，获得反馈后，再向用 户推荐网站中其它类似或相关的网页。 又如：w e b w a t c h e r “跟踪用户浏览网页过程，识别用户可能感兴趣的链接， w e b w a t c h e r 根据用户本人和其它用户的浏览情况，对每个新网页进行评估，以帮助用 户能够及时的浏览到自己感兴趣的网页。 2 ) 完善系统性能；系统服务的性能和质量对于用户是否满意网站的信息服务等至关 重要。w e b 使用挖掘为准确了解w e b 的访问情况提供了宝贵的决策支持。由此所获得的 挖掘结果将有助于设计出合理的w e b 缓存、网络通信、负载平衡、或数据分布等方案。 此外，安全问题也是w e b 信息服务( 尤其是电子商务) 顺利健康发展的重要保证，w e b 使 用挖掘还可以帮助进行入侵检测等网络安全工作。 3 ) 完善网站设计：网站的吸引力取决于其内容和组织结构的合理设计。w e b 使用挖掘 可以提供用户访问行为的详细反馈情况，从而能够为网站设计者改进网站的设计提供决 策依据。w e b 使用挖掘可以帮助网站进行有效测试，而无需有经验的人员参见。此外， 也可以利用w e b 使用挖掘的结果来探讨网站内容安排的自动改进问题。 4 ) 商业智能：有关用户访问网站的行为模式，对于电子商务中的市场人员来讲是非常 重要的，通过定义w e b 使用日志的超维立方体，将w e b 使用数据与电子商务应用数据 有机地结合在一起。这样就可以利用数据挖掘的方法与技术来为客户关系管理中的四个 重要阶段( 吸引顾客、保留顾客、交叉销售和顾客离开) 提供决策支持。例如：w e b l o g m i n e r 就可以将w e b 日志转换为超维数据立方体形式以便能够进行o l a p 分析处理和数据挖掘 工作。目前w e b l o g m i n e r 还可用于发现关联规则，完成分类和时序数据分析( 包括事件 序列分析、转换分析和趋势分析) 。 5 ) w e b 使用特征描述【6 】：目前正在进行的一项研究就是修改客户端浏览器，使其能够 记录用户的浏览操作，由此就可收集到有关用户与浏览界面的交互信息，以及浏览一个 特定网站时所采用的浏览策略等相关的详细信息，从而构造出一个网站的用户访问模 型，以帮助预测用户对一个给定网站中各网页的访问概率。该模型可以给一个网站中所 有网页( 根据网页的有关属性内容) 赋予相应的权值。模型中所使用的公式和参数均可以 通过对用户浏览交互的情况和模式统计获得。 2 3 2w e b 使用挖掘模型及其处理过程 在参照通用数据挖掘过程模型的基础之上，针对w w w 特性和电子商务的特殊需 求，a l e xqb u c h n e r 提出了w e b 挖掘的过程模型。包括9 个阶段。 1 ) 人力资源分配 虚拟实体中的问题提出以后，人力资源分配是知识挖掘的第一阶段，它需要网站专 家，数据挖掘专家，市场专家三类人员。三类人员的尽早接触对项目的成功非常重要。 在w e b 挖掘中