基于Web的信息检索技术综述

—7—基于Web的信息检索技术综述蒋凯，武港山（南京大学计算机软件新技术国家重点实验室，南京大学计算机科学与技术系，南京210093）摘要：随着信息技术的发展，特别是Web的不断普及和应用，Web上的信息飞速增长，形成了巨大的信息资源。因此，如何从巨量的信息中快速有效地提取出所需的信息，成为迫切需要解决的问题。文章分别介绍了几种传统的信息检索模型和基于潜在语义分析的信息检索模型，以及自动问答系统，并在多方面对它们进行比较，最后展望了问答系统的应用前景。关键词：信息检索；潜在语义分析；自动问答OverviewofInformationRetrievalTechnologyforWebJIANGKai,WUGangshan(StateKeyLaboratoryforNovelSoftwareTechnology,NanjingUniversity,DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093)【Abstract】Withthedevelopmentofinformationtechnology,especiallythewidespreaduseofWeb,informationonWebincreasesrapidlyandbecomesahugeinformationresource.Inthemeanwhile,suchabundantinformationmakesitanurgentproblem:howtoextractusefulcontentrapidlyandefficientlyfrominformationresources.Thispaperintroducesseveraltraditionalinformationretrievalmodelsandlatentsemanticanalysistechnique,andthengivesabriefdescriptionofthequestion-answeringsystem.Furthermore,thispapercomparesthesemodelsfromsomecertainaspects,andanalyzespossibleapplicationsofquestion-answeringsysteminthefuture.【Keywords】Informationretrieval;Latentsemanticanalysis;Question-answering计算机工程ComputerEngineering第31卷第24期Vol.31№242005年12月December2005·发展趋势/热点技术·文章编号：1000—3428(2005)24—0007—03文献标识码：A中图分类号：TP3911传统的信息检索模型传统的信息检索的目的是根据用户的查询即关键词从大量的文本中找到满足用户要求的相关文本，其中心问题是判别相关文本和无关文本。检索模型即是判断文本是否与查询相关和对相关文本进行排序的数学模型。根据相关度判别方法的不同，发展出了不同的信息检索模型，传统的信息检索模型大体可以分为3类：布尔模型，向量空间模型和概率推断模型。1.1布尔检索模型布尔（Boolean）模型[1]是最典型的一种集合模型，是信息检索系统提供的基本功能，在传统的信息检索中有着广泛的应用。它将文本表示成布尔表达式，然后再通过与用户的查询表达式进行逻辑比较来检索相关文本。标准布尔逻辑模型是二元逻辑。在布尔模型中，首先要针对文本定义一系列的二元特征变量，这些特征变量一般是从文本中提取出来的文本索引关键词，有时也包括一些更为复杂的特征变量，如数据、短语、私人签名和手工加入的描述词等。其次，使用这些特征变量的集合来表示文本Di=（dil,di2,…,din）,其中，n是特征项的个数；dik为True或False，如果特征项k在文本Di内容中出现，就赋予True值，反之置为False。在布尔模型中，用户可以根据检索关键词在文本中的布尔逻辑关系，用“∧”（AND）、“∨”（OR）、“¬”（NOT）等逻辑运算符将多个关键词连接成为一个逻辑表达式来递交查询。匹配函数由布尔逻辑的基本法则确定，通过对文本表达式与用户查询表达式的逻辑比较进行检索，所检索出的文本或者与查询相关，或者与查询无关。1.2向量空间模型向量空间模型(VectorSpaceModel,VSM)克服了使用布尔模型中二元权值的缺点，采用非二元权值来表示特征项在文本和用户查询中的权重，提出了允许部分匹配的模型结构。在向量空间模型中，文本是使用特征项构成的加权向量来表示的：文本向量Di=(t1,wil;t2wi2;…;tn,win)。其中，n是特征项的个数；特征项tk与布尔模型中类似；wik为特征项tk在文本i中的权重。一般有两种方法来确定权值wik，一种方法是由专家或者用户根据自己的经验与所掌握的领域知识人为的赋予权值，这种方法随意性很大，而且效率也很低，很难适用于大规模文本集的处理；另一种方法是运用统计学的知识，也就是用文本的统计信息（如词频、词之间的同现频率等）来计算项的权重，大部分的统计方法都基于香农信息学理论：(1)如果特征项在所有文本中出现的频率越高，那么它所包含的信息熵也就越少；(2)如果特征项只在少量文本中有较高的出现频率，那么该特征项就会拥有较高的信息熵。目前被广泛采用的权值计算公式是TF-IDF公式：ikikikWtfidf=×其中tfik（TermFrequency）表示特征项tk在文本Di中项频率，idfik(InverseDocumentFrequency)表示特征项tk反比文本频率，一个著名的TF-IDF加权方法[1]：基金项目：国家自然科学基金资助项目(60073030)；国家“863”计划基金资助项目(2002AA117010-10)作者简介：蒋凯(1981—)，男，硕士生，主研方向：Web信息检索；武港山，副教授、博士收稿日期：2004-12-02E-mail：[e-mail]—8—ikikiNWflogn⎛⎞=×⎜⎟⎜⎟⎝⎠其中，fik表示特征项tk在文本Di中出现的次数，N表示全部文本数，ni表示文本集中出现tk的文本数。文本之间或者文本用户查询之间的（内容）相关程度（DegreeofRelevance）通常用它们之间的相似度Sim(Di,Dj)来度量。当文本和查询均被表示为向量空间模型时，可以借助于向量之间的某种距离来表示二者之间的相似度，常用向量之间的内积进行计算：1(,)nijikjkkSimDDWW==×∑相似度Sim(Di,Dj)越大，说明两个文本或文本和用户查询之间相关度越大。因此，可以根据相似度进行排序。1.3概率模型概率模型（ProbabilisticModel）[2]是为了解决检索中存在的一些不确定性而发展起来的，以数学理论中的概率论为原理的一种检索模型。在此模型中，文本和用户查询的表示与布尔模型相同。同时，根据用户反馈，将文本分成相关的和无关的两类，然后根据每个特征变量（词）在相关文本集合和无关文本集合的分布情况来计算它们的相关概率，并将它表示成几率：()()/(1())ORPRPR=−（R表示“文本是相关的”，¬R表示是“文本是无关的”）。假设特征变量是相互独立的，因此，文本D和查询Q之间的相关几率可按如下公式计算：(|,)(1(|,))(|,)log()(|,)(1(|,))kkkkkPdRQPdRQORDQPdRQPdRQ∈−=¬−¬∑匹配的特征变量dk表示查询Q和文本D匹配的特征变量，(|,)kPdRQ表示该特征变量在相关文本集中出现的概率，(|,)kPdRQ¬表示该特征变量在无关文本集中出现的概率。概率模型的优势在于有很多形式，采用严格的数学理论为依据，能够按照相关度概率来对检索结果进行排序。它的检索效率要明显优于布尔模型。2基于潜在语义分析的信息检索模型2.1基本思想在传统的信息检索模型中，关于词之间的关系是假设相互独立的，但在实际环境中很难得到满足。因此，为了考虑词与词之间的相关性，处理自然语言的语义模糊性，从而产生了潜在语义分析的思想。潜在语义分析（LatentSemanticAnalysis,LSA）[3]是一种通过分析大量的文本集自动生成关键字-概念（语义）之间映射规则的方法。LSA认为词语在文本中的使用模式内隐含存在着潜在的语义结构，同义词之间应该具有基本相同的语义结构，多义词的使用必定具有多种不同的语义结构。LSA就是通过统计方法，提取并量化这些潜在的语义结构，进而消除同义词、多义词的影响，提高文本表示的准确性。2.2LSA/SVD为了实现LSA思想，需要通过数学方法建立潜在语义索引空间模型，这是LSA一个关键性的问题，直接影响运用LSA的性能。目前已有多种构造方法，本文只介绍LSA/SVD方法，这是最早提出使用，也是目前普遍使用的典型LSA空间的构造方法。LSA/SVD[3]方法通过对文本集的词-文本矩阵的奇异值分解（SingularValueDecomposition，SVD）计算，并提取K个最大的奇异值及其对应的奇异矢量构成新矩阵来近似表示原文本集的词条-文本矩阵。从某种意义上来说，LSA/SVD是一种用于发掘一组相互无关的索引变量（因素）的技术，从而使每个词-文本都可以利用左-右奇异值向量，表现为单个k维空间向量，并可以消弱噪音、词语使用多样性等对信息检索的影响。直观地说，因k值比文本集中词条m小得多，词义上地细微区别被忽略了。以下是具体做法：首先要构造一个训练集nm⋅词条-文本矩阵A=[aij],其中aij=L(i,j)*G(i),L(i,j)是单词i在文本j中的局部权重，G(i)是单词I在文本集中的全局权重,m为提取单词数，n为文本数。对A进行截取-SVD分解，(设mn,rank(A)=r,存在K,Kr且Kmin(m,n))，则在2-范数意义下，A的秩-K近似矩阵Ak为：A≈Ak=Uk∑kVkT。其中，Uk和Vk的列向量均为正交向量，UkTUk=VkTVk=Ik,Uk和Vk的列分别被称为矩阵Ak的左右奇异向量，∑k是对角矩阵，对角元素被称为矩阵Ak的奇异值。将SVD应用到LSI方法中（如图1所示），分解后各参数可作如下的解释：Ak：最接近词条-文本矩阵A的K秩矩阵；U：词语向量集；Uk：K维语义空间中词语向量集；m：词条数；V：文本向量集；Vk：K维语义空间中文本向量集；n：文本数；∑k:奇异值矩阵；K:降维因子；r:词语-文本矩阵A的秩。Ak是对A的一个近似，且在某种意义上保持了A中反映的词条和文本之间联系的内在结构(潜在语义)，但又去掉了因用词习惯或语言的多义性等带来的“噪声”。图1矩阵A的SVD分解3自动问答系统3.1基本思想传统的信息检索模型已经得到了广泛的应用，但是这些传统的信息检索模型还存在着很多缺点和不足[4]。自动问答系统是一种新的信息检索模型。对于问答系统，用户不需要将自己的问题分解成关键字，可以将问题整个提交给问答系统。系统运用自然语言处理技术，对问题进行理解，然后直接给出问题的答案。它就像一个知识渊博的专家一样，能够回答用户提出的各种问题。如，用户提交问题“伦敦在哪个国家”，系统回答“伦敦在英国”。3.2处理流程自动问答系统的处理流程如图2所示，它一般包括3个组成部分，也代表了问答系统需要解决的3个关键问题：问题分析，文本检索和答案抽取。问题分析（QuestionAnalysis）是至关重要的第一步，这个过程分析的效果对后续处理过程有着决定性的影响。它的职责就是准确而全面地获得自然语言问题中的语法、语义等信息，并将其用到便于系统识别和处理的方式提交给系统。主要有以下两方面的工作：A(AK)UKUΣVTKVTΣKkm*r词语向量文本向量≈m*nr*nkkkr*r—9—(1)问题分类。首先，为了寻找问题的答案，必须先知道答案的类型，系统会根据问题的