信息检索模型课件.ppt

1、信息检索n信息检索信息检索（information retrieval，IR），将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程。n发展的几个阶段 n手工检索(早期,情报检索)n穿孔卡片检索(1950s)n计算机检索(面向主题,1960s)n联机检索（1970s,1980s)nWeb检索(1990s)Ad hoc retrieval(特别检索:文档集合保持不变)Collection“Fixed Size”Q2Q3Q1Q4Q5IR的两种形式:Ad Hoc and FilteringFiltering(过滤:用户需求不变)Documents StreamUser 1Profil

2、eUser 2ProfileDocs Filteredfor User 2Docs forUser 1IR的两种形式:Ad Hoc and Filtering相关概念n停用词停用词（stop word），指文档中出现的连词，介词，冠词等并无太大意义的词。例如在英文中常用的停用词有the，a,it等；在中文中常见的有“是”，“的”，“地”等。n索引词索引词（标引词，关键祠）:可以用于指代文档内容的预选词语,一般为名词或名词词组.n词干提取词干提取（英文中）countries=country，interesting=interestn组合词组合词:北京大学n中文中文分词分词（word segmen

3、tation），或称切词切词，主要在中文信息处理中使用，即把一句话分成一个词的序列。如，“网络与分布式系统实验室”，分词为“网络/与/分布式/系统/实验室/”。信息检索模型信息检索模型的概述信息检索模型n信息检索模型信息检索模型（IR model），依照用户查询，对文档集合进行相关排序的一组前提假设和算法。IR模型可形式地表示为一个四元组 其中D是一个文档集合，Q是一个查询集合，F是一个对文档和查询建模的框架，R(qi,dj)是一个排序函数，它给查询qi和文档dj之间的相关度赋予一个排序值文档逻辑视图nD是一个文档集合，通常由文档逻辑视图来表示。文档逻辑视图可以是一组索引词或关键词。也可以用n

4、-gram方式表示。既可以自动提取，也可以是由人主观指定。（从全文到一组标引词）信息检索模型nQ是一个查询集合，用户任务的表达，由查询需求的逻辑视图来表示。nF是一个框架,用以构建文档,查询以及它们之间关系的模型nR(qi,dj)是一个排序函数，它给查询qi和文档 dj 之间的相关度赋予一个排序值n即:IR模型由上述四个要素组成 信息检索模型的分类三类:基于内容的信息检索模型,结构化模型,浏览型检索模型.基于内容的信息检索模型有n集合论模型：布尔模型、模糊集合模型、扩展布尔模型n代数模型：向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型n概率模型：经典概率论模型、推理网络模型、置

5、信（信念）网络模型非重叠链表模型邻近结点模型 结构化模型 检索:特别检索 过滤 浏览 用户任务 经典模型 布尔模型 向量模型 概率模型 集合论模型 模糊集合论模型 可扩展布尔模型 概率模型 推理网络模型 信任度网络模型 代数模型 广义向量模型 潜语义标引模型 神经网络模型 浏览 扁平式模型 结构导向模型 超文本模型信息检索模型的分类经典信息检索模型n布尔模型n向量空间模型n经典概率模型经典信息检索模型n经典的信息检索模型有三个：布尔模型、向量模型和概率模型。n每篇文档可以用一组有代表性的关键词即索引词集合来描述。索引词是文档中的词，其语义可以帮助理解文档的主题；因此，索引词常用于编制索引和概括

6、文档的内容。n索引词通常由名词构成，因为名词本身具有语义，人们能够比较容易地理解它的意思。形容词、副词、连词很少作为索引词，因为它们主要起补充作用，不能单独表示语义。布尔模型(Boolean Model)布尔检索模型n一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。n 遵循两条基本规则:每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为 0或1。n查询是由三种布尔逻辑运算符 and,or,not 连接索引词组成的布尔表达式。n根据布尔逻辑的运算规定，提问式可以被表示成由合取子项（conjunctive component）组成的析取范式（disjunctive norma

7、l form，简称DNF）形式。离散数学相关概念n用连词把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。p并且q，记作“pq”n用连词把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。p或q，记作“pq”n非p p离散数学相关概念n析取范式：仅由有限个简单合取式构成的析取式A=(pqr)(pq)(qq)n合取范式：仅由有限个简单析取式构成的合取式A=(pqr)(pq)(qq)n范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式离散数学相关概念n主析取范式主析取范式极小项极小项在n个变元的简单合取式中，若每个变元与其否定不同时存在，

