一种基于潜在语义结构的文本分类模型

1、一种基于潜在语义结构的文本分类模型 (江西师范大学计算机信息工程学院 江西南昌 330027)摘要：潜在语义索引（lsi）模型，是一种已经成功地应用于文本分类等很多领域的算法。lsi模型能在一定程度上解决一词多义和多词一义问题，并能过滤一部分文档噪音。然而在lsi模型中，对稀有类别很重要的分类特征，可能因为在整个文档集中不重要而被滤掉。针对这一问题，本文提出了一种新颖的扩展lsi模型的文本分类模型。新模型在尽量保留文档信息的同时，增加考虑了文档的类别信息。这样，新模型将能比lsi模型更好地表示原始文档空间中的潜在语义结构。在实验中，本分类模型也表现出了非常好的分类性能。关键词：文本分类 潜在语

2、义索引 偏最小二乘分析中图分类号：tp18文献标识码: a1 引言自动文本分类就是在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。如今，已经有很多基于统计和机器学习的文本分类算法，如：回归模型、k近邻、决策树、朴素贝叶斯和支持向量机等1。其中，很多现有的分类算法都是基于从文本中抽取关键词（经常是单独的词）的方法。在这种方法中，假定一个关键词唯一地代表一个概念或语义单元；然而实际的情况是：一个词往往有多个不同的含义，多个不同的词也可以表示同一个语义。这就是所谓的一词多义和多词一义。比如：“马上”可以有“立刻”的意思，也可以理解为“马的上面”；“感冒”、“伤风”和“着凉”却代表着同一种

3、疾病。像这样的情况是很难由计算机自动判别的。一词多义和多词一义，是所有基于语义的算法必须解决的两个主要问题。潜在语义索引（lsi: latent semantic indexing）2，是近年来比较有效的算法之一。lsi 把原始的向量空间转换成潜在语义空间，文档和查询就在转换后的语义空间上进行表示和比较。实验表明这种方法可以在一定程度上解决一词多义和多词一义问题：新的语义空间是原始“文档向量矩阵”的线性组合变换得到的，一般认为这个空间能捕捉文档集中的潜在语义结构。由于lsi在信息检索中的优异表现2，就有人开始尝试将其应用于文本分类领域。其中，wiener的工作3是很有代表性的。wiener的实

4、验中以两种方式使用了lsi。（1）利用lsi对原始向量空间降维。把潜在语义空间中权重较低的维滤掉，这样就可以得到原始空间的一个子集，并滤掉一些噪音；（2）将整个文档集按类别进行划分，为每个类别建立一个lsi表示。为每个类别构建一个单独的lsi表示，很重要的一个原因是：有一些对特定类很重要的词，由于词义不确定的问题，在整体考虑所有类的时候，反而会变的不重要。如bank这个词可能对财经类很重要，但如果把所有类放在一起考虑，这个词就有可能因为它的多义性在语义空间中被滤掉（或变得不重要）。实际上，我们发现这种分立的lsi表示，确实可以分别为每个类找到重要的词（或特征）。但在考虑整个文档集的时候，情形就

5、会有所不同：对单个类重要的词并不一定就对分类有大的贡献。文本分类的关键是在整体考虑下，在所有的类别中，为文档找到它最有可能属于的类。这种类别之间的舍取，在每个类别都是单独考虑情况下肯定不可能做到完全公平。在本文中，我们提出了一种对lsi扩展的算法。我们提取的语义特征不仅反映了文档和词的信息，也考虑了文档的类别信息。不同于为每个类建立单独的lsi表示，我们把所有的信息整合在一个lsi表示里。本文组织如下：第一部分是引言，第二部分介绍一些相关的基本概念，第三部分详细阐述本文提出的模型，实验结果和分析在第四部分中说明，最后是结束语。2 相关工作2.1 基于向量空间模型的文本分类在向量空间模型中，文档

