基于矩阵奇异值分解的文本分类算法研究

景永霞，王治和，苟和平*

(1.琼台师范学院 信息技术系，海南 海口 571100；2.西北师范大学 计算机科学与工程学院，甘肃 兰州 730070)

目前，文本分类方法主要包括决策树、K-最近邻(KNN)、贝叶斯算法(Bayes)、神经网络和粗糙集等.对于大量文本文档集进行分类时普遍存在的主要问题是文档特征空间维数高.对于成千上万的训练文档，将文档用特征词来表示，生成特征空间的维数高，分类计算开销大，分类效率低.

KNN分类算法是一个监督、惰性学习算法，是待分类文本到达时才与所有的训练文本进行相似度判断，获取训练文档中k个最相似的文档判定待分类文档的类别.这类算法的优点是简单高效，但在大样本集或者高维样本集下，分类计算开销大，分类效率降低[1]，且由于KNN是基于向量空间模型(VSM)的分类算法，向量空间模型(VSM)是假设各个词之间是相互独立、互不相关的，也与出现的顺序无关.因此，在文本分类过程中，往往会存在这样的情况：表达相同词义的词可能被抽取为不同特征词，即同义词问题，使得表达相同语义的文本有可能被分到不同的类别和表达不同语义的文本被分到同一个类别，影响文本分类的精度，同时，由于在特定的范围内，把具有相同语义的不同词都作为特征词，会增加文本特征向量的维数，影响分类速度.如对于含有1 000个文本训练集的分类器，如果向量的维数增加1，则分类时的相似度计算增加1 000次.

针对数据维数过高导致分类计算量大的问题，已经出现了许多文本特征向量降维方法和策略[2-4].特征向量降维主要是特征的抽取，有线性方法和非线性方法[5]，其中线性方法有主成分分析(PCA)、潜在语义分析(LSA)等，非线性方法的主要代表为多维标度法(MDS).

奇异值分解(Singular value decomposition, SVD)是现代数值分析的最基本和最主要的工具之一，它已经在统计分析、物理和信息科学与工程等领域广泛使用，能够有效实现高维数据的特征抽取，达到数据降维的目的[6-7]，是PCA和LSA的数学基础.文献[8]中提出了一种SVD和SVM结合方法优化特征词选择，提高了分类效率；文献[9]通过描述语义间的联系，结合SVD算法中的奇异值截断来降低特征维数.但这些方法都是对原始文本特征向量矩阵进行SVD分解，以达到降维目的.由于奇异值分解最显著的缺点是计算的时间复杂度呈3次方增长，中文文本分类系统中可达到上万个特征，使得文本特征向量矩阵规模非常巨大，如果单独采用奇异值分解算法，其计算开销就会急剧增长，使得许多应用变得不可行[10].因此，本文在建立文本特征向量矩阵之前通过信息增益方式进行特征选择，去掉那些对系统分类贡献非常小(信息量小)的项，然后再建立特征向量矩阵进行奇异值分解，使得SVD分解的时间开销降低，同时达到压缩文本特征向量维数的目标，提高文本分类效率.

1 矩阵的奇异值分解

定理1(矩阵奇异值分解) 令A∈Rm×n，则存在m阶正交矩阵U∈Rm×m和n阶正交矩阵V∈Rn×n，使得[6]

A=UΣVT,

(1)

采用奇异值分解实现文档向量空间压缩有2个方面：文档压缩和特征压缩，对于m×n矩阵A，其中每行表示一个特征，每列表示一个文档，下面是关于奇异值分解在文本分类中的应用解释.

1)n×n矩阵V为正交矩阵，用V右乘(1)式，得AV=UΣ，其列向量形式为[7]

(2)

因此，V的列向量vi称为矩阵A的右奇异向量，V称为A的右奇异向量矩阵.这就相当将m×n的矩阵A压缩到m×r的矩阵U，也就是对列进行压缩，即实现文档压缩;

2)对于m×m矩阵U为正交矩阵，用UT左乘式(1)，得UTA=ΣVT，其列向量形式为[10]

(3)

因此，U的列向量ui称为矩阵A的左奇异向量，U称为A的左奇异向量矩阵.这就相当于将m×n的矩阵A压缩到r×n的矩阵V，也就是对行进行压缩，即实现特征压缩.

(4)

则此奇异值分解的逼近质量可用谱范数和Frobenius范数来度量，其计算分别为[11]

其中q=min{m,n}.

因此，把奇异值分解应用到中文文本分类系统中，需利用(4)式进行截断，用一个低秩的矩阵Ak去逼近原始带噪声或扰动的矩阵A，达到数据降维的目标.

2 基于SVD和信息增益的KNN算法(SVD-A)

