（计算机软件与理论专业论文）基于日志分析的增量主题爬虫研究与实现.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机软件与理论 研究方向：基于网络的计算机软件应用技术 作者：2 0 0 7 级研究生徐尚瑜 指导教师：张卫丰 中文题目：基于日志分析的增量主题爬虫研究与实现 英文题目：t h er e s e a r c ha n di m p l e m e n to ft h ei n c r e m e n t a lf o c u sc r a w l e r b a s e do nl o g a n a l y s i s 主题词：主题爬虫，日志分析，主题相关度，网页更新，增量爬行 k e y w o r d s ：f o c u s e dc r a w l e r , l o ga n a l y s i s ，t o p i cr e l a t i v i t yd e g r e e ， s c h e d u l i n gs t r a t e g y 南京邮电大学硕士研究生学位论文 摘要 摘要 面对海量的互联网信息，传统搜索引擎在查找主题信息方面日益无法满足人们的要求， 如何帮助人们及时准确地获取主题信息变得越来越重要，而面向主题搜索引擎技术正是为 此应运而生的。主题搜索引擎是特殊化的搜索引擎，它只面向某一具体的领域或主题，比 起传统搜索引擎能更准确，更广泛的搜集领域或主题信息。然而如何为领域、主题相关性 的判定制定准确的规则，如何有效的分析过滤无关资源保留相关主题资源，如何扩大对主 题资源的搜索的覆盖度，成了主题爬虫系统的研究重点。 本文首先通过与普通网络爬虫工作流程的对比，介绍了主题爬虫的工作原理，接着详 细介绍了主题爬虫使用的关键技术，在此基础上，总结出影响主题爬虫准确度与效率的三 个主要问题：爬虫主题表示、网页主题相关性判断和爬行策略。在深入分析主题爬虫关键 算法的基础上，提出了一种基于日志分析的改进的网页主题相关度计算方法。该方法根据 齐次连续时间马尔科夫过程的性质，通过计算网页间的转移概率矩阵的平稳分布，作为网 页的用户兴趣度估计；结合网页分块算法，分别计算网页文本块的文本主题相关度和相关 链接块的链接关系重要程度。通过综合文本主题相关度、链接重要程度和用户兴趣度这三 个因素，提出一种改进的网页主题相关度计算方法，并通过实验测试，证明了改进的综合 方法的准确度都高于这三个因素的单一使用。 爬虫作为搜索引擎的一个重要组成部分，需要长期运行，如何有效地保证本地镜像的 “新鲜度”成为爬虫研究的一个热点问题。本文根据网页更新符合泊松过程的特点，提出 了一种及时同步本地数据库与远程网站的方法。通过保存的有关网页更新情况的历史记 录，统计出各个网页的更新频率，并以此确定爬虫对该网页的访问频率，并通过实验证明 了基于泊松过程的爬虫调度策略的可行性。 关键词：主题爬虫、日志分析、主题相关度、网页更新、增量爬行调度策略 w i t ht h ed e l u g eo fi n t e m e ti n f o r m a t i o n ，t h et r a d i t i o n a ls e a r c he n g i n e sa r eg r a d u a l l yu n a b l e t om e e tp e o p l e sn e e d si ns e a r c h i n gd o m a i ni n f o r m a t i o n ，h o wt oh e l pp e o p l et of i n ds u c hs p e c i f i c i n f o r m a t i o nt i m e l ya n da c c u r a t e l yi sb e c o m i n gm o r ea n dm o r ei m p o r t a n t ，t h ef o c u s e ds e a r c h e n g i n ei ss u c ht e c h n o l o g yt ot a c k l et h i sp r o b l e m f o c u s e ds e a r c he n g i n ei ss p e c i a l i z e ds e a r c h e n g i n e ，i to n l yf a c e so n ef i e l do ro n et o p i c h o w e v e r , h o wt od e s i g nt h es u i t a b l et o p i cr u l e sf o r d o m a i nc o n c e p t i o n ，h o wt oa n a l y z et h ew e bp a g ee f f e c t i v e l yi no r d e rt on o to n l yf i l t r a t et h e i r r e l a t i v er e s o u r c e s ，b u ta l s og e tt h eh i g h r e l a t i v et o p i cr e s o u r c e s ，a n dh o wt oe n l a r g et h ed o m a i n o ft o p i cr e s o u r c e s ，i sb e c o m i n gv e r yi m p o r t a n ti nr e s e a r c h i n gf o c u s e dc r a w l e rs y s t e m i nt h i sp a p e r , c o m p a r ew i t hw o r kf l o wo ft h et r a d i t i o n a lc r a w l e r , ii n t r o d u c e dt h ew o r k i n g p r i n c i p l ea n dt h ek e yt e c h n o l o g i e so ff o c u sc r a w l e r , o nt h i sb a s i s ，s u m m e du pt h r e ei s s u e s i n a f f e c t i n gt h ea c c u r a c ya n de f f i c i e n c yo ff o c u sc r a w l e r t h ed e f i n i t i o no ft o p i ci nf o c u sc r a w l e r , t h et o p i cr e l a t e dd e g r e eo fw e bp a g e s ，t h ec r a w l i n gs t r a t e g i e s ip r o p o s e dan e wi m p r o v e d m e t h o dj u d g i n gt o p i cr e l a t e dd e g r e eb a s e do nl o ga n a l y s i s i nt h i sm e t h o d ，ie s t i m a t e st h e t r a n s i t i o np r o b a b i l i t ym a t r i xb e t w e e nt h ew e b p a g e s a n dg e ti t ss t a t i o n a r yp r o b a b i l i t yd i s t r i b u t i o n b a s e do nt h eh o m o g e n e o u sn a t u r eo ft h ec o n t i n u o u s t i m em a r k o vp r o c e s s ，t h e nu s ei ta st h e e v a l u a t i o no fu s e ri n t e r e s t c o m b i n e dw i t hp a g eb l o c ka l g o r i t h m ，w ec a l c u l a t et h et e x tt o p i c r e l e v a n td e g r e ea n dl i n k si m p o r t a n c eu s i n gt h et e x tb l o c ka n dt h er e l a t e dl i n kb l o c k w eu s ea b o v e t h r e ef a c t o r st oc a l c u l a t et h ep a g et o p i cr e l a t e dd e g r e e ， c r a w l e ri sa ni m p o r t a n tc o m p o n e n to fs e a r c he n g i n e ，w h i c hr u n sc o n t i n u a l l y , a n dh o wt o e f f e c t i v e l ye n s u r et h e ”f r e s h n e s s ”o ft h el o c a lm i r r o rh a sb e c o m eah o ti s s u ei nc r a w l e rr e s e a r c h b a s e do nt h ew e b p a g e su p d a t e d i nl i n ew i t ht h ec h a r a c t e r i s t i c so fp o i s s o np r o c e s s ，w ep r e s e n ta n e wm e t h o df o rs y n c h r o n i z i n gt h el o c a ld a t a b a s ew i t ht h er e m o t es i t e w ec a l c u l a t et h eu p d a t e f r e q u e n c yo f w e bp a g e sb ys t a t i s t i c st h ep r e s e r v eh i s t o r yp r o d u c tb yc r a w l e r , a n dt h u sd e t e r m i n e t h ed i f f e r e n ta c c e s sf r e q u e n c yo fe a c hw e b p a g e a tl a s t ，w ed e s i g na ne x p e r i m e n tt ov e r i f yt h e f e a s i b i l i t yo ft h ec r a w l e rs c h e d u l i n gs t r a t e g yb a s e do np o i s s o np r o c e s s k e y w o r d s ：f o c u s e dc r a w l e r , l o ga n a l y s i s ，t o p i cr e l a t i v i t yd e g r e e ，s c h e d u l i n gs t r a t e g y i i 南京邮电大学硕士研究生学位论文目录 目录 摘要i a b s t r a c t i i 目蜀毛i i i 第一章绪论1 1 1 研究背景及意义1 1 2 国内外主题爬虫技术研究现状1 1 2 1 搜索引擎技术的发展现状- 1 1 2 2 主题爬虫技术的发展现状3 1 2 3 网络日志分析技术的发展现状4 1 3 本文的研究内容及创新点：6 第二章主题爬虫的关键算法- 7 2 1 网页处理技术：7 2 1 1 h t m l 技术7 2 1 2d o m 技术8 2 1 3 分词技术9 2 2 主题爬虫的主题表示。1 0 2 2 1 基于关键词的表示1 0 2 2 2 基于语义本体的表示一1 1 2 3 网页主题相关性判断1 2 2 3 1 基于文本的主题相关性1 2 2 3 2 基于w e b 链接的主题相关性1 6 2 3 3 基于本体的主题相关性1 7 2 4 爬行策略选择1 8 2 4 1 广度优先爬行18 2 4 2 最好最先爬行j 18 第三章基于日志分析的主题爬虫技术2 0 3 1 日志预处理2 0 3 1 1 会话划分2 1 - i i i - 南京邮电大学硕士研究生学位论文目录 3 1 2 构造用户浏览行为图2 2 3 2 基于日志分析的网页兴趣度计算：2 3 3 2 1 齐次连续时间马尔科夫链简介2 3 3 2 2 用户浏览模型分析2 4 3 2 3q p r o c e s s 与e m c 。2 4 3 2 4 幂法求e m c 矩阵平稳分布2 7 3 2 5 基于b r o w e r a n k 的网页用户兴趣度量2 8 3 3 改进的主题分析方法点2 8 3 3 1 网页分类与分块技术2 9 3 3 2 内容型网页的主题相关度3 0 3 3 3 目录型网页的主题相关度3 3 第四章主题爬虫更新调度分析j 3 6 4 1 泊松过程性质3 7 4 2 网页更新情况3 7 4 3 爬虫调度策略3 9 4 3 1 主题爬虫的网页更新算法4 0 4 3 2 调度策略的实例：一4 l 4 4 实验分析。4 2 第五章主题爬虫系统的关键技术4 4 5 1 主题爬虫系统框架及模块划分4 4 5 2 主题爬虫数据结构设计：4 7 5 2 1 主题爬虫数据库表设计4 7 5 2 2 主题爬虫主要类结构及其关系图4 8 5 3 爬虫系统若干关键模块的实现5 1 5 3 1 爬行优先权队列设计5 1 5 3 2 网页快速去重设计5 3 5 4 主题爬虫系统的实现一5 4 5 4 1 e s e a r c h 主题爬虫配置。5 4 5 4 2 e s e a r c h 主题爬虫初始化5 5 5 4 3 e s e a r c h 主题爬虫运行一5 6 5 5 主题爬虫系统的测试- 5 8 一i v - ， 南京邮电大学硕士研究生学位论文目录 第六章总结与展望6 0 致谢：一6 1 参考文献6 2 v 南京邮电大学硕士研究生学位论文第一章绪论 1 1 研究背景及意义 第一章绪论 随着互联网的不断发展和日益普及，互联网上的信息量爆炸性式的增长。w w w 万维 网技术的出现，以其直观的显示，简单的使用方式，多样的表现形式，成为互联网传播信 息的主要工具。在2 0 0 4 年4 月，全球w e b 页面的总数目至少达到了8 0 亿个和至少存在 5 6 0 亿个超链接，中国的网页数量也超过了3 亿【l 】。于此同时，这种新兴的网络媒介无时 无刻不在影响着人们的生活，截至2 0 0 9 年6 月底，中国网民规模达到3 3 8 亿，互联网普 及率达到2 5 5 2 1 。然而，在浩瀚的信息海洋中，用户往往赶到迷惘，过多的信息使人无 法直接快速的获取有效信息，形成了只依靠综合性的门户网站获取信息的习惯，大大的制 约了互联网的信息多样化的优势，用户在长期使用后，反而会觉得信息量不足。 搜索引擎是一种用于帮助互联网用户查询信息的搜索工具，它以一定的策略在互联网 中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而 起到信息导航的目的。随着w e b 的发展，通用搜索引擎越来越无法满足用户对于某一主题 或学科领域信息的查全率和精度的需求。此外，目前各大主题网站、科研工作人员在搜索 和整理网络主题资源的时候，迫切希望有一种工具或技术来代替或帮助工作人员进行主题 资源的搜集、整理等繁琐的工作。为此主题搜索引擎应运而生。 主题搜索引擎往往只提供关于某一主题或者领域的网络信息，但它针对特定领域的查 询通常可以取得比通用型搜索引擎更好的结果。主题搜索引擎较通用搜索引擎的主要区别 是在网络爬虫方面，通用网络爬虫的目标就是尽可能多地采集信息页面，而在这一过程中 它并不太在意页面采集的顺序和被采集页面的相关主题。这需要消耗非常多的系统资源和 网络带宽，并且对这些资源的消耗并没有换来采集页面的较高利用率。主题网络爬虫则是 指尽可能快地爬行、采集尽可能多的与预先定义好的主题相关的网页。 一 1 2 国内外主题爬虫技术研究现状 ， 1 2 1 搜索引擎技术的发展现状 搜索引擎作为一个为用户提供信息检索的重要工具，它的主要关键技术包括以下三个 方面：爬虫、索引、查询。网络爬虫( c r a w l e r ，s p i d e r ，r o b o t 等) 需要将w 曲网站上的 1 - ， 妻室坚皇奎堂堡主婴壅竺兰垡笙兰兰二兰堕堡 网页下载到本地；索引( i n d e x e r ) 是将本地保存的w e b 网页建立索引，不同搜索引擎的索 引方式各不相同；查询器( s e a r c h e r ) 根据用户输入的关键词查询索引数据，并对检索结 果进行排序和集合运算，再提取网页简单摘要信息反馈给查询用户。中文搜索引擎还需要 使用分词技术，中文分词是将汉语中的一句话分成若干语意上独立的单词项( t e r m ) ，以 便对每个单词进行索引。目前流行的谷歌、百度、雅虎等搜索引擎主要对关键词和内容的 筛选，不会对用户需求专业方向进行划分，称为通用搜索引擎，其结构如图1 1 所示。 索引数据库网页数据库 图1 1 通用搜索引擎结构图 经过了多年发展，搜索引擎的功能越来越强大，更贴近人们的需求。第一代搜索引擎 主要依靠人工分拣的分类目录，其中以搜狐和雅虎为主要代表，由于这种搜索引擎耗费大 量的人力资源，并且无法适应网络日新月异的发展速度，很快就被第二代搜索引擎取代； 第二代搜索引擎依靠机器抓取，建立在超链分析基础上，以谷歌和百度为代表，通过良好 的算法设计和投入大量的硬件资源，它可以自动适应网络规模的扩大，但返回结果参杂大 量的无关信息，令人头疼。针对这方面的不足，人们将重点放在了对搜索结果的处理上， 力求提供更优化的检索结果，于是出现了元搜索引擎、集成搜索引擎和垂直搜索引擎等概 念，但这些技术仅局限于对搜索结果的改进上，同属于第二代搜索引擎。当今，人们对搜 索引擎的定位正从“海量 需求逐步向“精准 转移。虽然第二代搜索引擎技术满足了人 们一定的需要，但由于其通用的性质，仍不能满足不同背景、不同目的和不同时期的查询 请求。目前，第三代搜索引擎技术成为研究的热点方向，其中个性化主题搜索引擎技术就 是针对这个问题而提出的，它为不同用户提供不同的服务，以满足不同的需求。主题搜索 引擎通过收集和分析用户信息来学习用户的兴趣和行为，从而实现主动推荐的目的。 南京邮电大学硕士研究生学位论文 第一 1 2 2 主题爬虫技术的发展现状 主题爬虫可以有效地减少采集页面的数量，增加了采集页面的规整程度，同时 了网络带宽，提高信息搜索的效率。主题网络爬虫的基本思路就是按照事先给出的 通过分析已经下载保存的父页面中的网页内容和链接关系，判定该网页的主题相关 时预测子页面u r l 的主题相关度，保证尽可能多地爬行、下载与主题相关的网页， 少地下载无关网页，图1 2 是两种爬虫的工作流程比较。目前国际上有关主题爬虫 的几种算法策略。 圃 获取u 网页i l 解析其中u r l ，去 l 重，加入待爬队列 z s 图1 2 普通爬虫与主题爬虫的工作流程对比 f i s hs e a r c h 【5 1 算法于1 9 9 3 年由荷兰t u e 大学的d e b r a 教授提出，并应到了当时流行的 m o s a i c 浏览器上。该算法是对鱼群觅食及产生后代过程的动态模拟，其核心是动态维护u r l 链接在队列中的顺序。该算法把u r l 链与鱼群相对应，主题相关网页与食物相对应，鱼群 是否可以生存取决于爬行的网页是否主题相关。每读取一个文档也就是指鱼找到食物，鱼 群就繁殖一定数量的后代，这里的繁殖后代是指再增加访问这里网页的链接深度，t 文档若 相关，鱼的生命力就越来越弱，后代也较少。如果鱼群穿过一系列主题无关网页，那么鱼 群的生命力会渐渐减弱而最后死去，即会把u r l 链接放入队列的最后。f i s hs e a r c h 算法的 动态特性和它相对的简单易行使它在实时搜索中到了大量的使用，但是它的p o t e n t i a l s c o r e - 3 - 南京邮电大学硕士研究生学位论文第一章绪论 是二值( 0 ，1 ) 设置，即网贞的关性仅仅是根据简单关键词或者语言规则匹配进行一种简单 的相关或不相关二元判断，却显得粗糙。 m i c h a e lh e r s o 访c i 【6 1 对f i s hs e a r c h 算法进行了改进，提出了s h a r ks e a r c h 法。该算法考 虑到f i s hs e a r c h 算法仅通过简单的二值进行网页的相关性判断过于粗糙，故引入了向量空 间模型，对主题相关性的评价进行细化。该算法的主题相关度主要受三个因素影响：链接 文本、链接上下文和对父结点相性的继承。 j c h o 等人提出通过先采集重要的网页来使采集更有效，进而提出了各种计算网页重要 度的方法【1 2 1 ，如网页与查找项的相关性、指向该页的网页个数( b a c k l i n k s ) 、该网页的 p a g e r a n k 值和该网页所处的位置。该方法考虑了网页重要度，而忽略了网页和特定主题的 相关度。结果，按照此方法设计的网络爬虫很快就失去了特定主题的方向，采集很少的主 题网页。因此，发现和预测主题网页是聚焦爬虫中关键问题。 r e n n i e 和m c c a l l u m 将巩固学) - - - j ( r e i n f o r c e m e n tl e a r n i n g ) 8 1 引入网络爬虫模型【7 1 。巩固学 习算法的优势在于能够预测远期回报价值。该算法把搜索过程划分为训练和搜索两个阶 段，训练阶段利用巩固学习算法计算每个链接的价值，并按价值大小将链接分成若干类， 并用每一类中链接的文本信息训练一个分类器在搜索阶段，面对价值未知的链接，则根据 分类器来预测和选择未来回报较大的链接进行搜索。该方法实现起来较复杂，。而且虽然可 以近似预测链接的价值但是却无法估计离目标页面的远近。 d i l i g e n t i 等研究者【9 1 提出基于语境图( c o n t e x tg r a p h ) 的爬行算法，该算法利用通用搜索 引擎获得的w e b 拓扑结构知识来训练一个机器学习系统，指导爬虫判断搜索方向和深度。 该算法过渡依赖其它搜索引擎且复杂度较高。 主题爬虫的搜索策略大致可以分成二类：基于内容的搜索策略和基于链接结构的搜索 策略。基于内容的搜索策略来源于文本检索，拥有很好的理论基础且容易计算，但是它忽 略了网页链接结构信息，所以在预测相关u r l 的准确度不高，其典型代表为f i s h s e a r c h 算法和s h a r k s e a r c h 算法。基于链接结构的搜索策略通过分析网页间的链接关系来决定网 页重要度，进而决定u r l 访问顺序，其典型代表为p a g e r a n k 算法和h i t s 算法【1 1 1 。在某 些条件下，h i t s 会出现“主题漂移”( t o p i cd r i f t ) 题，而p a g e r a n k 仅仅能够发现权威网页 或重要网页而不是主题网页。 1 2 3 网络日志分析技术的发展现状 传统意义上的w e b 日志挖掘技术就是从w e b 服务器的日志中发现用户的访问模式，分 - 4 塑室坚皇查兰堡圭堕壅竺兰垡堡茎笺二皇堑笙 析站点的使用情况。通过对w e b 日志的挖掘，可以发现用户访问页面的模式，改进w e b 站点的性能和结构，提高查找信息的质量和效率，增加个性化服务，在电子商务中发现潜 在的客户群。整个w e b 日志挖掘主要分为三个步骤【1 4 1 ： ( 1 ) 数据预处理：根据挖掘的目的，将原始w e b 日志文件中的数据进行提取、分解、 合并，最后转化成适合进行数据挖掘的格式，并形成用户会话文件，等待进一步的处理。 ( 2 ) 模式识别：运用各种算法对处理后的数据进行挖掘生成模式。该阶段的任务是识 别出用户访问模式。可采用以下算法来实现：序列模式识别、关联规则、分类聚类、统计 分析等。 ( 3 ) 模式分析：进行用户访问模式的分析，从而将有价值的模式提取出来的过程。其 中数据预处理这个环节是整个过程的基础和实施有效挖掘算法的前提，在w e b 日志挖掘中 起着非常重要的作用。 w e b 日志挖掘可以分为以h a n 为代表的基于数据立方体的方法和以c h e n 为代表的基 于w e b 事务的方法。c h e n 等人首先将数据挖掘技术应用于w e b 服务器日志文件，以期发 现用户浏览模式【1 5 1 。他们提出了最大前向引用序列m f r 的概念，并用它将用户会话分割 成一系列的事务，然后采用与关联规则相似的方法挖掘频繁浏览路径。h a n 等人则根据 w e b 日志建立数据立方体，然后对数据立方体进行数据挖掘和o l a p 1 6 】。m i n n e s o t a 大学 的w e bm i n e r 系统提出了一种通用的w e b 日志挖掘的体系结构，该系统能自动从w e b 日志中发现关联规则和序列模式等【1 7 】。 文献【1 8 , 1 9 1 提出了通过用户协作、学习浏览模式来抓取网页的方法。协作抓取需要获取 用户浏览行为，一般有两种方法：日志挖掘和用户标注。文献【1 8 】提出了用户浏览模式挖掘 法，对与某一特定查询谓词相关的网页作相似性建模。以大量公共域名代理的用户访问日 志为参考，经过对大群组用户信息过滤，统计并总结出了三种需要考虑的用户访问信息： 对不同网页访问频率；对不同网页特征访问频率；访问同一主题网页的时间局域性。其中， 试验表明，协作抓取比基于链接的智能抓取( i n t e l l i g e n tc r a w l i n g ) 策略有更好的准确性。 文献【旧】贝0 以用户在浏览过程中，对“有用”网页进行显式标注的网页集合为参考。利用 隐含马尔可夫模型( h i d d e nm a r k o vm o d e l ) 适于进行动态模式识别模型的特性，学习用户 的浏览行为，预测不同网页聚类之间的语义联系。 本文所使用的日志分析技术是将传统的日志挖掘技术应用于搜索引擎方面，利用w e b 日志可以获得页面的点击次数、页面停留时间和页面访问顺序等信息。通过分析w e b 日志 可以获得相关页面、用户对页面的兴趣度、相似用户群体和用户访问模式等信息，来指导 主题爬虫获得更有价值的页面。 5 - 南京邮电大学硕士研究生学位论文第一章绪论 1 3 本文的研究内容及创新点 本文首先介绍了课题的研究研究背景及意义，然后通过与普通网络爬虫工作流程对比 介绍了主题爬虫的工作原理，接着详细介绍了主题爬虫使用的关键技术，从爬虫主题表示、 网页主题相关性判断和爬行策略选择三个方面介绍了主题爬虫的主要算法。对主题爬虫的 关键算法网页的主题相关性判断方法进行了详细介绍。 在深入分析主题爬虫关键算法的基础上，提出了一种基于日志分析的改进的网页主题 相关度计算方法。该方法通过服务器端和客户端的用户访问日志构造用户浏览行为图，建 立网页间的转移概率矩阵，根据齐次连续时间马尔科夫过程的性质，计算转移概率矩阵的 平稳分布，即矩阵的最大特征向量。使用转移概率矩阵的平稳分布，作为网页的用户兴趣 度估计。改进的网页主题相关度的三个影响因素分别为：基于网页文本内容分析的主题相 关度、基于网页间相互链接关系的链接重要程度和基于日志分析的网页用户兴趣度。并通 过在第五章的实验测试，证明了该方法的准确度都高于这三种方法的单一使用。 第四章主要讨论了主题增量爬虫的调度方法。根据网页的更新情况都符合泊松过程的 特点，设计了一种适合网页更新变化频率的动态爬虫调度算法，通过本章的实验证实了此 调度方案确实可以及时地发现更新的网页，在节省资源的同时，也起到了很好的效果。 第五章是主题爬虫系统原型系统的具体实现部分。在主题爬虫系统框架分析、功能模 块划分的基础上，讨论了主题爬虫实现的主要数据结构及类关系。特别地，对影响爬虫性 能的关键模块，优先权队列和u r l 去重模块进行了重点分析。最后，对本文提出的基于 日志分析的网页主题相关判别方法与传统的基于文本和链接关系的方法进行对比测试，分 析实验结果。 本文主要创新点如下： ( 1 ) 分析用户对某网站的访问日志，构造用户浏览行为图，建立网页间的转移概率矩 阵，根据齐次连续时间马尔科夫过程的特点，计算转移概率矩阵的平稳分布，以此来估计 网页的用户兴趣度。 ( 2 ) 将按照上述方法计算的网页用户兴趣度作为影响网页主题相关度的一个因素。将 网页分为内容型网页和目录型网页两种，然后再通过网页分块进一步过滤噪声信息，提取 内容型网页中的文本及相关链接( 相关块中的链接) ，计算文本主题相关度和链接重要程 度，对目录型网页采取先预测，再计算的方式来进行主题相关度评价。 ( 3 ) 根据网页更新符合泊松过程的特点，提出一种可以根据网页更新频率，动态调整 爬行频率的调度策略，及时发现更新的网页。 - 6 一 南京邮电大学硕士研究生学位论文第二章主题爬虫的关键算法 第二章主题爬虫的关键算法 目前主题爬虫的研究已经相对成熟，关键技术和讨论热点主要集中在以下三个方面【3 】： ( 1 ) 如何描述主题( 主题的定义) ( 2 ) 用何种方式判断网页的主题相关性 ( 3 ) 如何决定待爬网页的顺序( 确定待爬u r l 的优先级) 2 1 网页处理技术 文本分类是指在预定义的分类体系下，根据文本的特征( 内容或属性) ，将给定文本与 一个或者多个类别联系起来的过程，因此，文本分类实际上涉及文本内容理解和模式分类 等若干自然语言理解和模式识别问题。一个文本分类系统不仅仅是一个自然语言处理过 程，也是一个典型的模式识别系统，该系统的输入是需要分类处理的文本，系统的输出则 是与文本关联的类别。 2 1 1 h t m l 技术 w e b 上大部分的文本信息都是以h t m l 网页的形式存在的。h t m l 是一种标识语言 ( m a r k u pl a n g u a g e ) ，它利用各种标记( t a g s ) 来控制超文本中资料的显示方式，如文字的颜色、 大小、文档的结构以及标识超链( h y p e r l i n k ) 等。通常，h t m l 文档主要分为三大部分： ( 1 ) 文本：这里的文本是指h t m l 页面上除了脚本代码和标签外的文字部分，这些 文字构成页面正文的一部分，并由标记层对其进行控制。 ( 2 ) 标记：标记是出现在正文中以字符“ 结尾的一个字符串，通 常成对出现，是用于描述功能的符号。 ( 3 ) 注释：注释是h t m l 文档中不显示的部分，通常是程序员对程序的功能说明。 事实上，有许多h t m l 文档中的标记不符合h t m l 语法要求，比如缺乏结束标记等。 这些错误影响对h t m l 文档的正确解析，因此，为便于解析，首先要对h t m l 文档进行 整理，将其转换成x h t m l 文档，x h t m l 严格建立在x m l 基础之上，并且明确定义了 格式良好的文档规则。这样就可以像对待一般x m l 文档一样对待x h t m l 文档，可以利 用各种x m l 标准技术来操纵x h t m l 文档。对h t m l 文档的整理主要是以下三个方面： ( 1 ) 为不成对的标记加上结束符“”，例女f l 3 1 j 上结束符为 ： 7 - 南京邮电大学硕士研究生学位论文 第二二章主题爬虫的关键算法 ( 2 ) 为所有属性值加上引号，例如， j j h 上引号变为 ： ( 3 ) 将u r l 中所有的“”换成“”。 通过上面的三种方式，对下载的网页进行预处理，规范化h t m l 网页，是下一步进行 网页分析的基础。 2 1 2d o m 技术 w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 的文档对象模型d o m ( d o c u m e n to b j e c tm o d e l ) 根 据文档中标记之间的嵌套关系，将文档表示为一个树形结构，文档中的元素、属性、文本、 注释以及处理指令等都是节点。于是人们可以利用d o m 树的形式来表示h t m l 文档，其 中d o c u m e n t 是文档根，是操作整个d o m 树的句柄，h t m l 文档中的每个成分都是一个 节点，h t m l 文档的d o m 表示是这样规定的： ( 1 ) 整个文档是一个文档节点 ( 2 ) 每个h t m l 标签是一个元素节点 ( 3 ) 包含在h t m l 元素中的文本是文本节点 ( 4 ) 每一个h t m l 属性是一个属性节点 ( 5 ) 注释属于注释节点 h t m l 文档中的所有节点组成了一个文档树( 或节点树) 。h t m l 文档中的每个元素、 属性、文本等都代表着树中的一个节点。树起始于文档节点，并由此继续伸出枝条，直到 处于这棵树最低级别的所有文本节点为止。图2 1 形象表示h t m l 网页对应的d o m 树。 图2 1h t m l 网页对应的d o m 树 当解析生成d o m 树之后，对h t m l 文档中信息的提取，就转换成为对d o m 树中相 8 南京邮电大学硕士研究生学位论文第二章主题爬虫的关键算法 应节点的查找，节点位置由定位规则指出，提取模式中的模板按照定位规则的指示提取出 相应位置的信息。 主题爬虫在获取网页后，需要对网页的内容和链接进行主题相关性分析，预测主题相 关u r l ，指导下一轮的爬行。通过将h t m l 网页转换成d o m 树的形式，我们可以方便地 提取其中的文本和链接信息。 2 1 3 分词技术 单词是最小的有独立意义的语义单位。汉语中的单词，不同于英文环境使用空格分隔 单词，是由若干个连续的字组成一个有意义的词。在汉语中的句子成分中，词与词、字与 字之间没有分隔标记，计算机难以直接处理，因此，中文词法分析是中文信息处理的基础 与关键。近十多年来，语言学界、人工智能领域和情报检索界的学者们，在汉语自动分词 与自动标引的研究与实践上进行了大量的研究，找到了许多解决汉语分词的方法。归纳起 来，目前国内公开报道过的分词系统采用的分词方法主要有三种类型【4 7 】： ( 1 ) 机械分词法。机械分词法是目前最常用的分词法，效果较稳定。常用的算法有最 大匹配法( m m 法) 、逆向最大匹配法( r m m 、o m m 、i m m ) 、逐词匹配法、部件词典法等。 ( 2 ) 语义分词法。语义分词法引入了语义分析，对自然语言自身的语言信息进行更多 的处理，如扩充转移网络法、知识分词语义分析法、邻接约束法、综合匹配法等。 ( 3 ) 人工智能法，又称理解分词法。人工智能是对信息进行智能化处理的一种模式， 主要有两种处理方式：一种是基于心理学的符号处理方法，通过模拟人脑的功能，构造推 理网络，经过符号转换，从而可以进行解释性处理；一种是基于生理学的模拟方法，旨在 模拟人脑的神经系统机构的运作机制来实现一定的功能。 本系统使用中国科学院计算技术研究所开发的i c t c l a s 中文分词系统【4 8 1 ，它的主要 思想是先通过c h m m ( 层叠形马尔可夫模型) 进行分词，通过分层，既增加了分词的准确 性，又保证了分词的效率。i c t c l a s 采用的是n 最短路径的词语划分方法，基本思路是： 先进行原子切分，然后在此基础上进行n 最短路径粗切分，找出前n 个最符合的切分结 果，生成二元分词表，然后生成分词结果，接着进行词性标注并完成主要分词步骤。该系 统的功能有：中文分词；词性标注；未登录词识别，分词正确率高达9 7 5 8 。 系统的词库是二元的隐马尔可夫概率矩阵，即扩展名是d o t 的文件，关键的部分就是字 典，搞清楚字典的结构对我们进一步研究分词系统有很大的帮助。在这套分词系统中，有 两种结构的字典，一种是保存常用词的词典，另一种是保存上下文关系的词典。i c t c l a s 塑室塑皇奎兰堡主塑塞圭兰堡垒奎茎三童圭望墨坐塑茎壁簦鲨 分词程序首先调用i c t c l a s _ w i n d i g ：o n b t n r u n ( ) j i ：t ：始程序的执行。处理方法是将源字符 串分段处理。并且在分词前，。完成词典的加载过程，即生成i c t c l a s 对象时调用构造函 数完成词典库的加载。 2 2 主题爬虫的主题表示 主题爬虫的主题表示是对爬行目标的精确定义，作为主题爬虫的行为标准，指导爬行 的全过程，“告诉 主题爬虫哪些网页是主题相关的。好的主题表示可以快速、准确地发 现目标网页、过滤不相关网页。现有的主题表示方式主要有基于关键词的主题表示和基于 语义本体的主题表示两种方法。其中基于关键词的主题表示方法为大多数主题爬虫采用， 但关键词的选择对爬虫的准确率影响很大，需要由经验的专家进行关键词选择；基于语义 本体的主题表示方法充分利用汉语中词与词之间的关系，进行语义和知识关联，使用本体 的概念解释领域中的主题。 2 2 1 基于关键词的表示 在主题爬虫研究的早期阶段，人们针对某一主题领域选择若干个具有代表性的关键词 来描述主题概念。简单关键词选择的方法实现起来简便，主题描述所采用的关键词向量， 一般是由人工选取并设定值。这种方法有如下缺陷： ( 1 ) 由于人工指定关键词，主题描述全面性较差； ( 2 ) 不能适应主题的变动性，对于活跃的主题，不发现新的主题词； ( 3 ) 仅仅从少数人的角度出发，缺乏用户反馈。 通常人为选择关键词，受很多不利因素的限制，特别是当用户对某一领域没有充分了 解，选择的关键词不具备代表性、遗漏很多重要关键词，这样爬行的结果就会产生较大偏 差。为了减少用户主观方面产生的不利影响，还有一种方法就是使用主题样本页面，所谓 主题样本页面就是在某一领域中具有一定的代表性、用户访问量较大的页面。在条件允许 的情况下，用户可以根据访问日志选择流行度较高的主题相关页面，抽取其中的文本内容， 计算共有关键词的价值度，找出价值度高的关键词，作为主题关键词的补充。 使用用户定