6、以由n个词组成的向量表示（这些词从文档集中选取得到），词也可以由m篇文档组成的向量表示。在实际使用中，用“文档向量矩阵”x能最好的代表这种对偶的信息表示，其中一列代表一个词、一行代表一篇文档：矩阵中的元素，一般表示词j在文档i中出现的频数；也可以根据其他因素调整它的权重4。比如，以反向文档频率（idf: inverse document frequency）调整：其中，文档频数是出现词j的文档数量。说明一下，由于一个词只会在很少的文档中出现，因此矩阵x中的大多数元素都会是零。信息检索的典型处理方式就是关键字匹配。用户提出一个查询q，然后用和文档一样的方式，把它看成一个由关键字组成的向量。通过计

7、算查询向量和文档向量之间的点积（对向量的规一化消除文档长度的影响），可以得出两者之间的相似度。所有m篇文档的相似度可以构成一个向量s()，查询q的相关文档就可以根据这个指标排序并返回给用户。文本分类，就是把新的文档归到已有的类别体系中去。有很多方法可以实现这个目的，一种简单的分类方法是为每个类别计算一个中心向量（类中所有文档向量的平均值）5。这些中心向量被认为是每个类别的代表。所有k个类别的k个中心向量，组成一个 的矩阵。判别文档属于某个类的标准是，该文档距离哪个类别的中心向量更近。其他的方法6则是通过最小化误差平方和c，来解决文本分类问题，c的定义如下：其中，b是保存训练集文档的正确类别信息

8、的矩阵。一篇新进文档，要通过投影到变换向量上得到与每个类的相似度，并由具体的阈值，决定其到底属于哪个类或哪几个类。2.2 应用lsi模型的文本分类在原始的“文档向量矩阵”中，存在着冗余、词语多义和噪音问题。我们希望建立一个比原始矩阵小得多，并只包含有效语义的子空间。要达到这个目的，一般可以通过有效的维数约减。维数约减后，冗余的信息可以合并在一起，词语多义可以通过考虑上下文相关信息解决，把相对不重要的一些特征约去则可以部分解决噪音问题。lsi就是这样一种维数约减方法。它可以通过对“文档向量矩阵”进行解奇异值分解（svd: singular value decomposition）运算，自动计算得

9、到一个比原始空间小得多的有效语义空间：其中，r是矩阵x的阶，是由特征值构成的对角矩阵，和分别是左、右特征向量。一般r个特征值是按大小排序的，当要进行特征值截取的时候，比如只保留前k个最大的特征值，下面的矩阵就是原始矩阵的非常好的近似：在得到的k维子空间中，一篇文档的投影是，而所有m篇文档的投影就是。查询q的变换方式也是如此。因此，查询q和文档之间的相似度计算在lsi的子空间中就变成了：维数的大量约减，既降低了计算的复杂度也滤去了一部分噪音。比如，求矩阵中心向量或作矩阵变换的计算量就从变成了 5。这样的方法在朴素贝叶斯分类模型7、knn模型和svm模型8中都被证明是非常有效的，提高了分类模型的准

10、确度。lsi成功的原因在于，lsi得到的语义空间比原始特征空间更能表达分类必须的语义结构，部分地解决了信息检索中的同义词和文本分类中的信息冗余问题。在数学上，通过svd选取的矩阵是原始矩阵x在k阶情况下的最佳近似。从统计观点看，lsi和主成分分析类似，是一种非常有效的维数约减方法。即：认为特征值较小的维是噪音，并将其滤去。然而，lsi在降低维数的同时也会丢失结构信息。实际上，lsi基于文档信息来建立语义空间（文档的类别信息并未考虑），得到的空间会保留原始矩阵中最主要的全局信息。但有一种情况是：一些对特定类别分类贡献很大的特征，放在全局下考虑却会变得不重要了。这样的特征在维数约减的过程中，就很容

11、易被滤掉，而如果这样，特定类别的分类精度就会受影响。要解决这个问题，文档的类别信息就应该也被考虑进来。以传统方式使用lsi的另一个问题是：没有理论说明，在得到的语义空间中到底应该保留多少维，而维数的变化对最后的结果又有很大的影响8。在实际使用中，人们一般中只能通过反复的实验来确定这个值。3 应用于分类的一种潜在语义模型使用lsi方法的前提假设是，在由大量的词和特征构成的“文档向量矩阵”中隐含着有规律的潜在语义结构。如前所述，稀有类别的重要特征却有可能被忽略掉。事实上也是，稀有类中出现的词很可能是文档集中的非常见词，而非常见词就很有可能被滤掉。于是对稀有类别很重要的分类特征，可能因为在文档集中不