单独采用信息增益的特征选择方法，使得选择的特征中含有意义相同的词汇，当表达同义的特征词汇太多，将会影响分类的精度，但单独采用SVD算法实现样本的特征维数缩减，其SVD分解计算量大.因此文中采用信息增益和SVD两种方法结合实现样本特征维数缩减.采用信息增益方法裁剪掉那些对分类系统几乎没有任何贡献的特征，也即特征为系统所带来的信息量极少.再对筛选出的特征集所构成的文档特征向量矩阵进行SVD分解，对包含的同义词进行处理，将其映射到另一个特征空间.具体步骤如下：

1)对于含有m个样本的集合Sm=(t1,t2,…,tm)，采用中文分词系统实现各样本ti(i=1,…,m)分词，并根据停用词表去除样本中的停用词;

2)建立文档-词(document-item)矩阵，根据信息增益(IG)[11-12],实现特征选择，获取信息增益量大的前n个词作为系统分类特征词;

3)根据TF-IDF特征权值计算方法，建立向量空间模型(VSM)[13]，实现文档向量化，构造文档特征向量矩阵Am×n;

4)采用矩阵SVD算法，对建立的Am×n矩阵进行分解，根据(4)式实现特征空间转换和降维，即新的特征向量空间

3 实验与评价

3.1 实验环境与数据

CPU为intel(R)CoreTMi5-4200 2.50GHz,4G内存,Windows 7操作系统,Eclipse集成开发工具,中科院分词系统ICTCLAS.实验数据集分别来自谭松波博士提供的TanCropMin数据集和复旦大学李荣陆博士提供的中文分类数据集.其中从谭松波博士提供的数据集选取10个类别，共951个样本(数据1)，各类中样本分布如表1所示.从李荣陆博士提供的数据集中选取10个类别，共529个样本(数据2)，各类中样本分布如表2所示.

表1 数据1中各个样本类分布情况

表2 数据2中各个样本类分布情况

3.2 特征选择与SVD分解

在实验中，对于两类数据集，都分别采用信息增益的方法选择了信息增益量前500个特征词，采用TF-IDF方式计算特征权重，对样本进行向量化，然后采用SVD分解算法对样本向量空间矩阵进行分解，降低特征维数.采用SVD进行样本向量矩阵截断的奇异值分解所需时间和截断的奇异值数量之间的关系如图1所示.随着奇异值数量k的增长(数据维数增长)，所需分解计算时间急剧增加.

图1 奇异值分解所需时间分析

对于数据集1选择前100个奇异值进行降维(即奇异值分解后的分类向量特征维数为100)，其奇异值分解前100个奇异值为：

其变化曲线如图2所示.

图2 数据集1分解后的前100个奇异值

对于数据集2选择前40个奇异值进行降维(即奇异值分解后的分类向量特征维数为40)，其奇异值分解前40个奇异值为：

其变化曲线如图3所示.

3.3 文本分类效果分析

文本分类效果常用的评价方法有准确率(Precision)、召回率(Recall)和F1值(F-Measure), 文中也是采用这3种评价指标对采用SVD降维后的数据分类效果进行评价，同时与采用信息增益的方式选择增益量大的前500个特征词(数据维数为500)的数据分类效果进行比较.文中在KNN分类过程中k值选为9，数据集分为10份，其中9份作为训练集，1份作为测试集，采用交叉验证方式进行实验，分别在两个数据集上进行实验， 算法分类效果的评价结果如表3和表4所示.为了描述简单，用IG-A表示单独采用信息增益选择特征词的分类方法,用SVD-A表示本文提出的信息增益和奇异值分解结合进行特征选择和降维的分类方法.

图3 数据集2分解后的前40个奇异值

表3 在数据集1上的分类效果

表4 在数据集2上的分类效果

从实验评价数据分析，对于数据集1，在准确率上，本文所提出的SVD-A分类算法在文档向量空间维数裁剪之后(100维)的分类准确率(平均值为74.1%)基本能够保持原来采用信息增益的方法IG-A选择500维时的分类准确率(平均值为75.35%)，其中，在科技、房产、电脑、人才和教育5个类上，本文的方法好于单纯采用IG选择特征的分类方法，是因为这几个类所包含的文档中有很多相似的文本特征(同义词)，例如在“人才”和“教育”类中都有“学生”、“高校”和“学校”等语义相关的词汇.在综合F1值方面，采用SVD-A分类方法(平均值为62.02%)高于原来IG-A分类方法(平均值为56.36%).

对于数集2，在准确率上，本文所提出的SVD-A分类算法在文档向量空间维数裁剪之后(40维)的分类准确率(平均值为57.51%)基本能够保持原来采用信息增益的方法IG-A选择500维时的分类准确率(平均值为58.17%)，其中，文学、军事、运输、矿产和历史等5个类上，本文的方法好于单纯采用IG选择特征的分类方法，是因为这几个类所包含的文档中也存在着很多的同义词.在综合F1值方面，采用SVD-A分类方法的F1值(平均值为57.12%)略高于原来IG-A分类方法(平均值为56.86%)的F1值.

