（计算机应用技术专业论文）基于web+community识别的专业搜索引擎研究.pdf

浙江大学硕士学位论文 摘要 随着i n t c m e t 的飞速发展，w 曲的信息量越来越大，传统的搜索引擎已经不能满足人们 对个性化信息检索服务的需求。对于用户提供的关键字，现有的搜索引擎往往返回成千上万 的搜索结果，用户很难从中找到自己真正需要的内容。为了解决这个日益严重的问题，针对 专业领域的个性化搜索研究正成为一个越来越热门的课题。 专业网站组成的集合，通常以w 曲g o 加n 岫n y 的形式存在，并具有s c a l e 血e 特性。在 一个具有s c a l 曲e e 特性的网络中，网络节点的“出度入度数”对应的分布函数及其相关参 数几乎不受网络规模的影响，保持很好的稳定性。通过识别相应的w 曲c 【h 衄m n i t y ，可以 有效地提高从网络获取信息的效率。 文章主要讨论分析一个专业w 曲c 0 u n i t y 识别系统的设计和实现过程，通过专业网 络蜘蛛从互联网有选择地抓取网页，并对抓取的网页内容进行专业相关性分析，不断将满足 条件的网页加入到、e bc o m m u n i i y 中，最终构建一个相对完整的专业w 曲q m m i i y 。文 章以对搜索引擎的背景和w 曲c o m “m n i i y 识别的相关技术介绍开始，分析了现有技术的不 足之处，接着对系统实现的关键技术进行了详细地讨论与分析。 对系统设计与实现的讨论主要集中在以下两个章节：专业网络蜘蛛的设计与实现和w 曲 c o m u i t y 识别关键算法研究。第三章描述了专业网络蜘蛛模块的设计实现以及性能优化等 问题。讨论分析了其搜索策略的制定。第四章在目前较成熟的w 曲c o m m u n j t y 识别技术的 基础上，提出了一种网页主题识别算法一w r 算法m i g h t e dk e y w dh i e r a r c h i c a l r e c 0 印i t i o n ) ，该算法可以有效提高页面主题判断的准确性，在实际测试中取得了良好的效 果。 论文的第五章叙述了系统的具体实现以及系统原型的相关测试分析。 最后，第六章对全文所做的工作做了一个总结，并提出进一步的展望。 关键词：搜索引擎，网络蜘蛛，搜索策略，完成端口，主题识别，w 曲c o 舢u n i l y 浙江大学硕士学位论文 a b s t i 甚c t t h em p j dd e v e l o p m e n to ft h el n i 唧e lb r i n 萨a b o u tt h ee x p 王o s i o n0 ft h ec o n t e n t so ni h e w w w ：n j sh a w e v c r m a k 髂龀聘嫡e v a lo fl h es e 砌e di n f o m a n 衄d 瑚c l l l t y w o r d b a s e d a f c hu 肌a y t i l i n sai 眦韶- v ea m o u n to f m d a t i v em s l l l t sw h i c ho v e r w h e l i nu f l l li n f o m a t i 蛐 n c w a r c he n g i n et e c h n o l o g yi si ne x i g e d td c 咖d 1 n l h e i n t e 础t ，w e b s i t e ss p e 醐i z e d i nac e r t a i nd o 啪i ne x i s t i nm e f 0 皿o f w e bc 0 咖i t y w i i ht h ed i s t i n c i i v ed h m c i e d s t i co fs c a k 4 l e en e t w o r k i nas c a k l l h en e 铆o r k t h ed 砌b u t i o no f l h ec 0 曲e 嘶蛐s0 ft l l en o d e si sv e r ys l e a d y 姐da p p x i m a l e l ys a 血f i 髓ac e r i a i n 妒w 盯l 删 d i s i r i b u t i o n b y 蹁t t i gu pas p c c i a l i z e dw 曲。珊哪u 血y ，w ec o u l di 唧v cl h ee 饿c i c 船y0 f t e t f i e v i n gt h en d e d 血f 0 n a t i o n 丘o mt h el i l 把m e t 1 n 山i s 也e s i s t l l ea u t h o ra i m st od 船i g na di m p l e m e n tas p e c i a l i z e ds e a r c he n g i n eb a 鸵d 蛐 w 曲c b 姗u n i t yf e c o g n i 吐o n t h es y s t e ms e l e c t i v e l yg m b s 璩w e bp a g e s 丘d mt h e 硫e m e tb y s p c c i a l j z e dw 曲s p i d e ra n d 柚a l y st b ep r o f e 站i o n a l 婵l a t i v i i yl h ep a g ec o m e n t s 而山锄e 艏c i e t a p p f o a c h mw h i c har e l a 虹v e 】yc o m p l e t ew 曲c o i n m u n i t yw i ub ec 佃s m l c t e dw i t bt h ee x p a 髂i 衄 o f h ec o v e r e ds c o p e 1 kt b e s i ss t a r t sw i 恤触j n d u c l i o nt ot h eb a c k g m u n d 柚d l a t e dt e c h l o g yo fw e b o d m m u n i t y ，w h i c bi sf o l l o w e db y 也ed e t a i l s0 ft l l es y s t e md e s i 髓如di i l l p l e m e n t a n o nt h e r e 撒e l 1 1 l es y s t e md e s i 鲫i s s u e sc o n c e n 仃a t e so nt h ef o n a w i n gt w 0c o m p o n e n t s ：as p e c i a l i dw e bs p i d e r a n d 柚s e m a n 廿c b a s e da l 酬t h mf o re m c i e tw 曲c o m m u n i t y r e c o g n i t i o n i nc h 叩t e r3 ，i h et l l e s i s m a i n 】ye x p a t i a t 幅d nt h ei m p l e m e n t a t i o no ft h ep r o f e s s j o n a lw c bs p i d e ra n d 妇o p t i l l l i z a l i o n t b 鼬 c h ef h e s i sf o c u s e si l sd i s c i i s s i o np u t d n gf 0 州a r da “n do fw e bi h e 腿r e c o 萨埘0 na l g o r i t l l m w 删rc w e i g i i t e d & y w o r d 埘e r 盯c h i c a lr e c 0 印i t j o n ) i nc h a p t e f4 。 f 曲a l l y t h et h e s i sc o n c l u d e s 、i t has u 衄a r y0 fp f e n ia n df i l t u r eo ft l i ea p p c a 曲no fw 曲 c o m m l l l l i t yi nt l l es e a r c he n g i n e 1 【e y w o r d s ： s e 盯c he n g i i l e ，w e bs p i d e ls e 辨hs t f a t e g y c o m p l e 抽np 0 n ，1 1 l e m r e c o 驴i t i o n ，w 曲c o m m u n i t y 2 浙江大学硕士学位论文 第一章绪论 1 1 背景 第一章绪论 随着l n l e m e t 的空前普及，网络正在彻底改变人们的生活方式。通过网络获取信息已经 成为人们信息获取的重要方式之一。目前w w w ( w o f l dw d ew 曲) 上信息呈现最主要的方 式是以h m l 协议为基础的网页，它以直观、简单、高效的使用方式和丰富的表达能力， 逐渐成为h i c m c t 上最重要的信息交互方式。随着信息时代的到来，w w w 上的信息飞速增 长，w w w 的使用者已经逐渐感觉到被信息海洋所淹没的困境。w w w 在给人们提供越来 越丰富的信息的同时，却使得信息的准确获取变得越来越困难：一方砸，w w w 上存在着 用户随时可以获取的庞大信息；另一方面，用户要从庞大的信息中迅速找到真正需要的信息 却非常困难。为了解决这个问题，搜索引擎应运而生，并为用户快速获取需要的网络信息提 供了巨大帮助，但同时，目前的一些主流搜索引擎，比如g 一e ，m o o l 等，都还有很多 不完善的地方，尤其是在专业领域的信息获取方面。对于专业领域的信息查询，现有的主流 搜索引擎往往会返回大量的无关信息。如何精确地从w w w 上获取需要的信息，尤其是精 确地获得特定专业领域的信息，是目前广泛研究的课题。 本文在这种背景之下，结合近年来比较热门的w 曲c o i n m u i t v 识别技术的研究成果， 对专业领域的信息获取提出了一种新的思路和解决方法。结合这种新思路所实现的专业搜索 引擎，在专业领域信息搜索的效率和精确度方面。都较传统的搜索引擎有较大的改进。在具 体深入讨论专业搜索引擎之前，本章将先对现有的一些和搜索引擎相关的技术做一个概括性 的介绍。 1 2 通用搜索引擎技术 为了解决从海量信息中获取所需信息的困难，提供w 曲页面搜索服务的搜索引擎技术 应运而生。如今的网页数量以亿为单位进行计算，单纯靠用户自己在海量的网页中去找寻需 要的信息，其难度可想而知。没有搜索引擎的帮助，在海量w 曲页面中进行信息检索是不 可想象的。随着w w w 的发展，搜索引擎技术正在不断影响改变着人们的生活，成为人们 生活的重要部分。目前已存在的太多数搜索引擎，它们关注广大用户的搜索需求，不对人群 需求进行划分，因而也被称之为通用搜索引擎。它们通常使用若干个的w 曲信息提取器( 网 络蜘蛛) 在互联网上收集各种感兴趣的信息，然后为这些信息创建相应的索引并存储在数据 库中。当用户输入关键字对信息进行查询时，系统将检索已经搜集到的信息，并将满足条件 的结果快速返回给用户。 基于关键字的搜索是w 曲页面信息搜索方式中最常见的一种，通常使用的是全文检索 浙江大学硕士学位论文 第一章绪论 技术，它将w 曲看作一个超大规模的全文数据库，每张页面对应若干个关键字。并采用高 度优化的数据结构对这些信息进行存储。当用户提交搜索请求时，采用关键词匹配进行信息 检索，在相关算法的支持下，在很短时间内返回查询的结果。 现有的通用搜索引擎一般预先对w 曲上的网页信息进行提取并进行相应的处理。这些 处理和具体的用户搜索请求是无关的。进行这些处理的原则是尽量减少获取搜索请求后的处 理步骤，从而尽可能地减少用户等待搜索引擎返回结果的时间。搜索引擎返回的结果中一般 包括了w 曲页面标题和相应的链接地址，同时根据页面的匹配程度进行降序排列，以便于 用户选择。 通用搜索引擎的典型工作原理如图1 1 所示。 图1 1 搜索引擎典型工佧原理图 从图1 1 中可以看到，一般的搜索引擎至少包括以下几个典型的模块： 1 、网络蜘蛛 网络蜘蛛是一个w 曲访问程序，它是搜索引擎从互联网上获取信息的主要手段。它根 据预先设定的u r l 地址去访问相应的网页，将网页内容抓取到本地，由页面处理程序分析 网页中的链接地址，根据相应的访问策略选择相应的链接继续进行访问。w 曲上网页间的链 接结构，将网页集合描述成了一个有向图，网络蜘蛛提取页面的过程就是对该有向图进行访 问的过程。网络蜘蛛搜索策略的核心是对该网页拓扑图进行访问时遍历策略的选择。从理论 上讲，为网络蜘蛛指定适当的初始网页集和适当的遍历策略，它可以遍历整个互联网，当然， 在实际中会遇到各种各样的问题。 2 、页面处理索引模块 页面处理模块对网络蜘蛛提取的网页进行处理这一步骤的关键在于对网页信息的分 析处理。如何准确去除网页中的噪音f 当前的网页中往往存在大量的广告等与网页主题毫无 关联的内容1 ，提取出关键字，是网页处理的关键。对于英语等以词为单位的语种，不需要 进行单词的划分，而对于中文来说，还涉及到对语句进行词语划分即分词的问题。提取山关 键字后，将进行索引建立等相关处理，最终将相关信息存入数据库。 索引性能的高低对整个搜索引擎的性能起着至关重要的作用。现有的索引一般按照倒 排文件的格式存放，同时根据具体情况对索引结构进行相应的优化调整。建立索引是在抓取 到页面内容后进行的，这是一个可以线下处理的过程，也就是说，这一步和具体的用户请求 无关。正因为如此，建立索引时应该考虑如何简化系统在获取用户搜索请求后的的计算量， 2 浙江大学硕士学位论文第一章绪论 使索引模块尽量在前期分担更多的计算量，从而减少搜索引擎得到用户检索请求后的处理时 间，使用户能够在较短时间内得到检索结果。 3 、检索模块 检索模块是搜索引擎和用户之间的接口。用户提交检索的关键字集合后，检索模块对用 户的查询条件进行分析，将其转化为对系统数据库的相关查询访问。得到查询结果后，根据 设定的相关度以及其他一些排序逻辑r 比如竟价排名等因素) ，按照重要性进行降序处理后返 回给用户。 除此之外，不同的搜索引擎还具有自身特有的的一些模块。比如，对于一些非商业化 的搜索引擎，根据用户请求查询到的搜索结果一般都直接返回给用户，而商业化的搜索引擎 还需要经过其商业逻辑模块的处理，如竞价排名等，最终再返回给用户。互联网搜索领域蕴 涵巨大的商业价值，很多机构都在积极研发功能更强大的搜索引擎，这使得当前的搜索引擎 技术发展极快，新技术不断涌现。 应该看到的是无论从当前的智能识别技术，还是从实际的计算量上，当前的通用搜 索引擎从页面提取关键词后很难对关键词进行语义层面的分析，关键词之间很难建立语义上 的联系。这使得基于关键词的检索在查询某一专业领域的概念时准确性较差，系统返回的结 果往往不是用户真正需要的。 1 3 元搜索引擎 与上面介绍的通用搜索引擎不同，元搜索引擎是一种通过调用其它独立搜索引擎而完 成搜索服务的搜索引擎，是用户同时利用多个独立搜索引擎进行网络搜索的中介。元搜索引 擎尽可能地减少和优化了检索操作，实现了一次检索输入，同时利用多个搜索引擎进行搜索。 元搜索引擎中整合、调用、控制和优化利用独立搜索引擎的技术，被称之为“元搜索技术” ( m e t a - s e a r c h i n gt c c h n i q u e ) ，它是元搜索引擎技术的核心1 6 j 。 图1 2 是元搜索引擎的原理示意图，从图中可以看到，用户通过相应的查询界面提交查 询请求后，元搜索引擎根据该请求，调用若干个独立搜索引擎进行搜索，得到各个独立搜索 引擎返回的结果后，再对这些结果进行汇集、筛选、合并等相关处理，最后以统一的格式返 同给用户。可见，元搜索引擎到底使用了哪些独立搜索引擎，对用户来说是透明的，从用户 的使用体验上来说，元搜索引擎和独立搜索引擎之间的使用差别是非常微小的【6 j 。但是，从 技术实现上而言，两者却是截然不同的：元搜索引擎没有自身的网页抓取机制，也没有自身 独立的索引数据库。它需要解决的问题主要集中在对检索的请求提交、检索接口代理和检索 结果的汇总处理等方面。 3 浙江大学硕士学位论文 第一章绪论 闰1 2 元搜索引擎原理示意图 作为若干独立搜索引擎的检索接口代理元搜索引擎需要具有较强的字符和语法转换功 能，使用户的检索请求能够被各种不同的独立搜索引擎所接受。对多个独立搜索引擎返回结 果的汇总处理是元搜索引擎的核心技术之一。由于不同的元搜索引擎在检索结果排序逻辑、 最大检索结果数量、相关度参数等方面存在着差异，这使得不同的元搜索引擎在调用相同的 独立搜索引攀进行搜索的情况下，在检索结果的数量多少、排序先后等方面仍会存在很大的 不同。 元搜索引擎的关键技术包括查询前的预处理和对返回结果的汇总。元搜索引擎可咀动态 地选择所需要的独立搜索引擎，充分利用各个独立搜索引擎的优势。即使某一个独立搜索引 擎发生故障，也不会对元搜索引擎的正常工作造成太大的影响。元搜索引擎的这些特性保证 了搜索结果的全面性和可靠性。 相对于独立搜索引擎，元搜索引擎存在着诸多优点。元搜索引擎通过综合利用多个搜索 引擎的搜索服务，可以在一定程度上弥补单个搜索引擎的不足。元搜索引擎不需要进行一般 搜索引擎中的提取存储网页、分析建立页面索引的工作，它将自身所调用的独立搜索引擎视 为一个外部实体，不需要去维护它们，只需要知道它们的调用接口，就可以与之进行交互。 相对于独立搜索引擎，元搜索引擎的硬件需求低、可维护性好。 尽管元搜索引擎有以上种种优点，但客观来说，元搜索引擎的出现，并不能使搜索引擎 技术得到质的b 跃。元搜索引擎仅仅只是提供了搜索结果的重新组织，除此之外，并没有更 多的创新【6 j 。同时，元搜索引擎在发展过程中也存在很多的i 捌难。首先，元搜索引擎在向独 立搜索引擎提交查询请求前，需要对查询格式进行处理，将其转化为各个独立搜索引擎分别 能识别的格式。由于大部分搜索引擎的查询格式并不统一，这使得查询格式处理变得较为复 杂。其次。各个独立搜索引擎返回结果的格式各不相同，结果中的相关度排序算法也存在差 异，这大大增加了元搜索引擎在最后结果的合并排序等处理上的复杂性。 4 浙江大学硕士学位论文 第一章绪论 1 4 专业搜索引擎技术 通用搜索引擎的出现很大程度上缓解了人们在互联网上查找信息的困难，如目前获得极 大成功的g 0 0 9 l e ，它为广大用户提供了强大的搜索功能。但是，正是由于它的服务是面向 所有用户的，这使得它在处理专业信息检索请求时很难提供用户真正需要的结果。比如，用 户检索“架构”一词，针对建筑业、计算机硬件、计算机软件等不同的领域，获得的结果应 该是不一样的，而现有的通用搜索引擎是无法做到这一点的。针对这个问趣，近年来一种新 的搜索引擎技术正在引起人们的关注，它就是目前比较热门的专业搜索引擎技术。相对于传 统搜索引擎，专业搜索引擎只关注某一特定专业或领域的信息，需要处理的信息量大幅减少， 因此能够为针对专业领域的搜索提供更高质量的服务。本节将对比通用搜索引擎，对专业搜 索引擎做一个概述性的介绍。 1 4 1 通用搜索引擎的弊端 目前的通用搜索引擎面临一系列亟待解决的难题：【1 0 l 1 准确获取用户搜索需求的问题 为了提供给用户最为简便的操作方式，现有的主流搜索引擎都采用了经典的关键字输 入框加搜索按钮的人机交互界面。一方面，用户可以通过最少的操作检索到自己需要的内容； 但另一方面，由于提供的只能是一个关键词集合，用户很难用几个关键词来准确表达真正需 要搜索的内容。即使用户输入了简单明了的关键词，比如上文提到的例子；用户输入“架构” 一词，由于其涉及到各个领域，搜索引擎仍然无法判断用户到底需要哪个领域的信息，而只 能简单地从字符层面对“架构”进行匹配，从两返回大量用户根本不需要的信息。由此可见， 用户和搜索引擎之间交互的困难将直接导致检索结果的不理想。 2 超大规模的网络信息量 截止到2 0 0 5 年5 月，相关研究表明，主流搜索引擎已经索引到全球互联网“可见网页” 中大约8 5 的网页数量，即超过1 1 5 亿页文件，而实际上互联网上可能存在的文件数量高达 5 0 0 0 亿【3 】，只是大部分受访问权限的限制而不能被控索引擎所索引，成为海量的“不可见网 页”。目前网页覆盖率最高的搜索引擎g o o g k ，也只抓取了整个网页数量的4 0 左右。【1 9 | 3 信息表示的不规范 对于从网上获取到的海量信息，其格式缺乏一个严格统一的标准。从信息类别上看， 可以分为文本、图片、声音、图像以及复合的类型。要对图片、声音以及图像等进行机器智 能分类识别，是极其困难的。即使是对于文本信息，由于大部分网页是基于m m l 文档标 准进行文字信息的表示，而m m l 文档是一种半结构化的数据，相对于严格定义的结构化 数据关系表，其更关注于数据的自然表示，而不是数据的内部逻辑处理，此外，大量棚：m 1 5 浙江大学硕士学位论文 第一章绪论 页面并没有严格遵守i r i m l 规范，泛滥的非标准的脚本语言( j a v a s c r i p t 、v l l s c 邱t 等) 都对 h 聊l 页面的自动分析处理造成很大的困难。h n 也文档的半结构化特点使得w 曲数据挖 掘同典型的数据仓库中的数据挖掘有明显的差别。 4 w 曲信息的时效性问题 目前，互联网上的信息量呈现指数增长的趋势，这导致搜索引擎索引到的信息的实时 性很难保证。由于待处理的信息量巨大，搜索引擎往往需要较长的周期来进行信息的更新。 这造成搜索引擎返回的结果很多时候是过时的，具体表现为链接己经删除或链接指向的页面 内容已经发生了改变，这会对用户的使用体验造成极大的影响。 1 4 2 专业搜索引擎的优势 面对通用搜索引擎发展所遇到的种种困难以及信息搜索需求的不断具体化，专业搜索引 擎技术应运而生并得到了广泛应用。相对于通用搜索引擎，专业搜索引擎只提供某一特定专 业或领域的信息，需要处理的信息量犬幅减少，这使得专业搜索引擎在处理面向特定领域的 搜索时有着强大的功能。 专业搜索引擎和通用搜索引擎在很多方面存在着差异。首先，专业搜索引擎不是面向大 众用户提供搜索服务，而只是为某一专业领域的用户提供服务；其次，专业搜索引擎并不关 注整个互联网的信息，而是选择性地关注某一专业领域的信息，从而在处理该领域的搜索请 求时，能够对请求做出更加精确的反馈。相对于通用搜索引擎覆盖面的“大而广”，专业搜 索引擎的目标是努力做到“深而精”。 由于专业搜索引擎只关注于某一领域内的信息，需要提取的信息量和通用搜索引擎相比 减少了许多数量级，这使得很多在通用搜索领域由于时间复杂度等问题而不能使用的算法模 型在专业搜索中变得可行。待处理信息量指数级的减少使得对信息进行更加深入的分析变得 可能。通过进行一些复杂的数据挖掘和分析，可以发现页面内容中蕴涵的更深层次的信息。 同时由于信息量相对较小，网页的更新周期较短，能够较好的保证信息的时效性。 对于准确获取用户搜索需求的问题，专业搜索引擎相对于通用搜索引擎也具有很大的优 势：用户在提交搜索请求时，相当于已经对需要搜索的信息进行了一次划分，这次划分极大 地减少了搜索引擎需要查询的目标集合，从而使搜索引擎需要处理的数据量大大减少。更为 关键的是，由于需要处理的数据量人幅减少，这使得专业搜索引擎从语义层面对页面内容进 行分析在时间上变得可行。这些优势都有助于专业搜索引擎更好地明确用户需求从而为用 户提供更好的搜索服务。 1 4 3w 曲c o m 啪n i t y 在近年来出现的专业搜索引擎技术中，基于w 曲c 0 m m u n i t y 识别的专业搜索引擎技术 6 浙江大学硕士学位论文 第一章绪论 逐渐引起了业界的关注。r e bc o m m 蚵是一个新近出现的概念，人们对于、bc o i i y 的认识来自于对w w w 结构的分析：w w w 上网页之间的链接结构，将两页描述成了链接 上标记着标签的有向图，这个有向拓扑图体现着网页之间的相互关系。通过对w w w 的拓 扑结构进行分析，可以发现拓扑图上的一些节点出现很明显的汇聚性。即形成一个较为明显 的页面团。这种特性并不直观，需要对w w w 的拓扑结构数据进行较大规模的统计分析才 能发现。、bc o i t y 中的网页间有着明显的关联性，相互之间存在大量的链接，这种 网页的聚类，被称之为w 曲c o m m u n i 一“。特定专业领域的页面往往也体现出w 曲 c o i n i t y 的这种汇聚性，从而使该专业领域的内容在互连网上的分布自然地形成一个w 曲 c m m n i t y 。 当然，对于大部分w 出c o 舢岫i t y 而言，处于w 曲c o i i 皿u n i t y 之内和之外的网页并 没有明显的边界，边界的划分直接依赖于聃，e be o 蛐蚰i t y 识别过程中所采用的划分标准。 在w 曲c o u n i t y 的识别过程中，通常定义相应的w 曲c m u n j t y 计算模型，并设定相应 的阀值，以此为标准对页面进行划分，最终得到一个满足条件的页面集合，这个集合即是满 足相应条件的、bc o m m u n i t y 。 w 曲c o u n i t y 的识别方法主要是对现有的w w w 上的网络链接结构进行聚类分析， 这种思路是基于以下几个出发点：首先，一个网页上存在着的指向其它页面的链接，很好地 反映了该网页对这些被链接网页的评价：其次，网络链接是网页上最容易获取的表述该网页 所处网络环境的信息。基于网络链接的网络聚类方法，将网络结构抽象成对网络描述的模型， p a g e r a n k ”，h n 苫m y p c d i n k l n d u c e d1 t o p i cs e a r c h ) 1 引， m 缸f l o wc 【佃m u n i t i e s 等几种 计算模型是其中的典型代表。以上几种基于链接的计算模型确保了在可接受的时间内对大量 的页面进行计算分析。g o o g l e 正是通过以p a g e r a l i l c 为代表的技术，为用户提供优质的搜索 服务，从而在搜索领域获得了巨大的成功。 基于链接结构的w 曲c o m m u n i t y 识别方法，主要有上文提到的几种算法，对于大量的 页面，以上几种算法的计算量都是可接受的。但是，在实际的应用中。单纯的基于链接结构 的w 曲c o m u n i t y 识别方法在专业搜索领域的效果并不理想。专业搜索从内容上来看局限 于特定的领域，具有很强的专业性。比如，对于一个医药类的w 曲c 【m m i t v ，该w 曲 c o m m u n i i y 内的网站都是和医药有密切关系的。通常的w 曲c u n i t y 识别方法在识别过 程中由于计算量等原因并没有对网页的内容主题进行判断，而仅仅停留在链接关系的层次， 这使得最终的结果并不理想。 w w w 上汇集了数量极其庞大的网页，各种网站网页的不断产生，使得互联网规模以 显著的速度增长。即使在互联网内的某个局部，用户可以按自己的意愿进行有序的管理，但 是从整体的角度看，互联网的结构和内容是完全无序的。因此，对网络进行有效的聚类有助 于提高搜索引擎的信息获取能力。 通过某种标准建立相应的w 曲c o u n i t y ，可以对互联网进行各种意义上的划分，减 7 浙江大学硕上学位论文第一章绪论 少搜索引擎在需要处理的信息量方面的负荷，从而使搜索引擎在处理信息搜索请求时可以在 一个较小的范围内对信息进行更加深入的分析匹配。因此，通过合理的策略快速发现海量 、b 页面中的w 出c ( 髓删l n i t y ，成为近年来搜索引擎研究中的一个热点。 本文的第二章将对当前、bc c 咖u n i l y 识别领域的一些研究成果以及相关技术进行详 细地介绍。 1 5 网络蜘蛛 网络蜘蛛是搜索引擎的基础组成部分，在站点拓扑结构分析、内容安全检测、页面有 效性分析等领域有着广泛的运用。从图1 1 可以看到，网络蜘蛛是搜索引擎工作流程中的起 点，它是搜索引擎重要的信息来源。 网络蜘蛛的英文名是w 曲s p i d c r ，这是一个很形象的名字。如果把互联网比喻成一个 蜘蛛网，那么s p i d e f 就是在网上爬来爬去的蜘蛛。网络蜘蛛通过网页的链接地址来寻找网 页，从网站某一个页面( 通常是首页) 开始，读取网页的内容，找到网页中的其它链接地址， 然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都 抓取完为l 匕。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上 所有的网页都抓取下来。 当然，对于搜索引擎来说，要抓取互联网上所有的网页在实际中几乎是不可能的，从 目前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的4 0 左右【1 9 】。 这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页许多网页无法从其它网页的 链接中找到；另一个原因是存储技术和处理技术的问题，如果按照每个页面的平均大小为 2 0 k 计算( 包含图片等其它信息) ，l o o 亿网页的容量是1 0 0 2 0 0 0 g 字节，即使有足够的空 间存储，下载也存在问题。按照一台机器每秒f 载2 0 k 计算，需要3 4 0 台机器不停的下载1 年时间，才能把所有网页下载完毕。同时，由于数据量太大，在提供搜索时也会有效率方面 的影响。因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页而在抓取的时候评价重 要性的主要依据是某个网页的链接深度。 在抓取网页的时候，网络蜘蛛一般有两种策略：j 一度优先和深度优先。广度优先是指 网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取 在此网页中链接的所有网页。这是最常用的方式。因为这个方法可以让网络蜘蛛并行处理， 提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处 理完这条线路之后雨转入f 一个起始页，继续跟踪链接。这个方法的优点在于网络蜘蛛的设 计相对简单。 8 浙江大学硕士学位论文第一章绪论 1 6 搜索引擎发展趋势 互联网上的第一代搜索引擎大约出现于1 9 9 4 年，以y 曲o o 、舢t a s t a 为代表。当时的 互联网上远没有目前这样庞大的信息量，所以这类搜索引擎的主要目标是提高对整个w 曲 的覆盖率，它们主要以关键词搜索和目录式搜索的形式提供服务。在当时，搜索引擎主要力 求为用户提供尽量“全”的搜索结果。 随着w 曲规模的急速扩大，网站数越来越多，网页数量呈现几何级数增长的趋势，w 曲 已经成为信息和数据的海洋。此时，如果再一味追求尽量“全”的搜索结果，对于用户提交的 搜索请求，搜索引擎将返回成千上万的匹配项用户要在大量的匹配项中找到自己真正需要 的内容，将变得非常困难。因此，提高搜索引擎返回结果的准确率，就显得尤为重要。第二 代搜索引擎的主要目标是为用户提供尽量“准”的搜索结果。为保证能够及时返回对用户真正 有价值的网页。第二代搜索引擎引入了超级链接分析的技术来提高搜索引擎返回结果的准确 率，它们的杰出代表是g 0 0 9 l e 。g g l e 创新性地提出了p a g e r a n l 【排序技术，力求人们能够 在返回结果的最前部分找到他们所需要的信息。凭借简单易用的用户界面和准确可靠的排序 结果，g o o g l e 取得了空前的成功。成为当今世界市场占有率最高的搜索引擎。 随着第二代搜索引擎的逐步成熟，世界各地的科研机构都在进行第三代搜索引擎甚至 更高级搜索引擎的研制。作为新一代搜索引擎，第三代搜索引擎力求在自然语言处理、数据 挖掘、机器自动学习技术、基于内容的媒体搜索等方面有所突破。 在前面提到的传统搜索引擎的弊端中，准确获取用户搜索需求是一个亟待解决的问题， 它直接关系到用户最终的使用体验。为了让大多数用户能方便地进行搜索，使用户能够更加 容易地和搜索引擎进行交互，支持自然语言的输入和理解是新一代搜索引擎最热门的发展方 向。目前，自然语言处理技术已经能够分析结构定义严谨的句子，较好地消除多义词歧义， 从而对句子进行语义层面的分析。但是对于结构定义不是很严谨的句子，自然语言处理系 统日前仍然很难判断其准确的语义。网络上大量的文本信息是以适合人的读取理解习惯存在 的，这使得计算机程序很难对其进行准确识别。【6 j 为了使人机交互更加容易，语义理解是搜 索引擎今后发展的一个必然趋势。 数据、信息、知识是属于三个不同层面的概念。知识是和用户能力及经验紧密结合的、 能够用于解决问题和创造新知识的信息组织，处于三个层面的最高端。互联网上分布着大量 不相关的数据，现代搜索引擎的发展目标就是要对它们进行筛选、组织和分析，发现其中蕴 涵的信息，最终提升到知识的层面并返回给用户。在数据库层面的知识发现k d d 汹o w l e d g e d i s c o v e r yi nd a t a b a s e ) 己得到广泛运用，其中许多技术可以运用到w 曲知识搜索上。【7 】同时， r e b 和传统数据库在很多方面又存在着巨大的差异，如何对k d d 的现有理论技术进行改进 移植，应用到w 曲知识搜索上，是当前搜索引擎研究中的一个难题，同时也是第三代搜索 引擎的重要发展方向。 9 浙江大学硬士学位论文第一章绪论 1 7 本文的工作和组织 本文对专业w 曲c o 蛐u n i t y 识别框架的设计和实现进行了详细地分析，介绍了当前w b b c o 蛐蚰埘识别的已有研究成果和相关技术。在具体的实验数据基础上，对w 曲c o 咖u l l i t y 的收敛性，页面主题判别等进行了研究。 在深入分析w 曲c o m m u n i t y 的相关特征和现有页面主题识别技术的基础上，本文结合 当前常见的w 曲c o 衄u n i l y 识别算法，提出了w 瓯g h 把dk e y w o r dh i 目a f c h i l r e c o g n j t i o n 嘲r ) 识别算法，该算法能够保证较高的页面主题识别准确率，并构建出相 应的w 曲c 0 m m u n i t y 。 同时，本文还描述了在项目的实旖过程中具体遇到的一些问题，着重介绍了网络蜘蛛的 架构设计以及具体实现，同时详细介绍了网络蜘蛛的性能优化等相关技术。 最后，本文通过项目中实现的系统原型进行了相关测试，并对网络蜘蛛的链接发现能力 以及w 曲c o m 枷n i t y 识别准确性等相关数据做了分析说明。 在文章结构的组织上，本文的第一章介绍了搜索引擎的相关背景以及它的基本原理，指 出了当前通用搜索引擎的不足之处，概述了专业搜索引擎的产生背景以及传统搜索引擎和专 业搜索引擎的异同，介绍了w 曲c 【啪u n n y 的特点并指出了进行、e b c o m i i y 识别研究 的必要性。 第二章介绍了w 曲c o n u n u n i i y 识别的基本原理，讨论了识别框架的基本设计思路，介 绍了当前常见的几种w 曲c o m m h i i y 识别算法。 第三章首先介绍了网络蜘蛛的基本原理与结构，然后对网络蜘蛛设计和实现中的主要问 题进行了具体分析，并从网络蜘蛛的内部并行性和外部并行性两方面对网络蜘蛛的性能优化 进行了讨论。 第四章详细描述了基于w b i g h t e dk e y w o r dh i e r a r c h i c a lr e c 0 印i t i m 噬h r ) 识别算法的 w 曲q m u n i t y 识别框架的具体设计。 在第五章，给出了系统原型的设计实现，以及系统的相关测试结果。 第六章对本文作了总结，并就进一步需要研究的问题和研究方向进行了展望。 1 0 浙江大学硕士学位论文 第二章c bc 0 咖n j t y 识别研究及其发展现状 第二章w e bc o m m 岫i t y 识别研究及其发展现状 随着对互联网各个领域研究的深入，w 曲c o m m u n i t y 的相关研究已经取得较大的进展， 并促成了其他一些相关研究领域的发展，尤其是在和专业搜索相关的领域，w 曲c 0 u i t y 技术更是得到了广泛应用。本章将介绍w 曲c m u n n y 识别领域的研究现状以及相关技术， 重点介绍在专业w 曲c o m m i f y 识别领域的相关情况。 w 曲c o m m n y 的识别是一个较为复杂的过程，涉及到网页信息获取、c o m 枷n i l y 识 别以及c o m u n j t y 性质研究等多个步骤。本章将在2 1 节介绍和c o i 砌蚰n y 信息获取相关 的专业网络蜘蛛技术，并在随后的两个小节中对w 曲c o n l “啪i t y 识别的两种主要技术：基 于主题的识别和基于链接的识别进行详细的阐述，最后在2 4 节，本章将对、bc o n l i i m i t y 的重要特性之一：s c a l e f r e e 特性进行深入的讨论。 2 1 专业网络蜘蛛 页面抓取是搜索引擎工作流程中的第一个步骤。通常是由网络蜘蛛完成的。网络蜘蛛在 采集w 曲信息时，通常从一个“种子集”( 如一些初始的种子页面) 出发，通过 r m 协议 请求并f 载w 曲页面，分析页面并提取链接，然后再访问新发现链接，通过这种不断扩散 的方式遍历访问w 曲。从整个l n l e m e t 网络拓扑图来看，网络蜘蛛从一开始几个离散的点， 通过页面间链接形成的边，逐步访问到整个拓扑图上的每一个节点，这是网络蜘蛛典型的工 作方式。按照图的遍历方式来看，网络蜘蛛可以采取深度优先、宽度优先等方式。 单纯的网络蜘蛛技术只是从k c c m e t 上获取网页内容，但是结合其它技术，网络蜘蛛可 以有非常广泛的运用，如站点结构分析、互联网有害信息监控、页面有效性分析以及个性化 信息检索等。 随着搜索引擎技术的不断成熟，网络蜘蛛技术也取得了很大的进展，在信息获取的覆盖 面和性能上都有了很大的提高，但是相对于w w w 上信息的爆炸性增长，现有网络蜘蛛的 信息获取能力还远远不能满足实际需求，尤其是在专业领域信息的获取方面，通用网络蜘蛛 技术更是很难适应实际应用的需要。 当前网络蜘蛛的不足主要体现在以下两个方面： 1 w e b 页面抓取的覆盖率 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的。原因之一是抓取技术 的瓶颈，搜索引擎无法遍历所有的网页，有许多网页无法从其它网页的链接中找到或者由于 访问权限限制而无法访问；另一个原因是存储技术和处理技术的问题，按照每个页面平均大 小为1 0 k 计算，1 0 0 亿网页的容量约为1 0 6g 。尽管以现有的存储技术能够存储这么大的数 据量，但是在下载速度上却存在着严重问题。由于网络的高延时和网络速度本身的限制，按 1 】 浙江大学硕上学位论文第二章w 曲i l l i i t y 识别研究及其发展现状 照1 0 0 0 k b ，s 的下载速度进行计算，一台计算机需要3 0 年时间才能把所有网页下载完毕 而实际中1 0 0 0 髓i s 的速度是远远达不到的。即使采用了并行处理技术，也很难从根本上解 决这个问题。 2 w e b 页面的时效性 w 曲页面内容存在着动态变化的特性每天都有近千万张新网页被添加到w 曲上，此 外，已存在网页中的1 0 左右也会发生变化，网络蜘蛛需要较快的网页抓取速度才能及 时更新相应的信息。考虑到需要更新的信息非常庞大，即使采用大规模s p i d e r 并行技术 网页抓取速度也存在着明显的瓶颈。 在抓取网页的时候，网络蜘蛛一般有两种策略：即图遍历中的广度优先和深度优先。采 用广度优先抓取策略时，网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的 一个链接网页，继续抓取在此网页中链接的所有网页。这是网络蜘蛛通常采用的方式，因为 这种方法可以让网络蜘蛛并行处理，提高页面抓取速度。 造成网络蜘蛛在信息获取方面困难的主要原因是w w w 上所存在的极其巨大的网页信 息。据估计，互联网上可能存在的文件数量高达5 0 0 0 亿p 1 这个数量级的页面信息，不是 任何一个现有的网络蜘蛛或是信息系统所能处理的。相比之下。专业网络蜘蛛关注的只是某 一专业领域的信息，在网页信息的分布上，只是w w w 一个很小的子集。例如，根据相关 人员对医药领域专业网站的分析结果，核心医药领域的专业网站只有2 0 2 个( 相关数据见 5 4 2 节) ，相对于h t c m e t 上数量巨大的站点，这是一个极其微小的子集。 网络蜘蛛的搜索策略与搜索引擎的性质和任务密切相关。为了获得高的w 曲覆盖率， 通用搜索引擎的网络蜘蛛一般尽量遍历到拓扑图地每个节点，通常采用深度优先、宽度优先 或其他改进型的遍历方式。 与通用搜索引擎不同的是，专业搜索引擎服务于特定人群，其索引的页面内容仅限于特 定领域，因此在搜索过程中没有对整个w 曲进行遍历的必要，只需选择与本领域相关的页 面进行访问。 由以上内容可知，专业网络蜘蛛是通用网络蜘蛛的特殊运用，两者的基本原理和结构是 相同的。专业网络蜘蛛和通用网络蜘蛛最大的不同在于，专业网络蜘蛛在搜索w 曲时，需 要对发现的u r l 进行主题预测和识别，对网页是否专业相关作出判断。本文将在后面的相 关章节中详细描述页面的主题识别技术。 2 2 基于网页内容的主题判别 主题判别模型是信息检索( m ) 中一个很成熟的研究领域，本小节主要讨论的是基于内容 的主题判别模型大致有： 1 ) 集合论模型：布尔模型； 2 1 代数模型：向量空间模型； 浙江大学硕士学位论文第二章w c bc o m n m n i l y 识别研究及其发展现状 本文将对常用的布尔模型、向量空间模型进行较为详细的介绍。当前。大多数主题判别 系统依赖于布尔模型，因为其实现晟为简单。此外，也有大量系统采用向量空间模型。相对 于布尔模型，它的判别准确性大大提高，同时计算复杂度也在合理的范围内。 2 。2 1 布尔模型 在构建主题判别系统时，布尔模型是最容易实现的。在布尔模型中，一个文档通过一个 关键词集合来表示。同时，某