（计算机应用技术专业论文）基于internet的用户个性化兴趣模型的研究.pdf

摘要互联网的飞速发展与普及，使我们的工作、学习、生活和娱乐等各个方面正在发生巨大变化，也给我们提出了许多亟需解决的实际问题。例如，如何通过更加智能和个性化的i n t e m e t 系统，解决“信息过载”和“资源迷向”的问题，让人们能够更充分地使用i n t e m 啦上的信息资源。本文所研究的“用户个性化兴趣模型”正是是各种个性化智能系统的基础，因此具有理论和实用价值。本文首先围绕建立用户个性化模型的关键技术进行研究，这些技术包括w e b 挖掘、用户行为挖掘、机器学习，以及a g e n t 技术等。w e b 挖掘是将传统的数据挖掘技术和w e b 技术相结合发展而来，是从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用模式和隐藏的信息，本文主要针对日志挖掘、文本挖掘和结构挖掘三种w e b 挖掘技术进行了研究。用户行为挖掘是研究用户个性化兴趣的另一个关键技术，也是本文所设计和研究的用户个性化兴趣模型中所采用的一项重要技术。机器学习技术方面本文主要研究的是在人工智能领域里发展十分成熟的神经网络技术。而a g e m 技术即智能代理技术，是目前各种智能i n t e m e t 系统广泛研究和采用的一项新技术，本文也对它的概念和应用作了初步的探讨。然后本文提出了用户个性化兴趣模型的体系结构，对各部分的实现算法进行了分析和设计，包括评定页面的用户兴趣度、页面的分词、特征提取、通过混合挖掘和学习算法建立和更新用户模型等，以及些实验。获取用户兴趣所采用的方法是：首先针对用户所浏览的w e b 页面，分析这些页面与用户兴趣的相关度，提出“用户兴趣度”的概念，通过暗地观察用户行为( 如收藏、保存、打印、浏览时间、拖动滚动条次数等) 分析页面的用户兴趣度。同时，进一步分聿厅不同行为所体现的不同的用户兴趣度的等级，以及不同用户行为体现不同的用户兴趣度的能力。然后分析用户所浏览的这些w e b 页面中所包含的用户真正感兴趣的内容。主要是结合w e b 挖掘技术和机器学习的方法，将文本转化为向量空间，进行特征提取，结合页面的用户兴趣度，进行相似度学习和神经网络学习。本文最后围绕用户个性化兴趣模型的应用进行了研究，设计了个性化主动信息服务模型。个性化主动信息服务模型又称为个性化的信息推荐系统，首先建立用户的的兴趣模型，然后进行智能的信息搜索与过滤，最后向用户提供个性化的信息推荐，同时根据用户的反馈更新用户的个性化兴趣模型。并且，系统可以通过兴趣小组的方式，结合用户的兴趣模型。实现用户之间的信息共享。最后，本文对智能搜索引擎、用户自适应w e b 站点以及基于i n t e m e t 的个性化学习等应用也进行初步探讨。关键词个性化用户兴趣模型w e b 挖掘用户行为机器学习智能代理a b s t r a c tw i mr a p dd e v e l o p m e n ta 1 1 dp o p u l a r i t yo f t h ei n t e m e t ，a i m o s te v e r ya s p e c to f o u rw o r ks t u d y ，i f ea n de n t 叫a i n m e n t h a v eb e 朋c h a n g i n gg r a d u a l l y ，如dm e a n 廿m em a n yp r o b l e m sn e e d e ds o l v e dq u i c k l ya r ea p p e a 丁 n g f o re x a m p l e ，h o wt or e s d l v et h ep r o b l e mo f ”i n f o r i i 】a t i 。no v e r l o a 矿a n d ”r e s o u r c e1 。甜”，a n dh e l p 1 ep e o p l et om a k et h eb e s to f 也ei n f 0 蛳a t i o na n dr e s o u r c eo fi n t e m e t ，b yd e v e l o p i n gm o r ei n t e l i 追e n ta n dp e r s o n a l i z e di m e m e ts y s t e m s i nt h i st h e s i s ，p e r s o n a l i z e du s e rp r o f i l ei sd i s c u s s e d ，w h i c hi st h e b a s eo f v a r i 叫si n t e i i i g e n ta r i dp e r s o n a i i z e ds y s t e m s s ot h es t u d yh a st h e o r e t i ca 1 1 dp r a c t i c a lv a i u e f 1 r s t ly ，t h ep 印e rp u t sf o r w a r d 血ek e yt e c h n i q u e st ob u l dp e r s o n a l i z e du s e rp r o n l e ，s u c ha sw e bm i n l n g ，u s e ra c t i o nm n i n g ，m a c h i n el e a m i n g ，a n da g e n t w e bm i n i n gi sd e v e l o p e db yt h ec o m b i n i n go ft h et r a d i t i o n a ld a t am i n i n ga n dt h en e w e bt e c h n i q u e s ，a n di st oe x t r a c tt l ei n t e r e s t e dp o t e n 廿a 1u s e m lp 啦e ma 1 1 dh i d d e ni n f b h n a t i o n 厅o mt h ew e bf i l e s 如dw e ba c t i v i t i e s t h r e ew e bm i n i n gt e c h n i q u e sa r ep u tf b n v o r di nt h i sp a p e r ：i o gm i n i n g ，c o n t c n tm i f l i n ga 1 1 ds t n l c tm n g a sa n o l h e rk e yt e c h n i q u e ，u s e a c t i o nm i n i n gi sa l s ou s e di nb u i l d i n gp e r s o n a l i z e du s e rp r o f i i e i nr e s p e c to fm a c h i n el e a m i n t h ep a p e rd i s c u s s e st h en e u r a ln e t w o r ka l g o r i m mw h i c hi saw e l l s t u d i e dm e t h o di nt h er e a i mo fa r i t i n c i a li n t e l l i g e n c e a n da g e n ta san e wm e 廿1 0 dw i d e l ys t u d i e da n du s e db ya 1 1k i n d so fi n t e l l i g e n ti n t e m e ts y s t e m st o d a y ，i sa i s od i s c u s s e di nb r i e f t h e nt h ep 印e rp u t sf o ，w a r dt h ea r c h i 据c l u r eo f t h ep e r s o n a l i z e du s e ri n t e r e s tm o d e 】t h ea l g o r i t i m so fe a c hp a no fm es ”t e ma r ea 1 1 a l y z e da n dd e s i g n e d ，i n c l u d i n ga s s e s s i n gt h eu s e ri n t e r e s td e g r e eo faw e bp a g e ，c u t t i n gw o r d s 鼢t e ) ( t ，e x t r a c t i n gf e a 仙r ew o r d s ，b u j l d i n ga r i du p d a t i n gu s e rp r o 打l eb yh y b r i dm i n i n ga n di e a m i n ga l g o r i t l l m s s o m ee x p e r i m e n ti sa l s od i s c u s s e d t bo b t a i nu s e r n t e r e s t ，t h e 打r s ts t e di st oa 1 1 a l y z e dt h er e l a t i v 姆b e t 、v e e nt h ep a g e sr e a db yu s e ra n dt h eu s e ri n e r e s t ，w h i c hi sn a m e d u s e ri n t e r s td e g r e e ”a n di sa n a l y z e db yo b s e r v i n gt l eu 5 e rb e h a v i o u r( s u c ha sb o o k m a r k 细g s a v i n 岛p r i m i n g ，b r o w s i n g ，a n ds c r 。h i n 曲a tt h es a m et i m e ，t h ea b i l i t ya n dt h ed e g f e eo f h o wd i f f 鲁r e n tu s e ra c t i o n st oi nd i c a t et h eu s e ri n t c r e s ta r ea l s od i s c u s s e d t h es e c o n ds t e pi st oa n a l y z e dw h a ti st h er e a lu s e ri n t e r e s t e dc o n t e n ti nt h ew e bp a g e b yc o m b i n i n gt l l ew e bm i n i n ga n dm a c h i n el e a m i n gm e t h o d ，c h a n g i n gt h eh t n l ld o c u m e n t st ov e c t o rs p a c e ，e x 妇c t i n gf e a t u r e ，a 工l dl e a m i n gu s e ri n t e r e s tb yr e ja t l v 时1 e 啪i n 2m e t h o da n dn e u r a ln e t w o r k f i n a l l yt h ep a p e rd i s c u 5 s e ss o m e 印p l i c a t i 蚰so fp e r s o n a l i z e du s e rp r o 右l ea n dd e s i g 工l sap e r s o n a l i z e da c t i v el n f o m a t l o ns e r v i c em o d e l p e r s o n a l i z e da c t v e1 n f o r m a t i o ns e r v i c em o d e li sa s 。n a m e dp e r s o n a l i z e di n f o m l a l i o 订r e c o m m e n d a t f o ns y s t e m t h es t e p st ob u i j dt h es y s t e ma r eb u i l d n gt h eu s e p r o n l e ，s e a r c h i n ga 1 1 df i l t e r i n gt h ei n f o m a t i o ni n t e l l i g e n 廿y r e c o m m e n d i n gt h ei n f o m a t i o na c t i v e l va n du p d a t i n gt h eu s e rp r o n l ea c c o r d i n gt ot h eu s e r sf e e d b a c k t h es y s t e mc a na l s oh e i pt h ep e o p i et os h a r et h ei n f b r r n a t i o nw u s e r so fi m e r e s tg r o u p s o m eo t h e r 印p 1 1 c a t l o n sa r ea l s od i s c u s s e d ，s u c ha si n t e l l i g e n ts e a r c h i n ge “g i n e ，a d a p t i v ew e bs i t ea n dp e r s o n a l i z e ds t u d yb a s e do ni n t e r n e t k e y w o r d sp e r s o n a l i z c ，u s e rp r o f j l e ，w e bm i n i n g ，u s e ra c t i o n ，m a c h i n el e a m i n g ，a g e n t1 2li 乞垒生三王一1 1 课题背景第一章绪论近年来，i n t e r n e t 的网络和应用都在以惊人的速度在发展。根据中国互联网络信息中心2 0 0 3 年1 月公布的中国互联网络发展状况的统计数据，在中国，上网计算机总数达到2 0 8 3 万，上网用户总数达到5 9 1 0 万，w w w 站点数约为3 7 1 6 0 0 个。而就全世界而言，上网用户数达到数亿。同时，各种各样的网络应用早已走进各行各业，尤其是远程教育、电子商务、搜索引擎等等。但是由于i n t c m e t 是一个开放、分布的信息空间，它本身所固有的3 个特点已经明显地阻碍了人们充分地使用i n t e m e t 上的信息资源：( 1 ) i n t e m e t 上可利用的信息是无组织的，多种结构形式的，并且分布在全世界的各个站点上；( 2 ) 数据和服务的类型以及数量每天都在大量增加，因而信息可利用性和可靠性也在不断地变化；( 3 ) 由于信息源的动态性以及潜在的有用信息的更新和保存问题，信息常常是模糊的：有时甚至是错误的。由于上述原因，在i n t e m e t 上进行信息检索经常会出现“信息过载”，即网上的信息是海量和无组织的，易发生“资源迷向”，即用户不知道如何更加有效地利用资源等问题。人们迫切需要一些智能的和个性化的i n t e r n e t 系统，能学习和了解用户的兴趣爱好，成为用户的助手或秘书，能帮助用户从浩如烟海的i n t e r n e t 信息中快速而准确地搜索出他们感兴趣的内容：能为用户提供主动的、最新的信息服务和推荐；能帮助用户实现个性化的远程学习等。而这些系统的基础都离不开一个“个性化的用户兴趣模型”。1 2 国内外研究动态和水平目前，随着人工智能领域的不断发展和a g e n t 理论的提出，各种个性化的智能系统不断涌现出来，如国外著名的w e bw a t c h e r ，帮助用户在网上导航，通过对用户选择的链接或站点跟踪学习，改善导航质量；如国内的南京大学研究实现了一个个性化的信息搜集a g e n t 系统瞰j ，它是一个远程开放式学习的教材信息搜集的多a g n e t 系统。这些系统的核心都是通过观察、收集、挖掘和分析用户的各种个性化信息，实现个性化服务。同时，与智能性和个性化相关的各种技术也发展迅速，如_ i ；| r e b 挖掘技术，是将传统的数据挖掘技术和w e b 结合起来，从w 曲文档和w 曲活动中抽取感兴趣的潜在的有用模式和隐藏的信息。针对用户行为的研究也很多，如把用户浏览的时长和动作视为用户兴趣的隐含指针，收集、衡量、评价“隐含兴趣指针”的预测用户兴趣的能力，以及将用户人为地评定页面的兴趣等级视为用户兴趣的显式指针，研究隐含指针与显示指针的相关性。在机器学习方面，有许多成熟的算法和不断涌现出来的新算法，如基于统计的贝页斯算法、神经网络算法、s v m 算法等，这些都为研究用户个性化兴趣模型提供了基础。如何在方便用户的同时。了解用户真实和不断变化的兴趣，是此项研究的难点a 而没有把针对w e b 页面的研究与用户行为的研究结合起来，是以前各种研究的不足之处。1 3 本文的主要工作本文一是围绕如何建立用户个性化兴趣模型，分析了解用户兴趣，以便进行个性化服务。首先研究了建立用户个性化兴趣模型的关键技术，包括w e b 挖掘，即日志挖掘、文本挖掘和结构挖掘，用户行为挖掘，机器学习，以及船e n t 技术等。机器学习技术主要研究有指导的学习算法，如人工智能的神经网络技术等。然后研究了用户个性化兴趣模型的体系结构，分析设计各部分的实现算法，包括评定页面的用户兴趣度、页面的分词、将文本转化为向量空间、进行特征提取、通过相似度学习或者神经网络学习，建立和更新用户模型的算法。二是围绕用户个性化兴趣模型的应用进行研究，包括个性化信息推荐、智能搜索引擎、电子商务中的个性化服务以及远程教育中的个性化学习等。个性化的信息推荐又可以称为个性化主动信息服务。是在建立用户个性化兴趣模型的基础上，针对用户兴趣在i n t e r n e t 上进行搜索，然后再通过用户兴趣模型对搜索结果进行过滤，最后向用户进行推荐。系统根据用户对所推荐信息的反馈，不断更新用户个性化兴趣模型，使模型可以随用户兴趣的变化而变化。这种反馈可以是显式的，如让用户对页面评定等级，也可以是隐式的，如用户的行为。并且，可以根据不同用户的个性化兴趣模型进行聚类，建立兴趣小组，实现兴趣小组之间的信息推荐。本文所研究的内容创新点在于，首先针对用户所浏览的w e b 页面，分析这些页面与用户兴趣的相关度，提出了“用户兴趣度”的概念，通过暗地观察用户行为( 如收藏、保存、打印、浏览时间、拖动滚动条次数等) 分析页面的用户兴趣度。同时，进一步分析不同行为所体现的不同的用户兴趣度的等级，以及不同用户行为体现不同的用户兴趣度的能力。然后分析用户所浏览的这些w e b 页面中所包含的用户真正感兴趣的内容。研究的成果是：1 、研究设计了一个基于1 1 1 t e m e t 的用户个性化兴趣模型，提出了系统的体系结构和实现方法，基于用户兴趣度，以及采用混合挖掘方法，建立和更新用户模型：2 、针对某些环节进行了实验性研究。3 、针对用户个性化兴趣模型的应用，设计了一个基于用户个性化模型的主动信息服务系统。1 4 课题研究的意义用户个性化兴趣模型的研究普遍适用于i n t e m e t 的各个应用中，包括自适应的w e b 站点( a d a p t i v es i t e ) 、智能搜索引擎、信息的个性化推荐、电子商务的个性化服务、远程教育的个性化学习等等。因此，此项研究具有理论价值和实用价值。1 5 论文的大致结构本文第二章介绍建立用户个性化模型的关键技术，第三章介绍用户个性化兴趣模型的设计与实现，第四章介绍用户个性化模型的应用，最后是总结与展望。2第二章建立用户个性化模型的关键技术正如第一章所介绍，伴随着i n t e m e t 应用的发展，人们越来越需要一种基于i n t e m e t的个性化服务。而所谓个性化服务，就是指对不同用户采取不同的服务策略，提供不同的服务内容。本文所提出的“用户个性化兴趣模型”，是关于用户兴趣、偏好、访问模式的可计算描述，它是个性化服务的基础。用户建模，是指根据用户信息( 如浏览内容、浏览行为等) 归纳出用户模型。用户建模是实现个性化服务的关键技术。本章主要介绍在用户建模中主要采用的技术，包括w e b 挖掘、用户行为挖掘、机器学习以及a g e n t 技术等。2 1w e b 挖掘1 概述6 0 年代，大的物理流伴随着大信息流。传统的文件方式不能适应信息处理的需求，因此出现了数据库技术。9 0 年代，人类积累的数据量以高于每月1 5 ( 或每年5 3 倍)的速度增加，数据海洋不能产生决策意志，为了进行决策，人们不断地扩大数据库能力，搜集海量数据，但这使得决策者更难于决策，因此出现了数据挖掘技术，以便从数据库中发现知识。数据挖掘技术包括特征、分类、关联、聚类、偏差、时间序列、趋势分析等。近年来，i i l t e m e t 正以令人难以置信的速度在飞速发展，越来越多的机构、团体和个人在i n t e m e t 上发布信息、查找信息。虽然i n t e m e t 上有海量的数据，但由于w e b是无结构的、动态的，并且w 曲页面的复杂程度远远超过了文本文档，人们要想找到自己想要的数据犹如大海捞针一般。信息检索界开发了许多搜索引擎，但其覆盖率有限，因此查全率低，一般的搜索引擎是基于关键字的查询，命中率较低，另外不能针对特定的用户给出特殊的服务，因为每个人感兴趣的东西是不一样的，因此不具有个性化。解决这些问题的一个途径，就是将传统的数据挖掘技术和w 曲结合起来，进行w e b 挖掘。w e b 挖掘f 1 就是从w 曲文档和w 曲活动中抽取感兴趣的潜在的有用模式和隐藏的信息w c b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行挖掘，确定权威页面，w 曲文档分类，w 如l o g 挖掘、智能查询，建立m e t a 。w e b 数据仓库等。万维网目前是一个巨大、分布广泛、全球性的信息服务中心，它涉及新闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其它信息服务。w e b 还包含了丰富和动态的超链接信息，以及w 曲页面的访问和使用信息，这为数据挖掘提供了丰富的资源。然而从以下的分析可以看出，对w 曲进行有效的资源和知识发现具有极大的挑战性。( 1 ) 对有效的数据仓库和数据挖掘而言，w 曲似乎太庞大了。w 曲的数据量目前以兆兆字节( t e r a b y t e s ) 计算，而且仍然在迅速地增长。许多机构和社团都在把各自大量的可访问信息置于网上。这使得几乎不可能去构造个数据仓库来复制、存储或集成w e b 上的所有数据。最近，有一些工作在致力予存储或集成w 如上的所有数据。例如，在n p ： v wa r c h i v e o r g i n d e x l h 缸n l 下，可访问到一个巨大的数十兆兆字节的因特网存档。( 2 ) w e b 页面的复杂性高于任何传统的文本文档。w 曲页面缺乏同一的结构，它包含了远比任何一组书籍或其它文本文档多得多的风格和内容。w 曲可以看做一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任何有关排列次序加以组织。它没有分类索引，更没有按标题、作者、扉页、目次等的索引。在这样个图书馆中搜索希望得到的信息是极具挑战性的。( 3 ) w 曲是一个动态性极强的信息源。w 曲不仅以极快的速度增长，而且其信息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。( 4 ) w 曲面对的是一个广泛的形形色色的用户群体。目前因特网上连接有约5千万台工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不已和在等待信息中失去耐心。( 5 ) w 曲上的信息只有很小的一部分是相关的或有用的。据说9 9 的w e b 信息相对9 9 的用户是无用的。虽然这看起来不是很明显，但个人只是关心w e b 上的很小很小一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴趣的，而且会淹没所希望得到的搜索结果。这些挑战已经推动了如何高效且有效地发现和利用因特网上资源的研究工作。w 曲挖掘是一个更具挑战性的课题，它实现对w 曲存取模式、w 曲结构、规则和动态的w 曲内容的查找。2w e b 挖掘的分类我们可以将w 曲挖掘一般地定义为：从与w w w 相关的资源和行为中抽取感兴趣的、有用的模式和隐含信息。一般地，w 曲挖掘可分为3 类：w e b 内容挖掘( w 曲c o n t e n tm i n i n g ) 、w 曲结构挖掘( w 曲s 衄l c n l r em i n i n g ) 和w 曲日志挖掘( w 曲1 0 9m i n i n g ) 。图2 1 给出了w 曲挖掘的分类图。( 1 ) w 曲内容挖掘w 曲内容挖掘是从文档内容或其描述中抽取知识的过程。w 曲文档文本内容的挖掘，基于概念索引的资源发现，以及基于代理的技术都属于这一类。w e b 内容挖掘有两种策略：直接挖掘文档的内容，或在其它工具搜索的基础上进行改进。采用第1 种策略的有针对w e b 的查询语言w e bl o g ，w e bo q l 等，利用启发式规则来寻找个人主页信息的a h o y ，等等。采用第2 种策略的方法主要是对搜索引擎的查询结果进行进一步的处理，得到更为精确和有用的信息。属于该类的有w 如s q l ，及对搜索引擎的返回结果进行聚类的技术等。( 2 ) w e b 结构挖掘w 曲结构挖掘是从w w w 的组织结构和链接关系中推导知识。由于文档之间的互连，w w w 能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。这方面工作的代表有p a g er a l l l ( 和c l e v e r 。此外，在多层次4硕士学位论文w 曲数据仓库( m l d b ) 中也利用了页面的链接结构。( 3 ) w 曲日志挖掘w e b 日志挖掘的主要目标则是从w e b 的访问记录中抽取感兴趣的模式。w w w 中的每个服务器都保留了访问目志( w 曲a c c e s sl o g ) ，记录了关于用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。这方面的研究主要有两个方向：一般的访问模式追踪和个性化的使用记录追踪。一般的访问模式追踪通过分析使用记录来了解用户的访问模式和倾向，以改进站点的组织结构。而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点图2 1w e b 挖掘的分类2 1 1w e b 日志挖掘w 曲挖掘的个重要任务是w 曲使用记录挖掘，即w e b 日志挖掘，它通过挖掘w e b 日志记录来发现用户访问w 曲页面的模式。通过分析和探究w e b 日志记录中的规律，可以识别电子商务的潜在客户，增强对最终用户的因特网信息服务的质量和交付，并改进w 曲服务器系统的性能和结构。目前，w e b 日志挖掘技术主要分为两大类：基于w e b 事务的方法和基于数据立方l 基于w e b 事务的w e b 日志挖掘技术激溅戮麓舯肝硎黻孰桩铲蝴呦臌州胪折戤撕骗w 曲日志预处理过程序列模式识别序列模式分析数据净化用户识别会话识别页面过滤路径补充图2 2c h e n 为代表的基于w 曲事务的方法基于w e b 事务的日志挖掘技术的基本流程是：( 1 )预处理过程。w e b 服务器日志中的内容非常丰富，但是由于本地缓存、代理服务器、防火墙的存在，使得直接在w e b1 0 9 数据上进行挖掘变得十分困难和不准确。因此，在实施数据挖掘之前，首先必须对w e bl o g 文件进行数据净化、用户识别、会话识别、页面过滤、路径补充等一系列的工作驯。数据净化( d a t ac l e a n i n g ) 是指删除w e b 日志中与挖掘算法无关的数据，同时将有用的w e b 日志记录信息转换适当的数据格式。用户识别( u s e ri d e n t i f i c a t i o n ) 和会话识别( s e s s i o ni d e n t i f i c a t i o n ) 是从日志中的每一条记录中，识别出相应的用户，并将曰志中的多条记录分割为不同的w e b 事务。页面过滤是针对w e b 页面的帧( f r a m e )结构，对日志记录进一步过滤，而路径补充则是考虑到用户可能在浏览器中使用b a c k方式而使w e b 日志中遗漏了重要的访问信息。( 2 )序列模式识别。w e b 事务分割完成以后，按下来就是实施“序列模式识别”的工作。第一步，通过m f 算法( m a x i m a lf o r w a r dr e f e n c e s ) 将日志数据中原始序列，转换为一个访问子序列集。其中的每一个访问子序列都代表一个从用户访问点出发的最大向前引用，其目的是过滤掉为了取消访问而产生的回退引用的影响，从而使我们能专注于挖掘有意义的用户访问序列。第二步，从最大向前引用集中找出“大引用序列”( l a r g er e f e r e n c es e q u e n c e s ) ，也就是频繁出现的引用序列。其方法和挖掘关联规则1 3 】( a s s o c e a t i o nr u l e s ) 的方法相类似，但不同的是，在挖掘访问模式时，一个引用序列必须是包含在最大向前引用中的连续引用，而在挖掘关联规则时，一个“大项目集”( l a r g ei t e m s e t ) 仅仅是一个事务中的项目的集合。第三步，从大引用序列中确定“最大引用序列”m a x i m a lr e f e r e n c es e q u e n c e s ) ，即频繁访问序列。这一步非常简单和直观，只要找出没有包含在其他任何大引用序列中的大引用序列即可。下面举个简单的例子说明以上的三个步骤。假设一个访问日志包含一个用户如下的访问路径： a ，b ，c ，d ，c ，b ，e ，g ，h ，g ，w ja ，0 ，u ，0 ，v ) ，如图2 3 所示。一三生- = 兰- _ 兰l 兰三二垒塞_ _ 。一ad图2 3 访问模式的示例于是，通过m f 算法可以得到这个用户的“最大向前引用集”是： a b c d ，a b e g h ，a b e g w ，a 0 u ，a o v 。在获取了所有用户的最大向前引用以后，问题就从“寻找频繁访问模式”映射为“在所有最大向前引用中寻找频繁连续子序列”。一个大引用序列( 1 a r g er e f e r e n c es e q u e n c e ) 就是指出现足够多次的一个引用序列。在一个最大向前引用集中，一个引用序列如果要被定义为一个大引用序列，必须出现的次数称为“最小支撑”( m i n i m a ls u p p o r t ) 。一个“大k 引用”( 1 a r g ek r e f e r e n c e ) 是指一个有k 个元素的大访问序列。将“大k 引用集”定义为l k ，而把它的候选集定义为c k 。正如前面所指出的，挖掘访问模式与挖掘关联规则的不同就在于，当挖掘访问模式时，一个引用序列必须是在一个最大向前引用里的连续引用，而挖掘关联规则时，个大项目集只要求是事务中的项目集合。因此，要得出大引用序列。必须研究新的算法。从“大引用序列”可以直接得出“最大引用序列”，一个最大引用序列就是没有包含在其他任何大引用序列中的大引用序列。例如，假设 a b ，b e ，a d ，c g ，g h ，b g )是“大2 引用集”( 也就是l 2 ) ，而 a b e ，c g h ) 是“大3 引用集”( 也就是l 3 ) 。那么，最大引用序列的结果就是a d ，b g ，a b e 和c g h 。对于信息服务的提供者而言，一个最大引用序列是与一个“热”的访问模式密切相关的。以下要着重描述在第一步中，将原始访问序列转换为最大向前引用集的m f 算法，以及在第二步中，为了从“最大向前引用集”中找出“大引用序列”，c h e n 等人提出的f s ( f u l ls c a n ) 和s s ( s e l e c t i v es c a n ) 两种算法。f s 算法从本质上说，是利用了一些h a s h 和p r u n e 技术，以解决前面所提到的访问模式与关联规则的差异问题，它要求每次都必须对事务数据库进行扫描。而s s 算法，则适当地利用了候选的引用序列，减少扫描事务数据库的次数，从而降低磁盘i 0 读写的开销。因此s s 算法相对f s 算法更先进，效率更高。寻找“最大向前引用”蝴f 算法一般而言，个访问日志数据库针对每一次链接的移动都包含一对 源节点，目的节点) 。在一条路径的开头，如果没有与前面的访问相链接，那么源节点为空。假定一个用户的一个访问序列是 ( s l ，d 1 ) ，( s 2 ，d 2 ) ，( s n ，d n ) ) ，我们可以将它映射为多个硕士学位论文以图2 2 为例，在第4 次移动( 也就是说，从d 到c ) 时出现了第一次回退引用。萼时，最大向前引用a b c d 被写入d f 中( s t e p3 ) 。在下一次移动( 也就是从c 到b )时，虽然在s t e p3 的第一个条件语句的判断结果是t r u e ，但因为此时标志f 为o ，表零至套倒退，所以不会写数据库d f 。在发生倒退从h 到g 时，出现了向前引用子序歹i ，这使得a b e g h 被放到y 中，然后写入到数据库d f 里。整个算法的执行过程列在下衾莘：5a b6a b e7a b e g8a b e g h9a b e ga b e g h1 0a b e g w1 1aa b e g w1 2a o1 3a o u1 4a oa o u1 5a o va o v ( e n d )表2 1m f 算法执行过程寻找“大引用序列”f s 与s s 算法一旦d f 数据库构造完成，即数据库里包含了所有用户的所有最大向前引用，那么就可以通过确定d f 中的频繁出现的引用序列来导出频繁访问模式。如果存在i 使s 。= ，f o r1 ，j j ，就称序列r 1 r k 是包含在序列s l s n 中的连续子序列。如果在d f 中有足够多数量的用户拥有包含r l ，r k 这个连续子序列的最大向前引用，那么这个含有k 个元素的引用序列r i ，r k ，就口u 做一个大k 引用序列。以下将描述两个挖掘访问模式的算法。一个叫做完全扫描算法( f u l l 一s c a n ，f s ) ，本质上是利用了d h p ( 就是h a s h i n ga n dp r u n i n g ) 的概念，同时解决访问模式与关联规则之间的差异问题。另一个是选择性扫描算法( s e l e c t i v e s c a n ，s s ) ，它充分利用了候选的引用序列，通过批量地选定大引用序列，从而减少所需扫描数据库的次数。_ 基于完全扫描( f s ) 的算法为了描述f s 算法，首先要概述一下d h p 算法的主要思想。d h p 在决定关联规则时有两个主要特征：一是有效率地产生大项目集，另一个是在每次扫描后有效地缩减事务数据库的尺寸。通过利用h a s h 技术，d h p 能非常有效率地产生候选项目集，特别是“大2 项目集”( 1 a r g e2 一i t e m s e t s ) ，从而能极大地改善整个过程的性能上的瓶颈。此外，d h p 有效地利用了p r u n i n g 技术来不断地缩减事务数据库的尺寸。前面已经定义l k 代表所有“大k 引用”( 1 a r g ek r e f e r e n c e s ) 的集合，而c k是一个候选“k 引用”的集合。c k 通常是l k 的一个扩展集( s u p e r s e t ) 。通过扫描d f ，f s 获得l l t 并创建h a s h 表( 也就是h 2 ) 来计算每个“2 引用7 的出现次数。类似于d h p ，从k 2 2 开始，f s 基于h a s h 表的统计数据( 包含在以前的扫描中的次数) 产生c k ，决定“大k 引用”集合，为下一次扫描缩减数据库的尺寸，并创建h a s h 表以决定候选的“k + 1 引用”。需要注意的是，当挖掘关联规则时，一个候选引用集合c k ，可以通过把l k l 和自己加到一起来产生，即三+ 。但是，由于访问模式与关联规则的不同，需要对该方法傲如下的修改。对于l k l 中的两个不同的访问序列r 1 ，r k 1 和s l 一，s k 一1 ，只有当r 1 ，r k l 包含s 1 ，s k 一2 ，或者s l 一，s k 一1 包含r l ，r k 一2时( 也就是说，在去掉一个序列的第一个元素和另一个序列的最后一个元素以后，剩9硕士学位论文下的两个k 一2 引用是一模一样的) ，这时才能把两个序列合在一起组成k 引用序列。当k 很小，特别是k = 2 的情况，如果把l k _ l 和自己加到一起来产生c k ，会导致非常多的候选引用，所以这时候使用h a s h 技术是很有帮助的。随着k 的增大，厶一，4 上。的尺寸将明显减小。因此，在j j 3 以后，f s 通常可以采用直接从厶一，+ 厶一，来产生c k 的方法，这对算法的简化是很有益的。为了计算在c k 中每一个k 引用的出现次数以决定l k ，需要扫描数据库d f 的一个被修整过的版本。从最大向前引用集中，找出c k 中的k 引用中的“大k 引用”。在扫描了整个数据库之后，那些在c k 中出现次数超过闽值的k 引用，就成为了l k 。如果l k 不为空，就重复继续下一轮，即k + 1 。与d h p 一样，每次数据库被扫描以后，f s 将对数据库进行修整以提高以后扫描的效率。一基于选择性扫描( s s ) 的算法s s 算法与f s 算法的相似点在于，它同样使用了h a s h 和p r u n e 技术来减少c p u 和i o 的开销，但不同点在于，s s 算法恰当地利用了以前的步骤中候选引用的信息，这些信息可以避免某些步骤中对数据库的扫描，从而进一步减少磁盘i o 的开销。具体所采用的方法是：在f s 算法中利用h a s h 技术能够产生较少数量的候选2 引用，事实上，这个小的c 2 可以用来产生候选3 引用。很明显，一个c ；如果由c ，c ：产生，而不是由厶+ l 产生，那么它的大小就会超过忆f ，g 由三：+ 三：产生。但是，如果瞄i 比c 3 l 并不大很多而且c ：和c ：都能存贮在主内存里，那么在对数据库进行下一次扫描时，就能同时找到l 2 和l 3 ，从而节省次数据库的扫描。由此可以设想，假如3 的c ：是由c ：一，产生，并且所有足3 的c ：都能够保存在内存中，那么扫描数据库的次数就可以减少至摄小，只需扫描2 次就可以决定所有的l k 。也就是说，用一个初始扫描来决定l 1 ，用一个最终扫描来决定所有其他的大引用序列。但要注意的是，当“最小支撑”相对较小，或者潜在的大引用较长时，c k 和l k可能会变得很大。如果当t 2 时j a + ，f 忱f ，c j 的尺寸可能会很会就变得很巨大，那么要从候选大引用集中产生所有的子序列f c 小， 七+ 1 ，将可能耗费过多的c p u 时间，从而节省磁盘i 0 开销所获得的全部利益就会被抵消。这表明，事实上有的时候扫描数据库来决定大引用序列是值得的。在一次数据库扫描之后，可以获得迄今为止尚未决定的大引用序列( 直到l m ) ，然后基于此时的l m 构建候选的m + 1 引用集合c 。根据c h e n 的实验发现，如果出现某个七2 且f q + 。f 雠j 时，进行一次数据库扫描来获取1 0硕士学位论文工。是值得的，这样可以避免候选引用集变得太大。( 与f s 算法一样，每次数据库扫描以后，s s 算法将对数据库进行修整以提高以后扫描的效率。) 然后，根据。获得c ：+ ：( 事实上这时+ ：和c 。是相等的) 。接下来，再利用c ；来得出c j j + 2 。这个过程不断持续直到候选的j + l 引用集为空。c h e n 通过实验对f s 和s s 算法进行了比较，无论是c p u 开销还是i o 开销，s s 比f s 都表现出了显著的优势。( 3 )序列模式分析。掌握了用户的访问序列模式，即频繁访问序列，就可以对所获得的知识进一步加以分析和利用。例如，路径分析( p 砒a n a l y s i s ) 可以用来发现w 曲站点中最经常被访问的路径，从而可以调整站点的结构，改善网站的组织方式，按照大多数访问者的浏览模式对网站加以重组。在w 曲使用记录挖掘的环境下，关联规则挖掘的目标是发现用户对站点各页面的访问之间的关系，这对于电子商务是非常有用的。时序模式1的发现，各种聚类和分类技术的采用对于w 曲使用记录中的模式发现都有其各自的作用。此外，个性化的用户交互和可视化的结果呈现，也是模式分析研究的新内容。在国外，p i t k o w 等人开发了w 曲v i z 系统来将w w w 的访问模式可视化。2 基于数据立方体的w e b 日志挖掘技术h a n 等人嗍提出基于数据立方体的w e b 日志挖掘技术 图2 4 ，他根据w e b 服务器目志文件，建立数据立方体( d a t a c u b e ) ，然后对数据立方体进行数据挖掘和联机分析处理( o l a p ) 【4 】。w 曲日志数据库数据立方体0 l a p 联机分析数据挖掘技术既弘画呻过滤转换l 逐层细化分析特征分析、性能分析、【汇总分析分类分析、关联分析、i 切片分析预测分析、趋势分析、l 切块分析时间序列分析图2 4h 为代表的基于数据立方体的的方法和基于w e b 事务的日志挖掘技术相似，基于数据立方体的w e b 目志挖掘同样要经过预处理、模式识别、模式分析三个步骤：( 1 ) 预处理过程。对w e bl o g 进