（计算机科学与技术专业论文）面向主题互联网视频搜索引擎关键技术研究.pdf

独创性声明及关于论文使用授权的说明 独创性声明 舢1 1 l l l 1 1 1 1 i 川l l i l l l l l i l y 17 8 8 3 6 7 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名： 赴0 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名： 摘要 摘要 随着y 0 u t l l b e 、优酷、土豆等互联网视频网站的迅猛发展，互联网视频数 量呈爆炸式增长。面对海量的互联网视频，如何从这些海量视频中准确、便捷 地找到所需视频，如何高效使用这些网络视频面临着巨大的挑战。尽管目前通 用搜索引擎做了很多研究工作，但是单纯为了追求检索内容覆盖率，为用户提 供的搜索结果往往是不划分主题、内容广泛的信息，仍然无法完全满足用户的 需求，在检索结果的准确性、覆盖率与时效性等方面都还存在诸多不足，在面 向主题的互联网视频搜索领域，传统搜索引擎依然面临巨大的技术挑战。 近年来，面向主题搜索的研究工作得到人们越来越多的关注。通过对主题 相关的数据内容的有针对性的收集与分析，面向特定主题搜索可以更高效地呈 现结构更清晰的数据结果。其应用范围十分广阔，而视频内容在互联网发展中 所占比重越来越大，针对互联网视频领域的面向主题搜索必将有更大的研究价 值与意义。 通过结合c o c i t a t i o n 算法的思想，本文提出了针对互联网视频信息的面 向主题采集方法，并通过基于链接窗口的方法对其进行了改进。运用信息抽取 的基本思想提出了基于极大并列子树族的相关链接集合概念以及生成算法并引 入窗口变量，使得互联网视频信息抽取方法能够将页面结构信息、已采集链接 的主题相关性以及互联网拓扑结构信息三类信息有机的结合，从而进一步提高 了面向主题的互联网视频信息抽取方法的主题采集精确性。 本文提出了一种面向互联网视频的复杂命名实体抽取模型。复杂命名实体 的识别不仅能够形成一种重要的数据资源，给互联网视频的信息抽取提供基础， 还有助于搜索引擎理解用户的查询意图，从而给出有针对性的、整合的搜索结 果。但是其识别工作尚未得到充分的研究。本文将复杂中文命名实体研究引入 到互联网视频搜索领域，对面向主题的互联网视频搜索有着非常重要的贡献。 本文设计了一种支持大规模主题搜索的可适应分布式框架。通过充分挖掘 利用互联网社区中的搜索日志，设计了基于m a p r e d u c e 计算框架的可并行处 理大规模w r e b 文档的可适应分布式框架。 i 北京 _ 业大学工学硕士学位论文 通过本文实验分析表明，本文中所提出的方法、模型对于面向主题视频搜 索有着明显的改进作用，对于改进用户体验、提高视频信息抽取效率有着显著 效果。 关键词面向主题采集；面向主题视频搜索：中文复杂命名实体；命名实体识 别：信息检索 a b s t r a c t a bs t r a c t w mt h er 印i dd e v e i o p m e n to fi m e m e tv i d e os i t e s ，s u c h 弱y 0 u t u b e ，y o u | ( u t u d o u ，e t c ，t l l e r ei s a i le x p l o s i v eg r o w 山i l l l ei n t e m 武v i d e on 啪b e r f a c i l l g m a s s i v ei n t e m e tv i d e o s ，也e r ei sa 伊e a tc h a l l e n g eo nh o wt 0a c c 眦a t e l ya 1 1 dq u i c h y f i n dt 1 1 ev i d e o s ，a n dh o wt 0e m c i e m l yu s em ei i l t e m c tv i d e o s 舢血o u 曲g e n e r a l s e a r c he 1 1 9 i n e sh 嬲d o n eal o to fr e s e a r c hw o r l ( s ，b u ts t i l lc a l l l l o t 如l l ys a t i s 黟t ：h e n e e d so fu s e r s ，b e c a u s et h e yp r 0 v i d eu s e r s 谢mn os u b - t o p i c si n j o 咖a t i o nf o rs h p l y p a ya t t e n t i o nt ot l l ec o v e r a g eo fr e t r i e v a l t h e r ei sm a u l yd e f i c i e n c i e si i l 也ea c c u r a c y ， c o v e r a g e 锄dt i i i l e l i i l e s so fs e a r c hr e s u l t s 1 1 1t o p i c o r i e n t e di n t e m e tv i d e os e a r c 也 h l l g et e c h i l i c a lc h a j l e n g e sc o m et om eg e n e r 甜s e a r c he n g i n e s r e c e n t l y ，n l er e s e a r c ho ft o p i c - o r i e m e ds e a r c h e si sg e t t i i 培p e o p l em o r e 觚d m o r ea t t e m i o n s t h es p e c i f i cs u b j e c t o r i e m e ds e a r c hc a np r 0 v i d eu s e r s 血f o m a t i o n m o r ec l e a r l ya r l dm o r ee 伍c i e n t l y m r o u 曲t h et a 唱e t e dc o l l e c t i o na i l d 锄m y s i so ft h e r e l e v a n tc o n t e m t m sp a p e rp r o p o s e sat o p i c - o r i e m e dc o l l e c t i o nm e t h o do fh l t e m e tv i d e o s ， d r 赫g o nt h ei d e ao fc o c i t a t i o n s 出g o r i t l m l a n dw ei 】n p r o v et h em e t h o d 丽t l l 也cl i l l l 【- 、i i l d o w s t t l ec o n o 印t 觚dg e n e m t 岖a l g o r i t ho fm er e l a t e dl i l l l 【s e t s b a l s e do nn l em a x i r n u mp a m l l e ls u 【b t i e ef 锄i l yi sp r o p o s e du s i i l gt l l eb a s i cm o u g h t o ft h e 抽面m l a t i o ne x 仃a c t i o n ，a n dw i l l d o w sv a r i a b l e s 孤ei 1 1 灯o d l l c e d s o 曲l a t 也e a c c u r a c yo ft l l et o p i cc o l l e c t i o ni si m p m v e d 凡n 1 1 e r t h i sp 印e rp r o p o s e saw e bv i d e oo r i e n t e dm o d e lt oe x t r a c tc o i n p l e xn a i l l e d e n t i t i e s c o i l l p l e xn 锄e de n t i t yr e c o g l l i t i o nc a i 1 0 tf o r mo i l l ya 1 1i m p o r t a n t 血t a r e s o u r c eo nm ei m e m e tt 0p r o v i d eab a s i s f o ri i l f i o m l a t i o ne x 位i c t i o n ，b u ta l s 0 l e v e r a g es e a r c he n g i r l e st oh e l pt 0u n d e r s t a j l dt l l eu s e r sq u e 巧i 1 1 t e n t s ，w i l i c h 西v e t a 唱e t e d ，i n t e 掣a t e ds e a r c hr e s u l t s t h e r ei s av e 巧i m p o r t a n tc o m r i b u t i o nf o r 协昀d u c i n gt l l er e s e a r c ho fc o m p l e xi 埝n l ee n t i t ) ri n t ot h ei i l t e h l e tv i d e o i i l 北京t 业大学t 学硕十学位论文 t m sp 印e rd e s i g i l s 姐a d 印t i v ei n e t l l o dt o s u p p o r te f l 宅c t i v es e a r c m i 坞o v e r l a 唱e s c a l ew e bd o c 眦e n t s i r it i l ea d a 【p t i v em e t h o d ，l o g i s t i cr e g r e s s i o n 谢t l lt 1 1 - i s t r e g i o na p p l i e d i i l m a p - r e d u c ee n v 的眦e n ti sd e v i s e d ， a i l di t p r o c e s s e s 血e l 鹕e s c a l ew e bd o c 啪e n t si np a r a l l e l t h u si t c a u le 髓c t i v e l yc l 弱s 坶t l l ew e b d o c u m e m sq u e r i e db yt h ed y n 锄i ci 1 1 1 p r e c i s e a r c l l i n g w i mt h e s er e s u b ，t h e m e t l l o do 唱砌z e st l l e mw i t l l 丘i e q u e n c yt r e ew h j c hs h a r e sr e d l i n d a n tc o n t e n t s 锄d r e c o r d st l l ec o u n t i n gf o rr a i l l ( i n g e x t e n s i v ee x p e r i m e n t sd e m o n s 吼t et h em 耐t so f o u ra d 卸t i v em e t l l o dt os u p p o r tt l l ee x p l o r a t o 巧s e a r c h e x p e r i m e n t a lr e s u h ss h o wt h a t 位m e t h o d 锄dm o d e lp r o p o s e db yt h i sp a p e r m a k et 1 1 et o p i c - o r i e n t e d 、e bv i d e o 。s e a r c hi i n p r o v i i l gm u c h ，b r i n gab e t t e ru s e r e x p e r i e n c ea n di n l p r o v et l l ee f f i c i e n c yo fv i d e oi i l f o 珊a t i o ne x t e a c t i o ns i g l l i f i c a n t l y k e y w o r d st o p i c o r i e n t e dc o l l e c t i o n ；t o p i c o r i e n t e dv i d e os e a r c h ；c h i i l e s ec o m p l e x n 锄e de m i t i e s ；i l a m e de n t i t ) rr e c o 鲥t i o n ；i n f o n n a t i o nr e t r i e v a l 摘要 目录 a b s t r a c t i 第l 章绪论 i i 。1 1 1 课题研究的背景1 1 2 面向主题搜索介绍2 1 3 面向主题搜索技术研究意义3 1 4 论文的主要工作3 1 5 本文章节安排4 第2 章课题的研究现状和分析 7 2 1 面向主题的互联网信息采集的研究现状7 2 1 1 面向主题采集7 2 1 2 基于文本的主题预测技术1 0 2 1 3 主题预测与u r l 相似度模型：1 2 2 1 4 主题预测与互联网页面拓扑结构1 2 2 2 复杂命名实体研究现状1 4 2 2 1 命名实体识别1 4 2 2 2 复杂命名实体相关研究15 2 3 本章小结一1 5 一 第3 章针对互联网视频的面向主题采集 1 7 3 1 引言- 1 7 3 2 基于c o c i m 玎i o n 算法的采集方法1 7 3 2 1c o c i t a t i o n 算法介绍1 7 3 2 2 基于c a c i t a r i o n 的主题采集1 8 3 2 3 基于链接窗口的改进方法2 0 3 3 互联网视频信息抽取2 2 3 3 1 信息抽取与面向特定主题的搜索2 2 - 3 3 2 网页信息自动化抽取工具r o a d r u n n e r 2 3 3 4 相关链接集合2 3 3 4 1 相关链接集合的定义2 4 3 4 2 相关链接集合的生成算法2 6 3 4 3 基于相关链接集合的面向主题视频采集方法2 7 3 4 4 实验结果与分析2 8 3 5 多窗口变量的融合方法3 0 3 6 更多形式的窗口变量3 1 - 3 6 1 文本相似度距离窗口3 2 3 6 2 链接相似度窗口3 3 3 7 本章小结3 3 第4 章面向互联网视频的中文复杂命名实体提取模型 一3 5 4 1 引言3 5 4 2 中文复杂命名实体3 5 4 2 1 中文复杂命名实体介绍3 5 4 2 2 中文复杂命名实体的研究意义3 6 4 3 面向互联网视频的中文复杂命名实体提取模型3 6 4 3 1 互联网视频文本信息抽取3 7 4 3 2 视频文本中的特征词选择3 8 一 4 3 3 互联网视频中的复杂命名实体识别4 0 4 4 实验结果与分析4 1 4 5 本章小结4 3 第5 章支持大规模高效搜索的可适应分布式计算框架 4 5 5 1 引言4 5 5 2 支持大规模高效搜索的可适应方法概述4 5 5 3 相关研究4 6 5 4 利用l o g i s t l c 回归组织搜索轨迹4 6 5 4 1 可信区域内的二阶逻辑回归4 7 5 4 2 计数频率树4 9 5 5 实验结果与分析5 0 5 6 本章小结5 2 结论 参考文献 攻读硕士学位期间所发表的学术论文 驾【 射 一5 5 - 5 7 。6 1 第1 章绪论 1 1 课题研究的背景 第1 章绪论 搜索引擎是指通过自动的从互联网中搜集信息，并经过相应的处理后，给 用户提供查询帮助的系统。互联网上的信息是海量且毫无秩序的，所有的信息 像汪洋中的一个个小岛，网页链接是这些小岛之间纵横交错的桥梁，而搜索引 擎，则为用户绘制一幅一目了然的信息地图，供用户随时查阅【。现在，搜索 引擎已经成为了互联网用户获取想要知道的信息所不可或缺的工具。g 0 0 9 l e 更 是成为了全球和中国互联网用户访问量最大的网站【2 】。通过使用搜索引擎，我 们检索信息的能力获得了极大的提高，成本也有效地降低。可以说，搜索引擎 是现代计算机技术、互联网技术与传统信息检索理论相结合的典范。 通用搜索引擎为用户提供了不限定主题、内容广泛的信息搜索服务，为了 保证检索内容的覆盖率，搜索引擎希望能够索引尽可能多的内容。同时为了保 证检索结果的时效性，需要尽可能减少索引库与数据源网站数据同步的延时。 网站和网页的数量非常庞大且增长迅速的，据统计互联网网站数量超过l 亿， 静态网页的数量在1 0 0 亿数量级以上。同时，网页的更新率非常高，据统计c o m 网站的首页内容平均每n 天就有5 0 的网页更新。搜索引擎很难索引如此海 量的网页数据，跟踪网页更新也需要耗费大量的时间和资源【j j 。 与此同时，传统搜索引擎提供信息的展现形势比较单一，都是以根据查询 内容与结果文档的匹配程度，从结果页面的正文中抽取一段摘的形式展现给用 户。但有时候用户的查询总是带有特定信息的，比如用户查询“电视剧名称”、 “电影名称 时，用户很可能想得到的信息是该视频的网络播放地址抑或是该 视频的评论，而且这些信息往往都以固定的模式出现在这些结果网页当中，但 是通用搜索引擎却不能结构化的提取其中的内容，无法满足用户的个性化需求 【4 】 o 在通用搜索引擎面临上述难以解决的问题时，面向主题的搜索引擎( 又叫 垂直搜索引擎) 诞生了。如面向新闻内容、图片内容、视频内容、面向科技文 献等各种针对特定领域、特定主题、特定网站类型的搜索引擎。面向主题的搜 索引擎只对特定网站或特定主题的网页进行索引，从信息采集的角度，面向主 题的搜索引擎需要过滤与主题无关的内容，从而减少了网页采集和分析的数据 规模。同时面向主题的搜索引擎可以利用领域知识和特点，通过具有特色的采 集调度和内容抽取技术，实现比通用搜索引擎获取网页更高的效率，并提高信 北京丁业大学工学硕士学位论文 息抽取的质量，使查询结果在展现上更加结构化。 下表是目前国内互联网的一些著名的垂直搜索站点的简要介绍： 表1 1 垂直搜索站点介绍 t a b 1 - ld e s c r i p t i o no f v e n i c a ls e a r c hs i t e 般搜索引擎的组成部分包括：网页采集、信息抽取、建立索引、提供检 索四个大部分。面向主题的搜索引擎的网页采集，即为本文所阐述的研究课题， 我们将其称为面向主题的互联网信息发现和采集( f o c u s e dc r a w l i n 2 ) 。面向主 题的网络信息发现和采集的主要目标是在有限资源的情况下，高效收集与用户 兴趣相关的内容，满足用户个性化的信息需要。面向主题的网络信息采集可以 用在专业网站的信息搜集、企业和商业信息的搜集与服务、w 曲数据挖掘等各 个方面。 1 2 面向主题搜索介绍 随着用户对信息需求多元化的增长，千篇一律的给形形色色、具有不同目 的的互联网使用者同一个入口、给所有用户同一个关键字的查询返回同样的查 询结果，显然已经不能满足特定用户更深入的查询需求。同时，通用搜索引擎 为了保证覆盖率与全面性要花费大量成本来及时抓取、更新互联网上的海量信 息，面对互联网信息量的进一步爆破式发展，通用搜索引擎显然已经无法满足 人们的个性化需求。这就需要一个分类细致、数据深入、更新及时的面向主题 搜索引擎，也叫做垂直搜索。由于面向主题搜索运用了人工分类以及主题相关 性判断等智能化策略，因此相对于通用搜索引擎，面向主题搜索网页抓取的准 确性高，与用户关心的主题相关度大，搜索的范围相对缩小，有利于快速搜集 到相关网页，更能满足人们的个性化需求p j 。 所谓面向主题搜索引擎，是指在互联网上发现并获取与某个主题相关的资 源的过程。专业搜索引擎是与通用搜索引擎相对应的一个概念，属于仅覆盖网 络某一领域的“垂直搜索引擎”，为用户提供某个特定主题的网络网页资源的检 索服务。它与通用搜索引擎的区别主要体现在资源与服务上，主题搜索引擎提 供的资源都是与某个主题相关的，服务上更具有专业特色，有一定程度的个性 化。 由于面向主题搜索运用了人工分类、专业领域知识等智能化策略，因此它 第1 章绪论 比通用的搜索引擎更加准确和有效。这类搜索引擎的特点是主题资源覆盖度高、 智能化程度高、检索对象多样化、服务个性化以及专业化。不同于那些搜索所 有互联网页面，对所有问题进行解答的通用搜索引擎，面向主题搜索引擎爬行 每个页面的链接的同时还需要做具体分析，判断哪些链接指向的页面可能是和 预定主题相关，对这些链接进行优先爬行，舍弃和主题无关的链接。它的目标 是尽可能地收集与特定主题相关的网页，同时最大限度地避免无关网页的下载， 这些对于节省硬件和网络资源都是有明显意义的。 1 3 面向主题搜索技术研究意义 面向主题的互联网搜索技术，指的是根据用户指定的主题内容搜索有限的 网络空间，选择性地对那些与预先定义好的主题集相关的页面进行采集，发现 与主题相关的信息资源，为用户提供个性化服务。它的研究意义在于： ( 1 ) 作为目前研究热点，面向主题搜索也代表了搜索引擎未来的发展方向。 传统的搜索引擎由于面向所有用户，因此其信息采集也面向整个互联网。通用 搜索引擎已经无法跟上目前互联网的增长速度。而主题w r e b 信息采集技术只采 集与预定主题相关的页面，有效地降低了硬件需求，减少开销，同时也使用户 在进行信息检索时能够获得更新、更准确，也更全面的信息，能比较有效地解 决目前通用搜索引擎所面临的增长性难题。 ( 2 ) 将互联网上无序的信息转化为有序的知识，为用户提供高质量、个性 化的服务，满足特定用户群体的信息需求。h t e m e t 上存在着海量的信息，从用 户的角度考虑，如何方便用户快速有效地找到自己需求的信息成为一个十分迫 切的课题。相对于传统的基于整个w e b 的信息采集技术而言，其采集页面更加 有针对性，采集效率更高，利用率也相应提升。传统的信息采集面向整个互联 网进行采集，采用深度优先或广度优先遍历算法，时空开销较大，采集的页面 针对性差，相关性与准确性也不尽如人意。而面向主题搜索则面向特定主题， 判别页面相关性，通过预测链接的价值来抓取页面信息，因此其针对性很强， 采集的准确率也相应提升。从用户的角度来考虑，主题搜索引擎能为用户提供 高质量，个性化的服务，满足特定用户的信息需求，具有相当重要的研究意义。 1 4 论文的主要工作 本文主要从理论和实践两个方面对面向主题的互联网视频搜索的关键技术 进行了阐述。 北京工业大学t 学硕士学位论文 图l l 论文主要工作 f i g 1 1m a i nw o r ko f t i l i sp a p e r 如图1 1 所示，本文的主要工作分为三个部分，第一部分提出了基于 c o c i t a t i o n 的面向主题采集算法并通过链接窗口进行改进，通过利用信息抽 取的思想，对互连网页面进行分析，利用r o a d r 咖e r 的模式查找的思想提出 了相关链接集合的定义以及生成算法，进一步引入窗口融合使得针对互联网视 频的面向主题采集算法能够将页面结构信息与互联网拓扑结构进行有机的结 合，进一步提高效率。 本文通过分析互联网视频的特点发现互联网视频中的很多文本信息都是无 意义的文字组合，通过中文复杂命名实体可以很好的解决其识别问题。本文提 出的一种面向互联网视频的复杂命名实体抽取模型。互联网视频本身就是很重 要的复杂命名实体类别，中文复杂命名实体在其中占有很大比重，但是其识别 工作尚未得到充分的研究。通过发现这些中文复杂命名实体可以更好的为用户 提供视频推荐等服务，更好的提升用户体验。本文将复杂中文命名实体研究引 入到互联网视频搜索领域，对面向主题的互联网视频采集有着非常重要的贡献。 最后，通过对互联网社区中的搜索日志的分析研究，本文设计了一种支持 大规模主题搜索的可适应分布式模型。提出基于m a p r e d u c e 的可信区域的二 阶l o g i s t i c 回归方法，改善了面向主题搜索的效率。 1 5 本文章节安排 本文总共分5 章，详细研究了面向主题的互联网视频搜索，并通过本文所 设计的实验验证与分析了本文所研究与改进的相关算法与模型。 第一章提出问题并概述了课题研究的背景及其理论和现实意义。 第二章介绍了国内外关于面向主题搜索的研究现状。 第1 章绪论 第三章详细介绍了c o c i t a t i o n 算法，并提出基于c o c i n 町i o n 的面向 主题采集算法，并利用链接窗口来对其进行改进，同时利用r o a d r i l n n e r 的思 想提出了相关链接集合的定义和生成算法，通过进一步引入窗口融合使得面向 主题的视频采集算法能够将页面结构信息与互联网拓扑结构进行有机的结合。 详细论述了互联网视频领域中所面临的中文复杂命名实体问题，并针对此问题 提出中文复杂命名实体提取模型。 第四章介绍了支持大规模高效搜索的可适应分布式计算框架。利用分布式 的搜索服务器中的搜索日志，提出基于的大规模w 曲文档的有效搜索方法，设 计了基于m a p r e d u c e 计算框架的可信区间的l o g i s t i c 回归方法，通过频率 树对动态的非精确查询条件下查询出的w e b 文档进行分类和组织后进行分级。 最后，结论部分对整个论文主要研究成果的总结，对全文进行概括性总结， 指出了本文的研究内容和取得的创造性成果和创新点理论，并对其应用前景和 社会、经济价值进行了预测和评价，并指出今后进一步在本研究方向进行研究 工作的展望。 北京t 业大学工学硕士学位论文 6 - 第2 章课题的研究现状和分析 第2 章课题的研究现状和分析 面向主题搜索引擎大都处于研究和试验阶段。目前国外对面向主题搜索引 擎的研究已经成为一大热点。 目前面向主题的搜索研究主要有两种思路： 基于内容的搜索。主要方式就是在搜索引擎内部建立一个针对主题的词表， 搜索引擎的爬行机器人根据其内设的词表对网上的信息进行索引。各个不同的 系统词表建设的复杂度也大不相同。 基于链接分析的搜索。网页之间的链接指引关系与传统的引文索引非常相 似，通过对链接进行分析可以找出各个网页之间的引用关系。由于引用网页 与被引用网页之间内容上一般都比较相关所以就可以很容易地按照引用关系 对大量网页分类。 而将面向主题搜索技术应用到视频搜索领域，国内尚无成型的研究体系。 下面四个小节将着重介绍与互联网视频搜索更为相关的关键技术的研究现 状。 2 1 面向主题的互联网信息采集的研究现状 面向主题的互联网视频信息采集是面向主题视频搜索的一个重要组成部 分，如何高效快速的收集与指定主题相关的互联网信息是面向主题的互联网采 集课题的研究目标。 2 1 1 面向主题采集 搜索引擎的网页采集工具被称为c r a w l e r 或s p i d c 一【刀。c r a w l e r 的基本原 理是通过模拟用户的互联网浏览行为，通过浏览某一页面，获取更多的待浏览 链接。 北京工业大学丁学硕十学位论文 图2 1 普通的网络采集方法与面向主题的网络采集方法 f 嘻2 一lc o m m o nn e t 、v o 呔a c q u i s i t i o nm e t h o d 锄ds u b j e c t - o r i e n t e dn e t 、v o r k q u i s i t i o n m e t h o d 在具体采集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常 见的一种是所谓“抓取 ( c m w l ) ：将互联网页面上的网页集合看成是一个有 向图，搜集过程从给定起始种子链接集合s 开始，沿着网页中的链接，按照深 度优先、宽度优先、或者某种别的策略对整个有向图进行遍历，不停的从s 中 移除链接，并采集相应的网页，解析出网页中新出现的链接，并将该链接添加 到集合s 。研究表呀引，按照宽度优先搜索方式得到的网页集合要比深度优先 搜索得到的集合重要( 这里当然有一个重要性的指标问题) 。下表是基于宽度 优先搜索的采集方法的主要流程： 表2 1 传统的基于宽度搜索的网络采集方法 t a b 2 - lt r a d i t i o n a ln e m o r k 犹q u i s i t i o nm e t h o db 弱e do nt i l ew i d t hs e a r c h 面向主题采集是在有限资源的情况下，高效收集与用户兴趣相关的内容【9 j 。 那么衡量一个面向主题的互联网信息采集器的基本原则就是：在采集的过程中， 判断与主题相关的页面在已采集页面中所占的比例。具体评价指标包括：采集 准确性( c 娜l e r p r e c i s i o n ) 印、采集召回率( c m w l e rc a l l ) c c 。其中采集准 确性指采集的所有网页中与主题相关的网页数所占的比例；采集召回率是采集 网页中与主题相关的网页数，占实际存在的与主题相关网页总数的比例【1 0 1 。在 采集的过程中，用c ( c 咫w l e d ) 表示已经采集的页面，r ( r e l e v a n t ) 表示在 第2 章课题的研究现状和分析 指定的可采集范围内与主体相关的贞面数量。那么采集精确率为： 凹= 钟 ( 2 1 ) 由于与主题相关网页数总难以统计，对采集召回率直接进行评估比较困难， 并且针对视频搜索的主题采集具有更加明显的特点，因此如何提高面向主题采 集的精确率成为了本课题的主要研究目标。 表2 2 视频搜索引擎某天网页采集情况 t 抽2 - 2s o m e d a yc a p t u r es i t u a t i o no fw e bv i d e o a r c h g i n e 表2 2 为某视频搜索引擎在某一天中，其视频采集系统收集到的页面和视 频情况。该结果是利用传统的b f s 算法的采集获得的，视频内容是通过采集页 面以后对页面内容进行分析而取得的。可以看到，对于视频类型网站：2 5 6 c o m 、 b n s i n a c o m c n 、j i m 啊c n b o o c o m 、p r o 酣u 1 1 a e e b o o c o m 这四个网站的采集情况具 有较高的精确率，而对于一般的网站而言b f s 算法的采集精确率则大大降低， 在这种情况下，c r a w l e r 大部分时间都在做无用功，这是对存储系统以及网络带 宽的极大浪费，因此势必需要寻找到一种有效地方法来提高面向主题视频搜索 的采集精确率。 传统的搜索引擎采集程序面对海量的互联网数据，采集完所有的网页基本 上是不可能的事情，因此在传统的网页采集过程中提出了网页采集调度的概念 【l l l 。采集调度器( s c h e d u l e r ) 通过调整待采集队列( 即上述传统采集方法中的 o p e n 表) 中待采集队列的优先级，优先采集那些更加重要的网页。这里网页的 重要程度往往是用p a g e 鼬m k 【1 2 】) 来进行衡量的，p a g e 黜m k 是一种通过互联网 页面拓扑链接结构关系来衡量网页重要程度的方法。通过计算预测待采集链接 的重要程度，调整待采集链接的采集优先级，优先采集重要程度较高的链接所 指向的页面。 北京丁二业大学t 学硕七学位论文 类似的，在面向主题的采集过程当中也可以引入采集调度的概念，通过预 测待采集链接与主题的相关性，来调整待采集链接的采集优先级，从而提高采 集精确率。如图2 1 所示，淡色的节点代表与主体相关的页面，如果在第一轮 采集完成以后能够提前预测下一步采集页面的主题相关性，将淡色节点表示页 面提前采集，那么从右图可以看出将会极大的提高采集精确率。 2 1 2 基于文本的主题预测技术 前一小节已经提出了如何提高面向主题互联网采集的准确性的途径通 过预测采集过程中未采集页面的主题来提高采准确性。主题预测技术当前主要 是针对未采集页面的己知链接信息进行分析的，已知的链接信息主要包括：链 接本身的切随信息，链接的文本信息，链接在互联网页面中的拓扑结构【1 3 】。 目前大部分面向主题采集方法都是利用链接的文本信息来进行的，待采集 连接的文本性质的信息主要包括： a 链接，所出现过的页面集合s b 所有集合s 中页面的文本信息( p 枨i n t t e x t ) c 所有集合s 中出现的链接，本身的文本信息( a n c h o r t e x t ) d 所有集合s 中出现的链接，周围的文本信息( s u 玎o u i l d i i l g t e x t ) 基于查询的互连网页面的即时采集方法，是指在提供查询以后，从某一相 关页面出发找到更多的相关页面的方法。这一类问题和面向主题的互联网采集 实际上是具有很大的相似性的。最具代表性的算法包括f i s h - s e a r c h 【1 4 】和 s h a r k s e a r c 【15 1 。 标准f i s h 算法把网络采集器采集w | e b 的行为比喻为为鱼群在大海中觅食， 算法中的每条鱼代表一个链接。当鱼找到食物( 发现某一连接所指向的页面是 相关的) 时，它的繁殖能力增强( 搜索宽度增加) ，并且它繁殖的后代寿命与它 自身相同( 搜索深度不变) ；当没有发现食物( 没有发现相关网页) 时，它的繁 殖能力保持不变( 搜索宽度不变) ，并且它后代的寿命缩短( 搜索深度1 ) ；当 进入污染区( 网页不存在或者读取时间太长) ，这条鱼死去( 放弃对该链接的爬 行) 。该算法的关键之处是根据输入的种子链接和查寻串等参数，动态地建立一 个链接的优先级爬行列表，这也是面向主题搜索的一般采集调度方法。 s i l a r k s e a r c h 是在f i s h - s e a r c h 上的一种改进算法，在f i s h - s e a r c h 中页面的 相关度是二值的0 或l ，而s h a r k s e a r c h 中用到了文本相似度的方法来计算当 前页面的主题相关度，用一个【o ，l 】间的实数尸描述。s h 破s e a r c h 认为儿子页 面的主题相关度是能够通过父亲页面来预测的，因此儿子的主题相关度等于 印，艿是一个衰减因子。父亲页面的第刀代子孙的主题相关度即为鲫。同时 儿子节点在父亲页面中出现时的描述链接文字以及链接附近的其它链接上的描 述文字的主题相关性进行文本相似度比较，得到在两个重要的分数描述链接分 第2 章课题的研究现状和分析 值以及链接描述文字分值。最终，算法将上述预测三类得分进行线性融合来调 整待采集数据的采集优先级。另外，有人提出对s h a r k s e a r c h 中链接附近链接 的选取方法【i 引，通过计算链接在h t m l 标签树中路径信息来进行聚类，从而找 到与该链接在视觉上接近链接的文本内容。 m ma l m a d e nr e s e a r c hc e n t e r 在1 9 9 9 年发表的f o c u s e dc r a l w e r 方法8 ，通 过对的网站分类数据进行分析，建立起页面集合的分类训练数据。整个 系统分为三个部分，c r a w l e r 、c l a s s i f i e r 和d i s t i l l e r 。c r a w l e r 负责采集页面信息； c 1 2 l s s i f i e r 负责对采集结果利用n a i v eb e s t f i r s t 进行分类，如果该结果是主题相 关的页面，那么会相应的提高该页面中待采集链接的采集优先级；d i s t i l l e r 的 作用是负责收集采集过程中主题相关的h u b 型页面【1 7 】( 主题相关的h u b 型页 面是指某一页面指向的很多的主题相关的页面) ，因为h u b 型页面往往是经常 被更新的页面，所以通过对h u b 型页面的重复采集能够获得更多的新诞生的页 面，从而加强整个系统对新出现的主题相关性页面的覆盖率。不久，他们又提 出了对这一方法的进一步优化方法【l8 j ：通过对h t m l 标签树中链接位置来度量 链接附近文本与连接本身的距离，根据h n 儿标签树距离的不同赋以不同的权 值，从而影响分类器对链接主题相关性预测的正确性。 上述是几个典型的基于文本信息的链接主题预测技术。此外，由于链接文 本信息一般都是很稀少的，一般的情况下只有极少数的若干个词语构成，因此 诞生了大量的基于语义扩展的主题预测方法【1 9 】【2 0 1 。由文献 2 l 】可知，其提出了 一种基于舢l c h o r 文字信息利用决策树的方法来进行文本分类，用户需要给定一 个在拓扑结构上联通的页面集合来作为训练集，这种方法能够有效地利用到网 络的结构信息和页面的文本信息。由文献 2 2 】可知，其中介绍了如何利用链接 的上下文相关文本技术进行分类。g a u t a m 研究认为，与单纯采用全文以及单纯 采用链接文本窗口的方式相比，采用全文与链接文本窗口结合的方式具有较好 的采集准确性，采用基于标签树的文本组合具有较好的采集覆盖率四j 。 i n t e l l i g e n tc r a w l i n g 技术，是一种文本信息、u r l t o k e n 信息以及链接的网 络拓扑结构信息( i i d i l l l ( 信息以及s i b l i n g 信息) 相融合的面向主题采集方法l z 4 j 。 就上述方法的不同之处是该方法考虑提取u r l 中的关键词，特别是位于u r l 中位置比较靠后的词语是能够准确的描述页面的主题相关性的，例如 h n p ：s p o n s s o h u c o m c n n b “中的n b a 。在利用拓扑结构信息方面，该算法提出 了了这样的概念：如果采集了某一个页面指向的若干个页面都是主题相关的， 那么这个页面中还剩下的没有采集的链接所指向的页面应该也具有较高的主题 相关性。 北京t 业大学丁学硕士学位论文 2 1 3 主题预测与切 也相似度模型 在i i l t e l l i g e n tc m w l i n g 技术中提到了运用u r l 信息，在互联网中尤其是大 型网站，如门户网站、视频分享网站、博客网站、b