12、重要而被滤掉。为了解决这个问题，wiener9使用局部lsi模型代替全局lsi模型。他们为每个类别建立了一个独立的lsi模型，在分类过程中，每个局部lsi模型都被单独的使用。这样的方法能局部解决前面提到的问题：对稀有类别很重要的特征可以在其局部lsi模型中保留下来。但这样还有其他的问题：（1） 一篇新进文档属于哪些类别，各个局部lsi模型是分别单独考虑的，那么不同的局部模型得到的相似度分值就很难相互比较。可能造成的情况是，应该属于某个类的文档却被错误的分到了其他类中。（2） 无法很好的解决一词多义的问题。比如，在某个特定类别（如：金融）中，一个多义词（如：bank）就可能变得没有歧义。局部ls

13、i模型会认为这种词很重要，但如果放在文档集中考虑，它对分类的贡献却不大。在分立的局部模型中，我们将无法考虑这种一词多义的情况。为了解决这个问题，我们提出了一种同时考虑文档信息和类别信息的分类模型。与lsi模型类似，我们也希望从原始空间中得到一个潜在语义空间；然而不同的是，我们要在尽量保留文档信息的同时，通过对文档信息和类别信息建模，把文档和类别之间的关联也考虑进来。从统计学的观点来看，和偏最小二乘分析（partial least square analysis）有些类似。下面给出一些符号约定：x是mn维的“文档向量矩阵”；是m维的类别信息向量，其中，；矩阵x和向量y都要先做规一化。向量分别是x

14、和y的潜在变量。现在我们所关注的就不是词信息的协方差矩阵x，而是x和y的交叉协方差矩阵。我们希望通过一组一组的潜在变量对来表示这些交叉信息，就如：其中，代表矩阵x中的潜在语义信息，代表矩阵y中的潜在信息。按他们代表信息的重要程度降序排列，也就是代表最重要的信息，代表次重要的信息，依次类推。确定这些变量对的原则是：（1）变量对，是在对矩阵x和向量y的最佳近似；（2）变量对，是对除去已表示部分的x和y的最佳近似；（3）变量对，是对除去和已表示部分的x和y的最佳近似；具体的变量对（如），它要满足如下条件：（a）变量，要尽可能好的表示矩阵x的信息；（b）变量，要尽可能好的表示矩阵y的信息；（c）变量对

15、，要尽可能好的表示矩阵x和y之间的联系。从统计上来说，条件（a）等价于使变量满足，即：要得到表示矩阵信息最多的变量，就是要使得该变量的方差最大；条件（b）等价于条件;条件（c）等价于要求 ，其中代表求两个随机变量之间的相关系数。把看成是由词组成的，也就可以写成：其中，u是一个待定的向量。即认为是词的线形组合，不同的词根据它对语义单元的重要性不同有不同的权重。类似的，我们也可以认为变量（v也是一个待定向量），是y中元素的线形组合。它也是一个非常重要的联系矩阵x和y的中间变量。这样，前面提到的三个条件就可以写成：其中，|u| 和 |v| 代表向量 u 和 v长度。根据协方差的定义，我们有：于是，前

16、面的三个极值问题就可以整合成一个极值问题10：假定代表点积，因为， 确定的问题就可以转成求解如下的极值问题：如果是这个极值问题的解，根据奇异值分解的原理，就是矩阵在一阶情况下的最佳近似11；其中，是奇异值分解的奇异值，分别是左右特征向量。得到潜在变量对后，我们就能计算出在矩阵x和y中，和所能表示的部分：那么，减去这些信息的矩阵就是和；从新的x和y出发，就可以通过相同的过程依次得到和其他的变量对。上面的过程与wold10提出的偏最小二乘算法（pls : partial least square）是类似的。为了避免进行奇异值分解运算，tenenhaus12对该算法做了改进，修改后的算法如下：算法

