北京印刷学院
毕业设计（论文）开题报告
课题名称： 基于SVM的文档分类研究
学生姓名： 单昕蕾 学 号： 024020301 专 业： 计算机科学与技术 学生班级： 计02－3 专业方向： 应用 合 作 人： 无 指导教师： 刘犇 日 期： 2006 年 3 月 6 日
一、文献综述（本课题研究的主要内容、目的、意义及现状等） 自动文档分类（Automatic Text Categorization，ATC）技术是人工智能技术和信息检索技术相结合的研究领域，是进行基于内容的自动信息管理的一项核心技术。在Web出现之前，人们已研究过许多普通文档分类的方法，形成了各种文档自动分类技术。当前，随着Internet的迅速发展，网络信息的多样性和多变性导致信息过度膨胀，ATC技术所处理对象自然地从普通文档扩展到网页信息；另一方面，用户却找不到需要的信息，急需对网上的信息进行有序的组织，以有助于信息的准确定位与分流，也促使了文档分类方法地进一步发展以满足用户的需求。 主要的文档自动分类算法可以分为词匹配法、基于知识工程法和统计学习法三类，前两类算法由于分类效果不佳或严重依赖于推理规则的质量，在实际的分类系统中相对较少使用。因此现有的分类方法主要是基于统计理论和机器学习方法的，比较著名的文档文类方法有Bayes、KNN、LLSF、Nnet、Boosting及SVM等。其中SVM和KNN较其他方法有更高的分类准确性和稳定性。而此次最为关注的SVM方法是建立在统计学习理论的VC维(VC Dimension)理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability)。由于SVM方法较好的理论基础和它在一些领域的应用中表现出来的优秀的推广性能，近年来，许多关于SVM 方法的研究，包括算法本身的改进和算法的实际应用，都陆续提了出来。 此课题的核心就是在海量网络信息涌现的背景下，比较几种ATC技术，由此对基于SVM的文档分类方法进行一定的改进，使其更适于面向网络信息。 二、研究方案（实施步骤、方法等） 运行平台：Visual C++ 6.0 和 基于libsvm (A Library for Support Vector Machines)的编程环境下，应用TREC、CMU、BERKLEY等提供的语料库对系统进行评测。 本课题是在海量网络信息涌现的背景下，比较几种ATC技术，由此对基于SVM的文档分类方法进行一定的改进，使其更适于面向网络信息。文档自动分类的一般过程如下图所示： 训练集 预处理 特征选取 分类算法 测试 分类结果 参数调整 1) 预处理。同普通文档相比，网页的设计比较随意，通常包含各类广告，设计人员的注释以及版权申明等无关信息。有时同一个网页甚至会包含多个不同的主题。在进行分类之前，需要自动清除这些“噪音”，否则这些“噪音”会降低分类质量。 2) 训练样本。选择合适的语料库为实现网页自动分类提供了一个良好的前提条件。 3) 特征选取。其任务就是要将信息量小，“不重要”的词汇从特征项空间中删除，从而减少特征项的个数，它是文本自动分类系统中的一个关键步骤。 4) 分类算法。我们选用SVM分类算法来实现基本的分类器。 5) 分类质量的评价指标。在信息检索领域，通常采用查准率和查全率，人们通常借鉴这些标准来评价分类系统的优劣。 基于SVM的文档分类利用训练样本进行特征选择和分类器训练，并根据选择的特征对待分类的输入样本进行形式化处理，然后输入到训练好的分类器中进行类别判定。SVM 是从线性可分情况下的最优分类面发展而来的, 基本思想可用图2的两维情况说明。 H H H2 如图2所示, 方形点和圆形点代表两类 样本, H 为分类线,H1、H2分别为过各类中 margin=2/||w|| 图2线性可分情况下的最优分类线 离分类线最近的样本且平行于分类线的直 线, 它们之间的距离叫做分类间隔(margin)。 k 经过相应处理可得到分类函数： f (x)=sgn{∑i=1αi*yik(xi﹒x)+b*} 这就是支持向量机。 概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求最优分类面。SVM分类函数形式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应一个输入样本与一个支持向量的内积，因此也被叫做支持向量网络。 决策规则 y=sgns （i=1αiyik(xi,α)+b） 权值 αiyi 基于支持向量机的非线性变换 x1, „,xS 输入空间 x=(x 1,x2 ,„,xd) 显然，上面的方法在保证训练样本全部被正确分类，即经验风险Repm 为0 的前提下，通过最大化分类间隔来获得最好的推广性能。如果希望在经验风险和推广性能之间求得某种均衡，可以通过引入正的松弛因子i来允许错分样本的存在。这时，约束变为: yi[(w·xi)+b]-1+i ≥0， i=1，„，n 而在目标——最小化1/2||w||2——中加入惩罚项Ci=1i，这样，Wolf 对偶问题可以写成： n n n Maximize: Q(α)=i=1αi－1/2i,j=1 αiαj yiyjK(xi，xj) s.ti=1yiαi=0 n 0≤αi≤C i=1，„，n 这就是SVM 方法的最一般的表述。 三、研究进度计划（分阶段完成的任务及阶段性成果形式） 计划时间 2005年12月 ～2006年1月 2006年1月 ～2006年3月 2006年3月 （2 周） 2006年4月～2006年5月 2006年5月（1周） 2006年6月9日 年 月 日～ 年 月 日 年 月 日～ 年 月 日 年 月 日～ 年 月 日 计划完成内容 分析题目 掌握相关技术 系统概要设计 系统详细设计及设计 系统调试 完成毕业论文 四、指导教师意见 指导教师（亲笔签名）： 年 月 日 五、教研室（工作室）意见 教研室（工作室）主任（亲笔签名）： 年 月 日