基于查询空间的分布式文档集合划分算法

1、基于查询空间的分布式文档集合划分算法    摘要：合理的文档集合划分能够有效的提高分布式信息检索的效果，本文针对分布式信息检索中的集合划分问题，提出了一种基于查询空间的文档集合划分算法。与传统的基于文档空间的划分算法相比，该算法从一种全新的角度看待和理解文档集合划分问题，给出了一种针对大规模海量信息的文档集合划分解决方案。实验表明该算法在算法效果和算法效率方面都有很大的提高。关键词：计算机应用；中文信息处理；分布式信息检索；文档集合划分；聚类1前言集合划分是影响分布式信息检索效果的一个重要问题。在分布式WEB信息检索中，开展集合划分的目的是希望通过集合划

2、分操作，继而在后面的检索过程中可以通过检索更少的文档而获取更好的检索结果。对于集合划分问题，直观的想法是为了让一个查询的相关文档都集中在一个或少数的集合中，但不同查询的相关文档可能是相同的，因此要实现将一个查询的相关文档都集中在一个或少数几个集合中的想法，常常会出现矛盾和冲突的情况。在以往的工作中，Claudine Badue等人研究了对索引划分的两种策略：一是把文档分布在多台处理机上，并行的建立索引并进行检索，在检索时采用并行检索的方式，每个搜索引擎同时检索；另一种策略是，将建立好的倒排索引，按照关键词的顺序分布在不同的机器上，每个引擎负责处理一部分关键词的倒排索引，在检索时，只有含有查询中

3、关键词的机器，参与到本次检索中。在这个工作中，对于第一种策略文档的分布是随机的，没有根据一定的原则来进行处理，在检索时采用的是并行的处理办法，由于对所有文档集合都要检索，没有降低检索的计算开销。Jeong通过研究对索引的划分来提高检索的效率，但这种对于索引的划分主要考虑的是提高检索的效率，没有对检索的效果进行充分的考虑。1999年SigIR上Xu和W.Bruce Croft等人采用的基于语言模型聚类的方法，把数据按照聚类结果进行划分，取得比较好的实验结果。该工作主要特点是从文档的聚类出发来实现对文档集合的划分。通过文档的聚类，有利于把相关的文档聚集在一个类中，从而改善检索结果的质量，由于文档集

4、合划分是为了进一步检索服务的，因此必须考虑用户查询对于文档集合划分的影响，而该方法主要从文档内容角度出发来实现对于文档集合的划分，没有考虑查询对于文档集合划分的影响，该方法在效率方面也难以面对海量的信息处理。本文将尝试从查询空间角度实现对文档集合的划分，该算法将在划分的效率与划分的效果方面具有明显的改善与提高。2算法基本思想集合划分问题，就是要将文档集合划分成若干个子集合，使得进一步的检索能够取得更好的检索结果。文档集合的划分问题，虽然是对文档集合的划分，但绝不能简单的从文档角度看待这个问题，因为文档集合划分的目的是为了更好更方便的查找信息，因此文档集合的划分必须和信息的需求紧密联系起来，而信

5、息需求又是通过查询来体现的。一般的，对于信息检索问题，存在着以下几个相互关联的空间：用户空间、查询空间、文档空间、作者空间，如图1所示。传统的文档集合划分算法都是基于文档空间的，也就是说从文档本身角度实现对文档集合的划分，基于文档空间的划分方法是建立在“Closely as-sociated document tend to be relevant to the same requests”这个假设基础之上的。但文档集合的划分最终目标是为查询服务的，如果只关注文档空间而忽略查询空间显然是不合理的。文档集合的划分应该是以有利于查询为导向的划分，其划分的目的是为了更好的实现查询，即：同一个查询的相

6、关文档尽量集中在一个或少数几个文档集合中。从查询空间出发，要实现对文档空间的划分，必须建立起查询空间与文档空间的联系，这种联系就是查询与文档的相关关系。通过搜索引擎记录的查询日志来建立查询与文档之间的相关关系是一种有效的方法，当用户向搜索引擎发出一个检索请求时，整个检索过程包括用户点击的检索结果都会被搜索引擎记录下来，形成查询日志。查询日志一般记录了用户所查询的查询词、点击查看的文档等。例如“搜狗”搜索引擎的查询日志如图2所示。该日志每一行是一个用户访问行为的记录，包括了用户Session ID、查询词、URL(文档)、该URL在检索结果中的排序和用户点击该URL的顺序等信息。用户查询日志记录

