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

论文字数:23141,页数:52  有开题报告，任务书，实习报告

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

Clustering Search Engine Based on Independent Users
 
 
 Abstract
 The rapid development of the Internet has provided more and more internet information. In order to search the required information rapidly, search engines have become one of the indispensable internet tools. Nowadays, although many search engine systems have been applying many methods to improve the retrieval precision, the retrieved results still include a lot of irrelevance documents mixing with the relevance ones, and it brings users an additional burden.
 Based on the profile of search engines and cluster analysis, the clustering search engine for the independent users is designed. It helps the web users choose required information from along list of returned snippets, clustering of the retrieved results will assign snippets to automatically groups based on calculating the similarity. The groups (clusters) formed should have a high degree of association between members of the same groups and a low degree between members of different groups. So the users can only view their interested groups and save much time. In the process of design and implementation, when a independent search request is send to the search engine, the Yahoo API is used to obtain the necessary research data sources in our system and inverted files indexing model is used to create index while using the key words denoting index. The similarity is calculated according to the title of retuned results, URL and summary in our system, then search results and their relationship of similarity are mapped to an undirected graph. Finally, the points of the undirected map are clustered according to the similarity of each point in the undirected map and the ultimate results are gotten.
 During the clustering process, a new clustering method is proposed. Firstly, the method randomly selects a few points as initial centers. Secondly, each point is gradually added one or several clusters based on re-calculation of the similarity between added point and each center. If the similarity is greater than predefined threshold, the point will be added some cluster, whose center are adjusted until adding all the points. Theoretic analysis shows that the used reverted file model in our system needs little resources and proposed clustering algorithm resolves the problem of . And the isolating point problem is also considered. Experimental results also show that the proposed method has better clustering performance and the returned results can be clustered effectively.
 

Key Words: Search Engine; Clustering; Index; Similarity

目   录
摘 要   I
ABSTRACT   II
插图索引  IV
附表索引  V
1. 绪 论 1
1.1 研究背景 1
1.2 研究概况 2
1.3 本文结构 3
2. 搜索引擎概述 5
2.1 搜索引擎的组成 5
2.1.1 Robot 5
2.1.2 分析器 6
2.1.3 索引器 6
2.1.4 检索器 6
2.1.5 用户接口 7
2.2 搜索引擎工作流程 7
2.3 搜索引擎分类 8
2.3.1 全文搜索引擎 8
2.3.2 目录索引搜索引擎 9
2.3.3 垂直搜索引擎 10
2.3.4 元搜索引擎 11
3. 聚类研究 13
3.1 文档自动分类 13
3.2聚类分析 13
3.3 基本聚类方法 14
3.3.1 平面划分方法 14
3.3.2 层次凝聚方法 16
3.4 网页聚类算法 19
3.4.1基于网页内容的聚类算法 19
3.4.2基于链接分析的聚类算法 20
3.4.3基于用户搜索日志的聚类算法 21
4. 聚类搜索引擎设计 23
4.1数据源预处理 23
4.2索引的建立 24
4.3相似度计算 28
4.4聚类处理 29
5.性能分析 35
5.1 理论分析 35
5.2 系统演示 36
总 结 39
致  谢 41
参考文献 43