（计算机软件与理论专业论文）基于智能agent的web个性化信息检索系统.pdf

山尔大学硕士学位论文 摘要 面对i n t e r n e t 上的信息海洋，人们利用搜索引擎往往难以找到自己真正所需 的信息和知识。w e b 信息挖掘技术可以有效地解决如何在异质、分布的w e b 上快速、 有效地发现资源和知识，可以弥补搜索引擎的不足。 本文的研究目标是帮助用户在网上进行个性化信息的搜集和挖掘。本文针对 当前搜索引擎输出结果太多不能准确表达用户需求的问题，在对i n t e r n e t 信息检 索的发展历史和现存的问题进行分析，以及在研究w e b 信息挖掘技术和智能a g e n t 技术的基础上，提出了一种基于智能a g e n t 的w e b 个性化信息检索系统，并分析了 在w e b 信息服务领域引入智能a g e n t 技术实现w e b 个性化信息服务的理论可行性、 优越性，着重对其总体思路作了论述，对其系统设计与建模作了初步探索。围绕 该模型的构建和软件实现，本文的主要工作和创新有： 首先。所提出的模型系统采用多a g e n t 体系结构，面向特定的用户。在该系 统模型中同时表达了文档和用户两种信息描述模型文档是信息处理的对象，文 档模型的建立是特征提取、文档过滤等智能信息处理的基础；用户模型则体现用 户的兴趣和意图，用于用户兴趣的表达和挖掘。 其次，在信息检索a g e n t 中，研究了文本特征选取和特征匹配问题。系统由 检索a g e n t 根据用户模型在i n t e r n e t 上搜集文档和信息。分析、过滤a g e n t 对所搜 集到的网页进行分析，抽取文档特征，形成文档的结构化表示。另外，系统还可 以按照用户的要求，对其感兴趣的部分站点，按照用户设定的检索周期，自主地 从w w w 上检索信息，把符合用户兴趣的最新信息按照用户预定的方式及时提交给 用户通过系统的主动信息服务功能减少用户检索次数，是提高检索效率的一个 较好的解决方法。 再次，研究了学 - a g e n t 自适应地调整用户模型。学习a g e n t 的学习过程，既 是用户相关性反馈过程，也是用户兴趣挖掘过程系统通过记录用户浏览行为、 获取用户对文档的反馈，以及从网上搜集到的文档作为学习的“原始强化信号”， 从而实现自适应调整用户模型 最后，构建了一个基于智能a g e n t 的w e b 个性化信息检索系统。从总体上描述 了该模型框架的功能、工作流程，说明了各类a g e n t 在系统中的结构、安排与作 用，并对模型结构，算法进行了分析设计并通过该原型系统的实现与现有信息 山东大学硕士学位论文 m _ - _ _ _ _ - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ _ _ _ - - _ _ _ _ _ - _ _ _ _ - l _ _ - _ _ _ _ _ _ _ - - - - 山东人学硕十学位论文 _ _ _ 一i i _ _ _ _ 一 a b s t r a c t t r a d i t i o n a ls e a r c he n g i n ec a nn o tm e e tp e o p l e si n f o r m a t i o n n e e d s f a c i n gt h eo c e a no fi n f o r m a t i o no ni n t e r n e t ，p e o p l ea l w a y sg e tt o o m u c hi n f o r m a t i o nt os e l e c ta n dt od i g e s t ，s oi t sh a r df o rt h e mt of i n d t h en e c e s s a r yi n f o r m a t i o na n dk n o w l e d g e w e bm i n i n gi san e wt e c h n o l o g y a n di tc a nd i s c o v e rr e s o u r c e sa n dk n o w l e d g eq u i c k l ya n de f f i c i e n t l y ， t h e r e f o r e ，i tc a nc o m p e n s a t et h es h o r t c o m i n g so fs e a r c he n g i n e t h ea i mo ft h et h e s i si st oh e l pp e o p l ew h os e a r c ha n dm i n ed o m a i n i n f o r m a t i o no ni n t e r n e t i nv i e wo ft h eq u e s t i o nt h a te x i s t i n gs e a r c h e n g i n e sc a n n o te x p r e s sr e q u i r e m e n t so fu s e r se x a c t l ya n do u t p u tt o om a n y r e s u l t s ，b a s e do nt h ea n a l y s i so ft h eh i s t o r yo fi n t e r n e ta n di n t e r n e t i n f o r m a t i o nr e t r i e v a l ，t h e nas y s t e mo fi g e bp e r s o n a l i z e di n f o r m a t i o n r e t r i e v a lb a s e do ni n t e l l i g e n ta g e n ti sp r e s e n t e db yi n t e l l i g e n ta g e n t t e c h n o l o g y b yt h ed e s c r i p t i o no ft h ew e bi n f o r m a t i o nr e t r i e v a lw o r k f l o w u n d e rt h i ss y s t e m ，t h ep a p e rb r i e f l ye x p l a i n st h eo v e r a l lt h o u g h t t h e s y s t e ma l s od i s c u s s e si n i t i a l l ya b o ud e s i g n i n gs y s t e ma n db u i l d i n gm o d e l a r o u n dt h eb u i l d i n ga n ds o f t w a r ed e v e l o p m e n to ft h em o d e l ，t h em a i nw o r k a n di n n o v a t i o no ft h i st h e s i sa r el i s t e da st h ef o l l o w i n g ： f i r s t l y ，t h ep r e s e n t e dm o d e lh a sam u l t i a g e n ta r c h i t e c t u r ea n d o r i e n t st h ep r a c t i c a lu s e r i nt h em o d e ls y s t e m , u s e ra n dd o c u m e n t r e p r e s e n t a _ t i o n sa r ed e p i c t e d d o c u m e n t sa r et h eo b j e c t so fi n f o r m a t i o n p r o c e s sa n dt h ef o u n d a t i o no fd o c u m e n tm o d e li st h eb a s eo fi n f o r m a t i o n p r o c e s ss u c ha sf e a t u r ee x t r a c t i o n ，d o c u m e n tf i l t r a t i o na n ds oo n u s e r m o d e le m b o d i e su s e ri n t e r e s t sa n di n t e n t i o n i ti su s e dt oe x p r e s sa n d m i n i n gu s e ri n t e r e s t s s e c o n d l y ，i nt h ei n f o r m a t i o nr e t r i e v a la g e n t s ，ak e yp r o b l e mi sh o w t oe x t r a c tt e x tf e a t u r e sa n dh o wt od e a lw i t ht h eh i g hn u m b e ro ft h e f e a r t u r e s r e t r i e v i n g m o n i t o r i n ga g e n tu s e st h ef e a t u r ev e c t o rt os e a r c h i n f o r m a t i o na n dd o c u m e n to ni n t e r n e t a n a l y s i s f i l t r a t i n ga g e n te x t r a c t s 山东大学硕士学位论文 - m i m _ _ t h ed o c u m e n tf e a t u r et of o r m u l a t es t r u c t u r e dr e p r e s e n t a t i o no ft h e d o c u m e n t m o r e o v e r ，t h eu s e rc a np l o tt h er e t r i e v a li n t e r v a lt os o m es it e s o fi n t e r e s t i n g ，t h e nt h es y s t e mc a nr e t r i e v ei n f o r m a t i o ni n v o l u n t a r i l yo n i n t e r n e t t h en e w l yi n f o r m a t i o ni nl i n ew i t hu s e ri n t e r e s t i n gc a nt i m e l y p u tu pt ou s e r sa c c o r d i n gt ou s e r ss c h e d u l e t h ef u n c t i o no fi n v o l u n t a r y s e r v i c eo ft h es y s t e mc a nr e d u c e n u m b e r o fu s e r sr e t r i e v a l i ti sab e t t e r m e t h o do fi m p r o v er e t r i e v a le f f i c i e n c y t h i r d l y ，l e a n i n ga g e n ta d j u s t st h eu s e rm o d e la d a p t i v e l yb y r e i n f o r c e m e n tl e a r n i n ga n dg e n e t i ca l g o r i t h m t h el e a r n i n gp r o c e s so ft h e a g e n ti st h ep r o c e s so fu s e rf e e d b a c k ，a n da l s ot h em i n i n gp r o c e s so fu s e r i n t e r e s t s t h es y s t e ma d o p t sb o t ht h ee x p l i c i ta n di m p l i c i tu s e rf e e d b a c k m e t h o d s r e c o r d i n gu s e rb r o w s i n gb e h a v i o r s ，o b t a i n i n gu s e re v a l u a t i o no n d o c u m e n t sa n dt h ed o c u m e n t sr e t r i e v e df o r mi n t e r n e t ，t h et h r e ef a c t o r s a r et h eo r i g i n a lr e i n f o r c e m e n ts i g n a l t h es i g n a li ss p r e a dt ou s e rm o d e l b yt h e i ri n t e r a c t i o na n dt h e na d a p t i v e l ya d j u s t st h es y s t e m f i n a l l y ，t h ep a p e rp u t sf o r w a r daw e bp e r s o n a l i z e di n f o r m a t i o n r r e t r i e v a ls y s t e mb a s e do ni n t e l l i g e n ta g e n t t h ep a p e rd e s c r i p t st h e f u n c t i o na n df l o w w o r ko ft h em o d e lf r a m e w o r ko no v e r a l l ，i n c l u d i n g a s s e s s i n gt h ea r c h i t e c t u r e ，t h ea r r a n g m e n ta n dt h ef u n c t i o no fa l lk i n d s o fa g e n t si nt h es y s t e m t h em o d e la r c h i t e c t u r ea n da l g o r i t h m sa r ea l s o a n a l y z e da n dd e s i g n e d a n dt h ee m p l e m e n t a t i o no ft h i sm o d e ls y s t e m i n s t a n c ei l l u s t r a t e sa n dv e r i f i e st h es u p e r i o r i t yc o m p a r i n gt h e i n f o r m a t i o nr e t r i e v a ls y s t e mc u r r e n t l y k e yw o r d s ：w e bi n f o r m a t i o nm i n i n g = i n t e lii g e n ta g e n t ；p e r s o n a li z e d i n f o r m a t i o nr e t r i e v a i ；s e a r c he n g i n e ；u s e r bp r o f il em i n n i n g ： 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅：本 人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文 ( 保密论文在解密后应遵守此规定) 论文作者躲掣导獬：缉 山东大学硕士学位论文 第一章绪论 1 1 论文研究背景 i n t e r n e t 是一个信息的海洋，有人说它是世界上最大的超级市场，这句话很 能形象地说明i n t e r n e t 网上信息资源的特点种类繁多而内容庞杂。美国时 代周刊曾这样评论i n t e r n e t ：“与其说把新用户带入了信息世界，不如说是把 他们领进了茫茫无际的大海。”网上信息归纳起来主要有这样一些特点： 1 ) 信息内容丰富 既有学术、教育、产业、经济、文化和商业等方面的信息，也有体育、娱乐、 旅游、消遣和奇闻轶事一类的信息。 2 ) 时效性强 有网上出版物，如网上报纸和期刊，其中很多免费向用户提供；动态信息，如政 府机构发布的消息、政策法规、会议消息、论文集、研究成果、项目进展报告、 产品目录、出版目录、广告等；有的著名数据库亦在网上设置网页，并提供一定 时间的免费检索，如：m e d i n ee i v i l l a g e 、美国专利q p a t u s 等等。 这几个特点已成为制约i n t e r n e t 信息服务进一步发展的瓶颈随着 i n t e r n e t 上信息资源、站点和用户数量的进一步增长，网络上的资源管理开趋 复杂，信息服务的主动化、个性化和智能化己成为i n t e r n e t 亟待解决的问题之 一 1 2 论文研究意义 目前，亟对i n t e r n e t 上的信息海洋，人们常常会陷入两种窘迫的境地：一是 收到太多的信息无从选择和消化，即淹没在繁杂的信息中：另一方面是信息迷失， 入们难于找到自己真正所需的信息。如何快速、准确地从浩瀚的信息资源中找到 所需信息已经成为困扰网络用户的一大难题。解决这个问题的一条途径是采用基 于智能a g e n t 的w e b 挖掘技术，从而实现个性化网络信息服务 实质上个性化网络信息服务，既是一种个性化服务，又是一种网络信息服务。 有效的信息服务一定是针对具体用户个人的背景、环境、知识、兴趣爱好、信息 需求等特征来实施的。因此，个性化网络信息服务最根本的应该是能够满足用户 个体信息需求的一种服务，即根据用户提出的明确要求提供信息服务，或通过对 山东大学硕士学位论文 - _ _ _ _ - - - _ _ _ - _ _ _ _ _ _ _ 一i mi - - _ - - - - - - 一 用户个性、使用习惯、每一次访问记录等数据的审查、过滤、分析，从而主动地 向用户提供其可能需要的信息服务。个性化网络信息服务的目标就是在充分利用 现有各类资源的基础上，通过各种手段采集大量的信息资源，运用新技术组合， 以用户的需求为服务内容，定时或不定时向用户发送感兴趣的信息。在网络信息 庞杂、用户对信息服务要求不断提高的环境下，个性化网络信息服务已经成为网 络服务发展的必然。 w e b 挖掘涉及到人工智能、机器学习、神经网络、自然语言理解、信息检索 技术、知识发现、数据挖掘等技术，是一个多学科交叉研究领域研究基于智能 a g e n t 豹w e b 挖掘技术，对网络信息服务主动化和智能化进程意义重大 w e b 挖掘技术和智能a g e n t 技术可以把网上信息推送与信息拉取技术相结合， 从而可以提高i n t e r n e t 信息服务的智能水平，为广大用户提供高效率的网络信息 服务，发现有用的知识。这是由于：其一，智能a g e n t 具有多种优良品质，利用机 器学习方法，可以识别和预测各种用户的兴趣或偏好，从而有针对性地、及时地 向用户主动推送所需信息，以满足不同用户的个性化需求其二，将智能a g e n t 技术应用于i n t e r n e t 智能信息检索，可提高搜索引擎的快速性和准确度，从而用 户可以更及时地拉取所需的最新动态信息。其三，通过w e b 挖掘技术和智能a g e n t 技术将信息推送与信息拉取相结合，可取长补短，既可及时地、主动地将最新信 息推送给用户，又可有针对性、选择性地满足用户个性化需求其四，采用w e b 挖掘的方法和技术，可从所“推送一拉取”的信息中提取有用知识，发现隐藏在 大量数据中的内在规律。 因此，对w e b 挖掘技术和基于智能a g e n t 技术的研究对网络信息服务主动化和 智能化进程意义重大 1 3 论文研究内容 本文分析了当前w e b 信息挖掘方面的研究概况和最新进展，讨论 a g e n t 相关 概念以及智能a g e n t 技术，在这些研究的基础上，综合信息检索、知识表示、数 据挖掘等多方面的技术，围绕着向用户提供个性化的信息和知识这一问题，针对 信息服务的个性化、智能化和主动性，根据w e b 智能信息检索的功能要求，提出 了一个基于智能a g e n t 的w e b 个性化信息挖掘系统模型。然后，详细地分析和讨论 了模型中各类a g e n t 的功能、算法设计和实现方案，最后，在系统实现中着重考虑 山东大学硕士学位论文 了该系统核心部分的算法、结构设计和实现。力求从理论和实践两方面阐述智能 a g e n t 在w e b 个性化信息检索中的可行性和优越性。本文的主要工作和创新之处 有： ( 1 ) 本文比较深入地分析和研究了w e b 挖掘的当前国际研究的最新进展，讨论了 w e b 挖掘的分类和主要的w e b 挖掘方法，并详细地介绍了w e b 文本挖掘技术。w e b 文本挖掘技术是本文研究的一个重点，主要包括w e b 文本特征的表示、w e b 文本特 征子集的提取，高维特征的处理等文本挖掘关键步骤。 ( 2 ) 本文详细地分析和讨论了智能, a g e n t 技术a g e n t 技术强调智能系统的自主 性、社会性和适应性，强调系统的开放性和与环境的交互行为，而不象传统的人 工智能方法那样注重系统所具有的知识。a g e n t 适应性的重要实现方式就是学习 强化学习方法基于和环境的交互，是一种目标驱动的学习方法。本文的学习a g e n t 通过采用强化学习的方式自适应调整用户模型。 ( 3 ) 对w e b 的智能化、个性化的信息挖掘服务问题，提出了一种基于智能a g e n t 的w e b 个性化信息挖掘系统模型。在系统模型中同时表达了用户、文档两种模型。 文档的表示是信息处理的基础，该系统基于向量空间模型，由于信息服务是 针对特定的用户，因而在考虑文档表示的时候，除了体现文档中的词频外，也要 体现文档与用户主题的隶属度。 由于用户的兴趣还直接表现于相关的文档，因而用户模型还需要反应用户对 文档的关注程度。同样用户模型的状态也应随着信息服务的进行雨逐步完善并随 用户关注点的转移而自动改变。 同时，模型可以按照用户的要求，对其感兴趣的部分站点，按照用户设定的 检索周期，自主地从删w 上检索信息，把符合用户兴趣的最新信息按照用户预定 的方式及时提交给用户通过系统的主动信息服务功能减少用户检索次数，是提 高检索效率的一个较好的解决方法 ( 4 ) 本文详细地讨论了检索a g e n t 的工作原理和设计方法。该a g e n t 包含个元 搜索引擎，具有如下优点：第一，a g e n t 可以一次调用多个搜索引擎进行并发查询， 因此往往能够获得较高的铝回率第二，由于a g e n t 利用其他搜索引擎的搜索结 果，不需要进行网页的索引工作，不需要维护庞大的网页索引数据库，大大降低 了工作的复杂度。实验结果表明：该a g e n t 的工作机制及其采用的相关策略是可行 山东大学硕士学位论文 的，具有自动化程度高、易维护、实用性强等特点检索a g e n t 设计和实现是本 文工作中有新意的个地方 ( 5 ) 本文深入研究 a g e n t 的学习方法。本文采用显式相关性反馈和隐式相关性 反馈相结合的用户相关性反愤方法，通过用户相关性反馈信息，学 - a g e n t 利用 机器学习技术自适应地调整用户模型，对用户兴趣进行学习和挖掘，从而使得用 户模型更加体现用户兴趣，提高网上信息挖掘系统服务的主动性、智能性和个性 化。 ( 6 ) 面商3 w e b 个性化信息检索系统i w r s 的设计和软件实现。提出了应用各种新技 术的方法和实现要点，该系统弥补搜索引擎及检索工具中查全率有余、查准率不 足的弊端，智能地理解用户的信息需求，提高用户的检索效率，从而实现真正意 义上的个性化服务。其中包括一些主要步骤、关键问题处理和主要算法等。 4 山东大学硕十学位论文 第二章w e b 挖掘理论基础 2 1 数据挖掘 2 1 1 数据挖掘技术产生的背景 当前数据库技术迅速发展，使得信息存储能力越来越强。信息以指数级地增 长，而隐藏在其中的知识并没有被很好的挖掘和利用，这种突出的矛盾称为“数 据爆炸而知识贫乏”。 计算机的一个领域一机器学习，主要的研究问题在于如何通过大量的训练事 倒进行学习，产生知识。二十世纪9 0 年代机器学习成为研究的热点之一 将数据库和机器学习结合起来，就产生了海量数据中的知识发现一一 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 ，简称k d d ，这就是数据挖掘这个新兴的领域。 当前数据挖掘技术也应用至l j w e b 上，称为w e b 挖掘。 2 1 2 数据挖掘概念和过程 数据挖掘“瑚( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、 随机的数据集中，提取有效的、新颖的、潜在有用的、以及最终可理解的模式的 非平凡过程。它是- f 7 涉及面很广的交叉学科，包括机器学习、数理统计、神经 网络、数据库、模式识别、粗糙集、模糊数学等相关技术。数据挖掘的目的是提 高市场决策能力；检测异常模式；在过去的经验基础上预言未来趋势等。这些知 识和规则是隐含的、先前未知的、对决策有潜在价值的有用信息。通过数据挖掘， 有价值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来， 为决策提供依据，从而使数据库作为一个丰富可靠的资源，为知识归纳服务。 在上面的定义中，涉及几个需要进一步解释的概念：“数据集”、“模式”， “过程”、“有效性”、“新颖性”，“潜在有用性”和。最终可理解性” 。数据集”是一组事实f ( 如关系数据库中的记录) “模式”是一个用语言l 来表 示的一个表达式e ，它可用来描述数据集f 的某个子集f 。e 作为一个模式要求它 比对数据子集f e 的枚举要简单( 所用的描述信息量要少) “过程”在数据挖掘中 通常指多个环节，涉及数据准备、模式搜索、知识评价，以及反复修改求精。该 过程要求是“非平凡的“，意思是要有一定程度的智能性，自动性( 仅仅给出所 有数据的总和不能算作是一个发现过程) “有效性”是指发现的模式对于新的 山东大学硕士学位论文 数据仍保持有一定的可信度“新颖性”要求发现的模式应该是新的。“潜在有 用性”是指发现的知识将来有实际效用，如用于决策支持系统里可提高经济效益。 “最终可理解性”要求发现的模式能被用户理解，目前它主要是体现在简洁性上。 有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之为“兴趣性” 数据挖掘可分为三部曲：数据准备( d a t ap r e p a r a t i o n ) 、数据挖掘，以及结 果的解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 数据准备又可以分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 数据选取的目标是 确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ，它是根据用户的需要从 原始数据库中抽取的一组相关数据。数据预处理一般可能包括消除噪声、推导计 算缺值数据、消除重复记录以及完成数据类型转换( 如把离散型数据转换为连续 型数据，以便于神经网络归纳) 等数据变换的主要目的是消除数据维数或降维 ( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减少数据挖掘 时要考虑的特征或变量个数。 数据挖掘阶段首先要确定挖掘的任务是什么，如数据分类、聚类、关联规则、 序列模式和预测等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。同样 的任务可以用不同的算法来实现，选择发现算法有两个考虑因素：一是不同的数 据有不同的特点，二是用户或实际运行系统的要求 完成了上述准备工作后，就可以实施数据挖掘操作了数据挖掘算法是k d d 的核心，要获得好的挖掘效果，必须对各种挖掘算法的要求或假设有充分的理解 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余或无 关的模式，这时需要将其剔除；也有可能模式不能满足用户的要求，这时则需要 整个发现工作退回到前面的阶段。另外，挖掘结果由于最终是面向用户的，因此 可能要对发现的模式可视化，或者把结果转换为用户易懂的另一种表示。 数掘挖掘的研究有很多的研究难题，如数据的巨量性、动态性、噪声性、缺 值和稀疏性，发现摸式的可理解性、兴趣或价值性，应用系统的集成，用户的交 互操作，复杂数据库的处理等等。 2 1 3 数据挖掘的主要技术 数掘挖掘有多种技术，主要包括以下几种： 山东大学硕士学位论文 关联规则 关联规则是用来描述在给定的事务集中，频繁出现的项目集的规则。关联规 则是k d d 研究中的一个重要分支。自从r a g r a w a l 等人在s i g m o d 9 3 上第一次提出这 个问题以来，关联规则一直是众多学者的研究热点。现己发表的研究论文包括确 定性关联规则的挖掘、量化关联规则的挖掘、增量式关联规则的挖掘、模糊关联 规则的挖掘、广义关联规则的挖掘等。著名的关联规则发现算法是a p r i o r i “1 ， 该算法首先识别所有的频繁项目集，这是算法的核心为了改善算法的性能， a g r a w a l 等人在v l d b 9 4 上又提出了快速算法。 分类 分类属于有导师学习，即利用给定的训练数据集建立分类模型，再通过分类 模型对新的数据进行分类的工程。主要的分类方法有决策树嘲、贝叶斯、神经网 络和粗糙集等。 聚类 聚类也可以称为无监督分类( 不需要训练集) 聚类，事先并不知道训练数据 的类标签，而是本着“最大化类内部数据相似度，而最小化类间数据相似度”的 原则，产生新的类别聚类方法包括统计方法m 、机器学习方法嘲和空间数据库 方法m 等。 可视化 可视化就是把数据、信息和知识转化为可视表示形式的过程。可视化技术为 人类与计算机之间提供了一个接口使用可视化界面，可以快速高效地与大量的 数据交互，以发现其中隐藏的特征、关系、模式和趋势等。a n d r e w 等从认知的角 度讨论了可视化在大规模高维数据集中挖掘的作用“”，l i 采用三维投影技术可视 化关系数据库1 2 2w e b 挖掘 2 2 1w e b 挖掘基本概念 w e b 挖掘就是从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用模式和隐藏的 信息“锄小“1 w e b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行挖掘， 确定权威w e b 页面的信息。w e b 文档分类，w e bl o g 挖掘，智能查询等。w e b 挖掘可 以分为w e b p q 容挖掘、w e b 结构挖掘和w e b r 志挖掘。 山东大学硕士学位论文 2 2 2w e b 挖掘研究现状 w w w 是众多情报类型中的一种，并且具有极大的特殊性。它的信息是分- 匆在 全球范围内，并且随时可变。这些分布在各地的信息允许任何人在任何地点任何 时间传播和获耿信息。传统的搜索引擎根本不评估站点的内容，而只是机械地识 n w e b 设计者提供的关键字，即使是最优秀的搜索引擎也需要用户亲自访问到不 同的站点并对信息加以验证另外不能针对特定的用户给出特殊的服务，因为每 个人感兴趣的东西是不一样的，因此不具有个性化。 解决这些问题的一个途径，就是将数据挖掘技术和w e b 结合起来，进行w e b 挖 掘。w e b 挖掘可以广义地定义为从w w w 中发现和分析有用的信息。w e b 为数据挖掘 提供了丰富的资源，但是w e b 挖掘比传统的数据挖掘具有更大的难度w e b 挖掘可 以在很多方面发挥作用，一般地，w e b 挖掘可分为三类：w e b 内容挖掘，w e b 结构挖 掘和w e b 使用记录的挖掘，w e b 使用记录的挖掘也称w e b 日志挖掘。图2 1 给出了 w e b 挖掘的分类图。 图2 iw e b 挖掘分类 2 2 3w e b 内容挖掘“”“町“” w e b 内容挖掘是自动地从数以百万计的w e b 站点和在线数据库中搜索和获取 信息和资料的过程。w e b 内容挖掘有两种策略，分为直接挖掘文档内容和在其 它检索工具搜索的基础上进行改进。w e b 内容挖掘根据其所处理的数据对象的 不同可分为文本挖掘和多媒体挖掘。文本作为信息资源的一个重要形式，据统 计在联机存储的信息中，8 0 以上的信息以文本的形式存在，而在w e b 上可用于 分析处理的信息之中有9 9 是以文本的形式存在，所以文本挖掘逐渐成为人们 山东人学硕士学位论文 研究的新课题。文本挖掘也是本文的主要研究对象。 由于w e bl - 的信息在很大程度上是文本信息，因此本文着重针对基于w e b 的 文本挖掘展开研究和探讨。文本挖掘最重要的步骤就是文本的特征表示方法和 特征子集的选取方法。 2 2 3 1 文本的特征表示 与数据库中的结构化数据相比，w e b 文档具有有限的结构，或者根本就没有 结构。半结构化是w e b 上数据的最大特点，也形成t w e b 文本挖掘的特色。文本 信息源的这些特征使得现有的数据挖掘技术无法直接应用于其上。需要对文本 进行预处理，抽取其特征并用结构化的形式保存，作为文档的中间表示形式。 文本的特征指的是关于文本的元数据，分为描述性特征和语义性特征。而文 本的内容特征的表示则相对复杂一些特征表示是指以一定的特征项( 如词条) 来代表文档信息，特征表示模型有多种，常用的有布尔型、向量空间型、概率 型等。近年来应用较多且效果较好的特征表示法是向量空间模型( v e c t o rs p a c e m o d e l ，v s m ) 法。在该模型中，将文本文档看成是一组词条( t l ，t 2 ，t n ) 构成，对于每一词条t i ，都根据其在文档中的重要程度赋予一定的权值w i ，可 以将其看成一个n 维坐标系，w 1 ，w 2 ，w n 为对应的坐标值，因此每一篇文档 都可以映射为由一组词条矢量组成的向量空间中的一点，对于所有待挖掘的文 档都用词条特征矢量( ( t l ，w 1 ) ；( t 2 ，w 2 ) ；( t n ，w n ) ) 表示。这种向量空 间模型的表示方法优点在于将非结构化的文本表示为向量形式，使得各种数学 处理成为可能。 2 2 3 2 文本的特征子集的选取 特征选取算法的优劣直接影响到本模型的效果一个有效的特征项集，必 须具有彻底性和专门性。其中彻底性指文本所讨论的内容被特征词覆盖的程 度；专门性指特征词必须能反映文本的具体内容，而不是泛泛而谈。为了满足 彻底性要求，对文本进行结构和内容分析，以保证对文本各部分内容的最大限 度的覆盖。为了满足专门性，需要消除停用词，选择具有实际意义的名词及其 短语，特别要注意选取面向内容的词汇 目自u 对w w w 文档特征所采用的特征子集选取算法一般是构造一个评价函数， 对特征集中的每一个特征进行独立的评估，这样每个特征都获得一个评估分 9 山东大学硕士学位论文 - _ _ _ _ - - - _ _ _ _ - _ - _ _ _ - _ - _ _ _ _ _ _ _ - _ _ - - _ _ _ - m l _ _ _ _ _ _ _ l _ _ _ - _ _ _ - - _ - _ _ _ _ _ _ _ 一 ( 也称为权值) ，然后对所有的特征按照其评估分的大小进行排序，选取预定数 目的最佳特征作为结果的特征子集所以，选取多少个最佳特征以及采用什么 评价函数都要针对一个具体的问题通过实验来决定特征选择主要用于排除那 些被认为无关或关联性不大的特征( 即术语) ，并自动将那些低频的特征用正交 方法合并成高频特征 一般采用的评估函数有信息增益( i n f o r m a t i o n g a i n ) ，期望交叉熵( e x p e c t e d c r o s se n t r o p y ) ，互信息( m u t u a li n f o m a t i o n ) 、文本证据权( t h ew e i g h to f e v i d e n c ef o rt e x t ) 、几率比( o d d sr a t i o ) ，词频( w o r df r e q u e n c y ) 等。这些评 估函数大致可分为两类：基于统计分析的方法和基于机器学习的方法。 信息增益法是一种在机器学习领域应用较为广泛的特征选择方法。它从信息 论角度出发，根据各特征取值情况来划分学习样本空间时，所获信息增益的多寡 来选择相应的特征，特征t 的信息增益g a i n ( t ) 计算公式如下： g a i r i ( t ) = 一：。p ( c t ) 1 0 9 p ( c i ) + p ( t ) ：。p z ( c i f t ) i 。g p ( c , f t ) ) + p ( i ) ：p ( c 。 i ) l o g p ( c p 其中m 为不同类型的w e b 网页数；c i 为某一类w e b 网页的集合：i 表示特征t 不 出现。 对于训练文档集，计算每一个特征的信息增益，对于信息增益低于给定阂值 的术语，将从特征空问把其排除。 2 2 3 3w e b 网页的特征提取 w e b 网页特征表示与普通文本有所不同，所以w 曲网页的特征提取有其特殊 性。w e b 网页是采用超文本标记语言编写的半结构化的文本文件，其所含信息体 现在三个部分：网页正文( 标题中的文字也算作正文中的内容) 、网页所含的超 文本标记、网页间的超链接。 图2 2 网页信息的构成 0 山尔人学硕十学竹论文 对网页进行特征提取首先要对超文本进行网页过滤，过滤处理后分别获得网 页正文、超文本标记和超链接信息，过滤后的网页正文与普通文档基本一样。对 它的处理即可转化为中文文档的处理。 1 标签信息 标签的作用是提供了有关文档结构的信息( 如标题、头部及段落等) 和格式 ( 如粗体和斜体等) 。显而易见，利用h t m l 文档的结构，人们能够很容易地知道 某个检索字的具体位置及格式。 h t m l 中的标签很多，与字符属性及文章标题相关的标签有：t i t l e ，h 1 - h 6 ，p ， s t r o n g ，b ，跏，i ，u ，d l ，o l ，u l 。它们标记的文字往往对揭示网页的主体内 容具有更加重要的作用。所以在网页特征提取时，统计这些标记的特征词条和次 数，为它们赋予较大的权值对标记信息的统计，既有效利用了标记对关键词重 要程度的标识作用，又对网页的理解增加了准确的尺度。表2 - 1 总结了这些h t m l 标记。 表2 1 对特征项有所帮助的唧l 标记 h t m l 标记解释例子 页面的标题( t i t l e w i n 2 0 0 0s e r v e r 小标题 i n t r o d u c t i o n 段落 w i n 2 0 0 0i s 表格 1 9 9 9 2 0 0 0 租体字 t h i si sas t r o n gl i n e 字体 t h i si sa m a i np o i n t 在h t m l 中还有一个重要的标记 ，它位于网页源码开始部分，在 和 之间( 也是 标题定义所在的位置) ，是一组定义网页属性的t h m l 标签。网页的作者可以在 中加入关于网页内容的关键词，以便搜索引擎将它准确分类。网页简述是m e t a 标签的第二种标签代码，它是对网页的描述，用以概括网站，比标题稍微展开一 点点， 。但目前的情 山东大学硕士学位论文 况是大部分网页的m e t a 处于空白状态，或网页的作者将它作为一种欺骗手段，因 此没有充分发挥它的价值 2 超链接信息 两页的超链接中所包含的信息有： ( 1 ) u r l 字符串中的字符信息； ( 2 ) 链接文本( 链接标记 和( a 阃的文字信息) ； ( 3 ) 链接所引入的超文本文件内容间的相关性 中文域名的应用，使得许多u r l 字符串中又包含了有一定意义的中文字符信 息。这些信息与网页的内容间虽有一定的联系，但规律性不强。且需要建立庞大 完备的知识库，提取难度较大 超链接包括同一网页内部的相互链接( 用l i n k 标记) ，和网页间的相互链接 ( f f i ah r e f