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

摘要随着网络技术的迅速发展，以及网络在社会生活中的广泛使用，使得网络上的信息资源越来越多，人类交互信息已不可避免地海量化，而巨量、无组织的信息给用户寻找感兴趣的信息增加了困难。面对巨大的网络信息，如何发现用户所需信息? 为了解决这个难题，w e b 挖掘技术应运而生。w e b 使用挖掘是w e b 数据挖掘研究领域中一个重要方面，它是通过挖掘w e b 服务器日志记录以发现用户访问w e b 页面的模式，挖掘有用模式和预测用户浏览行为的技术。本文对w e b 使用挖掘进行了系统、全面地归纳与分析。并在分析和总结国内外相关资料的基础上，深入研究了w e b 使用挖掘的二个阶段：( 1 ) 通过对w e b 使用挖掘的数据预处理过程的研究，提出了结合网页内容与网站结构进行预处理的方法。具体实现过程是利用i p + a g e n 什参考页面+ 网站拓朴结构识别用户，然后利用用户访问的网页内容进行事务处理。利用这种方法对数据预处理后，结果具有较高的精确性。( 2 ) 采用蚁群混合聚类算法进行用户聚类分析。即利用蚁群聚类算法进行初始聚类获得初始聚类中心，然后用k 均值聚类算法改进聚类的结果。在利用蚁群混合聚类算法实现用户聚类算法中，考虑到用户访问行为以及内容对用户兴趣的影响，改进了蚁群混合聚类算法的相似性计算公式。改进后的算法充分结合了两种聚类算法的优点，解决了传统聚类算法所面临的一些问题，能产生比较理想的聚类结果，从而提高了聚类质量。关键词w e b 使用挖掘，预处理，用户聚类，蚁群混合聚类算法a bs t r a c tw i t ht h er a p i dd e v e l o p m e n to fi n t e m e ta n di t sw i d eu s ei ns o c i a ll i f e ，t h e r ea r em o r ea n dm o r ei n f o r m a t i o nr e s o u r c e so ni n t e r n e t s ot h ei n f o r m a t i o nf o rp e o p l et oc o m m u n i c a t ei si n e v i t a b l yl a r g e r , b u tt h eh u g ea n du n o r g a n i z e di n f o r m a t i o nm a k e sp e o p l eh a r dt of i n dt h eo n et h e ya r ei n t e r e s t e di n t os o l v et h i sp r o b l e m ，w e bm i n i n gt e c h n i q u ee m e r g e s t h i st e c h n o l o g yi sa ni m p o r t a n tp a r ti nt h er e s e a r c hf i e l do fw e bm i n i n g i tm i n e st h eu s e f u lm o d ea n dp r e d i c t sb e h a v i o r so fu s e r s b r o w s i n gb ym i n i n gt h ew e bs e r v e rl o gt of i n dw e bp a g e su s e r sv i s i t t h i sp a p e rs u m m a r i z e sa n da n a l y z e sw e bu s a g em i n i n gs y s t e m a t i c a l l ya n dc o m p r e h e n s i v e l y , a n db a s e do na n a l y z i n gt h er e l e v a n tr e f e r e n c e sa th o m ea n da b r o a d ，i ta l s od i s c u s s e st h et w os t a g e so ft h et e c h n o l o g ya sf o l l o w s ：( 1 ) t h ef n - s ts t a g ep r o p o s e st oc o m b i n ew e bc o n t e n ta n ds i t es t r u c t u r ep r e t r e a t m e n tm e t h o d sb yp r e p r o c e s s i n go fw e bu s a g em i n i n gd a t a t h i sp r o c e s su s e si p + a g e n t + r e f e r e n c ep a g e + s i t et o p o l o g yt oi d e n t i f yau s e r , a n dt h e nd e a lw i t ht h eb u s i n e s su s i n gw e bc o n t e n tu s e r sv i s i t a f t e rp r e p r o c e s s i n gt h ed a t ai nt h i sw a y , w ef i n dt h er e s u l t sa r ec o m p a r a t i v e l ya c c u r a t e ( 2 ) t h es e c o n ds t a g ei st ou s ea n tm i x e dc l u s t e r i n ga l g o r i t h mf o ru s e r sc l u s t e ra n a l y s i s t h a ti st os a y , w eu s ea n tc l u s t e r i n ga l g o r i t h mt og e ti n i t i a lc l u s t e rc e n t e r , t h e nu s ek - m e a n sc l u s t e r i n ga l g o r i t h mt oi m p r o v ec l u s t e rr e s u l t s i na c h i e v i n gu s e r sc l u s t e r i n ga l g o r i t h m ，t a k i n gu s e r s a c c e s sa n dt h ec o n t e n t i m p a c to nt h ei n t e r e s t so fu s e r s w ei m p r o v et h es i m i l a rf o r m u l ao f a n tm i x e dc l u s t e r i n ga l g o r i t h m t h ei m p r o v e da l g o r i t h mf u l l yc o m b i n e st h ea d v a n t a g e so fb o t hc l u s t e r i n ga l g o r i t h ma n ds o l v e ss o m ep r o b l e m so ft h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h m ，w h i c hc a ng e tm o r ed e s i r a b l ec l u s t e r i n gr e s u l t s ，t h e r e f o r ei m p r o v et h eq u a l i t yo fc l u s t e r i n g k e yw o r d sw e bu s a g em i n i n g ，a n tm i x e dc l u s t e r i n ga l g o r i t h md a t ap r e p r o c e s s i n g ，u s e rc l u s t e r i n g ，原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：童至圭圭日期：鱼生7 一年旦月兰日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅：学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。作者签名：茎生蔓色导师签名亟 【之羔日期：卫垒卫年卫月上细硕士学位论文第一章绪论1 1 研究课题背景第一章绪论随着网络和互联网技术的飞速发展，互联网成为一个巨大的、分布广泛的、全球性的信息服务中心，它涉及到新闻、广告、金融管理、教育、电子政务、电子商务等各方面的信息服务。如今的互联网已经是人们生产、生活中不可缺少的一部分。随着互联网被广泛使用的同时，人们对它的要求也越来越高。许多研究者将互联网的研究集中在如何从海量数据和信息中高效地获取有用知识，如何从海量的信息中及时地获取最新信息，如何提高信息检索与推荐的智能水平，以及如何满足各种用户不同的个性化需求等方面，而解决这些问题的关键在于w e b使用挖掘技术。w e b 使用挖掘是w r e b 数据挖掘的一类，旨在通过对w e b 服务器日志文件进行有效的数据预处理，发掘隐藏在日志数据背后的规律和模式，如关联关系，时序关系，页面类属关系等。通过对w e b 日志文件的挖掘和对用户访问行为、频度、访问内容等方面的分析，找出频繁访问路径和用户聚类，将挖掘结果应用于网站中，能够更好地理解用户，发现用户隐藏的兴趣和群体用户的行为规律，从而改进我们的w e b 站点设计，按照用户的个性化信息进行主动式的推荐服务，提高网站质量。由于w e b 日志数据很多是不完整的、冗余的、错误的数据，造成w e b 使用挖掘预处理数据不够精确，将网页内容和网站结构与预处理过程相结合，对预处理进行改进，已成为当前的热点研究之一。另外w e b 服务器上的用户访问记录数据的速度增长，要想在数量庞大的w e b 中快速提取出需要的信息成为人们面临的一大难题，这给w r e b 使用挖掘带来了新的发展机遇和技术挑战。本文研究了将网页内容和网站结构相结合的数据预处理方法，得到预处理数据；然后结合w e b 用户浏览行为和浏览页面内容，采用蚁群混合聚类算法对结果进行聚类分析，提高用户聚类的质量和效率。1 2 国内外研究现状早在1 9 9 6 年就有学者m s c h e n ，hm a n n i l a ，t y a n 提出了可以将数据挖掘方法用于w e b 研究领域使用。并将w e b 挖掘分为w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘。最近几年，w e b 使用挖掘发展迅速，主要经历了如下阶段：硕十学位论文第一章绪论c h e n 等首先将数据挖掘技术应用于w e b 服务器同志，发现用户的浏览模式。提出最大向前引用( m f r ) 的概念。将用户会话分割成一系列的事务，然后采用与关联规则相似的方法挖掘频繁的浏览路径；i b m 公司的w a t s o n 实验室开发的s p e e d t r a c e r 就是对c h e n 等算法的应用。h a n 等人将w e b 服务器日志保存为数据立方体，然后在其上执行o l a p 的各种操作，用于发现用户的访问模式1 2 】；并给出了关于w r e b 日志挖掘系统w e bl o g m i n e r 。yj x i e 首先提出w e b 使用的挖掘由过去的单用户转移到用户组的分析上，并用聚类的方法分析相似的用户组会话【3 1 。a b r a h a m 基于模糊聚类( f c m ) 构建一个i - m i n e rw e b 使用挖掘系统【4 1 。为了改进聚类的质量，l a b r o c h e 、a b r a h a m 又提出引入了蚁群聚类的方法【5 l 。西安交大沈均毅教授等人提出以w e b 站点的u r l 为行、以u s e r i d 为列，建立u r l u s e r l d 关联矩阵，元素值为用户访问次数，然后对列向量进行相似性分析得到相似客户群体，对行向量进行相似度量获得相关的w e b 页面，对相关页面进行下一步处理，以发现频繁访问路径。提出了w e b 页面和客户群体的模糊聚类算法，在该算法中，首先根据客户站点的浏览情况分别建立w e b 页面和客户的模糊聚类集，在此基础上根据m a x m i i l 模糊相似度量规则构造相应的模糊相似矩阵，然后根据模糊相似矩阵直接进行聚类【6 1 。西安交大的陆丽娜教授等人，采用基于事务的方法，提出了一种基于扩展有向树模型进行用户浏览模式识别的w e b 日志挖掘方法| 7 】。中国科技大学王熙法教授等人提出基于神经网络的w e b 用户行为聚类分析方法。上海交大尤晋元教授等人引入w e b ，提出了基于页面内容和站点结构的页面聚类改进算法【引。1 3 研究的目的与意义w e b 使用挖掘的结果可以客观反映w e b 的组成、内容和访问频度等重要信息，也能帮助理解用户的网上访问行为。利用这些信息，研究人员和网站开发者建立了一系列的应用。( 1 ) w 曲个性化服务个性化服务1 9 l ( 也称推荐系统) 就是尽可能使每个客户在浏览网站时，都有自己就网站的唯一客户的感觉。尽可能地迎合每个客户的浏览兴趣，并且定期调整自己米适应用户浏览兴趣的变化。个性化服务的表现形式有：推荐的超链接列硕士学位论文第一章绪论表，推荐的商品列表，推荐的广告列表，经裁剪的文本或图像列表。它是通过收集和分析用户信息来学习用户的兴趣和行为，对用户可能访问的网页进行预测，从而实现主动推荐的目的。( 2 ) w r e b 系统改善对于网络服务提供商来说，用户满意度将是重要的指标。对于用户来说，服务质量和服务器性能是关键。w e b 使用挖掘向网站建立者提供了各种关于网站架构的信息，也提供了用户在使用网站时的习惯，网络管理员可以在w e b 缓存、网络结构安排、负载平衡和数据分布上进行统筹。( 3 ) 网站修改网站设计者通过w e b 使用信息挖掘得到用户的反馈，根据用户的浏览情况，调整网站的网页链接结构和内容，对网站进行优化，从而更好的为用户服务【l o 】。( 4 ) 商业智能商业智能就是将智能计算技术应用于传统商业领域，将商家中现在的数据转化为知识，从而提高数据分析能力，优化业务过程，提高商家竞争力。1 4 论文研究内容和组织结构本论文首先系统地阐述了w e b 使用数据挖掘的整个过程，对数据预处理阶段的几个步骤进行了详细分析，提出了结合站点内容和网站结构进行数据预处理的方法；然后在模式识别阶段中针对传统算法的缺陷，提出了蚁群混合聚类算法，并对算法权重值计算进行改进后应用于用户聚类算法中；最后一节提出一个性化推荐系统的模型。各章节内容的组织如下：第一章绪论首先阐述了课题背景，对w e b 使用挖掘研究现状进行了详细地分析；然后介绍了课题研究目的与意义。第二章w e b 使用挖掘介绍首先介绍数据使用挖掘技术的特点以及过程；然后对w e b 数据挖掘的数据采集、预处理、模式识别、模式分析四个过程分别进行详细介绍。第三章结合网页内容和网站结构的预处理首先对网页特征词的提取方法进行分析，并对网页进行聚类处理；然后对网站拓朴结构图的创建进行了讨论，在数据预处理阶段数据净化、用户识别、会话构造、路径补全、事务识别5 个阶段分析的基础上，提出了一种结合站点内容、结构进行数据预处理的方法。第四章1 蚁群混合聚类算法首先对常见的聚类算法进行了讨论，然后对蚁群聚类算法进行分析，提出了结合k 均值的蚁群混合聚类算法，并在用户访问模式中应用。硕七学位论文第一章绪论第五章个性化挖掘系统的实现利用第三章、第四章介绍的算法，提出了一个实现个性化挖掘系统模型。第六章结束语论文研究工作的总结和对今后研究工作的展望。4硕士学位论文第二章w e b 使用挖掘介绍第二章w e b 使用挖掘介绍r o b e r tc o o l y 将w e b 使用挖掘定义为数据挖掘技术应用在大型w - e b 资源中，分析w e b 站点的使用，w e b 使用挖掘的主要任务就是研究用户的浏览行为，是对用户在站点上的浏览路径以及相应的浏览时间进行挖掘1 1 1 j 。和其它数据挖掘一样，w e b 使用挖掘过程分为：数据采集、数据预处理、模式识别和模式分析等。本章将详细介绍w e b 使用挖掘各阶段。2 1 数据采集数据采集是w e b 使用挖掘过程中必不可少的部分，它的作用是收集与挖掘有关的数据，常用的数据采集来源于w e b 服务器端、应用服务器端、客户端和代理端【1 2 】。随着w e b 使用挖掘深入研究，为了提高挖掘质量，在挖掘过程中通常会借助于网站结构和页面内容。另外动态网站的快速发展与应用，w e b 数据库【1 3 1 也成为数据采集的对象之一。2 2 数据预处理w e b 使用挖掘并不是简单地把挖掘算法应用于采集的数据之上，必须采用框架来处理挖掘过程，即在使用挖掘之前要执行一系列的数据预处理过程，主要包括数据净化、用户识别、会话识别、路径补充和事务识别等工作，它的目的是为了保证w e b 使用挖掘质量。本节将介绍预处理各阶段及常用方法。2 2 1数据；争化数据净化是指删除w e b 服务器日志中与挖掘算法无关的数据f 1 4 1 ，也就是对日志文件进行数据精简，删除w e b 日志中与数据挖掘不相关的冗余项，删除操作通常包括对无用的记录删减和对无关属性删减。w e b 日志文件记录用户关心的正文u r l 外，还记录了请求页上的图像，声音，视频等文件，后者是无用的记录。w e b 使用挖掘的目的是获得用户的行为模式，并不关心那些用户没有显式请求的文件，所以通过检查u r l 的后缀删除认为不相关的数据。例如：将同志中记录的文件后缀名为g i f 、j p e g 和j p g 删除；后缀名为c g i 的脚本文件也应被删除：另外过滤掉w e b 服务器拒绝页面和非法请求的页面等。具体实现时可以使用一个缺省的后缀名列表帮助删除文件，列表必须根据当硕士学位论文第二章w e b 使用挖掘介绍前分析的站点类型进行修改，因为对一个主要包含图形文档的站点，日志中的g i f 和j p e g 文件可能代表了用户的请求，就不能将图形文件删除。除了对记录进行删减外，还要对属性进行删减。w e b 日志记录包括多项属性，而与数据挖掘相关的只有用户i p 地址、用户i d 、用户请求访问的u r l 页面及访问时间，其他属性可以去掉。2 2 2 用户识别用户识别的主要工作就是从经过数据净化的数据中识别每一个用户。识别用户的方法有多种，其中一种为利用c o o k i e s 和用户注册信息识别，但是这种方法对用户行为进行跟踪侵犯了用户的隐私权，很难得到用户的支持合作。多数用户会从安全方面考虑关闭c o o k i e s ，或者因为不愿泄露隐私而使用假信息进行注册1 1 5 1o另一种是通过分析w e b 服务器日志文件中的i p 地址、a g e n t 等信息来识别用户，常见的几种用户浏览网站情况：不同的用户可以在同一时间通过一个简单的代理访问w e b 服务器。同一个用户可能在不同的机器上访问w e b 服务器。一个用户可能在同一台机器上使用不同的浏览器访问w e b 服务器。不同的用户使用同一台机器浏览某一站点。由于本地缓存、代理服务器和防火墙的存在，为用户动态的分配i p 地址，正确识别出每一个用户变得很复杂。2 2 3会话识别会话( s e s s i o n ) 是指用户在一次访问网站期间，从进入网站到离开网站所进行的系列活动i 1 6 】。会话识别的目的是将用户每次访问的页面划分到不同的会话中，以会话为基本单元将有助于模式的挖掘分析。主要的会话构造方法分为：( 1 ) 基于时间的启发式方法这种方法只考虑用户与网站之间会话的时间因素。基于会话时间的启发式方法：用户一次访问时间不能超过时间阈值 ( 根据p e r k o w i t z 1 7 】统计结果，一般时间阈值o 为2 5 5 m i n ，业界通常取3 0 m i n ) 。在相同用户的前提下，假设一个会话的第一个页面请求的时间戳为t o ，那么这个会话中所有页面请求的时问戳t t o + o ) 的页面请求就是下一个新的会话的第一个访问页面。基于页面访问时问的启发式方法：用户在一个页面停留的时间不会超过时间阈值6 ( 通常6 = 1 0 m i n ) 。在相同用户的情况下，p 和q 是其依次发出相邻的两个页面请求，t p 和t q 分别表示页面请求p 和q 的时问戳( p q ) 。如果t q 气p + 6 ，则页面请求p 和q 属于同一个会话，否则页面请求p 和q 属于两个不同的会话。6硕士学位论文第二章w e b 使用挖掘介绍( 2 ) 基于引用的启发式方法基于引用的启发式方法主要思想是不考虑用户浏览页面的时间和在网站中活动的时间，而是根据网站页面的拓朴结构和用户的浏览活动相结合来进行会话构造的方法。假定同一用户依次发出相邻的两个页面请求p 和q ( 其中p 属于会话s ) ，t p 和t q 分别表示页面请求p 和q 的时间戳( t p t q ) 。如果页面请求q 的引用页面曾经在会话s 中出现过，那么q 就属于会话s ；或者q 的引用页为空并且t 。也 ( 为时间延迟，通常小于l m i n ) ，那么页面请求q 也属于会话s 。2 2 4 路径补全由于本地缓存的存在，一些重复请求的页面将不被记录在w e b 服务器日志文件中，而这些页面记录又是w e b 使用挖掘所需要的数据。路径补全就是利用请求页面内容推断出一些缓存网页的浏览情况，再将这些遗漏的请求补充到用户会话中1 1 8 j 。常见的本地缓存进行浏览方式：第一种是利用“后退”按钮进行后退；第二种是点击一个已访问过的链接：第三种是直接从浏览器的历史记录中访问链接。由于无法知道使用何种方法来读取缓存中的网页，常用的路径补全启发知识就假设利用最常用的“后退”方法，来进行缓存网页读取。检查引用日志确定当前请求来自哪一页，如果在用户的历史访问记录上有多个页面包含与当前请求页的链接，则将请求时间最接近当前请求页的页面作为当前请求的来源，若引用日志不完整，可以使用站点拓朴结构代替。2 2 5 事务识别用户会话是具备自然事务特征的对象，但对数据挖掘来讲，显得粗糙，事务识别的主要任务就是把会话进一步划分成具有一定语义的事务。目前主要有3种事务识别算法：( 1 ) 引用长度在不考虑网络延迟的情况下，用户浏览页面的时间，可以认为是当前页请求和其下一页请求之间的时间间隔。引用长度事务识别方法将w e b 页面集合划分为内容页和导航页两类。内容页面是用户关心的信息，浏览时间较长；导航页面是使用户快速地找到所需信息而设置的路标。可以采用页面所含超链接的数量作为划分标准，当页面中超链接达到一定数目时，可看成导航页，这是一种静态划分法。另外考虑到一个页面对于不同用户的作用不同，可根据用户花在这个页面上的时间来划分内容页与导航页。该划分方法认为一个事务由多个导航页面和一个内容页面组成，得出一个用户会话中内容页面和导航页面的分界，也就得到了该用户会话所对应的事务。( 2 ) 最大向自订路径硕十学何论文第二章w e b 使川挖掘介绍c h e n 等人提出的最大前向引用路径来定义事务的概念【l9 1 ，并用它作为划分事务的标准，对于每个用户会话，每一次前进浏览的第一页到回退的前一页组成的路径作为该用户会话的一个事务，该算法认为用户在回退前完成了一次有意义的页面访问过程，将缓存的因素考虑其中，消除了后退操作对访问模式的影响，目前这种算法被广泛应用于使用挖掘系统当中。( 3 ) 时间窗口基于时间窗的事务识别方法是将用户的访问操作按时间间隔分成一个个时间窗。假设有意义的事务模式的平均访问时长与时间窗有关联，对于充分大的时间窗，每个事务模式将包含整个用户的访问操作。时间窗口算法也可以用来对其他分割算法所产生的结果事务进行合并。例如，使用参引长度算法后，一个输入参数为1 0 分钟的合并时间窗口算法可以保证每个事务都有最小长度。2 3 模式识别模式识别是使用各种数据挖掘算法发掘隐藏在数据背后的规律和模式。模式识别可以采用众多领域( 如统计学、数据挖掘、机器学习、模式识别等) 的方法和算法，用于w e b 领域的主要算法有统计分析、关联规则、聚类、分类、序列模式等。2 3 1 统计分析它是从w e b 站点中抽取有关网站访问者知识的最常用的方法。通过分析会话文件和事务数据库，可对诸如网页视图、浏览时间、导航路径长度等做出不同种类的描述性统计分析。尽管这种方法缺乏深度，但这类知识有助于改进系统性能、提高系统的安全性、便于站点修改，并能提供营销决策支持。2 3 2 关联规则关联规则主要关注事务内在的关系。在w e b 使用挖掘中，关联规则挖掘就是挖掘用户在一个访问期间从服务器上访问的页面文件之间的关系，找出在某次服务器会话中经常一起出现的相关页面【2 0 l 。挖掘发现的关联规则往往是支持度超过预设闽值是一组访问网页，这些网页之间可能并不存在直接的引用关系。例如，用a p r i o r i 算法发现关联规则有可能发现访问电子产品的网页的用户和访问体育用品的网页的用户之间存在一定的联系。2 3 3聚类聚类就是把整个数据分成若干组，并使组与组之f 8 j 的差距尽可能大，组内数据的差异尽可能小。与分类不同，在丌始聚集之前用户并不知道要把数据分成几组，也不知道分组的其体标准，聚类分析时数据集合的特征是未知的。聚类根据8硕+ 学位论文第二章w e b 使川挖掘介绍一定的聚类规则，将具有某种相同性的数据聚在一起，也称为无监督学习1 2 。2 3 4 分类分类技术主要是根据用户群的特征挖掘用户群的访问特征( 某些共同特性) ，这些特性可将数据项映射到预先定义好的类中，即对新添加到数据库里的数据进行分类。在w e b 数据挖掘中，分类技术可以根据访问这些用户填写的个人信息或共同访问模式求出访问某一服务器文件的用户特征。另外，通过用户注册表和在线调查表也可得到用户的一些特性。但根据用户注册信息对用户进行分类，需要抽取出能最好地描述类别属性特征的特征。分类方法有很多种，常使用有监督的归纳学习算法。2 4 5 序列模式序列模式挖掘就是挖掘出数据集合间有时间序列关系的模式【2 2 】。这些序列所反映的用户行为有助于商家印证其产品所处的生命周期阶段，根据关心其产品的访问者的浏览模式决定广告的放置，针对特定用户群来制作广告，增加广告的针对性。利用对w e b 日志数据进行序列模式挖掘所获重的知识，有助于网站管理人员改善网站的组织，根据具有相同浏览模式的访问所访问的内容来裁剪用户与w e b 信息空间的交互，减少用户过滤信息的负担；预测未来的访问模式，了解w e b 正在发生的变化，改进市场策略。相关序列模式的存取分析，可对服务器的缓存、预取和交换参数等进行调整。另外，挖掘出来的一些暂时性的序列模式，可以分析企业战略实施或网站产品的促销效果。其它类型的空间序列模式分析可用于诸如趋势分析、转折点检测和相关性分析等序列模式的发现。2 4 模式分析如果没有合适的机制来辅助分析人员的理解，采用各种技术挖掘得到的模式数目庞大、表达晦涩，作用不大。模式分析技术和工具是近年来w e b 使用挖掘的一个新的热点。这些技术包括：统计，图形可视化，可用性分析和智能查询等 2 3 1o2 4 1可视化可视化是采用图形和图像表示抽象网络中错综复杂的关系；用文字描述解释和阐述模式之间相互的作用，帮助人们理解w e b 中海量数据各部分之间的关系、指导和加速查找的过程。i d l 交互式数据语言是面向矩阵、语法简单的第四代可视化语言，它支持o p e n g l 图形加速、量化可视化表现、集成数学与统计学算法、方便的数据输入输出方式、跨平台图形用户界面工具包、连接o d b c 兼容数据库及各种程序连9硕十学位论文第二章w e b 使用挖掘介绍接工具等，是目前科学数据可视化方面较好工具。2 4 2 联机分析处理o l a p 在基于多维数据模型的数据仓库或数据集市上使用，目标是满足决策支持或者满足在多维环境下特定的查询和报表需求，它将传统数据以多维数据模型重新组织，然后通过上卷、下钻、切片和切块、旋转等操作实现对多个抽象层上的知识发现。w e b 服务器访问数据随时间海量增长以及用户信息的数据存储呈现分布的趋势，表明了w e b 使用数据的分析通常需要大型数据仓库的支持。o l a p 技术整理信息的结构，允许基于主题对数据进行查询和分析，快速完成报表和数据分析功能，分析人员或管理人员能够从多角度对信息进行快速、一致、交互的存取，这些与可视化工具一起，大大增加w e b 使用挖掘的能力和灵活性。2 4 3知识查询机制知识查询机制首先分析查询目的，然后自动搜索相关的规则、模式以及其它知识，可以帮助分析用户的目的，用智能的方式回答查询，它不仅可以直接列出用户所指定属性的项目列表，还可以向用户提供辅助决策的附加信息。另外，为了使用户将焦点集中有某些感兴趣的细节上，常采用二种方法：一是在挖掘之前，在数据库上设置约束，使挖掘只在一部分数据中进行；二是挖掘过程中执行查询语句，不断筛选出需要的信息，将无用的数据过滤掉。2 5 本章小结w e b 使用数据挖掘的主要目的是用于发现用户访问站点的浏览模式，主要关注的就是如何从w e b 数据中发现出有意义的关联规则、序列规则、聚类分析、依赖模式等知识类型。本章对w e b 使用挖掘的数据采集、预处理、模式识别以及模式分析四个阶段进行了介绍，并对常用的预处理方法进行了分析。本章是第三章、第四章的研究基础。l o硕士学位论文第三章结合网页内容和网站结构的预处理第三章结合网页内容和网站结构的预处理预处理是w e b 使用挖掘的重要阶段，也是工作量较大的一部分，预处理的好坏将直接影响着挖掘结果的准确性、可信性。由于本地缓存、代理服务器和防火墙的存在，使得w r e b 日志中的数据并不精确，直接在其上进行预处理操作非常困难，而且可能产生错误预处理结果。网页内容、网站结构影响着w e b 使用挖掘的各阶段1 2 4 1 ，w r e b 使用挖掘的成功与否和网站的结构设计和内容安排有着密不可分的联系，反过来，w e b 使用挖掘的结果又能服务于网站结构和内容的设计与安排，二者相辅相成。如果在预处理阶段结合网页内容和网站拓扑结构，对提高挖掘结果起着积极的作用。本章围绕结合网页内容和网站结构进行预处理这一观点展开研究，首先介绍网页内容和网站结构的作用及处理方法，然后在此基础上提出结合网站内容和网站结构的预处理方法，该方法在区分用户上有较高的精度，为模式识别阶段提供较好的数据基础。3 1 网页内容处理用户所访问过的网页，可以认为是用户感兴趣的页面，对这些网页的内容进行准确描述，提取出页面的主题信息，再将信息应用于挖掘中，有助于提高挖掘结果的准确性1 2 引。也就是说，主题信息提取的准确性将直接影响网页内容的描述。由于w e b 页面的主题信息可以通过网页的特征词来反映，那么对网页特征词的提取就是对网页内容分析的重点和难点。对网页特征词的提取过程包括页面分词，特征评估，特征权重的计算等步骤。为了提高特征词提取结果的准确性，在提取之前还需要对网页内容进行分析处理，包括了文档采集、网页净化，提取之后进行文本聚类，将相似文本聚集在相似文本集中【2 6 1 ，对用户兴趣的分析有很重要的作用。网页内容处理的具体过程如图3 1 。图3 1 网页处理的一般过程3 1 1网页；争化因特网上的很多页面都是由一系列的h t m l 标记内容组成。根据w 3 c 组织对h t m l 语言的定义，h t m l 页面是一层层标记的嵌套体，诸如 的形式，有一个丌始标记就应该有一硕十学位论文第三章结合网页内容和网站结构的预处理个结束标记与它相对应l ! 。实际中的网页并不完全遵循这样的规范化格式，就算h t m l 标记只有开始没有结束，往往也能显示正确的内容。另外网页通常由体现内容的网页的“主题”信息和与主题内容无关的“噪音”部分组成。如一张新闻网页中的新闻部分，是主题内容，而导航条、广告信息、版权信息以及调查问卷等部分则是“噪音”内容。噪音内容通常分布在主题内容周围，有时也夹杂在主题内容中间，噪音内容一般无内容相关性。网页中的噪音内容不仅给w e b 上基于网页内容的应用系统带来困难，也给基于网页超链接指向的应用系统带来困难。快速准确地识别并清除网页内的噪音内容( 即网页净化) 是提高w e b 在净化后的网页上作信息提取不仅可以排除噪音信息对信息提取的干扰，提高信息提取的准确性，而且可以使得网页中的结构简单化，提高信息提取的效率。对于w e b 文档而言，净化后的h t m l 页面应该只保存网页内容文本，重要标签等信息。通过对净化的网页进行分析，发现h t m l 文档中隐藏了很多的规律。具体表现在有一些标记信息在文档中影响不大，如段落标记9 ，换行标记 ，块标记 p 胗等：而有一些信息却是用户非常关心的，如 、 、 等，进一步分析后发现其重要性各有不同，按递减依次排列如下：文档标题：文本标题： - 特殊文字样式： ( 粗体) ， ，q j ( 下划线) ， ( 斜体)链接： 文字吲a 值得一提的是 标记，如 ，虽然 标记中的数据能够提供了一些非常有用信息，但其格式不规范，有些网页中出现，而有些网页又不出现，还有一些网站为了提高搜索命中率，滥用该标记，因而只能起借鉴作用。在得到w e b 信息相应的文档以后，以标点符号为边界把文档切分成多个较短的字符串，并去掉其中多余的空格，变不规范格式为标准格式，为后面的分词做准备。3 1 2 特征词提取特征词提取是网页处理过程中的重点和难点，它是用户兴趣模型创建的基础，特征词提取的准确度越高，所构造的用户兴趣模型与用户需求就越接近。为了得到精确的特征词，需要经过一系列的过程e 引。可以采用页面分词、特征评分函数、权重计算等过程将网页的特征词提取并赋予权重值，最后用向量空| 日j 法表示。文献p 91 中常把名训和动词等有实际意义的词作为特征词。特征词提耿叶l硕+ 学位论文第三章结合网页内容希l 网站结构的预处理两个关键性的问题是评估函数的选取和特征词的选取。1 页面分词一个分词问题从直观上来说，就是要把连接的文本字符串序列进行边界划分，输出一系列的中文词串( 词条) 。对于中文文档来说，词与词之间没有分隔符，一个句子是由一串连续的汉字组成，汉语中的词具有不同的长度，相同的字可出现在许多不同的词中，还有许多词是由单个字组成，这使得中文分词是一个不平常的工作。由于存在许多可能的边界，可以这样分，也可以那样分，这就表示发生切分歧义，需要运用某种策略来选择一处正确的分词方案。汉词的分词方法可以分为基于词典的切分方法和基于概率统计的切分方法。本文采用一种基于词典的切分方法，它是目前最常使用的简单有效的方法，其基本思想是：主要依据词典信息，而不使用规则知识和统计信息，按一定的策略将汉字与词典中的词逐一匹配，如果匹配成功，就加以切分。匹配的方法有正向匹配法和逆向最大匹配法，二者基本原理相同，不同的是分词切分的方向，前者从汉字字串的开始抽取，后者从尾端开始抽取，另外使用的分词词典也不同。逆向最大匹配法从被处理文档的末端开始匹配扫描，每次取末端的字词作为查找匹配词，若匹配失败，则去掉最前面的一个字，继续查找。据统计，逆向最大匹配法比正向匹配法的误差要小，产生歧义的现象也比较少。例如切分字段“大学生活”，正向匹配法的切分结果为“大学生活”，而逆向最大匹配法利用逆向扫描，可得正确的切分结果“大学生活”。2 特征评估函数目前对文本特征提取的研究中，特征提取一般是通过构造一个特征评估函数，把测量空间的数据投影到特征空间，得到数据在特征空间的值，然后根据特征空间中的值对每个特征词进行评估，特征选择就成了选择值最高的若干个特征。特征选取中常见的特征评估函数有1 3 0 】：文档频率、信息增益、互信息等。这些方法的基本思想都是基于阈值的统计方法，即对每一个特征词，计算其统计值，然后设定一个阈值t ，把值小于t 的那些特征词滤掉，剩下的即认为是有效特征。( 1 ) 文档频率文档频率是训练集中出现某个特征词的文档数。其主要思想是：在训练文本集中对每个特征计算它出现的文档次数，若该项的d f 值小于某个阈值则将其剔除，若d f 值大于某个阈值也将其去掉，因为d f 值太低则说明该特征缺乏代表性，而d f 值太高则说明缺乏区分度。基于文档频率的特征选择是最简单的特征选取手段。它通过计算线性近似复杂度来衡量巨大的文档集，被认为是一个提高硕十学位论文第三章结合网页内容和网站结构的预处理效率的有效方法。( 2 ) 信息增益信息增益表示文本中包含某一特征值时文本类的平均信息量。它定义为某一特征词在文本中出现前后的信息熵之差，即该特征为该类别提供的信息量的大小。一般方法是，根据训练数据，计算出各特征词的信息增益，再按信息增益的对于特征词d 和文档类别c ，信息增益通过考察c 中出现和不出现的d 的文档频率衡量d 对于c 的信息增益【3 l l ，当信息增益小于某个预定的值时，特征词d就要被从特征集中去除。此方法度量了当知道一个特征词在文档中，进行类预测所获得的信息比特数。信息增益的定义如下：删 c ) - p 莩p ( 叫) l o g 篙+ p ( _ ) 军聃m g 篱、7公式( 3 1 ：7e f v i o ( d ) = i g ( d ，o公式( 3 2 )其中p ( c i l d ) 表示文本中出现特征词d 时，文本属于c i 的概率，p ( c i l d ) 表示文本中不出现特征词d 时文本属于c i 的概率；p ( c i ) 表示类别出现的概率；p ( d )表示d 在整个文本训练集中出现的概率。本文采用了信息增益进行特征项抽取的判断标准，其算法过程如下：初始情况下，该特征项集合包含所有该类中出现的词。对于每个词，计算词i g 值对于该类中所有的词，依据上面计算的i g 值排序。抽取一定数量的词作为特征项，具体需要抽取多少维的特征项，目前没有很好的解决方法，一般采用先定初始值，然后根据实验测试和统计结果确定最佳值，一般初始值定在几千左右。将每类中所有的训练文本，根据抽取的特征项，进行向量维数压缩，精简向量表示。其他抽取特征项的算法，除了判断函数上有所差别，主要过程类似。3 特征项的权重不同的特征项以及它出现的频率对于文档的重要程序和区分度是不同的，因此对文本进行形式化处理的时候，需要对特征词进行赋权。以前的研究中，通常考虑二个方面：一个词在某篇文档中出现的次数越多，则对识别文档的贡献越大；一个词在不同文档中出现的次数越多，则它区分不同的文档的能力越弱。以往权值计算的方法有很多，如词频权重，t f - i d f 权重等m 。本文采用提1 4硕十学位论文第二章结合网页内容和网站结构的预处理出一种基于熵概念的权重计算方法。因为特征提取和特征选择的评估函数，都是评价特征项中所包含的信息量多少的方法。可以认为特征提取和特征选择方法是对特征词重要性的某种刻画，因而用这些特征评估函数计算出的值可以作为“特征项权重”参加计算。采用这种方法对特征词进行赋权公式：w ( d o ) = t f ( d ) 幸e f v ( d )公式( 3 3 )或者w ( d i 沪t f i d f ( d ) 幸e f v ( d )公式( 3 4 )e f v ( d ) 为使用权值评估函数所得到的值，由公式( 3 2 ) 计算得到。通过3 1 1 节对净化后的页面进行分析，得出w e b 网页特征词的权重不仅与其在文档中出现的频率而且还与位置相关，但以上方法只考虑了特征词在文档中出现的频率对权重值的影响。因此，下文介绍综合考虑频率和位置的w e b 文档的权值计算方法。通过对网页h t m l 文档结构的分析，发现文档中某些特殊标记的特征词重要性相对较高些，主要有如下几种【3 2 】：在文档标题 出现的特征词，权重最大。在文本标题 ， ， 渺出现的特征词，权重较大。特殊文字样式 等出现的特征词，权重中等。文本内容中出现的特征词，权重比上面三种小些。考虑到h t m l 标记对权值的影响，定义九表示出现在网页中的带有标记0的特征词氐的权重调整因子( h t m l 标记与权重调整因子的关系参看表3 一1 ) ，表3 - 1 权重调整因子取值标记权重调整因子7654 3结合网页结构特征的权重函数h t w ( d i j ) 定义为：h d w i ( d , j ) = 砧w ( d ) = ( 如xt f ( d , j , 护) e f v ( d i , 目) )公式( 3 - 5 )占或者h ，w e ( d , i ) = 乃w ( d ) = ( 乃t f - i d f ( d , j , 臼) xe f v ( d f ，秒) )公式( 3 6 )口为了验证该方法的有效性，本文收集了某门户类网站的部分网页进行实验，硕十学位论文第三章结合网页内容利网站结构的预处理采用t f i d f 以及信息增益做特征评估函数，进行不同特征加权算法的实验比较。实验结果如表3 2 。表3 - 2 不同特征加权算法的实验比较t f i d fh a w i ( d )h d w 2 ( d )查全率查准率查全率查准率查全率查准率交通1 0 09 6 7 7 49 8 3 3 38 5 5 0 71 0 09 6 7 7 4体育1 0 09 9 0 9 99 8 1 8 21 0 01 0 09 9 0 9 9军事1 0 01 0 01 0 01 0 01 0 01 0 0医药9 8 3 3 35 7 8 4 39 8 3 3 35 8 7 0 69 5 5 0 06 3 5 8 7政治6 7 3 4 77 4 1 5 77 0 4 0 88 2 1 4 38 1 6 3 36 4 5 1 6教育9 3 8 4 69 1 0 4 59 6 1 5 49 8 4 2 59 6 1 5 41 0 0环境1 0 01 0 01 0 01 0 09 9 3 3 39 9 3 3 3经济9 4 6 6 79 9 3 0 19 3 3 3 39