信息检索模型课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息检索,信息检索,（,information retrieval,，,IR,），将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程。,发展的几个阶段,手工检索(早期,情报检索),穿孔卡片检索(1950s),计算机检索(面向主题,1960s),联机检索（1970s,1980s),Web,检索(1990s),信息检索信息检索（information retrieval,1,Ad hoc retrieval,(特别检索:文档集合保持不变),Collection,“Fixed Size”,Q2,Q3,Q1,Q4,Q5,IR的两种形式,:Ad Hoc and Filtering,Ad hoc retrieval(特别检索:文档集合保持,2,Filtering(,过滤:用户需求不变,),Documents Stream,User 1,Profile,User 2,Profile,Docs Filtered,for User 2,Docs for,User 1,IR的两种形式,:Ad Hoc and Filtering,Filtering(过滤:用户需求不变)Documents,3,相关概念,停用词,（stop word）,，指文档中出现的连词，介词，冠词等并无太大意义,的,词。例如,在英文中常用的停用词有the，a,it等；在中文中常见的有“是”，“的”，“地”等。,索引词,（标引词，关键祠）:可以用于指代文档内容的预选词语,一般为名词或名词词组.,词干提取,（,英文中,）,countries=country，interesting=interest,组合词,:北京大学,中文,分词,（word segmentation），或称,切词,，主要在中文信息处理中使用，即把一句话分成一个词的序列。如，“网络与分布式系统实验室”，分词为“网络/与/分布式/系统/实验室/”。,相关概念停用词（stop word），指文档中出现的连词，,4,信息检索模型,信息检索模型,5,信息检索模型的概述,信息检索模型的概述,6,信息检索模型,信息检索模型,（,IR model,），依照用户查询，对文档集合进行相关排序的一组前提假设和算法。,IR,模型可形式地表示为一个四元组,其中,D,是一个文档集合，,Q,是一个查询集合，,F,是一个对文档和查询建模的框架，,R(q,i,d,j,),是一个排序函数，它给查询,q,i,和文档,d,j,之间的相关度赋予一个排序值,信息检索模型信息检索模型（IR model），依照用户查询，,7,文档逻辑视图,D,是一个文档集合，通常由文档逻辑视图来表示。文档逻辑视图可以是一组索引词或关键词。也可以用n-gram方式表示。既可以自动提取，也可以是由人主观指定。（从全文到一组标引词）,文档逻辑视图D是一个文档集合，通常由文档逻辑视图来表示。文档,8,信息检索模型,Q,是一个查询集合，用户任务的表达，由查询需求的逻辑视图来表示。,F,是一个框架,用以构建文档,查询以及,它们之间关系的模型,R(q,i,d,j,),是一个排序函数，它给查询,q,i,和文档,d,j,之间的相关度赋予一个排序值,即:,IR,模型由上述四个要素组成,信息检索模型Q是一个查询集合，用户任务的表达，由查询需求的逻,9,信息检索模型的分类,三类:基于内容的信息检索模型,结构化模型,浏览型检索模型.,基于内容的信息检索模型有,集合论模型：,布尔模型,、模糊,集合模型,、扩展布尔模型,代数模型：,向量空间模型,、广义向量空间模型、潜在语义标引模型、神经网络模型,概率模型：,经典概率论模型,、推理网络模型、置信（信念）网络模型,信息检索模型的分类三类:基于内容的信息检索模型,结构化模,10,非重叠链表模型,邻近结点模型,结构化模型,检索,:,特别检索,过滤,浏览,用户任务,经典模型,布尔模型,向量模型,概率模型,集合论模型,模糊集合论模型,可扩展布尔模型,概率模型,推理网络模型,信任度网络模型,代数模型,广义向量模型,潜语义标引模型,神经网络模型,浏览,扁平式模型,结构导向模型,超文本模型,信息检索模型的分类,非重叠链表模型 结构化模型 检索:浏览 经典模型,11,经典信息检索模型,布尔模型,向量空间模型,经典概率模型,经典信息检索模型,12,经典信息检索模型,经典的信息检索模型有三个：布尔模型、向量模型和概率模型。,每篇文档可以用一组有代表性的关键词即索引词集合来描述。索引词是文档中的词，其语义可以帮助理解文档的主题；因此，索引词常用于编制索引和概括文档的内容。,索引词通常由名词构成，因为名词本身具有语义，人们能够比较容易地理解它的意思。形容词、副词、连词很少作为索引词，因为它们主要起补充作用，不能单独表示语义。,经典信息检索模型经典的信息检索模型有三个：布尔模型、向量模型,13,布尔模型(Boolean Model),布尔模型(Boolean Model),14,布尔检索模型,一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。,遵循两条基本规则,:,每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为,0,或,1,。,查询是由三种布尔逻辑运算符,and,or,not,连接索引词组成的布尔表达式。,根据布尔逻辑的运算规定，提问式可以被表示成由合取子项（conjunctive component）组成的析取范式（disjunctive normal form，简称DNF）形式。,布尔检索模型一种简单的检索模型，它建立在经典的集合论和布尔代,15,离散数学相关概念,用连词把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。p并且q，记作“pq”,用连词把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。p或q，记作“pq”,非,p,p,离散数学相关概念用连词把几个公式连接起来而构成的公式叫做合,16,离散数学相关概念,析取范式：仅由有限个简单合取式构成的析取式,A=(pqr)(pq)(qq),合取范式：仅由有限个简单析取式构成的合取式,A=(pqr)(pq)(qq),范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式,离散数学相关概念析取范式：仅由有限个简单合取式构成的析取式,17,离散数学相关概念,主析取范式,极小项,在n个变元的简单合取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种合取式叫做极小项,任何命题公式的主析取范式都是存在的，并且是唯一的。,定义形如AA,1,A,2,A,n,基中Ai(I=1,2,3n)为,极小项,记为：（m1m2m2n-1),离散数学相关概念主析取范式定义形如AA1A2A,18,布尔检索模型,首先，将查询转化为一个析取范式,DNF,例如：查询为,进一步表达为,即：每一个分量都是三元组,的二值向量,(1,1,1),(1,0,0),(1,1,0),Ka,Kb,Kc,布尔检索模型首先，将查询转化为一个析取范式DNF(1,1,1,19,布尔检索模型,定义：用,q,dnf,表示查询,q,的析取范式，,q,cc,表示,q,dnf,的任意合取分量。文献,d,j,与查询,q,的相似度为,如果 ，则表示文献,dj,与,q,相关，否则为不相关。,sim(dj,q),为该模型的匹配函数。,布尔检索模型定义：用qdnf表示查询q的析取范式，qcc表示,20,布尔检索模型,简单实例,q=,病毒,AND,（计算机,OR,电脑）,AND NOT,医,d1:,据报道，计算机病毒近日猖獗,d2:,小王虽然是学医的，但对研究电脑病毒也很感兴趣，最近发明了一种,d3:,计算机程序发现了爱滋病病毒的传播途径,哪些文档会被检索出来？,布尔检索模型简单实例,21,布尔模型,文档表示,一个文档被表示为关键词的集合,查询式表示,查询式(,Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序,匹配,一个文档当且仅当它能够满足布尔查询式时，才将其检索出来,检索策略基于二值判定标准,不同的系统可以使用,:,不同的去除停用词(,stopword removal),策略和,stemming,策略,索引中不同类型的辅助信息,不同的实现方法,布尔模型文档表示,22,优点,到目前为止，布尔模型是最常用的检索模型，因为：,由于查询简单，因此容易理解，,简洁的形式化。,通过使用复杂的布尔表达式，可以很方便地控制查询结果,相当有效的实现方法,相当于识别包含了一个某个特定term的文档,经过某种训练的用户可以容易地写出布尔查询式,布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”,优点到目前为止，布尔模型是最常用的检索模型，因为：,23,问题,布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回,非常刚性:“与”意味着全部;“或”意味着任何一个,如果“我想要n个词中m个词同时出现的文档”，怎么表示？,不可能企望用户自己规定,m值,系统可以从m=n开始，然后逐渐减少m，但很麻烦,很难表示用户复杂的需求，,准确匹配，信息需求的能力表达不足,很难控制被检索的文档数量,原则上讲，所有被匹配的文档都将被返回,很难对输出进行排序,不考虑索引词的权重，所有文档都以相同的方式和查询相匹配,很难进行自动的相关反馈,如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？,问题布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分,24,向量空间模型,向量空间模型,25,向量空间模型,向量空间模型(Vector Space Model,VSM),相比于布尔模型要求的准确匹配,由美国信息处理专家萨尔顿（G.,Salton,）在20世纪,60,年代末提出的。,VSM,模型采用了“部分匹配”的检索策略（即：出现部分索引词也可以出现在检索结果中）。,通过给查询或文档中的索引词分配非二值权值来实现。,通过计算D和Q的similarity,作为它们之间的relevance（相似性作为相关性判断）,向量空间模型 向量空间模型(Vector Space Mod,26,向量空间的原理,(1)文档向量的构造,(2)提问向量的构造,(3)匹配函数的选择及相似度的确定,向量空间的原理,27,向量空间模型,词典,=k1,k2,kt,d=,此时，变量,wi,称为权值，非负；表示对应词项,ki,对于判断,d,和查询,q,相关性的重要程度（注意，这里的,q,是一般的，而,d,是具体的）,q=,变量,vi,的含义类似于,wi,两个基本问题：如何定义,wi,和,vi,；如何计算,R(d,q),？,向量空间模型 词典,=k1,k2,kt,28,向量空间模型,让,wi,和,vi,为对应的词分别在,d,和,q,中出现的次数，于是我们有了两个,m,维向量，用夹角的,cos,表示,“,接近度,”,，即,R(d,q)=cos(d,q)=dq/|d|,|q|,认为,：,cos(di,q)cos(dj,q),，则,di,比,dj,与,q,更相关,。,通常系统就会取前若干个结果返回给用户,例如天网返回,3000,，虽然可能查出了几十万,向量空间模型 让wi和vi为对应的词分别在d和q中出现的次,29,向量空间模型,在索引词权值的计算方案有很多种。在进行加权计算时，索引词权值的大小主要依赖于对索引词的各种频率数据的统计，并通常考虑两个方面的因素局部权值和全局权值,局部权值是指第i个索引词在第j篇文档中的权值。,t,f,ij,表示,全局权值指第,i个索引词在整个系统文档集合中的权值。idf,i,表示,向量空间模型在索引词权值的计算方案有很多种。在进行加权计算时,30,向量空间模型,假设，N为系统的文档总数,n,i,为系统中含有索引词,k,i,的文档数,f,req,ij,为索引词k,i,在文档d,j,中出现次数,idf,i,表示索引词k,i,的逆文档频率,max,t,f