硕士论文文档自动分类技术及其在搜索引擎中应用的研究.doc

硕士论文 文档自动分类技术及其在搜索引擎中应用的研究1论论 文文 摘摘 要要本文首先介绍了 Internet 的发展状况，指出 Internet 是一个庞大、杂乱、瞬息万变的信息源泉，仅仅依靠网页上的超文本链用户是无法方便、快捷地找到自己所需的信息的，提供 WWW 信息导航服务的搜索引擎是解决这个问题的一个途径在介绍了传统的 Spider 式搜索引擎和基于人工分类的目录式搜索引擎的特点并对它们作了比较之后，指出支持分类目录是 Spider 式搜索引擎发展的趋势，而应用文档自动分类领域的研究对收集的网页自动分类，实现对分类目录的支持是一种可行的方法然后，本文介绍了天网搜索引擎的现状，分析了它的特点，说明要进一步发展天网系统，应当采用文档自动分类技术支持分类目录接下来，本文介绍了文档自动分类的意义和算法的分类，然后分别介绍了m-ary 分类系统和 Independent Binary 分类系统常用的算法和各个算法的特点，接着介绍了从 m-ary 分类系统转换到 Binary Independent 分类系统常用的三种算法以及这两种分类系统的性能评价指标，然后分析了特征项选取对分类系统的影响，介绍了常用的五种特征项选取的方法。

结合现有的天网搜索引擎，本文提出了天网系统支持分类目录的设计方案，详细介绍了自动分类系统的实现，说明了分类系统选用的分类算法的是 KNN算法，选用的评价特征项重要性的指标是 CHI 统计量，选用的转换算法是 Scut算法，然后讨论了自动分类系统在实现过程中遇到的问题以及解决的办法：1 使用两个文件描述分类目录，用 Begin——End 结构表示类之间的层次结构；2 通过限制文档向量最大分量的值显著地提高了系统分类的性能指标；3 使用稀疏矩阵在程序中表示文档向量，极大地缩短了分类响应时间，节省了占用的内存空间在说明了分类系统使用的分类目录、训练集和测试集之后，本文给出了系统的测试数据最后，本文详细介绍了将自动分类系统集成在现有的天网系统中的方法，讨论了对天网系统各个子系统的改造关键词：关键词：文档自动分类、搜索引擎、KNN硕士论文 文档自动分类技术及其在搜索引擎中应用的研究2目目 录录目 录............................................................................................................................................2 第一章 课题研究背景......................................................................................................................3 第二章 文档自动分类的主要算法和性能评价..............................................................................6 §2．1 文档自动分类的主要算法............................................................................................6 §2．1．1 算法的分类......................................................................................................6 §2．1．2 文档的向量空间模型......................................................................................7 §2．1．3 Independent Binary 分类系统..........................................................................8 §2．1．4 m-ary 分类系统..............................................................................................10 §2．2 分类系统的性能评价..................................................................................................13 §2．2．1 m-ary 分类系统的性能评价..........................................................................13 §2．2．2 Independent Binary 分类系统的性能评价....................................................15 §2．3 特征项的选取..............................................................................................................17 第三章 自动分类系统的实现及其在天网系统中的应用............................................................21 §3．1 支持分类目录的天网系统的设计..............................................................................21 §3．2 自动分类系统的实现..................................................................................................22 §3．2．1 自动分类算法的选用....................................................................................22 §3．2．2 对中文的支持................................................................................................22 §3．2．3 自动分类系统的实现.....................................................................................23 §3．2．4 自动分类系统的测试....................................................................................27 §3．3 现有天网系统各子系统的改造..................................................................................31 §3．3．1 收集分析子系统的改造................................................................................31 §3．3．2 WWW 查询页面和查询处理程序的改造....................................................32 第四章 展望....................................................................................................................................33 参考书目..........................................................................................................................................35 附录..................................................................................................................................................36硕士论文 文档自动分类技术及其在搜索引擎中应用的研究3第一章第一章 课题研究背景课题研究背景Internet 是一个由不同类型和规模的独立自主运行和管理的计算机网络组成的全球范围的计算机网络，它的前身是 1969 年美国国防部高级研究计划署组建的实验性网络 ARPANET，随着计算机网络和通信技术的发展，各个国家和组织的网络的不断加入，Internet 已成为一个规模巨大、自治性强、发展变化快、用户访问频繁的全球最大的国际互联网络，截至 1996 年 7 月，Internet 已连接了 134346 个网络，入网的国家和地区超过 150 个，主机 1228 万台，用户人数以亿计。

Internet 又是一个无穷无尽的信息源泉，它已深入到人们生产、生活的各个领域，向人们提供着巨大的并且还在不断增长的信息资源和服务，越来越多的公司、企业通过网页宣传自己，越来越多的科研机关和学校通过网页交流科研成果，越来越多的组织和个人拥有了自己的主页，越来越多的报刊、杂志加入了 Internet 的大家庭，足不出户而知天下事已不再是神话据不完全统计，1996 年 Internet 上的网页数已达到 1900 万，时至今日，这个数目决不会少于 4亿为了让用户能够在如此庞大、杂乱、瞬息万变的信息海洋中，方便、快捷地找到自己感兴趣的信息，而不是茫然不知所措，仅靠网页上的超文本链是远远不够的，提供 WWW 信息导航服务的搜索引擎（Search Engine）是解决这个问题的一个途径传统的 Spider 式搜索引擎通过被称为 Spider 的程序自动地在网上循着超文本链递归地访问、收集 WWW 网页，分析页面的内容，生成索引和摘要，并向用户提供 WWW 查询页面，根据用户的查询请求在索引库中查找相关信息在网上的位置，最后将查询结果按照相关度排序后返回，帮助用户尽快地找到所需的信息，给用户带来了极大的便利。

这类搜索引擎的代表有Infoseek 和 Alta Vista基于人工分类的目录式搜索引擎稍后出现，它在人工的参与下建立分类目录，对收集的网页按主题或者学科进行分类，编写摘要，用户可以沿着分类目录的层次结构，进入自己感兴趣的主题，进而找到所需的信息这类搜索引擎的代表是 Yahoo 和 Sohoo硕士论文 文档自动分类技术及其在搜索引擎中应用的研究4比较这两种搜索引擎，Spider 式搜索引擎自动地收集、分析和处理网页，因而它索引的网页数多，信息量大，并且能定期重新收集网页，更新索引库的内容，向用户提供最新的导航信息，但由于它只提供基于关键词或全文的检索，用户只有确切地知道自己想查什么，自己感兴趣的网页应当含有哪些关键词时，查询的效果才比较理想，否则，返回的结果很可能和用。