刘博宁_计算机技术.pdf

自动索引的矢量空间模型综述 刘博宁(兰州大学，730001）摘要摘要:在文件检索，或者是存储的实体文件之间比较以及与输入模式（搜索请求）比较的情形下，最好的索引（特征）空间是存储实体之间相距越远越好；在这种情形下，一个索引系统的键值可以用对象空间的密度函数来确定；特别地，检索表现可能与空间密度反相关。基于空间密度的一种计算方法曾经常常用于为文件集合确定合适的索引值。典型的估计结果表明了这个模型的有效性。A Abstractbstract:In the case of relatively well compared with the input mode between entities file retrieval or storage,the best index(feature)space is the distance between the farther the better storage entity;in this case,an index system density function keys can be used to determine the object space;in particular,the search may be inversely correlated with the performance space density.A calculation method based on the spatial density has been often used to determine the appropriate index values for the collection of files.Typical estimation results show the effectiveness of this model.关键词关键词:自动信息检索；自动索引；文本分析；文件空间 1 文件空间构造 设想一个文件空间由文件 Di构成，每一个文件空间由若干个索引项 Tj识别；每一个索引项可能会根据文件的重要程度加权，或者将权值减至 0 或 1 1。在 t 维相异的索引项出现时，三维的例子或许可以变为 t 维的。在这种情况下，每个文件 Di表示为一个 t 维矢量 Di=(di1,di2,.dit)，dij表示的是第 j 个索引项的权值。给出两个文件的索引矢量，计算它们之间的相似系数 S(Dj，Di)是可能的。S(Dj，Di)反应了对应索引项以及其系数的相似度。这个相似度的大小可能就是这两个矢量的点积，另外一个可能就是相应的两个矢量对之间角度的反函数。当索引项分配了两个完全一样的矢量时，这两个矢量之间的夹角就是 0 度，产生一个最大的相似度。对于每一个文件标示，并不是在坐标系中用从 0 开始的完全矢量表示，而是将相关的矢量之间的距离规范化到长度为一来保存的，同时假设单位圆表示矢量在空间表面的投影。在这种情形下，每一个文件可以一个单一的点描述，而这些点可以用相应文件矢量所形成的那片区域区分。具有相似文件索引项的文件用空间中响铃的两个点表示。简而言之，表示两个文件的点之间在空间中的距离与相应的两个矢量之间的相似度成反相关。由于文件空间的构造是索引项以及其权值对文件集合中每一个不同文件分配的一种函数，所以需要考虑一种最适宜的文件空间构造是否存在，也就是能够产生最佳检索效果的构造。在这种假设下，如果对于文件的特殊性一无所知，可以推测，理想的文件空间就是根据用户查询共同联系在一起而串起来的空间，因而这些文件共同检测出来以作为相应查询呢的响应。反之，那些从来不会同时查询的文件将会严格的出现在文件空间相对来说分离的位置。图 2 描述了这种情形，代表两个文件的矢量之间的距离反相关的与两个索引项之间的相似度联系在一起。图 2 所描述的文件构造也许确实描述了最好的情形，假设根据查询出现的相关的不想关的方面均描述得足够离散，而实际上这种构造是不存在的。因为在索引处理过程中，无法预知用户群体给出的相关性评估。也就 是说，最适宜的构造在没有给出文件集合的完全的检索历史的先验知识下无法得出。在这种情形下，可以推测次之的构造，最大可能的在空间中实现独立文件的分离，如图 3 所示。特别的，对于一个具有 n 个文件的集合，先使下面的函数最小化：（1）其中 S(Dj，Di)表示文件 i，j 之间的相似性。显然，当方程（1）被最小化之后，文件对之间的平均相似性是最小的。当给定的文件十分接近用户查询时，可以保证被检索到同时不会检索到领近的文件。这保证了检索输出的高度精确性。给定的一个确定的查询文件能够在检索到的同时不会检索到相邻的无关的文件。对于给定的用户查询，当几个不同的确定的索引分布在空间的大致相同的位置时，检索出许多相关文件而不相关文件被排除在外也是可能的。这可以产生高的召回率和准确率。这就提出了两个问题：首先，在实际上是否真的是离散的文件空间会产生好的检索表现，反之亦然好的检 索表现是否就说明了文件空间的离散程度；第二，是否存在一种可用的方法来衡量空间的离散程度。事实上，方程（1）是很难计算的，因为对于 n 个文件的文件集合，矢量的比较次数会正比于 n2。出于这个原因，将文件分类，每一类用一个质心代表，这种聚合的文件空间是考虑的最好的。一种典型的聚合文件空间如图 4 所示，这时不同的文件聚类可以用圆圈代表或者是由或多或少靠近各自族群中心的黑点所确定的质心代表。4对于一个给定的由 m 个文件组成的文件类 K，质心 C 的每一个元素可以定义为在相应的文件矢量中相同元素的权值平均，也就是：（2）相应于每一个独立文件群的质心，可以为整个文件空间定义一个质心。这个主质心，就像群组的质心从独立文件计算得到一样，可以按照一样的方式从各个独立的群组质心计算得到，在图 4 中用一个小矩形来表示。也就是说，整个空间的主质心就是各个不同的群组质心的加权平均。在一个聚合的文件空间中，如之前方程（1）介绍的那样，由成对的文件的相似度的和所构成的空间密度尺寸，可以用文件之间以及和主质心之间的相似系数的和来代替。也就是：（3）其中 C*表示的事主质心。尽管方程（1）的计算需要 n2的操作，每当 S(Dj，Di)正比于相应矢量的内积时，方程（3）的估计正比于 n。如图 4 所示，给定一个群组化的文件空间，有必要确定何种类型的群组代表最接近于图 3 所示的非群组化情形下的离散空间。对于大部分用户查询来说，如果假设紧密联系于一个群组的文件展示了同样的相关特征，那么较好的检索表现就是检索出表现的紧密联系而交错距离远的独立群组的群组化空间。也就是说，（a）在同一个群组空间里的文件对之间的相似度的平均值最大，同时（b）不通群组质心之间的相似度平均值达到最小值。当独立的群组松散的定义时，尽管不同群组质心之间的距离很小，也不会形成好的索引结果。在这篇文章接下来的讨论中，会给出联系文件空间和检索表现的实际的索引表现图表，以及关于自动检索好的模型的一些结论。2 检索表现和空间密度之间的联系 评估自动检索模型的实用的技术已经很好地理解了。总的来说，一种简单直接的处理会作为基本的准则。例如，从文件或者文件摘要中提取的关键字可以根据每个文件 i 中的检索项 k 出现的频率加权。这就是检索项频率加权模型。召回率图可以用来比较这种模型的检索表现和其他改进模型的输出。典型的例如，召回率图给出了步长 0.1，从 0.1 到 1 的，基于十个固定召回水平的用户查询请求的平均值的准确率数据。在同样的召回水 平上，较好的检索方法当然可以产生更高的准确率数据。将标准检索项的频率权值 fik和反相关于这个检索项下的文件（某一检索项下的文件集合）频率 dk的一个因子相乘，这个研究的一部分就是最好的一种最好的检索项自动加权处理评估2。特别地，如果 dk是某一检索项k 下的文件频率，那么检索项 k 下的反相关与文件频率的 IDFk可以这样定义3：则一个正相关于（fik*IDFk）检索项加权系统，将会赋给那些在独立文件中有高频率但是同时在整个文件集合中相对很少出现的检索项与最大的权值。我们从之前的研究中发现，在标准检索项频率权值系统上使用文件反相关的方法平均可以提高 14%的召回率和精确度（基于十个固定召回点的平均精确率提高）。对于 424 个空气动力学文件，使用两种不同的群组组织方法，获得的相应空间密度数据如表 I（a）所示：（i）群组 A 基于大量的相关的小群组，以及大量的群组之间的重叠部分（每个文件平均出 现在两个群组中）；通过放入与用户查询联系的所有文件的共同类中，群组的定义来源 于文件的相关性评估。（ii）群组 B 展示了某种大尺寸（相对于 A 中的每个类中 5.8 个文件，B 中每个类平均有 6.6 个）上的少量分类（B 中的 53 相对于 A 中的 155）；同时，在群组之间具有更少的重叠（A中每个文件平均在2.1个群组中，B 中为 1.3）。这些类用 Williamson 的自动快速树 搜索算法构建4。在表 I（a）中展现了两个群组的空间密度数据，包括文件和相应的群组质心之间的平均相似度（因子 x）；群组质心和主质心之间的平均相似度；两个群组质心之间的平均相似度（因子 y）。由于一个足够离散的空间将密集群组（大的 x）和不同群组之间的区别（小的 y）联系起来，故而比率 y/x 可以用来衡量空间的整体密度。从 I（a）中可以看出，基于反相关文件频率的索引系统具有较小的密度；也就是说，群组内的文件相似度越小，则群组之间的相似度越小。然而，群组之间的离散度要比群组内部文件之间的离散度要小。这就计算出了这两种索引系统之间的空间密度差别。表 I（a）的结果倾向于高准确度的检索结果与文件空间密度的减小有联系的观点。相反的提议，也就是无论较差的检索表现是否暗示了较大的空间密度，就是采取与以往不一样的实验，也即采用检索项权重操作测试。特别的，因为基于反相关于文件频率的权重系统产生了较好的召回准确度表现，那么直接根据文件频率加权的权重系统（出现在很多文件中的检索项得到较大权值）就会表现的相对较差。在表 I（b）的输出中，使用了正相关与（fik*DFk）的一种权重系统，其中 fik是文件 i 中的检索项 k 的检索频率，DFk+定义为 10/(IDF)k。表 I（b）中的召回率数据表明，与标准权重系统相比，该权重系统产生了大约 10%的检索性能下降。表 I（b）中的空间密度数据域 I（a）中的空间密度数据是一样的。对于 I（b）中的检索系统，不管实在群组内部还是外部，空间聚集现象都是值得注意的。然而，群组之间的质心相似度比群组内部文件之间的相似度增加更为明显。对于两种群组组织形式，y/x 的值分别增加了 16%和 7%。3 空间密度和检索表现之间的联系 在前面的部分中，在一种检索环境下能够搞笑操作的特定的检索方法似乎是和文件空间中矢量密度减小相联系的，并且相反的，较差的检索表现与密集空间有关。空间构造和检索表现之间的联系也许可以从一个相反的角度来考虑。相比于挑选文件分析和已知检索特征的检索系统，并且测试他们对文件空间密度的影响，为了弄清期待的召回率和精确度方面的改变是否出现，人为的改变文件空间构成是可能的。之前给出的空间密度原则表明，群组之间离散程度高的具有松散文件群组集合会产生较好的检索表现。倒过来也适用于没有很好离散的大的非齐次群组。为了改善检索表现，提高在同一群组中的文件之间的相似性，同时降低不同群组或者群组质心之间的相似性是比较有效的。首先产生的效果是通过加强一些群组中独有的，或者是在群组中出现的频率高度不对称（也即某一检索项在一个群组中的出现频率非常高，而在另外一个群组中却不经常出现）的检索项而产生的。第二个结果是通过弱化在很多群组中出现的检索项实现的。下面的两个参数在后续的变化中会用到：NC（k）：检索项 k 所出现的群组数目（如果一个检索项至少出现在一个群组中的一个文件 中，我们则说这个文件在这个群组中出现过）。CF（k，j）：检索项 k 在群组 j 中出现的频率，也就是检索项 k 在群组 j 中出现的文件数目。对于 p 个群组的集合，平均群组频率可以通过 CF(k,j)来定义：给定了上述参数之后，对检索项频率的描述可以通过一下的因子来进行：另外一方面，反相关于 NC（k）的因子 F2（例如 F2=1/NC（k）可以用来反映检索项 k 在不同的群组中出现的频率。通过将每个群组 j 中的检索项 k 的权值乘以正比于 F1*F2的一个因子，可以得到文件空间的一个合适的展开。相反的，当一个正比于 1/（F1*F2）的一个因子被使用时，空间就会被压缩。表 II（a）的输出表明，利用因子 F1*F2修正了检索项权值后，收到了预期效果：同一群组（因子 x）中的文件之间的相似性更大了，而不同群组质心（因子 y）之间的相似性减小了。总之，两种群组组织方式下，空间密度（y/x）分别降低了 18%和 11%。对于伸展空间而言，平均检索表现如表 II（a）底部所示，提高了几个 百分点。相应的，利用变换因子 1/（F1*F2）压缩空间之后的结果如表 II（b）所示。同一群组内的文件之间的相似度减小了，而群组质心之间的相似度增加了。整体上，与标准检索项权值空间相比，两种群组组织形式下，空间密度分别上升了 11%和 16%。这样的密集文件空间导致了召回率和精确度方面 12%13%的损失。总之，表 I 和表 II 说明，检索表现和文件空间木渎呈现反相关，也就是说，在召回率和精确度方面好的有效的检索方式与离散的文件空间相联系；另一方面，认为改变空间密度将会引起期待的检索表现改变。之前提到的证据确认了检索项区别对待模型的无效性，并且这是自动检索理论的基础。这些问题将会在接下来的研究中简要解释。4 价值区别对待模型 作为索引区别对待的一种文件检索模型用于实验2,6。这种模型基于检索项的区别价值 DV，也就是基于一种可以衡量给定检索项长度的索引，当一种文件矢量分配给给定的文件集合时，这种索引可以增强文件矢量的区别。一个好的检索项具有高度可区别的值，从而当分配给文件集合时，可以降低文件之间的相似度，如图 5所示。相反的，劣等的检索项具有低区别度。为了衡量一个检索项的区别度，可以在分配特定的检索项前后取得空间密度，特别的，用类似方程（3）的函数来衡量整个空间的密度，也就是用所有文件以及空间质心的相似性的总和来衡量。一个给定的检索项对空间密度的贡献可以用如下方式来计算：（3）其中 Qk是检索项 k 从所有的文件矢量中删除后文件空间的紧凑程度。如果检索项 k 具有好的区别度，对于内容的区别具有价值，则 QkQ，也即文件空间在移除检索项 k 之后变得更紧凑（因为该检索项的分配导致了该文件集合中的文件聚合程度降低了，空间也因此变得展开）。所以，区别度高时有 Qk-Q0，反之则 Qk-Q0。从区别度的定义中可以明显看出，区别度好的就是当独立文件降低相似度分配而导致空间展开的那些参差不齐的出现频率的分布。同样的也适用于相反的情况。表 III 显示了从时代杂志上获取的 425 篇文章集合的最理想的 10 个检索项和表现最差的 10 个检索项列表（按照 Qk-Q 排序）。这个集合上总共有 7596 个检索项，排除删除的英语中的一些情态动词。为了将区别值模型变换为可用的索引理论，更加详细的测试好坏区别者的特性是必要的。图 6 是分配给由450 篇医学文章构成的简单集合的检索项，这些则是按照他们的文件频率排序的。对于每一个检索项分类频率为 1 的一类，为 2 的一类，等等相应的检索项按照平均区别度排序（等级 1 表示具有最好的区别度，因为总共有 4627 个检索项，所以等级 4627 表示最差检索项）。图 6 表明，较低文件频率的检索项平均起来具有较低的区别排名，例如那些仅仅在一两个文件中出现的检索项。几千个文件频率为 1 的检索项在区别度排序中排在 3000 到 4726 位。具有高文件频率的检索项则具有更为差劲的区别度排名，例如在 450 分文件中出现过 138 次的检索项。具有超过 25 次文件频率的检索项在医学文件集合区别度排名时均出现在 4000 名以后。区别度好的都会那些文件频率不高不低的区别者。图 7 中总结的是联系文件频率和检索项区别值的情形。4%的检索项具有最高的文件频率，代表了检索项分配的文件集合的 50%，这些具有最差的区别度。70%的检索项具有差劲的区别度。对于 n 个文件构成的集合，文件频率出现在 n/10n/100 之间的检索项占 25%，这些具有最好的区别度。如果图 7 是正确表示联系检索项重要度的模型，则有如下结果6,7：（a）具有中等水平文件频率的检索项应该直接作为内容标示，不需要做额外的变换。（b）具有高文件频率的检索项应该通过变换成低频率移动到文件频率表的左边；实现这个变换的最好方式是获取高频率的检索项并且将它们作为索引短语的成分短语“编程语言”将会比“编程”或者“语言”具有更低的文件频率。（c）具有低文件频率的检索项应该通过变换成高频率向文件频率图的右边移动；一种实现变换的方式是集合同一检索项分类中在语义上相似或者含有相同检索项的低文件频率的检索项。每一个汇集的分类都会有它所代替的单个检索项更高的文件频率。这种检索理论，通过从文件中直接提取文本作为检索项，结合高频度短语组成的检索项以及低频度元素汇集而成的检索项，已经在空气动力学，医学，世界杂志上的文件集合上得到过测试。图 8 显示了 450 篇医学文件的典型的召回率精度图。当召回率与精确度矛盾时，最接近右上方角落的曲线反映了最好的检索表现。可以从图 8 中看出，将高频率的无区别者用低频率的短语代替之后提高了平均 39%的检索效果（在是个固定召回点时提高的精确值比平均 39%要高）。对于之前提到的三种测试集合，右到左（短语变换）变换和左到右（汇集变换）变换总结于表 IV 中。对于低的召回率，精确度提高了 90%，中等召回率则提高了 40%70%，检索表现表最后的高召回率情形下则提高了45%。针对没有修正的单一检索项，上述在标准单一检索项频率处理过程中通过短语和汇集的变换，在世界杂志集合上了提高 18%，在医学文件集合上提高了 50%。针对空间密度分析的证据和文件频率索引模型对于检索表现的最佳性证明还无法给出。但是，这个模型对几个不同主题和领域的集合的检索表现都不错。以笔者的经验来看，本研究中的检索结果还没有超越以前进行的手工的或者自动进行的检索和分析。这个模型在实际用户环境下对于普通文件集合或许可以获得最好的检索结果。参考文献参考文献:1 Amazon EC2.http:/ Cisco Data Center.http:/goo.gl/Sil548.3 E.Bin,O.Biran,O.Boni,E.Hadad,E.K.Kolodner,Y.Moatti,and D.H.Lorenz.Guaranteeing high availability goals for virtual machine placement.In ICDCS,pages 700709,2011.4 C.Hyser,B.McKee,R.Gardner,and B.J.Watson.Autonomic virtual machine placement in the data center.Technical report,HP Laboratories,February 2008.5 Carnerro A G,Robert H K.Slash and burn agriculture:A close look at its implications for settlement pattersA.In:Anthony F C,Wallace E D.Men and CulturesM.Philadelphia:University of Pennsylvania Press,1960.229-234.6 J.W.Jiang,T.Lan,S.Ha,M.Chen,and M.Chiang.Joint vm placement and routing for data center traffic engineering.In INFOCOM(Mini-Conference),pages 31583162,2012.7 X.Li,Z.Qian,S.Lu,and J.Wu.Energy efficient virtual machine placement algorithm with balaced and improved resource utilization in a data center.Mathematical and Computer Modelling,58(5-6):1222 1235,September 2013.