中文摘要摘要 文本自动分类是基于内容的信息自动分类的核心技术，它是由计算机自动判 别文本类别的过程。文本分类问题具有文本向量稀疏性大、维数高、特征之间具 有较大的相关性的特点，因此，支持向量机非常适合于文本分类问题，在文本分 类中具有很大的应用潜力。同时，文本分类也给支持向量机提出了许多富有挑战 性的课题。例如，文本分类具有类别和样本数目多、噪音多等特点，支持向量机 用于文本分类时存在训练和分类速度较慢等缺点。 本文从降低文本分类过程中文本向量数目的角度出发，来加快训练支持向量 机分类的速度。采用密度聚类的方法提取原始样本中对分类起决定性作用的样本 作为新的训练集进行分类器训练。这些起决定性作用的样本点就是分布在边界上 的点，这些点在ＳＶＭ理论罩被称为支持向量。本文的目的就是尽可能的将这些点 从原始文本向量集中提取出来。 如果将常见的密度聚类算法直接拿来使用，效果并不好，因为它们的时｜．日Ｊ复 杂度太高，导致整体的分类训练过程效率比较低。本文采用一种改进的密度聚类 算法，该算法融合了层次聚类算法ＣＵＲＥ的特点，既保留密度聚类算法对边缘点 比较敏感的特性，又降低了算法的时间复杂度。同时，本文通过大量的试验得出 了针对文本分类样本的高维性特点，在对其进行密度聚类时仞始参数的动态设置 方法，从而在一定程度上解决了以前只能通过人工估算束确定参数值时效率低下， 实际应用效果不佳的弊端。

关键词：支持向量机：文本分类；密度聚类 英文摘要 Ｓｔｕｄｙ ｏｎＴｅｘｔＣｌａｓｓｉｆｉｃａｔｉｏｎＢａｓｅｄｏｎＳＶＭ Ａｂｓｔｒａｃｔ Ｔｅｘｔａｕｔｏ ｃｌａｓｓｉｆｉｃａｔｉｏｎｉｓｔｈｅｃｏｒｅ ｔｅｃｈｎｏｌｏｇｙ ｏｆｉｎｆｏｒｍａｔｉｏｎａｕｔｏ －ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｂａｓｅｕｏｎｃｏｎｔｅｘｔ．Ｉｔｉｓｔｈｅ ｐｒｏｃｅｓｓ ｔｈａｔｔｅｘｔ ｃａｔｅｇｏｒｉｅｓ ａｒｅｃｌａｓｓｉｆｉｅｄ ａｕｔｏｍａｔｉｃａｌｌｙｂｙ ｕｓｉｎｇｃｏｍｐｕｔｅｒ．Ｔｈｅｒｅ ｍａｎｙｆｅａｔｕｒｅｓａｂｏｕｔｔｅｘｔｃｌａｓｓｉｆｉｃａｔｉｏｎ：ｗｉｄｅ ｓｐａｒｅ ｏｆｔｅｘｔ ｖｅｃｔｏｒ，ｈｉｇｈｄｉｍｅｎｓｉｏｎｃｏｍｐａｒａｔｉｖｅｌｙ ｒｅｌａｔｉｏｎ ａｍｏｎｇ ｆｅａｔｕｒｅｓ．ＳｏＳＶＭｉｓ ｖｅｒｙ ｓｕｉｔａｂｌｅ ｒｅｓｏｌｖｉｎｇｔｅｘｔｃｌａｓｓｉｆｉｃａｔｉｏｎ．Ｍｅａｎｗｈｉｌｅ，ｔｈｅｒｅａｒｅｌｏｔｓｏｆｔａｓｋｓｔｈａｔａｒｅ ｆｕｌｌｏｆ ｃｈａｌｌｅｎｇｉｎｇｂｙｒｅｓｏｌｖｉｎｇ ｔｅｘｔｃｌａｓｓｉｆｉｃａｔｉｏｎ ｕｓｉｎｇ ＳＶＭ．Ｆｏｒ ｅｘａｍｐｌｅ．ｔｈｅｒｅ ｔｏｏｍａｎｙｃａｔｅｇｏｒｉｅｓ，ｓａｍｐｌｅｓ，ｎｏｉｓｅｓ，ａｎｄ ｃｌａｓｓｉｆｉｅｒ ｓｐｅｅｄ ｉｓｓｌｏｗ ｂｙｕｓｉｎｇ ＳＶＭ． Ｔｈｉｓ ｐａｐｅｒｓｐｅｅｄｓｕｐ ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｒｏｃｅｓｓｂｙｄｅｃｌｉｎｉｎｇ ｔｈｅｎｕｍｂｅｒｏｆｔｅｘｔ ｖｅｃｔｏｒｓ．Ｔｈｉｓｔｈｅｓｉｓｃｈｏｏｓｅｓｔｈｅｄｅｃｉｓｉｖｅ ｓａｍｐｌｅｓ ｆｒｏｍｔｈｅ ｏｒｉｇｉｎａｌ ｓｅｔ ｂｙｕｓｉｎｇｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ｔｈｅｎ ｒｉｓｅｓｔｈｅｄｅｃｉｓｉｖｅｓａｍｐｌｅｓ ａｓｎｅｗ ｔｒａｉｎｉｎｇ ｓｅｔｔｏｔｒａｉｎｔｈｅ ＳＶＭｃｌａｓｓｉｆｉｅｒ．Ｔｈｅｓｅ ｓａｍｐｌｅｓ ｐｏｉｎｔｓｔｈａｔｄｉｓｔｒｉｂｕｔｅａｒｏｕｎｄ ｅｄｇｅ，ｗｈｉｃｈ ａｒｅｃａｌｌｅｄ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒｉｎ ＳＶＭ．Ｔｈｅ ｔａｒｇｅｔ ｆｉｎｄｏｕｔｔｈｅｓａｍｐｌｅｓｆｒｏｍｔｈｅ ｏｒｉｇｉｎａｌ ｓｅｔ。