17、(lsr/pls1): ; ; for k=1,s do ; ; ; ; endfor当所有的潜在变量对都计算出来后，我们就可以按如下方式对文档进行分类：假设有一新进文档，为了表示它与训练集中心向量的差异，对做变换得到，其中；然后就可以按下面的公式，递推出s个元素（其中k = 1, , s）：是一个中间变量；是规范化的主成分，在算法(lsr/pls1)中第k步确定；表示第k个主成分所代表的语义信息；因此，元素代表的是第k步时，矩阵中的剩余信息。最终，文档的类别信息可以这样计算出来：其中，的计算方式和类似。本算法既考虑了文档信息（在公式中由e表示），也考虑了类别信息（在公式中由f表示）。算法中由

18、变量表示前者，变量表示后者，而由两者同时表示。与全局lsi比较，我们的方法增加了类别信息；与局部lsi比较，我们没有分别考虑不同类别的信息，而是整体考虑的；这样在分类时，文档属于某个类别的相似度分数就易于比较了。另外，非常有意思的是当向量y的取值全是1的时候，上面的模型就变成了传统的lsi模型。这也就是说，lsi模型是我们这个模型的一个特例。4 实验结果和讨论做文本分类实验，语料库的选择是非常重要的；只有语料库一致，不同作者之间的实验结果的比较才有意义。英文文本分类方面，国外已经有了reuter，trec，ohsumed等一些标准权威的分类语料库；而在中文文本分类方面，目前还没有一个公认权威的

19、中文文本分类语料库。一般国内的作者，都是自己收集文档建立语料库，并在上面做实验；而这样得到的结果很难与其他同行的结果做比较。经过选择，我们选用了复旦大学中文文本分类语料库。该语料库总共有19637篇文档，其中测试文档9833篇，训练文档9804篇；训练文档和测试文档基本按照1:1的比例来划分。经分析发现语料库存在大量重复文档和少量损坏文档，去除后这些文档后，保留有14377篇文档，其中训练文档8214篇和测试文档6163篇。跨类别的重复文档没有考虑，即一篇文档只属于一个类别。所有文档分为20个类别，但文档的分布并非平均分布；其中训练文档最多的类economy有1369篇训练文档，而训练文档最少

20、的类communication只有25篇训练文档；整个语料库中训练文档少于100篇的稀有类共有11个。在预处理阶段，中文分词部分，我们采用了中科院计算所开源项目“汉语词法分析系统ictclas”系统，然后按词性只保留了名词和动词；对文档中出现的英文予以保留，全部转为小写形式，去除了英文停用词，没有做词干化处理。特征提取算法采用了算法。词的权重表示方式，采用了ltc权重：其中，是词i出现在文档k中的频数，n是训练集文档的总数，m是训练集中词的总数，是出现了词i的文档数。文本分类系统中两个常用的评价指标是准确率(precision = l/m)和召回率(recall= l/n)，其中l为分类正确的

21、文本数，m为确定了类别的文本数，n为待分类的总文本数。综合考虑准确率和召回率，可以得到新的评估指标f1测试值，也称为综合分类率，计算公式如下： 为了评测系统整体的分类性能，我们还采用了微平均f1和宏平均f1两种指标。其中宏平均f1平等对待每一个类别，因此它的得分主要受非常见类的影响；而微平均f1则平等考虑每一个文档，因而它将主要受常见类的影响。在实验中，我们用算法(lsr/pls1)建立了多二分分类器。循环次数s，由矩阵的值决定。当对矩阵x的估计（）近似于零的时候，那么我们就认为矩阵中剩余的信息已经很少了，而停止循环。阈值的确定，是另一个比较复杂的问题。在实验中，我们把整个训练集代回分类器，通

22、过最大化f1的方式确定阈值。为了检测本算法在特征维数变化情况下的性能，我们对算法在不同维数下的微平均f1和宏平均f1作了比较。结果如下：表1 不同特征维数的情况下的微平均f1和宏平均f1特征维数1002005001,0002,0003,0004,0005,0006,0007,0008,000微平均f107720817085408740887088408820883088608830886宏平均f104850545063606990727072607340721074607300753从表1中可以看出，本算法在特征维数只有100的情况下，依然具有可接受的分类性能；而在特征维数大于1000以后，微

