（模式识别与智能系统专业论文）垂直搜索中的数据清洗和排序算法研究.pdf

摘要 摘要 “信息过载”问题随着w e b 信息资源的迅速膨胀变得越来越严重，而搜索 引擎是解决这一问题的基本工具。由于传统搜索引擎是面向大众用户的，检索结 果往往面向各行各业，因此用户不容易找到自己所需要的信息。垂直搜索引擎的 出现在一定程度上解决了通用搜索引擎对专业领域及特定主题信息覆盖率过低 的问题。在国家科技支撑项目子课题一“基于本体的农业搜索引擎 ( 2 0 0 6 b a d l 0 a 1 4 1 0 ) 和国家自然科学基金“农业复杂自适应搜索引擎” ( 6 0 7 7 4 0 9 6 ) 的支持下，本文围绕农业垂直搜索引擎的关键问题开展研究。 中国搜索引擎用户不满意因素的调查结果显示：用户对结果的排序不满意占 了很大的比重。本文对搜索排序算法进行了认真分析，现有通用搜索引擎大都采 用了输入一输出的响应模式，该模式没有考虑用户反馈。论文提出了一种基于 l u c e n e 基础排序算法的改进算法，该改进算法考虑了多个排序因素：( 1 ) 为了体 现网页链接的重要性，算法融合了p a g e r a n k 算法；( 2 ) 网站等级得分；( 3 ) 用 户反馈得分：将反映用户兴趣的点击行为和网页浏览时间转化为兴趣度并作为搜 索结果排序的一个得分因子。该算法通过实验验证了其优越性。 优秀的排序算法也需要一个高质量的数据来源，高质量的搜索结果必然依赖 于高质量的数据，为了避免得到重复、相似或者信息不完整的搜索结果，数据的 正确性是至关重要的，否则就会出现“一流的引擎，二流的数据库 的现象，所 以，数据预处理工作相当重要，数据清洗工作也被提到显著位置。本文设计了基 于m d 5 数字签名的数据消重算法，在查准率、查全率和响应时间上都满足实际 需求，同时，在处理不完整信息方面提出了处理方法，即利用其它项属性值来推 测缺失项属性值，以及使用最可能的值来填充缺失值，该方法己成功应用于农业 垂直搜索引擎中。 最后，本文设计一个农业垂直搜索引擎，从总体设计到核心模块设计进行了 详细说明。该垂直搜索引擎的系统测试结果显示其在查准率、查全率、响应时间 三个重要指标中均表现良好，满足了项目的实际需求。 关键词：垂直搜索用户反馈搜索排序算法数据清洗 a b s t r a c t w i t ht h er a p i de x p a n s i o no ft h ew e bi n f o r m a t i o nr e s o u r c e s ，t h e ”i n f o r m a t i o n o v e r l o a d ”p r o b l e mi sg e t t i n gw o r s e ，a n dt h es e a r c he n g i n ei st h eb a s i ct o o lt os o l v e t h i sp r o b l e m b e c a u s et h et r a d i t i o n a ls e a r c he n g i n ei sf o rp u b l i cu s e r s ，a n dt h es e a r c h r e s u l t sa r ef o ra l lk i n d so fi n d u s t r i e s ，s oi ti sd i f f i c u l tf o ru s c e st of i n dt h ei n f o n n a t i o n t h e yn e e d t oac e r t a i ne x t e n t ，t h ev e r t i c a ls e a r c he n g i n er e s o l v e st h ep r o b l e m so fl o w c o v e r a g eo fi n f o r m a t i o nf o rp r o f e s s i o n a la r e a sa n ds p e c i f i cs u b j e c t sw h i c hac o m m o n s e a r c he n g i n eh a s t h i sa r t i c l ei s s t u d y i n gh o wt or e s o l v et h ek e yp r o b l e m sw h i l e d e v e l o p p i n gav e r t i c a ls e a r c he n g i n ef o rt l l ea g r i c u l t u r a la r e a t h i sr e s e a r c hw 懿 s u p p o r t e db y t h en a t i o n a ls c i e n c ea n dt e c h n o l o g y s u p p o r t i n gp l a n u n d e rg r a n t n o 2 0 0 6 b a d10 a1410n a m e d “a na g r i c u l t u r es e a r c he n g i n eb a s e do no n t o l o g y , t h e n a t i o n a ls c i e n c ef o u n d a t i o n o fc h i n au n d e rg r a n in o 6 0 7 7 4 0 9 6n a m e d “a n a g r i c a l t u r e c o m p l e xa d a p t i v es e a r c he n g i n e ” i nt h es u r v e yo ft h ef a c t o r sa b o u td i s s a t i s f a c t i o nw h i l eu s i n gt h ee a r c he n g i n ei n c h i n a ，i tr e v e a l st h a tt h ed i s s a t i s f a c t i o nw i t ht h er e s u l t so ft h er a n k i n gm a k e su pa l a r g ep r o p o r t i o no fa l lt h ef a c t o r s t h i sa r t i c l em a d eac a r e f u la n a l y s i sa b o u tt h e r a n k i n ga l g o r i t h m m o s to ft h ec o m m o ns e a r c he n g i n e sa d o p tt h e i n p u t o u t p u t r e s p o n d i n gm o d e lw i t h o u tc o n s i d e r i n gt h ef e e d b a c kf r o mt h eu s e r s t h i sa r t i c l eg i v e s a na m e l i o r a t e da l g o r i t h mb a s e do nt h er a n k i n ga l g o r i t h mo fl u c e n e ，t h i sa l g o r i t h m c o n s i d e r sm u l t i - f a c t o r s ：( 1 ) t os h o wt h ei m p o r t a n c eo f t h ew e b l i n k s t h ea l g o r i t h mt a k e s t h ep a g e r a n ka sar a n k i n gf a c t o r ；( 2 ) t h er a n k i n go ft h ew e b s i t e ；( 3 ) t h ef e e d b a c kf r o m t h eu s e r ：c o n v e r t i n gt h ec l i c k sa n dw e b r e a d i n gt i m et oas c o r ea sar a n k i n gf a c t o r t h e e x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h ma c h i e v e dg o o dr e s u l t s a ne x c e l l e n tr a n k i n ga l g o r i t h ma l s on e e d sah i g h - q u a l i t y d a t a b a s e ，a n dt h e h i g h q u a l i t ys e a r c hr e s u l t sm u s tr e l yo nh i g h q u a l i t yd a t a i no r d e rt oa v o i dd u p l i c a t e d ， s i m i l a ro ri n c o m p l e t e ds e a r c hr e s u l t s ，t h ec o r r e c t n e s so fd a t ai sv i t a l o t h e r w i s et h e p h e n o m e n o no f ”af i r s t c l a s ss e a r c he n g i n e ，as e c o n d c l a s sd a t a b a s e ”w i l lh a p p e n s o t h ew o r ko fd a t ap r e p r o c e s s i n gi sv e r yi m p o r t a n t ，a n dd a t ac l e a n i n gh a sa l s ob e e n m e n t i o n e di nap r o m i n e n tp o s i t i o n i nt h i sp a p e r , t h ed a t ac l e a n i n ga l g o r i t h mw h i c hi s b a s e do nm d 5d i g i t a ls i g n a t u r ei sd e s i g n e d i tm e e t st h ea c t u a ln e e d si np r e c i s i o n ， r e c a l la n dr e s p o n s et i m e ，t h i sp a p e ra l s og i v e sam e t h o dt o p r o c e s st h ei n c o m p l e t e i n f o r m a t i o n ，n a m e l y , t h eu s eo fo t h e ri t e m s a t t r i b u t ev a l u et oe s t i m a t et h em i s s e d i i a b s t r a c t a t t r i b u t ev a l u e sa sw e l la st h em o s tl i k e l yv a l u et oj f i l lt i l em i s s i n gv a l u e t h em e t h o d h a sb e e ns u c c e s s f u l l yu s e di na g r i c u l t u r ev e r t i c a ls e a r c he n g i n e f i n a l l y , av e r t i c a ls e a r c he n g i n ef o ra g r i c u l t u r ew a sd e s i g n e d ，a n dt h ea r t i c l e i n t r o d u c e dt h eg e n e r a ld e s i g na n dt h ec o r em o d u l e si nd e t a i l as y s t e mt e s t i n gs h o w s t h a tt h ev e r t i c a ls e a r c h e n g i n eh a sg o o dp e r f o r m a n c ei nt h ep r e c i s i o n ，r e c a l la n d r e s p o n s et i m ea n dm e e t sw i t ht h er e a ln e e d so ft h ep r o j e c t k e y w o r d s ：v e r t i c a ls e a r c he n g i n e ，u s e r s f e e d b a c k ，r a n k i n ga l g o r i t h m ，d a t ac l e a n i n g i i i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 臻 o1 b 作者签名：主! ) 瘟 协9 7 年6 月f j 日 第l 章绪论 1 1 选题的背景和意义 1 1 1 选题的背景 第1 章绪论 目前全球有近干亿网页，面对这一海量网络信息资源，全球l o 亿互联网用 户面临严重的“信息过载”问题，而搜索引擎是解决这一问题的有效工具。截至 2 0 0 8 年年底，中国搜索引擎用户人数达到2 0 3 亿人，与2 0 0 7 年同期相比，搜索 引擎的用户净增了5 1 0 0 万人，年增长率达到惊人的3 3 6 。目前，搜索引擎在 全国互联网用户中的使用率为6 8 ，在各种互联网应用中列第四位。传统搜索引 擎大致可分为三种类型：以目录搜索为特征的搜索引擎( 以雅虎为代表) ，以关 键词搜索、页面重要性分析与超链分析技术为特征的全文搜索引擎( 以谷歌，百 度为代表) 以及元搜索引擎( 以m e t ac r a w l e r 、m a m m a 为代表) 。然而这三类搜 索引擎在实际应用中还存在以下几点缺陷( b j j a n s e ne ta l ，2 0 0 0 ) ( r o b e r tk r o v e t z e ta l ，1 9 9 2 ) ( et a n u d j a j ae ta l ，2 0 0 2 ) ：( 1 ) 用户无法用简单的关键词准确表达出查 询的真实意图，具有一定的盲目性，查准率很难保证，搜索结果中往往会出现大 量与用户本意不同、无关的垃圾信息；( 2 ) 搜索引擎只返回包含大量的指向w e b 页面的网页地址，距离用户所需要的真正信息还存在很大差距；( 3 ) 搜索引擎收 录的网页覆盖率低：网络信息资源呈几何级数爆炸性地增长，搜索引擎在网页信 息搜集能力方面远远赶不上网络信息资源的增长速度。同时由于w e b 中大量的 动态网页无法实时搜索，因此单个搜索引擎的覆盖率一般都低于3 0 ，很难索引 所有的网页资源( s t e v el a w r e n e ee ta l ，1 9 9 8 ) ( s t e v el a w r e n e ee ta l ，1 9 9 9 ) 。为了解决 以上通用搜索引擎所产生的问题出现了垂直搜索引擎，相对而言垂直搜索引擎是 一个令用户满意的解决方案。所谓垂直搜索，即是针对某一特定行业的专业搜索， 是通用搜索的细化和延伸，是对网页库中的分门别类的信息的一次整合，垂直搜 索引擎按照行业抽取出用户需要的数据，并进行处理后以某种特定格式返回给用 户。垂直搜索引擎的应用方向非常广阔，比如火车票信息搜索、机票信息搜索、 租房信息搜索、城市地图搜索、m p 3 音乐搜索、化工行业企业搜索等等，几乎 各行各业，各类信息都可以建立一个与之对应的垂直搜索引擎。 1 1 2 选题的意义 目前，我国建有1 5 0 0 0 余个涉农网站，积累了丰富的农业技术、农产品价格 第1 章绪论 信息、供求信息、政策法规、农业新闻等信息资源。据不完全统计，到2 0 0 7 年 8 月，全国有7 万多农业产业化龙头企业、1 5 万左右农村合作及中介组织、近 1 0 0 万经营大户、2 0 0 多万农民经纪人能够定期使用这些信息资源( 郭作玉， 2 0 0 8 ) 。这些网站由于信息资源缺少统一的形式化表达方法与网页格式，使得网 页信息资源异质、异构、分散、重复现象严重，形成所谓的“信息孤岛”，这样 就很难发挥农业信息资源的最大效用。同时考虑到我国农户的文化基础、计算机 操作水平以及农业网络信息服务的复杂性，要求“三农用户利用传统的搜索引 擎去直接搜索、捕捉和筛选其需要的真实信息，不仅是不现实的，也是不可能的。 因此，建立专业化以及高度智能化的农业垂直搜索引擎意义重大。 1 2国内外相关研究综述 围绕垂直搜索引擎的研究，国内外研究者已经取得了很多成果，本章主要介 绍一下几个具有代表性的系统： ( 1 ) 国外科学搜索引擎s c i r u s ：这是一个专门为搜索高度相关的科学信息而设 计的垂直搜索引擎，它收集到的信息源主要包括网页和期刊两部分； ( 2 ) n e c 研究院的c i t e s e e r ( i w i t t e ne ta l ，1 9 9 8 ) 系统：这是一个较为成功的针 对计算机科学领域的论文检索系统； ( 3 ) 国内酷讯搜索引擎：酷讯搜索最初是以火车票搜索起家的。当人们通过 百度，谷歌等通用搜索引擎很难找到自己想要的火车票信息时，酷讯搜索提供了 一个快速且准确的搜索平台，满足了用户的需求。现在搜索领域更是覆盖了火车 票，招聘，住房，特价机票，汽车等诸多生活领域； ( 4 ) 雅虎e l 碑网是中国最大的生活搜索引擎，涵盖娱乐餐饮、买房、租房、 工作、旅游等生活消费信息，信息涉及所有大中城市。 ( 5 ) 农业领域的垂直搜索引擎如w e b a g r i 、a 9 2 n i c 等，但是只限于提供 英文农业信息的搜索服务功能。 垂直搜索引擎的关键技术中包括如何对网络爬虫采集来的数据再加工( 数据 清洗、规范化) 、标引，在搜索阶段如何克服关键字匹配带来的查全率和查准率 不高以及如何让搜索结果排序更“智能 等闯题。 数据清洗中一个重要方向是识别并消除数据库中的相似或者重复数据( m a h e m a n d e ze ta l ，19 9 8 ) ( j o n a t h a ne t a l ，2 0 0 0 ) ( s t e v cl a w r e n e e e ta l ，19 9 8 ) ( s t e v e l a w r e n e ee ta l ，1 9 9 9 ) ( m o n gl e ee ta l ，1 9 9 9 ) 。网络爬虫从不同的网站上采集来的数 据，由于各个网站之间的相互转载、用户的重复发布等原因会产生大量的重复记 录，如何消除这些相似的或者重复的数据是目前数据清洗领域中研究最多的内 2 第1 章绪论 容。( 孟坚等，2 0 0 5 ) 提出了一种基于规则描述的交互式数据清洗模型，在一定 程度上解决了用户和数据清洗工具之间缺少交互的问题，这样就使得用户在一定 程度上可以控制过程的发展，提高了数据清洗的效率，从而保证了清洗后的数据 质量。( 覃华等，2 0 0 4 ) 提出了一种基于遗传神经网络的数据清洗框架，它主要 是利用神经网络的非线性映射和遗传算法的全局优化特性来解决数据清洗问题。 ( 鲍玉斌等，2 0 0 5 ) 提出以用户为中心的数据清洗方法。黄大荣( 2 0 0 4 ) 则在基 于粗糙集理论的基础上提出一个海量数据库系统的数据清洗框架，以解决信息不 完备决策问题。郝博( 2 0 0 4 ) 提出基于最小二乘法原理和模拟退火遗传算法的数 据预处理组合模型。但是这些方法主要存在清洗效率不高，尤其是在面对海量数 据的时候，耗时太多，不能满足农业垂直搜索引擎对数据库及时更新的要求。 传统的排序是通过用户输入搜索的关键词，通过特定的算法计算相关文档得 分，然后按照得分高低顺序依次输出给用户，是单一的“输入一输出 响应模式， 这种方法只考虑用户输入的关键词，根据用户输入计算索引库中和搜索关键词匹 配的文档，完全没有关心搜索结果排序是否符合用户的真实需求，忽视了用户行 为。 本文正是研究建立农业垂直搜索引擎中所面临的上述关键问题，这对文化程 度以及计算机操作水平相对较低的涉农用户将有更加迫切的需求。农业垂直搜索 引擎的研究成功将为我国蓬勃发展的农业企业、农业协会、农民大户以及广大农 业技术人员提供农业市场信息、农业技术以及政策新闻搜索等服务，这将有效缓 解农业信息服务“信息过载 问题，对促进我国农村与农业信息化建设也将起到 积极作用。 1 3 本文研究的内容 1 3 1 数据清洗算法 清洗模块是垂直搜索引擎中一个非常重要的模块，它的好坏直接关系到数据 质量，后续的搜索模块使用的数据就是经过清洗模块处理后的数据。利用m d 5 数字指纹技术对海量数据进行清洗，利用一定规则完成对不完整数据的处理，有 效改善数据库存储的数据质量，达到节约存储资源以及提高查准率和查全率以提 高用户满意度的目的。 1 3 2 查询结果排序算法 搜索结果排序关注的是用户体验，综合考虑影响排序的多方面因素将“优秀 3 第1 章绪论 的结果”排在靠前的位置展现给用户，分析了传统的t f i d f 方法，全面考虑链 接关系，网贞重要性，网站等级这些传统因素对文档得分的贡献，同时根据用户 兴趣爱好及时调整文档得分，将用户感兴趣的文档尽可能的排序靠前。 1 4 本文的组织 本文的组织结构如下： 第l 章：绪论。介绍了本文的研究背景和意义。 第2 章：相关背景技术。介绍了l u c e n e 开源项目，然后简要介绍了通用搜 索引擎的系统结构，并由此引出了系统自适应的排序思想，对排序模块的自适应 理论做了简要介绍，然后给出了根据点击次数和浏览时间转换为兴趣度的计算公 式。 第3 章：垂直搜索中的数据处理。介绍了基于m d 5 数字签名的数据消重方 法，针对农业数据的行业特点提出了改进的算法；同时介绍了处理缺失数据的填 充方法。 第4 章：搜索结果排序算法。分析了当前比较经典的排序算法，从对排序结 果贡献的关注点出发，有效融合多种方法，提出一个基于l u c e n e 基础排序算法 的改进算法。 第5 章：系统设计与实现。介绍了系统的设计和实现方法，这个系统包括了 数据清洗模块和自适应排序模块。 第6 章：总结与展望。对全文进行了总结，对需要进一步研究的内容进行了 展望。 4 第2 章相关背景技术 第2 章相关背景技术 本章主要介绍一个开源项目l u c e n e 以及通用搜索引擎的系统结构；在介绍 搜索结果排序算法之前，先引出本文搜索结果排序算法中将要使用的带有用户兴 趣反馈的方法的原理和用户兴趣采集技术。 2 1 全文检索框架l u c e n e 技术概述 l u c e n e 是一个叫a p a c h e 软件基金会下面的一个开源子项目，是一个供用户 免费使用的全文检索引擎工具包，它不是一个完整的可以直接使用的全文检索引 擎，而只是一个全文检索引擎的框架，但它提供了完整的查询引擎、索引引擎以 及部分语言的分析引擎。l u c e n e 的最初目的就是为软件开发人员提供一个简单 易用的开发工具包，以便于实现全文检索的系统j 或者是以l u c e n e 为基础进行 二次开发建立起完整的全文检索引擎。作为开源软件，l u c e n e 具有和其他开源 软件一样的与生俱来的优点：功能和结构的透明性、功能强大且具有较强的扩展 性、技术社区有力的技术支持。此外与其他搜索引擎开发包相比，l u c e n e 还具有 如下的优点：a p i 简单易用但是功能强大，用户可以很容易的在自己的应用程序 中实现包括模糊查询、分组查询等在内的索引、分析功能；架构清晰，易于扩展 和学习，利于用户根据自己的实际需求扩展系统；强大的索引文件，l u c e n e 的 索引文件格式独立于应用平台，使索引文件能够跨平台共享，分块索引文件，通 过为新增的文件单独创建索引然后再合并的方式可以获得高速和优化的索引功 能：可应用于多种文档格式和多种不同的语言。由于l u c e n e 的诸多优秀特性使 得其获得了越来越多的应用，国内外目前已经有很多应用程序的搜索功能都是基 于l u c e n e 实现的。可以说，l u c e n e 的出现极大地推动了全文检索技术在各个行 业和领域尤其是在构建垂直搜索引擎领域中的更深层次的应用。 l u c e n e 开源代码中共包括7 个子包( 朱学吴等，2 0 0 8 ) ，每个包完成特定 的功能，o r g a p a c h e 1 u c e n e a n a l y s i s 包：语言分析器，这个包主要功能是对文档进 行分词，因为文档在建立索引之前必须要进行分词，所以这个包的作用可以看成 是为建立索引做准备工作，该包已经实现中文分词，但是中文分词功能非常简单， 提供接口支持自定义分词；o r g a p a c h e 1 u c e n e d o c u m e n t 包：实现索引存储时的文 档结构管理功能，提供了一些为封装要索引的文档所需要的类； o r g a p a c h e 1 u c e n e i n d e x 包：实现索引管理功能，这里面有两个基础的类： i n d e x w r i t e r 类和i n d e x r e a d e r 类，其中i n d e x w r i t e r 类是用来创建索引并添加文档 到索引中的，i n d e x r e a d e l 类是用来删除索引中的文档的； 5 第2 章相关背景技术 o r g a p a c h e l u c e n eq u e r y p a r s e x 包：查询分析器，实现查询关键词间的逻辑运算， 如与、或、作操作等；o r ga p a c h e l u c 口a es t o r e 包：实现数据存储管理功能，主要 包括一些底层的i o 操作；o 瞎a p a c h e 1 u c e n e s e a r c h 包：实现检索管理功能，根据 用户输入的查询条件，从索引中检索得到结果；o r ga p a c h e l 愀眦u t i l 包：一些公 用的类。本文最终设计的系统就是在l u c e n e 基础上进行二次开发的。 22 搜索引擎的通用系统结构 搜索引擎的构成主要包括三个子系统：( 1 ) 信息采集子系统；( 2 ) 索引子系 统；( 3 ) 检索子系统。从系统结构的角度看大致都是采用如图21 所示的系统 结构。其中搜索引擎通过信息采集子系统使用能够从互联网上自动采集网页信 息的网络爬虫，自动访问网页，并沿着网页中的所有的链接地址爬到其它网页， 重复这个采集过程并把爬过的所有网页采集存放到服务器中。通过网页分析程序 对采集到的h t m l 文档进行分析，提取相关网页信息，这些信息包括网页所在 u r l 地址、编码格式、页面内容包含的关键词及关键词位置、网页的生成时间、 采集时间、同页文件大小、与其它网页的链接关系等，以此获得网页的相关内容 并按照指定格式存放到原始数据库中。对原始数据库中的数据进行数据处理，该 处理过程包括重复和相似数据的识别和清除，不完整数据填充等，由索引子系统 对处理完的数据库建立网页索引文件，当用户输入搜索关键词后，分解搜索关键 词，由检索子系统从网页索引文件中找到符合该关键词的所有相关网页，然后对 这些相关网页进行排序相关度越高，排名越靠前。最后将搜索返回结果的阿页 链接地址和页面内容摘要等内容组织起来显示给用户。 晤赢翮 图2 1 通用搜索引擎结构圈 第2 章相大背景技术 2 3 排序模块的自适应 2 3 1自适应系统的基本理论 从以上介绍的通用搜索引擎工作流程和系统结构可以得出：通用搜索引擎的 体系结构采用单一的“输入输出”响应模式，并没有考虑到用户对搜索结果的 选择情况，从而忽略了用户的兴趣情况，而仅仅是按照系统认为的最优排序返回 给用户。下面我们从自适应系统的基本原理出发，引入一种带反馈自适应的搜索 排序子系统，它能够主动记录用户对搜索结果的访问情况，挖掘这些访问记录中 潜在的能够反映用户兴趣的信息，以此来影响下一次相同关键词搜索结果的重新 排序，使得搜索排序具有自适应能力。 自适应的定义和特征： 定义：自适应系统在工作过程中能不断地检测系统指标或运行参数，根据系 统指标或运行参数的变化，改变控制参数或控制作用，使系统工作于最优工作状 态或接近于最优工作状态( 李言俊等，2 0 0 5 ) 。“自适应系统”是一个蓬勃发展 的研究领域，已经研究出一大类在某种受限的条件下类似于有生命系统与生物适 应过程的自适应系统，我们研究的带反馈白适应搜索排序就是自适应系统的一 种。 自适应系统的特征如下( b e r n a r dw i d r o we ta l ，2 0 0 7 ) ： ( 1 ) 能够自动地适应外部( 自最优) 变化( 非平稳) 的环境与变化的系统要求。 ( 2 ) 能够训练成去完成特定的滤波或者判决任务，具有这些能力的系统综合 是通过训练自动完成的。在某种意义下，自适应系统可认为是通过学习过程“编 程了的”系统。 ( 3 ) 自适应系统通常被描述成是具有时变参量的非线性系统。 2 3 2 系统原理图 为了克服通用搜索引擎体系结构带来的单一的“输入输出响应模式的缺 陷，使系统变成“输入输出反馈输入输出 的响应模式，参考以上介绍 的反馈自适应系统的基本原理，我们构造出带反馈自适应的搜索引擎系统的基本 原理图( 图2 2 ) ： 7 第2 章相关背景技术 图2 2 自适应搜索引擎原理图 在图中，输入就是用户的查询输入，输出为搜索引擎根据查询输入搜索出来的结 果排序，反馈信号是根据自适应算法采集到的用户对搜索结果的选择情况生成的 信号，反馈信号的存在首先使得系统具有自适应的能力，其次随着系统不断地运 行，搜索引擎根据反馈信号不断调整自己的检索结果排序，使得自己的搜索结果 排序逐渐适应用户的需求。 2 3 3 反馈自适应搜索的系统结构 从系统结构角度分析，带反馈自适应搜索排序的系统结构大致可用如图2 3 所示的结构。 用 户 浏 览 器 j 1 j 户使用情况 用户兴趣采集子系 统 j ，u 竺纠预搜索引擎 刊铷槽零；l 蛩 返回结果 搜索结果调整子系 l统 聚类处理子系统 用户兴趣信息库 用户兴趣反馈子系统 图2 3 系统结构图 图2 3 中，用户兴趣采集子系统利用自适应算法记录用户对搜索结果的选择情况， 并将记录送入聚类处理子系统进行相应处理生成反馈信息存放到用户兴趣信息 库中。搜索结果调整子系统主要负责最后搜索结果的合成，它结合预搜索引擎反 8 第2 章相关背景技术 馈回来的预搜索结果和用户兴趣反馈子系统反馈回来的的信息按照新的评价准 则排序后返回给用户。从以上系统结构图我们可以看出，在系统的具体实现方面 关键是需要解决两大技术，一是用户兴趣采集技术，另外一个是搜索结果的集成 技术，在接下来的章节中将要介绍用户兴趣采集技术。 2 4 用户兴趣采集技术 用户兴趣反馈从获取方式上主要分为显式反馈和隐式反馈两种类型，下面分 别介绍这两类反馈信息： 显式反馈主要是指系统为用户提供搜索结果后，要求用户对查询结果以明确 的方式( 如打分，给出明确评价等) 作出反馈，类似于问卷调查。这种显式反馈 方式主要是把检索结果返回给用户之后，由用户显式的对结果进行评价。这一方 式的优点在于实现起来相当简单，且能够很好韵保证得到的反馈信息反映用户的 真实意图。而缺点则是给用户增添了很多额外的负担，很多用户并不愿意对搜索 结果进行显式评价，因此在实用性方面大打折扣。 隐式反馈主要是指系统根据用户的查询请求给用户提供相关的搜索结果，然 后系统在客户端浏览器的后台自动地监视和跟踪用户的浏览和操作行为，通过一 定的规则和方法去判断用户对哪些文档真正感兴趣，然后对这些用户感兴趣的文 档进行内容分析，提取文档标题中的文档关键词和兴趣特征词，把这些词当作是 用户的兴趣特征词。隐式反馈的主要好处是不需要用户给予显式的反馈，从而减 轻了用户的负担，隐式反馈的主要不足是反馈质量不如显式反馈高。然而从另一 个角度考虑，即使用户没有对搜索结果显式的做任何标记活动，也有大量的隐含 用户信息可以用来改进搜索质量。 网页点击次数以及浏览时间是反映用户兴趣的两个重要特征。d i r e c t h i t 是 a s kj e e v e s 公司的一种注重用户行为反馈和信息质量的排序算法，它的基本思想 是：用户输入检索关键词q 后，如果用户在浏览搜索引擎提供的n 条结果记录 中第1 条记录( u r l ) 时，停留了比较长的时间，则说明记录i 与关键词q 具有比 较高的相关度，如果用户停留时间比较短，用户很快返回结果记录浏览第j 条记 录，则说明记录i 与关键词q 的相关度比较小；如果返回的结果记录中第1 条记 录被用户点击次数越多，说明记录i 与关键词q 相关度越高，反之越低。由此可 见，同一个词在不同的时间进行检索，得到的搜索结果排序可能是不同的，即 d i r e c t h i t 排序算法是一种依赖用户搜索行为的动态排序方法。在该排序算法中， 网页排序结果由两部分决定：被浏览的时间长度和u r l 被点击的次数。借助于 这种思想，我们希望能将点击次数和浏览时间很好的转换为排序权值，从而达到 9 第2 章相关背景技术 用户兴趣影响最终排序的目的。 2 4 1浏览时间及点击次数转化为兴趣度的方法 用户的浏览时间和平均浏览时间是用户兴趣的重要体现。但如何用浏览时间 衡量用户兴趣大小是一个很关键的问题。传统的将浏览时间转化为兴趣度的方法 比较多，比如文献( m l a d e n i cd e ta l ，1 9 9 8 ) ，文献( s c h w a be ta l ，2 0 0 0 ) 和文献( j o e r d i n g t a ，1 9 9 9 ) 都是根据用户在页面上的停留时间来判断用户对页面是否感兴趣。但文 献( m l a d e n i cd e ta l ，1 9 9 8 ) 和文献( s c h w a be ta l ，2 0 0 0 ) 都认为只要停留时间大于零， 就判断用户对该页面感兴趣，即只要用户点击浏览了网页就认为用户对该网页感 兴趣；文献( j o e r d i n gt a ，1 9 9 9 ) 则认为只有当停留时间大于5 秒时，才认为用户对 该页面感兴趣。所有这些兴趣度值转化方法转化以后的结果都不能很好地反映用 户的兴趣和浏览时间长短的对应关系。比如个用户打开一个网页，但在有效浏 览过程中有事离开，然而他却没有关闭网页，这时统计得到的网页浏览时间就会 很长，但是该浏览时间并不能反映真实的兴趣度；同时笼统的判断用户对一个网 页有兴趣或者没有兴趣，而不是很好的量化到一个值也是没有道理的，因为对于 一个用户浏览了3 分钟的感兴趣的网页和只是浏览了2 0 秒的网页感兴趣程度是 不一样的。 关于点击次数的应用，清华大学的刘奕群( 2 0 0 8 ) 提出了点击比率的概念，他 定义了网页r 针对查询q 的“点击比率 为 点击比警c q ，r ，= 主甏譬蓦等菩蓑杀毒淼 。2 ，、 该方法在其实现对搜索引擎性能自动评价的实验中取得了良好的效果。用户个体 的点击行为确实容易受到多种多样的因素干扰而导致偏移现象发生，这是由于用 户的点击行为是基于搜索引攀返回结果所显示的标题与部分文字摘要作出选择 的，但标题和文字摘要却无法完整地代表网页全貌，甚至为了提高网页排名有部 分网站专门设计标题与摘要用于欺骗用户点击，这在s e o 即s e a r c he n g i n e o p t i m i z a t i o n 操作中很常见，这些原因导致个体用户点击行为的质量变得不是那 么可信。但宏观而言，大量用户群体的点击行为我们认为还是可以信任的。 2 4 2 对网页兴趣的计算 结合文献( 何兴无，2 0 0 8 ) 提到的方法，我们给出一种将用户点击次数和浏 览时间转化为兴趣度的计算方法，该方法保证了较高的点击率和较长浏览时间对 应的兴趣度也较高，而且很好的单调分布在0 到l 之间，为后续的计算提供方便， 1 0 第2 章相关背景技术 给出计算方法： ，一2 。，+ 。f 查询q 的用户中，点击i 的次数 。 1 2 i 觚纰i 萄蕊丽谲两而丽+ 高j ( 2 2 ) 其中，为用户对第i 个页面的兴趣度值，为第i 个页面的用户浏览时间。 a v e r a g e t i m e 为用户的平均浏览时间，丌为圆周率。 2 5 本章小结 本章从系统应用的角度出发，首先介绍了l u c e n e 开源项目和通用搜索引擎 的系统结构，并由此引出了系统自适应的排序思想，对排序模块的自适应理论做 了简要介绍，然后给出了根据点击次数和浏览时间转换为兴趣度的计算公式。 第3 章垂直搜索中的数据处理 第3 章垂直搜索中的数据处理 在搜索引擎的索引文件建立过程中，一个被广泛认识但又经常被忽略的问题 是索引文件所使用的数据的质量问题。高质量的搜索结果必然要有一个高质量的 索引数据库，为了避免得到重复、相似或者信息不完整的搜索结果，数据的正确 性是相当重要的，否则再好的搜索结果排序算法也是徒劳的，所以数据预处理工 作至关重要，数据清洗工作也被提到显要位置。本章将要针对冗余数据以及不完 整数据提出解决方案。 3 1 重复数据的产生背景和消重的重要意义 3 1 1 重复数据的产生背景 随着互联网的飞速发展，人们越来越多地在互联网上发布和获取信息资源。 互联网已经成为信息制造、发布、加工和处理的主要平台。传统的互联网应用技 术大多是基于文档内容的，与经典的数据库技术和信息检索技术有着密切的关 系。但是，互联网中所特有的诸多问题，使得互联网应用技术很难有效地应用。 大量重复的网页就是其中的一个问题：有4 l 的网页是具有5 0 的相似性 ( a n d r e ib r o d e re ta l ，1 9 9 7 ) 。s t a n f o r d 的c h 0 等人在1 9 9 9 年利用g o o g l e 搜索到的 2 5 ，0 0 0 ，0 0 0 个网页的数据集统计得出约4 8 的网页是重复的( j u n g h o oc h oe t a l ，2 0 0 0 ) 。而垂直搜索引擎面向领域的特点使得这种现象更加突出，根据我们采 集到的农业数据进行的分析，每天采集到的数据有6 0 左右是重复的( 李营， 2 0 0 8 ) 。 3 1 2 数据消重的重要意义 从以上的数据中可以发现，重复数据已经成为一个严重影响搜索引擎检索结 果的因素。如果能设计一个良好的数据消重方案，则可以从以下三个方面做出贡 献： 第一，可以节约大量的磁盘空间，以便存储更多的有效资源。 第二，对未有效消重的数据建立索引时，必须对大量的重复网页建立索引， 一方面使倒排文件变得很庞大，另一方面耗时严重，而对消重后的数据建立索引 可以很好的减轻索引负担。 第三，庞大的倒排文件直接影响提供服务时的响应速度，并且检索结果中会 1 2 第3 章垂直搜索中的数据处理 出现大量的重复结果，毫无价值，降低用户满意程度，因此有效消重可以改进服 务效果，提高查准率和召回率( 也称查全率) 以及响应时间。 3 2 数据消重的一般方法 3 2 1 基于网址的网页消重 文献( 王建勇等，2 0 0 0 ) 中给出了一种基于排除相同网址的消重方法，它 分析来自不同搜索引擎的网页网址，相同的网址认为是相同的网页；或是拥有不 同的网址，但是其i p 地址相同的情况下也认为是相同的网页，然后予以消重。 该方法可以消除一部分相同的静态网页，简单直观且易于实现。但是该方法一方 面没有利用网页的文本内容结构信息，不能对转载造成的内容重复的网页消重， 另一方面没有考虑网页动态更新问题，虽然网站网址一样，但是每天发布不同的 信息，其网页内容并不一致。 3 2 2 基于聚类方法的网页消重 这种方法有效的利用