搜索
1文本检索技术杨建武Email:yangjianwu@icst.pku.edu.cn第三章：北京大学计算机科学技术研究所文本挖掘技术2信息检索概述3信息爆炸¾网页数量：1997:3.2亿1999:8亿(15TB)2002:20亿(Google)2004:43亿(Google)2006:100亿(Google)¾recentlystudyshows:1TB/yearforbooks,2TB/yearfornewspapers,1TB/yearforperiodcals,19TB/yearforofficedocs.4信息检索花费大量时间68%的人认为信息难找51%的人每天至少花2个小时检索信息5信息检索的定义¾informationretrieval¾广义的信息检索是指将信息按一定的方式组织和存储起来，并根据信息用户的需要找出有关的信息的过程和技术。全称：信息存储与检索（informationstorageandretrieval）。¾狭义的信息检索则仅指该过程的后半部分，即从信息集合中找出所需要的信息的过程，相当于人们所说的信息查询（informationsearch）。6信息检索的发展¾信息检索通常是指对无结构数据（如自然语言文本）的检索¾图片，音频、视频文件等多媒体数据也是无结构的，不在传统IR研究范围之内。但近年来逐渐纳入IR领域内，如TREC引入了SDR(SpeechDocumentRetrieval)Track和VideoTrack。¾信息检索的发展阶段手工检索(早期,情报检索)穿孔卡片检索(1950s)计算机检索(面向主题,1960s)联机检索（1970s,1980s)Web检索(1990s)7基于分类的检索¾以分类体系为基础，将各种资料的按信息的类别进行分类和系统排列，并编排组织成一个完整的体系。¾按照知识门类的逻辑次序，运用概念划分和归属的方法，由总到分，逐级展开，形成一个严格有序的等级制体系8分类的例子¾Ａ马、列、毛思想、邓小平理论¾Ｂ哲学、宗教¾社会科学——Ｃ社会科学总论¾Ｄ政治、法律¾Ｅ军事¾Ｆ经济¾Ｇ语言、文字¾Ｉ文学¾Ｊ艺术¾Ｋ历史、地理¾自然科学——Ｎ自然科学总论9分类检索的不足¾检索者检索时首先必须了解分类体系才能顺利查找到相应的类目，如果不熟悉分类体系，会带来一定的困难。¾体系分类采用列举类目的方法，受到类目数量的限制，缺乏专指性，查准率不高。¾由于分类表的结构是固定的，不便于随时修订和增设新的类目。¾体系分类语言采用分类号作为检索标识，检索文献时，需要将检索文献的主题内容转换成分类号，转换过程中，容易产生误差，造成误检。10基于主题词的检索11基于元数据的检索¾元数据是关于数据的数据是以计算机系统能够使用与处理的格式存在的与内容相关的数据，它是对内容的一种描述方式，表示内容的属性与结构信息。¾元数据分为：描述元数据语义元数据控制元数据结构元数据12科技文献元数据检索语言13现代信息检索¾基于内容检索基于内容的文本检索—全文检索基于内容的图像检索基于内容的视频检索……¾结构化检索¾浏览型检索14文本检索¾TR(TextRetrieval)又：全文检索¾文本检索的任务是根据用户的信息需求来定位满足用户需求的文档集。¾与信息检索IR(InformationRetrieval)的关系广义IR•可以检索非文本信息(如:图象)•多种任务(如:文本检索,过滤,分类,摘要)狭义IR=文本检索•给定文档集合•给出信息检索需求•检索相关文档15文本检索¾TR是IR中最重要的一项技术，大多数的信息需求是针对文本的。文本检索是信息检索的基础,包括很多具体应用，•如：搜索引擎，数字图书馆，……•检索,定位,筛选,问答…文本检索的技术可以用来检索其他的媒体信息。16文本检索应用实例TheWebLibrary,etc.SpiderInvertedIndexUserSearchEngine17信息需求索引预处理解析文档集排序查询文本输入如何构造查询?如何表示文本?文本检索过程如何组织索引?18文本检索基本步骤19文本检索的难点¾不同的用户有不同的检索需要¾有时用户也不知道需要什么,或不知道怎样表达自己的需要¾语言的歧义性¾一词多义,多词一义¾相关性的判定:80%20信息检索模型21信息检索模型¾信息检索模型（IRmodel），依照用户查询，对文档集合进行相关排序的一组前提假设和算法。¾IR模型可形式地表示为一个四元组D,Q,F,R(qi,dj)其中:D是一个文档集合，Q是一个查询集合，用户任务的表达F是一个框架,用以构建文档、查询以及它们之间关系的模型R(qi,dj)是一个排序函数，它给查询qi和文档dj之间的相关度赋予一个排序值22信息检索模型的分类¾许多检索模型被提出，理论基础覆盖几何、逻辑、概率和统计¾三大类:内容模型结构模型浏览模型23Non-OverlappingListsProximalNodesStructuredModelsRetrieval:AdhocFilteringBrowsingUserTaskClassicModelsbooleanvectorprobabilisticSetTheoreticFuzzyExtendedBooleanProbabilisticInferenceNetworkBeliefNetworkAlgebraicGeneralizedVectorLat.SemanticIndexNeuralNetworksBrowsingFlatStructureGuidedHypertext信息检索模型的分类24信息检索模型的分类信息检索模型检索模型浏览模型内容模型结构模型布尔模型矢量模型概率模型非重叠链表模型邻近节点模型平坦模型结构导航模型超文本模型25浏览模型¾浏览模型概念用户的兴趣可能不在于提交一个对系统的查询。而是有意花一点时间来浏览文档空间，以寻找所关心的文档。用户是进行文档空间的浏览而不是搜索；浏览和搜索是不同的信息发现行为，通常来说，搜索比浏览更适合于有明确查找目标的用户。26浏览模型¾浏览模型类别平坦浏览•文档集可以被描述为平面上的点或是链表中的元素•用户在这些文档上到处浏览，以寻找有关信息，•在反馈过程中，用户通过在邻近文档中的浏览，查找出相关的资料，找出一些感兴趣的关键词27浏览模型¾浏览模型类别结构导航•文档被组织成为如目录那样的结构•目录是类的层次结构•对文档按照主题来分类和组织•Æ分类检索28浏览模型¾浏览模型类别超文本(Hypertext)•超文本是一个允许以非顺序的方式在计算机上浏览文本的高层交互式导航结构•它由节点和链组成，节点之间的关系由链表示，节点和链构成一个有向图。•支持用户的非线性浏览和信息存取。•超文本的导航过程可以被理解为一个有向图的游历过程，图中被链接的节点表示节点之间有某种语义关联。•ÆWeb可看作一个巨大的超文本29结构模型¾结构模型概念用户希望能够对文档中的某些结构组元中包含的信息进行检索例如，对出现在章节标题的词进行检索把文档内容与文档结构结合起来30结构模型¾结构模型类别非重叠链表模型•文档中的整个文本划分为非重叠文本区域，并用链表连接起来•相同链表中的文本区域没有重叠，而不同链表中的文本区域可能会重叠ChapterSectionParagraph31结构模型¾结构模型类别邻近节点模型•文档上定义一个或多个分层索引结构•每个索引结构是一个严格的层次结构ChapterSectionParagraph32内容模型¾内容模型集合论模型：布尔模型、模糊集合模型、扩展布尔模型代数模型：向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型概率模型：经典概率论模型、推理网络模型、置信（信念）网络模型、统计语言模型33布尔检索模型¾一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。¾遵循两条基本规则:每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为0或1。¾查询是由三种布尔逻辑运算符and,or,not连接索引词组成的布尔表达式。查询转化为一个主析取范式DNF()abcqkkk=∧∨¬34扩展的布尔模型¾ClassicalBoolean的最大缺点：只有0和1，没有ranking。要么返回大量结果，要么没有结果。¾ClassicalBoolean另一缺点：太僵化，在OR方式中，包含很多查询词的文档和包含少数词的文档是等同的；在AND方式中，即使缺少一个词，结果也是FALSE，等于一个词也没有¾多种扩展模型p-norm模型∞≤≤⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎝⎛=⎟⎟⎟⎟⎠⎞⎜⎜⎜⎜⎝⎛−−=∑∑∑∑====p)()),(...),(,())1((1)),(...),(,(111111111135向量空间模型（VSM）¾向量空间模型中将文档表达为一个矢量，看作向量空间中的一个点Example:D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T37325•IsD1orD2moresimilartoQ?•Howtomeasurethedegreeofsimilarity?Distance?Angle?Projection?36广义向量空间模型(GVSM)¾GeneralizedVectorSpaceModel¾原理通过其在多个文档中出现的模式（occurrencepatterns）来定义词项对查询中的词项也同样定义相似度的计算基于对d和q中重叠的模式来进行37广义向量空间模型(GVSM)¾基本步骤将文档集合表达为一个向量C=[D1,D2,...,Dm]将每一个词项按照其在文档集合上的分布也表达成一个向量：vec(ti)=[Tf(ti,D1),Tf(ti,D2),...,Tf(ti,Dm)]定义词项之间的相似度：sim(ti,tj)=cos(vec(ti),vec(tj))38广义向量空间模型(GVSM)¾基本步骤（续）sim(q,d)不再是q和d的向量点乘，而是用上述“词项-词项”相似度的某个函数。例如，对q的每一个词项，分别得到它和d中词项的最大相似度，将这些最大相似度加起来得q和d的相似度sim(q,d)=Σi[maxj(sim(tqi,tdj)]39广义向量空间模型(GVSM)¾好处自动包含了部分相似的效果•“北大”和“创建一流”等就会较高的相似度（near-synonyms，其实是共生词）不需要做查询扩展或者相关性反馈¾不利因素计算开销较大效果=“向量空间+Q扩展”的效果40概率模型¾贝叶斯定理¾词条的独立假设：P(AB)=P(A)P(B)当且仅当A与B相互独立¾由此对一篇文档而言，若文档中的各个词相互独立，则有P(dj)=P(k1)…P(kt))()()|()|(BPAPABPBAP⋅=假设标引词独立，则（假设标引词独立，则（KiKi：所有的词）：所有的词）()1()0()1()0((|))((|))(,)~(|))((|)ijijijijiigdgdjiigdgdPkRPkRsimdqPkRPkR====××∏∏∏∏41统计语言模型¾一元(Unigram)模型假设词与词之间是相互独立的，一个词出现的概率与这个词前面的词没有存在必然联系。¾N元(NGram)模型假设词与词之间是相互关联的，一个词出现的概率与这个词前面的词存在一定的关联。二元(Bigram)模型N元(NGram)模型)()...()()..(2121nnWPWPWP=)|()...|()()..(112121−=nnnWWPWWPWP)..|()...|()()..(12112121−−=42查