搜索
基于LSA和HS-SVM的文本分类研究摘要：为了提高文本分类的准确性和效率，提出了一种基于潜在语义分析和超球支持向量机的文本分类模型。针对SVM对大规模文本分类时收敛速度较慢这一缺点，本文将超球支持向量机应用于文本分类，采用基于增量学习的超球支持向量机分类学习算法进行训练和分类。实验结果表明，超球支持向量机是一种解决SVM问题的有效方法，在文本分类应用中具有与SVM相当的精度，但是明显降低了模型复杂度和训练时间。关键词：文本分类；潜在语义分析；支持向量机Abstract:AtextcategorizationmodelbasedonLatentSemanticAnalysisandHypersphereSupportVectorMachine(HSSVM)isproposedtomiprovetheaccuracyandefficiencyoftextcategorizationAstheconvergencerateofusingSVMtocategorizethelargescaletextisrelativelyslow,theHypersphereSupportVectorMachineisappliedtotextcategorizationandtheHypersphereSupportVectorMachineClassificationLearningAlgorithmbasedonincrementallearningisappliedtotrainingandcategorizationExperimentsshowthattheHypersphereSupportVectorMachineisanefficientsolutiontotheSVMproblem,andhasthesameaccuracyastheSVMinthetextcategorizationapplications,butsignificantlyreducesthecomplexityofthemodelandthetrainingtime.Keywords:textcategorization;latentsemanticanalysis;supportvectormachine1.引言文本分类(TextCategorization)作为信息过滤、信息检索、数字图书馆、邮件分类和数据挖掘等领域的技术基础，能够在给定类别的条件下，根据每个类别的训练样本，推出该类别的判别公式和判别规则[1]。而后当遇到未知类别的文本时，根据判别公式和判别规则，确定此文本所属的类别，从而帮助用户有效地管理和利用信息资源[2]。潜在语义分析(LatentSemanticAnalysis，LSA)是S.Deerwester等人提出的一种用于知识获取和表示的计算理论和方法，它使用统计计算的方法对大量的文本集进行分析，从而提取出词与词之间潜在的语义结构，并用这种潜在的语义结构来表示词和文本，达到消除同义词和多义词之间的相关性和简化文本向量实现降维的目的，提高了计算效率[3]。2.算法介绍作为一种对传统向量空间模型(VectorSpaceMode，lVSM)的改进方法[4]，LSA在自然语言理解、文本分析、信息过滤、情报检索以及分类聚类等领域得到了广泛的应用。在文本分类方面，文献[5]将LSA与Kohonen网络(自组织特征映射神经网络)相结合，文献[6]将LSA与BPNN(BackPropagationNeuralNetwork)相结合，文献[7]将LSA与KNN(KNearestNeighbour)相结合，文献[8]将LSA与SVM(SupportVectorMachine)相结合，都获得了较好的分类效果。但Kohonen网络训练速度慢、分类精度低，BPNN的收敛速度慢、容易陷入局部极小值，KNN对训练集要求高、空间复杂度高和计算量大，SVM比其他的机器学习算法表现出更高的分类精度，但在大规模数据上存在收敛速度较慢、训练时间长及不易扩充等问题。超球支持向量机(HypersphereSupportVectorMachine，HSSVM)是最近机器学习领域发展起来的一种分类学习近似算法，是一种比SVM更快的机器学习方法[9]。球结构支持向量机与平面支持向量机有本质的区别:平面型支持向量机的目标是寻找能将两类样本分开的由支持向量所支撑的最优超平面，而超球支持向量机是寻找一个能包含某类全部样本在内的由支持向量所支撑的最紧超球面。它的基本思想是将SVM的二次规划问题转化为一个最小包围球(MinmumiEnclosingBal，lMEB)问题，通过求解MEB得到SVM的解，从而显著地降低了二次规划的复杂程度，所以其可处理样本的规模大、算法的复杂度小[10]。当增加新类别样本数据时，只需要构建新类别对应的超球，故还具有易于扩充和推广的优势[11]。本文将LSA和HSSVM相结合，提出了一种基于LSA和HSSVM的文本分类模型。在该模型中，用LSA进行特征抽取并实现降维，提高文本表示的精度和减少计算复杂度；采用一种基于增量学习的HSSVM分类学习算法进行训练和分类。实验结果表明，该模型取得了很好的分类效果，并且在训练时间上比SVM有较大的改进。3.文本分类模型与算法3.1分类模型本文提出的基于LSA和HSSVM的文本分类模型如图1所示。图1基于LSA和HSSVM的文本分类模型该模型由文本预处理、基于LSA的特征抽取与降维、文本向量化表示、HSSVM分类器学习和HSSVM分类器几个模块组成。1)文本预处理。文本都是非结构化的，而且文本的内容是人类所利用的自然语言，计算机很难处理其语义，因此要进行必要的文本预处理。预处理模块主要对文本集进行分词处理，本文使用中国科学研究院计算所的ICTCLAS系统对文本进行分词处理，去除停用词和高频词，只保留名词和动词。2)基于LSA的特征抽取与降维。基于LSA的特征抽取与降维模块利用LSA对训练集的词∀文档矩阵进行特征抽取与降维。它通过对词∀文档矩阵的奇异值进行分解，提取k个最大的奇异值及其对应的奇异矢量，构成新矩阵来近似表示原文档集的词∀文档矩阵。与VSM相比，该方法能够反映词之间语义上的联系以及上下文语境对词义的影响，消除同义词和多义词在文本表示时所造成的偏差，并且实现了文本向量的降维，缩小了问题的规模。3)文本向量化表示。经过特征抽取与降维模块处理后构成LSA向量空间模型，模型中的词∀文档矩阵的每一个行向量代表一个文本，这样就对文本进行了向量化表示。测试过程中，每一个测试样本经过分词处理，生成初始文本向量，然后在文本向量化表示模块中利用训练过程中构造的LSA空间模型，将初始文本向量映射到潜在语义空间，生成新的文本向量。4)HSSVM分类器学习与分类。HSSVM分类器就是利用构造最小超球的方法对文本进行分类，它能够在新加入的数据被超球包围时，不改变该类别的支持向量，所以，在此分类器中笔者采用增量学习分类算法进行训练和分类，该算法能够很好地利用这一特征。经过文本向量化表示，模块处理后将生成的新的文本向量输入到分类模块中进行分类，得到最终分类结果。3.2基于潜在语义分析的特征抽取与降维基于文本关键词的VSM利用词的权值量化文档向量，具有简单易用、效率高等优点，但是它忽略了特征之间的语义相关性与序关系，无法刻画文档的语义。它仅仅统计了词的频率，而忽略了词之间语义上的联系以及上下文语境对词义的影响，这样就使得文本的相似度仅取决于它们所拥有的相同词的多少。而文档本身却具有一词多义和多词同义的特征，这种分法就使得拥有不同词但词义相同的文本被分到不同类中，而拥有相同词但词义不同的文本却被视为一类，严重降低了分类精度。另外，VSM方法构造的文本矩阵一般都是高维度的稀疏矩阵，训练和分类的效率低，不适合处理大规模的文本集。针对这些不足，LSA都能够进行有效的解决。它认为，文本中的词与词之间存在着某种潜在的语义结构，这种潜在的语义结构隐含在文档本身词语的上下文使用模式当中。因此，它通过对词∀文档矩阵的奇异值进行分解计算，提取k个最大的奇异值及其对应的奇异矢量以构成新矩阵，用新矩阵来近似表示原文档集的词∀文档矩阵，这样就把高维的VSM表示的文本映射到了低维的LSA空间，并从中提取潜在的语义结构，避免了词之间相关性的影响，大大提高了文本表示的准确性。LSA本质是基于奇异值分解的，它将文档和词汇映射到一个低维的向量空间，简化了文本向量，降低了维度，提高了文本表示的准确性。其处理步骤如下:步骤1:构建词∀文档矩阵。在LSA模型中，一个文本集可以表示为一个m∃n(m表示文本集中包含的所有不同的词条个数，n表示文本集中的文本数)的词∀文档矩阵：A=[aij]m∃n(其中aij表示第j个文档中第i个词的权重值)步骤2：奇异值分解。把矩阵A分解为三个矩阵的积，U&，S&，V&，其中U&，V&是正交矩阵，S&是奇异值的对角矩阵。S&中对角线上的k个较大的单值被保留，其他较小的单值被置为0，去掉S&中单值为0的所有行和列，得到对角阵S，去掉U&、V&中相应的列，得到矩阵U、V，利用得到的这3个矩阵来构造一个新的词∀文档矩阵R=USVT。通过奇异值分解，忽略了空间排列中较小的、不重要的影响因素，在文本中没有出现的关键词，如果与文本语义相关，它就会在新的词∀文档矩阵中通过一个非0的分量表示出来。因此，新的词∀文档矩阵从数值的角度反映了关键词之间存在着的潜在语义关系，它在最小平方意义下最接近原来的词频矩阵。在处理过程中，向量空间中每一维的含义发生了很大的变化，它反映的不再是词条的简单出现频度和分布关系，而是强化的语义关系；向量空间维数的降低，有效地提高了文本集的分类速度[5]。LSA利用矩阵R代替A来表示词与文档间的语义关系，通过奇异值分解和取K秩近似矩阵，消除了原词∀文档矩阵中包含的噪声因素，从而更加凸显出词和文本之间的语义关系，另外使得词和文本的向量空间大大缩减，提高了文本分类的效率。3.3基于增量学习的HSSVM分类算法HSSVM将每一类文本用一个最小包围球来界定，不同类的文本形成不同的最小超球，这样整个文本空间就划分成若干个超球，这样显著降低了二次规划的复杂程度且易于扩充。当训练集中增加新类别样本数据时，只需构造新类别对应的超球，而无需额外的约束条件调整。其分类原理是对某类样本，在超球半径尽可能小的情况下，包含该类样本尽可能多。当测试样本不处于任何一个超球中时，比较测试样本到各类超球的距离，离哪个最近，就属于该超球所代表的类[13]。在球分类中我们所得到的支持向量实际上是每一类中边界上的点，它们决定了每个类别超球的半径，当该类新加入的数据被超球包围时，该类别的支持向量将不会改变[14]，这样我们就能将增量学习方法较好地应用进来，形成基于增量学习的HSSVM文本分类算法[15]。该算法的具体步骤如下：设Am为A中属于第m类的样本子集，其中m=1，2，3，∋，N。对于每一类样本Am，利用超球支持向量机，在LSA特征空间寻找一个超球(am，Rm)，其中am是该类超球的球心，Rm为超球的半径。若有一类新类别样本集AN+1加入，则利用超球支持向量机在特征空间确定其映射对应的超球(aN+1，RN+1)，完成一次增量学习。对于分类样本x，由以下算法步骤来判断其所属的类。步骤1：利用公式(4)计算x映射到每个超球球心am的距离22,()||()||(,)(,)2(,)mmmmmmmmijijijijidxgxaKxxKxxKxx（4）步骤2：若存在唯一的n，使得()rdxR，则x属于第n类，转向步骤5，否则转向步骤3。步骤3：若对于所有的()mdx，()mmdxR都成立，先根据公式(5)计算样本x对于每个类别的隶属度rm，再根据公式(6)计算x所属的类别n，之后转向步骤5，否则转向步骤4。()mmmrrdx（5）argargmmrr（6）步骤4：若存在两个或者两个以上的()mdx，使得()mmdxR，则根据公式(7)计算样本x对于该类的隶属