信息检索-1 概论课件

第一讲概论戴林2012.9《信息检索》课程信息检索-1概论提纲课程介绍搜索引擎发展历程信息检索信息检索中的关键问题搜索引擎Web搜索引擎搜索工程师信息检索-1概论课程介绍内容基础知识、索引技术、排序技术、文本分类和文本聚类、情感计算、跨语言信息检索、开源项目分析……共36学时，授课36学时，约16个主题教材讲义、PPT参考文献：《搜索引擎：信息检索实践》

（美）W.BruceCroft

DonaldMetzler

TrevorStrohman

译者：刘挺秦兵张宇车万翔《信息检索导论》ChristopherD.Manning信息检索-1概论课程介绍授课方式讲授、课后预习考查方式及格、中、良、优大作业回目录信息检索-1概论搜索引擎发展历程回目录信息检索-1概论搜索引擎的鼻祖：Archie1990年由Montreal的McGillUniversity（麦吉尔大学）学生AlanEmtage、PeterDeutsch、BillWheelan发明的Archie(ArchieFAQ)实际上是一个可搜索的FTP文件名列表信息检索-1概论现代搜索引擎的起源：Wanderer1993年MIT的学生MatthewGray开发了WorldWideWebWanderer，它是世界上第一个利用网页之间的链接关系来监测Web发展规模的机器人（Robot）程序。最开始只是用来统计互联网上的服务器数量，之后发展为也能捕获网址。信息检索-1概论Yahoo1994.4美籍华人JerryYang(杨致远)和DavidFilo完成了一套搜索软件。最初Yahoo的数据是手工输入的，实际上只是一个可搜索的目录。1995年1月，正式成立Yahoo网站

信息检索-1概论第一个现代意义上的搜索引擎：Lycos1994.7CarnegieMellonUniversity的MichaelMauldin将JohnLeavitt的蜘蛛程序接入到其索引程序中，创建了Lycos.提供了前缀匹配和字符相近限制、网页自动摘要、数据量相对较大。信息检索-1概论Infoseek1994年底，Infoseek推出，沿袭Yahoo!和Lycos的概念。友善的用户界面、大量附加服务使其后来者居上。1995.12与Netscape的战略性协议使它变得很强势2001年2月，Infoseek改用Overture的搜索结果信息检索-1概论第一个元搜索引擎：

Metacrawler元搜索引擎(AMetaSearchEngineRoundup)。用户提交搜索后，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户。第一个元搜索引擎，是Washington大学硕士生EricSelberg和OrenEtzioni开发的Metacrawler（1995）。信息检索-1概论第一个支持自然语言搜索的搜索引擎：

AltaVista1995年12月出现(AltaVistaPublicBetaPressRelease)。AltaVista是第一个支持自然语言搜索的搜索引擎。2003年AltaVista被Overture收购，后者是Yahoo的子公司。信息检索-1概论搜索引擎的后来之王：Google1995年，佩奇来到斯坦福读博士，开始网络链接结构方面的研究项目BackRub。之后，他和布林提出了PageRank技术，用于对网页评级之后用于搜索引擎，改写了搜索引擎的定义，建立了Google。信息检索-1概论搜索引擎的后来之王：GoogleGoogle在斯坦福引起了人们的关注。佩奇开始准备出售该技术，但是没有成功。Sun公司创始人的投资，随后成立公司。2000年和Yahoo合作，一飞冲天。2004年7月上市，市值250亿，增长速度超过微软。信息检索-1概论Google之特点专注、进取、朴素、低调、神话般的创业故事信息检索-1概论中文搜索引擎老大：百度2000.1李彦宏创立了百度。2001.8发布百度测试版。目前是最大的中文搜索引擎MP3搜索特色信息检索-1概论百度的特点专注于技术专注于中文搜索信息检索-1概论北大天网由北大计算机系网络与分布式系统研究室开发，于1997年10月29日正式在CERNET上提供服务。利用教育网优势，有强大的FTP搜索功能。信息检索-1概论中国互联网使用率

使用率

使用率信息渠道生活助手

网络新闻77.3%

网络求职15.2%搜索引擎74.8%

网络教育24.0%写博客19.1%

网络购物25.5%交流工具

网络销售4.3%即时通信69.8%

网上旅行预订3.9%电子邮件55.4%网上银行

