ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 信息检索及信息过滤方法概述(转)

信息检索及信息过滤方法概述(转)

原创 Linux操作系统 作者:jcszjswkzhou 时间:2019-05-14 12:12:06 0 删除 编辑
A Survey of Information Retrieval and Filtering Methods
1995年
Christos Faloutsos and Douglas Oard
University of Maryland
College Park, MD 20742
{christos,oard}@eng.umd.edu
中科院计算所软件室
(2002125日重新修改)
wangbin@ict.ac.cn
摘要
本文总结了信息检索(IR)的主要技术,主要内容分成两部分:第一部分,对传统IR方法(全文本扫描(full text scanning)、倒排文件(inversion)、签名文件(signature file)及聚类(clustering))的回顾;第二部分,介绍一些试图引入语义信息的新的IR方法(如自然语言处理(NLP)、隐性语义标引(latent semantic indexing, LSI)、神经网络(neural network)等等)
1 引言
本文分成两部分。第一部分回顾了传统文本检索的方法。总结传统方法出于两个目的:一,传统方法对了解新进展提供了丰富的背景知识;二,对这些传统方法进行变形或者扩展构成新方法的中心内容。具体来说,本文考察了(1)全文扫描方法及其在近似搜索(approximate searching)方面的进展;(2)可能在任何IR系统中都使用的快速倒排文件方法;(3)签名文件方法;(4)情报学中传统使用的聚类方法。
总结上述背景知识后,本文第二部分中介绍了近年来一些将NLP技术和IR方法进行结合的尝试,如隐性语义标引、神经网络等等。
文章最后是结论部分,作者给出了每种方法的要点及相关建议。
2 传统文本检索
2.1 全文扫描(Full Text Scanning)
确定某个字符串在哪些文档中出现,最直接的方法就是在所有的文档中查找该字符串(称为子串测试,substring test)。“字符串”是一系列字符组成的序列(不包含通配字符,Don’t Care Characters。比如我们常用*或者?来表示通配字符,译者注)。如果一个查询是由多个待查字符串组成的复杂布尔表达式,那么就需要额外的步骤来判断通过子串测试找到的匹配是否满足该布尔表达式(查询求解,query resolution)
本文不打算深入考查有关一般正则表达式的搜索方法,该主题可以参照HopcroftUllman1979年撰写的《自动机理论》[31,pp.29-35]。给定一个正则表达式,可以构造一个有限状态自动机,该自动机可以检测该正则表达式在文档中的出现。自动机的搜索时间与文档大小成线性关系,但是自动机的状态个数可能与正则表达式的大小成指数关系。
然而,如果搜索模式仅限于字符串,那么就可以应用比有限状态自动机更高效的方法。下面我们就讨论这些方法。
(1) 最显而易见的子串测试方法是:将搜索字符串与文档相应字符串进行比较,如果不匹配,则将文档指针右移一个字符位置后(也可以说将搜索字符串右移一个位置)重新将搜索字符串与文档当前的字符串比较,直至找到该字符串或碰到文件结束为止。该方法虽然简单易行,但算法实现时速度很慢。假设搜索的字符串长度为m,文档的长度为n,则最坏情况下需要O(m*n)次比较。
(2) KnuthMorrisPratt[37]提出一种只需要O(m+n)次比较的算法(KMP)KMP的主要思路就是,不论何时,只要能够预测到字符串的不匹配,则可能将搜索字符串右移不止一个位置。该方法需要对搜索字符串做一些预处理工作来检测递归的字母序列。预处理的时间为O(m)(该方法设计精巧,是数据结构课程中的典型内容,译者注)
(3) 当前所知道的最快的子串测试方法由BoyerMoore提出[5]。他们提出对字符串进行从右到左的比较;如果不匹配,搜索字符串可最多右移m个位置再进行匹配。最坏情况下,该方法需要n+m次比较,但通常情况下,比较的次数远小于这个数目。例如,对于一个随机的长度为5的搜索串(m=5),该算法的典型实现需要考查文档的i/4个字符(i为开始匹配的字符在文档中的位置)。同样,该方法需要O(m)的预处理时间。
(4) 近来对基本算法的变形可以参见Sunday [71]
(5) 子串测试的另一种方法基于自动机理论。AhoCorasick[1]1975年提出一种基于有限状态自动机的方法,该方法允许同时并行搜索多个字符串。搜索的时间为O(n),建立自动机的时间与待搜索字符串的长度成线性关系。
(6) WuManber[78]提出了一种能够容忍键入错误的搜索方法。该方法以每次一个字符的方式扫描数据库,并通过一种灵巧的位编码来记住当前已经匹配的字符串。该方法速度很快(Sun级别的工作站上几秒钟就可以查询数兆文本),也很灵活。其源码可从Arizona-Tucson大学匿名下载。
总之,每种全文扫描方法的优点都在于不需要空间消耗 (无索引),极小的插入和更新的费用(不需要更新索引);缺点在于反应时间太长,该缺点在面对大数据量时表现得尤为突出。所以,全文扫描方法常常用专用硬件实现(Hollaar1983)[30],或者将该方法同能够限制搜索范围的其他访问方法(如倒排文件)相结合使用。
2.2 签名文件(Signature File)
签名文件方法当前引起了广泛的关注。在本方法中,每个文档都通过Hash函数及重叠编码(superimposed coding)产生一个称为签名(signature)的位串。文档的签名结果顺序存入一个单独的文件(签名文件)中,签名文件比原文件小得多,因此可以提供更快速的搜索。FilesHuskey[26]将该方法用于一书目数据库。他们使用一停用词表来忽略普通的词,对非普通词则使用一个自动过程将它们还原成词干。同时,他们使用一个数值函数而非对照表(look-up table)作为Hash函数,。Harrison[28]使用签名文件方法以加快子串测试速度。他提出使用相邻的连续字母(n-gram)作为Hash函数的输入。Barton等人[3]1974年提出使用等频率文本片段(equi-frequent text segment)代替n-gram。因此,签名中“1”的服从均匀(uniform) 分布。TsichritziaChristodoulakis[73]试图使用无重叠编码的签名文件。他们的方法通过将文档中每个词的签名串联起来就得到该文档的签名。这样的话,就必须保留位置信息。RabittiZizka[48]声称该方法预期将比重叠编码更加重CPU的负担。
其他一些学者采用了类似的方法用于格式化的记录。一些文章中提出了对文本检索有潜在利用价值的想法。
Roberts [52] 1979年在一个电话目录的应用中使用了一级签名文件。他讨论了许多有趣的应用细节,其中的两个细节可以用于文本检索:
- 签名文件采用一种位片(bit-slice)的方式存储。即所有签名的头一位连续存放,次一位再连续存放,。尽管该结构使得更新很困难,但它能够减少检索的I/O费用。
- 他建议在构造签名时,查询中经常出现的标引项必须特殊对待。
然而,Roberts并没有提供这个方面的任何数学分析,而文档[23]中则对这一点进行了尝试。文章表明,如果词的访问模式和出现频率事先已知,并且分布足够偏斜的话(八二开),那么与同样大小的普通签名文件相比,该方法设计出的签名文件,可以避免约50%的误选(false drop)
此外,人们还提出了具有更高搜索速度的二级签名文件[55][54];签名树[14]以及基于签名的分割[39]也被提出,但是没有应用于真实数据库的时间结果的报道。
重叠编码方法的设计和研究由来已久。首先将重叠编码用于文本检索的人是C. N. Mooers [46]。他发明了一种很精巧的基于边缘凹口卡片和探针的机械设备。该设备可以快速处理对书目的联合查询。关键词抽取由人工实现,而Hash函数则使用对照表实现。
这种采用边缘凹口卡片的方法引起了广泛的兴趣。Stiassny[68]使用字母对来产生每个词的签名。他还证明:对于一个给定的签名长度,当文档的签名中“1”的数目等于“0”的数目时,误选概率达到最小。OroszTachacs [47]使用乔丹定律(Jordan’s theorem),给出了文档签名中“1”的概率分布的一个封闭形公式。KautzSingleton[35]讨论了设计一个没有误选的签名系统的问题,他们从编码和信息理论的角度对该问题进行了研究。尽管他们的方法在理论上很有意义,但在实现时有很多缺点:需要对照表;不易处理日益增长的词汇表;签名集合的设计需要巨大的开销。
在对签名文件方法的讨论即将结束之际,需要指出的是,该方法的主要缺点就是当文件很大时反应时间较长。优点在于实现简单,对插入的处理效率高,能够处理词的部分查询,能够支持不断增长的文件以及对键入和拼写错误的容错性。另外,该方法易于并行化(见文[67]中在Connection Machine上的一个实现)
2.3 倒排文件(Inverted File)
每个文档都可以用一系列关键词来表示,从检索目的来说,这些关键词描述了文档的内容。只要找到文档,便可以找到文档中的关键词。反过来,如果按关键词建立到文档的索引,便可以根据关键词快速地检索到相关文档。具体地,关键词被存储在索引文件(index file)(比如,按字母顺序存储),对于每个关键词,都有一个指针链表,该表中的每个指针指向与该关键词相关的某个文档,所有指针链表构成置入文件(posting file)。这种倒排文件的方法几乎被当前所有的商用IR系统所采用[61]
组织索引文件可以采用更复杂的方法,如:B树,TRIE树,Hash表或者这些方法的变形或混合([36] 471-542)STAIRS[32]使用了二级索引文件。以相同字母对开始的词在二级索引中放在一起,一级索引中包含指向二级索引的指针,每个指针指向每个字母对。Lesk[40]使用一张负荷过度、链分开的Hash(over-loaded hash table with separate chaining)来获得对一书目数据库的快速检索。
倒排文件方法的缺点有:存储开销大(倒排文件的大小可能会达到原文件大小的300%[29]);动态环境下索引文件更新和重新组织的开销大;如果表太大太多,则将它们合并的开销巨大。
该方法的优点有:实现相对简单,查询速度快,很容易支持同义词查询(例如,同义词可以在词典中组织成穿插表(threaded list))。由于上述原因,倒排文件的方法在当前绝大部分的商用系统中被采用(DIALOGBRSMEDLARSORBITSTAIRS,见[61]第二章)
近年来倒排文件方面方面的进展和挑战包括:
- 置入表分布不均匀(满足Zipf’s Law[1][82])。这意味着小部分词出现频率高,而大部分词只出现一次或两次。这样的话,有些置入表很长,而大部分置入表的长度为12。为了解决问题,人们提出了混合方法策略[24]以及使置入表可调增长的算法[25]
- 现实中,索引文件通常很大,可能有数兆甚至上G。而不管索引文件的大小如何,都要求必须能够快速地处理插入。快速增量式插入的技术可以参见Tomasic等人[72]CuttingPedersen[12]Brown等人[6]的工作。他们的做法基本上都是基于置入表分布的不均,对于较长和较短的置入表,分别采取不同的处理办法。为了解决倒排索引存储开销太大的问题,人们提出了一些压缩方法:Zobel等人[83]Elias的压缩体制[22]用于置入表。最后要提到的是,“glimpse”软件包[44]中使用一个很粗的索引加上“agrep”包[78]来实现近似搜索。
2.4 向量模型和聚类(Vector Model and Clustering)
聚类的基本想法就是将相似的文档聚合在一起形成类,该想法基于聚类假设(cluster hypothesis):紧密关联的文档往往与相同的查询要求有关。通过将相似文档聚类可以加速搜索过程。
聚类在信息检索、情报学[61][75]以及模式识别[16]等领域中都引起了广泛兴趣。虽然在模式识别中文档聚类并非重点,但模式识别中的许多方法和思想都可以用于文档聚类。
注意到聚类的对象除了文档外还可以是标引项,因此标引项也可以聚类形成共现标引项(co-occurring terms)类。共现标引项常常彼此相关,有时可能是同义词。标引项的聚类对叙词词典[2](thesaurus)的自动构造和降维(dimensionality reduction)很有用。叙词词典的自动构造基于统计准则,因此它在概念上与文档聚类方法是等价的。然而,Salton[58]声称自动标引项聚类算法的效率值得怀疑,因此,他建议使用半自动方法。
文档聚类包括两个过程:聚类产生(cluster generation)及聚类搜索(cluster search)。首先我们讨论聚类产生的方法并将它们分类。聚类搜索问题相对容易,将在后面部分讨论。
2.4.1 聚类产生方法(Cluster generation methods)
聚类产生过程的操作对象是向量或者t维空间上的点。每个文档都表示成一个向量,该向量被分配一些关键词,即将文档表示成关键词(可能包含权值)组成的向量。这个过程称为标引(indexing),可以通过手工或者自动实现。Salton[59]对这两种实现方式的对比表明,实验环境下实现的简单自动标引方法至少与手工方法性能一样好。
自动标引过程通常使用以下词典([57],第117页,第144-145)
- 一个用于去掉普通词(如“and”、“the”等等)的负性词典(negative dictionary),通常也叫停用词词表(stoplist)
- 一个用于抽取单词词干(stem)的前缀和后缀表;
- 一个用于将每个词干分配到一个概念类的同义词词典。
这种方法下,每个文档表示成一个t维向量,其中t是允许的标引项(概念)的个数。某个标引项在文档中不存在用0标识或-1标识[9],反之则用1(二值文档向量)或者某个正值(标引项的权重)标识,该权重反映了该标引项在文档中的重要程度。以下是几种其他的权重函数:
- FREQik:第k个标引项出现在第i个文档中的频率。该值很容易获得且比二值表示的权值更有效。(这个值就是通常所说的TF, Term Frequency,指Term在文档中出现的频率,一般来说,TF越大,表明该Term在文档中的重要性越大,译者注)
- 标引项专指度(Term specificity) [3] [66]logN-log(DOCFREQk)+1,其中DOCFREQk表示包含标引项k的文档数目,N是文档的总数。该值也容易获得,并且同样比二值表示的权值更有效。(这个值实际上可以认为是IDF计算的一个变形,表明该Term在整个文档集合中的分布情况,DF DOCFREQk越高,该值越低,越不可以用于区分,译者注)
- 逆文档频率(Inverse Document FrequencyIDF)FREQik/DOCFREQk。与前面的权值相似但似乎更有效([61]105)(IDF通常是指N/DOCFREQk, TFIDF才是FREQik/DOCFREQk,译者注)
- FREQik*TERMRELk:其中 TERMRELk=(rk/(R-rk))/(sk/(I-sk)),称为标引项相关因子(term relevance factor)R为文档集合中所有相关的文档数目,rk为相关文档中含有标引项k的文档数目,I为所有不相关的文档数目,sk为不相关的文档中含有标引项k的文档数目。在某种条件下,该权值为理论上最优的权值[79],且试验结果似乎证实了这一点([61]207)。该方法的问题在于必须对查询和所有文档之间进行相关性评估并对每个标引项计算相应的参数,这需要人类专家花费大量时间才能实现。(TERMRELk可以认为是该Term在相关文档出现的概率和在不相关文档出现的概率的比值,是概率检索模型中常用的一个参数,现在通常通过相关反馈方式来计算,译者注)
上述过程将文档表示成t维空间中的点。下一步就是要将这些点划分到不同的类中。在理想情况下,划分过程应该达到两个目标:(1)在理论上稳定(theoretically sound)(2)高效(efficient)。理论上的稳定性准则是指([75],第47)
- 该方法在增长情况下保持稳定,也就是说,当插入新的文档时,划分不会显著地改变;
- 文档描述中的细微错误只导致划分的细微改变;
- 方法与文档的初始顺序无关。
高效性准则主要是指聚类的时间开销。在分析聚类生成方法的性能时,常常忽略该方法的空间消耗。
迄今为止,人们提出了许多聚类生成方法。但不幸的是,没有哪个单一的方法同时满足稳定性准则和高效性准则。因此,在这里将各种聚类生成方法分成两类:
- 基于文档间相似矩阵的稳定性方法;
- 有效的直接来自文档向量的迭代方法。
基于相似矩阵的方法(Methods based on the similarity matrix)
这类方法通常需要O(n2)或更多的时间费用(n为文档的数目),且常常要用到图论技术。该方法中,必须选择文档之间的相似性函数来度量两个文档之间的相似程度。人们提出了很多不同的相似性函数(如可参见[61]202-203),但是文档[75](38)指出,如果对上述相似性函数进行适当的归一化处理,则会发现它们提供几乎相同的检索性能。
给定一个文档相似矩阵,此类聚类方法的一个最简版本运行如下 ([16]238)
(1) 先选定一个适当的阈值;
(2) 相似度大于该阈值的文档之间用边相连;
(3) 该图的连通分量(最大簇)即为所要的类。
如果将类分层,即将类再聚类形成父类,父类再聚类形成父类的父类,,则常常可以加快检索的速度。一个将类分层的方法是将上述方法中的阈值不断减小进行使用。一个更好的将类分层的方法可以参见文档[74],该文档中使用单链(最近邻)聚类准则进行聚类。将该方法用于200个文档进行实验,实验结果表明,该算法执行需要的时间复杂度为O(n2)
上述方法(也许所有的聚类生成方法)的一个共同缺点就是它们都至少需要一个经验常数:用于相似性度量的阈值或者一个想要的分类个数。该常数会显著影响最后的划分结果,它会给给定的数据强加某种结构,而不是去探测数据内在可能已经存在的结构。也就是说,划分结果可能不是实际存在的某个结构,而是硬性划分的一个结构。
Zahn[81]提出的方法试图解决这一问题。他提出寻找给定点集合(文档集合)的最小生成树,然后删除不相容边(inconsistent edges)。当某条边的长度l比它的的入边的平均长度lavg大得多时称该边为不相容边。结果图的连通分支即作为聚类结果。同样,该方法基于一个经验值(用于不相容边定义中的阈值)。但是,该方法的结果受该经验值的影响并不十分敏感。在文章中,Zahn宣称其方法在多种环境下应用于真实2维数据的有效性:重叠高斯型聚类(Overlapping Gaussian Clusters),延伸型聚类(核粒子轨迹),以及生物样本建立的聚类等等。文章中没有实验结果的报道,但是该方法似乎很有前途。
迭代型方法(Iterative methods)
该方法包含了运行时间少于O(n2)时间(O(nlogn)O(n2/logn))的多种方法。这些方法直接基于对象(文档)的描述,并且它们不需要预先计算的相似矩阵。该方法在提高效率的同时,付出的代价是牺牲了理论稳固性,最后的分类结果依赖于对象处理的顺序,并且,文档描述错误的结果是不可预测的。这些算法基于启发式方法,并且也需要一些经验值参数,比如:
- 想要的分类数目;
- 每个类中含有的最小及最大文档数目;
- 用于文档和类之间相似度量的阈值,一个文档与类的相似度小于该值时便将它排除在该类之外;
- 类间相互重叠的控制值;
- 一个任意选择的用于优化的目标函数。
该类方法的过程可以概述如下:
- 确定一个初始的划分;
- 反复迭代,重新将文档分配到各个类中,直至不存在一个更好的重新分配为止。
很多迭代型方法都在文献中找到。对迭代型方法的一个综述可以参见文档[75](51-53)。最简单、最快的方法似乎是单遍(single pass)方法[62]。每个文档只须处理一次,要么它被分配到某个类(如果允许重叠的话,可以分配到多个类)中,要么它产生一个新的类。
在实际中常常可以将基于相似矩阵的稳定性方法和迭代型方法混合使用。SlatonMcGill[61]提出,可以先使用迭代型方法建立一个粗划分,然后通过图论方法将先前划分继续划分。Van-Rijsbergen[75]提出另一种混合方法。该方法首先从文档集中抽样出一些文档,然后利用一个时间为O(n2)的算法为这些样本文档构造一个核心聚类,最后使用一个快速的分配策略将剩余的文档分配到已存的类中。
Salton[60]对一些迭代型聚类方法的运行时间进行了分析。分析表明,如果假定平均的类个数为lognn/logn,则迭代型聚类方法的平均运行时间为O(nlogn)或者O(n2/logn)。然而,最坏情况下,运行时间将达到O(n2)
2.4.2 聚类搜索(Cluster searching)
在已经聚类的文档中搜索将比聚类生成简单得多。输入查询将表示成一个t维向量,然后将该向量与每个类的质心进行比较。搜索过程处理最相似的那些类,即那些与输入向量相似度大于某个阈值的类。该算法中必须选择一个用于度量类与查询向量之间相似度的函数,这个函数常常选择向量间的夹角余弦函数[57]
YuLuk[80]对上述搜索策略作了修改:给定一个(2)查询向量及(2)类向量,他们推导出一个公式,该公式用于计算每个类中满足查询的文档数目的期望值。然后,算法将只在可能含有足够多满足查询的文档的类中继续搜索。在文档[62]中,他们给出了该方法的实验结果。实验表明,该方法与夹角余弦函数方法的性能几乎一样(后者更简单些)
Croft[11]采用模式识别方法,推导出一个线性判别式函数,该函数本质上是一个查询向量与类之间的相似度计算函数。他使用文档频率的对数值作为每个标引项在类中的权值,通过与夹角余弦函数方法的比较,他认为这种方法性能更优越。
查询和文档的向量表示可以采用一种称为相关性反馈(relevance feedback) [53]的方法,该方法能够提高搜索的效率。用户可以在检索到的文档集合中确认真正相关的文档,根据这些文档,检索系统可以重新生成查询向量重新进行搜索。通常,重新生成查询向量的方法是将相关文档的向量与原查询向量相加,并减去不相关的文档向量,加减的过程中可能会加权。
实验结果表明,通过23次迭代之后,上述方法可以得到很好的结果[56]
3 使用语义信息(Using Semantic Information)
在上面讨论的IR方法中,我们只使用了文档的很少一部分信息用于确定相关性[42]。尽管这些方法存在固有的缺陷,但它们却常常能够达到可以接受的正确率,这主要是因为一个文档的所有文本中包含了大量的冗余信息。下面,本文将考查近年以来一些试图从文档中获得更多信息、获得更好性能的方法。
这些方法可以分成三类:(a) 使用分析技术,句法信息及一般自然语言处理技术的方法;(b) 隐性语义标引方法;(c) 使用神经网络比如激活扩散(spreading activation)模型。
3.1 自然语言处理(Natural Language Processing)
NLP技术试图通过将某个查询的语义信息与文档的语义信息进行匹配来提高查询的性能[33][49][76]NLP技术已经被应用于大规模Text Retrieval Conference(TREC) 语料库,并获得了一定程度的成功[70][41][69]。尽管人们声称,要使IR达到其最佳潜能,必须对文本和查询进行更深层次的语义分析。但是,自动语义分析技术能否带来显著的性能提高仍然有待证实。
然而,NLP技术和浅层的IR技术之间并不像它们起初表现那样具有明显的边界。例如,通常使用的停用词表就用于去掉语义含量较低的词语。另一个将NLP技术与传统的IR方法相结合的简单例子就是使用短语作为标引项。Croft等人[10]提出使用一个粗分析器[7]来探测句子,然后利用句子来进行索引(与使用单个标引项相反)。使用短语作为标引项的好处就是,短语携带了更多的语义,但是,这样做的代价就是,短语的特殊性将会降低依赖于一般性的评分(ranking)及匹配算法。基于同样的思路,RauJabobs[50]利用词典进行分析,将关键词分组来获得更高的正确率和召回率。Mauldin[45]使用一个浏览式(skimming)分析器(quick-and-dirty式分析器)将文档转换为格框架(case frames)。同简单的关键词系统相比,该方法尽管有时会产生更坏的结果,但通常可以提高正确率和召回率。Salton等人[63]提出首先利用文档向量进行初始过滤,然后再利用章节、段落以及句子向量进行比较。
在一个具有更完备的NLP功能的IR系统中,第一步很可能是自动句法分析。近年以来,自然语言的句法模型方面取得了相当多的进展,出现了多种可用的宽领域高效分析器[43]。语义分析不太好理解,但是一个称为词汇成分语义学(lexical compositional semantics)的语法制导语义(syntax-directed semantic)技术取得了进展。更深层的语义表达看来需要更广阔的知识工程,因此束缚了依赖于NLP的系统的进一步发展。作为一种人工智能技术的格框架(case frame)分析方法,在某些限定领域被成功使用[51]
3.2 隐性语义标引(Latent Semantic Indexing)
隐性语义标引(LSI)是一种被证实比在SaltonSMART系统中使用的传统向量空间技术性能更好的IR向量空间技术。下面将给出LSI的一个简要但很严格的数学描述细节。
为了简明扼要起见,本文省略了很多有关LSI进展的基本原理以及奇异值分解[4](Singular Value DecompositionSVD)的存在性和唯一性论述,对该内容感兴趣的读者可以与Deerwester等人联系[13]LSI在信息过滤以及信息检索方面的应用在文[27][21][19]中都有介绍,该技术的未来展望参见文[17][18][2]
首先我们通过一个最简单的例子来阐述LSI技术的本质。首先从全部的文档集中生成一个标引项-文档矩阵,该矩阵的每个分量为整数值,代表某个特定的标引项出现在某个特定文档中次数。然后将该矩阵进行奇异值分解,较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和查询向量映射到一个子空间中,在该空间中,来自标引项-文档矩阵的语义关系被保留,同时标引项用法的变异被抑制。最后,可以通过标准化的内积计算来计算向量之间的夹角余弦相似度,再将文档按与查询的相似度降序排列。
3.2.1 符号
我们采用了Deerwester等人[13]引入的符号。标引项-文档矩阵Xt(每行表示每个标引项在文档中的出现情况)d(每列表示集合中的每个文档)SVD X=T0S0D0T,结果T0是一个t×m的矩阵,它的标准正交列称为左奇异向量;S0是一个m×m的正奇异值按降序排序的对角矩阵;D0是一个d×m的矩阵,其标准正交列称为右奇异向量。m为矩阵X的秩。图1XSVD作了描述。
通过T0S0D0X可以精确地重构。LSI中的关键创新在于只保留S0中的k个最大的奇异值,而将其他的值置为0k的值是设计时的一个参数。k的取值通常在100200之间。原来的X矩阵可以用X来近似,X=TSDTT是一个含有标准正交列的t×k矩阵,S是一个正定的k×k对角矩阵,D是一含有标准正交列的d×k矩阵。图2XSVD作了描述。

