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

毕业论文第1.绪论 11.1研究背景 11.2研究概况 21.3本文结构 32.搜索引擎概述 52.1搜索引擎的组成 52.1.1Robot 52.1.2分析器 62.1.3索引器 62.1.4检索器 62.1.5用户接口 72.2搜索引擎工作流程 72.3搜索引擎分类 82.3.1全文搜索引擎 82.3.2目录索引搜索引擎 92.3.3垂直搜索引擎 102.3.4元搜索引擎 113.聚类研究 133.1文档自动分类 133.2聚类分析 133.3基本聚类方法 143.3.1平面划分方法 143.3.2层次凝聚方法 163.4网页聚类算法 193.4.1基于网页内容的聚类算法 193.4.2基于链接分析的聚类算法 203.4.3基于用户搜索日志的聚类算法 214.聚类搜索引擎设计 234.1数据源预处理 234.2索引的建立 244.3相似度计算 284.4聚类处理 295.性能分析 355.1理论分析 355.2系统演示 36总结 39致谢 41参考文献 431.绪论1.1研究背景万维网(WorldWideWeb,简称WWW或Web)是为广大用户交换或共享信息而发展起来的一种因特网(Internet)应用，从1991年出现以来，经过短短十几年已经发展成为一个巨大的全球化信息空间。面对这一庞大的信息资源，用户迫切需要一个强有力的检索系统快速有效地检索Web信息，以使从浩如烟海的信息中找到自己所需的信息。搜索引擎是Web信息检索服务的一种形式，从1993年年底第一个搜索引擎WWWW(WorldWideWebWorm)在Colorado大学开发成功以来，经过发展，因特网上的搜索引擎己经达到上千个，而包括搜索引擎在内的信息检索也已成为仅次于电子邮件的第二大网络应用。根据CNNIC最新的统计报告数据显示，我国近70%万的网民经常使用搜索引擎。由于搜索引擎本身具有极大的商业价值，所以以盈利为目的搜索引擎服务提供商在这个领域争相投入大量的资源进行研究。而除了通用搜索引擎之外，细分搜索公司的增多，也验证了搜索市场生态的繁荣，并为搜索引擎的进一步发展找到了新出路，比如：大量垂直搜索的涌出。垂直搜索的用户特定性，可以有针对各个行业的垂直搜索引擎，有很大的发展空间。首先，因为垂直搜索对数据源进行了更详细的划分和更人性化、智能化的操作，比如自动分类、自动聚类、个性化专题等，并将其通过简单易用、搜索结果精确分类等方式表现出来，并可采用按效果付费的广告模式HYPERLINK[1]，这就超越了传统搜索广告点击付费的单一广告方式。其次，垂直搜索能够提供更为集中的受众群体，其中大部分是潜在消费者或产品使用者，从而提高搜索引擎广告受众的精确度，这是一般的通用搜索做不到的。虽然搜索引擎的系统种类繁多，功能服务特点各异，但是在这个领域仍然有很多的问题亟待解决：首先，尽管现有的搜索引擎采用了多种方法来提高检索结果的精度，用户从搜索引擎搜索到的结果中仍然存在大量无效信息。有统计标明，对现有的20个流行的搜索引擎的前200个返回结果进行的2000次检索测试和统计，其搜索结果中用户根本无法连通的链接约占30%，重复内容约占12%，与用户需求不相关的内容约占8%，与用户需求相关但不完全符合用户需求的约占36%，而完全符合用户需求的仅占14%，搜索引擎虽然经过了相关度排序，然而相关文档和不相关文档相互混杂，用户必须逐个浏览结果列表以找到相关文档，花费了大量的精力，当返回的结果数目众多时，这个问题更为突出，即使搜索引擎找到了用户所期望的结果，无法快速地定位自己所需资源，甚至有许多属于同一类型、同一方面的无效信息返回，这些问题致使一些搜索引擎的检索质量大大降低，成为了今天搜索引擎迫切需要解决的问题之一。1.2研究概况搜索引擎发展到今天,无论从产业角度还是从产品角度来看,都成为计算机领域的一个重要研究方向，创造了一个又一个互联网亮点。众多搜索引擎有着不同的信息搜集方法和服务提供方式，如：Baidu、Google所采用的全文检索搜索引擎；Yahoo、LookSmart所采用的目录式搜索引擎；以及LookSmart、WebCrawler所采用的元搜索引擎。其中Google以搜索精度高、速度快成为最受欢迎的搜索引擎。互联网的普及，使用搜索引擎的用户多样化，覆盖各个行业领域，各个年龄阶段，其需求也呈现多样化。大多数搜索引擎目前仍然采用通用式的搜索方式，即针对同一关键词进行的查询，搜索引擎会对不同用户给出相同结果。这种模式以网页的加权评价为核心，而并非以用户为核心，并不能满足不同用户的不同需求。针对某一特定行业的专业搜索，即垂直搜索的出现在一定程度上填补了这一需求缺口，但其覆盖范围有限，搜索信息有限，用户群体有限。现在大多数的搜索引擎以搜索文字信息为主，随着网络带宽的不断加大，多媒体信息在网上迅速增加，这就对多媒体信息的检索提出了要求。多媒体信息检索主要是指基于音频的检索、基于图片的静态图像检索和基于视颖的动态图像检索，现在研究得较多的是图像检索。然而这些搜索引擎还存在很大局限性，并不能完全解决互联网信息检索的问题。搜索引擎不能搜索整个互联网、正确率非常低、召回率(返回的相关文档占所有相关文档的比率)和准确率(返回的相关文档占返回的所有文档的比率)都非常低。搜索引擎面对的挑战主要表现在以下几个方面：1.网络资源的发展，使得搜索引擎能够检索的范围越来越小；2.互联网是一个动态增长的信息源，随时会发生各种变化，搜索引擎不能及时反映这种变化；3.对于用户来说，用户检索到的结果与用户所需要的信息相比，用户检索到的有用信息经常淹没在众多的无用信息当中HYPERLINK[2]。为了缓解上述问题，各大搜索引擎开发商不断采用更好的技术，提高产品性能；其中，Robot(机器人)技术是国内外关于搜索引擎采用的较好技术之一，即由一种叫“蜘蛛”的计算机程序在网络中爬行，并发现、加工、整理信息，为用户提供检索服务；部分中文搜索采用目录式搜索引擎（DirectorySearchEngine），即通过人工发现信息并依靠编目员的知识进行分类；前者获得的信息量较大，耗费资源较少，后者精确度较高。而元搜索引擎没有自己的数据，是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户；其服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛选。近年来，聚类技术也在搜索引擎中逐渐运用。在搜索引擎结果的聚类研究中，聚类实现技术大致可分为两种：一种是事先聚类，检索前预先对文档集进行聚类。由于这一聚类处理的文档集巨大，所以对计算资源要求较高，多为脱机处理。另一种是事后聚类，对检索结果进行聚类。由于事后聚类处理的文档集较小，所以可实现联机处理。Web信息资源是时刻动态增加变化的，提前将文档进行聚类分类，不能满足信息及时更新的需求，且处理的文档集巨大对计算资源要求较高，代价较大，所以将检索结果进行聚类的技术更加能够满足Web信息灵活多变的需要。从老牌聚类搜索引擎Vivisimo，到2003年刚刚问世的，十分被人们看好的聚类搜索引擎Mooter，国外聚类搜索引擎正在蓬勃发展；当前国内也出现了比比猫等优秀的中文聚类搜索引擎，可见将聚类技术应用于搜索引擎是大势所趋。1.3本文结构本文的研究目标是希望通过有效的聚类分析，对现有的搜索引擎进行优化，将大规模中文网页集合进行层次结构的聚集和管理，便于浏览检索和进一步分析，使用户可以更快定位自己所需结果集，缩小选择范围，提高用户搜索效率。本文结构如下：第一章绪论简单介绍了当前搜索引擎的发展状况及趋势；第二章搜索引擎概述对几种主要的搜索引擎的工作流程及原理进行了介绍；第三章聚类研究详细阐述了主要的聚类算法及设计中所用到的思想；第四章聚类搜索引擎设计 详细阐述了本文聚类搜索引擎的整体设计；第五章性能分析对本聚类搜索引擎的性能展开分析；最后总结全文，概述本文的主要工作及价值，并分析了相关不足和以后的研究方向。搜索引擎概述2.1搜索引擎的组成自从第一个搜索引擎WWWW(WorldWideWebWorm)在Colorado大学开发成功以来，Web上的搜索引擎己经发展到上千个，虽然各个搜索引擎，包括各全文搜索引擎、目录索引搜索引擎、垂直搜索引擎在内的大部分搜索引擎，具体实现不尽相同，但一般包含5个基本部分：Robot、分析器、索引器、检索器和用户接口，各部分的相关技术介绍如下HYPERLINK[3]。图2-1搜索引擎的基本组成2.1.1Robot采用一定的搜索策略对Web进行遍历并下载文档，系统中维护一个超链队列，或者堆栈，其中包含一些起始URL。Robot从这些URL出发，下载相应的页面，并从中抽取出新的超链加入到队列或者堆栈中，上述过程不断重复队列直到堆栈为空。为了提高效率，搜索引擎中可能会有多个Robot进程同时遍历不同的Web子空间；为了便于将来扩展服务，Robot应能改变搜索范围。Robot一般采用以宽度优先搜索策略为主、线性搜索策略为辅的搜索策略HYPERLINK[4]。线性搜索策略：这是最简单的搜索方法，它的基本思想是沿着一个起始的IP地址，按IP地址递增的方式搜索后续的每一个WWW地址中的HTML文件，完全不考虑各站点的HTML文件中指向其他Web站点的超链接地址。此策略不适用于大规模的搜索（主要原因在于IP可能是动态的），但可以用于小范围的全面搜索，利用此种策略Robot可以发现被引用较少或者还没有被其他HTML文件引用的新HTML文件信息源。深度优先搜索：这是在开发Robot的早期使用较多的一种方法，它的目的是要达到被搜索结构的叶结点。深度优先搜索顺着HTML文件上的超链接走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链接。当不再有其他超链接可选择时，说明搜索已经结束。深度优先搜索适宜遍历一个指定的站点或者深层嵌套的HTML文件集，但对于大规模的搜索，由于Web结构相当深，也许就再也出不来了。宽度优先搜索策略：该搜索策略执行时先搜索一层中的内容，然后再继续搜索下一层。如一个HTML文件中有三个超链接，选择其中之一并处理相应的HTML文件，然后返回并选择刚才第一个网页的第二个超链接，处理相应的HTML文件，再返回。一旦一层上的所有超链接都已被选择过，就可以开始在刚才处理过的HTML文件中搜索其余的超链接。该搜索策略保证了对浅层的首先处理，当遇到一个无穷尽的深层分支时，也就不会再陷进去；且容易实现，具备大多数期望的功能，但是需要花费比较长的时间才能到达深层的HTML文件。2.1.2分析器对Robot下载的文档进行分析以用于索引，文档分析技术一般包括：分词、过滤和转换。这些技术往往与具体的语言以及系统的索引模型密切相关。2.1.3索引器将文档表示为一种便于检索的方式并存储在索引数据库中。索引的质量是Web信息检索系统成功的关键因素之一。一个好的索引模型应该易于实现和维护，检索速度快，空间需求低。搜索引擎普遍借鉴了传统信息检索中的索引模型，包括倒排文档、矢量空间模型、概率模型等。例如在矢量空间索引模型中，每个文档d都表示为一个范化矢量ti为词条项，wi(d)为ti在d中的权值，一般被定义为ti在d中出现频率tfi(d)的函数。2.1.4检索器从索引中找出与用户查询请求相关的文档，采用与分析索引文档相识的方法来处理用户查询请求。如在矢量空间索引模型中，用户查询q也被表示为一个范化矢量。然后按照某种方法来计算用户查询与索引数据库中每个文档之间的相关度，例如在矢量空间索引模型中，相关度可以表示为查询矢量与文档矢量之间的夹角余弦。最后将相关度大于阀值的所有文档按照相关度递减的顺序排列并返还给用户，当然搜索引擎的相关度判断并不一定与所有用户的需求完全吻合HYPERLINK[5]。2.1.5用户接口该部分为用户提供可视化的查询输入和结果输出界面。在查询界面中，用户按照搜索引擎的查询语法制定待检索词条及各种简单、高级检索条件。在输出界面中，现有大部分搜索引擎将检索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要和超链等信息；检索结果中相关文档和不相关文档相互混杂，用户需要逐个浏览以找出所需文档。这也正是本课题所要解决的问题。Web信息是动态变化的，因此Robot、分析器和索引器模块要定期更新数据库，时间视具体搜索引擎实现不同而有所差异，索引数据库越大，更新也越困难HYPERLINK[6]。2.2搜索引擎工作流程包括全文搜索引擎、目录索引搜索引擎、垂直搜索引擎在内的大部分搜索引擎的工作可以分为如下三步：从互联网上抓取网页→建立索引数据库→在索引数据库中搜索排序。（1）从互联网上抓取网页：利用能够从互联网上自动收集网页的Spider系统程序，自动访问互联网，并沿着任何网页中的所有URL爬到其它网页，重复这过程，并把爬过的所有网页收集回来。（2）建立索引数据库：由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息（包括网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其它网页的链接关系等），根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面内容及超链接中每一个关键词的相关度，然后用这些相关信息建立网页索引数据库。（3）在索引数据库中搜索排序：当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。由于所有相关网页针对该关键词的相关度早已算好，所以只需按照现成的相关度数值排序，相关度越高，排名越靠前。最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。搜索引擎的Spider一般要定期重新访问所有网页（各搜索引擎的周期不同，可能是几天、几周或几月，也可能对不同重要性的网页有不同的更新频率），更新网页索引数据库，以反映出网页内容的更新情况，增加新的网页信息，去除死链接，并根据网页内容和链接关系的变化重新排序。这样，网页的具体内容和变化情况就会反映到用户查询的结果中HYPERLINK[7]。2.3搜索引擎分类搜索引擎按其工作方式主要可分为四种，分别是全文搜索引擎(FullTextSearchEngine)、目录索引类搜索引擎(SearchIndex/Directory)、元搜索引擎(MetaSearchEngine)和垂直搜索引擎(VerticalSearchEngine)HYPERLINK[8]。2.3.1全文搜索引擎全文搜索引擎是从网站提取信息并建立网页数据库。搜索引擎的自动信息搜集功能分两种。一种是定期搜索，即每隔一段时间（比如Google一般是28天），搜索引擎主动派出Spider(“蜘蛛”程序)，对一定IP地址范围内的互联网站进行搜索，一旦发现新的网站，它会自动提取网站的信息和网址加入自己的数据库。另一种是提交网站搜索，即网站拥有者主动向搜索引擎提交网址，它在一定时间内（2天到数月不等）定向向网站派出“蜘蛛”程序，扫描网站并将有关信息存入数据库，以备用户查询。由于近年来搜索引擎索引规则发生了很大变化，主动提交网址并不保证所提交网站能进入搜索引擎数据库。当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到与用户要求内容相符的网站，便采用特殊的算法（通常根据网页中关键词的匹配程度，出现的位置／频次，链接质量等）计算出各网页的相关度及排名等级，然后根据关联度高低，按顺序将这些网页链接返回给用户。在全文搜索引擎中，google和百度是当前国内用户数较多的搜索引擎产品。Google（/）成立于1997年，几年间迅速发展成为世界范围内规模最大的搜索引擎。Google数据库现存有42.8亿个Web文件，每天处理的搜索请求已达2亿次，而且这一数字还在不断增长HYPERLINK[9]。Google借用Dmoz（/）的分类目录提供“网页目录”查询（/dirhp?hl=zh-CN&tab=wd&ie=UTF-8&oe=UTF-8&q=），但默认网站排列顺序并非按照字母顺序，而是根据网站PageRank的分值高低排列。百度（/）是国内最早的商业化（早期为其它门户网站提供搜索服务，现在的竞价排名更为其带来高效回报）全文搜索引擎，拥有自己的网络机器人和索引数据库，专注于中文的搜索引擎市场，除有网页搜索外，百度还有专门针对新闻、MP3、图片等搜索，并成功推出了“贴吧”、“百科”、“知道”等功能。2.3.2目录索引搜索引擎与全文搜索引擎相比，目录索引有许多不同之处。首先，搜索引擎属于自动网站搜索，而目录索引则更加依赖手工操作。用户提交网站后，目录编辑人员会亲自浏览你的网站，然后根据一套自定的评判标准甚至编辑人员的主观印象，决定是否接纳你的网站。其次，搜索引擎收录网站时，只要网站本身没有违反有关的规则，一般都能登录成功。而目录索引对网站的要求则高得多，有时即使登录多次也不一定成功。尤其象Yahoo！这样的超级索引，登录更是困难。此外，在登录搜索引擎时，我们一般不用考虑网站的分类问题，而登录目录索引时则必须将网站放在一个最合适的目录(Directory)。最后，搜索引擎中各网站的有关信息都是从用户网页中自动提取的，所以从用户的角度看，我们拥有更多的自主权；而目录索引则要求必须手工另外填写网站信息，而且还有各种各样的限制。更有甚者，如果工作人员认为你提交网站的目录、网站信息不合适，他可以随时对其进行调整。目录索引，顾名思义就是将网站分门别类地存放在相应的目录中，因此用户在查询信息时，可选择关键词搜索，也可按分类目录逐层查找。如以关键词搜索，返回的结果跟搜索引擎一样，也是根据信息关联程度排列网站，只不过其中人为因素要多一些。如果按分层目录查找，某一目录中网站的排名则是由标题字母的先后顺序决定(也有例外)。目前，全文搜索引擎与目录索引有相互融合渗透的趋势。原来一些纯粹的全文搜索引擎现在也提供目录搜索，如Google就借用OpenDirectory目录提供分类查询。而象Yahoo！这些老牌目录索引则通过与Google等搜索引擎合作扩大搜索范围。在默认搜索模式下，一些目录类搜索引擎首先返回的是自己目录中匹配的网站，如国内搜狐、新浪、网易等；而另外一些则默认的是网页搜索，如Yahoo！(Yahoo！已于2004年2月正式推出自己的全文搜索引擎，并结束了与Google的合作)。在当前目录索引搜索引擎中，雅虎、新浪及网易较为公众所熟知。雅虎中国分类目录（/）是最早的分类目录，现有14个主类目，包括“商业与经济”、“艺术与人文”等，可以逐层进入进行检索，也可以利用关键词对“分类网站”进行搜索（http://m6.search.cnb.yahoo.com/dirsrch/）。此外，雅虎中国也可以对“所有网站”进行关键词搜索（http:///websrch/），早期，他的搜索结果使用Google的数据，2004年2月正式推出自己的全文搜索引擎，并结束了与Google的合作。搜狐分类目录（http://dir.sohu.com/）把网站作为收录对象，具体的方法就是将每个网站首页的URL地址提供给搜索用户，并且将网站的题名和整个网站的内容简单描述一下，但是并不揭示网站中每个网页的信息内容。除此之外，也可以使用关键词对搜狐的“分类目录”或所有网站进行搜索。2.3.3垂直搜索引擎垂直搜索引擎是相对通用搜索引擎信息量大、查询不准确、深度不够等提出的新的搜索引擎服务模式。它通过针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务，是搜索引擎的细分和延伸，其特点就是“专精深”，且具有行业色彩，相比较通用搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具体和深入。垂直搜索引擎是对网页库中的某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后再以某种形式返回给用户。垂直搜索引擎和普通的网页搜索引擎的最大区别是对网页信息进行了结构化信息抽取，也就是将网页的非结构化数据抽取成特定的结构化信息数据，好比网页搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位，而垂直搜索是以结构化数据为最小单位，然后将这些数据存储到数据库，进行进一步的加工处理，如：去重、分类等，最后分词、索引再以搜索的方式满足用户的需求。垂直搜索引擎的三个特点：（1）垂直搜索引擎抓取的数据来源于垂直搜索引擎关注的行业站点；（2）垂直搜索引擎抓取的数据倾向于结构化数据和元数据；（3）垂直搜索引擎的搜索行为是基于结构化数据和元数据的结构化搜索。垂直搜索引擎的应用方向很多，比如企业库搜索、供求信息搜索、购物搜索、房产搜索、人才搜索、地图搜索、mp3搜索、图片搜索。几乎各行各业各类信息都可以进一步细化成各类的垂直搜索引擎。2.3.4元搜索引擎目前，虽然各个商家的搜索引擎为了在竞争中获胜而不断地增加其索引的Web页面数目，但是却跟不上Web的发展速度，任何一个搜索引擎对Web的覆盖度都相当有限，不超过30％。因此，用户经常需要检索多个系统以提高检索的召回率(Recall)。但是，每个搜索引擎的用户接口是异构的，有其特定且复杂的界面和查询语法，这给用户同时使用多个系统带来了不便，针对这些情况，出现了元搜索引擎。元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返回给用户。元搜索引擎将多个独立的搜索引擎集成在一起，提供统一的界面，试图通过实现现有数据库的综合利用来提高搜索引擎的性能。元搜索引擎是建立在多个独立搜索引擎之上的一种搜索引擎．它自己并不收集网站或网页信息，通常也没有自己的资源库和Robot，其结果来源于它所管理的独立搜索引擎。当用户向元搜索引擎发出查询请求时，元搜索引擎即根据该请求向多个独立搜索引擎发出实际查询请求，然后将所有来自独立搜索引擎的查询结果处理后返回给用户。其结构示意图如下图2-2元搜索引擎结构示意图元搜索引擎的基本设计思想及工作流程可以总结如下：(1)对用户查询请求进行处理，分别将其转换为若干个底层搜索引擎能处理的格式；(2)向各个搜索引擎发送查询请求，并等待其返回检索结果。例如：MetaCrawler同时检索Yahoo、LookSmart、AltaVista等3个主要的搜索引擎；(3)对检索结果进行后处理，包括:组合各个搜索引擎返回的检索结果，消除重复项，对结果进行排序等。有些搜索引擎在必要时还通过下载Web文档来实现一些搜索引擎不支持的查询，或者对文档作进一步的分析以提高信息检索的精度；(4)向用户返回经过组合和处理后的检索结果。上述思想虽然简单，但是效果却比较明显，对于设计人员而言，不需要建立和维护庞大的索引数据库，也不需要使用复杂的检索机制，对于用户而言，元搜索引擎提供了一个能够同时查询多个搜索引擎的集成界面，它将各个搜索引擎的位置、接口等细节都屏蔽了起来，与此同时元搜索引擎还提高了检索的召回率和精度。著名的元搜索引擎有InfoSpace()、Dogpile(http://www.dogpile.com)、Vivisimo()等。而中文元搜索引擎中具有代表性的有比比猫（http://）等。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。聚类研究3.1文档自动分类搜索引擎可对因特网上海量杂乱无章的信息进行索引，帮助人们找到想要的信息。为了快速、准确地从Web上找到人们所需的信息，对网页文档进行聚类分析是非常重要的。在搜索引擎上，聚类分析可用于对搜索引擎中的Robot抓到的网页进行聚类分析，自动生成便于用户查询的网页聚类系统。聚类分析还可用于对用户查询的结果进行处理，以一种超链接的层次方式提交给用户，提高查询的查全率和查准率HYPERLINK[10]。在设计搜索引擎时，聚类技术对创建索引的结构化和检索的优化，对大量网页有效寻找和自动分类的组织方法是很重要。目前，多数搜索引擎对搜索结果的组织方法基本一致，即将搜索结果按照一定规则(相关度、Pagerank等)排列，以列表的方式呈现给用户。这种方式存在一些缺陷，如：搜索结果动辄成千上万，用户无法一一查看，而真正符合用户需要的搜索结果很有可能因为排位靠后而被错过了，因为Pagerank等排序方法只能保证排在前面的搜索结果是最权威的，而不一定是最符合用户需要的；从另一个方面来说，这也是对搜索引擎资源的一种浪费，因为返回结果中只有很少的部分得到了用户的有效利用。因此，在排序的基础上，进一步组织和控制搜索结果，是提高搜索结果质量的有效途径之一。在搜索引擎中应用聚类技术，可以有效地组织和控制搜索引擎的搜索结果。经过聚类处理的搜索结果以类目的形式呈现，内容相似的搜索结果被划分为一个类目，类目之间又具有包含关系，这样，搜索结果就被有效地组织起来，用户可以快速地了解搜索结果的整体分布情况，并快速定位自己需要的搜索结果。3.2聚类分析聚类分析是根据数据项和聚类之间的关联计算来安排数据项自动分类的多变化分析技巧，用来产生数据集的目录结构。聚类的最终目的是达到同一个聚类中的成员有较高的关联度，不同聚类中的成员有较低的关联度的效果HYPERLINK[11]，其中关联计算可以用相似度、相异度和欧几里德距离等进行度量。聚类分析方法有两种类型：一类是非分层聚类方法，把N个数据项的数据集分成M个类，常用的有单遍方法和重新分配方法；另一类是分层聚类，在一对数据项里或成功链接的类里产生一个嵌套数据集，常用的有单链路方法、完全链路方法、组平均链路方法和Ward方法HYPERLINK[12]。聚类分析在文档上的实现有以下几种方法：(1)文档根据它们所包含的索引词来聚类。方法的目的是提供有效的和高效率的检索；(2)索引词可以根据联合发生的文档来聚类。这种方法可以改进词典的结构或者是加强查询；(3)文档也可根据联合发生的引用来聚类。这个方法可以提供进入某个信息领域的途径HYPERLINK[13]。3.3基本聚类方法聚类法是根据所生成的簇类结构来分类的。大体上，主要的聚类法可分为平面划分方法(Partitioningmethod)、层次凝聚方法(Hierarchicalmethod),基于密度的方法(Density-basedmethod),基于网格的方法(Grid-basedmethod)和基于模型的方法(Model-basedmethod)。由于这些方法有不同的理论和实践基础，每种方法又有多种具体实现算法，可以产生不同的聚类结构，聚类方法的选择将决定查询的结果和效果。聚类的方法决定了聚类的结果，而具体的实现算法决定了聚类过程的有效性。随着聚类技术的不断发展和计算机技术的发展，处理海量数据集的新的聚类方法也在不断出现HYPERLINK[14]。3.3.1平面划分方法平面划分法主要应用于早期的文档聚类，比如在SMART项目中的聚类试验。由于早期计算资源有限，平面划分法比起层次凝聚类方法在时间和空间需求上相对比较低，所以在信息检索系统中的应用重点在于最佳匹配的有效性上。平面划分法的主要思想是将文档集分割为若干簇类，这类算法包括K-Means和Singlepass。Singlepass的方法属于加入法，其具体过程如下：首先将文档集D中的第一个文档作为一个簇类，计算与簇类的相似度，如果相似度超过某一阀值，就将加入到簇类中，否则另外建立一个包含的簇类；以此类推，将剩余的文档归入与它最相近的簇类中，或者另建新簇类。该方法的优点在于遍历一次各文档，就可以形成各簇类。缺点是它与文档顺序有关，不同的文档顺序，聚类结果出入很大，而且也容易形成较大的簇类，但它仍然是最受欢迎的增量式聚类方法。K-Means属于调整法，主要思路是:给定要构建的划分数目,先创建一个初始化分。然后采用一种迭代的重定位技术，尝试通过再划分移动来改进划分，具体过程如下：(1)确定要生成的聚类的数目；(2)按照某种原则生成个聚类中心作为聚类的种子；(3)对中的每一个文档，依次计算它与各个种子的相似度；(4)选取具有最大的相似度的种子,将归入以为聚类中心的中，从而得到一个聚类结果；(5)然后重新计算个聚类的中心点或者是平均值，再以中心点或者平均值作为种子，重复步骤3-4若干次，直到聚类结果不再发生变化，或者直到准则函数收敛。通常，采用平方误差准则，其定义如下:这里的E是数据集中所有对象的平方误差的总和，p是空何中的点，表示给定的数据对象，mi是簇类ci平均值(p和mi都是多维的)。这个准则试图使生成的结果聚类尽可能地紧凑和独立。这个算法尝试找出使平方误差函数值最小的个划分。当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。但聚类前要求用户必须给出(要生成的簇类的数目)也算是该算法的一个缺点，且它不适合于发现非凸面形状的簇，或者大小差别很大的簇，另外由于不同的个种子的选择会导致不同的聚类结果，所以这种算法具有很大的不确定性。生成个簇类种子的方法有以下几种：前元法直接取前个文档作为初始凝聚点，或者称做种子点（中心点）；经验法凭经验确定文档集合为几类，对每一类指定一个代表点，其中代表点有多种确定方法；随机法首先确定将文档集合分为几类，然后将每个文档随机地分配给每一类，计算每一类的均值作为初始凝聚点；或者直接随机指定几个文档点作为初始凝聚点；密度法先人为给定两个数()，对每一个文档统计和它相距不超过的文档数目，并称为它的密度。将文档按照密度由大到小排列，首先将密度最大的文档加入到凝聚点集中，然后考虑密度次大的文档，如果该文档到现有的任一凝聚点的距离都大于，则将该文档加入到一个凝聚点集合HYPERLINK[15]。其它平面划分方法的变形如：CLARA，不考虑整个数据集合，选择实际数据的一小部分作为数据的样本，然后用PAM(PartitioningaroundMedoid，围绕中心点划分)方法从样本中选择中心点。CLARA抽取数据集合的多个样本，对每个样本应用PAM算法，返回最好的聚类结果作为输出。平面划分方法不需要提前计算相似性矩阵；但平面划分法依赖于输入文档的顺序，且要求k预先确定。3.3.2层次凝聚方法随着计算资源的发展与进步，以及一些聚类分析软件包的实现，使得近几年层次聚类方法在信息检索系统中得到了较为广泛的应用。层次聚类的方法是对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。凝聚的方法属于合并法，也称自底向上法，开始将每个对象作为单独的一个簇类，然后相继地合并相近的对象或簇类，直到所有的组合并为一个(层次的最上层)，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇类中，在迭代的每一步中，一个簇类被分裂为两个或多个更小的簇类，直到最终每个对象在单独的一个簇类中，或者达到一个终止条件。在文档聚类中，由于用于分裂法的实现算法较少，所以层次法中主要以凝聚法为主，我们这里只讨论层次凝聚方法。文档聚类中层次凝聚法主要的实现思想基本是：(1)计算n个文档两两之间的相似性，记为初始相似性矩阵；(2)初始构造n个簇类，每个文档自成一簇类；(3)找出两个最相似的文档或点(这里的点包括文档和簇类)，将其合并成一个新簇类；(4)计算新类与当前簇类的相似性，更新相似性矩阵，若簇类数等于1或者达到一个停止准则，则跳至步骤5，否则跳至步骤3；(5)选定分类阀值，决定簇类的个数和簇类。所谓停止准则是指用户提前定义的聚类数目，或者聚类程度，达到一定的聚类数目或聚类程度，聚类自动停止。具体过程如下:（1）将文档集中的每一个文档看作一个具有单个成员的簇类，这些簇类构成了的一个聚类；（2）计算中每对簇类之间的相似度,形成初始相似性矩阵；（3）选取具有最大相似度的簇类对，并将和合并为一个新的簇类，从而构成D的一个新的簇类,更新相似性矩阵；重复上述步骤，直到中只剩下一个类或满足停止规则为止。聚类过程如图3-1所示:图3-1层次凝聚类示意图在层次凝聚法中除了需要定义文档之间的相似性之外，还需要定义簇类间的相似性。设有文档集合,,我们需要一种侧度来衡量两簇类之间的相似性，既需要定义函数，不同的簇类间相似性测度函数应用到上述过程中，就会得到不同的层次凝聚方法。在文档层次凝聚法中主要有以下四种方法：SingleLinkMethod,CompletelinkMethod，GroupAverageLinkMethod,Ward'sMethodHYPERLINK[16]。SinglelinkMethod(最大相似性法)；使用两聚类间的最近两点的相似性来描述两簇类间的相似程度，即两聚类、间的相似度可表示为：CompletelinkMethod(最小相似性法):使用两簇类间最远两点间的距离来描述两簇类间的相似程度，即两聚类、间的相似度可表示为：GroupaverageMethod(类平均值法):类平均值法使用聚类,中两两对象点相似性的平均值来表示累计相似程度，即两聚类、间的相似度可表示为：其中，、分别为,中对象点的个数。Ward'sMethod(离差平方和法):Ward从方差分析的观点出发，认为正确的分类应当使得类内方差尽量小，而类间方差尽量的大。样本集的类内方差为:每次选择类间最相似的两类合并，使得增加最小，最终得到一个的局部极小值。此方法只适用于欧氏距离，并不适用于采用相似函数作为样本点间相似性测度的情形HYPERLINK[17]。文档与文档之间、文档与簇类之间、各簇类之间的相似度计算算法会在很大程度上影响聚类的质量，不同的计算相似性算法也造成了不同的聚类方法特点。具体来说，SinglelinkMethod的主要实现算法有：SLINKalgorithm和Minimalspanningtreesalgorithm等；CompleteLinkMethod的主要实现算法有:Defays'CLINKalgorithm、Voorheesalgorithm等；Groupaveragelink的主要实现算法有:Voorheesalgorithm等；Ward'smethod的主要实现算法有:Reciprocalnearestneighbor(相互最近邻算法)等。在凝聚层次聚类方法中，用户需要定义希望得到的簇类数目作为一个结束条件。层次聚类方法尽管简单，但经常会遇到合并点选择的困难。这样的决定是非常关键的，因为一旦一组对象被合并，下一步的处理将在新生成的簇类上进行。已做的处理不能被撤销，聚类之间也不能被交换对象。如果在某一步没有做好选择合并的决定，可能会导致低质量的聚类结果。而且，这种聚类方法不具有很好的可伸缩性，因为合并的决定需要检查和估算大量的对象或簇类。改进层次方法的聚类质量可以将层次聚类和其它的聚类技术进行集成，形成多阶段聚类。例如:BIRCH方法综合了层次凝聚和迭代的重定位方法，它首先用树结构对对象进行层次划分，采用自底向上的层次算法，然后用迭代的重定位来改进结果；Buchshot方法首先将部分对象用层次凝聚类法确定最初几个类，然后将其它对象归入到已有簇类中；Fraction方法将聚类对象随机地分成几个部分，然后在各自的小范围进行层次凝聚类，以此确定聚类结果。层次聚类方法最终形成一个树状结构的谱系图(Dendogram)如图3-1所示，簇类之间存在着包含嵌套关系，每一个小子簇都包含在它上一级的父节点更大的簇类中；相比较平面聚类法簇类之间没有关系。3.4网页聚类算法根据聚类的对象不同，可以将目前较为流行的网页聚类算法分为3类：基于网页内容的聚类算法、基于链接分析的聚类算法和基于用户搜索日志的聚类算法。3.4.1基于网页内容的聚类算法基于网页内容的聚类算法是通过分析网页中包含的文字对网页进行聚类的，包括STC(SuSxTreeClustering)算法、模糊聚类算法等。传统的聚类算法首先对网页内容进行处理，去掉标点符号及词语的前缀后缀，并将复数形式转化为单数形式，去除停用词，从而获得若干能够表示网页实际内容的关键词，并将这些关键词作为聚类的依据。这是基于单个词的聚类算法，其缺点是只关注单个词，而忽略了词间关系。而词间关系对于体现网页内容是至关重要的，传统算法并没有充分利用网页内容所传达的信息。STC是基于词组的聚类算法。STC算法首先对网页内容进行处理，得到若干词组；然后，通过后缀树算法，辨别出拥有相同词组的网页，并将它们作为基本类；最后将基本类不断合并，形成高层次的类。这种算法克服了传统算法的缺陷，将词间顺序也作为聚类的重要依据，从而充分利用了网页所包含的信息。STC算法的优势在于，它的执行时间与网页包含词组的多少成线性关系，非常高效。并且它将词组作为聚类依据，有效地利用了词间关系，聚类准确度比基于关键词的聚类算法要高得多。但是，也正因为STC算法是基于词组进行聚类的，所以其准确率低于利用全文信息进行聚类的算法。3.4.2基于链接分析的聚类算法基于链接分析的聚类算法是通过分析网页之间的链接关系对网页进行聚类的。该算法假设对任一网页而言，存在两类链接，一类是包含在中的，指向其他网页的链接；另一类是包含在其他网页中，指向的链接。若网页、都包含指向网页的链接，则网页、具有同引关系；若网页包含指向网页、的链接，则、因为被相同的网页链接而具有同被引关系。此种算法认为具有同引关系和同被引关系的网页之间具有较大的相似性，并将这两种引用关系作为聚类的依据。假设是检索结果集合中的一个网页，用N维向量POUT和M维向量PIN表示，其中POUT=(Po1,Po2…Poi…Pon)。若网页P中包含指向检索结果集合中第i个网页的链接，则Poi为1，否则Poi为O；其中Pin=(Pi1,Pi2…Pij…Pim)。若检索结果集合中的第j个网页包含指向网页P的链接，则Pij为1，否则Pij为0。计算检索结果中任意两个网页P，Q之间相似度的方法如下：其中，聚类的过程如下：从检索结果集合中去除无关网页，依据上述相似度计算公式对网页之间的相似度进行计算，将相似度大于阈值的网页作为一个聚类。3.4.3基于用户搜索日志的聚类算法基于用户搜索日志的聚类算法是通过用户对搜索结果网页的访问情况对网页进行聚类的。对用户日志进行聚类，以两个假设为前提：（1）如果两个检索式包含相同的检索词，那么这两个检索式代表了相同或者相似的搜索需求；（2）如果用户通过两个不同的检索式访问了相同的网页，那么这两个检索式具有一定程度的相似性。两个检索式、的相似度计算方法如下：其中是检索式中拥有的关键词数目，是检索式、共有的关键词数目。这种算法对每个用户输入的检索词及其对搜索结果的访问情况进行记录，并且依据上述假设对搜索结果进行相似度计算，对相似度大于阈值的搜索结果归于同一个类目下HYPERLINK[18]。上述3种网页聚类方法各有利弊，一般来说，它们会在聚类搜索引擎中结合使用。