20.9%娱乐工具

网上炒股14.1%网络音乐68.5%

网络影视61.1%

网络游戏47.0%

回目录信息检索-1概论信息检索信息检索-1概论什么是信息检索信息检索（InformationRetrieval，IR）就是从数据源中找到满足需求的信息的过程。传统信息检索根据笔画从字典中查找某字的读音和意思从《三国演义》中查找貂蝉出场的章节和地点从《概率论》中查找贝叶斯公式等等信息检索-1概论电子信息时代的信息检索从手机通信录中查找某条短信从电子词典中查找某单词的例句从某个网页中查找某关键字出现的地方从数据库中查询满足检索条件的记录本书重点要讨论的信息检索：从互联网中检索包含某个关键字的最相关的网页信息检索-1概论信息检索的定义GerardSalton’sdefinition:信息检索是关于信息的结构、分析、组织、存储、搜索（search）和获取（retrieval）的领域。“信息检索”一词含义非常宽泛，涵盖了很宽范围的信息类型和各种与搜索相关的应用。信息检索-1概论从20世纪50年代开始，该领域的主要焦点一直是文本(text)和文本形式的文档(textdocument)。网页、电子邮件、学术论文、图书和新闻报道只是文档类型中的一部分。文档和典型的数据库记录（例如银行账户记录或航班预定记录）最重要的区别在于，文档中的大部分信息以文本形式存放，文本是没有结构的。信息检索-1概论信息检索的另一个通俗的定义为：是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。术语“非结构化数据”（unstructureddata）指的是那些没有清晰和明显语义结构的数据，而计算机不易处理这类数据。信息检索-1概论严格意义上的非结构化数据在实际中并不存在:文本数据往往被认为是典型的非结构化数据，但是如果考虑文本中隐含的语言结构信息，那么它们也不能算是“

