基于独立用户的聚类搜索引擎

摘   要
互联网的迅速发展提供了越来越多的网络信息，为了快速检索到所需信息，搜索引擎成为不可或缺的网络应用工具之一。而现有的搜索引擎尽管采用了各种方法来提高检索结果的精度，仍无法排除检索结果中用户查询请求不相关的文档，而且相关文档和不相关文档仍然相互混杂，也给用户带来了额外负担。
本文在对搜索引擎概况和聚类过程分析进行介绍的基础上，设计实现了一个基于聚类的独立用户搜索引擎，帮助Web用户从搜索引擎所返回的大量文档片断中筛选出自己所需要的文档，通过将搜索引擎返回的结果进行聚类为若干个簇类，使得同一簇类内文档相关度尽可能的大，不同簇类间文档相关度尽可能的小，从而大大缩小用户所需浏览的结果数量，缩短用户查询所需要的时间。在系统的设计与实现时，对用户的每次独立搜索请求，我们都采用Yahoo提供的API接口来获取研究所需的源数据，采用倒排文件索引模型建立索引同时采用关键词语的方法表征索引，根据检索结果的标题、URL和网页摘要所含信息计算返回结果网页之间的相似性，并将检索结果以及它们之间的相似性关系映射到无向图，最后根据无向图中每个点的相似度进行聚类最终得到结果。在聚类过程中，本文提出了一种新的聚类方法，该方法首先随机选取几个点作为初时质心，然后依次计算剩余点与质心的相似度并决定是否将其加入某个簇。如果大于某个阀值则将其加入该质心所代表的类并调整质心的位置，直至加入全部的点。理论分析表明，系统采用的倒排文件模型需要较少的资源，所提出的聚类算法在一定程度上解决了文档多义性问题，同时系统对孤立点问题也进行了相应的处理。实验结果也表明，本文所提的聚类方法具有较好的效果，能对返回结果进行有效聚类。 think58好，好think58 [资料来源：THINK58.com]

关键词：搜索引擎，聚类，索引，相似度
2.1.1 Robot
采用一定的搜索策略对Web进行遍历并下载文档，系统中维护一个超链队列，或者堆栈，其中包含一些起始URL。
Robot从这些URL出发，下载相应的页面，并从中抽取出新的超链加入到队列或者堆栈中，上述过程不断重复队列直到堆栈为空。为了提高效率，搜索引擎中可能会有多个Robot进程同时遍历不同的Web子空间；为了便于将来扩展服务，Robot应能改变搜索范围。Robot一般采用以宽度优先搜索策略为主、线性搜索策略为辅的搜索策略[4]。线性搜索策略：这是最简单的搜索方法，它的基本思想是沿着一个起始的IP地址，按IP地址递增的方式搜索后续的每一个WWW地址中的HTML文件，完全不考虑各站点的HTML文件中指向其他Web站点的超链接地址。此策略不适用于大规模的搜索（主要原因在于IP可能是动态的），但可以用于小范围的全面搜索，利用此种策略Robot可以发现被引用较少或者还没有被其他HTML文件引用的新HTML文件信息源。深度优先搜索：这是在开发Robot的早期使用较多的一种方法，它的目的是要达到被搜索结构的叶结点。深度优先搜索顺着HTML文件上的超链接走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链接。当不再有其他超链接可选择时，说明搜索已经结束。深度优先搜索适宜遍历一个指定的站点或者深层嵌套的HTML文件集，但对于大规模的搜索，由于Web结构相当深，也许就再也出不来了。宽度优先搜索策略：该搜索策略执行时先搜索一层中的内容，然后再继续搜索下一层。如一个HTML文件中有三个超链接，选择其中之一并处理相应的HTML文件，然后返回并选择刚才第一个网页的第二个超链接，处理相应的HTML文件，再返回。一旦一层上的所有超链接都已被选择过，就可以开始在刚才处理过的HTML文件中搜索其余的超链接。该搜索策略保证了对浅层的首先处理，当遇到一个无穷尽的深层分支时，也就不会再陷进去；且容易实现，具备大多数期望的功能，但是需要花费比较长的时间才能到达深层的HTML文件。 copyright think58 [来源：http://think58.com]
2.1.2 分析器
对Robot下载的文档进行分析以用于索引，文档分析技术一般包括：分词、过滤和转换。这些技术往往与具体的语言以及系统的索引模型密切相关。
2.1.3 索引器
将文档表示为一种便于检索的方式并存储在索引数据库中。索引的质量是Web信息检索系统成功的关键因素之一。一个好的索引模型应该易于实现和维护，检索速度快，空间需求低。搜索引擎普遍借鉴了传统信息检索中的索引模型，包括倒排文档、矢量空间模型、概率模型等。例如在矢量空间索引模型中，每个文档d都表示为一个范化矢量
 
ti为词条项，wi(d)为ti在d中的权值，一般被定义为ti在d中出现频率tfi(d)的函数。
2.1.4 检索器
从索引中找出与用户查询请求相关的文档，采用与分析索引文档相识的方法来处理用户查询请求。如在矢量空间索引模型中，用户查询q也被表示为一个范化矢量 。
然后按照某种方法来计算用户查询与索引数据库中每个文档之间的相关度，例如在矢量空间索引模型中，相关度可以表示为查询矢量 与文档矢量 之间的夹角余弦。最后将相关度大于阀值的所有文档按照相关度递减的顺序排列并返还给用户，当然搜索引擎的相关度判断并不一定与所有用户的需求完全吻合[5]。
2.1.5 用户接口
该部分为用户提供可视化的查询输入和结果输出界面。在查询界面中，用户按照搜索引擎的查询语法制定待检索词条及各种简单、高级检索条件。在输出界面中，现有大部分搜索引擎将检索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要和超链等信息；检索结果中相关文档和不相关文档相互混杂，用户需要逐个浏览以找出所需文档。这也正是本课题所要解决的问题。

内容来自think58 [资料来源：http://THINK58.com]

Web信息是动态变化的，因此Robot、分析器和索引器模块要定期更新数据库，时间视具体搜索引擎实现不同而有所差异，索引数据库越大，更新也越困难[6]。

[资料来源：http://think58.com]