Web搜索结果自动归类系统-毕业论文

Web搜索结果自动归类系统摘要随着因特网上信息资源的爆炸性增长，搜索引擎已经成为了目前网络上最重要的信息检索工具。但很显然，人们对目前的搜索引擎还有很多不满之处。对于用户提交的检索要求，现有的搜索引擎（如Google, Yahoo, MSN, 百度）通常计算网页相关性后返回给用户一长串结果列表。由于搜索结果中各种检索主题是混和在一起的，用户需要在大量的搜索结果中寻找所需要的信息，而且用户很难对搜索结果进行控制。要解决这些问题，一种组织和控制搜索结果的有效方法是必要的。如果在搜索引擎中采用聚类技术对搜索结果进行聚类处理，经过聚类处理的搜索结果以类目的形式呈现，主题相似的搜索结果被划分为一个类目，类目之间同时又具有包含关系。这样，用户可以快速了解搜索结果的整体分布情况，并快速定位自己需要的搜索结果。在研究搜索引擎原理和聚类算法的基础上，本文对聚类搜索引擎的体系结构，以及应用于网页聚类的Lingo聚类算法进行了详细探讨。并基于开源聚类搜索引擎Carrot22的框架，实现了适用于中文领域的Web搜索结果自动归类系统。首先，在本系统的框架设计上，充分考虑到中文环境的特殊性，由此在接口设计和可扩展性设计上，做了十分有意义的工作。其次，本文实现了描述优先的聚类算法Lingo，系统聚类结果的可读性和可理解性都得到大大提高。最后，通过比较说明，采用描述优先的聚类算法对提高标签可理解性的优势。关键词：聚类算法，搜索引擎，Carrot2, Lingo算法IVAn 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 users 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 look 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 automatic 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 principle 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 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 of descriptive clustering algorithm to enhance labeling understandability.Key words：Clustering algorithm, Search Engine, Carrot2, Lingo algorithm目 录 第一章 绪论11.1研究背景11.2聚类搜索引擎的现状31.3本文主要内容41.4本文结构安排5第二章 网页自动聚类技术62.1文档预处理62.1.1预处理步骤62.1.2 中文分词62.2向量空间模型（VSM）72.3描述优先的聚类算法82.4 Lingo聚类算法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系统开发与测试20III4.1 ACS系统设计概述204.2系统详细设计224.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致谢38ContentsChapter 1 Preface11.1 Background11.2 Research Status of Clustering Search Engine31.3Content of Thesis41.4 Outline of Thesis5Chapter 2 Clustering Technology for Web pages62.1 Web pages preprocessing62.1.1 Preprocessing62.1.2 Chinese tokenizer62.2 Vector Space Model72.3 Descriptive Clustering82.4 Lingo Clustering Algorithm102.4.1 Suffix Arrays102.4.2 Latent Semantic Indexing112.5 Conclusion12Chpater 3 System Architecture133.1 Search Results Clustering Engineering133.2 System Architecture133.2.1 Graphical User Interface143.2.2 Schedule Center143.2.3 Data Fetch Module143.2.4 Serch Results Resorting153.2.5 Clustering Module153.2.6 Output Module193.3 Developing Tools and Environment193.4 Conclusion19Chapter 4 Development and Evaluatation204.1 General Design204.2 Design Specification224.2.1 Architecture Design224.2.2 System Flow Design224.2.3 Error Control254.3 Implementation254.3.1 Local Interface274.3.2 Query Process Chain274.3.3 Main Classes284.3.4 Chinese Tokenizer294.4 Evaluatation324.5 Conclusion33Chpater 5 Summary and Envision34Bibliography36Acknowledgement38VI第一章 绪论第一章 绪论2007年1月23日，中国互联网络信息中心（CNNIC）发布了第19次中国互联网络发展状况统计报告。根据报告，用户经常使用的网络服务中搜索引擎占51.5%，名列三甲。网民主要使用互联网的工具性功能，搜索信息与使用MSN等网上即时通讯成为网民花最多时间的网上活动。搜索引擎现在已成为用户利用因特网信息资源所不可缺少的工具1。但是现有的搜索引擎并不能很好的满足用户的需求。 1.1 研究背景对于用户提交的检索要求，现有的搜索引擎（如Google， Yahoo， MSN， 百度）通常是通过计算网页相关性返回给用户一长串的结果列表。用户需要在大量的搜索结果中寻找自己需要的信息，因为搜索结果中各种检索主题全部混和在一起。这往往给用户带来烦恼。例如：用户在百度中输入关键词“引擎”，想了解汽车引擎方面的知识。在百度返回的44，600，000篇网页信息中(查询于07-05-17)，排在前列的内容基本都是关于“搜索引擎”方面的知识。如果用户足够耐心，当他查看排在第100位的网页时，才会了解到有关“汽车引擎”的内容。所以，在搜索引擎普遍采用相关度排序的今天，用户将不得不在经历一系列无关网页后才会获取到自己想要的内容。这种检索方式显然是存在缺陷的。图1-13显示了用户对现有搜索引擎搜索结果的满意程度。图1-1 用户对搜索引擎结果的困惑程度总得来说，传统的独立搜索引擎面临着以下挑战：（1） 返回的搜索结果数量太多。在很多情况下，用户总要在纷杂的搜索结果中仔细寻找自己想要的搜索结果。（2） 用户很难对搜索结果进行控制，无法分类查看或限定搜索结果，只能更换关键词重新搜索。（3） 所有的搜索结果都是线性排列，用户只能逐行地从上往下浏览。无法迅速地获得搜索结果之间的类别关系和重要程度。（4） 搜索结果是按照搜索引擎自身的相关性算法进行排序。然而同一关键词可能指代不同的语义，搜索引擎无法对这些不同的语义差别性地对待。 要解决这些问题，一种组织和控制搜索结果的有效方法是非常必要的，也就是需要在搜索引擎中采用聚类技术，对搜索结果进行聚类处理。搜索引擎结果聚类技术实质上是为了方便用户的浏览，将聚类技术用于Web信息检索结果的可视化输出。Web网页聚类是指将网页集合分成若干个簇，要求同一簇内网页所描述的主题内容尽可能地相似，而不同簇间的相似度尽可能地小。搜索引擎结果聚类技术根据搜索引擎结果所提供的信息（如URLs、标题、摘要等）来归纳出聚类，使得对搜索引擎返回的大量的文档列表的过滤操作变得方便，这些聚类是搜索引擎返回的文档集合的高层视图。在搜索引擎中应用聚类技术，可以有效的组织和控制搜索引擎的搜索结果。经过聚类处理的搜索结果以类目的形式呈现，内容相似的搜索结果被划分为一个类目，类目之间同时具有包含关系。这样，搜索结果就被有效的组织起来，用户可以快速地了解搜索结果的整体分布情况，并快速定位自己需要的搜索结果。例如上述碰到的问题可以通过网页内容的聚类得到有效的解决或改善。如果把通用搜索引擎返回的搜索结果进行聚类，分成独立的语义相关的主题，如“搜索引擎”，“图像引擎”，“游戏引擎”，“汽车引擎”等，那么用户可以快速的了解搜索引擎返回的结果都包含哪些主题，这样就可以轻松的获得自己关心的话题了。同时，我们也注意到自动归类等一些特性如今也越来越受到用户的追捧。 图1-2 不同年龄段的网络用户愿意网站跟踪其行为从而获得个性化服务的比例Choice Stream在2006的年度调查如图1-2所示，用户愿意牺牲部分的网络隐私，以获得更个性化的服务。根据报告8，有79%的用户很愿意获取个性化的信息服务，有43%的网络用户愿意以个人隐私作为交换，来得到个性化信息服务，对比2005年这个比例有显著的增长（11%），尤其是在18-34年龄段的人群中，有14%的增幅。在Read/Write Web8今年发起的一个搜索引擎用户调查如图1-3所示，个性化搜索与聚类搜索都获得了较高的票数，也证实了个性化搜索是获得用户好评的搜索服务。得票数图 1-3 最有前景的搜索引擎特性聚类搜索引擎作为新兴的搜索引擎，其市场地位仍处于劣势。但可以看到，国内外各个聚类搜索引擎都在不断地尝试各种服务，为用户提供有别于传统搜索引擎的差异性服务。目前聚类搜索引擎还处于一个不断摸索和变化的阶段，其营利模式和市场竞争力还有等进一步发掘。然而，聚类搜索引擎作为整个搜索市场的一股新生力量，正在渐渐打破传统单一的独立搜索引擎独占的市场模式，给用户带来更新鲜的搜索体验，也掀开了搜索引擎市场激烈竞争的冰山一角。1.2 聚类搜索引擎的现状关于聚类搜索引擎的最早研究始于上个世纪70年代，由O. Zamir和 O. Etzioni等人在1997年第三届国际知识发现和数据挖掘大会（3rd International Conference on Knowledge Discovery and Data Mining）上提出的4，此后，Oren Zamir等人又进一步论证了将聚类技术应用于搜索引擎的可行性，并开发了第一个聚类搜索引擎Grouper5。聚类引擎是近几年才开始实际研究的课题，但很快引起了学术界的重视。自1999年开始，学者们开始以网页中包含的文字内容为聚类对象，对搜索引擎的聚类算法展开广泛的研究。在这个过程中，研究的层次不断深入，从对网页中分析出的关键词的进行聚类研究，到综合网页的语法语义信息对网页进行实际意义上的聚类。在针对网页文字内容的聚类算法展开研究的同时，学者们也尝试着将搜索引擎在搜索中产生的各种相关信息作为聚类对象，对这些信息的聚类算法进行研究。这些相关信息包括用户输入的检索式，用户对检索结果的访问情况，检索结果网页之间的链接关系等等。国外关于聚类技术在搜索引擎中的应用研究，已经有了较完整的理论体系，并且已经为互联网搜索用户提供聚类搜索服务，比较成熟的商业用聚类搜索引擎有Vivisimo6、Clusty、iBoogie、Webclust等。目前，聚类搜索引擎已呈现出多元化的发展方向，例如Grokker与Quintura将聚类结果进行可视化显示，Infocious将各种信息进行聚类整合，为搜索用户提供多种搜索服务。Carrot22是一个十分成功的开源聚类搜索引擎开发框架。它提供了基本的底层接口和一些基本的处理链，对一些聚类搜索共用的模块进行了有效的封装或者改进。这样大大提高了研究人员或者开发工作者试验新想法、新算法的效率。本系统就是基于Carrot2的开发框架，成功实现的适合中文环境的Web搜索结果自动归类系统。国内对聚类搜索引擎的研究还处于起步阶段，目前仅有一家商用的聚类搜索引擎BBMAO，但可以看到业界逐渐对聚类搜索引擎引起重视，很多学术机构都在研究这个领域，例如北大信息科学学院的Hua-Jun Zeng等人的论文Learning-to-Cluster7提出了聚类引擎就是其中一种解决方案。上海交通大学的APEX实验室也已发布一个简单的聚类搜索引擎。1.3 本文主要内容在本论文中，我们所做的主要工作如下：1 重点研究Carrot2底层的开发框架，并且根据实际情况作了大量针对中文语言环境下有益的改造和改善工作。主要有以下几个方面：（1） 构建系统底层查询流程，组织畅通的数据流通渠道。特别是在系统的整个开发框架中，如何保持接口的可扩展性以及高效性，本文作了很大的改进。针对中文应用，在本系统的框架设计上考虑了中文处理的特殊性，特别设计了中文预处理模块接口，而且成功的应用到了Web搜索结果自动归类系统中。（2） 添加中文分词，以适应中文查询的需求。在Carrot2提供的开发框架中，并没有提供中文应用方面的相关支持。而中文分词对于本系统的成功实现起到关键性作用。本文在仔细研究中文分词的相关技术后，成功地实现了适合中文查询的Web搜索结果自动归类系统。2 除了在框架设计，中文分词上所做的工作以外，还建立了一套适合中文领域的查询处理流程。本系统的实现流程如图1-4所示：图1-4 系统实现流程图1.4 本文结构安排论文主要探讨了描述优先的聚类算法，并在Carrot22的开源框架上，构建并实现了适用于中文的Web搜索结果自动归类系统（ACS）。本文共分为五个章节，各章节安排如下：第一章：绪论，涉及问题的提出，并介绍了聚类搜索引擎的研究背景，现状，以及本文的目的。第二章：网页自动聚类技术，介绍了研究和开发网页自动聚类系统的一些相关知识。第三章：自动归类系统（ACS）框架设计，讨论了Web搜索结果自动归类系统的体系结构，运用的技术以及系统所涉及的模块。第四章：ACS系统开发与测试，本系统成功高效的开发，得益于Carrot22高可扩展性的框架。第五章：总结与展望，对本系统开发的一些感想，以及对聚类系统今后发展趋势的一些展望。- 5 -Web搜索结果自动归类系统第二章 网页自动聚类技术Web搜索结果自动归类系统通常由以下几个部分组成：数据获取、数据预处理、特征提取和聚类过程，如图2-1所示。我们首先对聚类系统中涉及的一些概念和技术做一个阐述。图2-1 检索自动聚类系统的一般步骤2.1文档预处理2.1.1预处理步骤Web网页通常包含有大量的标签信息、脚本元素等噪音内容，如何在数据进行聚类之前把这些数据清洗完毕是一个十分关键的步骤。一般可以分为以下几个步骤： （1）去除HTML标签：javascript等一些脚本元素。（2）去除非字字符：如￥#&。（3）标记标题：在计算词项权重的时候可以作为参考。（4）页面语言识别：对采用那一种分词方法很重要。 下面着重介绍一下中文分词方法。2.1.2 中文分词众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以汉字为单位，词与词之间没有明显的形态界限，要进行汉语的计算机处理，必须首先将汉语的词与词分割开，即分词。句子中所有的字连起来才能描述一个意思。例如，英文句子“It is a stone”，用中文则为：“这是一块石头”。计算机可以很简单通过空格知道“stone”是一个单词，但是不能很容易明白石、头两个字合起来才表示一个词。如果对“这是一块石头”这个句子进行分词，分词的结果是：“这是 一块 石头”。中文分词是其他中文信息处理的基础，自动归类只是中文分词的一个应用。目前采用的分词归纳起来不外乎三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。在本系统的实现过程中，我们使用了基于字符串匹配方法，其容易理解，实现也相对简单。下面仅对该方法做一介绍。基于字符串匹配的方法基于字符串匹配的分词方法，又叫做机械分词方法。它是按照一定的策略将待切分的汉字串与机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别）。按照扫描的方向不同，串匹配分词方法可分为正向匹配分词方法和逆向匹配分词方法；按照优先匹配的长度不同，又可分为最大匹配分词方法和最小匹配分词方法；按照是否与词性标注过程相结合，又可分为单纯分词方法和结合标注分词方法。本系统中，采用正向和逆向结合的双向匹配方法来进行中文分词。2.2向量空间模型（VSM）向量空间模型（Vector Space Model, VSM）是目前信息检索中最常用的文档表示模型。在万维网信息检索方面，向量空间模型比布尔模型等传统模型更适合。这是因为布尔模型是最简单的检索模型，标准的布尔模型是二元逻辑，所检索的页面要么与所键入的关键词组有关，要么无关，检索结果一般不进行相关性排序；而向量空间模型不仅可以方便地产生有效的检索结果，而且能够提供相关页面的文摘，并进行检索结果分类，为用户提供准确的所需信息。基于向量空间模型的信息检索一般过程如下21：（1）将各个文档和查询都表示为向量；（2）计算查询与各个文档之间的相似度；（3）按照查询与各个文档之间的相似度对相关的文档进行排序；（4）将排序后的文档以线性列表的形式返回给用户 在向量空间模型中，各个文本和查询项的内容都表示为向量。设共有个文档，对所有文本进行词语切分、过滤和转换之后，合适的个词项（Term）被提取出来，构造的词项/文档关系矩阵（Term-Document Matrix），矩阵中的元素表示第- 51 -Web搜索结果自动归类系统个词项在第个文档中的权重（Weight）。这样，每个词项就可以用W中对应的行向量来表示。 应用上述方法，文本被表示为一组有代表性的词项（Term，索引项）的集合。通常需要提取待处理文本集合中含有的所有索引项。设索引项的集合，其中表示文本集合中含有的索引项的个数，实际使用中都是随着文本集合的不断变化而增加的。通常都是在预处理以后，只保留文档中最具有明显标志性作用的索引项。对初始文档，其中是文档含有的索引项的数目，经过预处理以后其中，预处理可以很好的减小计算量。向量空间模型通过分配权重给文档中的索引项，将文档表示为权重的向量，其中表示索引项在文档中的权重。的计算采用TFIDF加权策略，具体的计算公式可以表示为： （2-1）其中表示词在文档中出现的次数，表示要处理的文档的个数， 表示含有词的文档个数。这种权重计算方式中的大小与在文档中出现的次数成正比，而与在整个文本集合中出现的次数成反比。此外，对的计算还有许多形式，在此不一一列举。在检索时也需要将查询表示成权重的向量以计算查询与文档的相似度。查询表示为。相似度的计算公式表示为： （2-2）这种相似度计算是通过考察特征向量的余弦夹角实现的。2.3描述优先的聚类算法俗语有云：“物以类聚，人以群分。”聚类就是利用计算机技术来实现这一目的的一种技术，其输入是一组未分类的记录，且事先不知道如何分类，也可能不知道要分成几类，通过分析数据，合理划分记录集合，确定每个记录所属的类别，把相似性大的对象聚集为一个簇。聚类的标准是使簇内相似度尽可能大、簇间相似度尽可能小。聚类属于无监督学习，由于数据密度分布、聚类规则、处理数据量等的多样性，从而产生了许多种聚类算法。聚类算法可以分为划分聚类、层次聚类、密度型聚类、网格型聚类和其他几种聚类算法910。而本系统采用的Lingo算法与上述几种聚类算法有所不同，Lingo算法采取的是描述优先的策略来达到最终标签的可理解性。我们可以通过图2-2很清晰的看出描述优先的聚类算法和传统聚类算法的区别。图2-2 传统聚类（左）和描述优先聚类（右）的比较在本节中，将介绍在信息检索领域，传统的文档聚类算法和描述优先的聚类算法有哪些区别。下面我们主要从需求和文档遍历方式上来进行分析。聚类的一般定义如下：11给定一定数量的对象或个体，并且每个个体都用一定的数学方法来表示，按照一定分类规则，把这些对象分入一定的类内，使得类内的对象尽可能的相似，类间的对象差别尽可能的大。类的数目和各个类的表示需要自行定义。上面的定义没有涉及有关类标签的问题，而其目的只是去发现拥有相似对象的类。如果应用程序需要把聚类的结果呈现给用户，则需要找到合适的文字去描述相应的类，而这个问题在定义中是没有提到的。一个好的算法（根据定义）如果它没法去解释类里面包含的内容，那么对用户来说可能根本没用。所以最核心的问题是如何从发现类聚主题的算法转移到更好的类聚描述的方法。比如，在VSM模型中，想从这个“词袋”模型中构建聚类标签来表示得到的类，似乎不太可能。同时，用关键词或者频繁出现的短语来表示类标签，并不能很好的满足应用程序的需求。 鉴于以上问题，Dweiss在他的博士论文11中提出了一种描述优先的算法。其着重类标签的表达。以下是他的定义：描述优先的聚类算法是一种可以用有意义的，可理解的，精简的文字标签来表示的语义相关的不同的类。根据以上定义，一个描述优先的聚类结果应该有清晰的，可理解的标签描述的类。所以，文档内容聚类是一个起决定性作用的步骤，但并不是我们的最终目标。综上，我们可以放弃那些没有办法用有意义标签来描述的类。可能一开始还感到疑惑，但是在Dweiss的实验中11，可以充分印证这个思想的合理性：（1）如果标签表达不清晰，用户不会花额外的时间来弄明白一个标签的意思。（2）如果标签只是一个单独的关键词，用户将不会查看该类里面的文档。（3）类描述和类内的文档，如果不清晰或者关系模糊，将使用户失去信心。在本系统中采用的Lingo算法13就是一个描述优先的算法，最终聚类标签的可理解性是我们一个十分重要的目标。2.4 Lingo聚类算法本系统实现并使用了Lingo（Label INduction Grouping algOrithm）和STC（Suffix tree clustering）算法。在Lingo算法中应用了标签优先聚类算法的思想，并在文中详细讨论了算法的流程和实现步骤。由于篇幅，这里不介绍STC聚类算法12。本文通过实现这两种算法，构建Web搜索结果自动归类系统，进一步了解聚类搜索引擎的工作原理，以及采用Lingo算法的优势。在Lingo中，需要两个很重要的步骤。一个是用后缀数组提取共现频繁短语，这是提取候选标签的基础。另一个是LSI方法，我们前面介绍了构建VSM的方法，而LSI方法就是基于VSM的，并在计算了TF-IDF权重之后，用SVD（奇异值分解）进行矩阵分解，使矩阵的维数进一步降低，有利于主题的聚类。下面将详细介绍后缀数组和LSI。2.4.1后缀数组（Suffix Arrays）后缀数组的概念定义12定义1： 对于字符串，定义的长度为，第个字符为，第个字符至第个字符组成的子串为。构成字符串的字符集。定义2：的，即的前个字符组成的字符串，如果，则其。定义3： 按所有后缀字符串的排序的后缀数组为，相应的名次数组为13 。后缀数组（suffix array）是字符串处理应用中使用的各种数据结构的基础。表示在字符集上的一个字符串，$ 是唯一的终结符且小于字符集中的任一字符，是在字符串的末尾加上终结符得到的一个新字符串，如果表示字符串的长度，表示S的第个字符，那么是字符串的第个后缀数组。例如：，在其后增加一个结束符，得到，那么，是的第2个后缀数组。2.4.2潜在语义索引（LSI）在Web上对某个特定领域的信息进行采集，首先需要让采集系统了解这个领域的精确描述。通常是给定一个样本文档集合，采用合适的代数模型进行描述。传统的检索模型描述中16，无论布尔模型，向量空间模型（Vector Space Model，VSM) 还是概率模型，尽管实现方法上有很多差异，但对文本的过滤、检索等操作都是通过文档之间的词匹配来实现的。由于词具有同义性，多义性和使用上的概念相关性，仅仅通过字面的匹配不能准确地进行各种功能操作。从1988年开，Dumais等进行了一系列的研究，提出了新的信息检索代数模型，主要是为克服现有的查询词与文档匹配检索技术的缺点而设计的。在VSM基础上，利用线性代数的知识，通过矩阵的奇异值分解(Singular Value Decomposition，SVD) 来进行潜在语义索引，简称为LSI(Latent Semantic Indexing)或者LSA(Latent Semantic Analysis)。LSI通过数学分析，计算出文档集合中潜在内涵的概念之间的关系，通过潜在概念集表示所有的概念空间，减少了概念表示之间的模糊性，避免了VSM中各维之间概念正交的假设。它把观测到词项/文档关联数据的不可靠性看作是一种统计问题，认为在数据中存在一种潜在的语义结构，这种结构由于检索词出现的多样性被干扰。LSI使用统计技术去估计这些潜在的语义结构，去掉这种“噪声”。针对一些TREC文档库的实验结果及一些初步的理论分析，证实了LSI的优越性24。通过特定领域样本文档集LSI矩阵，获得样本集潜在语义的矩阵描述，可以很好地计算文档之间潜在内容的相关性，是目前在信息检索领域最具有前景的发展方向之一。与传统的信息检索代数模型相比，LSI具有如下优点15：(1) 表示的不仅仅是所有标引词的简单出现频度和分布关系，而是所有标引词在样本文档集合中的潜在语义关系，通过对样本文档集合的文档操作，语义精度得到较大的提高。(2) 采用一个低秩近似矩阵替代了词项/文档矩阵，存储计算效率上得到较大的提高。(3) 不仅表示了标引词和文档之间的关系，而且包含了不同词之间的潜在关系，可以表示标引词之间，文档之间，标引词与文档之间，查询伪文本和文档之间的各种相似度，使用上更加灵活。LSI模型的主要问题是从高维映射到低维时如何确定值16，目前还没有理论上合适的方法。一方面希望足够大，能够适合所有的潜在语义结构，但太大会导致噪声，对于LSI使用产生影响;如果太小，则不能适应样本的误差或其他次要的细节，保留下来的结构太少，无法把握运算的结果。实际中，往往需要通过多次的试验，以选取针对具体文档集合操作效率最好的值。对于非常大的文档集，取100300比较适合16。中文文档集合LSI初步测试基本吻合英文的取值范围。2.5小结本章介绍了一系列网页自动聚类技术，其中包含预处理，中文分词，向量空间模型。在介绍聚类算法的同时，着重介绍了描述优先的聚类算法。本系统采用的Lingo聚类算法就采用了描述优先的聚类思想。为了更加直接、简明的了解Lingo聚类算法的运作原理，在本章中我们通过简化文档，描述了Lingo聚类处理的整个流程。下一章，将详细介绍ACS系统的体系结构以及开发该系统所需要的相关技术。第三章 自动归类系统（ACS）框架设计第三章 自动归类系统（ACS）框架设计聚类搜索引擎是搜索引擎的一种，它用关键词从传统的独立搜索引擎中获取搜索结果列表，通过对搜索结果进行聚类处理后，将二次加工后的搜索结果和聚类类目呈现给用户。一般而言，聚类搜索引擎是元搜索引擎，它本身并不对网络文档进行爬行和索引，而只是利用接口向各个独立搜索引擎发出关键字检索请求，对请求得到的搜索结果进行聚类处理。但也有极少数聚类搜索引擎建立有自己的网页索引库，例如 Northern Light 聚类搜索引擎，同样具备有爬行器和网页索引数据库，用户提交关键字搜索时只在自己的索引数据库中进行检索。本系统就是一个聚类搜索引擎，本章主要讲述ACS(Automatic Categorization System)的框架设计，应用的技术以及各个模块的内涵。3.1聚类搜索引擎概述聚类搜索引擎13自动将来自各个搜索引擎的搜索结果，自动组织成各种类(Cluster)，统一呈现给搜索用户。这种聚类技术是实时进行，聚类过程中没有人工干预，因而不同于分类(Classification)和标引(Tagging)。此外，由于聚类搜索引擎将搜索结果分为各个类目，其类名的选取非常重要，它为用户指示了此类的核心内容。类名的选取需要遵循简洁、可理解、准确、唯一性的特点。聚类搜索引擎由于对海量的搜索结果进行了聚类处理，使得搜索结果具有目录式的分类，用户可以方便快捷地找到自己的目标信息，即对应类下的搜索结果，而免去在无数的搜索结果中进行甄别、筛选、过滤等人工辨别。3.2 ACS系统体系结构描述绝大多数聚类搜索引擎属于元搜索引擎，图3-1是聚类搜索引擎的体系结构13，可以看到，其工作原理与元搜索引擎有不少相似之处。聚类结果输出调度中心数据获取模块GoogleYahoo!MSN百度独立搜索引擎搜索结果重排序聚类分析搜索引擎用户界面 图3-1聚类搜索引擎的体系结构3.2.1搜索引擎用户界面该模块负责与用户进行交互，它接收用户的查询请求，以及用户检索偏好，例如选择的独立搜索引擎对象，返回的搜索结果数量等。同时，该模块还将聚类处理后的最终结果以统一的格式返回给用户。3.2.2调度中心调度中心是聚类搜索引擎一个核心的调度模块，负责接受用户的检索请求传递到数据获取模块，并将其返回的数据处理后，传递给搜索结果重排序模块。在本系统中，在原有Carrot22提供的控制接口上，实现了整个处理流程的控制，并成功的组织调用相关组件，保证数据流的通畅。3.2.3数据获取模块数据获取模块负责与各个独立搜索引擎的交互，包括多个搜索引擎的接口代理，它们把用户的查询转换成对应搜索引擎能够辨识的格式分别发送，并负责解析对应搜索引擎返回的搜索结果，并将解析过的搜索结果传递给调度中心。数据获取模块往往采用多线程(Multithreading)的方式作并行地在各个独立搜索引擎中进行搜索，并行地调用多个搜索引擎。并且对于每个独立搜索引擎，数据获取模块通过多个线程并行地取回其搜索结果网页。只有这样采用并行线程，才能更快地获取足够多的搜索结果。在本系统中，我们只实现了从Yahoo搜索引擎获取数据，关于对其他搜索引擎数据的获取，将在以后的改进阶段实现。3.2.4搜索结果重排序模块搜索结果重排序模块负责对数据获取模块传递过来的各个搜索结果列表，进行网页去重和搜索结果重排序。由于本系统如今只实现了从Yahoo接口获取数据，故并没有涉及结果重排序模块，若以后从多个搜索引擎获取结果，则需在系统中加入此步骤。下面对重排序做一简单介绍：对于相同的搜索关键字，不同搜索引擎的返回结果均不相同，并且彼此的搜索结果中会有重复之处。搜索结果重排序模块需要把来自各个搜索引擎的搜索结果列表综合起来，去重后，重新排序形成一个统一的搜索结果列表。一种简单有效的重排序算法是最高位置算法(Highest-Rank Algorithm) 21，下面简要描述这一算法。对各个独立搜索引擎返回的每一项搜索结果进行检查，以它在各个搜索引擎返回的搜索结果列表中出现的最高位置作为它的序号，并删除它在其它位置的出现，直到各个搜索结果列表都没有重复的搜索结果为止，然后将所有的搜索结果按照其序号顺序排列成为一个统一的列表。对于相同序号的搜索结果，可以根据其最高位置所在的搜索引擎的优劣质量顺序排序18。3.2.5聚类分析模块在这个模块中，聚类搜索引擎要完成数据清理和聚类处理处理过程。（1）数据清理：各个搜索引擎的搜索结果中一般包括相关页面的标题、摘要和目标URL地址。数据清理过程便是将搜索结果页面的各部分内容进行清理，合并成一个文档内容，来表示搜索结果页面内容。在这个过程中，聚类处理模块对搜索引擎返回的搜索结果网页进行解析，去除其中的HTML标签，并以标点符号、空格等为边界把网页切分成多个较短的字符串。然后用中文分词处理将之表示成一个短语序列，为关键词组提取作好准备。（2）聚类分析：接下来，对所有的搜索结果文档(短语序列)，使用Lingo聚类算法13进行处理。在数据预处理之后，我们先提取网页中的候选标签，这需要使用到后缀数组。然后通过潜在语义索引(LSI)，分解矩阵，确立网页的主题分类。最后通过选取合适的标签，并把文档重新归类到相应的标签底下。这样就完成了聚类分析过程。对文档完成聚类后，再对生成的聚类类目进行排序，一般对聚类类目的排序采用最大类别优先的策略，即按照包含的结果文档数从大到小排序。下面对ACS系统采用的聚类算法Lingo进行详细描述：Lingo算法的大致流程如图3-2所示13。图3-2 Lingo算法的流程在ACS系统中，Lingo是默认的聚类算法。所以这里用一个小例子来解释一下Lingo是如何运作的。图3-3 词项/文档矩阵文档矩阵如图3-3左所示，是一个以词项为行向量，文档为列向量的一个矩阵。为了建立VSM模型，我们需要建立一个词项/文档矩阵：一个包含所有出现在输入文档中词项频度的矩阵。假设，如果只有2个词项，词项和词项。这样就可以方便的把VSM模型可视化为二维平面。平面的每一个点代表一个文档。图3-4 词项/文档矩阵矩阵分解的任务是通常把一个矩阵分解为两个矩阵，而这两个矩阵的叉积尽可能的与原始矩阵相似，并且具有更低的维数。其中，左矩阵可以看作是低维空间的基向量，而另一个矩阵可以看作是我们重建原始矩阵的一个系数。在图3-4中，基向量大致刻画了输入集合中的主要走势。图3-5 候选标签选取在图3-5中，请注意，频繁短语和基向量都表示在同一个向量空间中（输入文档矩阵）。所以这里可以通过余弦值找到适合每个基向量的最相似的频繁短语。这样，每个基向量都将找到一个聚簇标签。图3-6 聚簇标签的选定和内容聚类为了形成合适的聚簇，我们可以再次通过利用余弦值相似度方法，把大于一定值的文档赋给合适的标签即可，如图3-6所示。到此为止，聚类已经成功完成，只要组织输出即可。3.2.6聚类结果输出模块该模块将经过聚类处理的各搜索结果网页，以聚类搜索引擎本身采用的统一格式进行处理。一般独立搜索引擎的搜索结果中，都包括对目标网页的标题描述、网页摘要、URL目标地址、网页获取时间等。这一模块分析各个独立搜索引擎结果的格式，对其内容进行处理，统一表述成自己的搜索结果显示方式。此外，此模块还可以在格式化后的搜索结果中，加入有自身特色的数据。例如结果数据的搜索引擎来源，在不同搜索引擎中的排列序号等等。在本系统中，还可以查看每个网页文档属于的类。3.3系统开发工具和运行环境（1）开发工具：Eclipse + Tomcat（2）版本管理工具： CVS（3）测试工具： JUnit （4）基于平台： Windows（5）相关资源：Yahoo API,Log4j日志工具，缓存管理工具Ehcache等3.4 小结本章详细介绍了Web搜索结果自动归类系统的整个框架设计，并把系统分为六大部分，分别是搜索引擎用户界面，调度中心，数据获取模块，搜索结果重排序模块，聚类处理模块和聚类结果输出模块。其中由于现在我们只从单一的搜索引擎抓取数据（Yahoo），所以在实际的开发过程中，搜索结果重排序模块并没有使用到。Web搜索结果自动归类系统第四章 ACS系统开发与测试ACS(Automatic Categorization System)系统的设计目标是设计在线的，根据内容分类的，更好地满足用户需要的中文网页自动归类系统。在线是指即时响应用户的聚类要求，迅速提供最新的聚类结果。根据内容分类的，指聚类的结果是经过分门别类之后，展现给用户的。类与类之间应该允许重叠，即若信息涉及多个类的主题则可以属于多个类，并且采用树的组织形式，树中每个结点都对应一个类。下面通过介绍系统的设计、开发、测试来了解ACS系统的实现过程。4.1 ACS系统设计概述 图4-1 ACS系统查询界面本系统的设计本着为用户着想的目的，为用户提供一个输入查询词的界面，如图4-1所示，并且可以选择从搜索引擎获取多少数据量(现在备选的有50，100，200，400，默认100)，还可以根据爱好，选择相应的算法(现在实现的有Lingo和STC，默认为Lingo)。聚类后的结果用目录结构展现给用户，如图4-2所示，用户可以方便的选择相应的主题目录进行浏览。 图4-2 聚类结果输出界面 下面7点是我们系统开发的范围和目标：(1) Web搜索引擎返回的页面是动态的，其文档类别是未知的、不固定的。这也是通用搜索引擎的一个特性，我们针对这个情况采取相应的办法，使得文档最终可以分 类后展现给用户。(2) 根据页面内容自身的差异，使用文档聚类