非结构化数据”。现实中的大部分文本仍然都有其他结构，如文本的标题、段落、脚注等，这些结构往往通过显式的标记来体现（如网页中的格式标签）。我们也把网页这种具有格式标记的数据称为“半结构化数据”（semi-structureddata）。例如对于新闻报道。报道有一些属性，比如标题和新闻来源，但重要的内容是报道本身。信息检索-1概论对比在数据库系统中:无论在格式上，还是在意义上，这两个属性都被非常精确地定义。要比较这些属性的值是非常容易非结构化情景中：对于提交给网络搜索引擎的查询，如果跟某篇报道有关，如具有“手机银行”或“网银”这样的字眼，则被返回给用户定义一个词、句子、段落或者整个新闻报道相关的意义，比定义一个账号要难得多，因此文本的比较并不容易对人们比较文本的过程进行理解和建模，并设计计算机算法以便精确地执行这种比较，是信息检索的核心信息检索-1概论检索对象：从文本到多媒体检索信息检索的应用包含了带有结构的多媒体文档、有意义的文本内容和其他媒体常见的信息媒体包括图片、视频、音频（包括音乐和语音）当前搜索非文本文档的技术依赖于对这些内容的文本描述，而不是这些媒体自身的内容。对媒体内容的直接比较技术正在不断进步，例如图片的比较信息检索-1概论信息检索应用通用搜索：万维网上进行的搜索是信息检索最常见的应用垂直搜索（Verticalsearch）是网络搜索的特殊形式，搜索被限制在特殊的主题上企业搜索(enterprisesearch)是在散布在企业内部网中的大量计算机文件中寻找所需的信息桌面搜索(desktopsearch)是企业搜索的个人版，信息源是存储在一台个人电脑中的文件集合，包括那些被浏览过的邮件和网页P2P搜索(peer-to-peersearch)是在节点机或计算机构成的网络中搜寻信息，但没有任何集中式的控制信息检索-1概论信息检索的任务基于用户查询的搜索(有时称为特殊搜索(adhocsearch)，因为查询的范围巨大而且事先没有约定）是搜索引擎研究的主要任务。其他任务包括过滤(filtering)分类(classification)问答(question

answering)“珠穆朗玛峰的高度是多少？”、“亚马逊河流有多长？”信息检索-1概论信息检索-1概论按照规模分类第一个级别是以

Web搜索（websearch）为代表的大规模级别，此时需要处理存储在数百万台计算机上的数十亿篇文档：如何采集到这种规模的文档？如何在这种大规模数据量的情况下建立高效运行的系统？如何应对Web特性所带来的特殊问题（比如欺骗）？FYI:2005年，网民可以在百度搜索到的网页数已经从1月份的6亿上升到现在的8亿，已经大大超越了google的大约5亿中文网页信息检索-1概论第二个级别是小规模，个人信息检索（personalinformationretrieval）:操作系统中已经融合的信息检索的功能桌面搜索(desktopsearch)邮件程序中的搜索功能、分类问题：如何处理个人计算机上各种格式的文档？如何保证搜索系统的免维护？如何在启动搜索系统、处理信息和使用磁盘时保持简单且占用的系统资源足够少而不至于对用户的正常工作造成影响？信息检索-1概论介于第一种大规模和第二种小规模之间的信息检索主要面对的是中等规模的数据，包括面向企业、机构和特定领域的搜索（domain-specificsearch）：公司内部文档专利库或生物医学文献学术论文的搜索这种情况下，文档往往存储在集中的文件系统中，由一台或者多台计算机提供搜索服务回目录信息检索-1概论信息检索中的关键问题回目录信息检索-1概论相关性(relevance)相关性是信息检索中的基本概念。相关文档包含用户把查询发给搜索引擎后他想要找的信息。对查询和文档进行简单的比较，寻找精确的匹配，那结果的相关性一定很差。蟑螂、小强bankmoney，bankmonkey信息检索-1概论话题相关(topicalrelevance)和用户相关(userrelevance)话题相关：如果一个文本与查询是话题相关的，就意味着两者有相同的话题。用户相关会考虑该报道的一些附加特性。“地震”玉树地震“限行政策”信息检索-1概论检索模型(retrievalmodel)一个检索模型是对查询与文档匹配过程的形式化表示，它是排序算法(rankingalgorithm)的基础，搜索引擎利用排序算法生成文档的有序列表一个好的检索模型能够找

到那些与提问者相关的文档。真实环境中的搜索引擎，必须使用包含了用户相关性的排序算法。在信息检索中，检索模型往往对文本的统计特征而不是语言结构建模。信息检索-1概论评价文本排序的质量依赖于该文本与用户期望的匹配程度在20世纪60年代，CyrilCleverdon率先制定了评价方法，他使用的两种评价指标，准确率(precision)和召回率(recall)，目前仍很流行准确率是非常符合直觉的评价指标，它是检索出来的文档中相关文档所占比例。召回率是全部相关文档中被检索出来的文档比例最知名的测试集是TREC(TextREtrievalConference，)评测会议提供的测试集检索模型和搜索引擎的评测是一个非常活跃的领域信息检索-1概论信息需求(informationneed)：用户交互信息需求是人们向搜索引擎发送查询的背后动因。用户是搜索质量的终极判定者。人们怎样与搜索引擎之间进行交互，帮助用户表达他们的信息需求文本查询通常是用户实际需求的一种很糟糕的描述。“猫”

“在哪儿能买到猫”OR“猫王”的信息?查询建议(querysuggestion)、查询扩展(queryexpansion)和相关反馈（relevancefeedback）回目录信息检索-1概论搜索引擎回目录信息检索-1概论搜索引擎是信息检索技术在大规模文本集合上的实际应用。“搜索引擎”一词原来是指为文本搜索服务的特殊的硬件。从20世纪80年代中期开始，在描述用来比较查询和文档并生成文档排序结果的软件系统时，逐渐更多地使用“搜索引擎”一词，而不是“信息检索系统”或者“全文检索系统”。信息检索-1概论搜索引擎的不同结构网络搜索引擎，比如Yahoo，必须能够捕获，或者说爬取(crawl)TB级的数据，并对每天收到的全世界数以百万计的查询提供亚秒级的响应时间。企业搜索引擎，比如Autonomy，必须能够处理一个公司内部不同类型的信息源，使用与公司有关的特殊知识作为搜索和相关任务(如数据挖掘(datamining))的一部分。数据挖掘指从数据中自动发现有趣的结构，也包括聚类(clustering)技术。桌面搜索引擎，比如google和百度的桌面搜索引擎，必须能够在人们制作和浏览新文档、网页和邮件时快速地合并，同时提供非常直观的界面来搜索这些非常异质的混合信息。信息检索-1概论OpenSourceSE开源(OpenSource)搜索引擎是另外一类重要的搜索系统，与商业搜索引擎有不同的设计目标Lucene是一个基于Java的流行的搜索引擎（也有C++和C#的实现），它已经被用于大范围的商业应用中，其中使用的信息检索技术相对简单Xapian是一个基于C++的开源的工具包，基于STL实现，越来越多的应用采用该组件信息检索-1概论搜索引擎设计中的重要问题搜索引擎设计中的重要问题包括了信息检索中的各种问题：有效的排序算法、评价及用户交互。大规模数据给搜索引擎带来了其他许多难题,首要问题是搜索引擎的性能:响应时间(responsetime)查询吞吐量(querythroughput)索引速度(indexingspeed)。信息检索-1概论新数据处理能力搜索要处理动态持续变化的信息。另一个重要的性能指标是把新数据合并到索引中的速度。覆盖率(coverage)衡量现存信息（比如在一个企业信息环境中）有多少被索引和存储在搜索引擎中。新近性(recency)或时新性(freshness)衡量所存信息的年龄(age)。信息检索-1概论可扩充性(scalability)搜索引擎可以用在小规模数据集上，也可以用于极大规模的数据集，比如整个互联网。对某个应用可能只有很少的一些用户，也可能有成千上万的用户。可扩充性(scalability)：设计应该考虑到数据量和用户量的增长。搜索引擎必须是可定制的(customizable)或者说是自适应的(adaptable)。这意味着搜索引擎的许多功能，比如排序算法、界面或索引策略，能够为满足新的应用需要而调整和适应FYI:GOOGLE的排序算法每天更新一次以上。信息检索-1概论特殊问题特殊问题也会影响搜索引擎的设计，最好的例子是网络搜索中的垃圾信息(spam)。垃圾信息(spam)：为某种商业利益而制作的文档中误导的、不合适的或不相关的信息。但搜索引擎必须处理的一种类型是文档中的垃圾词，这些词导致该文档能够在搜索引擎响应一些热门查询时被检索出来。由于垃圾索引(spamdexing)显著地导致搜索引擎排序质量的降低，网络搜索引擎的设计者不得不开发能够识别和删除这些垃圾文档的技术。信息检索-1概论回目录信息检索-1概论Web搜索引擎回目录信息检索-1概论背景与历史Web在很多方面都是空前的：不仅在规模上史无前例，而且其创建过程中协调机制的缺乏也是空前的Web参与者的背景和动机的多样性同样也是空前的以上的每一个因素都使得Web搜索有别于传统的文档搜索。一般来说Web搜索要困难得多。信息检索-1概论人人可以制作网页人们很容易就能阅读某个URL对应的原始HTML标记文档，这样新用户就无需太多的学习或者经验便可以创建自己的HTML内容，甚至可以选择喜欢的网页作为样例直接学习。浏览器会忽略其不能解析的内容，这个特点使得Web内容的创建和使用能够被迅速扩散开来。在Web上发布网页已经不是少数训练有素的编程人员的特权，而是上亿普通网民参与的活动。对于大部分的用户和需求来说，Web已经迅速成为提供和消费各种信息的重要场所，这些信息包括从疑难杂症到地铁时刻表的任何内容。信息检索-1概论信息发现的尝试如果其他用户不能发现并使用Web上发布的大量信息，那么这些信息实际上就毫无价值。有关Web信息发现的早期尝试可以归成两类：(i)像Altavista、Excite和Infoseek一样的基于全文索引的搜索引擎(ii)诸如Yahoo!的Web网页分类体系

前者在前台给用户提供了关键词搜索界面，而在后台则采用前面介绍的倒排索引和排序机制。后者可以允许用户沿树形结构的类别体系进行浏览。信息检索-1概论Web网页分类体系Web网页分类体系很多缺点：大部分工作都是人工编辑完成，那么随着Web规模的扩大这种做法很难扩展要准确发现Web网页并把它们分到类别节点上去，用户的理解必须要和分类体系的编辑人员一致当类别体系的规模急剧增长时，这一点也变得相当具有挑战性。Yahoo!的分类体系很早就超过了1000个的节点。FYI:Open

Directory

Project

（）是互联网上最大的，最广泛的人工目录。它是由来自世界各地的志愿者共同维护与建设的最大的全球目录社区。信息检索-1概论第一代Web搜索引擎第一代Web搜索引擎将前面介绍的传统搜索技术应用到Web领域，它们主要关注规模上的挑战性。最早的Web搜索引擎必须要处理包含上千万文档的索引，而这个规模比以前所有的公共域IR系统的数据规模要高很多个数量级。第一代Web搜索引擎针对上述挑战取得了巨大成功，它们能够持续索引很大一部分Web页面，并且能在亚秒级时间内完成对查询的应答。搜索结果的质量和相关性离期望还有很大的距离。这就亟需研发出新的排序机制和反作弊技术来提高搜索质量。而且必须要度量文档的权威度（authoritativeness），即计算权重度时可利用诸如其所在网站之类的信息。信息检索-1概论Web的信任问题由于网络内容的创作具有极大的民主化，所以这就意味着几乎在任何一个话题上都会出现一些粒度更细的不同观点。这也表示Web中包含真理、谎言、矛盾和大量猜测。我们应该相信哪些Web网页？传统的非Web出版方式下，这并不是个问题，用户可以自己选择他们认为可信的来源。需要指出的一点是，可能并不存在统一的、与用户无关的可信度标准，对某个用户可信的网页内容不一定对其他用户可信。我们将基于链接分析技术考察理解上述问题的方法。信息检索-1概论Web到底有多大？Web到底有多大？“某个搜索引擎中索引的网页数目是多少？”到1995年底，Altavista声称它采集并索引了大概三千万个静态网页。动态页面（dynamicpage）通常是由应用服务器应答数据库的查询需求时产生的。这种页面的一个标志是URL中通常包含字符“?”。在1995年时，由于大家相信每过几个月静态页面的数目就会翻番，所以早期的包括Altavista在内的Web搜索引擎必须要经常增加硬件和带宽来采集和索引网页。信息检索-1概论Web图我们可以将整个静态Web看成是静态HTML网页通过超链接互相连接而成的有向图，其中每个网页是图的顶点，而每个超链接则代表一个有向边。一个网页的入链接数目被称为这个网页的入度（in-degree），在一系列研究中得到的网页的平均入度大概从8到15左右不等。信息检索-1概论该例子中共有6个网页，网页B的入度为3、出度为1。该图不是强连通图，因为B不可能到A。信息检索-1概论连接的分布有充分的证据表明，这些链接并不满足随机分布。如果每个网页都是随机均匀地选择链接目标时，那么链接到一个网页的链接数目应该满足泊松分布，但是实际中的数目并不满足预想的泊松分布。实际上，有大量研究表明这个分布满足幂分布定律（powerlaw），具有入度为i的网页总数目正比于1/iα

，研究中一个有代表性的α值是2.1。信息检索-1概论一些研究表明，整个Web有向图结构是个蝴蝶结(bowtie)形：从IN中的任一网页出发通过超链接到达SCC的任一网页，从SCC中的网页达到OUT中的任一网页。从SCC中的任一网页可以到达SCC中的其他网页。不可能从SCC中的网页到达IN的任一网页，也不能从OUT中的网页到达SCC中的任一网页信息检索-1概论IN和OUT的规模大致相当，而SCC的规模则稍大，大部分网页都落入到这三大类中。剩余的网页构成了所谓管道（tube），它由少部分SCC之外的网页组成，可以直接将IN和OUT中的网页相连。另外，还有一些不能从IN到达或者只能到达OUT的网页构成的所谓卷须（tendril）。信息检索-1概论作弊网页Web搜索引擎显然是连接广告商和顾客的一种重要途径！例如：用户在搜索“Chicagogolfrealestate”时，他想做的不仅仅是搜索有关Chicago的高尔夫球场地产的新闻或者娱乐信息，而且很可能要寻找并购买这样的地产。这导致了第一代作弊网页（spam）:即通过操作网页内容来达到在某些关键词的搜索结果中排名较高的目的。为了避免用户对这些冗余和重复信息的极度反感，一些老练的作弊者还会采用一些手段和技巧，比如将这些重复的词设置成和背景一样的颜色。信息检索-1概论伪装作弊者也发展出了更多的作弊技术。一种技术被称为伪装（cloaking）根据http请求是来自搜