Ｉｔ’ｓ ｎｏｔａ ｇｏｏｄｗａｙ ｍａｋｉｎｇｕｓｅｏｆｔｈｅｃｏｍｍｏｎ ｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ ｄｉｒｅｃｔｌｙ，ｂｅｃａｕｓｅ ｔｈｅｉｒｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｖｅｒｙｈｉｇｈ，ｔｈｉｓｗｉｌｌｃａｕｓｅｔｈｅｔｏｔａｌ ｃｌａｓｓｉｆｙｉｎｇ ｐｒｏｇｒｅｓｓ ｅｆｆｉｃｉｅｎｃｙｖｅｒｙ ｌｏｗ．Ｓｏｔｈｉｓ ａｒｔｉｃｌｅ ｕｓｅｓ ａｌｌ ｉｍｐｒｏｖｅｄｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇ ａｉｇｏｒｉｔｈｍ，ｔｈｉｓａｌｇｏｒｉｔｈｍ ｍｉｘｅｓｆｃａｔｕｒｅｓｏｆｈｉｅｒａｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ ＣＵＲＥ．Ｉｔ ｏｎｌｙｒｅｔａｉｎｓｔｈｅｆｅａｔｕｒｅｔｈａｔ ｓｅｎｓｉｔｉｖｅｔｏｅｄｇｅｐｏｉｎｔ，ｂｕｔ ａｌｓｏｄｅｃｌｉｎｅｓｔｈｅｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｄｅｎｓｉｔｙｃｌｕｓｔｅｒｉｎｇｐｒｏｇｒｅｓｓ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｉｔｄｏｅｓｌｏｔｓｏｆ ｅｘｐｅｒｉｍｅｎｔｓ ｔｏｆｉｎｄｏｕｔａｍｅｔｈｏｄｔｈａｔｃａｎ ｄｙｎａｍｉｃａｌｌｙ ｓｅｔｔｈｅｉｎｉｔｉａｌ ｐａｒａｍｅｔｅｒｓ ｔｈａｔｗｉｌｌｂｅｕｓｅｄｉｎ ｍｏｒｅｅｆｆｉｃａｃｉｏｕｓｔｈａｎｔｈｅｏｌｄｏｎｅｔｈａｔｍｕｓｔｓｅｔ ｐａｒａｍｅｔｅｒｓｍａｎｕａｌｌｙ． ＫｅｙＷｏｒｄｓ：ＳＶＭ；ＴｅｘｔＣｌａｓｓｉｆｉｃａｔｉｏｎ：ＤｅｎｓｉｔｙＣｌｕｓｔｅｒｉｎｇ 知识水坝@damdoc damdoc为您倾心整理(小店damdoc.taobao)(QQ@2218108823) 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：｛弋ｆ％为净；月一日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在——年解密后适用本授权书。 本学位论文属于： 保密口 不保密（请在以上方框内打“”） 论文作者签名：｛缸导师签名：渗’盏烈 隰砷年岁月伊 知识水坝@damdoc damdoc为您倾心整理(小店damdoc.taobao)(QQ@2218108823) 基于支持向量机的文本分类问题研究 第１章绪论 １．１问题的提出及意义 随着信息时代的来临，为了从海量的信息中迅速查找需要的信息，就需要对 信息进行分类。传统的做法是对信息进行人工分类，并加以组织和整理，为人们 提供一种相对有效的信息获取手段。但是，这种传统的人工分类的做法存在着许 多弊端：一是耗费大量的人力，物力和精力；二是存在分类结果一致性不高的问 题。

