（计算机软件与理论专业论文）web挖掘在教学资源搜索引擎中的应用研究.pdf

摘要 本文针对中小学信息化基础教育的需求和特点，从查询结果个性化的角度出发，对 教学资源的个性化搜索引擎进行了一个特色规划。随着用户群和教学资源库的不断壮 大，如何人性化的理解用户的查询需求，尽可能准确地返回查询请求内涵和外延的结果； 如何在用户查询条件不十分确定的情况下将与其查询条件类似的页面以聚类的方式返 回给用户，是现有条件下搜索引擎研究应该努力着手解决的问题。 本文主要研究了w e b 挖掘在教学资源搜索引擎中的应用，w e b 挖掘分为w e b 内容挖 掘，w e b 结构挖掘和w e b 使用挖掘。作者主要对其中的前两项内容进行了研究，结构挖 掘是从w 聊的组织结构、w e b 文档结构和链接关系中推导知识。就搜索引擎技术领域来 说，可以通过分析一个网页或整个网站链接和被链接的数量、对象，建立w e b 自身的链 接结构模式，通过分析和研究基于链接结构的搜索结果排名算法，可以指导网站链接结 构优化，有组织，有规划地提高网页在搜索结果中的排名，避免盲目处理造成的混乱结 果。本文主要针对目前主流的p a g e r a n k 算法，集中研究了该算法的计算方法、网页链 接结构对p a g e r a n k 值的影响，并分析该算法在独立网站、包含入站链接和出站链接等 几种模型下的效果，提出了相应的优化策略。最后通过总结p a g e r a n k 的优缺点，针对 其中的主题漂移现象给出了改进后的p a g e r a n k 算法，并对其进行了验证。 在w e b 内容挖掘方面，作者所做的工作是研究如何利用w e b 挖掘技术，并结合现有 的聚类技术，实现对w e b 文本数据的高准确率的分类和聚类。本论文提出通过w e b 内容 挖掘和结构挖掘，提取网页在整个网站中的层次类别信息，通过这些层次类别信息对网 页进行聚类。作者尝试引入后缀树( s u f f i xt r e ec l u s t e r i n g ) 的概念对页面进行动态 聚类，这是一种新的聚类算法。为一种新颖的、增量式的线性时间运算方法，该算法生 成的数据结构非常紧凑，节约了大量的存储空间。非常适合于解决基本的字符串问题， 这种方法的提出，为今后中文文本挖掘领域的研究提供了一个新的思路。 关键字：p a g e r a n k 搜索引擎w e b 挖掘文本分类 a b s t r a c t i nt h i sp a p e r ，w ee x p l o r eas p e c i a lp l a na b o u tac h i n e s ep e r s o n a l i z e de d u c a t i o nr e s o u r c e s s e a r c he n g i n ef a c i n gt h en e e dp r o p e r t yo fh i 曲e l e m e n t a r ye d u c a t i o n w i t ht h ei n c r e a s i n g d e v e l o p m e n to ft h eu s e r sa n dt h et e a c h i n gr e s o u r c e sd a t a b a s e ，i tw i l lb e c o m ev e r yi m p o r t a n t a b o u th o wt ou n d e r s t a n dt h eq u e r yn e e do f t h eu s e rc o n s i d e r a t e l ya n dr e t u r nt h er e s u l t sw h i c h c a nr e f l e c tt h ec o n n o t a t i o na n dt h ee x t e n s i o no ft h eq u e r yn e e d ，h o wt or e t u r na n di n q u i r e a b o u tt h er e s u l to f a s k i n gf o ri n t e n s i o na n de p i t a x ya sa c c u r a t ea sp o s s i b l e ；r e t u r nt on s e r sb y w a yo fc l u s t e ri np a g eh o wt oi n q u i r ea b o u tt h ec o n d i t i o nw i t hi ti nas i t u a t i o nt h a tu s e r s i n q u i r ea b o u tt h ec o n d i t i o na n dd o e sn o tc o n f i r mv e r ym u c ht os i m i l a rt o ，i ti st h es e a r c h e n g i n eu n d e rt h ee x i s t i n gc o n d i t i o nt h a ts t u d i e st h ep r o b l e mt h a ts h o u l db es e ta b o u ts o l v i n g h a r d t 1 1 i sp a p e rm a i n l yf i n i s h e dt h er e s e a r c ha b o u tt h ew e bd a t am i n i n gw h i c hi su s e di n s e a r c he n g i n e t h e r ea r et h r e em a i nc o n t e n t so fw e bd a t am i n i n g ：c o n t e n tm i n i n g s t r u c t u r e m i n i n ga n du s a g em i n i n g w e bs t r u c t u r em i n i n gi st od e d u c es o m ek i n do f k n o w l e d g ef r o m s t r u c t u r e so f w w w , w c bd o c u m e n t sa n dh y p e r l i n k s a sf o rs e a r c he n g i n e w ec a l le s t a b l i s h al i n k i n gs t r u c t u r ep a t t e mb ya n a l y z i n gq u a n t i t ya n dt a r g e t so faw e bp a g eo rw e b s i t e s i n l i n k sa n do u t - l i n k s b ys t u d y i n gs u c ha l g o r i t h m sb a s e do nh y p e r l i n ka sp a g e r a n k ，w ec a n g u i d eo u rl i n k i n go p t i m i z a t i o na n dc o n t i n u o u s l yi m p r o v et h ew e b s i t e sr a n k , a v o i dd e a l i n g w i t ht h ec o n f u s e dr e s u l tc a u s e db l i n d l y t i l i sp a p e rh a sc o n c e n t r a t e do ns t u d y i n gt h e c o m p u t i n gt e c h n o l o g y ，w e b p a g eo ft h i sa l g o r i t h ma n dc h a i n i n gt h ei m p a c to np a g e r a n k v a l u eo f t h es t r u c t u r et op a g e r a n ka l g o r i t h mo f t h em a i n s t r e a ma tp r e s e n tm a i n l y ，a n da n a l y s e i ni n d e p e n d e n tw e b s i t e s ，r e s u l ti n c l u d i n gi n b o u n dc h a i n i n ga n ds e t t i n go f fu n d e rs e v e r a l k i n d so fm o d e l s ，s u c ha sc h a i n i n g ，e t c o fa l g o r i t h m ，h a v ep u tf o r w a r dt h ec o r r e s p o n d i n g o p t i m i z a t i o nt a c t i c s p a s st h ep l u s e sa n dm i n u s e so fs u m m a r i z i n gp a g e r a n kf i n a l l y ，d r i f t a b o u tt ot h et h e m ea m o n gt h e mt h ep h e n o m e n o np r o v i d ep a g e r a n ka l g o r i t h ma f t e ri m p r o v i n g ， a n dh a sp r o v e dt oi t w h e nm e n t i o n e dc o n t e n tm i n i n g ，t h ew o r kt h a tt h ea u t h o rd o e si st os t u d yb o wt ou t i l i z e w e bt oe x c a v a t et e c h n o l o g y ，a n dc o m b i n ee x i s t i n gc l u s t e rt e c h n o l o g y ，r e a l i z et h e c l a s s i f i c a t i o na n dc l u s t e ro ft h eh i g hr a t eo fa c c u r a c yt ow e bt e x td a t a t b i st h e s i sp r o p o s e s e x c a v a t i n gt h r o u g hw e bc o n t e n te x c a v a t i n ga n ds t r u c t u r e d r a wt h el e v e lc l a s s i f i c a t i o n i n f o r m a t i o no fw e b p a g e si nt h ew h o l ew e b s i t e ，c a r r yo nt h ec l u s t e rt ot h ew e b p a g et h r o u g h t h e s el e v e lc l a s s i f i c a t i o ni n f o r m a t i o n t h ea u t h o rt r i e st oi n t r o d u c et h ec o n c e p to ft h es u f f i x t r e e ( s u f f i xt r e ec l u s t e r i n g ) a n dc a r r yo nt h ed y n a m i cc l u s t e rt ot h ep a g e ，t h i si sak i n do f n e wc l u s t e ra l g o r i t h m f o rt h el i n e a rt i m eo p e r a t i o nm e t h o d so fak i n do fn o v e lo n e ， i n c r e m e n tt y p e ，t h ed a t as n u c t i i r et h a tt h i s a l g o r i t h mp r o d u c e si sv e r yc o m p a c t h a v e e c o n o m i z e da l a r g en u m b e ro fm e m o r ys p a c e s b a s i co n eb u n c ho f p r o b l e m so fc h a r a c t e rt h a t s u i t e dt os o l v i n gv e r ym u c h ，t h ep r o p o s i t i o no ft i f f sm e t h o d ，h a v eo f f e r e dan e w t h i n k i n gf o r t h er e s e a r c ht h a tt h ec h i n e s et e x te x c a v a t e dt h ef i e l di nt h ef u t u r e k e yw o r d ：p a g e r a n k ，s e a r c he n g i n e ，w e bd a t a m i n i n g ，t e x tc l a s s i f i c a t i o n i l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：李钆日期门车6 日1 日 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定， 即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：盟 日期：! 丝i 旦l 目 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名：壁! 墨查 日期：妇垒旦i 旦 电话： 邮编： 第一章引言 1 1 课题研究背景及现实意义 1 1 1 数据的海量性 信息的生产、传播、搜集与查询是人类最基本的活动之一，随着计算机与信息技术 的发展，有了信息检索学科领域，有了关于图书或文献的全文检索系统，使得我们能够 很方便的在“关键词”粒度上得到相关的信息。 1 9 9 4 年左右，万维网( 简记为w w w ) 出现，它的开放性和其上信息广泛的可访问性 极大地鼓励了人们创作的积极性。作为一个信息源，w e b 和上述全文检索系统的工作对 象相比，具有许多不同的特征，它们给信息检索领域带来了新的发展机遇和技术挑战。 在短短的1 0 年左右时间，人类至少生产了4 0 亿网页 g o o g l e ，2 0 0 4 ，而人类有文字上万 年以来产生了大约1 亿本书；中国网上到2 0 0 4 年初大致有了约3 亿网页 天网，2 0 0 4 ， 而中华民族有史以来出版的书籍大约不过2 7 5 万种。研究表明，2 0 0 0 年，i n t e r n e t 上平均每天增加7 ，3 0 0 ，0 0 0 个网页，对应约i o o g 的数据量；2 0 0 0 年至2 0 0 2 年的2 年里， 互联网上的数据量至少翻了3 倍，2 0 0 2 年已经达到9 2 ，0 1 7 t ，其中表层网络( s u r f a c e w e b ) 占1 6 7 t ( 表层网络指所有静态网页构成的网络，相应地动态生成的网页构成的网络称为 深层网络) 。目前，全球最大搜索引擎g o o g l e 索引的网页数量为4 2 8 亿张，而据调查 显示，没有一个搜索引擎的网页索引超过总网页的六分之一。从如此海量的数据中快速 获取真正需要的数据信息变得越来越富有挑战性，人们迫切需要工具来帮助他们完成这 一点，而搜索系统正是这样一种工具。g o o g l e 、a l t a v i s t a 、i n f o s e e k 、y a h o o 、s o h u 、 天网等是其中的代表。这些搜索引擎给用户提供了极大的方便。“ 1 1 2 目前搜索引擎的局限 面对互联网上的海量信息，搜索引擎为人们提供了检索w e b 上相关信息的方法，搜 索引擎对w e b 上的文档进行索引并进行分类，为人们提供一个w e b 内容的层次化的目录 结构，有的搜索引擎对w e b 上的页面进行全文索引，提供基于关键词的检索。 目前的基于传统信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 方法的搜索引擎大部分使 用的是基于文档内容的词频统计，即t f i d f 方法的索引方式。这种基于文档关键词的检 索手段随着w e b 上数据量的迅速增加而越来不适应人们的要求，它的主要缺陷有： 1 返回信息过量 返回太多的无关内容。若干个关键词构成的一个查询组合可能返回上万个相关页面 链接，很多检索结果和用户查询毫无关系，而且返回的信息很少具有个性化的相关度排 序，用户最满意的信息并不是最先推送给用户。研究指出，大概7 5 的搜索结果可能是 和查询条件无关的。 2 查全、查准率较低 任意单一搜索引擎的w e b 覆盖范围有限。上面提到，有调查显示目i j i 没有任何一个 搜索引擎的网页索引超过整个w e b 总网页的六分之一。由此可见，每个搜索引擎虽然相 对查全率比较高，而实际查全率则比较低。现有的大部分信息检索系统采用关键词输入 方式进行检索，查询以关键字和布尔查询为主，关键词是由用户自由选择的，不受任何 限制，用户所选择的词有很大的随意性，无法实现同义概念、上下位概念的检索，无法 通过逻辑推理进行检索，检索智能化程度不高。目前搜索技术仅仅对关键字进行简单的 匹配，而不能根据用户查询目的进行查询内容的扩展，此外有些信息查询是很难用关键 词组合来准确的描述。全文检索已是一个很成熟的技术，它能够解决对网页细节的检索 问题。从理论上说，只要网页上出现了某个关键词，就能够使用全文检索用关键词匹配 把该网页查出来，但是这又导致了它的缺陷一返回的信息太多。更严重的是，除了综合 性的搜索引擎站点有这个现象之外，现在较大的站点对自身站内信息的检索也会返回大 量的网页。传统的文本信息检索一般使用查全率( r e c a l l ) 与查准率( p r e c i s i o n ) 来对检 索效果进行量化评价，但是在海量的互联网信息检索上用查全率与查准率来衡量检索效 果是否合适? 在某些场合，高的查全率带来的成千上万命中网页对用户实在是一个沉重 的负担，除此之外，它还有两个不很直观的深层次问题，也给信息检索带来了不少困难。 这两个问题都与词汇密切相关：一个是“忠实表达”的问题。很多情况下，用户很难简 单地用关键词或关键词串来忠实地表达他所真正需要检索的内容，表达困难导致检索困 难。另一个是“表达差异”问题。人类的自然语言中，随着时间、地域或领域的改变， 同一概念可以用不同的语言表现形式来表达。因此，对同一概念的检索，不同的用户可 能使用不同的关键词来查询，例如：“计算机”和“电脑”，“麦克风”与“话筒”。但在 有些搜索引擎上使用“麦克风”是查不到含“话筒”的网页的，虽然它们指的是同一种 东西。 3 专业性的搜索引擎较少 目前的中文搜索引擎多是综合搜索引擎，可以提供全面的检索服务，这对于普通用 户而言比较方便，但是对于比较专业的用户来讲就很难满足需要。在西文搜索引擎中就 有不少专业搜索引擎，如美国的医学文献数据搜索引擎等。专业搜索引擎能比较集中、 迅速、准确和全面地反映某一行业的技术和发展情况，对开展科技信息的服务和咨询也 是很有好处的。 4 只能发现信息，而不是知识 w e b 中包含着大量信息，而这些信息经过提炼加工可以上升为知识。单纯的使用统 计的方法无法把海量的信息转化为知识的形态。 5 更新速度比较慢 搜索引擎机器人只能在由系统管理员确定的一定时问间隔内跟踪特定信息，不能保 证信息的及时更新，导致产生错链和死链。随着网络信息数量的指数增加，引擎数据库 急剧膨胀，检索速度也将会变慢。 通过上面的分析我们可以看出，搜索引擎实际上就是在用户( 搜索引擎的使用者) 和互联网资源( 搜索引擎的搜索对象) 这两者之间建立起一个联系，将用户真正想要的 2 内容呈现给用户，同时用户不想要的内容不呈现给用户。我们称这一要求为“所得即所 需”。当前搜索引擎并不能很好的解决查准与查全的问题，造成这种困难的实质在于搜 索引擎缺乏知识处理能力和理解能力，对要检索的信息仅仅采用机械的关键词匹配来实 现。把信息检索从目前基于关键词层面提高到基于知识( 或概念) 层面，是解决问题的根 本和关键。为了解决w e b 信息检索中存在的各种问题，e t z i o n i 提出了w e b 挖掘( w e b m i n i n g ) 的概念嘲：它是指从大量的w e b 文档集合中发现蕴涵的、未知的、有潜在应用价 值的、非平凡的模式。它所处理的对象包括：静态网页、w e b 数据库、w e b 结构、用户使 用记录等信息。通过对这些信息的挖掘，可以得到仅通过文字检索所不能得到的信息。 应该注意到基于w e b 的数据挖掘和传统的基于数据仓库的数据挖掘有着不同的含义。它 是数据挖掘技术在w e b 环境下的应用，根据w j f r a w l e y 和g p s h a p i r o 等人的定义， 一般的数据挖掘指从大型数据库的数据中提取人们感兴趣的知识，这些知识是隐含的， 事先未知的、潜在的有用信息，它侧重在于从已有的信息中提取规律性的知识。而w e b 挖掘的研究对象是以半结构化和无结构文档为中心的w e b ，这些数据没有统一的模式， 数据的内容和表示互相交织，数据内容基本上没有语义信息进行描述，仅仅依靠h t m l 语法对数据进行结构上的描述。为了对这种半结构化数据进行分析和处理，w e b 挖掘必 须和其研究手段结合起来。由于涉及到很多的知识领域，w e b 挖掘现在是多个研究方向 的交汇点，包括数据库、信息获取、人工智能、机器学习、模式识别、统计学、自然语 言处理等。 1 1 3 本文研究的现实意义 随着我国教育信息化工作的深入开展，教学资源的迅速膨胀，如何从海量教学资源 库中准确快速地搜索到所需信息成为教与学过程中亟待解决的问题。由于传统的搜索引 擎大多基于关键字的简单匹配技术，对用户输入的查询条件缺乏理解能力，返回的信息 太多且查全率和查准率都不高，以至于对用户的意义不大。而教学资源又有其自身的学 科特点，因此，研究专门的智能化的教学资源搜索引擎成为一种客观的需求。 目前，专门针对中国中小学基础教育资源的专业搜索还尚未出现，比之于通用文件 信息检索的发展，教育信息化改革和中国中小学基础教育资源建设的发展相对较缓慢， 当历史的车轮迈进入2 1 世纪时，信息技术的飞速发展加快了教育信息化的步伐，中文 信息检索技术本身的进步也给教育信息化带来了很好的启示，我们东北师范大学理想信 息技术研究院是专门开发适合我国具体国情的教学支撑软件和建设教学资源的单位，以 东北师大的专家教授为依托，以全国的中小学为服务对象，每天接触的资源种类繁多， 对工作人员要求较高，既要求他们懂得相关专业知识，也要熟悉计算机方面的相关技能， 即使如此，仍不可避免的造成资源的个别分类错误，此搜索引擎的研究开发无疑对提高 今后的工作效率起到很大的促进作用。 综上，开展对基于教育资源的搜索引擎研究具有重要的科研价值和应用价值。 3 1 2 国内外研究现状 1 2 1 中文搜索引擎研究现状 从1 9 9 4 年4 月中国科学院网首次与i n t e r n e t 网互联至今，在这短短的1 0 多年间 里，中文搜索引擎的发展速度惊人。据有关统计，比较有影响的简体中文搜索引擎有1 1 3 个，繁体搜索引擎有2 1 4 个。1 而且经过几年的发展，中文搜索引擎的检索范围、检索 功能也正在不断完善。出现了一些较高质量的中文搜索引擎，这些引擎既有网站检索， 也有全文检索：既有简单查询，也有支持复杂条件的高级查询；既有新闻组和f t p 检 索，也有全新智能型的搜寻功能；既可支持简体中文g b 码，又可支持繁体中文b i 9 5 码。但与国外的一些搜索引擎相比，中文搜索引擎还有相当的差距，还有许多问题亟需 解决。 与其他语言搜索引擎相比，中文搜索引擎至少具有两大特点：一是汉字的内码，二 是汉字的切分。 i 、汉字的内码 由于历史与政治的原因，目前中文网页在中文语言的使用上存在较大的差别，中国 大陆、新加坡使用的是简体中文，台湾、香港、澳门使用的是繁体中文，体现在计算机 处理上最重要的区别是采用了不同的字符集和内码体系，大陆是国标码( g b ) ，台湾用 的是大五码( b i g 5 ) 。尽管不少中文搜索引擎都提供编码选择，支持检索繁体或简体的中 文信息，但这仅仅解决了信息检索问题，而最为重要的是如何实现两种编码的自动转换， 以方便用户利用。 2 、汉字的切分 对词的切分主要是对网络信息资源的标引和对用户检索词的切分，由于西文字符之 间用空格分隔，方便计算机标引与检索，而中文的字词之间没有明显的分隔符，这成 为汉字自动分词的障碍。目前有两种处理方法，一种是按单汉字检索，将文章中的单个 汉字都录入索引库中，用户根据单汉字的匹配原则进行检索，这虽然能够保证很高的检 全率，但会返回大量的无关结果，误检率相当高。于是又提出了对字与字之间的位置 限定。位置的限定可以减少一些虚假组配，提高检准率，但基于单汉字的检索仍然会带 来很多的垃圾信息。另一种是根据一定的原则与方法对文章进行自动分词，然后按词组 或短语建库。同样，也需对用户的检索输入切分，然后再与库中的词组匹配，返回相 一致的结果。 1 2 2 与国外搜索引擎的差距 l 、索引数据库容量 作为搜索引擎，必须要有足够多的库容量才具有一定的代表性和实用性，我们甚至 可以把搜索引擎可搜索的数据库容量大小看作是衡量搜索引擎质量的第一要素。0 1 从| ；i 面所考察的主要中文搜索引擎来看，除了g o o g l e 和雅虎依靠自身的优势数据库容量在 几十亿网页以上外，其他国内的主要中文搜索引擎中，数据库容量最大的百度也只有3 亿网页。而据统计，g o o g l e 已经能够提供4 0 多亿个网页及网页快照供大家搜索，支持 4 8 6 种不同的语言搜索，如今全球7 5 的网上信息搜索都是通过g o o g l e 完成的。其他 一些国外的大型搜索引擎数据库容量也都在1 0 亿网页以上。 2、核心技术， 搜索引擎是一个技术含量很高的网络应用系统。它包括网络技术、数据库技术、检 索技术、智能技术等等。是否拥有核心技术将最终决定一个搜索引擎的成败。对中国搜 索引擎，技术是一个致命的障碍。因为他们并不像g o o g l e 那样拥有核心的技术，也无 法向雅虎学习，对于中文搜索引擎来讲，由于国外的很多先进技术是建立在西文内核的 基础上，所以我们还不能单纯引进、照搬照抄。如何发挥我们在中文处理上的长处，研 发出有我们自己版权的核心技术，将成为中文搜索引擎发展的当务之急。 3 、多样化服务 靠提供多样化服务来吸引更多的用户，以此来获取更多的广告收益，这是国外著名 搜索引擎的生存之道。而在这一方面，中文搜索引擎也缺乏相应的资本和影响力。 国外专业搜索引擎做的比较好的机构有：e l s e v i e r 公司，加州大学伯克利分校，n e c 研究院，美国国家数字图书馆等。嘲 1 3 论文的研究内容与创新点 本文首先对搜索引擎的现状、存在的问题及其未来发展趋势进行了探讨，提出了基 于w e b 挖掘的搜索引擎思想，并对w e b 挖掘如何应用于小型局域网搜索引擎进行了重点 的讨论和研究，在此基础上，提出了东师理想教学资源搜索引擎的系统架构，且对系统 各部分的功能和关键技术进行了论述。 本论文的创新点主要有： 教学资源搜索引擎是一种专门性的搜索引擎，目前国内还没有专门的教学资源搜 索引擎：因而研究教学资源搜索引擎本身就是一种尝试。 本系统是服务于特定的资源对象( 高中政治学科) ，面向特定人群( 理想信息技 术研究院员工及其产品用户) ，他们的搜索需求往往具有一些特定的指向与目的性，这 对搜索引擎提出了更高的个性化要求，作者提出了基于w e b 挖掘的个性化技术，通过w e b 挖掘发现用户兴趣和访问模式，使查询结果更符合用户的需求。 根据东师理想信息技术研究院教学资源库的现状和用户特点，提出了基于w e b 挖 掘的教学资源搜索引擎模型。 对网页排序的p a g e r a n k 算法进行了较为系统的研究，通过分析各种不同网络结 构，对影响p a g e r a n k 值的因素进行了较为详细的分析。并对p a g e r a n k 算法进行了改进 与优化，通过加入网页对在网络结构中出现次数的判定，对p a g e r a n k 算法中的主题漂 移现象进行了较好的抑制。并在局域网范围内进行了实验论证。 对利用w e b 挖掘处理教学资源数据、对页面进行自动聚类进行了有益的探索。引 入后缀树的概念对爬取页面进行动态聚类，由于这种数据结构在字符串处理方面的优越 性，可以取得较为理想的效果。 5 1 4 论文的组织结构 第一章首先介绍了课题的研究背景与现实意义，对国内外搜索引擎的研究进展进行 了综述，简单介绍了论文的研究内容与创新点，同时对论文的组织结构进行了说明。 第二章对搜索引擎的相关理论进行了概述，主要包括搜索引擎的分类，工作原理， 关键技术，面临的关键问题与挑战等内容。 第三章主要介绍了w e b 挖掘的相关理论，其中包括w e b 挖掘的定义，w e b 挖掘的分 类，然后通过介绍w e b 挖掘的自身特点，从目前搜索引擎所面临的问题入手，明确了w e b 挖掘与搜索引擎相互补充的良性关系，最后分析了将w e b 挖掘应用于搜索引擎技术各方 面的显著优势。 第四章作者建立了基于w e b 挖掘的东师理想信息技术研究院面向政治学科领域的搜 索引擎模型，提出了东师理想政治学科搜索引擎结构框图，详细论述了各模块功能实现 的关键技术。 第五章对网页排序模块中的p a g e r a n k 算法进行了重点论述，解析了算法的推导过 程，并通过实例分析了影响p a g e r a n k 值分布的因素，指出了算法的不足之处并给出了 算法改进的策略，提出了一种基于二阶相似性的算法改进并进行了相关实验论证。 第六章从w e b 文本挖掘的角度出发，采用了一种新的树形数据结构对文本进行动态 聚类，聚类的目标是将文档分成若干个簇，要求同一类中文档的相似度尽可能大，不同 簇间相似度尽可能的小。后缀树由于其自身数据结构的特点，可以很快的判别一个文档 是否归属于哪一类。本节介绍了后缀树算法的特征、流程以及将其应用在文本动态聚类 中的过程。 第七章对未来将要进行的工作进行了总结与展望。 6 第二章搜索引擎相关理论 2 1 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种“3 ，分别是全文搜索引擎( f u l lt e x ts e a r c h e n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎( m e t as e a r c h e n g i n e ) 。 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、f a s t a 1 1 t h e w e b 、 a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。它们都是通过 从互联网上提取各个网站的信息( 以网页文字为主) ，建立索引数据库和倒排文档，检 索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此它 们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己的检索程 序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程序，并自建网页 数据库，搜索结果直接从自身的数据库中调用，如上面提到的7 种引擎；另一种则是租 用其他引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。 目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是按目 录分类的网站链接列表而己。用户完全可以不用进行关键词( k e y w o r d s ) 查询，仅靠分 类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的y a h o o 雅虎。 其他著名的还有o p e nd i r e c t o r yp r o j e c t ( d m o z ) 、l o o k s m a r t 、a b o u t 等。国内的搜狐、 新浪、网易搜索也都属于这一类。 元搜索引擎( 雠t as e a r c he n g i n e ) 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返 回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等，中文元搜索引擎 中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结 果，如d o g p i l e ，有的则按自定的规则将结果重新排列组合，如v i v i s i m o 。 除上述三大类引擎外，还有以下几种非主流形式； i 、集合式搜索引擎：如h o t b o t 在2 0 0 2 年底推出的引擎。该引擎类似m e t a 搜索引 擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的4 个引擎当中选 择，因此叫它“集合式”搜索弓f 擎更确切些。 2 、门户搜索引擎：如a o ls e a r c h 、m s ns e a r c h 等虽然提供搜索服务，但自身即没 有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 3 、免费链接列表( f r e ef o ra l ll i n k s ，简称f f a ) ：这类网站一般只简单地滚动 ， 排列链接条目，少部分有简单的分类目录，不过规模比起y a h o o 等目录索引来要小得多。 由于上述网站都为用户提供搜索查询服务，为方便起见，我们通常将其统称为搜索 引擎。 2 2 搜索引擎的工作原理 搜索引擎作为一个网络应用软件系统，对它有如下基本要求：“1 1 能够接受用户通过浏览器提交的查询词或者短语，记作q ，例如“非典”，“伊拉 克战争”，“床前明月光”等等。 2 在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表，记作l 。 这个列表的每一条目至少包含三个元素( 标题，网址链接，摘要) 。 现代大规模高质量搜索引擎一般采用如图2 1 所示的称之为三段式的工作流程， 即：网页搜集，预处理和查询服务。 图2 一l 搜索引擎三段式工作流程 网页搜集模块 如果说软件系统是工作在某个数据集合上的程序的话，这个软件系统操作的数据不 仅包括内容不可预测的用户查询，还要包括在数量上动态变化的海量网页，并且这些网 页不会主动送到系统来，而是需要由系统去抓取。 在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见的一种 是所谓“爬取”：将w e b 上的网页集合看成是一个有向图，搜集过程从给定起始u r l 集 合s ( 或者说“种子”) 开始，沿着网页中的链接，按照先深、先宽、或者某种别的策略 遍历，不停的从s 中移除u r l ，下载相应的网页，解析出网页中的超链接u r l ，看是否 已经被访问过，将未访问过的那些u r l 加入集合s 。整个过程可以形象地想象为一个蜘 蛛( s p i d e r ) 在蜘蛛网( w e b ) 上爬行( c r a w l ) 。在真正的系统中，其实是多个“蜘蛛” 同时在爬。 有一种方法是让网站拥有者主动向搜索引擎提交它们的网址( 为了宣传自己，通常 会有这种积极性) ，系统在一定时间内( 2 天到数月不等) 定向向那些网站派出“蜘蛛” 程序，扫描该网站的所有网页并将有关信息存入数据库中。大型商业搜索引擎一般都提 供这种功能。 预处理模块 得到海量的原始网页集合，下一步是离线对这些网页进行预处理，现行最有效的数 据结构是“倒排文件”( i n v e r t e df i l e ) ；倒排文件是用文档中所含关键词作为索引， 文档作为索引目标的种结构( 类似于普通书籍中，索引是关键词，书的页面是索引目 标) 。从网页集合到形成这样的倒排文件( 即我们所说的“预处理”) 主要包括四个方面， 关键词的提取，“镜像网页”( 网页的内容完全相同，未加任何修改) 或“转载网页” ( n e a r r e p l i c a s ，主题内容基本相同但可能有一些额外的编辑信息等，转载网页也称 为“近似镜像网页”) 的消除，链接分析和网页重要程度的计算。 1 关键词的提取 对于中文来说，就是要根据一个词典，用一个所谓“切词软件”，从网页文字中 切出所含的词语来。在那之后，一篇网页主要就由一组词来近似代表了，p = ， f 2 ，f 。) 。一般来讲，我们可能得到很多词，同一个词可能在一篇网页中多次出现。 从效果和效率考虑，不应该让所有的词都出现在网页的表示中，要去掉诸如“的”，“在” 等没有内容指示意义的词，称为“停用词”。这样，对一篇网页来说，有效的词语数量 大约在2 0 0 个左右。 2 镜像网页的消除 研究表明，网页的重复率平均大约为4 。也就是说，当你通过一个u r l 在网上看到 一篇网页的时候，平均还有另外3 个不同的u r l 也给出相同或者基本相似的内容。这种 现象对于广大的网民来说是有正面意义的，因为有了更多的信息访问机会。但对于搜索 引擎来说，则主要是负面的；它不仅在搜集网页时要消耗机器时间和网络带宽资源，而 且如果在查询结果中出现，无意义地消耗了计算机显示屏资源，也会引来用户的抱怨， 。这么多重复的，给我一个就够了”。因此，消除内容重复或主题内容重复的网页是预 处理阶段的一个重要任务。 3 链接分析 一般爬取的网页中都含有大量的h t 札标记，这些标记既给网页的预处理造成了一 些麻烦，也带来了一些新的机遇。从信息检索的角度讲，如果系统面对的仅仅是内容的 文字，我们能依据的就是“共有词汇假设”，即内容所包含的关键词集合，最多加上词 频( t f ) 和词在文档集合中出现的文档频率( d f ) 之类的统计量。而t f 和d f 这样的频 率信息能在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关性， 这是有意义的。有了h t m l 标记后，情况还可能进一步改善，例如在同一篇文档中， 和 之间的信息很可能就比在 和 之间的信息更重要。因为文章的主要内容 往往在标题中就有所反映。特别地，h t m l 文档中所含的指向其他文档的链接信息是人们 近几年来特别关注的对象，认为它们不仅给出了网页之间的关系，而且还对判断网页的 内容有很重要的作用。 4 网页重要程度计算 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的顺序是 很重要的一个问题。由于面对各种各样的用户，加之查询的自然语言风格，对同样的q 0 返回相同的列表肯定是不能使所有提交q 0 的用户都满意的( 或者都达到最高的满意度) 。 因此搜索引擎实际上追求的是种统计意义上的满意。如何讲一篇网页比另外一篇网页 9 重要? 人们参照科技文献重要性的评估方式，最直观的一个想法就是“被引用多的就是 重要的”。“引用”这个概念恰好可以通过h t m l 超链在网页之间体现得非常好，作为 g o o g l e 创立核心技术的p a g e r a n k 就是这种思路的成功体现。除此以外，人们还注意到 网页和文献的不同特点，即一些网页主要是大量对外的链接，其本身基本没有一个明确 的主题内容，而另外有些网页则被大量的其他网页链接。从某种意义上讲，这形成了一 种对偶的关系，这种关系使得人们可以在网页上建立另外一种重要性指标。这些指标有 的可以在预处理阶段计算，有的则要在查询阶段计算，但都是作为在查询服务阶段最终 形成结果排序的部分参数。 综上，搜索引擎的工作过程是：首先从蜘蛛开始，蜘蛛程序每隔一定的时间( 象 g o o g l e 一般是2 8 天) 自动启动并读取网页u r l 服务器上的u r l 列表，按深度优先或广 度优先算法，抓取各u r l 所指定的网站，将抓取的网页分配一个唯一文档i d ( d o c l d ) ， 存入文档数据库。一般在存入文档数据库之前进行一定的压缩处理。并将当前页上的所 的超连接存入到u r l 服务器中。在进行抓取的同时，切词器和索引器将已经抓取的网页 文档进行切词处理，并按词在网页中出现的位置和频率计算权值，然后将切词结果存入 索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库，这样 用户就可以查询最新的网页信息。查询器首先对用户输入的信息进行切词处理，并检索 出所有包含检索词的记录，通过计算网页权重和级别对查诃记录进行排序并进行集合运 算，最后从文档数据库中提取各网页的摘要信息反馈给查询用户。 2 3 搜索引擎的关键技术 这一部分主要论述搜索引擎使用到的关键技术，其中包括：p a g e r a n k 技