《《信息检索模型》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《信息检索模型》PPT课件.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息检索n信信息息检检索索（informationretrieval，IR），将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程。n发展的几个阶段n手工检索(早期,情报检索)n穿孔卡片检索(1950s)n计算机检索(面向主题,1960s)n联机检索（1970s,1980s)nWeb检索(1990s)Ad hoc retrieval(特别检索:文档集合保持不变)Collection“Fixed Size”Q2Q3Q1Q4Q5IR的两种形式:AdHocandFilteringFiltering(过滤:用户需求不变)Documents StreamUser 1ProfileUser
2、 2ProfileDocs Filteredfor User 2Docs forUser 1IR的两种形式:AdHocandFiltering相关概念n停停用用词词（stopword），指文档中出现的连词，介词，冠词等并无太大意义的词。例如在英文中常用的停用词有the，a,it等；在中文中常见的有“是”，“的”，“地”等。n索索引引词词（标引词，关键祠）:可以用于指代文档内容的预选词语,一般为名词或名词词组.n词干提取词干提取（英文中）countries=country，interesting=interestn组合词组合词:北京大学n中中文文分分词词（wordsegmentation），或称
3、切切词词，主要在中文信息处理中使用，即把一句话分成一个词的序列。如，“网络与分布式系统实验室”，分词为“网络/与/分布式/系统/实验室/”。信息检索模型信息检索模型的概述信息检索模型n信信息息检检索索模模型型（IRmodel），依照用户查询，对文档集合进行相关排序的一组前提假设和算法。IR模型可形式地表示为一个四元组其中D是一个文档集合，Q是一个查询集合，F是一个对文档和查询建模的框架，R(qi,dj)是一个排序函数，它给查询qi和文档dj之间的相关度赋予一个排序值文档逻辑视图nD是一个文档集合，通常由文档逻辑视图来表示。文档逻辑视图可以是一组索引词或关键词。也可以用n-gram方式表示。既可
4、以自动提取，也可以是由人主观指定。（从全文到一组标引词）信息检索模型nQ是一个查询集合，用户任务的表达，由查询需求的逻辑视图来表示。nF是一个框架,用以构建文档,查询以及它们之间关系的模型nR(qi,dj)是一个排序函数，它给查询qi和文档dj之间的相关度赋予一个排序值n即:IR模型由上述四个要素组成信息检索模型的分类三类:基于内容的信息检索模型,结构化模型,浏览型检索模型.基于内容的信息检索模型有n集合论模型：布尔模型、模糊集合模型、扩展布尔模型n代数模型：向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型n概率模型：经典概率论模型、推理网络模型、置信（信念）网络模型非重叠链表模
5、型邻近结点模型结构化模型检索:特别检索过滤浏览用户任务经典模型布尔模型向量模型概率模型集合论模型模糊集合论模型可扩展布尔模型概率模型推理网络模型信任度网络模型代数模型广义向量模型潜语义标引模型神经网络模型浏览扁平式模型结构导向模型超文本模型信息检索模型的分类经典信息检索模型n布尔模型n向量空间模型n经典概率模型经典信息检索模型n经典的信息检索模型有三个：布尔模型、向量模型和概率模型。n每篇文档可以用一组有代表性的关键词即索引词集合来描述。索引词是文档中的词，其语义可以帮助理解文档的主题；因此，索引词常用于编制索引和概括文档的内容。n索引词通常由名词构成，因为名词本身具有语义，人们能够比较容易地
6、理解它的意思。形容词、副词、连词很少作为索引词，因为它们主要起补充作用，不能单独表示语义。布尔模型(Boolean Model)布尔检索模型n一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。n遵循两条基本规则:每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为0或1。n查询是由三种布尔逻辑运算符and,or,not连接索引词组成的布尔表达式。n根据布尔逻辑的运算规定，提问式可以被表示成由合取子项（conjunctive component）组成的析取范式（disjunctive normal form，简称DNF）形式。离散数学相关概念n用连词把几个公式连接起来而构成的公
7、式叫做合取，而此合取式的每个组成部分叫做合取项。p并且q，记作“pq”n用连词把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。p或q，记作“pq”n非p p离散数学相关概念n析取范式：仅由有限个简单合取式构成的析取式A=(pqr)(pq)(qq)n合取范式：仅由有限个简单析取式构成的合取式A=(pqr)(pq)(qq)n范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式离散数学相关概念n主析取范式主析取范式极小项极小项在n个变元的简单合取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种合取式叫做极小项n任何命题公式的主析取范式都是存在
8、的，并且是唯一的。定义形如AA1A2An基中Ai(I=1,2,3n)为极小项极小项记为：（m1m2m2n-1)布尔检索模型n首先，将查询转化为一个析取范式DNFn例如：查询为 n进一步表达为n即：每一个分量都是三元组 的二值向量(1,1,1)(1,0,0)(1,1,0)KaKbKc布尔检索模型n定义：用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分量。文献dj 与查询q的相似度为如果，则表示文献dj与q相关，否则为不相关。sim(dj,q)为该模型的匹配函数。布尔检索模型简单实例nq=病毒 AND（计算机 OR 电脑）AND NOT医 nd1:据报道，计算机病毒近日猖獗nd2:小
9、王虽然是学医的，但对研究电脑病毒也很感兴趣，最近发明了一种nd3:计算机程序发现了爱滋病病毒的传播途径 n哪些文档会被检索出来？布尔模型n文档表示n一个文档被表示为关键词的集合n查询式表示n查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序n匹配n一个文档当且仅当它能够满足布尔查询式时，才将其检索出来n检索策略基于二值判定标准n不同的系统可以使用:n不同的去除停用词(stopword removal)策略和stemming策略n索引中不同类型的辅助信息n不同的实现方法优点n到目前为止，布尔模型是最常用的检索模型，因为：n由于查询简单，因此容易理解，
10、简洁的形式化。n通过使用复杂的布尔表达式，可以很方便地控制查询结果n相当有效的实现方法n相当于识别包含了一个某个特定term的文档n经过某种训练的用户可以容易地写出布尔查询式n布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”问题n布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回n非常刚性:“与”意味着全部;“或”意味着任何一个n如果“我想要n个词中m个词同时出现的文档”，怎么表示？n不可能企望用户自己规定m值n系统可以从m=n开始，然后逐渐减少m，但很麻烦n很难表示用户复杂的需求，准确匹配，信息需求的能力表达不足n很难控制被检
11、索的文档数量n原则上讲，所有被匹配的文档都将被返回n很难对输出进行排序n不考虑索引词的权重，所有文档都以相同的方式和查询相匹配n很难进行自动的相关反馈n如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？向量空间模型向量空间模型 n向量空间模型(Vector Space Model,VSM)n相比于布尔模型要求的准确匹配,由美国信息处理专家萨尔顿（G.Salton）在20世纪60年代末提出的。VSM模型采用了“部分匹配”的检索策略（即：出现部分索引词也可以出现在检索结果中）。n通过给查询或文档中的索引词分配非二值权值来实现。n通过计算D和Q的similarity作为它们之间的rel
12、evance（相似性作为相关性判断）n向量空间的原理(1)文档向量的构造(2)提问向量的构造(3)匹配函数的选择及相似度的确定向量空间模型 n词典,=k1,k2,ktnd=n此时，变量wi称为权值，非负；表示对应词项ki对于判断d和查询q相关性的重要程度（注意，这里的q是一般的，而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)
13、，则则di比比dj与与q更相关更相关。n通常系统就会取前若干个结果返回给用户n例如天网返回3000，虽然可能查出了几十万向量空间模型n在索引词权值的计算方案有很多种。在进行加权计算时，索引词权值的大小主要依赖于对索引词的各种频率数据的统计，并通常考虑两个方面的因素局部权值和全局权值n局部权值是指第i个索引词在第j篇文档中的权值。tfij表示n全局权值指第i个索引词在整个系统文档集合中的权值。idfi表示向量空间模型n假设，N为系统的文档总数nni为系统中含有索引词ki的文档数nfreqij为索引词ki在文档dj中出现次数nidfi表示索引词ki的逆文档频率nmaxtfj表示文档dj中所有索引词
14、出现次数的最大值向量空间模型 n权值wij的选取方法：n对文档向量dj的构造，考察：n局部权值tfij=freqij/maxtfjn全局权值idfi=log(N/ni)n索引词权值wij=tfij*idfin称为tfidf（词频逆文档频率），最流行的权值计算公示n任意文档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为在表述
15、用户信息需求的文本内容中使用的所有索引词出现次数的最大值向量空间模型 n重要的学术贡献，用了几十年nG.Salton and M.E.Lesk,“Computer evaluation of indexing and text processing,”Journal 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在许多方面依然和“现实”都不
16、符，但实际效果不错（至少比布尔模型好很多）向量空间模型 n综合题：综合题：按照下述描述和要求完成相关工作按照下述描述和要求完成相关工作 n给定文档语料给定文档语料:nd1:北京安立文高新技术公司nd2:新一代的网络访问技术nd3:北京卫星网络有限公司nd4:是最先进的总线技术。nd5:北京升平卫星技术有限公司的新技术有。向量空间模型 n利利用用中中文文切切分分词词软软件件，分分别别得得到到用用“/”分分开开的一些字词：的一些字词：nd1:北京/安/立/文/高新/技术/公司/nd2:新/一/代/的/网络/访问/技术/nd3:北京/卫星/网络/有限/公司/nd4:是/最/先进/的/总线/技术/。n
17、d5:北京/升/平/卫星/技术/有限/公司/的/新/技术/有。向量空间模型 n你你的的任任务务是是设设计计一一个个针针对对这这些些文文档档的的信信息息检检索系统。具体要求是：索系统。具体要求是：n(1).给出系统的有效词汇集合（说明取舍原因）。(2).写出d1和d2在VSM中的表示（使用tf*idf，写出各项的数字表达式，具体数值不必实际计算出来）。(3).画出系统的倒排文件示意图。(4).按照向量夹角的余弦计算公式，给出针对查询“技术的公司”的前3个反馈结果。向量空间模型 n特点：基于多值相关性判断、基于统计学方法的词加权处理模式、采用检索结果的排序输出策略。搜索引擎采用的检索模型n搜索引擎
18、采用了布尔模型和向量空间模型结合的方法来进行信息检索，布尔模型的检索效率高且易于实现；向量空间模型能够提高检索的相似度，通过相似度排序的手段能够大大改善查询效果，因此搜索引擎将二者的优势相结合，完整的检索过程如图所示。分词学习信息检索学习 信息检索倒排表检索包含“学习”文档列表包含“信息检索”文档列表文档列表求交集既包含“学习”也包含“信息检索”文档列表学习 信息检索向量化求向量相似度按相似度排序输出图中方块为计算部分，斜方块为数据部分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这样，学校和学生的相关度是n练 习 简 述 信 息 检 索 三 种 基 本 模 型(booleanmodel,vectormodel,probabilisticmodel)。