3.2.2 文档匹配(Document Matching)
LSI的有效性依赖于SVD可从文档集的标引项频率向量中抽取关键特征。为了更好地理解这一点,首先有必要给出一个关于构成SVD的三个矩阵的操作性解释。在源向量空间表示中,XTX是文档向量的内积d×d对称矩阵(即计算文档之间的两两相似度,译者注),其中每个文档利用标引项频率向量表示。这种矩阵的一个用途是支持文档集合的聚类分析。XTX矩阵的每一列都是X矩阵相应列的文档向量与每个文档向量的内积集合。于是,文档i和文档j的夹角余弦相似度可以如下计算:

因此,我们可以将矩阵XT看成一个从列向量Xq(描述某个单一文档或查询)到一个内积列向量(可以用于计算夹角余弦相似度)的线性函数(XTXq中的d个分量代表d个文档分别和Xq的相似度,译者注)。利用SVDXT扩展,XTXq=D0S0T0TXq。将该式看成由D0S01/2S01/2T0T这两个线性函数的合成对帮助我们理解很有用。首先考虑S01/2T0T。该操作将查询向量投影到由左奇异向量生成的m维空间上。本质上,T0T矩阵将t维文档向量空间中的文档向量投影到一个m维的文档特征空间。因为每个奇异值都是正定的,S01/2是一个真正的对角矩阵。因此S01/2矩阵通过分别调节每个特征而在文档特征空间上重新调节。综合到一起来看,m×t矩阵S01/2T0T是从文档向量空间到文档特征空间的一个投影,在投影过程中加入了这样的想法,在估计文档相似性时,一些特征比另一些特征更重要。
一旦文档特征向量可用,d×m矩阵D0S01/2可以用来计算我们想要的内积。具体地,可以计算文档向量空间中的m

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10294527/viewspace-122065/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论