摘要 摘要 随着互联网的飞速发展，人们利用互联网共享各种信息，使得网络信息资源日趋丰富，搜索引擎正是为了解决这一问题而发展起来的，而现在的搜索引擎存在明显的缺陷：一是搜索引擎结果数量庞大，二是搜索结果线性排列，本文在现有搜索引擎各种技术研究的基础上，对Web文档聚类进一步研究，致力于搜索结果的自动分类，从而使得用户更加直观高效地找到所需结果。 数据挖掘(Data Mining，DM)是指从大量不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。发展自统计学的聚类分析作为数据挖掘的一项主要功能和任务，成为数据挖掘中的一个重要的研究领域，至今已提出了大量的理论和方法，取得了丰硕的研究成果。其表现形式为概念(Concepts)、规则(Rules)、模式(Patterns)等形式。数据挖掘的功能包括发现概念类描述、关联规则、分类和预测、聚类、趋势分析、偏差分析和类似性分析。 如何从WEB包含的大量信息中发现固有的模式和关联，成了人们迫切希望解决的问题。将传统的数据挖掘技术与Web结合起来，进行Web挖掘就是一个途径。Web挖掘是传统数据挖掘技术在Web环境下的应用，试图从大量的Web文档集合和用户浏览Web的数据信息中发现未知的，有潜在应用价值的模式。因此，显而易见进行基于Web挖掘的聚类引擎研究有着十分重要的意义。 本论文的研究目的是在系统地回顾了互联网信息检索、数据挖掘、搜索引擎以及聚类技术的应用研究现状基础上，将搜索引擎的搜索结果进行聚类处理，最后以结构化的方式显示给最终用户。 本文的主要研究成果包括： (1) 对互联网信息检索、搜索引擎、数据挖掘及其聚类的应用研究现状进行分析和概述，从而指出基于Web挖掘的聚类搜索引擎研究是一个具有重要意义的研究课题。 (2) 本文根据Ming-Cheng Tseng中提出的confidence-lift模式，改进Apriori算法在最大值约束条件下来找到最大频繁项集。 (3) 将文本聚类与现代搜索引擎技术结合起来，提出了一种新的搜索引擎体 I
摘要 系结构，解决了现在搜索引擎存在的一些缺陷。 (4) 在以上面各项研究的基础上，设计了原型系统，从而证明了提出的新的聚类搜索引擎体系结构的可行性。 聚类搜索引擎是一个崭新的领域，其相关的许多技术还在发展，本文的最后对进一步的研究工作进行了展望。 关键词：信息检索，搜索引擎，Web挖掘，Apriori算法，Web文档聚类 II
Abstract Abstract With the rapid development of computer network, Internet is used to publish and share information, this cause information resources on Web have been expanded increasingly. Search engines are developed to solve this problem. At present, search engines have two distinct flaws, one is the number of results returned by search engine are numerous, the other is that the results are displayed linearly. Based on previous research results and technologies of search engines, we further the research on the Web document clustering and classifying web search results automatically. DM refers to the process of finding hidden and useful information from large quantities of incomplete, noisy, fuzzy and random data. Derived from statistics, clustering analysis is one of the main tools of data mining. Data clustering has been studied extensively in past decades, and a mass of theories and methods have been achieved. It is expressed in the form of concepts, rules and patterns, etc. The function of DM includes finding concept description, associated regulations, classification and prediction, clustering, trend analysis, deviation analysis and similarity analysis. How discover the proper mode and connection from a great deal of Web information, become people to hope urgently the problem for resolve. Scooping out traditional data mining technique and Web together, carry on the Web data mining is a path. The Web mining is the application that the traditional data mining technique under the Web environment , try to discover from a great deal of Web text file gather to browse the data information of the Web with customer unknown, there is the mode that the latent application be worth. The study of clustering search engine based on Web data mining is very important and necessary. After systematically reviewing the development of Web information retrieval, data mining, search engine and clustering, this dissertation summarizes the existing problems in search engine, and presents the corresponding solutions. The solution clusters the web results returned by search engines and displayed to users structured. The main achievements of the thesis are following: III
Abstract (1) The current situations of application research on Web information retrieval, data mining, search engine and clustering are summarized. We pointed out the study of clustering search engine based on Web data mining is a very important research subject. (2) This paper based on confidence-lift pattern improves the Apriori approach to find the large-item sets under the rules of maximum constraint. (3) We integrate document clustering with modern technologies of search engines and bring forward a new architecture of search engine, which solves some problems of modern search engines. (4) Based on previous research on search engine, we develop a demo system, which proves the feasibility of the new architecture of search engine. Search Engine is still a new conception, and many technologies involved are not yet mature and being developed. The future research problems are also prospected in the end of the paper. Keywords: Information Retrieval, Search Engine, Web Data Mining, Apriori Approach, Web Document Clustering IV
目录 目 录 第一章 绪论 ................................................................................................................................... 1 课题研究背景 ............................................................................................................... 1 发展现状 ....................................................................................................................... 3 数据挖掘发展现状 ........................................................................................... 3 Web搜索引擎发展现状 .................................................................................. 5 Web挖掘发展现状 .......................................................................................... 6 存在的主要问题 ............................................................................................... 7 论文研究方向和意义 ................................................................................................... 8 论文的组织 ................................................................................................................... 9 第二章 理论基础 ......................................................................................................................... 10 Web搜索引擎 ............................................................................................................ 10 Web搜索引擎的分类 ..................................................................................... 10 Web搜索引擎的工作原理 ............................................................................ 11 网络信息抓取策略 ......................................................................................... 12 元搜索引擎 ................................................................................................................. 13 元搜索引擎作用 ............................................................................................. 13 元搜索引擎的分类 ......................................................................................... 13 元搜索引擎的运做原理 ................................................................................. 14 元搜索引擎的发展 ......................................................................................... 15 Web挖掘 .................................................................................................................... 16 Web挖掘的技术分类 ..................................................................................... 17 Web挖掘的技术流程 ..................................................................................... 17 Web挖掘的方法............................................................................................. 18 聚类分析 ..................................................................................................................... 18 聚类分析中的数据结构 ................................................................................. 19 聚类算法的分类 ............................................................................................. 20 聚类的有效性 ................................................................................................. 22 第三章 Apriori算法及其改进算法 ............................................................................................ 23 引言 ............................................................................................................................. 23 Apriori算法 ................................................................................................................ 23 产生频繁项集 ................................................................................................. 24 产生频繁项集实例 ......................................................................................... 24 利用最大约束条件的多最小支持度改进算法 ......................................................... 27 实验比较 ..................................................................................................................... 28 小结 ............................................................................................................................. 30 第四章 Web文档聚类 ................................................................................................................ 31 本聚类的概述 ............................................................................................................. 31 聚类算法在搜索引擎中的应用特点 ......................................................................... 32 关键词组的提取 ......................................................................................................... 33 问题的提出 ..................................................................................................... 33 V
目录 基本思想 ......................................................................................................... 34 第五章 利用频繁项集进行Web文档聚类 ............................................................................... 36 引言 ............................................................................................................................. 36 文档表示模型 ............................................................................................................. 37 特征项的获取 ................................................................................................. 37 挖掘最大频繁单词(项目)集 .......................................................................... 38 建立特征项矩阵 ......................................................................................................... 39 利用频繁特征项集进行Web文档聚类 ................................................................... 39 定义 ................................................................................................................. 39 聚类过程 ......................................................................................................... 40 算法描述 ......................................................................................................... 41 第六章 基于Web挖掘的聚类搜索引擎介绍 .............................................................................. 43 设计原理 ..................................................................................................................... 43 体系结构 ..................................................................................................................... 43 数据获取 ..................................................................................................................... 44 数据清理 ..................................................................................................................... 45 聚类搜索引擎工作原理 ............................................................................................. 46 第七章 总结与进一步研究展望 ................................................................................................... 48 论文工作总结 ............................................................................................................. 48 进一步研究展望 ......................................................................................................... 48 参考文献......................................................................................................................................... 49 致谢 ................................................................................................................................................ 53 攻读学位期间发表的学术论文 ..................................................................................................... 54 VI
第一章 绪论 第一章 绪论 课题研究背景 如今，互联网是一个巨大的、分布广泛的全球性信息服务中心，它内容涉及新闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其他信息服务。Web还包含了丰富和动态的超连接信息，以及Web页面的访问和使用信息，这为数据挖掘提供了丰富的资源。然而，基于以下的分析，Web对有效资源的利用和数据挖掘还是具有极大的挑战性[1][2][3]。 (1)对有效的数据仓库和数据挖掘而言，Web似乎太庞大了。Web的数据量目前以几百兆字节计算，而且仍然在迅速地增长。许多机构和团体都在把各自大量的可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制、存储或集成Web上的所有数据。 (2)Web是一个动态性很强的信息源。Web不仅以极快的速度增长，而且其信息还在不断发生着更新。新闻、股票市场、公司广告和Web服务中心都在不断地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。 (3)Web页面的复杂性远比任何传统的文本文档复杂得多。Web页面缺乏同一的结构，它包含了远比任何一组书籍或其他文本文档多得多的风格和内容。Web可以看作一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任何有关排列次序加以组织。它没有分类索引，更没有按标题、作者、封面页、目次等的索引。对在这样一个图书馆中搜索希望得到的信息是极具挑战性的。 (4)Web面对的是一个广泛的形形色色的用户群体。目前因特网上连接有约五千万台工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不已和等待一段信息中失去耐心。 (5)Web上的信息只有很小一部分是相关或有用的。据说99%的信息对99%的用户是没有价值的。虽然这看起来不是很明显，但一个人只是关心Web上的很小一部分信息确是事实，Web所包含的其余信息对用户来说是不感兴趣的，而 1
基于WEB挖掘的聚类搜索引擎研究 且会淹没所希望得到的搜索结果。 目前有许多基于索引的Web搜索引擎，它可以完成对Web的搜索，对Web页面作索引，并建立和存储大量的基于关键字的索引，用于定位包含某关键字的Web页面。利用搜索引擎，有经验的用户可以通过提供一组紧密相关的关键字和词组，快速定位到所需的文档。但是，目前基于关键字的搜索引擎存在一些问题。首先，对任一范围的话题，都可能很容易地包含成百上千的文档。这会使得搜索引擎返回的文档数过于庞大，其中很多与话题的相关性并不大，或所包含的内容质量不高。其次，很多与话题相关的文档可能并不包含相应的关键字。这被称为多义问题，例如，关键字“数据挖掘”可能会带出很多与采掘工业有关的Web页面，而可能无法识别有关知识发现，统计分析，或机器学习方面的论文，原因是它们不包含关键字“数据挖掘”。 数据挖掘(Data Mining)是指从大量数据中提取有用的、非一般的模式或知识的过程，又称为数据库中的知识发现(Knowledge Discovery in D[4][5]atabases)。数据挖掘的数据源可以是一般的数据库或数据仓库，也可以是非数据库系统中的数据。数据挖掘的结果是概念化的知识，这些知识源于数据，但高于数据。随着社会的信息化发展，Web数据挖掘(Web Mining)逐渐成了一个新的研究热点[6][7][8]，它可以解决上述Web搜索引擎中存在的不足。 聚类(Clustering)是数据挖掘的基本形式之一[4][9][10]。研究工作集中在为大型数据库的有效和实际的聚类分析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。聚类与分类的不同：分类是一种监督学习(Supervised Learning)，其类别是根据应用的需要事先确定的，根据表示事物特征的数据可以识别其类别；聚类是一种非监督的学习，其类别不是人为指定的而是分析数据的结果，聚类完全由计算机自动进行，不需要人工干预[4]。 数据挖掘技术作为一种新兴计算机应用技术，虽然只经过了短短十几年的发展，却已经在各种领域显示出巨大的潜力。信息检索技术和数据挖掘技术的结合，可望使搜索引擎上升到新的高度，使普通用户也能很容易地在互联网上找到自己真正需要的信息。把新的Web挖掘技术应用到搜索引擎中去，为Web信息利用提2
第一章 绪论 供了新的解决方案。因此，进行基于Web挖掘的聚类搜索引擎研究有着十分重要的意义。 发展现状 数据挖掘发展现状 数据挖掘就是从数据中提取人们感兴趣的知识，这些知识是隐含的，有效的，新颖的，潜在有用的以及最终可以理解的模式。 ①数据挖掘过程： 数据准备 数据挖掘 知识的解释评估 ∣ ∣ ∣ ∣ 知识的解释评估 数据挖掘 数据预处理 数 据 选 择 知识 数 据 集 成 模式 预处理后数据 数据仓库 目标数据 数据库 图 1-1知识发现过程 -1 Process of Knowledge Discovery 广义的观点，数据挖掘的一般过程也就是知识发现的过程(图1-1)。该过程可以归纳为数据预处理、数据挖掘、知识的解释评估三个基本步骤。 数据采集和数据选择的目的是辨别出需要分析的数据集合，缩小处理范围，然而实际系统中收集到的原始数据通常是“脏”的，即数据存在杂乱性、重复性及不完整性；数据预处理可以处理数据中的遗漏及清洗脏数据，从而提高数据挖掘的质量，数据预处理应该包括数据集成、数据清理、数据变换和数据简化等几方面的功能。数据挖掘算法执行，仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影响要素：一是所采用的数据挖掘技术的有效性；二是用于挖掘的 3
基于WEB挖掘的聚类搜索引擎研究 数据的质量。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的结果将不会好的。比如，用户在挖掘途中发现选择的数据不太好或使用的挖掘算法不好，这时，用户需要重复先前的过程，甚至从头重新开始；解释评估这一步骤的任务不仅是把结果表达出来(例如采用信息可视化方法)，还要对信息进行过滤处理，如果不能令决策者满意，需要重复以上数据挖掘的过程。 ②数据挖掘产生的模式[4][12] 数据挖掘产生的模式，在实际中应用比较多的有： 分类：即从给定的训练数据集(分类己知的数据集)中，建立分类模型，之后通过分类模型对新的数据进行分类的过程。经常采用的分类算法有决策树、贝叶斯、神经网络、支持向量机等[4][11]。 回归模式：回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值是离散的，回归模式的预测值是连续的。 聚类模式：聚类似乎和分类很相似，但却是不同的过程。聚类，事先并不知道训练数据的类标签，而是本着“最大化类内部数据相似度，而最小化类间数据相似度”的原则，生成新的类别。分类属于机器学习中的“有教师监督”学习，而聚类则属于“无教师监督”学习。 关联规则：是用来描述在给定的事务集合中，频繁出现的项目集的规则。关联规则广泛使用在超市数据分析，商务站点上的商品布局分析等方面。因此，关联规则的挖掘是当前商业用途最广泛的数据挖掘方法。 序列模式：序列模式类似于关联规则，把数据之间的关联性和时间联系起来，从而预测数据在时间上的发展趋势。 ③数据挖掘的应用 由于数据挖掘带来的显著经济效益，使数据挖掘越来越普及。它不仅能用于控制成本，也能给企业带来效益。很多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包括争取新的客户、在己有客户的身上赚更多的钱、保持现有优质客户。如果能够确定好客户的特点，那么就能为客户提供针对性的服务。比如，己经发现了购买某一商品的客户的特征，那么就可以向那些具有这些特征但还没有购买此商品的客户推销这个商品；找到流失的客户的特征就可以在那些具有相似特征的客户还未流失之前进行针对性的弥补，因为保留一个客户要比争4
第一章 绪论 取一个客户成本低得多。 数据挖掘可以应用在各个不同的领域。电讯公司和信用卡公司是用数据挖掘检测欺诈行为的先行者。保险公司和证券公司也开始采用数据挖掘来减少欺诈。医疗应用是另一个前景广阔的产业：数据挖掘可以用来预测外科手术、医疗试验和药物治疗的效果。经销商更多的使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖掘更灵活的使用促销和优惠卷手段。制药公司通过挖掘巨大的化学物质和基因对疾病的影响的数据库来判断哪些物质可能对治疗某种疾病产生效果。除此之外，数据挖掘技术在金融，体育比赛，天文，生物等领域的数据分析上，也有相应的成功案例。 Web搜索引擎发展现状 Web搜索引擎指的是一种在Web上应用的软件系统，它以一定的策略在Web上搜集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。用户查询的途径主要包括自由词全文检索、主题词检索、分类检索及其他特殊信息检索。随着计算机和互联网技术的飞速发展，网络上的信息量急剧增长，已经成为了人类有史以来资源数量最多、资源种类最全、资源规模最大的一个综合信息库。其信息来源丰富、分布广泛，各种类型的信息资源异构地分布在网络空间中，如果不能使庞杂的信息有序化，就很难有效获取，如何准确有效地从互联网上获取信息就成了一项艰巨的任务，目前解决这一问题的最佳方案是利用搜索引擎。 搜索引擎最初起源于1990年加拿大麦吉尔大学开发的Archie软件，Archie通过定期搜索并分析FTP系统中存在的文件名信息，提供自动搜索分布在各个FTP主机中的文件服务。1993年Matthew Gray开发了World Wide Web Wanderer，是世界上第一个利用HTML网页之间的链接关系来监测Web发展模型的“机器人”(Robot)程序，最初仅仅用来统计互联网上的服务器数量，后来也能够捕获网址(URL)。现代搜索引擎的思路来源于Wanderer，不少人在Matthew Gray工作的基础上对他的蜘蛛程序做了改进。1994年7月，Michael Mauldin 将John Leavitt的蜘蛛程序引入到其索引程序中，创建了Lycos。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos第一个在搜索结果中使用了网页自动摘 5
基于WEB挖掘的聚类搜索引擎研究 要。1995年12月DEC正式发布的AltaVista是第一个支持自然语言搜索的搜索引擎，也是第一个实现高级搜索语法的搜索引擎。1997年8月Northern Light Group正式发布的Northernlight搜索引擎是第一个支持对搜索结果进行简单自动分类的搜索引擎。1998年，Google在PageRank、动态摘要、网页快照、DailyRefresh、多文档格式支持、地图、股票、词典、寻人等集成搜索、多语言支持、用户界面等功能上的革新，像AltaVista一样，再一次彻底地改变了搜索引擎的定义。在国内，对搜索引擎的研究起源于“中国教育研网”(CERNET)一期工程的子项目，1997年10月北京大学计算机系在CERNET上推出了天网搜索版本，2000年百度(Baidu)公司推出了专注于中文搜的“百度”商业搜索引擎索()。 Web挖掘发展现状 Web挖掘是一项综合技术[13]，涉及Web、数据挖掘、信息学、计算语言学等多个学科，目前尚属一个较新的研究领域，正处于发展阶段，尚无统一结论。Web数据的非结构化这一显著特征使Web数据挖掘更加复杂和困难。Web数据挖掘是从数据挖掘发展而来，都是在分析大量数据的基础上，做出归纳性的推理，预测客户的行为，帮助企业的决策者调整市场策略、减少风险并做出正确决策的过程。目前，国际上对Web挖掘的研究主要集中在：搜索引擎的设计、文件自动分类技术、关键词的自动化信息的提取以及Web上新型应用的研究应用领域中通用的Web挖掘工具还比较少，主要分文本信息挖掘工具和用户访问模式挖掘工具。 在Web内容挖掘方面，Web内容数据挖掘和信息检索有较深的渊源，因此许多技术都是源自信息检索领域。互联网上信息量很大，但由于这些信息缺乏结构化和组织的规整性，目前几乎所有的互连网查询工具搜索引擎都面临匹配的查准率低，给出的查询结果存在大量冗余但是查全率却不高的问题。研究这个问题，国外学术界有两派：一是从信息检索角度研究这个问题，主要研究如何处理文本格式和超级链接文档，这些数据是非结构化或者是半结构化的。二是从数据库角度研究，主要处理半结构化的Web数据库，也就是超级链接文档，数据多采用带权图或对象嵌入模型(OEM)，或关系数据库表示，应用Proprietary算法、经过6
第一章 绪论 修改了的关联规则挖掘算法，从而寻找出网站页面之间的内在联系。 目前，国内的Web使用挖掘研究主要侧重于理论研究，东南大学的宋爱波等提出了一种新颖的MBP算法，针对 Web浏览和日志文件固有的模糊性和不确定性，讨论了Web页面的模糊聚类问题，并且对发现的知识在其推荐系统及自适应Web站点中的应用并给出了相应算法。中科院提出了K-paths路径聚类方法，根据用户访问兴趣对用户集进行划分。上海交大提出了一种Web日志预处理阶段的Frame页面过滤算法。中国科技大学提出了一个用户识别的通用算法。西安交通大学在Web挖掘研究方面做了多项工作。河海大学成功地将Web挖掘应用到了防洪网站中。国防科技大学、武汉大学也在做电子商务网站中数据挖掘的研究。 存在的主要问题 Web搜索引擎的主要功能是信息组织和信息检索。目前，大多数搜索引擎一般在首页中都有检索对话框，允许用户输入欲查询的关键词，搜索结果由搜索引擎的检索软件进行处理。在一定程度上，Web搜索引擎解决了网络信息资源查找的问题，但也如很多文献所讨论的，Web搜索引擎还存在着诸多问题[14][15]： (1) 智能性程度低 无法对于汉语语法、词的上下文和语义等中文信息处理技术，自动收集、识别网上的信息，智能化地提取摘要和关键词，建立索引，提供个性化、专业化信息查询，对不良信息监控、报警的网络信息自动发现、查询系统。 (2) 无法实现统一的自动分类 目前网页分类基本上还是人工分类，对数据进行挖掘以实现精确分类，但是最大问题是无法应对网上海量的信息资源。虽然目前存在有大量的搜索引擎，但还没有一个统一严格的分类方法来管理，统一的自动分类标准势在必行。 (3) 检索精度不够 Web搜索引擎的检索结果通常数目相当庞大，所包含的信息资源类型多样，大量对用户无用的信息混杂其中，因此传统的Web搜索引擎精度一般较低。如何提高搜索引擎的精度是当前研究的重点问题。本文进行的基于Web挖掘的聚类搜索引擎研究就是设法提高搜索结果的精度。 7
基于WEB挖掘的聚类搜索引擎研究 (4) 单一搜索引擎的能力限制 单个搜索引擎与整个Web的分布之间存在着无法避免的矛盾。一方面，需要管理的信息资源极其巨大，任何一个搜索引擎都无法完全满足要求；另一方面，各个搜索引擎各行其是，重复建设。随着Web的发展，目前的搜索引擎己经不能适应信息检索服务的需要。因此，引入元搜索引擎，它的优点是能够在短时间内提供相对全面和准确的信息。 (5) 查询结果缺少结构化 大多数的搜索引擎都只返回一张长长的检索结果表，该表中可能包含成千上万个指向Web站点的指针。用户无法迅速、准确的找到自己所需要的查询结果。本文将搜索结果以聚类树的方式提供给用户，以便于用户查询。 综上所述，基于Web挖掘的聚类搜索引擎的研究是一个新兴的研究方向。如何将数据挖掘技术运用到搜索引擎上，从而促进搜索引擎的发展，使互联网用户能快速、准确的从网上查询到自己所需要的信息等相关问题，值得深入研究。 论文研究方向和意义 随着互联网的迅猛发展，信息爆炸式增长，产生了信息过载，而在相当大的程度上，搜索是面临信息过载的唯一选择。但是，现在的搜索引擎缺陷也很明显，几乎快成了新的信息过载：一是搜索结果数量庞大；二是搜索结果的线性排列。针对上面提到的问题，我们将数据挖掘中的聚类知识引用到现有搜索引擎，构建“聚类搜索引擎”，“聚类搜索引擎”实现的功能就是把检索出来的结果自动分类，使得用户能很直观的根据需求点击，直接定位到要查找的网页。本文是在元搜索引擎搜索结果的基础上，利用聚类方法将搜索结果加以组织，以便用户能够迅速、准确的获得所需要的信息。其过程如下： 互联网←→搜索引擎←→元搜索引擎←→聚类搜索引擎←→用户 我们之所以对元搜索引擎的结果进行聚类，而不是对整个互联网数据信息进行聚类分析，是因为互联网数据规模巨大而且质量参差不齐。在此，利用元搜索引擎对互联网数据进行过滤，从而使得聚类效果更为明显，可行性更高。本论文是想把Web数据挖掘技术与搜索引擎相结合，构建一个基于Web数据挖掘的聚类搜索引擎系统。提高搜索引擎的工作效率。最后，介绍了原型系统的设计结构与8
第一章 绪论 实现，并用一个实例，证明了将聚类引入搜索引擎的可行性。 论文的组织 论文的组织如下： 第一章“绪论”，介绍论文的研究背景、研究现状、研究目的、研究内容、论文工作以及论文结构。 第二章“理论基础”，介绍搜索引擎与数据挖掘领域中相关的基础知识。 第三章“Apriori算法及其改进算法”，提出一种改进的Apriori算法，利用Apriori算法获取频繁项目集。 第四章“Web文档聚类”，整体介绍Web文档的聚类以及搜索引擎中常见的聚类算法。 第五章“利用频繁特征项集进行Web文档聚类”，将Web文档结构化，利用的Apriori算法及其改进算法获得相应的频繁特征项集，利用频繁特征项集进行Web文档聚类。 第六章“基于Web挖掘的聚类搜索引擎整体介绍”，通过对聚类搜索引擎体系结构中各个模块的实现，验证了聚类搜索引擎设计的可行性；从整体上解析了聚类搜索引擎的工作原理。 第七章“总结与进一步研究展望”，本论文工作的总结，同时指出了尚需进一步研究的方向。 9
基于WEB挖掘的聚类搜索引擎研究 第二章 理论基础 Web搜索引擎 搜索引擎指的是一种在Web上的应用软件系统[16][17]，它以一定的策略在Web上搜集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。用户查询的途径主要包括自由词全文检索、主题词检索、分类检索及其他特殊信息的检索。 Web搜索引擎的分类 搜索引擎按照检索方式可分为全文搜索引擎、分类目录搜索引擎和元搜索引擎三大类： 第一类，全文搜索引擎，又叫机器人搜索引擎，是通过一个叫网络机器人(Robot)或网络蜘蛛(Spider)的软件，自动分析网络上的各种链接并获取网页信息按规则加以分析整理，记入数据库。其比较典型的代表是Google和Baidu。全文搜索引擎系统的优点是全文搜索，检索功能强，信息更新速度快。缺点是信息太多，命中率低，重复链接较多，层次结构不清晰。 第二类，分类目录搜索引擎，是利用各网站向搜索引擎提交网站信息时填写的关键词和网站描述等资料，通过人工的方式收集整理网站资料形成数据库。优点是层次，结构清晰，易于查找；多级类目，便于查询到具体明确的主题；内容提要、分类目录下，有简明扼要的内容，用户可以根据目录有针对性地逐级查询信息，其缺点是需要人工介入、维护量大、搜索范围较小、查全率较低，对偏僻主题、新兴学科、交叉学科不能很好地涵盖，类目间的交叉会导致重复和资源浪费。另外，由于数据库更新速度比较慢，站点本身的动态变化不能及时地反映到搜索结果中，严重影响了查询结果的时效性。 第三类，元搜索引擎，这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户，这类搜索引擎兼集多个搜索引擎的信息，并且加入10
第二章 理论基础 新的排序和信息过滤，可以很好地提高用户满意度；该类搜索引擎的优点是能够在短时间内提供相对全面和准确的信息；缺点是不能够充分使用所使用的搜索引擎的功能，用户需要做更多的筛选。 此外，还有其他的分类方式，例如按查询方式可分为浏览式搜索引擎、关键词搜索引擎、全文搜索引擎、智能搜索引擎；按语种又分为单语种搜索引擎、多语种搜索引擎和跨语言搜索引擎等。 Web搜索引擎的工作原理 现代大规模高质量的搜索引擎一般采用三段式的工作流程[18][19]，即：网页搜集、预处理和查询服务。网页搜集是指搜索引擎利用一种称为蜘蛛(Spider)或爬虫(Crawler)的软件从互联网自动搜集网页，按照某种约定的搜索策略遍历，不停地沿着URL爬取Web网页，并下载收集相应的网页。Web搜索引擎的工作流程如(图2-1)所示： 网络蜘蛛 WWWWW 页面存储器 日志分析器 分析索引器7 索引数据库 用户行为 日志数据库 查询器 用户接口 用户 图2-1搜索引擎工作流程图 -1 Flow Chart of the Search Engine 分析索引系统程序对下载的网页进行预处理，提取网页的主题以及和主题相关的内容(包括网页所在URL、编码类型、页面内容包含的关键词、摘要、正文、生成时间、相关链接等信息)，去除所搜集网页集合中主题内容重复或链接的网 11
基于WEB挖掘的聚类搜索引擎研究 页。根据一定的相关度算法进行大量的计算得出网页的重要性(或相关度)，然后利用这些相关信息为原始网页建立索引，并对索引网页库进行网页切分，将每一篇网页转化为一组词的集合；最后将网页索引词的映射转化为索引词到网页的映射，形成倒排文件(包括倒排表和索引词表)，同时将网页中包含的不重复的索引词汇聚成索引数据库。查询服务提供友好的查询界面，接受用户提交的查询任务，并根据要求从索引数据库中找到符合要求的所有相关的网页，按照一定的规则排序输出。 网络信息抓取策略 在遍历Web的过程中，Spider通常将Web作为一个有向图来处理，将每一个页面看作图的一个节点，将页面中的超级链接看作图中的有向边。因此，可以使用有向图的遍历算法来对Web进行遍历。当前流行的遍历算法包括以下几种： (1) IP地址搜索策略：先赋予Spider一个起始的IP地址，然后根据IP地址递增的方式搜索本IP地址段后的每一个WWW地址中的文档，它完全不考虑各文档中指向其他Web站点超级链接地址。这种算法搜索全面，能够发现没有被其他文档引用的新文档信息源，但效率较低，不适合大规模搜索； (2) 深度优先算法：从起始页面出发，沿上的某一个链接一直搜索到某个不包含任何链接的文件为止，这样形成一条完整的链。再返回继续选择其他链接进行相似的访问。访问结束的标志是不再有其他超级链接可以搜索。这种算法的优点是在理论上能够遍历一个Web站点下所有深层嵌套的页面，但如果遇到深度很大的搜索树，有陷入一个分支当中或者进入循环状态的危险，因而不具有完备性和最优性； (3)广度优先算法：先搜索完一个Web页中所有的链接再继续下一层的搜索，直到最底层为止。它克服了深度优先算法所不具备的完备性和最优性的缺点，保证一个服务器上至少有一篇文档加入到索引数据库，能降低同一服务器被访问的频度，但时间复杂性和空间复杂性较大； (4) 合作抓取算法：由被抓取网站，提供可被抓取内容的网站地图，双方协议好，只抓取这些特定内容，在抓取速度及时间上双方前期进行协商。另外还可以完全由被抓取方，提供详细内容，抓取过程都可以省略一些步骤。 12
第二章 理论基础 元搜索引擎 元搜索引擎是将多个搜索引擎集成在一起[20]，通过一个统一的检索界面接受并处理用户的查询提问，在进行检索时调用一个或者多个独立搜索引擎的数据库，检索结果是来自独立搜索引擎的检索结果或者是来自多个搜索引擎检索结果集合的综合，基于独立搜索引擎结果的二次加工，呈现给用户的检索结果既可以是引用原始的独立搜索引擎的页面，也可以是由元搜索引擎重新定制后的形式，标明结果记录的来源搜索引擎及其局部相关度，提供了全局的相关度。 元搜索引擎作用 研究表明：任何一个搜索引擎对互联网的覆盖度都在16%以下，并且来自各个搜索引擎的结果往往相差40%左右。针对这种情况，一些研究人员开发了元搜索引擎(meta-search engine)。元搜索引擎能够自动地同时调用多个搜索引擎，综合其搜索结果，并以统一的格式显示给用户。 其优点是：(1)节省时间，元搜索引擎自动地把用户的查询同时提交给多个搜索引擎，与用户手工把查询一个一个地提交给各个搜索引擎相比，节省不少时间。(2)扩大范围，元搜索引擎能够调用多个搜索引擎，自然就扩大了搜索的范围。(3)统一格式，各个搜索引擎搜索结果的格式互不相同，元搜索引擎将这些搜索结果综合起来以统一的格式显示，使搜索结果看起来更清楚明了。(4)简化使用，因为元搜索引擎自动地调用多个搜索引擎，所以用户不必了解各个搜索引擎的网址及其用法，只需知道元搜索引擎的网址和用法就可以了；另外，元搜索引擎的管理者会维护其调用的搜索引擎列表，将新出现的搜索引擎加入，将已停止的搜索引擎删除，所以用户也不必了解存在哪些可用的搜索引擎；从系统管理者的角度看，元搜索引擎的实现与维护都更简单。 元搜索引擎的分类 (1)桌面元搜索引擎 桌面元搜索引擎接受用户的检索提问，翻译成对应不同搜索引擎的语法，通过网络接口连接一个或多个在线搜索引擎，各个搜索引擎返回的结果在Web浏 13
基于WEB挖掘的聚类搜索引擎研究 览器的不同窗口中显示。桌面元搜索引擎使用方便，不需要用户记忆和保存众多搜索引擎的地址以及检索语法，不需要打开Web浏览器就可以实施检索，用户可添加新的搜索引擎。但用户必须分别浏览各个搜索引擎返回的结果，检索结果难以控制和筛选，检索效率不高。 (2)All-in-One式的元搜索引擎 All-in-One方式的元搜索引擎又称搜索引擎元目录，它将主要的搜索引擎集中起来，并按类型组织成目录，构成检索界面，为用户选择检索工具提供帮助，最终实现与普通单一搜索引擎的检索。搜索引擎元目录无自建数据库，制作与维护技术简单，可随时对所链接的搜索引擎进行增删调整和及时更新。但是通过一个界面来帮助用户选择和使用搜索引擎，只能选择一个搜索引擎进行检索，使用它的显示格式，不能控制和优化检索结果，检索功能简单。 (3)并行搜索式元搜索引擎 并行搜索式元搜索引擎将多个搜索引擎集成在一起，提供一个统一的检索界面，用户发出检索请求后，被同时提交、发送给多个独立搜索引擎，同时检索多个数据库，最终经过聚合、去重将检索结果输出。并行搜索式元搜索引擎效率较高，借鉴联机检索中的跨文档检索功能，用户使用同一指令语言检索不同的搜索引擎的索引数据库，检索结果经过了预处理，格式统一，检索噪音较小。 元搜索引擎的运做原理 元搜索引擎是用户同时利用多个搜索引擎进行网络资源搜索的中介。检索时，元搜索引擎根据用户提交的检索要求，调用源搜索引擎进行搜索，并对检索结果进行汇集、去重、排列等优化处理后，以统一的格式在同意界面集中显示。在这个过程中，元搜索引擎依次通过以下3个机制进行运做： (1) 选择机制，元搜索引擎在执行查询之前必须进行搜索引擎列表的初始化，对需要调用的搜索引擎进行选择。选择的方式有两种：系统选择和用户选择。前者是有系统决定选择哪几个独立搜索引擎，这是在对源走索引擎的功能效率进行自动评价的基础上实现的；用户选择是用户通过浏览搜索引擎列表，自主选定独立搜索引擎。此外，这一机制还可以实现检索时间、结果数量的选择等用户个性化设置。 14
第二章 理论基础 (2) 转换机制，包括两部分内容：把用户的查询请求转化成符合各源搜索引擎要求的标准查询模式；把各源搜索引擎的查询结果转换为统一的输出形式。由于各个独立搜索引擎的检索算法和数据库结构存在差异，需要转换机制精确掌握它们调用CGI的格式，逐一作出适应源搜索引擎的转换，以提高检准率。同样，各搜索引擎的查询结果页面表达格式各有侧重，也需要依赖转换机制将它们统一起来。 (3) 排列机制，整合各搜索引擎的检索结果，分为引用排列和重新排列两种方式。引用排列是指采用搜索引擎提交的结果顺序，依次将不同来源的结果显示出来。这种方式无需进行结果去重而只需完成格式转换，因此显得简单易行，而且它有利于用户了解哪些搜索引擎对自己所需的信息不能提供或提供的很少，以后再查询时可以将它们从引擎组合中删除。但这种方式也很有可能使一个搜索引擎的不相关结果排在了另一个搜索引擎相关结果之前，使用户错过了重要信息；重新排列方式则要多结果进行更多的处理，首先是筛选处理，对被多个搜索引擎检出的结果进行合并去重；然后是对结果再排序，目前常用的排序算法有摘要排序法和位置排序法。 元搜索引擎的发展 元搜索引擎依赖于数据库选择技术、文本选择技术、查询分派技术和结果综合技术等。目前，利用智能检索技术研究，开发智能元搜索引擎，实现检索系统户界面的改进、调用策略的完善、返回信息的整合以及最终检索结果的排序，是元搜索引擎研究的重点[21]。 (1) 智能化代理，元搜索引擎技术重点是检索请求提交机制和检索接口代理和结果的集成。智能元搜索引擎能够分析整理成员搜索引擎的工作记录数据，建立调用策略模型，实施检索时动态地决定调用策略，将搜索请求递交给最适合的搜索引擎处理，检索技术统一集成界面，具备多样化的检索选项和功能设置，综合运用检索平台，支持匹配、逻辑与位置限定等检索，通过自然语言理解和与成员搜索引擎相匹配的格式转化实现检索语言自动转换与功能实现。 (2) 知识检索，信息检索从目前基于关键词检索的层面提高到基于知识检索的层面。知识发现技术与人的思维行为模式相吻合，在智能检索系统中增加了分 15
基于WEB挖掘的聚类搜索引擎研究 词词典、同义词典，并从知识层面上通过主题词典、上下位词典、相关同级词典，形成一个知识体系或概念网络，准确定位搜索结果的范围，使检索结果深入到知识单元，通过对搜索内容相关性的自动学习，对用户检索请示实现合理的联想和扩检，给用户智能知识提示，不断提高搜索结果的可用度。 (3) 垂直搜索，用户希望通过专业化信息查询可以得到最确切的答案，而水平搜索引擎技术则很难达到用户这样的要求。垂直类搜索引擎面向某一特定专业领域，专注于自己的特长和核心技术，保证了对该领域信息的收录齐全与更新及时对整个搜索领域进行细分，提高信息检索的针对性，解决以往Web搜索结果大多是综合性缺乏专业性，检索深度和分类细化程度难以满足专业人员的需求的问题。 (4) 个性化的信息供给服务，进行歧义信息的检索处理，通过歧义知识描述库、全文索引、用户检索上下分析以及用户相关性反馈等技术揣摩用户的心理，高效、准确地把信息反馈给用户；分析成员搜索引擎的工作记录数据，利用数据库技术注意标引、统计记录的访问频率，实现记录的自动建立、保存，了解记录使用程度，实施检索时动态、智能地决定调用策略，选择并激活最合适的成员搜索引擎，通过信息推荐、信息反馈与信息跟踪服务实现元搜索引擎灵活完善的、智能化的、个性化的信息供给服务。 Web挖掘 Web挖掘是一项综合技术[22]，涉及Web、数据挖掘、信息学、计算语言学等多个学科，目前尚属一个较新的研究领域，正处于发展阶段，尚无统一结论，在此列出几个比较公认的Web挖掘的定义： (1)是第一个提出 Web 挖掘术语的人，他认为 Web挖掘是运用数据挖掘技术从Web文档和服务中自动地发现和抽取信息。 (2) Web挖掘可以宽泛地定义为从WWW中发现和分析有用的信息。 (3) Web挖掘是指从Web数据中发现潜在的、有用的和从前不知道的信息和知识的完整过程，是知识发现对Web数据的扩展。 由上述关于Web挖掘的定义可以看出，Web挖掘就是对文档的内容、可利用资源的使用以及资源之间的关系进行分析，从Web数据中发现潜在的有用信16
第二章 理论基础 息和先前不知道的知识的整个过程。从这个意义上说，Web挖掘完全包含了知识发现的标准过程，而不同于数据挖掘是知识发现的一个阶段。 Web数据的非结构化这一显著特征使 Web数据挖掘更加复杂和困难。Web数据挖掘是从数据挖掘发展而来，都是在分析大量数据的基础上，做出归纳性的推理，预测客户的行为，帮助企业的决策者调整市场策略、减少风险并做出正确决策的过程。 Web挖掘的技术分类 Web挖掘按照挖掘方式一般地可分为三大类：Web内容挖掘(Web Content Mining)，Web使用挖掘(Web Usage Mining)，以及Web结构挖掘(Web Structure Mining)。 (1)Web内容挖掘：是从文档内容或其描述中抽取知识的过程。它又可以分为Web页面内容挖掘和搜索结果挖掘。页面内容挖掘指的就是对Web页面上的数据进行挖掘，而搜索结果挖掘则指的是以某一搜索引擎为基础，对已搜索结果进行挖掘。 (2) Web使用挖掘：即Web日志挖掘，是通过挖掘Web日志记录，发现用户访问 Web页面的模式。它又可分为一般访问模式挖掘和个性化服务模式挖掘。 (3) Web结构挖掘：是从WWW的组织结构和链接关系中推导知识。它又可以分为外部结构挖掘、内部结构挖掘和URL挖掘。Web结构挖掘的目的是通过聚类和分析网页的链接，发现网页的结构和有用的模式，找出权威页面。 而对于 Web挖掘的这些运用也恰是一个企业网站所关心和关注的内容，对于实现企业网站的优化，实现企业网站内容和结构的有的放矢，增加企业网站的用户访问数量，提高访问用户的满意度都是不可忽视的问题。 Web挖掘的技术流程 (1) 查找资源：任务是从目标Web文档中得到数据，值得注意的是有时信息资源不仅限于在线Web文档，还包括电子邮件、电子文档、新闻组，或者网站的日志数据甚至是通过Web形成的交易数据库中的数据。 (2) 信息选择和预处理：任务是从取得的Web资源中剔除无用信息和将信息 17
基于WEB挖掘的聚类搜索引擎研究 进行必要的整理。例如从Web文档中自动去除广告连接、去除多余格式标记、自动识别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。 (3) 模式发现：自动进行模式发现。可以在同一个站点内部或在多个站点之间进行。 (4) 模式分析：验证、解释上一步骤产生的模式。可以是机器自动完成，也可以是与分析人员进行交互来完成。 Web挖掘的方法 (1) 关联分析，用于发现同一事件中不同数据项的相关性。常用的Apriori算法分为两步，首先找出满足最小支持度阈值的频繁项集；然后由它们形成满足最小置信度阈值的强关联规则。可以将Web挖掘得到的关联规则用于改进电子商务站点的结构，将相关联的商品放在一起，减轻用户过滤信息的负担，增加交叉销售。 (2) 分类分析，通过学习已被告知类标号的训练集，得到分类器模型，然后将其用于对其它数据的分类。常用的方法有贝叶斯分类法、决策树技术和支持向量机技术。 (3) 聚类分析，使用划分方法、层次方法、基于密度的方法、基于网格的方法等技术，使同一类中的对象之间具有很高的相似度，而不同类中的对象高度相异。经聚类分析，可以对电子商务平台中的具有相似浏览模式的用户提供个性服务，以满足该类消费群体的特殊需要。 (4) 序列分析，是挖掘频繁出现的有序事件或子序列模式，侧重于数据项间的前后关系。在电子商务平台上，可以帮助企业预测用户未来的购买行为，指导企业制定销售计划。 聚类分析 聚类是人类一项最基本的认识活动。所谓聚类就是按照事物的某些属性，把事物聚集成簇，使簇内的对象之间具有较高的相似性，而不同簇的对象之间的相似程度较差。聚类是一个无监督的学习过程，它同分类的根本区别在于：分类是需要事先知道所依据的对象特征，而聚类是要找到这个对象特征，因此，在很多18
第二章 理论基础 应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。例如在商务中，聚类分析能够帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学中，聚类分析能用于推导植物和动物的分类，对基因进行分析，获得对种群中固有结构的认识。聚类分析也可以用于在泥土观测数据库中对相似地区的区分，也可以根据房子的类型、价值和地域对一个城市中的房屋进行分类。聚类分析也能用于分类Web文档来获得信息。作为数据挖掘的功能，聚类分析可以作为一个获得数据分布情况、观察每个类的特征和对特定类进一步分析的独立工具。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。 一个能产生高质量聚类的算法必须满足下面两个条件：类内(Intra-class)数据或对象的相似性最强，以紧致度描述；类间(Inter-class)数据或对象的相似性最弱，以分离度描述。聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法和实现方式，同时也取决于该算法能否发现部分或全部隐藏的模式。 聚类分析中的数据结构 许多基于内存的聚类算法选择如下两种有代表性的数据结构： (1)数据矩阵(Data Matrix，或称为对象与变量结构)：它用p个变量(也称为度xxx♣ •量或属性)来表现111f1n个对象，例如年龄、身高、体重、性别、种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者看成n×p(n个对象×♦÷p个变量)的矩阵。 xxxi1ifip ♦÷ xxxn1nf np ♥≠(2)差异度矩阵(Dissimilarity Matrix，或称为对象－对象结构)：存储n个对象两两之间的差异性，表现形式是一个n×n矩阵。 19
基于WEB挖掘的聚类搜索引擎研究 0♣ •♦÷d(2,1)0 d(n,1)d(n,2)0♥≠在这里d(i ,j)表示对象i 和 j 之间的相异性的量化表示，通常它是一个非负的数值，满足d(i, j)=d(j ,i)，d(i,i) =0，并且当对象i 和 j 越相似或接近，其值越接近0；两个对象越不同，其值越大。 数据矩阵经常被称为二模矩阵(Two-mode)，而差异度矩阵被称为单模(One-mode)矩阵，这是因为前者的行和列代表不同的实体，后者的行和列代表相同的实体，许多聚类算法以差异度矩阵为基础。如果数据是用数据矩阵的形式表示的，在使用该类算法之前要将其化为差异度矩阵。 聚类算法的分类 聚类分析算法取决于数据的类型、聚类的目的和应用。大体上可以分为以下几类：划分方法，层次方法，基于密度的方法，基于网格的方法，基于模型的方法等。另外，根据聚类间重叠程度可分为：硬聚类和模糊聚类。 (1).划分方法(Partitioning Method) 划分方法创建数据集的一个单层划分：给定一个包含n个对象的数据集，以及要生成的簇的数目k。划分方法首先创建一个初试划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间的移动来改进划分。也就是说，它将数据划分为k 个组，同时满足以下的要求：每个组至少包括一个对象；并且每个对象必须属于且只属于一个组(硬划分)。为了达到全局最优，基于划分的聚类会要求穷举所有尽可能的划分。该方法的典型代表是k-means 算法，k-medoids算法[23]，PAM(Partitions for Around Medoids )算法[23] ，CLARA ( Clustering Large Applications)算法[23]，CLARANS(Clustering Large Applications based upon RAN domized Search)算法等[24]。 (2).层次方法(Hierarchical Method) 一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上还是自顶向下形成，层次聚类的方法可以进一步分为凝聚(Agglomerative)的和20
第二章 理论基础 分裂(Division)的。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后不断地合并相近的对象或组。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个类中，在迭代的每一步中，一个类被不断的分裂为更小的类。相对于划分算法，分层算法不需要指定聚类数目，然而在凝聚或者分裂的层次聚类算法中，用户可以定义希望得到的聚类数目作为一个约束条件。 (3).基于密度的方法(Density-based Method) 为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将簇看作是数据空间中被低密度区域分割开的高密度对象区域。基于密度的聚类的主要思想是：只要临近区域的密度(对象或数据点的数目)超过某个阈值就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤噪声和孤立点数据，发现任意形状的类。DBSCAN[25](Density Based Spatial Clustering of Applications with Noise)算法是一个有代表性的基于密度的方法。 (4).基于网格的方法(Grid-based Method) 基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这种方法主要的优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中每一维上的单元数目。基于网格的有代表性的算法包括：STING(Statistical Information Grid)算法，Wave Cluster算法，CLIQUE(Clustering In QUEst)算法等。 (5).基于模型的方法(Model-based Method) 基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。这样的方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要有两类：统计学方法和神经网络方法。 (6).孤立点分析 经常存在一些数据对象，它们不符合数据的一般模型，这样的数据对象被称为孤立点(outlier)。孤立点可能是度量或执行错误所导致，也可能是数据突变的结果。许多数据挖掘算法试图使孤立点的影响最小化，但由于噪声与信号的相对 21
基于WEB挖掘的聚类搜索引擎研究 性，孤立点本身有可能包含重要的信息，因此在某些情况下，如金融和商业欺诈检测，网络入侵异常监测等，孤立点分析就显示出重要的作用。孤立点挖掘可以描述如下：给定一组n个数据对象的集合和预期的孤立点数目k，发现与其它的数据相比是显著差异的、异常的、或不一致的前k个对象。孤立点挖掘问题可以看作在给定的数据集合中定义孤立点并找到一个有效的方法来挖掘这样的孤立点。 当聚类算法将孤立点作为噪声剔除时，从另一方面看，同时也进行孤立点的探测。因此，孤立点分析也成为一类数据聚类问题。基于计算机的孤立点分析方法分为三类：统计学方法、基于距离的方法和基于偏离的方法。 聚类的有效性 聚类是要发现数据中潜在的分组，因此，发现聚类是否有效是聚类分析中重要的一环。在评价聚类结果时，适合数据的最优的聚类个数是评价聚类有效性的一个重要方面。尤其是对于多维特征向量的模式，不能直观的看出聚类效果，需要用多种指标对其进行衡量。 依据聚类的基本原则，提出了许多聚类评价指标。以下是一些常用的有效性评价指标：(1)聚类中心的距离矩阵；(2)各聚类域中样本与聚类中心的距离方差，方差越小，表明聚类效果越好；(3)改进的 Hubert统计法；(4)分离系数；(5)分离熵指标；等等。 在数据挖掘中，聚类分析是一个活跃的研究领域。本节介绍了聚类分析的数据结构和数据类型，聚类算法的分类，详细阐述了数据挖掘中用到的主要聚类算法，最后对聚类结果的评价方法进行了简要介绍。 22
第三章 Apriori算法及其改进算法 第三章 Apriori算法及其改进算法 引言 近年来，随着数据库技术，人工智能和数理统计技术的发展，数据库中的知识发现(KDD)和数据挖掘技术(DM)应运而生。数据挖掘是指从大量的数据中挖掘出隐含的，先前未知的，对决策有潜在价值的知识和规则的高级处理过程。通过数据挖掘，有价值的知识，规则或更高层次的信息就能数据库的相关的数据集合中抽取出来，并从不同的角度显示，从而使大型的数据库作为一个丰富，可靠的资源为知识的提取服务[26]。 关联规则的概念和模型是首先由等人在1993年提出来的[27]，是对一个事物和其他事物的相互依存和相互关联的一种描述[28]。针对数据而言是发现数据中项集之间潜在得关联或依赖联系。提出的Apriori算法也是关联规则挖掘算法中最有影响[4]，最著名的算法。其核心就是用前一次扫描数据库的结果产生本次扫描的候选项目集。但是由于数据库的规模通常很庞大，所以每次迭代时产生候选项目集来统计其支持度是非常耗时的。 根据Apriori算法之后提出了很多的算法，但是这些算法都是对所有的项目和项目集都只有一个最小支持度。但是在实际的应用中，支持度阈值需要项目的不同来改变。例如，对于商场中的所有的商品数据库，对于那些便宜的或者是日用品的最小支持度可能就要比那些昂贵的商品的最小支持度阈值要高。如果那些昂贵的商品的支持度阈值和便宜的商品的支持度阈值一样的话，昂贵的商品的关联规则就会被忽略[29]。 Apriori算法 Apriori算法在发现关联规则领域有很大的影响力。算法命名是源于算法引用了频繁项集性质的先验知识。在具体实现时，Apriori算法将发现关联规则的过程分为两步：第一步是通过迭带，检索出源数据中的频繁项集，即支持度不低于用户设定的阈值的项集；第二步是利用第一步中检索出的频繁项集构造出满足用 23
基于WEB挖掘的聚类搜索引擎研究 户最小信任度的规则。其中，第一步即挖掘出所有频繁项集是该算法的核心，也占整个算法工作量的大部分。 产生频繁项集 Apriori算法产生频繁项集是采用迭带的方法实现的。每一次迭带包括两个步骤：产生候选集；计算和选择候选集。第i次迭代计算产生出所有频繁i项候选集，包含i个元素。 在第一次迭代的第一步中，产生包含所有1-项集的候选集，即源数据中所有的项。通过对支持的搜索，计算出支持度。然后，选择支持度大于所需阈值的1-项集为频繁项集。这样，通过第一次的迭代，得到所有频繁1-项集。 在第2次迭代中，基本上将所有成对出现的项都作为候选项集。但在第一次迭代中所获得的非频繁项集的基础上，除去这些非频繁项集，来减少候选集的树木。这样做的原理是基于Apriori算法的一个特殊的性质，即如果一个项集是频繁的，那么它的所有子集也是频繁的，反之，任何一个含有非频繁项集子集的项集，都是非频繁项集。通过i次迭代，就可以产生i项频繁项集。 产生频繁项集实例 假定数据库中有项目{A，B，C，D，E}，支持度阈值s=50%，过程如下：表 3-1 Apriori算法的第1次迭代 -1 Apriori Algorithm for the 1st Iteration 24
第三章 Apriori算法及其改进算法 (1)第1次迭代，产生大1-项集。在进行第1次迭代时，首先产生1-项集C1，如表3-1(a)所示。然后，算法计算没一个候选集的出现次数并计算支持度，如表3-1(b)所示。最后，选择支持度s≥50%的大1—项集L1，如表3-1(c)所示。 表 3-2 Apriori算法的第2次迭代 -2 Apriori Algorithm for The 2nd Iteration 25
基于WEB挖掘的聚类搜索引擎研究 (2)第2次迭代，产生大2-项集。在Apriori算法中，使用L1*L1产生候选项集，“*”运算定义为：Lk * Lk={X∪Y，X与Y∈Lk，∣X∩Y∣=K-1} 当K=1时，该运算为单连接，设C2为包含在第2次迭代中产生的2－项集。按照上述公式，应该为∣L1∣·(∣L1∣-1)/2。在此例中为4×3/2=6。因此，产生6项的2—项集C2，如表3-2(a)所示。计算支持度如表3-2(b)所示，选择支持度s≥50%的大2-项集L2，如表3-2(c)所示。 (3)第3次迭代，产生大大3-项集。候选项集C3可以使用运算L2*L2产生，而实际上，在经过第2次迭代后，产生的大2-项集总，只有｛B,C｝和｛B,E｝是第1项相同的大2-项集。由｛B,C｝和｛B,E｝组成的第2项集｛C,E｝由于也是大2-项集，所以｛B,C,E｝的所有子集都是大项集，｛B,C,E｝就成为一个候选3-项集。没有其他的候选3-项集，经过计数，得到如表3-3所示的大3-项集。 表 3-3 Apriori算法的第3次迭代 -3 Apriori Algorithm for The 3rd Iteration 因为在此例中L3无法产生候选的4-项集，所以算法到此停止迭代。Apriori算法不仅计算所有频繁项集的支持度，也计算那些在删减过程中不会被排除的非频繁候选项集的支持度。所有这些非频繁但由Apriori算法的支持度的候选项集的集合被称为负边界。如果项集是非频繁的，但它的所有子集都是非频繁的，那么它就在负边界中。 Apriori 算法如下： (1) L1={频繁1项集}； (2) for(k=2；Lk-1≠Φ ；k++) do begin 26
第三章 Apriori算法及其改进算法 (3) Ck =apriori_gen( Lk-1)；// 新的潜在频繁项集 (4) for all transactions t ∈D do begin (5) Ct =subset(Ck ,t)；// t 中包含的潜在频繁项集 (6) For all candidates c∈Ct , do (7) ++； (8) end； (9) Lk={c∈Ck |>=minsup}； (10) end； (11) Answer=∪Lk 利用最大约束条件的多最小支持度改进算法 传统Apriori算法的挖掘过程，可以总结如下三个阶段： （1） 确定用户给定的阈值，包括最小支持度阈值，最小置信度阈值。 （2） 利用迭代找到最大项目集。最大项目集的计数必须要大于等于最小支持度阈值。 （3） 利用最大项目集来产生关联规则，产生的规则的置信度要大于等于最小置信度阈值。 改进算法的主要的步骤如下： 输入：数据库D，最小置信度，各个项目的最小支持度阈值。 输出：感兴趣的关联规则 （1） 计算给定事物的计数，得出所有项目的支持度值。 （2） 检查每一个项目的支持度，将支持度值大于等于项目最小支持度的放入最大1-项集L1中。 （3） 类似于Apriori算法通过Lr生成的候选集Cr+1，计算这些候选集的支持度，支持度要大于等于候选集中项目的给定最小支持度阈值的最大值。这个项目集就可以就可以加入到最大Lr+1-项集中去。如果Lr+1为空，则停止。 （4） 构建关联规则。 （5） 输出关联规则。 （6） 利用confidence-lift模式输出关联规则中感兴趣的规则[30]。 27
基于WEB挖掘的聚类搜索引擎研究 我们在原先算法的基础上在算法的最后一步加入Ming-Cheng Tseng 中提出的confidence-lift模式，来求出关联规则中我们感兴趣的规则。 实验比较 下面给出具体的事例来演示这个算法。给定用于挖掘的10个事务如表格3-4所示。假定每一个项目的最小值支持度阈值如表格3-5所示。假设最小置信度阈值为。 表3-4 事务集合 Tab 3-4 Collection of Things TID Item 1 ADFG 2 FDC 3 BCEFG 4 ACDF 5 BCEFG 6 ACF 7 CDEG 8 CF 9 BCFG 10 CDEF 表3-5 各个项目的最小支持度阈值 Tab 3-5 Minimum Support Threshold of Each Item Item A B C D E F G Min-Sup 按照算法中给出的步骤，首先由给定的事务集合求出各个项目的支持度(如表格3-6所示)，根据给定的项目的最小支持度阈值来去除不符合要求的项目。就G来讲，G的计数是6，则支持度是6/10=。然后将这些支持度值与给定的阈值相比较，得到A,B,C,E,F是符合要求的，将其放入最大1-项集中。由L1得28
第三章 Apriori算法及其改进算法 到候选集C2。在C2中每两个项目集中的项目的支持度要大于等于这两个项目最小支持度的最大值。拿{C,F}为例，C和F的支持度分别是和，要比C和F的最小支持度阈值的最大值要大，因此可以将{C,F}加入到候选集C2中。利用同样的方法可以得到C2={{E,G},{C,G},{C,F},{B,E}}.然后计算C2中的支持度计数，如表格3-7所示。将C2中的候选项集的支持度值与项集中所包含的项目的最小支持度阈值进行比较，若是大于最小支持度阈值的最大值则可以放入最大2-项集中。以{B,E}为例，{B,E}的支持度值是，B和E的最小支持度阈值分别是和，都小于这两个最小支持度阈值，因此{B,E}不可以放入最大2-项集中。用同样的方法我可以得到最大2-项集是L2={{E，G}，{C，F}}。按照上面对方法得出候选3-项集为空，则停止计算。 表 3-6 项目的支持度值 Tab 3-6 Support of The Project Value Item A B C D E F G 表 3-7 候选2-项集项目的支持度值 Tab 3-7 Support of Candidate 2-itemsets Project Value 2-Itemset E,G C,G C,F B,E Support 得出了频繁项集后，我们就可以求出关联规则，分别计算频繁项集的置信度值，如下： E G的置信度为 SE G EG E的置信度为 SE G 1 GF C的置信度为 SC F F的置信度为 SC F .由于给出的最小置信度值为，因此可以得到强关联规则G E和F C。在利用confidence-lift模式求出则两个关联规则对我们有利的关联规则。 29
基于WEB挖掘的聚类搜索引擎研究 在confidence-lift模式中给出一个参数lift来确定一个关联规则是否是对决策者有利的，也就是确定这个关联规则是否是有兴趣的。具体的公式如下： 如果一个强关联规则是有兴趣的当且仅当( ) s uGp(F )c o nf(G)FliftGsuGFp1 ! (F)sup(F)sup()利用这个概念我们可以求出强关联规则E G和F C是否为有兴趣的。 ( )c on f(E G)1liftEGG sup6 1 !()0. ()conf(FC) C supC 1 ()这样我们就可以得到E G是我们所感兴趣的强关联规则。 小结 数据挖掘简单的说就是从大量的数据中提取有利的信息，本章引用了Yeong-Chyi Lee的在最大值约束条件下的多个最小支持度关联规则挖掘算法，在此基础上进行改进，输出我们感兴趣的关联规则。通常情况下生成的关联规则不一定就是对决策者有用的关联规则，通过利用confidence-lift模式来求出我们有兴趣的关联规则，这样更有利用于决策者做出决定。 30
第四章 Web文档聚类 第四章 Web文档聚类 本聚类的概述 作为一种无监督的机器学习方法，聚类技术已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来越多的研究人员所关注。 文档聚类[31]是一种无指导的文档归类方法，它把一个文档集划分成若干个称为集簇的子集，每个集簇中的文档成员之间具有较大的相似性，而集簇之间的文档具有较小的相似性，用户可以在自己感兴趣的集簇中查看结果。作为一种无监督的机器学习方法，文档聚类技术把大量的文档划分成用户可以迅速理解的簇，从而使用户可以更快地把握大量文档中所包含的内容，加快分析速度并辅助决策。大规模文档聚类是解决海量文本中数据理解和信息挖掘的有效解决手段之一，已为越来越多的研究人员所关注。 文本聚类的应用方面有很多： (1) 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤，比较典型的例子是哥伦比亚大学开发的多文档文摘系统。将每天发生的重要新闻文本进行聚类处理，并对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档。 (2) 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。 (3) 对用户感兴趣的文档(如用户浏览器cache中的网页)聚类，从而发现用户的兴趣模式并用于信息过滤和信息主动推荐等服务。 (4) 聚类技术还可以用来改善文本分类的结果。 (5) 数字图书馆服务，通过SOM神经网络等方法，可以将高维空间的文档拓扑保序地映射到二维空间，使得聚类结果可视化和便于理解，如SOMlib系统。 (6) 文档集合的自动整理。如Scatter/Gather是一个基于聚类的文档浏览系统。而微软的Ji-Rong Wen等五人则利用聚类技术对用户提出的查询记录进行聚类，并利用结果更新搜索引擎网站的FAQ。 31
基于WEB挖掘的聚类搜索引擎研究 聚类算法在搜索引擎中的应用特点 聚类算法的分类在章节中已做过具体介绍，再此不再重述。 借助于文档聚类技术，可以对已经检索到的Web文档进行聚类。Web 文档聚类即是把搜索引擎所返回的检索结果按照一定的依据进行聚类，创建类目体系，同类文档相似性大，异类文档相似性小。然后再把类目呈现给用户，使用户能在更高的主题层次上来浏览结果，从与主题相似的文档形成的类中选择相关的Web 文档。 传统的搜索引擎返回的结果是基于网页级别的，用户还是得从大量的线形表示的结果中选择所需信息，现在的大多数搜索引擎都是基于网页级别这个机制。我们要试图改变搜索结果的显示形式，许多文档聚类依赖于离线的大量文档，而搜索引擎返回的结果量也是非常之大，但是它需要支持在线查询，所以选择的聚类必须满足一些关键条件。 以什么算法进行聚类分析是本文要解决的关键问题。由于大多数聚类算法复杂度是聚类文档数的二次方，满足不了在线聚类的速度要求，而且这些聚类算法把文档看作是单词的集合，而不是有序的单词序列，这样会丢失一些有价值的信息。我们要找到一种线形的聚类算法模型间，在不增加搜索引擎的资源需求的前提下将搜索结果进行聚类。这个模型需要满足如下的关键要求： (1) 聚类一致性：这个聚类算法要将所有类似的文档聚到一类，把与用户查询条件相关的文档与不和关的文档分开。 (2) 浏览高效性：用户一眼就可以找到自己感兴趣的聚类内容，所以模型需要提供简明精确的聚类描述。 (3) 重叠性：因为文档通常有多个主题，所以它们不需要限制在一个单独的类，可以叠加聚类。 (4) 快速性：聚类算法应该能够快速聚类摘要，在将查询结果显示给用户前不能有很大的延迟。可见，聚类的质量和速度与聚类算法的好坏有很大关系。 32
第四章 Web文档聚类 关键词组的提取 问题的提出 数据提取直接影响到检索的方式和效果。目前，搜索引擎都是基于关键词组的搜索引擎，因此关键词组提取(key phrase extraction)是搜索引擎的一个关键环节。同时，数据的特征提取(feature extraction)也是聚类研究中一个很重要的问题。这是因为，为了有效地进行数据挖掘，一般需要先进行数据的特征提取，也就是对原始的数据进行变换得到最能反映其本质的特征。数据的特征提取直接影响挖掘算法的设计及其性能。对聚类来说，如果不同类别的数据在这些特征上差别越明显，那么就越容易设计出效果较好的聚类算法。 在现实世界中信息是以自然语言来表达的，例如互联网上许许多多的网页文档。一般的信息检索技术是将自然语言文档看成词的集合(set of words[32])，如果按照这种方式，即在词层次上进行特征提取，虽然可以使模型得到简化，但是会丢失词与词之间的邻近(proximity)关系和顺序((order)关系等重要信息。从自然语言处理(natural language processing)角度看，语言单位的层次越高，其蕴藏的语义信息越丰富，而所需的语言模型会越复杂。 英文与中文的语言单位层次对应如下： English：word phrase sentence paragraph document 中文： 字 词 词组 句子 段落 篇章 定义〔词组)：词组印hrase)是指有顺序的多个词所组成的造句单位，它是比词更高一级的语言单位。 定义 (关键词组)：一个文档的关键词组(Key Phrase)是指最能概括文档内容的那些词组。 定义 (关键词组提取)：从文档中找出关键词组的过程称为关键词组提取(Key Phrase Extraction)。 在词组层次上进行特征提取实际上就是以文档的关键词组作为该文档的特征。我们认为，以关键词组作为文档的特征能够给文档聚类带来两个重要的好处： (1)能够体现文档中更多的信息，从而提高聚类的合理性； (2)能够简明准确地描述各个类，从而提高聚类的可读性。 33
基于WEB挖掘的聚类搜索引擎研究 对英文信息来说，仔细研究了词组在文档聚类中的作用[33]。他对大量英语文档分别以关键词和关键词组为特征进行聚类，实验结果表明以关键词组为特征能够显著提高各种聚类算法(如Random Clustering, Fractionation, GAVG, Single Pass, Buckshot, K-Means, STC等)的平均准确率(average precision)。 还进一步通过实验指出：词组的作用不能被固定长度的低阶n元字符串(n-gram)或者无序的单词集合((word set)所代替，这就是说词组“不定长”和“有顺序”的特点对提高文档聚类的效果都具有实质性贡献。 而中文信息与英文信息不同，它们间有一个很大的区别：中文书面语是按句连写的，词与词之间没有空格分隔，而英文的词与词之间则有空隔。这意味着计算机面对的中文句子是连续的汉字序列，而非分隔开来的各个词。要对中文信息在词层次上进行特征提取，就必须让计算机在词与词之间自动加上空格，把汉字的序列切分成为词的序列，这就是所谓“中文自动分词”工作[34][35][36][37]。由于中文存在分词问题，因此对中文信息的处理比对英文信息的处理更加复杂。 中文自动分词长期以来一直是中文自然语言处理的研究热点，它看上去很简单实际上却非常困难，如或者多个词组成)实际上都是明确含义的汉字组合 (序列模式)。在本论文中，中文词组都是广义而言的。这样就可以认为词组直接由汉字构成，对中文信息就可以直接在词组层次上进行特征提取，从而跳过了中文自动分词的困难。 基本思想 关键词高度概括了文本的主要内容，易于使不同的读者判断出文本是否是自己需要的内容。不仅如此，由于关键词十分精练，故可以利用关键词以很小的计算代价进行文本相关性度量，从而高效地进行信息检索、文本聚类和分类等处理[38][39][40]。 在这方面应用最广泛的还是文本检索。在搜索引擎中输入关键词，系统将出现此关键词的所有文本返回给用户。国外对于关键词的研究起步较早，已经建立了一些实用或实验系统。Turney等设计了GenEx系统，它将遗传算法和决策树机器学习方法用于关键短语的提取；Witten等开发了系统KEA，它采用朴素贝叶斯技术对短语离散的特征值进行训练，获取模型的权值，以完成下一步从文34
第四章 Web文档聚类 档中提取关键短语的任务"在实际研究和应用中，通常所说的关键词实际上有相当一部分是短语。短语比词更具有概括能力，包含的信息更加丰富，研究关键词短语的提取具有更加重要的意义。Turney和Witten的研究都把文本中连续出现的几个词序列看成候选关键词短语，但并未充分考虑这些词序列是否符合人们习惯认可的短语形式。 一种比较常见的研究方法是通过统计N2gram词性匹配模式的方法来提取关键词短语；另外一个相关的研究领域是Chunk的自动识别，但Anettehelth指出通过自动识别的方法难以获得符合人们习惯的关键词短语，为此她人工总结了56个词性匹配模式，用于英文关键词短语的自动提取。从国内看，由于汉语语言本身的特点，没有显式的词边界，为关键词自动标引任务又增加了一定的难度"目前主要的工作包括：基于PATTree结构获取新词，并采用互信息等统计方法对文档的关键词进行标引，但获取候选词选用的PATTree，它的建立用计算机实现时需要大量的空间消耗；李素建等提出的利用最大熵模型进行关键词自动标引的方法，由于特征选择和特征参数估计时不够准确，造成关键词自动标引应用时不够理想；王军提出了一种用于自动标引的文献主题关键词抽取方法，它限于从已标引的结构化语料库中元数据的标题中抽取关键词；索红光等提出了利用知网知识库构建词汇链的方法，但这种方法只适用于收录在《知网》中的关键词。 35
基于WEB挖掘的聚类搜索引擎研究 第五章 利用频繁项集进行Web文档聚类 引言 随着WWW的飞速发展，互联网上出现了海量的Web 信息资源。为了使人们有效的利用这些资源，搜索引擎便问世了。搜索引擎的出现给人们带来了很大的方便，但同时也暴露出一定的问题，搜索结果不能很好的满足用户需求。因此，Web文档聚类技术受到了人们的广泛关注。 Web 文档聚类主要有基于概率和基于距离的两类方法。基于概率的方法以贝叶斯概率为理论基础[41]，用概率的分布方式描述聚类结果，可以处理类间相互重叠的情况；缺点是当特征空间维数较高或特征值间呈现出较强的相关性时，聚类精度和效率均不能令人满意。基于距离的方法[42]，如K-均值和最近邻等，都以传统的特征向量表示文档，再将文档看作是向量空间中的一个点，通过计算点之间的距离进行聚类，比较形象直观；缺点是特征向量必须经过规范化处理以避免由于文档长度不同或各个文档间关键词出现的频度各异而产生的畸变，特别是当数据维数较高时，聚类的质量和算法的性能都明显下降。 Web文档聚类可以有效地压缩搜索空间，加速检索速度，提高查询精度。因此，文档聚类是Web挖掘的一个重要研究方向。文档聚类与分类的不同之处在于，聚类是一种无监督的文档分类，聚类没有预先定义好的主题类别，它的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能大，而不同簇间的相似度尽可能小。文档聚类是搜索引擎的关键技术，Hearst 等人的研究已经证明了“聚类假设”，即与用户查询相关的文档通常会聚类得比较靠近，而与用户查询不相关的文档则相隔得比较远 。因此，可以利用文档聚类技术将搜索引擎的检索结果划分为若干个簇，用户便可以在自己感兴趣的簇中查看结果，或者根据聚类情况提出更精确的查询。 针对上述问题，本章将介绍一种新颖的聚类方法，利用频繁项集进行Web文档聚类[43]。此类频繁项集可以利用关联规则挖掘算法中的Apriori算法极其改进算法而有效的获得。这种方法通过发现频繁特征项集对文档的维数进行约减，提高了算法运行的准确率和速度；而且频繁特征项集可以对文档类别进行较精确36
第五章 利用频繁项集进行Web文档聚类 的描述，有效地提高了聚类的性能，并且能够处理文档类之间存在的固有重叠情况。 文档表示模型 频繁特征项集是关联规则挖掘算法的基础，很多有效的算法曾被提出，如Apriori算法。基于频繁项集的聚类方法是可行的，因为它提供了一种自然的方法来降低文档向量空间的维数。 计算机与人类的区别在于无法在阅读完成后产生自己的理解。这就要求我们必须将文档表示成计算机可识别的模式。文档聚类首先需要对文本信息进行预处理，预处理技术包括分词(中文)，特征表示和特征提取等[44]。文档中存在很多非结构化信息，以一定的特征项来表示文档从而实现对非结构化文档的处理。 本章采用文档向量空间(VSM)对文本进行表示，向量空间模型可以将文本表示成特征项和特征项权重组成的向量，从而把聚类问题转化成向量计算问题。 如：包含n个特征项的文档D，D可以表示为：{t1;w1，t2;w2……ti;wi……tn;wn}，其中ti为文本特征项，wi为特征项 ti的权值，i ∈[1,n]；文档D的特征项的集合 TD ={ t1 , t2, „, ti , „, tn }；文 档D的特征向量WD =[w1, w2, „,wi, „, wn ] 。文档D和其特征项集合TD的维数都为 n，即|D| = | TD |=n。对文档D特征项集合TD和特征向量WD的第i项亦可分别用D[i]、TD [i]和WD [i] 表示，即D[i] = ti:wi ，T [i] =ti，W[i] =wi。 特征项的获取 将每个搜索结果看作一个文档，将其中的每个单词看作一个项目，将整个搜索结果看作一个数据库。在这样的模型中所挖掘出的文本特征项集包含的是在一篇文档中频繁同时出现的单词。 句子作为一个语法单位在句法上独立，并表达了某个基本的语义，而一篇文档的中心思想也是通过组织句子的基本语义来表达的。同时出现在一个句子中的单词之间存在着或多或少的语义联系，并且与在同一文档中几个句子中出现的单词相比，出现在同一句子中的单词集包含了更多的局部信息，并具有更多的语义相关性，因而更适合作为文档的特征项。 37
基于WEB挖掘的聚类搜索引擎研究 基于以上的分析，我们将每个单词被看作一个项目，每条搜索结果被看作一个事物，而所有搜索被看作是一个数据库。利用Apriori算法及其改进算法可以挖掘出以一条搜索结果为事物的频繁单词(项目)集，把其作为特征项，来进行聚类。但当文档数量很大时，其所包含的频繁单词集也将非常多，由于最大频繁单词集包含了所有的频繁单词集，且数量远远少于频繁单词集，为了减少计算规模，利用最大频繁单词集来代表搜索结果的特征项，再在此基础上对文档进行聚类。 挖掘最大频繁单词(项目)集 将搜索结果转化成文档数据库模型，需要对每个文档进行数据预处理(参见)。然后利用Apriori算法及其改进算法挖掘最大频繁单词(项目)集[45]，并将这些单词作为文档的特征。和传统挖掘算法不同的是[46][47]，本章介绍的挖掘算法是建立在文档数据模型上的。 算法如下： (1) L1={频繁1项集}； (2) for(k=2；Lk-1≠ Φ ；k++) do begin (3)DjCk =apriori_gen( Lk-1 ); // 新的潜在频繁项集 (4) for all transactions t∈D do begin (5) Ck =subset(Ck ,t); // t 中包含的潜在频繁项集 (6) For all candidates c∈ Ct , do (7) ++; (8) end; (9) Lk={c∈Ck |>=minsup}; (10)end; (11)Answer=kL k算法遍历所有的搜索结果文档，对每个文档进行最大频繁项目集的挖掘，挖掘出每个文档的所有最大频繁单词集，得到每个文档的特征项目集。 38
第五章 利用频繁项集进行Web文档聚类 建立特征项矩阵 挖掘出每个文档的最大频繁单词集后，必须得对文本特征向量进行规范化表示，并计算特征项的权值，也就是最大单词集表示文档的近似程度。 给定一个包含 N 个文档的集合Ω= { D1, D2, „, Dn}，其特征项的集合记作T :，档集合Ω所包含的全部最大频繁单词集的数量为 m，对于T : N。文 T1Dii任意一个Di ∈Ω，需要对其规范化，把规范化后的文档记D，其生成方式如下： i'TD'[k] T [:k]iWk W↑°→D[ p],TD[k]T&[k] T[p] ''[]iDTiDiDiD'i0,°↓T[k] Tζ'iDi其中，1≤i≤N ，1≤k≤m，1≤p≤| Di|。 规范化后的文档的集合记作Ω={D1，'D'2……D'n}。Ω的特征项矩阵： W[WD'1,W D'2,,WD'N][wij]m:N υ其中 1≤i≤m，1≤j≤N。Wij表示第i项单词集 属于第j个文档的权值。应用 TF. IDF方法得到Wij的值： Ntlogυ♣ •ij2 ♦i♥÷nw ≠ij。 2mƒ N •÷k 1 ni ≠特征项矩阵WΩ可以看成是由 N 个文档特征列向量组成的。 利用频繁特征项集进行Web文档聚类 定义 将所有搜索结果作为文本文档数据库记作Ω={D1,D2,……Dn},并且将所有在Ω中出现的单词集记作T。每个文档Di被出现在Di中的单词集所描述。赋予 39
基于WEB挖掘的聚类搜索引擎研究 minsupp一个初值：0≤minsupp≤ 1。对任意单词集S，S T，让cov(S)表示S的一个覆盖，文档集合包含S的所有单词。如：所有文档的项集支持S，则cov(S)= {Dj∈Ω/S Dj }，令F={F1……Fk}表示文档D中对应满足最小支持度的规范频繁单词集，F={Fi T/∣cov(Fi) ≥ minsupp.∣Ω∣} 聚类过程 令Uij=Fi*Fj，点乘的结果越大，说明两文档的相似性越高，给定初值minu，当Uij≥minu时，我们初步认定Di与Dj相似，并且相似具有传递性。 由于点积的计算速度很快，因此可以很快确定初步聚类，初步聚类的计算速度还和阈值的选择有关，如果阈值选择太大，算法速度很快，但会把所有的文档分到同一个类中；阈值选择得太小，则会把所有的文档分到不同的类中。太大或太小的阈值都会导致初步聚类不理想。 通过初步聚类，可将文档集 表示成Ω={ C1, C2, „,Ch} ，h为初步聚类的类别数。但是初步聚类只是通过粗略的计算得到的，如果一个文档向量的权值太大，会影响其它的文档和它的相似性的判断结果。要得到精确的聚类结果，必须对初步聚类的结果进行更精确的聚类。在进行精确聚类以前，需要计算每个类的特征向量。 对初步聚类得到的文档类进行确认分为两步： (1) 计算不同文档类之间的相似度，对类间相似度不小于指定阈值 min- sim的类进行合并。 (2) 计算文档类内的内聚度，对内聚度不大于指定阈值 maxcon的类进行拆分。 给定包含 h个类的文档的集合Ω={ C1, C2, „, Ch}，对于任意两个类 Ci和 Cj，它们之间的相似度sim(Ci,Cj)如下： mW ƒ [k] Wυ[k]cc ijk1simC,C ij mW22[k] υƒW[k]ƒk1 40
第五章 利用频繁项集进行Web文档聚类 其中，Ci∈Ω,Cj∈Ω，1≤i≤h，1≤j≤h。 类间相似度反映两个文档类的耦合程度，相似度的取值范围在[0,1]之间，两个类越相似则相似度越大，反之则相似度越小。内聚度实际上反映了某文档对其所属类贡献的大小，内聚度越大则表明该文档对类的贡献越大，反之则表明该文档对类的贡献比较小。贡献小的文档自然应该从所属类中去除。通过设置阈值可把对类贡献不大的文档从当前类中分出去。 算法描述 算法首先得到每个文档的特征项和支持度，然后对挖掘结果进行规范化，得到新的文档的特征项集合，并计算每个特征项的权值，为了降低算法的计算规模，先对文档集合进行初始聚类，对于结果要求比较粗糙的应用，此时算法即可结束。对于结果要求比较精确的应用，再在上述结果基础上进行精炼，根据类间相似度和类内内聚度，循环对聚类结果进行合并和拆分，直到得到稳定的输出。算法描述如下： 1) Ω= { D1 D2, …, Dn},num = 0 2 ) for each Di∈Ω do TDi = Max-Miner( Di) / / 计算最大频繁单词集 3) 规范化Ω={ D1’,D2’,…,Dn’}；计算each Wij并生成特征项矩阵 4) for each (D∈Ω,∈Ω)andD≠do i'D 'ji'D'j5) if Uij≥minu then Unite(D,,Ω) i'D 'j6) end for 7 ) for each Ci∈Ω 计算其特征向量 8 ) do 9) num=∣Ω∣ 10) for each (Ci∈Ω,Cj∈Ω)and Ci≠Cj do 11) if sim(Ci,Cj) ≥minsim then Unite(Ci,Cj,Ω) 12) end for 13) for each Ci∈Ω do 14) for each Dk∈Ci do 41
基于WEB挖掘的聚类搜索引擎研究 15) if con(Dk,Ci)≦maxcon then Split(Ci,Dk,Ω) 16) end for 17) end for 18) while(num= =∣Ω∣) 在算法中的函数Max-Miner为计算最大频繁项目集的经典算法，用来计算某个文档句子级的最大频繁单词集。函数Unite用来合并两个类或者两个文档，合并后将产生一个新的类，该类将包含原来的两个类中所有的文档，合并后特征项的权值为原来特征项权值的和，把合并后的类并入文档集合Ω，并把原来的两个类从文档集合Ω中删除。函数Split 则把文档Dk从类Ci中分出来，变成两个独立的类，把原来的类Ci从文档集合Ω中删除。 42
第六章 基于Web挖掘的聚类搜索引擎介绍 第六章 基于Web挖掘的聚类搜索引擎介绍 设计原理 基于Web挖掘的聚类搜索引擎研究，其难点在于互联网环境的复杂性(分布、自治、异构、动态)和互联网数据的复杂化 (不规则、不精确、不稳定、半结构化或非结构化)。传统的搜索引擎无法很好的满足人们的查询需求。为了方便用户从搜索引擎的检索结果中快速、准确地获得自己所需要的信息，对其搜索结果进行聚类分析的必要性越来越明显。 基于Web挖掘的聚类搜索引擎要求及时的响应用户查询，因此，合理高效的聚类算法的应用将十分重要；根据处理信息的内容来看，进行语意聚类，使之能够直接汇聚具有指定特征或含有特定内容的信息。聚类后赋予每个类一个关键词组来简明且准确地概括类内信息的共同主题(Topic)，使用户看到关键词组就能了解这个类的内容，类与类之间应该允许重叠，即若某条信息涉及多个主题则可以属于多个类；聚类分析后，显示给用户的搜索结果应该具有合理的结构，以便于用户通过几次点击就可以获得自己所需要的信息，树型结构便是比较理想的显示模式。 体系结构 基于Web挖掘的聚类搜索引擎的体系机构如图6-1所示。 (1) 用户输入所需查询，利用搜索引擎对互联网信息进行检索； (2) .利用元搜索引擎，对一个或者多个独立搜索引擎的数据库或检索结果进行二次加工，相当于对检索结果进行一次数据清理； (3) 对元搜索引擎的检索结果利用一定的聚类算法进行聚类(聚类搜索引擎所做工作； (4) .将聚类搜索引擎聚类后的信息，以树型的形式反馈给用户，以便于用户的查询。使用户可以迅速、准确的获得自己所需要的信息。 43
基于WEB挖掘的聚类搜索引擎研究 用户 查询 聚类树 聚类搜索引擎 元搜索引 擎 搜索引擎 搜索引擎 搜索引擎 ……… „ 互联 网 图6-1 聚类搜索引擎系统结构 Fig 6-1 Clustering Search Engine System 数据获取 通过元搜索引擎获取数据(参考)，即将用户提出的查询 (一般是关键词组的逻辑表达式)转交给多个搜索引擎，依靠搜索引擎得到相关Web信息的列表。 为了满足及时响应，应该尽量提高数据获取的速度，因此，可以利用多线程的方式作并行元搜索，也就是并行地调用多个搜索引擎。另外，搜索引擎一般通过动态生成的HTML网页返回搜索结果，然而搜索结果往往很多，必须多个网页才能放得下。如果串行地从一个搜索引擎取回其搜索结果网页，那么将需要较长的网络通信时间。 因为对同一个查询的不同搜索引擎返回的搜索结果列表有所不同，一项搜索结果往往只在某些列表中出现，而且往往出现在不同的位置，所以需要将来自各个搜索引擎的搜索结果列表综合起来，重新排序(Re-rank)形成一个统一的搜索结果列表。我们在此采用一种简单而有效的重新排序算法(Re-ranking algorithm)最高位置算法(Highest-rank Algorithm)。最高位置算法检查每一项搜索结果，以它在各个搜索引擎返回的搜索结果列表中出现的最高位置作为它的行44
第六章 基于Web挖掘的聚类搜索引擎介绍 号，并删除它在其它位置的出现，如此直到各个列表都没有重复的项出现，然后将所有搜索结果按照行号顺序排列成为一个统一的列表，其中行号相同的几项搜索结果可以根据其最高位置所在的搜索引擎的优劣顺序排列。 数据清理 搜索引擎的搜索结果中一般包括相关Web信息的URL，标题和摘要等。所谓数据清理就是将Web信息的标题和摘要合在一起作为一个“文档”，以这个“文档”来表示Web信息的主要内容。 例如，搜索引擎Google(htttp:// 图 6-2搜索结果 Fig 6-2 Search Results 为了满足及时响应，用户在下载所有相关Web信息的网页得到完整内容时，用户等待的时间不能很长。但是，如果用户可以通过相关Web信息的URL访问网页，从而浏览该Web信息的完整内容，用户就要等待很长时间，这违背了“在线的”准则，实际上，搜索结果中包括的相关Web信息的标题和摘要就是起内容很好的总结。因此，我们可以将一个Web信息的标题和摘要合在一起作为一个“文档”，以这个“文档”来表示该Web信息的主要内容。这样，可以缩短用户浏览相关Web信息网页的等待时间。在下文中，我们所说的“文档”就是指这类文档。 在这一步要解析搜索引擎返回的搜索结果网页，得到相关Web信息各自对 45
基于WEB挖掘的聚类搜索引擎研究 应的文档(Web信息的标题和摘要)(参见)，接着以标点符号为边界把文档切粉成多个较短的字符串，并去掉其中多余的空格，为关键词组提取作好准备(参见 )。例如，在数据清理这一步完成后，图6-2的搜索结果对应的文档显示在图6-3中。 数据挖掘 从大量数据中获取有效的 新颖的 潜在有用的 最终可理解的模式的非平凡过程 从存放在数据库 图 6-3 相应文档 Fig6-3 Corresponding documents 聚类搜索引擎工作原理 聚类搜索引擎是针对元搜索引擎的搜索结果进行文档聚类，将聚类的结果以树型的形式反馈给用户。通过聚类搜索引擎，用户可以迅速而准确的获得自己想要的信息。从而提高了信息查询的工作效率。 通过元搜索引擎进行数据获取 (参见)，即将用户提出的查询 (一般是关键词组的逻辑表达式)转交给多个搜索引擎，依靠搜索引擎得到相关Web信息的列表。搜索引擎的搜索结果中一般包括相关Web信息的URL，标题和摘要等。将Web信息的标题和摘要合在一起作为一个“文档”，以这个“文档”做为Web信息的主要内容。再通过关键词提取(参见)获得关键词，构造差异度矩阵。 利用改进的Apriori算法(参见第3章)找出文档频繁特征项集，将其子集中的频繁特征词语作为候选聚类，而不是直接对高维的文档向量进行聚类，能够有效降低特征项的维数(参见第5章)。 为了满足“树型的”准则，将所有文档的标识组建成一棵树的形式，称之为文档的“聚类树”。其目的是为了进一步方便用户浏览与查找各个文档的类，缩短相关Web信息的浏览距离 。而且，聚类树与文件系统的树形目录结构非常相似，用户比较容易理解。以上是整个聚类搜索引擎的工作原理。 46
第六章 基于Web挖掘的聚类搜索引擎介绍 本章通过对聚类搜索引擎体系结构中各个模块的实现，验证了聚类搜索引擎设计的可行性；从整体上解析了聚类搜索引擎的工作原理。 47
第七章 总结与进一步研究展望 第七章 总结与进一步研究展望 论文工作总结 随着互联网技术在全球范围内的迅速发展与普及，网络信息资源日趋丰富现有的互联网信息检索技术和方法已经不能满足用户对信息的快速性与有效性的需求。把新的Web数据挖掘技术应用到搜索引擎中去，可使搜索引擎上升到新的高度，为Web信息的利用提出了新的解决方案。 本文通过对搜索引擎技术和数据挖掘相关知识进行了研究，改进了传统的Apriori算法，利用频繁项集进行Web文档聚类；并针对搜索引擎的一些不足，将聚类算法与搜索引擎相结合，引入了聚类搜索引擎。构建了一个基于Web挖掘的聚类搜索引擎原型系统，它能够以语义的、在线的方式对搜索引擎的搜索结果进行聚类，而且可以处理中文互联网信息。 进一步研究展望 搜索引擎技术涉及到计算机网络，人工智能，数据库，分布式处理，数据挖掘等各个领域，本文主要将聚类算法与搜索引擎结合起来，并开发了实际的原型系统，证明了设计的有效性，但是仍然存在许多问题作深入细致的研究： (1)在页面分析方面，本论文只是从页面所包含的关键词组进行了研究，即是对页面的语义信息进行了研究。如何对页面的语法结构，如页面内容描述方式、页面元数据、网站组织结构、页面组织结构等方面进行研究，即将语法结构分析纳入页面分析，是需要进一步研究的方向。 (2)由于系统对搜索结果的聚类是在线的，所以对速度和精确度的要求特别高，因此以后的研究过程中，应该引入更加优异的聚类算法。 (3)本文对搜索引擎的改进是限定在聚类这个特定的领域，其实在实际应用中，可以引入人工智能，分布式处理，自然语言处理等领域的最新研究成果，使搜索引擎具有智能，能代理每个用户，自动从网络上搜索到最符合每个用户特定需求的结果。48
参考文献 参考文献 [1] 汪挺.WWW信息查询技术展望[J].情报学报，(增刊)，1997. [2] S. Lawrence,C. L. and Distribution of Information on the Web[J].Nature,July,1999. [3] Pretschner, based Personalized Search[R].Proceedings of llth IEEE International Conference on Tools with Artificial Intelligence, 1999. [4] , .数据挖掘：概念与技术.[M]. 北京：机械工业出版社，2001. [5] Fayyad U., Discovery and Data Mining towards a Unifying ' 96 Int . Knowledge Discovery&Data Mining, AAAI Press,1996. [6] 安淑芝 等.数据仓库与数据挖掘[B].北京：清华大学出版社，2005：2-17. [7] M-S Chen,J. Han,P. S. Mining:An Overview from a Database Perspective [J].IEEE Trans on Knowledge and Data Eng., ,,1996. [8] David Hand, Heikki Mannida, Padhraic of Data Mining[M]. 北京：机械工业出版社,2003. [9] A. K. Jain and R. C. DubesAlgorithms for Clustering Data[M].Prentice Hall, 1988. [10] Raymond T. Ng, Jiawei and Effective Clustering Methods for Spatial Data Mining[M]. [11] Mitchell. Machine Learing[M].McGrarHill，1996. [12] U. M. Fayyad,G. Piatetsky-Shapiro, Data Mining to Knowledge Discovery in Databases[J].Al Mag.,,1996. [13] 陈莉，焦李成.Internet/Web数据挖掘研究现状及最新进展[J]. 西安电子科技大学学报，自然科学版，2001，28. [14] David Hawking,Nick Craswell,Donna Harman. Results and Challenges in Web Search Evaluation[R].Proceedings of the Eighth International World Wide Web Conference, 1999. [15] Steve Lawrence, C. Lee Giles. Accessibility of Information on the 49
基于WEB挖掘的聚类搜索引擎研究 Web[J].Nature,,8 Ju1y,1999. [16] 李振星.搜索引擎专业化智能化研究[D]. 北京航空航天大学博士学位论文，2003. [17] 贾红英.网络搜索引擎探析[J].情报资料工作,2003(3). [18] Huang Lieming,etal. ADMIRE:An Adaptive Data Model for Meta Search Engines[J].Available at: [19] Daniel D. D-Integrating Heterogeneous WWW Search Engines[J].May 1995. [20] 何晓聪.元搜索引擎的理论与实践[J].现代情报，2004(8)：35. [21] 张卫丰，徐宝文. Web搜索引擎研究 [J]. 计算机研究与发展，2000, 3 [22] 李炫，庄镇泉.Web访问挖掘项处理的用户识别算法[J]. 计算机工程与应用，2002，(7). [23] , . Finding Groups in Data: an Introduction to Cluster Analysis[J]. NY:John Wiley&Sons,1990. [24] , . Efficient and effective clustering method for spatial data mining[R]. Proceedings of the International Conference on Very Large Data Bases(VLDB’94), San Fransisco: Morgan KaufmannPublisheers,1994: 144-155. [25] , H.-P. Kriegel, , . A density-based algorithm for discovering clusters in large spatial databases[R]. Proc. of the 2nd Int'l Conf. on Knowledge Discovery and Data Mining(KDD'96).Portland: AAAI Press, 1996: 226-231. [26] 李芸。数据挖掘中关联规则挖掘方法的研究及应用[J].2007 [27] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases[R]. Proceedings of the ACM SIGMOD Conference on Management of data, . 207-216, May 1993. [28] 杜鹢. 数据挖掘中关联规则挖掘方法的研究与应用[M].解放军理工大学，. [29] Yeong-Chyi Lee,Tzung-Pei Hong,Wen-Yang Lin. Mining association rules with multiple minimum supports using maximum constraints Internat[J]. Approx. Reason. 40 (2005) 44–54. 50
参考文献 [30] Ming-Cheng Tseng，Wen-Yang Lin. Efficient mining of generalized association rules with non-uniform minimum support[J].Data & Knowledge Engineering 62 (2007) 41–64. [31] 苏中，马少平，杨强，张宏江.基于Web-Log Mining的Web文档聚类[J].软件学报，2002，vol,13，. [32] Ricardo Baeza-Yates,Berthier Information Retrieval[J]. ACM Press, Addison Wesley Longman Limited,1999. [33] O. Zamir and O. Etzioni. Web Document Clustering:A Feasibility Demonstration [R]. In Proceedings of the 21st International ACM SIGIR Conference on Research and Development in Information Retrieval,Melboume,Australia,1998. [34] 黄吕.中文信息处理中的分词问题[J].语言文字应用，Vol. 1,1997. [35] 叔湘，朱德熙.语法修辞讲话〔第二版)[M].中国青年出版社，1979. [36] 朱德熙.语法讲义[M].商务印书馆，1982. [37] of Syntax[J].The MIT Press, 1965. [38] J. D. Phrasal Issues in Natural Language Processing[R].ACL Annual Meeting,-63,Cambridge,MA,1975. [39] R. Wilensky,Y. Arens and D. to UNIX in English:An Overview of UC[R].Communications ofthe ACM,,1984 [40] and Self-extending PhrasalLexicon[J]. Computational Linguistics, Vo ,,1987. [41] Ackerman,M. Billsus, D. Gaffney. Learning probabilistic user profiles[J]. AI Magazine, 1997,18(2):47~56. [42] Ron,, V. Mark. Hypursuit: a hierarchical network search engine that exploits content-link hypertextclustering[R].In:ACM, of the 7th ACM Conference on Hypertext. New York: ACM Press, 1996. 180~193. [43] Savaserea, Omiecinskie,Navathe. An efficient algorithm for mining Association rules in large databases[R].Proceedings of 21th Int Conference on Management of Data,Tucson,Arizona,USA,1997. [44] 宋擒豹，沈钧毅.基于关联规则的文档聚类算法[J].软件学报，,. 51
基于WEB挖掘的聚类搜索引擎研究 [45] 陆建江，宋自林，钱祖平.挖掘语言值关联规则[J].软件学报2001,12(4) [46] Willet Trends in Hierarchic Document Clustering: A Critical Review[J]. Information Processing and Mangement,1988,24(5). [47] Rocchio Retrieval Systems-Optimization and Evaluation[M]. Harvard University, Cambridge,MA,1966. 52
致谢 致谢 本论文的研究工作是在我的导师周爱武副教授的精心指导下完成的。从论文的选题、撰写、直到定稿的整个过程中，无不倾注着周老师的汗水和心血。周老师渊博的知识、严谨的治学态度、勤勉的工作作风和关爱学生的良好师德使我受益匪浅，为我今后的工作和学习树立了良好的榜样，在这里我由衷地表示感谢和敬意！ 在三年的学习期间，不断得到院系领导的关心和支持，使我有一个安定的学习环境，在此向他们致谢！ 感谢周闪闪、李玉梅等同学给我提出的宝贵意见和提供的参考资料，与他们之间的交流令我受益匪浅。 感谢所有三年来在生活和学习上帮助过我的同学们，正是在与他们的相互关心和学习过程中，使我的学业不断进步。 同时，衷心地感谢在百忙之中评阅论文和参加答辩的各位专家、教授！ 最后，特别感谢我的父母！在三年的学习期间他们所给我的精神上和物质上的支持，是我能够顺利完成学业的中流砥柱。 53
攻读学位期间发表的学术论文 攻读学位期间发表的学术论文 [1] 周爱武，王宝铜，李玉梅，周闪闪。最大值约束下的多最小支持度关联规则挖掘[J]. 现代计算机.(2):9-10 [2] 周爱武，周闪闪，邹武，王宝铜，李玉梅。一种基于变精度粗糙集理论的属性约简算法[J]. 计算机技术与发展. (已录用) [3] 周爱武，李玉梅，王宝铜，周闪闪。基于返回结果的Deep Web查询接口识别[J].计算机技术与发展.(已录用) 54