因此通过对数据集的分析，文中采用SVD-A方法能够解决文本中的同义词和许多语义相关词的问题，提高了部分样本类的分类准确率.但同时由于SVD是一种有损压缩算法，在部分样本类中的同义词和语义相关的词较少，压缩后存在对分类特征的损失情况，造成在这些样本类上的分类准确率和召回率下降，但从总体上看，该算法在实现数据降维的同时能够基本保持原有数据集的分类能力.

3.4 时间开销分析

由于KNN算法在训练阶段需要对训练数据集中的各个原始文档进行分词，形成特征-文档矩阵，然后在此矩阵的基础上进行降维处理，以达到在分类阶段减少分类比较次数的目的.对于训练数据集的处理及相应数据维数如表5所示.

表5 训练数据集的处理及相应数据维数

根据表中数据的维数可以看出原始“词-文档”矩阵维数高，如果直接进行SVD分解，会使得矩阵分解的时间代价巨大.采用IG方法选择对文档具有较好分类区分度的特征词，去掉基本不具有分类区分度的特征词.然后再采用SVD方法，缩减那些具有同义词和语义相关词的特征项，使得矩阵的维数进一步减小.

在训练阶段的时间开销基本稳定(包括建立“词-文档”矩阵、采用IG降维、SVD分解等时间开销)，即训练阶段是只需要运行一次即可完成，在分类阶段才分别计算与样本集中各个样本的相似度.因此，此类文本分类算法的时间开销主要体现在对未知类别的样本进行分类阶段所产生的时间开销.文中提出的SVD-A算法与单独采用信息增益的IG-A算法在2个数据集上运行的时间开销如表6所示.

表6 两种算法在不同数据集上的分类时间开销

综合上述对文中提出的SVD-A分类算法在文本分类效果和分类计算时间开销上的分析可知，在基本保持原有分类准确率和F1值的情况下，极大地提高文本分类的速度，因此，文中提出的算法特别适合对分类实时性要求比较高的系统.

4 结束语

随着大数据出现，数据维度高、数据关系复杂，给数据的分析带来很大的困难，其中降维处理对高维数据的分析越来越重要.为了提高中文文本分类系统的分类效率，文中将信息增益和矩阵奇异值分解结合起来实现高维文本特征向量的降维处理，使得样本向量空间的维度减少，同时能够保留原有特征的分类信息，实验结果表明此方法能够获得较好的分类效果，尤其是对样本集中含有同义词较多的样本类分类效果更好.但由于奇异值分解时对样本空间进行转换，形成了另外一个语义空间，生成的向量空间无法解释每个样本的具体含义，因此，对于采用SVD进行样本缩减后所形成样本集中的样本，如何建立其与原始样本集中样本的映射关系，达到通过样本数缩减来提高文本分类效率，这将是我们下一步研究的重点.

:

[1] 潘丽芳,杨炳儒.基于簇的K最近邻(KNN)分类算法研究[J].计算机工程与设计,2009,30(18):4260.

[2] CAO X.Optimization models for feature selection of decomposed nearest neighbor[J].IEEETransactionsonSystems,2016,46(2):177.

[3] BOLON-CANEDO V,SANCHEZ-MARONO N,ALONSO-BETANZOS A.Feature selection for high-dimensional data[J].ProgressinArtificialIntelligence,2016,5(2):65.

[4] 梁俊杰,冯玉才.LBD:基于局部位码比较的高维空间KNN搜索算法[J].计算机科学，2007,34(6):145.

[5] 刘峰.机器学习系统设计[M].北京：人民邮电出版社,2014.

[6] 张贤达.矩阵分析与应用[M].北京：清华大学出版社,2013.

[7] 刘贵龙,王慧玲,宋 柔.矩阵的奇异值分解在文本分类研究中的应用[J].计算机工程,2012,28(12):17.

[8] 王永智,滕至阳,王鹏,等.基于LSA 和SVM 的文本分类模型的研究[J].计算机工程与设计,2009,30(3):729.

[9] 龙军,彭毅.基于LSI/SVD的文本分类方法研究[J].微计算机信息,2009,25(10-3):10.

[10] TZENG J N.Split-and-combine singular value decomposition for large-scale matrix[J].JournalofAppliedMathematics,2013,16(1):227.

[11] 范明,孟小峰.数据挖掘概念与技术[M].北京：机械工业出版社，2001.

[12] 李锐,李鹏,曲亚东,等.机器学习实战[M].北京：人民邮电出版社,2013.

[13] 牛萍,黄德根.TF-IDF与规则相结合的中文关键词自动抽取研究[J].小型微型计算机系统,2016,37(4):711.