8、而二者之一必出现且仅出现一次，这种合取式叫做极小项n任何命题公式的主析取范式都是存在的，并且是唯一的。定义形如AA1A2An基中Ai(I=1,2,3n)为极小项极小项记为：（m1m2m2n-1)布尔检索模型n首先，将查询转化为一个析取范式DNFn 例如：查询为 n进一步表达为 n即：每一个分量都是三元组 的二值向量()abcqkkk(1,1,1)(1,1,0)(1,0,0)dnfq(,)abckkk(1,1,1)(1,0,0)(1,1,0)KaKbKc布尔检索模型n定义：用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分量。文献dj 与查询q的相似度为如果 ，则表示文献dj与q相关

9、，否则为不相关。sim(dj,q)为该模型的匹配函数。ccccdnfcc1 if q|(qq)(,()(q)(,)0 otherwiseiijijk g dgsim d q(,)1jsim dq 布尔检索模型简单实例nq=病毒 AND（计算机 OR 电脑）AND NOT医 nd1:据报道，计算机病毒近日猖獗nd2:小王虽然是学医的，但对研究电脑病毒也很感兴趣，最近发明了一种nd3:计算机程序发现了爱滋病病毒的传播途径 n哪些文档会被检索出来？布尔模型n文档表示n一个文档被表示为关键词的集合n查询式表示n查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先

10、次序n匹配n一个文档当且仅当它能够满足布尔查询式时，才将其检索出来n检索策略基于二值判定标准n不同的系统可以使用:n不同的去除停用词(stopword removal)策略和stemming策略n索引中不同类型的辅助信息n不同的实现方法优点n到目前为止，布尔模型是最常用的检索模型，因为：n由于查询简单，因此容易理解，简洁的形式化。n通过使用复杂的布尔表达式，可以很方便地控制查询结果n相当有效的实现方法n相当于识别包含了一个某个特定term的文档n经过某种训练的用户可以容易地写出布尔查询式n布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”问题n布尔模型被认为是功能最弱的方式，其主要问题

11、在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回n非常刚性:“与”意味着全部;“或”意味着任何一个n如果“我想要n个词中m个词同时出现的文档”，怎么表示？n不可能企望用户自己规定m值n系统可以从m=n开始，然后逐渐减少m，但很麻烦n很难表示用户复杂的需求，准确匹配，信息需求的能力表达不足n很难控制被检索的文档数量n原则上讲，所有被匹配的文档都将被返回n很难对输出进行排序n不考虑索引词的权重，所有文档都以相同的方式和查询相匹配n很难进行自动的相关反馈n如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？向量空间模型向量空间模型 n向量空间模型(Vector Space

12、 Model,VSM)n相比于布尔模型要求的准确匹配,由美国信息处理专家萨尔顿（G.Salton）在20世纪60年代末提出的。VSM模型采用了“部分匹配”的检索策略（即：出现部分索引词也可以出现在检索结果中）。n通过给查询或文档中的索引词分配非二值权值来实现。n通过计算D和Q的similarity作为它们之间的relevance（相似性作为相关性判断）n向量空间的原理(1)文档向量的构造(2)提问向量的构造(3)匹配函数的选择及相似度的确定向量空间模型 n词典,=k1,k2,ktnd=n此时，变量wi称为权值，非负；表示对应词项ki对于判断d和查询q相关性的重要程度（注意，这里的q是一般的，而

13、d是具体的）nq=n变量vi的含义类似于win两个基本问题：如何定义wi和vi；如何计算R(d,q)？向量空间模型 n让wi和vi为对应的词分别在d和q中出现的次数，于是我们有了两个m维向量，用夹角的cos表示“接近度”，即nR(d,q)=cos(d,q)=dq/|d|q|n认为认为：cos(di,q)cos(dj,q)，则，则di比比dj与与q更相关更相关。n通常系统就会取前若干个结果返回给用户n例如天网返回3000，虽然可能查出了几十万向量空间模型n在索引词权值的计算方案有很多种。在进行加权计算时，索引词权值的大小主要依赖于对索引词的各种频率数据的统计，并通常考虑两个方面的因素局部权值和全

14、局权值n局部权值是指第i个索引词在第j篇文档中的权值。tfij表示n全局权值指第i个索引词在整个系统文档集合中的权值。idfi表示向量空间模型n假设，N为系统的文档总数nni为系统中含有索引词ki的文档数nfreqij 为索引词ki在文档dj中出现次数nidfi表示索引词ki的逆文档频率nmaxtfj表示文档dj中所有索引词出现次数的最大值向量空间模型 n权值wij的选取方法：n对文档向量dj的构造，考察：n局部权值 tfij=freqij/maxtfjn全局权值 idfi=log(N/ni)n索引词权值 wij=tfij*idfin 称为tfidf（词频逆文档频率），最流行的权值计算公示n任

15、意文档dj（w1j，w2j，.，wtj），t维向量向量空间模型n查询向量的构造：nq（w1q，w2q，.，wtq），t维向量nwiq表示第i个索引词ki 在提问q中的权值n索引词权值:wiq=(0.5+0.5*freqiq/maxtfq)*idfinfreqiq 为在表述用户信息需求的文本内容中索引词ki的出现次数 nmaxtfq为在表述用户信息需求的文本内容中使用的所有索引词出现次数的最大值 向量空间模型 n重要的学术贡献，用了几十年nG.Salton and M.E.Lesk,“Computer evaluation of indexing and text processing,”Jou

16、rnal of the ACM,15(1):8-38,January 1968.nG.Salton,The SMART Retrieval System Experiments in Automatic Document Processing.Prentice Hall Inc.,1971.n实践证明，尽管VSM在许多方面依然和“现实”都不符，但实际效果不错（至少比布尔模型好很多）向量空间模型 n综合题：综合题：按照下述描述和要求完成相关工作按照下述描述和要求完成相关工作 n给定文档语料给定文档语料:nd1:北京安立文高新技术公司 nd2:新一代的网络访问技术nd3:北京卫星网络有限公司 nd

17、4:是最先进的总线技术。nd5:北京升平卫星技术有限公司的新技术有。向量空间模型 n利用中文切分词软件，分别得到用利用中文切分词软件，分别得到用“/”分开分开的一些字词：的一些字词：nd1:北京/安/立/文/高新/技术/公司/nd2:新/一/代/的/网络/访问/技术/nd3:北京/卫星/网络/有限/公司/nd4:是/最/先进/的/总线/技术/。nd5:北京/升/平/卫星/技术/有限/公司/的/新/技术/有。向量空间模型 n你的任务是设计一个针对这些文档的信息检你的任务是设计一个针对这些文档的信息检索系统。具体要求是：索系统。具体要求是：n(1).给出系统的有效词汇集合（说明取舍原因）。(2).

18、写出d1和d2在VSM中的表示（使用tf*idf，写出各项的数字表达式，具体数值不必实际计算出来）。(3).画出系统的倒排文件示意图。(4).按照向量夹角的余弦计算公式，给出针对查询“技术的公司”的前3个反馈结果。向量空间模型 n特点：基于多值相关性判断、基于统计学方法的词加权处理模式、采用检索结果的排序输出策略。搜索引擎采用的检索模型n搜索引擎采用了布尔模型和向量空间模型结合的方法来进行信息检索，布尔模型的检索效率高且易于实现；向量空间模型能够提高检索的相似度，通过相似度排序的手段能够大大改善查询效果，因此搜索引擎将二者的优势相结合，完整的检索过程如图所示。分词学习信息检索学习 信息检索倒排

19、表检索包含“学习”文档列表包含“信息检索”文档列表文档列表求交集既包含“学习”也包含“信息检索”文档列表学习 信息检索向量化求向量相似度按相似度排序输出图中方块为计算部分，斜方块为数据部分n本计算中可能会得到负相关，如果考虑到Na,Nb都是小量，可以忽略，那么CorrAB=Nab/(Na+Nb-Nab)至此，要计算相关度之间的全部要素都获得了。思考，那么到底 学校 和学生 之间的相关度是多少呢？我们利用google来回答这个问题吧：约有91,700,000项符合学校的查询结果约有88,200,000项符合学生的查询结果约有48,900,000项符合学生 学校的查询结果Corr学校，学生48,900,000/(91,700,000+88,200,000-48,900,000)=0.37这样，学校和学生的相关度是0.37n练 习 简 述 信 息 检 索 三 种 基 本 模 型(boolean model,vector model,probabilistic model)。