聚类搜索引擎设计从总体结构上讲，本文所设计系统由三层组成：第一层是系统接口层；第二层是信息聚类层，负责文本聚类算法的实现乃至形成最终结果的职责，起着代理与聚类处理承上启下的双重作用；第三层是数据源层，位于服务器端，负责数据获取，是系统与Internet的接口。聚类搜索引擎系统的结构如图4-1所示。图4-1聚类搜索引擎系统的模块结构4.1数据源预处理考虑硬盘存储、服务器硬件条件等各方面条件限制，本文采用从yahoo获取数据的方式解决处理数据源的问题。系统通过元搜索引擎的方式获取信息，即将用户提出的查询转交给其它搜索引擎（如google或yahoo），调用Web上现有的搜索引擎，通过对结果的合并和整理来得到检索结果的一种方式。其实现既不需要网络爬虫程序，也不需要使用复杂的检索机制，但元搜索引擎提供了一个可以同时查询多个搜索引擎的统一接口，将各个搜索引擎的位置，接口等细节屏蔽起来。它的特点在于不必对整个网络进行扫描，减小了网络的流量和机器的负荷，同时提高了检索的广度、召回率和精度。该系统通过元搜索引擎原理的运用满足“在线”要求，完成了信息获取的过程。为了提高信息获取的速度，系统需要以多线程的方式做并行元搜索，即并行地调用多个搜索引擎。因为搜索引擎一般通过动态生成的网页返回搜索结果，然而搜索结果往往很多，必须多个网页来显示。如果系统串行地从一个搜索引擎取回其搜索结果网页，就需要较长的网络通信时间，因此系统就通过多线程并行调用多个搜索引擎来达到更高的并行度，提高系统的运行效率。由于对同一个查询来说不同的搜索引擎返回的搜索结果列表有所不同，一项结果往往只在某些搜索结果列表中出现，而且往往出现在不同的位置。对于这种情况系统需要将来自各个搜索引擎的搜索结果列表综合起来，先削除里面的重复项，再对其重新排序形成一个统一的搜索结果列表，以提高信息检索的精度(precision)。并将得到的文本数据进行切词处理，利用中文分词算法将这些文本切分为多个词语，优先选择长度较长的文字进行匹配切词。分析标题、摘要，选取最能表现文本特征的词或词对，用以建立对应的索引，其中包括去除表现力不强的词HYPERLINK[19]。采用的是基于字符串匹配的分词方法。这种方法又叫做机械分词方法它是按照一定的策略将待分析的汉字串与分词词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况可以分为最大(最长)匹配和最小(最短)匹配，优先选择长度较长的文字进行匹配切词；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。采用的最大逆向单纯分词方法，实验表明:对于汉语来说，该方法是最有效的。初步分词包括：1）原子切分；2）找出原子之间所有可能的组词方案；例如：“他说的确实在理”这句话。（1）原子切分的目的是完成单个汉字的切分。经过原子切分后变成“始##始/他/说/的/确/实/在/理/末##末”。（2）然后根据“词库字典”找出所有原子之间所有可能的组词方案。经过词库检索后，该句话变为“始##始/他/说/的/的确/确/确实/实/实在/在/在理/末##末”。4.2索引的建立索引的建立对于搜索的性能影响重大，本系统采用的建立索引模型为倒排文件模型（InvertedFilesList）。倒排文件模型是将文本看成一组单个字符或者一些词的有序串联HYPERLINK[20]，是面向单个字符或词的思想。倒排表方法直观，创建效率高，维护相对容易，所以本系统使用倒排表模型来抽取关键短语。在一些全文检索系统中也以倒排表作为索引模型。倒排表是一些二元组的集合，它的第一个元素是索引项，基于词的特征表示中，索引项指的是词，第二个元素是该索引项在文本集中出现的所有位置，因此从倒排表可以很快得到每个索引项在文本集中出现的所有位置。倒排表空间开销与索引项和位置的定义密切相关。由于在全文检索系统中文本集巨大，倒排表的索引项包括全部汉语词条。清华版的常用词表有13万常用词，专业词表采用《中国分类主题词表》也有6万主题词，如果包括全部的汉语词条系统的空间开销很大，但是索引项可以按照既定的顺序分配地址，在动态使用中，索引项不用再排序。由于文档集的大小范围变化比较大，小到个数位，最大可达到几十万数量级。因为检索结果和用户的检索条件一一对应，不同的检索条件将可能导致完全不同的检索结果集，所以针对于每一次的检索聚类，都是不同的输入数据集。倒排表既要适应数据集的变化，节省空间开销，又要能迅速地创建，尽可能地实现高效率，还要考虑如何便于抽取关键短语。考虑到以上因素，本系统中的倒排表，索引项为单个词汇或相邻词组，索引项指向的元素对象链表包括有共同索引项的检索结果的类对象中所有内容。用于建立索引项的关键字或者关键点短语在计算相似度时起决定性作用。文档的关键短语列表用于倒排索引的索引项，只有当文档之间至少有一个共有的索引项时，才计算它们的相似性，否则对应的文档之间相似性值为0。下面举一个实例用以说明该模型的原理和工作流程：设有两篇文章1和2，内容分别为：文章1：TomlivesinGuangzhou,IliveinGuangzhoutoo.文章2：HeoncelivedinShanghai.由于是基于关键词索引和查询的，首先我们要取得这两篇文章的关键词，通常我们需要如下处理措施：（1）根据已有的文章内容，即一个字符串，我们先要找出字符串中的所有单词，即分词。英文单词由于用空格分隔，比较好处理。中文单词间是连在一起的需要特殊的分词处理。（2）将不代表概念的词可以过滤掉。文章中的“in”，“once”，“too”等词没有实际意义，中文中的“的”、“是”等字通常也无具体含义，可以将它们过滤掉。（3）所有单词统一大小写。因为用户通常希望查“He”时能把含“he”，“HE”的文章也找出来。（4）将部分词还原。用户通常希望查“live”时能把含“lives”，“lived”的文章也找出来，所以需要把“lives”，“lived”还原成“live”。（5）过滤标点符号。文章中的标点符号通常不表示某种概念，也可以过滤掉。经过上面处理后，两篇文章所对应的关键词分别为：文章1的所有关键词：tomliveguangzhouiliveguangzhou文章2的所有关键词：heliveshanghai有了关键词后，我们就可以建立倒排索引了。上面的对应关系是：“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成：“关键词”对“拥有该关键词的所有文章号”。文章1、2经过倒排后如表4-1所示。表4-1文章1和2经过倒排处理后的结果关键词文章号关键词文章号guangzhou1he2i1live1,2shanghai2tom1通常仅知道关键词在哪些文章中出现还不够，还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：字符位置和关键词位置。字符位置，即记录该词是文章中第几个字符，其作用是关键词亮显时定位快；关键词位置，即记录该词是文章中第几个关键词，其作用是节约索引空间、词组查询快。加上“出现频率”和“出现位置”信息后，索引结构如表4-2所示。表4-2文章1和2经过加强处理后的倒排结果关键词文章号[出现频率]出现位置guangzhou1[2]3，6he2[1]1i1[1]4live1[2],2[1]2，5，2shanghai2[1]3tom1[1]1以live这行为例我们说明一下该结构：live在文章1中出现了2次，文章2中出现了一次，它的出现位置为“2，5，2”。结合文章号和出现频率分析，其含义为文章1中出现了2次，那么“2，5”就表示live在文章1中出现的两个位置，文章2中出现了一次，剩下的“2”该设计实现的索引接口、索引及结果封装如下HYPERLINK[21]：namespaceIndex{publicclassIndexer:IIndex{privatestaticstringdeleteStr=".,。，()（）!！";privateconstdoubleTITLEWEIGHT=1.2;privateconstdoubleCONTENTWEIGHT=1;publicIndexer(){inerindex=newHashtable();urlindex=newHashtable();documentID=-1;}publicIndexTableGetIndex()publicvoidAddWordArray(WordResult[]title,WordResult[]wordArray,stringUrl){documentID++;urlindex.Add(documentID,Url);AddWordArray(title,FieldType.Title);AddWordArray(wordArray,FieldType.Content);}privatevoidAddWordArray(WordResult[]wordArray,FieldTypeft);}}4.3相似度计算根据搜索引擎返回的结果文档的标题、URL和摘要信息进行聚类，则先需要通过相似度函数计算返回结果之间的相似性，然后根据相似性密度评价标准来聚类。本方案将检索结果之间的相似度关系映射为无向图，然后再根据节点之间的距离决定其是否在同一个簇类当中。根据类之间依赖性处理，从而使得相互联系比较紧密的对象能够放在同一个簇类中。由检索结果之间的相似性矩阵，将每个文本以及它们之间的相似度关系映射成无向图，每个文本对应图中的一个点，两个点之间带有权值的边表示文本之间超过一定阀值的相似度的值，只有两个结果之间的相似度大于一定的阀值，才构成一条边；如图4-2所示：图4-2使用相似度为权重的无向图由上一节所介绍的倒排文档结构可知:倒排表模型非常有利于相似性矩阵的计算，通过扫描遍历倒排表，我们只计算有共同索引项的相似度的值，其余没有共同索引项相似度值为0，从而节省了计算时间，大大提高了效率。具体的相似度计算算法过程如下：（1）初始化相似性矩阵，令Sim[i,j]=0；（2）遍历倒排表，文本相似度矩阵；（3）计算Sim值。计算索引项1在网页i文本中的权重公式为：Tweigh[i]=(索引出现次数*W0+索引在标题文本中出现次*W1)，其中W0和W1分别为索引项出现在文本正文中和出现在标题处的权重。文本相似度矩阵TR[i,j]的计算公式为：TR[i,j]=TR[i,j]+（TWeigh[i]/TSnip[i].num+Weigh[j]/TSnip[j].num），其中num为出现次数。URL相似度矩阵计算采用字符串比较的方式，使用一级域名扫描。如：http://www./sports/basketball与/sports/football。其URL地址http://www.sina.com相同，则继续扫描，/sports相同，但后续部分不一样，则扫描到该断停止，于是有：UR[i,j]=1+1+0。Sim矩阵的具体计算公式如下：Sim[i,j]=p*TR[i,j]+q*UR[i,j]，其中UR[i,j]为URL相似度矩阵,p、q为调整系数。4.4聚类处理算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”来进行计算的。采用模糊聚类方式，对于一个定点，并不一定只属于某一类，而可能属于某两个甚至更多的类，这样也符合聚类的目的和需求。（1）从n个数据对象任意选择k－1个对象作为初始聚类中心；（2）根据每个聚类对象的质心，从剩余对象中任意选取一个计算它与这些中心对象的距离；通过比较其相似度与所选取的阀值T判断对相应对象进行划分；当该对象与聚类中心的相似度大于阀值时，该对象属于这一聚类，若某一对象不属于前k－1类，则将其划分为第k类；（3）重复步骤（2）直到所有点都处理完为止。其主要算法为：classQueue{public:Queue(intsz){size=sz+1;rear=front=0;listArray=newdouble[size];}~Queue(){ delete[]listArray;}voidclear(){ front=rear;}boolenqueue(constdouble&it){if((rear+1)%size==front) returnfalse;listArray[rear]=it;rear=(rear+1)%size;returntrue;}virtualintlength()constbooldequeue(double&it){if(length()==0) returnfalse;it=listArray[front];front=(front+1)%size;returntrue;}boolfrontValue(double&it)const{if(length()==0) returnfalse;it=listArray[front];returntrue;}};classGraphm{public: Graphm(intnumVert,string*vmark,intk,double**Synphor){ inti=0; intj=0; numVertex=numVert;//对顶点数进行赋值 numEdge=numVert*(numVert-1)/2;//对边数进行赋值 mark=(string*)newint[k];//为标记数组申请空间 for(i=0;i<k;i++) mark[i]=vmark[i];//对标记数组进行赋值 matrix=(double**)newint*[numVert];//为存储数组申请空间 for(i=0;i<numVert;i++) matrix[i]=(double*)newint[numVert]; for(i=0;i<numVert;i++) for(j=0;j<numVert;j++) matrix[i][j]=Synphor[i][j];//对存储数组进行赋值 }//构造函数完成，且运行没有错误 ~Graphm(){ delete[]mark; for(inti=0;i<numVertex;i++) delete[]matrix[i]; delete[]matrix; } doubleweight(intv1,intv2){ returnmatrix[v1][v2]; } stringgetmark(intv){ returnmark[v%numVertex]; } voidsetmark(intv,stringvalue){ mark[v%numVertex]=value; } intfirst(intstart){ inti=0; for(i=0;i<numVertex;i++) if(!matrix[start][i]) returni; returni; } intnext(intstart,intfirst){ inti=0; for(i=first+1;i<numVertex;i++) if(matrix[start][i]) returni; } voidsetEdge(intv1,intv2,doublewgt)//在两个搜索结果之间设置相似度 voidCreatweiRandomCenterArray(intk){ inti=0; intj=0; for(i=0;i<k;i++) Center[i]=0; srand((unsigned)time(NULL)); for(i=0;i<k;i++){ inta=rand()%numVertex; for(j=0;j<i;j++){ if(Center[j]==a) break;//判重 elseif(j>i&&Dijkstra(a,j)<T[j]) Center[i]=a; else i--; } } }//至此建立了一个质心 doubleDijkstra(intstart,intdestination)//最短路径算法 voidBFS(intstart,Queue*Q){ doublev=0;intw=0; stringt=""; Q->enqueue(start); setmark(start,mark[start%numVertex]); while(Q->length()){ Q->dequeue(v); for(w=first(start);w<n();w=next(start,w)){ t=getmark(w); if(&t==&mark[0]&&(weight(start,w)>T[start%numVertex])) setmark(w,mark[w%numVertex]); AddToCluster(start,w);//这里进行聚类 } } } voidUpdateCenter(intk) voidAddToCluster(intindex,intadder){ Cluster[index%numVertex][Top[index]++]=matrix[index][adder]; }//聚类函数 voidCopyCenter(intk){ for(inti=0;i<k;i++) CenterCopy[i]=Center[i]; }};

