本科毕业设计--基于文本的数据挖掘论文.doc

目 录 第一部分 基于文本的数据挖掘.1 第一章 绪论.1 1.1 问题的背景.1 1.2 技术发展现状.1 1.3 全文安排.2 第二章 基于支持向量机理论的分类机设计.2 2.1 引言 2 2.2 支持向量机算法的提出.3 2.3 支持向量机算法的描述.4 2.4 支持向量机算法和其他算法的性能比较.9 第三章 支持向量分类器的具体编程实现.12 3.1 系统功能综述.12 3.2 程序总体框架描述.12 3.3 主要功能函数说明.14 第四章 程序运行结果和结果分析.22 4.1 训练集和测试集选取.22 4.2 运行结果及正确率分析.23 4.3 运行结果分析.30 第五章 论文结论.31 5.1 论文总结.31 5.2 未来研究展望.32 参考文献.33 代代 码码.35 外文资料外文资料.44 中文译文中文译文.56 第二部分 论文.66 第一章 基于支持向量机算法和其他算法在文本分类中的性能比较.66 1 支持向量机的基本思想和算法.67 2 支持向量机算法和其他算法的性能比较.70 3 支持向量机的优缺点.72 参考文献.73 第二章第二章 Bifurcations of a Homogenous Diffffusive.74 Introduction.74 1.Steady state bifurcation.76 2.Conclusion.81 References.82 第三章 基于主题和文档的文本文摘构件库.83 1 文本摘要的意义及该领域技术发展现状.83 2 文本摘要的技术分析方法.84 3 Luhn、LSA 摘要算法实现.85 4 性能评价.89 参考文献.90 第四章 基于 web 的实验室管理系统设计与开发.92 1 引言 92 2 系统设计.93 3 实验室管理系统的分析.97 4 实验室管理系统的实现.99 参考文献.102 第五章人工神经网络的发展及应用.103 1 人工神经网络的发展.104 2 人工神经网络的特性.106 3 人工神经网络的应用.106 参考文献.107 第六章对人工神经网络的初步认识.107 1 人工神经元模型的提出.107 2 神经元的结构及模型.107 3 人工神经网络的特点.108 4 人工神经网络计算机与传统计算机的比较.109 1 第一部分 基于文本的数据挖掘第一章 绪论 1.1问题的背景 对数据的分类问题是人类所面临的一个非常重要且具有普遍意义的问题。将事物正确的分类，有助于人们认识世界，使杂乱无章的现实世界变得有条理。因此在科学技术、工农业生产以及工商业领域，数据分类、文本分类都起着至关重要的作用，例如人类基因序列的识别、电子商务、图书的分类、搜索引擎、动植物的分类等。同时，随着计算机技术的飞速发展，人们现在可以利用计算机自动的或者辅以少量的人工帮助，对大量的数据进行快速、准确的分类，人们称这种自动（半自动）的分类方法为分类器。近年来，随着Internet 的迅猛发展以及人们利用信息技术生产和搜集数据能力的大幅度提高，大规模的网络文本库不断涌现。为了便于在海量文本库中搜寻、过滤、管理这些文本，基于人工智能技术的文本自动分类方法成为人们研究的焦点。机器学习中所谓的文本分类，即是对所给出的文本，给出预定义的一个或多个类别标号。按文本语料的性质和应用需求的不同，文本自动分类可分为基于分类体系的自动分类和基于信息过滤和用户兴趣的自动分类。基于分类体系的分类一般要经过特征提取、文本表示、分类模型训练和分类几个步骤。基于信息过滤（Information Filtering）的自动分类的目的是为用户自动过滤掉那些用户所不感兴趣的信息从而为用户提供个性化服务，节省用户时间。文本分类作为组织和管理数据的一种有力手段，可以被应用于抽取符号知识、发布新闻、过滤电子邮件、学习用户兴趣从而个性化网页服务等方面。目前常用的文本分类器有K-最近邻分类器（K-NN Classifier），NaveBayes 分类器和支持向量机分类器（Support Vector Machines Classifier）等。1.2技术发展现状 文本分类是文本挖掘（Text Mining）19的一个重要应用方面。文本挖掘是由数据挖掘衍生而来的。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。因此，数据挖掘也体现在对一些事实或观察数据的集合中寻找模式并提出决策支持的过程。逻 辑数 据库 被选择被选择的数据的数据 预处理后数据 被 转 换被 转 换的数据的数据 被抽取被抽取的信息的信息 被同化被同化的知识的知识 选择选择 善而从 择择择 预处理预处理 转换转换 挖掘挖掘 分析和同化分析和同化 2 图 1-1 数据挖掘流程图 文本分类（Text Categorization 或 Text Classification）是在已给定的分类体系下（文本集），依据文本的内容或对文本的标识信息等，通过分类程序的学习和运算等处理方式，自动地确定文本所关联的类别。从数学角度来看，文本分类是一个映射的过程，即系统根据已经掌握的每类若干样本的数据信息，总结出分类的规律从而建立并关联判别公式和判别规则；当分类器遇到输入的未标明类属的新文本时，根据总结出的判别规则，确定该文本相关联的类别。这种映射可以是一一映射，也可以是一对多的映射。文本分类映射的数学公式可表示为:BAf分类:其中，A 为待分类的文本集合，B 为分类体系中的类别集合。长期以来，文本分类都是自然语言处理的一个重要的应用领域。直到 80 年代末，在文本分类方面占主导地位的一直是基于知识工程的分类方法，即由专业人员手工编写分类规则来指导分类，其中最著名的系统是为路透社开发的 Construe 系统。90 年代以来，随着信息存储技术和通信技术的迅猛发展，大量的文字信息开始以计算机可读的形式存在，并且其数量每天仍在急剧增加。这一方面增加了对于快速、自动的文本分类的迫切需要，另一方面又为基于机器学习的文本分类方法准备了充分的资源。于是，机器学习中的很多分类方法开始在实际应用中流行起来。1.3全文安排 本文实现了基于支持向量机方法的文本分类器，分类器算法的核心为一个采用线性核函数的支持向量机。全文的组织如下：第一章 绪论，介绍数据挖掘和文本分类的发展情况，为下文做基础。第二章 支持向量机算法的提出和基于 SVM 的分类器的设计。该章首先介绍支持向量机的提出，理论基础和实现方法，然后说明了它的发展并将其与其它算法进行了比较，并说明经典支持向量机的优缺点和适用范围。第三章 支持向量机分类器程序的编程实现。该章详细说明了支持向量机分类器实现的整体架构以及各部分的实现细节，包括重要函数功能说明和样本集的格式等。第四章 分类器程序运行演示及结果分析。该章说明了基于支持向量机的分类器的实现方法，同时介绍了编程实现的环境和使用的样本集（训练集，测试集），最后展示了分类器在不同的样本集和参数设定下的运行效果以及在实际的样本集上的分类精确度，主要体现在利用测试集进行分类时的分类准确度上。第五章 全文结论。该章对全文进行总结。首先对分类器的具体实现进行一些必要的说明，然后提出可以改进的方面和方法，最后提出了支持向量机的未来的研究方向。第二章 基于支持向量机理论的分类机设计 2.1引言 分类的概念是在已有数据的基础上学会一个分类函数或构造一个分类模型，该函数或模 3 型能够把数据库中的数据记录映射到给定类别中的某一个。构造分类器，首先需要一个训练样本集作为输入，以便分类器能够学习模式并找到分类函数。训练集(Training set)由一组数据库纪录或元组构成，每个记录是一个由有关字段值组成的特征向量，这些字段称做属性(Feature)，用于分类的属性叫做标签(Label)。一个具体样本的形式可以表示为)|,(1yi,1jyyy 其中i 表示样本中的特征分量，y表示该样本的分类值（Label）。训练集中标签属性的类型必须是离散的。为降低分类器错误率，提高分类效率，标签属性的可能值越少越好。对于经典支持向量分类机来说，正负二类分类值+1，-1(binary classification)是最理想的分类值状态。从训练集中自动地构造出分类器的算法叫做训练。得到的分类器常要进行分类测试以确定其分类准确性。测试集使用的数据和训练集通常具有相同的数据格式。在实际应用中常用一个数据集的 2/3 作为训练集，1/3 作为测试集。2.2支持向量机算法的提出 很多机器学习方法都与统计理论相联系。机器学习的统计方法就是研究如何从一些观测数据（样本）出发得到（模拟）目前尚不能利用原理分析或实验得到的规律，利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预测。图 2-1 机器学习的统计方法在医学上的应用 机器学习特别是统计学习方法的面临的一个问题是：统计学是一种渐进理论，研究极限特性，即当样本数目趋向于无穷大时的特性，统计学中关于估计的一致性、无偏差和估计方差的界等以及模式识别中关于错误率等的结论都是这种渐进特性。但是数据挖掘以及文本挖掘中常出现的却是小样本集。基于对小样本问题的研究，Vapnik.V 于 1995 年提出了一种基于统计学习理论的通用学习方法，支持向量机(Support Vector Machine,SVM)。支持向量机算法基于结构风险最小化理论（Structural Risk Minimization,SRM）。（SRM 通过使 VC 维即泛化误差的上确界最小化，来使 SVM 具有更好的泛化能力。）SVM 用于模式识别的基本思想是构造一个超平面作为决策平面，并使正负分类值（二值分类器）之间的空隙最大（出于算法健壮性考虑）。SVM 从学习线性决策规则开始，其 4 中W为权值向量，b 为阈值。输入是有 n 个训练样本的数据集。对于一个线性可分的分类问题，SVM 可以找到最优分类超平面。对于线性不可分问题，SVM 把输入向量i映射成高维特征空间上的向量i，并在此高维空间中构造一个最优分类超平面，进而构造分类器的决策函数。图2-2 线性决策规则，使用线性超平面（Linear Separating Hyperplane）图2-3 支持向量机理论中的超平面变换。核技巧通过高维的特征空间放大有用的特征（feature）并实现在高维环境下的线性分化，从而有利于获得更好的分类精度并且避免过分增加算法复杂度。2.3 支持向量机算法的描述 2.3.1 统计学习理论的核心理论 Vapnik.V 的统计学习理论的核心可以表述为：对于两类模式识别问题，经验风险和实际风险之间至少以概率（1）满足一下关系：)4ln()1)2(ln()()(nhnhwRwRemp (1-1)yatxcxccxg2210 tccc210,a txx2,1y 5 其中n为样本数，h为机器学习的VC维（Vapnik-Chervonenki Demantion,用来代表机器的容量），niiiempwXfylwR1|),(|21)(为模式识别的经验风险（Empirical Risk），且niiiempwXfyLnwR1),(,(1)(min(Empirical Risk Minimization)，)(wRemp被定义来表征训练集中的平均出错率（Mean Error Rate），)(wRe m p对于给定的样本和w是固定值。支持向量机基于计算学习理论的结构风险最小化原则。结构风险最小化的观点是找到这样一种假设h，使得h 可以保证最小的真误差（true error）。h 的真误差是指假设h 对未知或者随机测试样本的错误概率。可以用一个上界（upper bound）来关联假设h 的真误差和训练集以及包含假设h的假设空间（可通过VC维衡量）9。支持向量机通过有效控制假设空间H的VC维来找到假设h（该h 使得上界最小，即达到上确界）。图 2-4 结构风险最小化示意图 2.3.2 支持向量机的基本思想和算法：支持向量机1234方法根据有限的样本信息在模型中的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的通用能力(Generalization Ability)。SVM 建立在统计学习理论和结构风险最小原理基础上，从线性可分情况下的最优分类面发展而来。图 2-5 中，实心点和空心点代表两类样本，H 为分类线，H 1、H2 分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔（margin）。6 图 2-5 线性可分情况下的最优平面 所谓最大分类面就是在线性可分情况下，要求分类线不但能够将两个类无错误的分开（训练错误率为零），而且要使两个类的分类空隙最大。支持向量机的分类方程为0bXW。对其进行归一化得到：使得对线性可分的样本集 1,1,2,1),(imiiYRXniYX 满足),2,1(,01)(nibXWyii (1-2)此时分类间隔为|2W，使间隔最大就相当于使2|W最小。满足归一化条件并使得间隔最大（2|21minW）的分类面为最优分类面。使归一化条件等号成立的样本点为支持向量（Support Vectors），即图中21,HH上的样本点。利用拉格朗日优化方法（Lagrange Optimization）可以把上述最优分类面问题转化为其对偶问题，即：在约束条件 01niiiy 和 nii,2,1,0 下对i求解以下函数的最大值：ninjijijijiiXXyyQ11,)(21)(1-3)i为原问题中与每个约束条件（1.1）对应的 Lagrange 乘子。这是一个不等式约束下二次函数寻优的问题，存在唯一解。解中将只有一部分（通常是一少部分）i不为零，对应的 样 本 就 是 支 持 向 量。解 上 述 问 题 得 到 的 最 优 分 类 函 数 是：)*)(*sgn()sgn()(1bniiiXXyibXWxf (1-4)7 阈值*b可由任一个支持向量求得或通过两类中任一对支持向量取中值求得。对非线性问题，支持向量机通过非线性变换（核技巧，Kernel Trick）转化该问题为某个高维空间中的线性问题，在变换空间求最优分类面。在上面的对偶问题中24，不论是寻优 目 标 函 数（1-2）还 是 分 类 函 数（1-4）都 只 涉 及 训 练 样 本 之 间 的 内 积 运 算（)(),(jijiXXXXK）。设非线性映射HRd:将输入空间的样本映射到高维的特征空间 H 中。当在特征空间 H 中构造最优超平面时，训练算法仅使用空间中的点积)()(jiXX，而不出现单独的)(iX。因此在高维空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数)()(),(jijiXXXXK实现的。根据泛函的有关理论，只要一种核函数满足 Mercer 条件24，它就对应某一变换空间中的内积。常见的核函数有多项式，高斯径向基，S 形等 5。综上，在最优分类面中采用适当的内积函数)()(),(jijiXXXXK就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时目标函数(1-3)变为：ninjijijijiiXXKyyQ11,),(21)(1-5)相应的分类函数变为：)*)(*sgn()sgn()(1bniiiXXKyibXWxf (1-6)支持向量机的以上特点提供了解决 维数灾难的方法：SVM 在构造判别函数时，不是对输入空间的样本作非线性变换，然后在特征空间中求解；而是先在输入空间中比较向量(例如求点积)，再对结果作非线性变换24。这样，大的工作量将在输入空间而不是在高维特征空间中完成。函数)()(),(jijiXXXXK称为点积的卷积核函数，根据 4，它可以看作在样本之间定义的一种距离。显然，上面的方法在保证训练样本全部被正确分类，即经验风险niiiempwXfylwR1|),(|21)(为 0 的前提下，通过最大化分类间隔来获得最好的推广性能。在对分类函数的求解中常引入惩罚参数 C 来限制i的取值范围。则支持向量机算法可以描述为24：1 已知训练集nnnYXYXYXT)(),(,),(11，其中niYYRXXimi,2,1,1,1,8 2 选择核函数)()(),(jijiXXXXK和惩罚参数 C0，构造并求解最优化问题njinjjjijijiXXKyy1,1),(21min S.T.niiiiniCy1,2,1,0,0 3 求得最优解),(*1*nT；4 选 择*的 一 个 小 于C的 正 分 量，并 据 此 计 算 nijiiiXXKyyb1);,(*5 求得决策函数)*),(*sgn()(1niiibXXKyXf 依 KKT 条件，nibXWyiii,2,1,0)1)(解中只有很少一部分*不为零，而它们对应的样本就是支持向量。由于 KKT 条件是最优解应满足的充要条件24，所以目前提出的一些算法几乎都是以是否违反 KKT 条件作为迭代策略的准则。图 2-6 持向向量机分类过程示意图。当)(),(jijiXXXXK时，就产生了线性支持向量分类器。其中：),(sgn(1niiiibxxKyy，权值iiiyw，),.,(21dxxxX 是输入的新数据。1x11y2xdx22yssy),(1xxK),(2xxK),(xxKsyX 9 2.4 支持向量机算法和其他算法的性能比较 常用的分类算法除支持向量机方法外，还有 K-NN 方法（Nearest Neighbour），朴素贝叶斯方法（Nave Bayes），神经网络方法（Neural Network）等。2.4.1 K 最近邻分类 K 最邻近（K-NN）是一种有效的近邻学习算法。采用 K-NN 方法进行文档分类的过程描述如下：对于某一给定的测试文档 d，在训练文档集中，通过相似度找到与之最相似的 K 个训练文档。在此基础上，给每一个文档类别打分，分值为 K 个训练文档中属于该类的文档与测试文档之间的相似度之和。即如果在这 K 个文档中，有多个文档同属于一个类，则该类的分值为这些文档与测试文档之间的相似度之和。对这 K 个文档所属类的分值统计完毕后，还应当选定一个阈值，只有分值超过阈值的类别才予以考虑。测试文档属于超过阈值的所有类。KNN 的决策规则可以形式化表示为：dbcdyddSimcdscoreKNNjiijji),(),(),(1-7)其中：1 1,0),(jjcdy：如 果 文 档jd属 于 类 别ic则1),(ijcdy；否 则0),(ijcdy。2),(jddSim为测试文档 d 到训练文档jd之间的距离。ib为阈值。对于某一特定类来说，ib是一个有待优化选择的值。ib可以通过一个验证文档集来进行调整。KNN 分类算法的优点是易于快速实现，分类效果好。同时它也存在一些局限：1 应存储训练例子的数量：如果存储全部例子，分类器的分类速度可能太慢且不实用。较为理想的是存储可以概括重要信息的典型例子。2 相似性度量问题：如果属性是连续的，则可以通过欧氏距离计算。一般情况下应该考虑消除无关属性，不要让无关属性导致距离计算不准确。2.4.2 朴素贝叶斯分类 朴素贝叶斯（Naive Bayes,NB）分类方法是一种简单而有效的分类方法。该方法的一个前提假设是：在给定的文档类语境下，文档属性是相互独立的。Na ve Bayes 文档可以看作是文档属性事件的有序序列。假定每个属性事件在文档中发生的概率与文档长度无关，则一个文档就相当于一串符合多项式概率分布的独立试验。而每个试验相当于随机地从文档属性表中重复抽取一个属性，抽取次数为该属性在文档中出现的次数。文档中的每一属性都对应于这样的一次独立实验。10 假设id为任意一文档，它属于分类 C 中的某一类。由 NB 分类法有：njjijicdPcPdP1)|()()(，)()|()()|(ijijijdPcdPcPdcP (1-8)对文档id进行分类，就是按)()|()()|(ijijijdPcdPcPdcP计算所有文档类在给定情况下 的 概 率，概 率 值 最 大 的 那 个 类 就 是 所 在 的 类，即：)|()|(|max1ijnjijjidcPdcPcd (1-9)对于给定分类背景和测试文档，用朴素贝叶斯方法分类的关键就是计算)(jcP和)|(jicdP。计算)(jcP和)|(jicdP的过程就是建立分类模型的过程。朴素贝叶斯方法假设一个单词在一个分类文档中的发生概率与该文档中的其它单词无关，从而使得计算复杂度简单，具有较高的效率。但是该假设对于绝大多数真实的文本都不成立，从而分类精度有所降低。2.4.3 神经网络 在人工智能领域，神经网络（Neural Network）技术已被广泛研究。神经网络是一些计算装置，模仿大脑中神经细胞的功能。它实际上是许多并行的、内联的计算单元。每个单元执行简单的操作并与相邻的单元通讯。与传统的计算机程序为执行特定的任务一条接一条地执行指令不同，神经网络可以通过对不同例子计算过程的学习执行特定的任务。典型的神经网络中节点均按层次组织。每一层的一个节点均与下一层的节点有边相连，边上有权值，同时每个节点也有一个激活值。在模式识别过程中，每个节点作为一个阈值。在求出所有的输入权值与连接权值的乘积之和后，应用激活函数进行求解。在神经网络中，权值和网络的拓扑结构决定了它所能识别的模式类型。一个学习算法是用于发现给定任务的权值的程序。最流行的神经网络学习算法是 BP 算法（Back-propagation Algorithm）。神经网络提供了比较容易的方式预测非线性系统，优点是对于包含噪声、不完全甚至错误的数据也是有效的。它的主要缺陷是：缺少解释能力，它自身作为一个黑盒子。另一个限制是训练过程非常慢，不能适应大数据量的学习。2.4.4 支持向量机的优缺点 支持向量机方法的主要优点有：1 它专门针对有限样本情况，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值；2 算法最终将转化成为一个二次型寻优问题，理论上说，得到的将是全局最优 11 点，解决了在神经网络方法中无法避免的局部极值问题；3 算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space)，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关；4 支持向量机是非常通用的学习器，其基本形式是学习线性阈值函数，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类器、径向基函数(Radial Basic Function 或 RBF)方法、多层感知器网络等许多现有学习算法1。5 支持向量机的学习能力是与特征空间的大小无关的，它们根据所分开的数据的间距（margin）而不是特征的数目来衡量假设的复杂度。因此如果数据可以用假设空间中的函数来进行区分，并且可以得到较大的分类间距1，就可以将其推广应用到高维空间中去。同时，经典支持向量机也有一些缺点14。经典的支持向量机都是二值分类机（Binary Classsification）对于需要多值分类（Multi-Class）的情况，人们往往采用迭代方法来解决。除此之外，对于一个支持向量机的训练就等同于解决一个数据点数与变量数相同的的线性约束下的二次分化问题（linearly constrained quadratic programming）23，因此对于一个样本数量为 N 的数据集来说，支持向量机的运算复杂度至少是)(2NO，这也就直接造成了经典支持向量机在进行大数据集的分类工作时消耗的学习时间很长，直接影响了其分类效率23。12 第三章 支持向量分类器的具体编程实现 3.1系统功能综述 本章首先介绍程序中支持向量机分类器算法实现的总体架构，包括界面的安排和运行结果表示方式，数据集的格式和表示法，分类器的结构和主要功能函数等。最后详细叙述程序中应用的关键技术和重要函数的功能。3.2程序总体框架描述 在程序设计初期，为了缩短分类器训练时间，在程序中使用了 780 个含有 8 个特征分量的样本作为数据集。其中 480 个样本组成训练集，剩下的 300 个组成测试集。所有的样本都由Reuster-21578数 据 集 经 过 向 量 化 并 进 行 降 维 处 理 得 到。780,2,1i),(iiyXT 其中 1,1y)x,x,x(XiT821i。但是，该分类器并非围绕 780 个样本的小数据集进行实现的，所以在后期分类机也使用了有 2000个样本的训练集和有 600 个样本的测试集。程序主要由三个功能部分组成：1 第一个功能部分主要完成程序框架构建（SDI界面）并实现在界面中显示运行结果。主要涉及到文字显示。2 第二个功能部分主要完成对数据集的学习工作，并以此产生决策函数)*),(*sgn()(1niiibXXKyXf。主要涉及到决策函数生成时使用的的计算式的编程实现。（算式参看2.3.2）3 第三个功能部分实现对分类机的测试工作，来模拟在实际应用中则是对新输入数据的分类，并且根据分类结果计算分类准确率。为了方便程序运行，对数据集中的样本提出两点要求：非负特征分量序号，特征分量序号从小到大排列。3.2.1界面基本框架和文本显示 本程序使用了Windows下的单文档界面（SDI）。构建单文档界面框架的工作大部分由VC自动完成。添加的代码主要是为了实现在单文档界面中显示功能菜单和文字。在文档界面中显示文字是利用了CSvmView类中的GetActiveView()函数来给当前界面指针赋值，由CString 变量ShowText向SetWindowText()函数传递要显示的字符串。用GetWindowText()保留已显示的文字部分。最后由FlashWindow()完成单文档界面的刷新，从而显示出文字。菜单则列出了各个功能选项。3.2.2支持向量机训练阶段 在该功能段中，程序实现了应用训练集对支持向量机的训练功能，得到并保存相应的决策函数（模式）。该功能部分主要包括先期的文本处理和后期生成决策函数（模式）两部分。在本功能段中，首先预设了和支持向量机有关的一些参数，例如惩罚参数 C，决策函数 13 的阈值 b，对支持向量分类器优化的阈值，循环运算终止条件，近似解的上界等。然后调用相关文本处理函数（ReadLine(),ReadFile(),Tokenize()）完成训练支持向量机前对样本集的准备工作。首先通过文件操作函数 ReadLine()扫描全部文本文件，得到训练集的基本信息,例如样本数 sumline，每个样本中特征分量数 maxfeaturenum，特征分量的最大序数maxid 等。这些文本信息将作为以后进行运算的前提条件，即为以后运算的工作空间。同时，因为模式中保存了支持向量，所以在测试阶段，ReadLine()也会读取模式文档。ReadFile()函数扫描训练集得到每个样本的分类值 y，同时调用 Tokenizer()函数进行分词化取得每个样本中的特征分量，并将文本文件中的各项内容读到内存中等待支持向量分类机对其分类模式进行学习。Tokenizer()函数在支持向量机的训练阶段由 ReadFile()函数调用，在支持向量机的分类测试阶段由 SvmTest()调用，其作用是对文本中的每行进行处理，提取特征分量的权值，分类值。对于 SVM 的学习阶段就是处理训练集，对于 SVM 的测试阶段就是处理测试集。因此支持向量机训练阶段的文本部分处理主要是使用 readline()函数扫描文本确定文本中的行数 linenum（样本数）和词数 wordnum_line（分类值 label 以及特征分量），扫描结果保存在 long*linenum 和 long*wordnum_line 数组指针中。利用 linenum 和wordnum_line 作 ReadFile()函数的输入数据，来决定 ReadFine()函数调用 Tokenizer()进行样本行分割，提取出分类值(label)，特征分量权值(weight of a feature)的次数。在完成文本操作以后，调用 SvmTrain()函数，支持向量机开始进行模式识别。受SvmTrain()直 接 调 用 的 函 数 有 InitShrink()，Converge()，CleanShrink()。其 中InitShrink()函数用来初始化和分配内存给用来减小支持向量运算量的 Shrinkage()函数，CleanShrink()函数则在训练函数结束时回收 InitShrink()分配的内存块。Shrinkage()函数由 Converge()函数调用，完成削减一些对模式计算起作用不明显的训练样本的功能。Converge()函 数 利 用 二 次 分 化 方 法（Quadratic Programming）得 到),(*1*nT的值。Converge()还会调用 SvmOptimizer()完成对阈值retrain 的设置,retrain 决定了支持向量分类机是否被优化以及哪些特征向量会被优化。（找出并去掉那些不可能成为支持向量的训练样本）并最终得到分类机决策函数（模式）)*)(*sgn()sgn()(1bniiiXXKyibXWxf，分类器训练的大部分功能在 SvmTrain()以及其调用的 Converge()函数中完成，对于数据集的文本处理则在OnFileTrain()函数中完成，SvmTrain()以文本处理结果作为输入。模式识别完成，得到决策函数后，由WriteModel()函数把模式记录到文本文档中，以便测试时读取。记录内容包括核函数类型，支持向量等。3.2.3支持向量机测试（分类）阶段 该功能段主要实现了根据训练阶段产生的决策函数进行分类测试。涉及到的主要函数有 14 SvmTest(),ReadLine(),Tokenizer()，ScanModel()。SvmTest()函数中涉及到的主要功能有扫描测试集和模式文档，利用学习训练集时得到的模式对测试集进行分类，同时记录分类正 确 率。SvmTest()首先 调 用 ReadLine()函数 获 得“test480.txt”（测 试集）和“model480.txt”（模式文档）的行数信息，再利用 Scanmodel()函数从模式文本中得到模式参数，包括向量机的类型，核的类型，支持向量个数，特征向量个数，训练样本个数，全部的支持向量等，得到的数据存储在 MODEL 结构体中。利用 Tokenizer()函数逐条对测试集中的样本进行分词处理，同时由决策函数)*),(*sgn()(1niiibXXKyXf计算当前测试样本所属类别，并与测试集中该样本已有的分类值进行对比，计算分类正确率。计算测试样本所属文本类的过程如图 3-1 所示。图 3-1 支持向量机分类过程示意图。其中：),(sgn(1niiiibxxKyy，权值iiiyw，),.,(21dxxxX 是输入的新数据，在本程序中由测试集模拟。程序中)(),(XXXXKii 3.3主要功能函数说明 3.3.1界面中文字显示 单文档界面中的文字显示使用PrintView()函数来调用CSvmApp类中的ShowText()函数。ShowText()函数完成取得视图指针、得到当前界面上的文字，向界面添加新文字，刷新界面的工作。因为在界面中显示文字是一个追加的过程，所以显示文字就是保留已经显示的文字，读取界面上的原有文字字符串，同时在原有文字后面添加新的字符串。涉及到的系统函数有CWnd类中的GetWindowText()、SetWindowText()、FlashWindow()函数,以及CView类中的GetActiveView()函数。同时还要能够实现文字的回车换行功能，所以在每次要输出到界面 1x11y2xdx22yssy),(1xxK),(2xxK),(xxKsyX 15 的字符全的首尾都自动添加了回车换行符，这样在程序中调用PrintView()函数时就无需用使用“n”强制换行。3.3.2文本处理 作为该文本分类器的基本输入的样本数据集的特征决定了程序文本处理阶段主要的任务是解决如何对从文本文件中读取字符串进行分类，如何将读取的数据保存到内存块中以及如何在文本文档中记录程序运行结果的问题。文本处理涉及到的函数有 ReadLine()、ReadFile()、Tokenizer()、WriteModel()和 ScanModel()函数。文本处理函数中跟数据集处理有关的是 ReadLine()，ReadFile(),和 Tokenizer()。除此之外，WriteModel()函数负责记录分类机通过训练得到的模式。ScanModel()函数负责在测试分类器时读入该模式并将其保存在 MODEL model 结构体中。下面就文本处理中的各个函数的功能作以说明：1 ReadLine()函数通过扫描数据集文档得到数据集中所含样本数。样本要求以分类值开头，以特征分量结尾，样本中间不能换行显示，因为程序以回车换行符作为识别一个样本是否结束的标志。通过逐一扫描样本得到数据集中最长的样本，同时利用特征分量序号后的冒号作为识别标志得到样本中最多所含的特征分量数。2 ReadFile()函数则与 Tokenizer()函数配合实现对文档的分词化和读入数据到内存块。ReadFile()首先利用 ReadLine()计算出的样本最长值（字符值）设置内存块，该内存用来存贮 Tokenizer()所扫描的每一个样本中的字符串。ReadFile()函数最终得到每个样本的分类值，同时统计正类、负类和未分配分类值的样本的个数。同时也保存了 Tokenizer()提取到的特征分量值。3 Tokenizer()用来实现分词化，即对每一个样本进行拆分，得到样本的分类值和特征分量值。主要的功能段是一个循环，循环条件是一个样本的还有未提取的特征分量。函数首先由 ReadFile()得到样本最长的长度，分类值保存指针，特征分量保存指针，最大分词数等参数，然后按照最大分词数确定循环的终止条件，并总是把当前特征分量值保存到指针中供 ReadFile()调用。4 WriteModel()除了在界面上显示“在文本文档中记录模式.”，主要是负责记录模式，其中包括了支持向量机的类型，使用的核函数，样本中最多含有的特征分量数，支持向量数，阈值b（)*)(*sgn()sgn()(1bniiiXXyibXWxf，nijiiiXXKyyb1),(*），以及所有的支持向量。以上涉及的所有数据都由 MODEL model 结构体保存。5 ScanModel()由SvmTest()函数调用。ScanModel()函数会在界面上显示文字以 16 说明运行进度，同时它扫描模式文档得到于支持向量机有关的参数和信息（WriteModel()函数写入的参数），并把支持向量保存到MODEL model结构体中，以便SvmTest()使用它进行分类。3.3.3支持向量机训练阶段 支持向量机的训练阶段又称学习阶段，所完成的任务就是通过对训练集中样本的学习得到对应的分类决策函数（模式），也就是利用二次分化方法（Quadratic Programming Problem）求出映射函数)*),(*sgn()(1niiibXXKyXf中的b*和*，同时得到支持向量。训练分类机的准备工作主要是对训练集的处理，这些工作在 CMainFrame:OnFileTrain()中进行。OnFileTrian()调用 SvmTrain()完成对分类机的训练工作。训练完毕时 OnFileTrain()调用 WriteModel()函数记录模式文档。图 3-2 分类准备阶段图示 作为支持向量分类器训练阶段的主函数，SvmTrain()直接调用到的函数有 InitShrink()，Converge()，CleanShrink()。其中 InitShrink()函数用来初始化和分配内存给用来减小支持向量运算量的 Shrinkage()函数，CleanShrink()函数则回收 initshrink()分配的内存块。Shrinkage()函数由 Converge()函数调