2020/5/13信息存储与检索1第七章信息检索模型2020/5/13信息存储与检索2第七章信息检索模型•7.1信息检索模型概述•7.2经典的信息检索模型•7.3集合论检索模型•7.4代数检索模型•7.5概率检索模型•7.6结构化文本检索模型•7.7超文本检索模型2020/5/13信息存储与检索37.1信息检索模型概述7.1.1信息检索概述•信息检索是一门研究从一定规模的文档库中找出满足用户需求的信息的学问,它指的是对非结构化或半结构化信息的检索,半结构化信息检索人们通常称为文本信息检索,而非结构化信息检索多指多媒体信息检索。•信息检索是对信息集合与需求集合的匹配和选择。•信息检索基本原理:用户通过一些列关键词来阐明自己的信息需求,信息检索系统则检索与用户查询最为匹配的文献,同时借助某种相关性指标对检索出的文献进行排序。2020/5/13信息存储与检索47.1.2信息检索模型1、定义•信息检索模型的核心问题是检测哪些文献相关,哪些文献不相关,即判断一篇文献是否与用户的查询条件相关,以及相关的程度。•信息检索的模型,就是运用数学的语言和工具,对信息检索系统中的信息及其处理过程加以翻译和抽象,表述为某种数学公式,再经过演绎、推断、解释和实际检验,反过来指导信息检索实践。2020/5/13信息存储与检索52、信息检索模型的组成(1)用户的需求表示:包括用户查询信息的获取与表示。(2)文档的表示:文档内容的识别与表示。(3)匹配机制:用户需求表示与文档表示之间的查询机制,以及它们之间相关性排序的准则和函数表示。(4)反馈修正:对检索结果进行优化。7.1.2信息检索模型2020/5/13信息存储与检索6结构化文本模型集合论模型文本检索模型非重叠链表模型邻近节点模型布尔模型向量模型概率模型浏览模型超文本模型基于本体的模型经典模型超文本模型知识检索模型扩展布尔模型模糊集合模型广义向量模型潜语义标引模型神经网络模型推理网络模型信任度网络模型代数模型概率模型3、信息检索模型的类型7.1.2信息检索模型2020/5/13信息存储与检索77.2经典的信息检索模型7.2.1定义及假设•定义:令t表示文档集里所用不同标引词的数目,Ki表示一个标引词,K={K1,K2K3,…Kt}表示所有标引词的集合,对于文档Dj中存在的标引词Ki,其权重Wij0;对于文档Dj中没有的标引词Ki,其权重Wij=0。这样就可以将文档Dj表示成一个向量Dj=(W1j,W2j,W3j…Wtj),向量Dj的第i维就对应项Ki在文档Dj中的权重。2020/5/13信息存储与检索87.2.1定义及假设•在经典的信息检索模型中,还存在以下一些普遍性假设:(1)被检索对象主要为文档对象。(2)标引词是相互独立的。(3)用户检索是根据文档内容的表示及所需信息的表示进行的。(4)所有文档的内容和所需信息的表示都是非精确的。2020/5/13信息存储与检索97.2经典的信息检索模型7.2.2布尔检索模型–布尔(Boolean)模型是基于集合论和布尔代数的一种简单检索模型。用布尔表达式表示用户提问,通过对文献标识与提问式的逻辑运算来检索文献。–在传统的布尔模型中,每一文献用一组标引词表示。Dj=(K1,K2,K3,…,Km)表示文献Dj,式中K1,K2,K3,…,Km表示文献Dj中的所有标引词集合。2020/5/13信息存储与检索107.2.2布尔检索模型•文档与标引词建立一个布尔关系。用若干标引词的布尔表达式来表达和解释查询Q。–对于一个表示为Q=(K1ANDK2)OR(K3AND(NOTK4))的提问式,系统的响应必须是这样一组文献集合:这些文献中都含有标引词K1和K2,或者含有标引词K3但不含有标引词K4。•常用的布尔逻辑组配运算符有:逻辑“与”(AND,常用符号“∧”表示)、逻辑“或”(OR,常用符号“∨”表示)、逻辑“非”(NOT,常用符号“-”表示)。2020/5/13信息存储与检索11布尔检索模型•在布尔检索模型中标引词在文献中要么出现、要么不出现,因此标引词Ki在文档Dj中的权重全部被设为二值数据,即Wij∈(0,1)。•用户提交的查询条件由若干个标引词用与、或、非等逻辑符号相联结,在布尔检索模型中被表示成了布尔表达式Q=(K1,K2,…),其本质可以表示为多个标引词权值的合取向量的析取Qi(Qi为表达式Q的任意合取向量),则文献Dj和查询Q的相关度表示为不相关和查询,表示文献,此时相关和查询,表示文献,此时QDQQQDQQQDSimjijij01),(2020/5/13信息存储与检索12布尔检索模型•如要检索“布尔检索或概率检索但不包括向量检索”方面的文档,其相应的查询表达式为:Q=检索and(布尔or概率not向量),那么Q可以在其相应的(检索,布尔,概率,向量)标引词向量上取(1,1,0,0)(1,0,1,0)(1,1,1,0),那么文档Dj的向量如果与这中间一个相等,那么即可认为他们之间存在相似关系,而这种相互关系也是布尔值,即sim(Q,Dj)只能为0或1。•这也就是布尔模型的局限性所在,描述所有关系都是布尔值,而现实中文档与标引字或者标引字与查询语句之间的关系都不可能只是有关系或者没关系,换句话说布尔模型中无法描述关系的密切程度。2020/5/13信息存储与检索13简单实例:Q=病毒AND(计算机OR电脑)ANDNOT医•D1:…据报道,计算机病毒近日猖獗…•D2:…小王虽然是学医的,但对研究电脑病毒也很感兴趣,最近发明了一种…•D3:…计算机程序发现了爱滋病病毒的传播途径…•D4:…最近我的电脑中病毒了…请问:哪些文档会被检索出来?2020/5/13信息存储与检索14布尔检索模型•Boolean模型存在着一些缺陷:–第一,它的检索策略是基于二元判定标准(例如,对于检索来说一篇文档只有相关和不相关两种状态),缺乏文档分级(rank)的概念,限制了检索功能。–第二,虽然布尔表达式具有精确的语义,但常常很难将用户的信息需求转换为布尔表达式,实际上大多数检索用户发现在把他们所需的查询信息转换为布尔时并不是那么容易。2020/5/13信息存储与检索157.2经典的信息检索模型7.2.3向量空间模型–向量模型通过分派非二值权重给查询和文档中的标引词来实现检索目标。这些权重用于计算系统中的每个文档与用户的查询请求的相似程度,向量模型通过对文档按照相似程度降序排列的方式,来实现文档与查询项的部分匹配。这样做的结果中的文档排列顺序比通过布尔模型得到的结果要合理得多。2020/5/13信息存储与检索167.2.3向量空间模型•定义:在向量空间模型中,标引词Ki在文档Dj中的权重Wij是一个大于0的非二值数。文档Dj可以看做是一个向量:Dj=(W1j,W2j,W3j………Wtj)其中,t是文档集中所有标引词的数目。用户查询中的标引词也是有权重的,设Wiq是用户检索提问式(查询)Q的标引词Ki的权重,且Wiq≥0,则查询向量Q被定义成:Q=(W1q,W2q,W3q…………Wtq)。衡量文档和查询的相关度转化成计算文档向量和查询向量之间的相似度。一般使用文档向量和查询向量之间的夹角余弦值来计算它们之间的相似度。2020/5/13信息存储与检索177.2.3向量空间模型WijK1k2…KnD101…0D210.8…0.5……………Dn0.20…1文档向量空间的表示:文档D1(W11,W21,…Wn1)查询Q(W1q,W2q,…Wnq)文档D2(W12,W22,…Wn2)特征项1特征项2特征项3文档向量空间模型:2020/5/13信息存储与检索18文档和文档之间的相似度Sim可以表示如下:nknkjkiknkjkikjiDWDWDWDWDDSim11221))()(((()()(cos),(titiiqijtiiqijj)))(((cos),(文档和查询之间的相似度Sim可以表示如下:7.2.3向量空间模型2020/5/13信息存储与检索19例子•D1=2K1+3K2+5K3•D2=3K1+7K2+K3•Q=0K1+0K2+2K3文档D1=2K1+3K2+5K3查询Q=0K1+0K2+2K3文档D2=3K1+7K2+K3特征项1特征项2特征项313.0591)2()173(210703),(81.0385)2()532(250302),(2222122221QDSimQDSim2020/5/13信息存储与检索20•标引词的权重计算(TF-IDF)–N为文档集合,ni为包含标引词Ki的文档篇数,TFij表示标引词Ki在文档Dj中出现的频数,则文档Dj中标引词Ki的标准化频率Fij为Fij=TFij/maxjTFij–最大值是通过计算文档Dj中出现的所有标引词来获得的。如果标引词Ki没有出现在文档Dj中,则Fij=0。–标引词Ki的IDF为IDFi=log(N/ni)–标引词Ki在文档Dj中的权重Wij=Fij*IDFi7.2.3向量空间模型2020/5/13信息存储与检索21TF-IDF举例说明文本:“俄罗斯频繁发生恐怖事件,俄罗斯的安全部门加大打击恐怖主义的力度。”TFIDFTF-IDFTFIDFTF-IDF俄罗斯2较高高安全1中等高恐怖的2较高高部门1较低低的2非常低很低加大1较低低频繁1较低低打击1中等高发生1较低低主义1较低低事件1较低低力度1中等高2020/5/13信息存储与检索227.2.3向量空间模型•向量空间模型的主要优点:–对标引词的权重进行了改进,其权重的计算可以通过统计的办法自动完成,使问题的繁杂性大为降低,从而改进了检索效率。–把文档和查询本身简化为标引词及其权重集合的向量表示,把对文档内容和查询要求的处理简化为向量空间中向量的运算。–根据文档和查询之间的相似度对文献进行排序,有效地提高了检索效率。–可以实现文档自动分类。2020/5/13信息存储与检索23•向量空间模型的主要缺点:(1)标引词仍然被认为是相互独立,会丢掉大量的文本结构信息,降低语义准确性。(2)相似度的计算量大,当有新文档加入时,必须重新计算词的权值。7.2.3向量空间模型2020/5/13信息存储与检索247.2经典的信息检索模型7.2.4概率模型1、基本思想–用户提出了查询,就有一个由相关文档构成的集合,该集合只包括与查询完全相关的文档而不包括其他不相关的文档,称该集合为理想结果集合,记为R。如果知道R的特征,就可以找到所有的相关文档,排除所有的无关文档。因此,可以把查询看成一个寻找R的特征的过程。2020/5/13信息存储与检索257.2.4概率模型在第一次查询时并不知道R的特征,只能去估计R的特征来进行查询。第一次查询完成后,可以让用户判断一下检索到的文档哪些是相关文档,根据用户的判断,可以更精确地估计R的特征。然后系统利用该信息重新定义理想结果集合的概率描述;重复以上操作,就会越来越接近真正的结果文档集。估计R的特征进行检索用户判断2020/5/13信息存储与检索267.2.4概率模型2、相关概念•贝叶斯定理:•词条的独立假设:P(AB)=P(A)P(B)当且仅当A与B相互独立.•若文档中的各个索引词相互独立,则有P(Dj)=P(k1)…P(kt))()()|()|(BPAPABPBAP2020/5/13信息存储与检索277.2.4概率模型3、定义:–对于概率检索模型而言,标引词Ki在文档Dj中的权重Wij∈{0,1},同时用户查询中的标引词Wiq∈{0,1},查询Q是标引词空间的一个子集,用R表示已知的相关文献集,用表示R的补集,条件概率P(R∣Dj)表示文档Dj与查询Q相关的概率,条件概率P(∣Dj)表示文档Dj与查询Q不相关的概率。文献Dj与查询Q的相似度Sim(Dj,Q)可以定义为两者的比值,即:RR)()|()()|()|()|(),(RPRDPRPRDPDRPDRPQDSimjjjjj2020/5/13信息存储与检索287.2.4