第一讲概述

第一讲概述信息检索：即从一堆东西（集合）中找到用户所需要的（子集）。蕴含的问题是：这堆东西是什么？存放在哪里？怎么存放？怎么找？例如：汉语字典1、是什么？所有汉字及其解释。2、在哪里？印刷在纸上。3、怎么存放？按汉语拼音顺序存放。4、怎么找？(1)建立一个汉语拼音的索引。(2)建立一个偏旁部首的一级索引，再建立一个笔划数目的二级索引。可见，索引既是一种结构，也是一种查找（检索）方法。且是重要的环节。5、一些特殊的汉字如何处理？建立一个难索字表。亻宀…四画价优…（正文内容）结构化与非结构化数据的检索我们所讨论的是计算机（数字设备）上存储的数据（信息）如何检索的问题。蕴含的问题是：数据从哪里来？如何存放？如何查找？目前，解决该问题的成熟、流行和高效的方法是建立数据库系统。1、数据库存放数据要求是结构化的，即关系表。这就是如何存放的问题。2、数据库检索数据的方法是SQL。这就是如何查找的问题。selectsno,sname,sagefromstudentwheresage18andsdept=‘CS’数据库技术较难解决的问题：1、若数据是一些文本呢？如一段文字，甚至是一本书。而这些的文本众多。2、若数据是许多图片、音频、视频呢？这些统称为多媒体数据。这些数据的特点是：海量、难以结构化（称非结构化数据）。目前，信息检索一般是指从非结构化的信息集合中找出与用户需求相关的信息。信息检索现状1、商业成功案例：网络搜索引擎(1)如谷歌、百度等等。出现了新的商机，出售关键词。(2)商业竞争的背后是科技实力、创新思维的竞争。(3)搜索引擎的关注者：企业：是否投入广告。网站经营者：如何使自己的网页排在搜索结果前面。普通网民：搜索所需信息。学者：研究其原理、实现方式、如何高效而准确、拓宽应用。2、应用效果不理想。主要原因是理论基础不完善。3、你还能想到什么应用？（这往往意味着新的商机）手机短信检索：可用于监控。论文比对系统：判别论文的抄袭现象。自动问答系统：替代人工问答，企业咨询自动化。企业内部信息搜索：可做到较为精准，提供决策支持。指纹、人脸识别系统：属图像检索，为公安侦破提供帮助。浏览器网页内容过滤：防止浏览到不良信息，为家长解决后顾之忧。信息检索系统一般结构这里的文档是一个较为宽泛的概念，它可以是一篇文章，甚至一本书，也可以是一个自然段，或一句语，甚至是一幅图像，等等。即作为被检索的一个逻辑单元。如在网页检索中，一个网页即可做为一个文档。用户查询接口搜索引擎数据源获取预处理/结构化特征库索引网络文档集对于特征库，这里蕴含的问题是文档的特征是什么？如网页文本内容的特征是什么？指纹图像的特征是什么？等等。本课程主要研究内容以Internet网页检索为应用背景，主要研究文本数据的组织与检索方法，简单介绍图像检索问题。具体涉及以下主要内容：1、数据的获取：即如何抓取网页及提取文本内容。2、文本特征的提取：即如何进行中文切词。3、特征数据的组织：即索引的建立问题，也是数据结构问题。4、检索的方法：即各种检索模型的研究。5、简单介绍图像特征及检索的初步问题。6、为实现上述过程所涉及的技术细节。课程最终目标：能独立完全一个简单的文本检索系统。实验安排：1、网页的抓取和超链接提取2、中文切词3、基于向量空间模型的实现信息检索技术研究与应用面临的主要困境1、数据海量。这加大了检索准确性和效率的难度，甚至形成一对矛盾。2、数据不断更新。体现在数据不断消失的同时，还不断增加。这为检索系统文档集的实效性提出挑战。3、机器的自然语言理解。人类使用自然理解，但机器理解和翻译目前还很不理想，难度极大。有时语句的词法、语法、语义对人脑都难以理解。4、特征提取很不成熟。文档的精确特征是什么？许多特征就是人类自身都很难说清楚。如一篇文章讲的是什么事？在茫茫人海中你是怎么识别出你熟悉的面孔的？甚至听见脚步声都知道是谁，这个脚步声形成的音频有什么特征？5、检索要求的表达。该问题与机器的自然语言理解有关。除此之处，还与用户的表示不清楚有关，使检索系统从源头上（即检索要求的表达）就存在误差。但很难设计出一种既便于机器理解，又能适合人类表达的规范化或格式化语言。信息检索系统的评价检索系统作为软件系统，当然需要从系统所占用的空间和响应时间两个角度来评价。除此之外，还有一些其它的评价指标。评价和比较检索系统性能时，需要以下条件：1、一个文档集合C。系统将从该集合中按照查询要求检出相关文档。2、一组用户查询{q1,q2,…,qn}。每个查询qi描述了用户的信息要求。3、对应每个用户查询要求的相关文档集{R1,R2,…,Rn}。该集合可人工事先给定。4、一组评价指标。这些指标能够反映系统的检索性能。通过比较检索系统实际检出的结果文档集和标准的相关文档集，从而得到评价指标值。一般来说，检索系统的检索结果都是文档的序列，相关程度高的文档排在前面。准确率和召回率设有查询q，q对应的标准相关文档集为R。用某给定检索系统针对q进行检索，得到检出结果A。令Ra为A与R的交集。CRARa准确率：即系统检出的相关文档数与检出文档数的比值，即召回率：即系统检出的相关文档数与实际相关文档数的比值，即aRPAaRRR显然，希望系统的准确率和召回率均越高越好。准确率和召回率计算示例假定针对查询q的相关文档集为Rq={d2,d5,d9,d12,d23}，共5个。而实际检出文档集为Aq={d3,d4,d5,d6,d8,d10,d12,d19,d20,d23}，共10个文档。则检索准确率为：P=3/10=0.3；召回率为：R=3/5=0.6。但一般情况下，检索系统返回的检索结果比较多，且结果按相关度排序输出。这时可从第一篇文档开始依次查看排序列表，每查看到一篇相关文档时，则以查看过的文档作为检出结果集来计算准确率和召回率，这就会得到一系列的准确率和召回率之值，将这些值以召回率为横坐标，准确率为纵坐标绘制一条曲线，该曲线较好地反映了检索系统的性能。称为准确率/召回率曲线。如上例，可得准确率/召回率曲线为：RP1/32/73/10有时也常采用10点标准召回率下的准确率曲线，即计算召回率分别为0.1、0.2、0.3、…、1共计10个点下的准确率，从而绘制曲线来评价检索系统。平均准确率由于不可能仅使用一次检索的结果来评价检索系统，而往往要使用多次的不同检索来评价。这该如何评价呢？可以对每个召回率水平下的准确率进行平均化处理，称为平均准确率，即11()()qNiiqPrPrN式中，Nq为使用的检索总数；Pi(r)是召回率为r时的第i次检索的准确率。例如，某检索系统在使用q1检索时，在召回率为0.1下的准确率为0.8；在使用q2检索时，在召回率为0.1下的准确率为0.6；在使用q3检索时，在召回率为0.1下的准确率为0.3；则该系统在召回率为0.1下的平均准确率为(0.8+0.6+0.3)/3≈0.567；已检出相关文档的平均准确率均值下面介绍几个单值评价方法。已检出相关文档的平均准确率定义为：11riiMAPri第个相关文档的位置式中，r为相关文档数。例如，在使用q1检索时，有4个相关文档，其位置分别为1、2、4、7；在使用q2检索时，有5个相关文档，但只检出3个，其位置分别为1、3、5；此时，对于q1，平均准确率为(1/1+2/2+3/4+4/7)/4≈0.83对于q2，平均准确率为(1/1+2/3+3/5+0+0)/5≈0.45因此，MAP=(0.83+0.45)/2=0.64该评价指标反映了相关文档在检出结果中所在位置的重要程度，即顺序越靠前则该指标值越大。若针对多次检索，则该准确率取均值即可。P@10准确率和R准确率P@10准确率：即检索结果中前10个检出文档的准确率。该指标考虑了人在使用检索系统时中行为特征，即一般人们总是希望能在检出结果的前10个就能得到所需要文档。例如，若针对q1有50篇相关文档，针对q2有10篇相关文档。在使用q1检索时，若前50个中有17篇为相关文档，则其R准确率为17/50=0.34在使用q2检索时，若前10个中有7篇为相关文档，则其R准确率为7/10=0.7则此时，平均R准确率为(0.34+0.7)/2=0.52。例如，在检出结果前10篇文档中有3篇为相关文档，则P@10准确率为0.3。R准确率：若当前检索q共有R篇相关文档，则计算检出结果中前R篇文档的准确率。即RRpR前篇文档中相关文档数准确率直方图当评价两个检索算法（系统）时，可采用准确率直方图来比较。即使用同一评价指标，在多次检索的基础上，分别计算出两种不同算法的评价指标值，并作差，然后以该差值绘制一个直方图。例如，针对检索算法A和检索算法B，采用R准确率，分别进行10次不同的检索，分别得到算法A和算法B的10个不同的R准确率值，记为RPA(i)和PRB(i)，然后以RPA(i)-PRB(i)的差值作直方图。12345678910q1-1从该直方图中可明显看出，算法A的检索性能要优于算法B。调和均值与E均值评价指标这两个评价指标可以将准确率和召回率综合为一个数值。调和均值定义：211FPR显然，只有当准确率和召回率都比较高时，F值才较高。E均值定义：2211bEbPR式中，b值由用户给定，用来强调在评价时准确率和召回率的不同重要程度。当b=1时，强调准确率和召回率同等重要，该值即为调和均值。当b1时，强调在评价时召回率的重要性。当b1时，强调在评价时准确率的重要性。面向用户的评价方法其中，U表示用户已知的相关文档集，Rk表示检出的用户已知的相关文档集，Ru表示所检出的用户未知的相关文档集。覆盖率定义：RkCUCRARkRuU即在用户已知的相关文档集中检出相关文档所占比率。新颖率定义：RuNRkRu即在检出的相关文档中用户未知的相关文档所占比例。相对查全率：定义为检出的相关文档数与用户期望得到的相关文档数之比。召回率负担：定义为用户期望得到的相关文档数与要得到这些相关文档所需检索的文档总数的比值。国内外信息检索评测通过以上讨论，若要对检索算法进行评价，必须要有一个较权威的评测样本集。显然，样本集的采集是很费时费力的。目前，在国际信息检索评测方面，有影响力的三个组织分别为：1、美国的TREC（TextREtrievalConference）。其文档主要来源于新闻和报纸，以英文为主，也包括汉语在内的其它语种文档。大约有一百多万篇文档。我国清华大学、北京大学、哈工大、中科院等多家单位都参加了该项评测活动。2、日本的NTCIR（NIITextCollectionforInformationRetrievalSystems）3、欧盟的CLEF（CrossLanguageEvaluationForum）国内比较有影响的是863信息检索评测项目、全国搜索引擎和网上信息挖掘会议（SEWM）。其中，863信息检索评测项目在2004年从网络上搜集获得了五百七十多万个网页，容量为90GB的网页文档数据构成评测数据集。显然，在大量的文档集中，针对每一个检索q，由人事先给出一个相关文档集是不实现的。主要的搜索引擎目前，Internet上的搜索引擎可以说是成千上万，几乎每个网站都设有搜索功能，它们要么提供站内的搜索服务，要么提供整个Internet信息搜索服务。这里所列出的主要英文搜索引擎几乎都同时支持对汉语的搜索。1、Yahoo一个较难欢迎、访问频率很高的门户网站。2、Altavista号称最大的搜索引擎。即搜索范围非常大，搜索结果也十分丰富。3、Excite最大特点是提供概念检索。如检索“computer”，则结果中包括“PC”等。4、Lycos资格最老的搜索引擎之一。搜索范围广，据说覆盖了全球90%的主页。5、Google商业推广和动作最成功的搜索引擎。6、主要的中文搜索引擎有：中文雅虎、搜狐、新浪、网易、百度。主要的学术文献数据库检索系统1、美国《工程索引》（Ei）数据库2、英国《科学文献》（INSPEC）数据库3、美国《科学引文索引（SCI）网络数据库4、中国科技期刊全文数据库（CNKI）5、万方数字化期