现代信息查询与利用信息检索及发展

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第7章 信息检索及开展,?现代信息查询与利用?课程组,7.1,信息检索概述,信息检索研究历史和现状,7.3,信息检索模型,3,7.1.1 信息检索词汇terms,检索的含义“检索就是查找，这仅仅是一种狭义的解释。从广义的角度讲，检索包括“存贮和“查找两个过程。,没有存贮就没有查找，存贮是为了查找，但查找必须有存贮，两者缺一不可。,4,信息检索词汇terms,“检索Retrieval一词是一个外来词，来源于英语“InformationRetrieval信息检索,Information retrieval (IR),Information access (obtain),Information search (look for),Information searching (look for),Information seeking (focus on users, active),locate,hit,7.1.2,信息检索的原理,信息检索是,指从任何信息集合中查出所需信息的活动、过程与方法。,广义的信息检索还包括信息存贮，两者又往往合并称为,“,信息存贮与检索,(Informationstorageandretrieval),。,信息检索的原理,信息存贮与检索,信息检索的起源,信息检索起源于图书馆的参考咨询和文摘索引工作，从19世纪下半叶首先开始开展，至20世纪40年代，索引和检索成已为图书馆独立的工具和用户效劳工程。,随着1946年世界上第一台电子计算机问世，计算机技术逐步走进信息检索领域，并与信息检索理论紧密结合起来；脱机批量情报检索系统、联机实时情报检索系统,8,信息检索开展阶段,手工操作,(manual),计算机化,(computerized),网络化,(networked),智能化,(intelligentized),认知化,(cognized),9,主要检索系统类型,联机检索(online search),脱机检索offline search,光盘检索CD search,网络检索Interne/Web search,全球数字图书馆系统digital global system,10,1,、,联机检索,(online search),通信网络,联机检索中心,检索终端,数据库,主机,WAN,微机,11,检索终端,局域网,效劳器,光驱,LA,N,微机,光盘联机检索,(CD,online),12,网络Internet信息检索,Internet,网络检索,分布、开放、异种机；,客户机,/,服务器模式，,浏览器,/,服务器模式,信息量大，无质量控制；,自动发掘、采集；,免费服务居多,个人用户检索模式；,WIMP,（浏览,+,检索）；,自然语言,检索为主,13,信息检索研究历史和现状,研究历史和现状,1948年C. N. Mooers在其MIT硕士论文中第一次使用了“Information Retrieval这个术语,196070年代在建立文摘检索系统中，产生了布尔模型(Boolean Model)、向量空间模型(Vector Space Model)和概率检索模型(Probabilistic Model),14,信息检索研究历史和现状,研究历史和现状,1980,年代出现商用数据库检索系统：,Dialog,，,ORBIT, MEDLINE,1990s,第一个网络搜索工具：,1990,年加拿大蒙特利尔大学开发的,FTP,搜索工具,Archie,15,信息检索研究历史和现状,研究历史和现状,第一个,WEB,搜索引擎：,1994,年美国,CMU,开发的,Lycos,1995,斯坦福大学博士生开发,Yahoo,1998,斯坦福大学博士生开发的,Google,，提出,PageRank,计算公式,1998,年基于语言模型的,IR,模型提出,16,信息检索研究历史和现状,研究历史和现状,1990,年代推荐系统的出现：,Ringo,，,Amazon,，,NetPerceptions,文本分类和聚类的使用、信息抽取：,Whizbang,17,信息检索研究历史和现状,研究历史和现状,2000s的重要事件,文本检索会议TREC(Text Retrieval Conference )的开展,问答系统评测专项Q/A track(Question Answering Track),2001年，百度成立,18,信息检索研究历史和现状,研究历史和现状,2000s,以来的其他重要事件,多媒体,IR,，,Image,，,Video,，,Audio and music,跨语言,IR,，,DARPA Tides,，文本摘要，,DUC,评测,19,7.3,检索模型,三类,7.3.1,基于内容的信息检索模型,7.3.2,结构化模型,7.3.3,浏览型数学模型,20,检索模型分类,信息检索模型,检索模型,浏览模型,内容模型,结构模型,布尔,模型,向量,模型,概率,模型,非重叠,链表模型,邻近节,点模型,平坦,模型,结构导,向模型,超文本,模型,21,7.3.1,内容模型,基于内容的信息检索模型有,集合论模型,布尔模型、,模糊集合模型、扩展布尔模型,代数模型,向量空间模型,、广义向量空间模型、潜在语义标引模型、神经网络模型,22,7.3.1,内容模型,基于内容的信息检索模型有,概率模型,经典概率论模型、推理网络模型、置信信念网络模型,23,检索模型的根本概念相关概念,标引项,(Index Term),文档表示成多个,Term,的集合,通常用词来表示，但是也可以用其他语言单位来表示,关键词,(key words),可以看成,Term,的一种,标引项的,权重,(Weight),不同标引项作用是不同的,通过权重加以区分,24,检索模型的根本概念模型要素,F,是一个,框架,用以构建文档,查询以及它们之间关系的模型,D,是一个,文档,集合，通常由文档逻辑视图来表示。可以是一组索引词或关键词。既可以自动提取，也可以是由人主观指定。,25,检索模型的根本概念模型要素,Q,是一个,查询,集合，是用户任务的表达，由查询需求的逻辑视图来表示。,R(qi,dj),是一个,排序,函数，它给查询,qi,和文档,dj,之间的相关度赋予一个排序值,即,: IR,模型由上述三个要素组成,R(qi,dj) = F( D, Q ),26,1,、,布尔模型,一种简单的检索模型，它建立在经典的集合论和布尔代数的根底上,27,1,、,布尔模型,根本原理,系统索引词集合中的每一个索引词在一篇文档中只有两个状态,出现,不出现,检索提问式q由三种布尔运算符 “and、“or、“not连接索引词来构成,28,布尔模型,集合的几种表示,具有某种属性的事物的全体就构成一个集合，以,A, B, C,表示构成集合的事物，以,a,b,c,表示该集合的元,某个图书馆现存的所有图书,有限集 以,S1,a,b,c,d,表示,29,布尔模型,集合的几种表示,所有的正整数,无限集 以,S2,1,2,3,4,表示,P(x),表示与元,x,有关的一个属性,S3,x|x,是正偶数,S4,x|1x10 ,为空集,30,布尔模型,集合的表示,集合间的关系,x,是,A,中的一个元，记作,x A,x,不是,A,中的一个元，记作,x A,集合的图形表示,空间,E,集合,A,元,x,31,布尔模型,集合的运算,并运算,设A，B是两个集合，集合A与B的并运算是由A的一切元素和B的一切元素所组成的集合，记做 AB，数学表示为：,设 A=a,b,c,d,e，B=c,d,x,y,z,那么 AB=a,b,c,d,e,x,y,z,即 AB=x|xAxB ,A,B,空间,E,32,布尔模型,集合的运算,交运算,设A，B是两个集合，包含A和B的所有公共元素的集合叫做A与B的交集，记做 AB，数学表示为：,设 A=a,b,c,d,e，B=c,d,x,y,z,那么 AB=c,d,即 AB=x|xAxB ,33,布尔模型,遵循两条根本规那么,每个索引词在一篇文档中只有两种状态：出现或不出现，对应逻辑值为 0 或 1,查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式,34,布尔模型,集合的运算,差运算,设A，B是两个集合，A-B是由一切属于A但不属于B的元素所组成的集合，称为B在A中的余集，或者A与B的差，即,设 A=a,b,c,d,e， B=c,d,x,y,z,那么 A-B=a,b,e， B-A=x,y,z,数学表示为,A-B=x|xAxB ,35,布尔模型,定义,用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分项，文献dj 与查询q的相似度为,如果 ，那么表示文献dj与q相关，否那么为不相关。,sim(dj, q) 为该模型的匹配函数(相似度),36,布尔模型,优缺点,优点,简单而整齐,自我保护功能，降低用户对搜索系统的期望，使自己不在责任方，检索结果不好的原因在于用户构造查询不好,简单、易理解、简洁的形式化,缺点,它的检索策略是基于二值决策准则，即一个文档只被判断成相关的或不相关的，无任何等级变化,当用布尔表达式表示精确语义的时候，很难将信息表达为一个布尔表达式,准确匹配，信息需求的能力表达不足,布尔模型,目前仍然是商业文档数据库的主流模型，并为一些新的领域提供了一个好的起点,38,2,、向量模型,n,维向量,考虑从空间坐标系原点出发其他向量可以平移到原点出发的向量 ，其终点坐标为，我们称之为一个n维向量,39,2,、向量模型,n,维向量,向量的运算,加、减、倍数、内积,40,向量模型,空间概念,文献空间,如果把每个标引词看作是一个向量，代表了空间的一个维，那么由这些标引词集合定义了一个空间,文献集合中的任一文献都可以表示为这个多维空间中的一个向量，这个空间就成为“文献空间,41,向量模型,空间概念,标引词空间,文献集合中的一篇文献可看成是标引词空间的一个维，空间中的一点代表一个标引词点,从原点到该点的向量就是一个标引词向量,它在各个轴上的分量就是该标引词在各个轴所代表的相应文献中的权重,42,向量模型,模型含义,向量空间模型(Vector Space Model, VSM),由康奈尔大学Salton等人在上世纪70年代末提出并倡导的，原型系统为SMART*,该模型采用了“局部匹配的检索策略，即：出现局部索引词也可以出现在检索结果中，以克服布尔模型的缺点,* 可从下载全部源码和相关语料,43,向量模型,模型含义,向量空间模型,(Vector Space Model, VSM),通过给查询或文档中的索引词分配非二值权值来实现,查询和文档都可转化成,Term,及其权重组成的向量表示，并可以看成空间中的点。向量之间通过距离计算得到查询和每个文档的相似度,*,可从下载全部源码和相关语料,44,向量模型,模型含义,向量模型通过分派非二值权重给查询和文档中的索引项来实现检索目标,这些权重用于计算系统中的每个文档与用户的查询请求的相似程度，向量模型通过对文档按照相似程度降序排列的方式，来实现文档与查询项的局部匹配,结果中的文档排列顺序比通过布尔模型得到的结果要合理得多,45,向量模型,模型含义,在该模型中，与ki，dj相关联的权重wi,j是一个非二值数,查询中的索引项也是有权重的，设wi,q是与ki，q相关联的权重，且wi,q0，那么查询向量Q被定义成 Q=w1,q，w2,q，w3,qwt,q其中，t是系统中所有索引项的数目,46,向量模型,模型含义,文档dj的向量可以表示为 wj=w1,j，w2,j，w3,jwt,j，,向量模型通过wj和Q的相关度来评价文档dj和查询q的相关度。这种关系可以用定量表示，一般使用两个向量之间的夹角余弦值来计算,47,向量模型,模型含义,变量wi称为权值，非负,表示对应词项ki对于判断d和查询q相关性的重要程度注意，这里的q是一般的，而d是具体的 q=,变量vi的含义类似于wi,两个根本问题：,如何定义wi和vi,如何计算R(d, q),48,向量模型,模型含义,设wi和vi为对应的词分别在d和q中出现的次数，于是我们有了两个m维向量，用夹角的cos表示“接近度，即,49,3,、,概率模型,概率模型根本思想是：,给定一个用户的查询，那么有一个包含相关文档且不包含不相关文档的集合。设想这个文档集合是一个理想的结果集。,50,7.3.3,概率模型,根本假设,给定一个查询q和文档集中一个文档dj，概率模型试图找出用户对其感兴趣的概率,模型假设这个概率只是依赖于查询和文档的表示，进而模型假设文档集中存在一个子集，它使得总体相关概率在集合中的文档被认为是与查询相关的，不在集合中的那么被认为是不相关的,51,概率模型,贝叶斯定理,贝叶斯定理,词条的独立假设,P(AB)= P(A) P(B) 当且仅当 A与B相互独立,对一篇文档而言，假设文档中的各个索引词相互独立，那么有,P(dj)=P(k1)P(kt),52,概率模型,模型定义,定义,设索引词的权重为二值的，即：,R表示的相关文档集或最初的猜测集，用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj, q)可以定义为：,53,概率模型,优缺点,优点,理论上讲，文档按照其与目标集合的相关概率 降序排列,缺点,需要最初将文档分为相关和不相关的集合,所有权重都是二值的，模型中仍然假设索引项之间是相互独立的,54,比较,布尔、向量和概率模型是三个传统的检索模型,布尔模型是基于集合理论和布尔代数的一种简单检索模型,向量模型采用非二值的索引项权重，把文档和查询用t维权重向量表示，计算这两个向量之间的相似度来实现查询与文档的匹配,概率模型是一种标准的模型，它试图预测给定查询的相关文档，排序原那么根据文档与集合的相似度进行排序,55,7.3.2,结构化文本检索模型,结构化文档检索算法可以看作是一种信息检索算法，但排序机制并不健全,使用“匹配点来表示文本与用户查询相匹配的词串位置,使用“区域表示文本的块,使用“节点表示文档的结构化组元,这样，一个节点是一个区域，具有文档的作者与用户所共知的、预定义的逻辑属性,56,结构化文本检索模型,基于非重叠链表的模型是把文档中的整个文本划分为非重叠文本区域，并用链表连接起来,因为有多种方法将文本分为非重叠的区域，所以，对于同一个文档，会产生多个链表,这些链表清晰的记录了文档的数据结构,在相同链表中的文本区域没有重叠，而不同链表中的文本区域可能会重叠,57,结构化文本检索模型,该模型是一种允许在相同文档上独立定义分层索引结构的模型，每个索引结构是一个严格的层次结构，其中每个结构组元称为节点，每个节点与一个文本区域相关，两个不同的层次结构可能涉及到两个重叠的文本区域,针对不同层次结构的用户查询，所聚集的结果是由来自其中一个层次结构的节点组成,58,7.3,浏览模型,三种浏览模型：平坦模型，结构导向模型和超文本模型,平坦模型把文档集看成是一个平坦的文档空间。由于是平坦的，这种模型的导航关系不清楚,结构导向模型提供了层次性目录式的导航模型，是一种非平坦模型,超文本模型是由节点和链组成的非线性的信息组织网络，能够为用户提供比上两种模型更多的信息，更方便的浏览，Web是它最成功的应用,