1、IWeb 搜索结果自动归类系统摘要随着因特网上信息资源的爆炸性增长，搜索引擎已经成为了目前网络上最重要的信息检索工具。但很显然，人们对目前的搜索引擎还有很多不满之处。对于用户提交的检索要求，现有的搜索引擎（如 Google, Yahoo, MSN, 百度）通常计算网页相关性后返回给用户一长串结果列表。由于搜索结果中各种检索主题是混和在一起的，用户需要在大量的搜索结果中寻找所需要的信息，而且用户很难对搜索结果进行控制。要解决这些问题，一种组织和控制搜索结果的有效方法是必要的。如果在搜索引擎中采用聚类技术对搜索结果进行聚类处理，经过聚类处理的搜索结果以类目的形式呈现，主题相似的搜索结果被划分为一个
2、类目，类目之间同时又具有包含关系。这样，用户可以快速了解搜索结果的整体分布情况，并快速定位自己需要的搜索结果。在研究搜索引擎原理和聚类算法的基础上，本文对聚类搜索引擎的体系结构，以及应用于网页聚类的 Lingo 聚类算法进行了详细探讨。并基于开源聚类搜索引擎 Carrot22的框架，实现了适用于中文领域的 Web 搜索结果自动归类系统。首先，在本系统的框架设计上，充分考虑到中文环境的特殊性，由此在接口设计和可扩展性设计上，做了十分有意义的工作。其次，本文实现了描述优先的聚类算法 Lingo，系统聚类结果的可读性和可理解性都得到大大提高。最后，通过比较说明，采用描述优先的聚类算法对提高标签可理解
3、性的优势。关键词：聚类算法，搜索引擎，Carrot2, Lingo 算法IIIIIAn Automatic Categorization System for Clustering Web Search ResultsAbstractWith the exploding expand of the information resources in Internet, search engines have become the most important tools for users when surfing in Internet. However, obviously, web use
4、rs are not satisfactory with the present search engines.For each retrieval request by users, present search engines (such as Google, Yahoo, MSN and BaiDu) usually return a lot of search results by counting the relevance of web pages and the results are mixed with different subjects. Users have to lo
5、ok for what they actually need in a mass of search results without any direction. As well, its very hard for users to control the display of the search results. To solve these problems, an effective method to organize and control the search results is useful by applying clustering technology. With a
6、utomatic clustering system, all the results are organized as several clusters, which are gathered by similarity of web pages. So, web users can quickly get to know the entire distribution of all the search results and orient themselves to the object rapidly.With a study on the search engine principl
7、e and the clustering algorithms, this thesis discussed the architecture of clustering search engine, and the Lingo(Label INduction Grouping algOrithm) algorithm. Based on the open source framework Carrot22 clustering search engine, we have implemented an automatic clustering system for web pages in
8、Chinese. Firstly，as in the environment of Chinese, We consider a lot to design the system architecture to fit for it. Secondly, the thesis successfully implements the descriptive clustering algorithm which makes the result labels much more readable. Finally, the comparison shows that the priorities
9、of descriptive clustering algorithm to enhance labeling understandability.Key words：Clustering algorithm, Search Engine, Carrot2, Lingo algorithmVI目 录 第一章 绪论 .11.1 研究背景.11.2 聚类搜索引擎的现状.31.3 本文主要 内容.41.4 本文结构安排.5第二章 网页自动聚类技术 .62.1 文档预处理.62.1.1 预处理步骤.62.1.2 中文分词.62.2 向量空间模型（VSM） .72.3 描述优先的聚类算法.82.4 Li
10、ngo 聚类算法 .102.4.1 后缀数组（Suffix Arrays）.102.4.2 潜在语义索引（LSI）.112.5 小结.12第三章 自动归类系统（ACS）框架设计 .133.1 聚类搜索引擎概述.133.2 ACS 系统体系结构描述 .133.2.1 搜索引擎用户界面.143.2.2 调度中心.143.2.3 数据获取模块.143.2.4 搜索结果重排序模块.153.2.5 聚类分析模块.153.2.6 聚类结果输出模块.193.3 系统开发工具和运行环境.193.4 小结.19第四章 ACS 系统开发与测试 .20IV4.1 ACS 系统设计概述 .204.2 系统详细设计.2
11、24.2.1 系统过程设计.224.2.2 系统流程设计.224.2.3 系统容错设计.254.3 系统的实现.254.3.1 本地接口层次.274.3.2 查询处理链.274.3.3 系统的主要协调类.284.3.4 添加中文分词.294.4 系统聚类结果评测.324.5 小结.33第五章 总结与展望 .34参考文献 .36致谢 .38VContentsChapter 1 Preface.11.1 Background .11.2 Research Status of Clustering Search Engine.31.3 Content of Thesis .41.4 Outline
12、of Thesis .5Chapter 2 Clustering Technology for Web pages .62.1 Web pages preprocessing .62.1.1 Preprocessing.62.1.2 Chinese tokenizer.62.2 Vector Space Model .72.3 Descriptive Clustering .82.4 Lingo Clustering Algorithm.102.4.1 Suffix Arrays .102.4.2 Latent Semantic Indexing .112.5 Conclusion .12Ch
13、pater 3 System Architecture.133.1 Search Results Clustering Engineering .133.2 System Architecture.133.2.1 Graphical User Interface.143.2.2 Schedule Center .143.2.3 Data Fetch Module.143.2.4 Serch Results Resorting.153.2.5 Clustering Module .153.2.6 Output Module.193.3 Developing Tools and Environme
14、nt.193.4 Conclusion .19VIChapter 4 Development and Evaluatation.204.1 General Design .204.2 Design Specification.224.2.1 Architecture Design .224.2.2 System Flow Design .224.2.3 Error Control .254.3 Implementation .254.3.1 Local Interface .274.3.2 Query Process Chain .274.3.3 Main Classes.284.3.4 Ch
15、inese Tokenizer.294.4 Evaluatation .324.5 Conclusion .33Chpater 5 Summary and Envision .34Bibliography .36Acknowledgement .38第一章 绪论- 1 -第一章 绪论2007年1月23日，中国互联网络信息中心（CNNIC）发布了第19次中国互联网络发展状况统计报告 。根据报告，用户经常使用的网络服务中搜索引擎占51.5%，名列三甲。网民主要使用互联网的工具性功能，搜索信息与使用MSN等网上即时通讯成为网民花最多时间的网上活动。搜索引擎现在已成为用户利用因特网信息资源所不可缺少的
16、工具 1。但是现有的搜索引擎并不能很好的满足用户的需求。 1.1 研究背景对于用户提交的检索要求，现有的搜索引擎（如 Google， Yahoo， MSN， 百度）通常是通过计算网页相关性返回给用户一长串的结果列表。用户需要在大量的搜索结果中寻找自己需要的信息，因为搜索结果中各种检索主题全部混和在一起。这往往给用户带来烦恼。例如：用户在百度中输入关键词“引擎” ，想了解汽车引擎方面的知识。在百度返回的44，600，000 篇网页信息中(查询于 07-05-17)，排在前列的内容基本都是关于“搜索引擎”方面的知识。如果用户足够耐心，当他查看排在第 100 位的网页时，才会了解到有关“汽车引擎”的
17、内容。所以，在搜索引擎普遍采用相关度排序的今天，用户将不得不在经历一系列无关网页后才会获取到自己想要的内容。这种检索方式显然是存在缺陷的。图 1-13显示了用户对现有搜索引擎搜索结果的满意程度。图 1-1 用户对搜索引擎结果的困惑程度总得来说，传统的独立搜索引擎面临着以下挑战：（1） 返回的搜索结果数量太多。在很多情况下，用户总要在纷杂的搜索结果中仔细寻找自己想要的搜索结果。（2） 用户很难对搜索结果进行控制，无法分类查看或限定搜索结果，只能更换关键词重新搜索。Web 搜索结果自动归类系统- 2 -（3） 所有的搜索结果都是线性排列，用户只能逐行地从上往下浏览。无法迅速地获得搜索结果之间的类别
18、关系和重要程度。（4） 搜索结果是按照搜索引擎自身的相关性算法进行排序。然而同一关键词可能指代不同的语义，搜索引擎无法对这些不同的语义差别性地对待。要解决这些问题，一种组织和控制搜索结果的有效方法是非常必要的，也就是需要在搜索引擎中采用聚类技术，对搜索结果进行聚类处理。搜索引擎结果聚类技术实质上是为了方便用户的浏览，将聚类技术用于 Web 信息检索结果的可视化输出。 Web 网页聚类是指将网页集合分成若干个簇，要求同一簇内网页所描述的主题内容尽可能地相似，而不同簇间的相似度尽可能地小。搜索引擎结果聚类技术根据搜索引擎结果所提供的信息（如 URLs、标题、摘要等）来归纳出聚类，使得对搜索引擎返回
19、的大量的文档列表的过滤操作变得方便，这些聚类是搜索引擎返回的文档集合的高层视图。在搜索引擎中应用聚类技术，可以有效的组织和控制搜索引擎的搜索结果。经过聚类处理的搜索结果以类目的形式呈现，内容相似的搜索结果被划分为一个类目，类目之间同时具有包含关系。这样，搜索结果就被有效的组织起来，用户可以快速地了解搜索结果的整体分布情况，并快速定位自己需要的搜索结果。例如上述碰到的问题可以通过网页内容的聚类得到有效的解决或改善。如果把通用搜索引擎返回的搜索结果进行聚类，分成独立的语义相关的主题，如“搜索引擎” ， “图像引擎” ，“游戏引擎” ， “汽车引擎”等，那么用户可以快速的了解搜索引擎返回的结果都包含哪些主题，这样就可以轻松的获得自己关心的话题了。同时，我们也注意到自动归类等一些特性如今也越来越受到用户的追捧。图 1-2 不同年龄段的网络用户愿意网站跟踪其行为从而获得个性化服务的比例