23、平均f1值就稳定在比较高的88左右。说明本算法相对于特征数量的鲁棒性较好。下面我们进一步给出在2000维的情况下，各个类别具体的precision，recall和f1变化的情况：类别训练文档测试文档precisionrecallf1economy136911270.894 0.917 0.905 sports12049800.968 0.927 0.947 computer10195910.974 0.953 0.963 politics10109890.915 0.915 0.915 agriculture8476350.904 0.945 0.924 environment8053710.

24、945 0.933 0.939 art5102860.733 0.815 0.772 space5062480.953 0.899 0.925 history4664680.774 0.763 0.769 military74750.576 0.507 0.539 education58580.646 0.534 0.585 transport57580.800 0.690 0.741 law51520.735 0.481 0.581 medical51520.926 0.481 0.633 philosophy40330.538 0.424 0.475 mine33290.762 0.552

25、 0.640 literature33320.667 0.063 0.114 energy30310.870 0.645 0.741 electronics26260.750 0.577 0.652 communication25220.773 0.773 0.773 表2 各个类别的precision，recall和f1从表2中可以看出，本算法对于训练文档数大于800的常见类的f1值均大于了90，对于大部分稀有类的分类性能也在可接受范围内，只有个别类的分类性能较差（估计与语料库有一定的关系）。说明本算法的整体性能较好，是一种非常有效的文本分类算法。5 结束语本文提出了一种新颖的扩展lsi模型

26、的文本分类模型。针对lsi模型中对稀有类别很重要的分类特征，可能因为在文档集中不重要而被滤掉的问题，新模型在尽量保留文档信息的同时，增加考虑了文档的类别信息。这样，新模型将能比lsi模型更好地表示原始文档空间中地潜在语义结构。在实验中，本分类模型也被证明是一种非常有效的文本分类算法。未来的工作是：进一步完善和优化算法，找到一种比较好的循环判停条件和一种更好的阈值判定算法；并与其他经典分类算法作一下比较。致谢：实验用的“复旦大学中文文本分类语料库”是由复旦大学李荣陆提供，中文分词用的“汉语词法分析系统ictclas”系统是由中科院计算所张华平提供。在此表示感谢！参考文献1 sebastiani,

27、 f. (2002) machine learning in automated text categorization, acm computing survey, 34(1):1-47.2 deerwester, s., dumais, s.t., furnas, g.w., landauer, t.k., harshman, r. (1990) indexing by latent semantic analysis, journal of the american society of information science, 41(6): 391-407.3 wiener, e.,

28、pedersen, j.o., weigend, a.s. (1995) a neural network approach to topic spotting, proceedings of sdair-95, 4th annual symposium on document analysis and information retrieval, pp. 317332.4 salton, g. and buckley, c. (1988) term weighting approaches in automatic text retrieval, information processing

29、 and management, 24(5): 513-523.5 dumais, s.t. (1995) using lsi for information filtering, the third text retrieval conference (trec-3), d. harman, ed., national institute of standards and technology special publication.6 yang, y. (1995) noise, reduction in a statistical approach to text categorizat

30、ion, 18th acm international conference on research and development in information retrieval, pp. 256263.7 baker, l.d., mccallum, a.k. (1998) distributional clustering of words for text classification, proc. acm- sigir-98, pp. 96103.8 park, h., howland, p. and jeon, m (2003) cluster structure preserv

31、ing dimension reduction based on the generalized singular value decomposition, siam journal on matrix analysis and applications, 25(1):165-179.9 wiener, e., pedersen, j.o., weigend, a.s. (1995) a neural network approach to topic spotting, proceedings of sdair-95, 4th annual symposium on document ana

32、lysis and information retrieval, pp. 317332.10 wold, h. ( 1985) partial least squares, kotz, s. and johnson n.l., encyclopedia of statistical science. wiley, new york.11 harville, d.a. (1997) matrix algebra from a statisticians perspective. spinger.12 tenenhaus, m. (1998) la rgreesion pls. thorie et pratique. ditions technip, paris.a latent semantic structure model for text classificationz