《借助查询历史改善结果排序的文件检索系统的设计及实现毕业论文》由会员分享，可在线阅读，更多相关《借助查询历史改善结果排序的文件检索系统的设计及实现毕业论文（61页珍藏版）》请在金锄头文库上搜索。
1、北京大学硕士研究生学位论文题目：一个借助查询历史改善结果排序的文件检索系统的设计与实现姓 名： 学 号： 院 系：信息科学技术学院专 业：计算机系统结构研究方向：计算机网络与分布式系统导 师： 版权声明版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。摘摘 要要随着网络的发展，网络上提供文件共享服务的服务器越来越多，共享的文件数量也随之增加。如何更好的检索、利用这些共享文件成为一个重要的问题。针对用户对文件检索的需求，本文在文件检索技术领域有如下贡献。1.
2、本文首先提出了一个文件检索的模型，明确了在文件检索模型中检索对象、查询串、查询与检索对象的匹配方式三部分的含义。检索对象，即文件条目表示为六元组name, ext, size, date, site, path的形式，查询串表示为以空格分隔的字符串的集合，查询与检索对象的匹配则表示为查询串与文件条目的匹配串之间的匹配。2. 提出了对文件检索系统进行评测的指标。将查询结果视作集合时以查全率、查准率为评测指标。将查询结果视作有序序列时，分析了查询结果的相关性、连接下载速度以及结果的可用性等因素对排序的影响，并提出了对排序进行评测的指标排序指数。作者还提出对于两个排序策略进行比较时，应当在结果的每个
3、页面内部应用排序策略，而不是在全体结果集合上应用排序策略，并比较平均用户选取条目的页内排名。3. 通过统计、分析用户对文件搜索引擎的检索和对检索结果中下载地址条目的选取，作者发现了用户行为习惯中的两个重要规律：一、少数查询串占据了全部查询请求的大多数，具体而言，前 20%的热门查询串占据了全部查询请求的80%；二、对全体用户而言，假设有 n 次不同的查询请求使用了同一个查询串，并且它们代表 k 类不同的查询意图。那么通常 k3，因而在 n 较大的情况下，则 n/k 的值较大，即大量的来自不同用户的请求代表了相同的查询意图。4. 基于上文所述，作者设计并实现了一个真实的系统。该系统借助查询历史改
4、善结果的排序。与一般基于用户历史信息的检索系统不同的是，本系统借助的历史信息不局限于当前用户的历史信息，还包含提交了相同查询串的其他用户的查询信息。或者说，即使当前用户是第一次使用本系统，本系统也能利用其他用户的历史记录来改进结果的排序和筛选。作者最后还验证了其实际的效果。应用本方法后，平均用户选取条目的页内排名从原来的13.70 名前进到了 8.93 名。试验结果表明文中所做的分析是正确的。关键词：文件检索系统，查询历史，检索模型The Design and Implementation of a File Index System which Improve the Order by Qu
5、ery HistoryAbstractWith the rapid expansion of the Internet, there are more sharing file servers. And the number of sharing files is increasing rapidly too. So its more important to retrieve these files easily.For the requirement of file retrieving of the users, we did the following jobs:1. We propo
6、sed a file index model. The model is composed of the expression of an index object, the expression of a query, and how the query word matches the index object. The index object can be expressed as name, ext, size, date, site, path, the query string is expressed as strings separated by space, and the
7、 matching between query and index object is realized by matching the query string and the matching strings of the file item.2. We also proposed the evaluation indicator for the file index evaluation. The precision and recall are useful when we evaluate the query result. But the result is not a set,
8、but an ordered list. So we indicated the factors in order: the relativity of the item, the connecting and download speed and the availability of the site. We proposed how to evaluate the order: average rank of chosen items. If we just want to compare two ranking strategy, we should not reorder all i
9、tems in the result set but only reorder the items within each page and compare the average rank of chosen items within page.3. By analyzing the records of users queries and the file items that users chosen from a real file search engine, we discovered two lows. 1). Most query strings are repeating h
10、ot query strings. 80% query words are the top 20% hot query strings. 2) If there are n times of queries using the same query strings, and the total number of different intensions is k. Then k should be a very small number (usually, k5对应的查询串的个数3315781010从上表可见，查询意图只有 13 个的查询串占全部记录数据的绝大部分，超过 5 种不同意图的查询
11、串在统计的日志中根本就没有出现。我们再来看一下 n 和 k 的比例的分布，统计结果如下图。图中横坐标表示查询串被查询的次数 n，综坐标为 n/k 的比值。要说明一点就是为了使图像中的点线显示清晰，我们忽略了很少量的查询次数非常高的词（这些点对应的横坐标值非常大），但事后的手工验证仍然证明了它们符合本文的规律。110100100001002003004005006007008009001000图 4-3 查询串与查询意图种类比值分析其中横坐标为查询串查询次数 n，综坐标为 n/k 比值（为指数标度）从图中可以看到，当 n100 时，n/k 的值都在 30 以上。由上面的分析我们能够知道，尽管查询
12、串不同，但一般说来，它们所代表的查询意图的数量并不是太多的，通常在1-3 种，并且在 n 较大的情况下（如n100），通常 n/k 的比值较大（本例中大于 30）。因此我们得到了第二个重要的规律：规规律律二二：假假设设有有 n 次次不不同同的的请请求求查查询询了了同同一一个个查查询询串串，并并且且它它们们代代表表k 种种不不同同的的查查询询意意图图。在在 n 较较大大的的情情况况下下（ n100），n/k 的的值值较较大大（ n/k30）。4.3用户行为特点的启发利用上面的用户行为特点中的两个规律，以及前面关于相关反馈方法的思路，可以考虑采用如下思路来实现一个借助查询历史信息改善结果排序的文件
13、检索系统。从上面的特征我们知道，大多数的查询请求不仅其查询串本身是重复的，而且其所代表的查询意图也是重复的。这样我们就可以由“较早的相同的查询串的结果选取记录”作为用户的反馈信号。这样一来，后来提交同样查询串的用户不需要任何主动干预，就可以得到经过反馈信号处理过的重新排序的查询结果了。当然，由于用户意图并不唯一，我们并不能确定究竟本次查询的用户是哪种查询意图，但因为 k 值通常都相当小（小于等于 3），因此对用户而言，很容易从这为数极少的查询意图中找到满足自己意图的结果。具体而言，我们可以考虑如下的思路。首先记录下每次用户对查询结果的选取。我们认为，用户在查询结果中点击的下载地址，就是用户认为
14、比较理想的下载地址。通过一段时间的记录，我们就得到了对于大量查询串的较理想的匹配结果。对于一个查询串q，我们有一个用户认为较好的文件条目的集合 S，我们将其表示为一个二元组 (q,S)。这样，我们就得到了大量的这样的二元组。依据规律 2，我们知道每个查询串可能代表几个不同的查询意图，那么不同的查询意图对应的理想下载地址肯定不同（否则就是相同的查询意图了），我们可以采用聚类的方法对每个 S 中的文件条目进行聚类。聚类后，对于每个q，我们会得到 k 种不同的类别，这 k 个类别就也就反映了不同的查询意图，而每个类别中的文件条目，就可以看作这个类别的训练集。每个类别中的条目个数，也直接反映了这个类别
15、的权重。当再次有用户查询同样的查询串 q 时，我们首先采用原始的检索方法，得到一个结果集合，然后用聚类得到的 k 个类别和训练集对其进行分类处理。一些条目被分到这 k 个类别中，另外一些可能不属于任何类别。不属于任何类别的条目往往也是用户不太需要的条目，可以考虑抛弃或排在结果的最后输出。第5章 系统体系结构与主要算法5.1系统体系结构基于以上分析，我们设计了如下的检索系统来改善文件检索系统的排序。Query String (q)Normal Index System (I)Index Result (S0)Feedback data DataBaseSite List DataBasequer
16、yClusteringThe training set for query item qItems not belong to any groupResult after Categorizati on (S)Categorization, OrderingFileitems that user clicked图 5-1 系统结构图下面我们来详细介绍这个模型。我们首先查看模型中的各个组成部分。Query String (q)：用户输入的查询串；Normal Index System(I)：常规的文件检索系统；Index Result(S0)：初始查询结果集；Feedback Data DB(F)：该数据库中记录了已有的每个查询请求和它对应的不同的 k 种查询意图，以及每种意图的作为训练集的文件条目。Fileitem DB(D)：该数据库中保存了每次用户进行检索后对查询结果的选取情况。具体而言，当用户进行查询后，检索系统返回结果，当用户在结果页面中对文件条目进行点击并下载时，本模型