5.性能分析为了对聚类算法的性能进行评价，很多研究都是利用多种聚类方法对同一个数据集进行聚类，根据最终的结果比较其优劣。如：把聚类结果同经过专家人工分类的结果对照，然而（即使是在实验条件下，也很难评估一个聚类算法）对聚类算法性能的评价是一个相当困难的问题，因为每个方法算法都有不同的属性和着重点，实验研究很难给对不同的聚类算法给出一个综合的评价HYPERLINK[22]。5.1理论分析本文从如下几个方面考虑所设计系统的性能：（1）时间和空间需求 在处理大型数据集时，必须考虑聚类分析中的需求资源。该系统在空间占有上主要是文档的存储和文档之间相似性矩阵的存储。时间上主要是计算需求集中在求相似性矩阵，而倒排文档索引结构大大简化了计算量，它只需计算有共同索引特征项的检索结果之间的相似性就可以了，所以相似性的计算既依赖于文档集特征项的选取范围，还依赖于有共同特征项的结果。针对于特征项的选取范围，我们分别对40条和80条“湖南大学”的检索结果以及40条“软件工程”的检索结果进行了关键短语与简单分词之间的对比试验，以关键词作为特征项是指只对检索结果进行分词、过滤、去除无用词和高频词低频词，不进行联合词组的组合的单个词汇最为特征项，试验结果如下表6-1所示:表5-1单个词汇与关键短语特征项对比表测试对象类别40条“湖南大学”80条“湖南大学”40条“软件工程”关键词180417193关键短语161349239通过试验可以看出，采用关键短语的方法不但没有增加特征项数目，反倒比简单分词的特征项数目稍微少一些，可见采用关键短语的方法并没有增加计算量。并且随着检索结果数目的增加，特征项由于受到整体词汇量的限制，增加到一定程度后将不再随检索结果的增加而大幅增加，这对提高检索性能有着很大的积极作用。（2）网页多主题特性 一般而言一个网页的内容可能同时涉及几方面的主题，聚类算法应该能适当的考虑这种属性。本文提出的聚类算法允许簇类中元素有重叠，属于模糊聚类，实验表明这种结果符合检索结果可能分属不同主题的实际情况。与之相反，在文献xx中提到的xxx聚类算法则没有考虑文档的多主题特性。（3）孤立点处理 在数据集中，常常存在一些数据对象，它们不符合数据的一般模型，即与数据的其他部分(往往是大部分)不同或不一致，我们称这样的数据对象为孤立点。搜索引擎返回的网页中存在相当多的孤立点的情况，一种好的聚类算法应该能够有效地处理孤立点的情况。本系统中将相似度不满足阀值要求的孤立点做为一类整体簇类处理，避免其影响整体聚类结果。但该系统在选词特征项的选取和聚类名称的有效性方面，该系统还需要改进。5.2系统演示本文设计实现了一个基于聚类的搜索引擎原型系统，利用该系统进行信息检索的过程可以演示如下。实际使用时，只需要在输入框中输入要检索的关键词即可返回分类后的结果。用户登陆系统网站，会显示如下登陆界面：图5-1用户登陆界面本系统默认显示第一簇类的网页信息，输入关键字“软件工程”后返回的结果显示如下图5-2所示：图5-2用户搜索关键字显示页面在页面最左边既是本系统经过聚类后显示的结果，系统默认聚为六类，每类的类名由系统根据文本片断中出现频率最高的关键词自动指定。点击左边“示范性”一栏显示结果如下图5-3所示，从中我们可以看出，所指定的类名和聚类后返回的显示网页内容逻辑关联较为紧密。图5-3点击某一聚类栏显示信息总结本文提出并设计了一种聚类搜索引擎的方案，帮助Web用户从搜索引擎所返回的大