这就要求我们探索文本自动分类的有效方法，提高分类效率。只有这样才能 保证检索的查全率和查准率都得到提高。 面对如此复杂的问题，分类技术在信息检索、信息过滤、数据挖掘等方面起 着至关重要的作用。而网上的大部分信息以文本的形式存在，因此，文本自动分 类就成为信息处理领域的一个重要的研究课题。 文本自动分类是信息检索技术和人工智能技术相结合的研究领域，是进行基 于内容的自动信息管理的核心技术。文本自动分类是根据一些已经分配好类别标 签（这些类别标签预先定义好）的训练文档集合，来对新文档分配类标签，其目的 就是对文本集进行合理处理和组织，使得这些文本能够按照类别区分开来。作为 知识的组织工具，它为信息检索提供了更高效的搜索策略和更准确的查询结果。 其中，高效性在于用户可以首先确定查询的可能类别，以减小需进一步匹配的文 本数量；有效性在于相似的文本很可能与相同的查询相关。这样使得检索的查全 率和查准率都得到了提高。 文本分类的目标是在分析文本内容的基础上，给文本分配一个或多个比较合 适的类别，从而提高文本检索等应用的处理效率。另外，文本分类可以应用到垃圾 邮件的判定；新闻出版按照栏目分类，类别｛政治，体育，军事，…）；词性标注， 类别｛名词，动词，形容词，…）；词义排歧，类别｛词义１，词义２，…），文本检 索，文本过滤以及主题发现与跟踪等。

从ＳｐｒｉｎｇｅｒＬｉｎｋ全文电子期刊与ＩＥＬ（ＩＥＥ， ＩＥＥＥ）数据库中，可以看到最近的期刊与国际会议论文，有大量的关于文本分类的 文章，说明随着大量网上电子信息的出现，文本分类仍是人们研究的热点。 第１章绪论 １．２研究背景及现状 国外自动分类的研究起步较早，始于１９５０年代末。１９５７年，ＩＢＭ公司的 Ｈ．Ｐ．Ｌｕｈｎ在这一领域进行了开创性地研究，他首先将词频统计的思想用于文本分 类中。１９６０年Ｍａｒｏｎ在ＪｏｕｒｎａｌｏｆＡＳＭ上发表了有关自动分类的第一篇论文《０ｎ ｒｅｌｅｖａｎｃｅ。ｐｒｏｂａｂｉｌｉｓｔｉｃｉｎｄｅｘｉｎｇ ａｎｄｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌ》），标志着自动分类作为一 个研究课题的开始。１９６２年博科（Ｈ．Ｂｏｒｋｏ）等人提出了利用因子分析法进行文献的 自动分类。其后许多学者在这一领域进行了卓有成效地研究。国外的文本分类经 历了可行性基础研究和实验性开创研究，目前已经进入到实际性商业应用，在信 息检索、电子会议、网络安全，机器翻译等方面都得到了广泛地应用。 文本分类的发展历史大致可分为两个阶段，从６０年代起步至８０年代末主要 是以专家人工构建的知识工程技术为支撑，分类系统包含专家定义的一系列逻辑 规则，依据这些规则可以把新给定的文本归类为某种或几种特定类别，典型的代 表系统有麻省理工学院（ＭＩＴ）为白宫开发的邮件分类系统、卡内基集团为路透社开 发的Ｃｏｎｓｔｒｕｅ系统等。

第二阶段从９０年代开始，随着互联网技术的快速发展，文 本自动分类的研究也进入了一个新的阶段，各种方法相继得到了发展Ｉｔ２】，包括机 器学习技术为主的信息分类技术逐渐取代了基于知识工程的方法，成为文本自动 分类研究的主要形式，如ＮａｖｉｅＢａｙｅｓ，Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ，神经网络等等。１９９８年 Ｄｏｒｔｍｕｎｄ大学的Ｊｏａｃｈｉｍｓ［３１探讨了用支持向量机方法进行文本分类，取得了很好 的效果。此外，～些学者还采用］Ｂｏｏｓｔｉｎｇ［４Ｊ方法来探讨提高分类处理的方法。这类 分类算法通常是从预先分类正确的训练文本集合中学习到类别的特征判别信息， 再通过测试文本集合对分类器性能进行测试。目前，这种方法所达到的分类性能 已经不亚于人工分类。典型的代表系统有Ｇｏｏｇｌｅ公司的搜索引擎和ＩＢＭ公司的文 本智能挖掘机等。 国内自动分类研究起步较晚，始于２０世纪８０年代初期。１９８１年侯汗清对计 算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、计 算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，国内 的研究者在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识， 基于支持向量机的文本分类问题研究 然后应用于中文之上，继而形成中文文本自动分类研究体系。

到目前为止，我国 陆续研制出一批计算机辅助分类系统和自动分类系统。这其中有基于人工智能技 术的分类系统，有基于统计技术的分类系统，还有基于模糊技术的分类系统，近 几年来基于统计知识的分类方法占主流，也不乏有基于规则的分类方法。国内的 清华大学，上海交大，哈工大，中国科学院等科研院所在文本分类领域作了很多 的研究，在中文文本自动分类镢域中已经取得了令人瞩目的研究成果，其中一些 已经被成功地推广和应用，典型地代表系统有北大天网和百度搜索等。 １．３本文的研究工作 支持向量机从被广泛重视到现在只有几年的时间，其中还存在很多尚未解决 或尚未充分解决的问题，需要进一步完善和改进以适应实际应用的需要。面对文 本分类等具有类别和样本数目多、噪音多等特点的应用，支持向量机在应用过程 中存在以下问题： （１）支持向量机是针对二分类问题提出的，当用于多分类伺题时必须将其推 广。对于类别数目较多的分类问题，目前仍缺乏有效的支持向量机多分类方法。