7、了用户一系列重要的行为，因此常常被用来帮助提高检索结果的质量。如果假设用户通过搜索引擎返回的文档摘要(Snippet)可以判断该文档是否是查询的相关文档，那么可以认为用户点击过的文档都是查询的相关文档，也就是查询日志中每条记录的URL都是其查询词的相关文档，这样利用查询日志就建立起了文档和查询之间的相关关系，当然这相关关系的建立与实际的相关情况有一定的偏差，但总的来说用户的点击行为可以刻画查询与文档的相关关系。如图3所示，利用查询日志构建的文档和查询之间的关系可以被看作一个二部图，文档和查询之间的相关关系是二部图中的边。下一步本文需要解决的问题是利用构建的查询与文档的关系图，实现对文档集合的划

8、分。针对查找时间和空间开销随聚类进行不断增长的现实，本文提出采用BloomFilter算法来解决这个问题。BloomFilter算法可以使查找时间为一个常数，不随被查找集合的大小而发生变化，BloomFilter的另外一个优点是，空间开销固定不变，不会随处理的进行而不断增大，它是一种综合平衡时间、空间代价，允许存在查找错误的有效查找算法。虽然可能存在查找的错误，但在理论和实践方面，都可以把查找的错误控制在可以接受的范围内。另外，在查询日志中，相同的查询可能被用户多次查询，重复出现的查询在计算相关度时是被重复计算的，这样的计算是有实际意义的，因为如果文档d1和文档d2是查询qi的相关文档，而查询

9、qi被查询了很多次，虽然不能说因为查询qi重复出现了多次，就能增加文档d1和文档d2的相关性，但是从聚类角度认为d1和d2更相关是合理的，因为将d1和d2放入到一个集合中将有利于qi的查询，而qi的被查询次数多，有利于qi，就有利于降低查询的整体开销，这显然是合理的。4实验与分析为了验证基于查询空间的文档集合划分算法的                    有效性，本文使用的实验数据是“搜狗”搜索

10、引擎发布的查询日志数据。直观定性的感觉，一种好的文档集合划分结果应该具有这样的特点：1.一个查询的相关文档应该集中在一个或尽量少的文档集合中，这样在检索时，只要检索少量的文档集合，就可以得到全部相关文档。2.一个文档集合中尽量包含一个查询的相关文档，而不包含其他查询的相关文档，这样检索时处理的无关文档减少，有利于检索。3.文档集合的数量应该有一定的限制，如果没有集合数量上的限制，令每个文档集合中只包含一个文档，虽然可以很好的满足上面的两条要求，但这样的划分显然是不现实的。但这些直观的原则不能定量的刻画一种划分算法的有效性，本文采用了下面的评价原则来对划分结果进行评价，该原则很好的体现了上面对文

11、档集合划分的要求。评价原则：对于给定的一种文档集合划分算法和一个待查询的查询集合，计算出对于每个查询要检索到其全部相关文档所需要处理的平均文档数，把这个平均文档数作为评价原则，需要处理的平均文档数越少，说明划分越合理，划分方法越好。为了更好的说明实验所使用数据的特点，本文针对日志文件进行了分析统计。该数据集合的一些统计特性如表1所示。我们将用户查询日志分为“训练集合”和“测试集合”两个部分，训练集合用来对文档集合进行划分，而测试集合用来评价划分的结果。在实验中，文档空间与查询空间的相关关系采用前面定义的方法。为了方便比较，采用了随机的划分方法作为参照(随机的划分算法就是随机的将文档归入某个类别

12、)，具体的实验结果如表2所示。其中avgdoc1表示包括集合选择在内的整体代价(平均文档数)，而avgdoc2表示不计算集合选择过程的代价(avgdoc1和avgdoc2的计算方法，将在文档集合划分评价部分阐述)，由于文档集合共被划分为100个子集合，因此avgdoc1和avgdoc2相差100。从实验结果看，如果按照基于查询的划分方法，检索一个查询词需要处理的文档数目，大概只是随机划分方法的十分之一，约占整个文档集合的2.7，可见基于查询的文档集合划分方法相对于随机的划分方法取得了很好的实验结果，这充分体现出了采用该算法对于文档集合划分问题的重要意义。从效率角度看，对文档数为8 404 35

13、6的整个文档集合进行划分大约耗时57分钟，划分算法所消耗的绝对时间也是一个可以接受的划分时间，由于该算法是一个线性时间复杂度的算法，因此算法的运行效率是可以满足文档集合划分要求的。5结论基于查询的文档集合划分方法从查询空间这一全新视角实现对文档集合的划分，该方法利用查询日志建立起文档与查询的关系图，并采用本文提出的LIBCA算法实现了从查询空间出发对文档集合的划分。基于查询的文档集合划分方法体现了文档集合划分的直接目标，即：划分的目的是为查询服务。从实验结果看，无论是算法的效果还是算法的效率都取得了比较理想的结果。在基于查询的文档集合划分中，实现了利用查询空间对文档空间的划分，反过来，利用文档空间也可以实现对查询空间的划分，或者是在对文档集合划分后，会自然形成每一个子文档集合对应着一系列的查询的情况，这些查询对应了该子文档集