甄志龙，于 非，王海鹃

(通化师范学院 计算机科学系，吉林 通化 134002)

随着计算机、网络以及通信技术的迅猛发展，如何有效地组织和管理信息，并且快速、准确、全面地找到用户所需要的信息是当前信息技术领域面临的一大挑战.文本分类可以在较大程度上解决信息杂乱现象，而且在信息检索、信息过滤、搜索引擎等领域都有广泛的应用.文本分类是依据文本的内容，将每篇文本自动归入到一个或多个预先定义好的类别中[1].在文本分类过程中经常会遇到高维的特征空间，特征向量的维数可达数万维甚至十几万维，众多的特征项中可能含有大量的冗余或噪声，这不仅会影响到分类的精度，还会导致过高的计算复杂度，使某些分类算法变得不可行.因此，许多维数约减方法[2,3,4]已应用于文本的表示和索引.考虑到文本中的词与词之间存在某种联系，即存在某种潜在的语义结构，文献[5]中提出了经典的潜在语义索引(Latent Semantic Indexing，LSI)文本表示方法.传统的向量空间模型是假设词条间相互独立，事实上，词语之间存在着关联性，出现了“斜交”现象，这必然会影响文本处理的结果.本文提出了一种有监督保局索引(Supervised Locality Preserving Indexing，SLPI)的方法，SLPI的目标是找出高维特征空间中的样本对应在低维空间中的文本表示，从而提高文本分类的性能.

1 有监督保局索引(SLPI)

SLPI的核心思想是基于He[6]等人提出的LPP方法.但是在监督模式、邻接图的构造、边的权重和约束条件上都与LPP不同.

算法的具体过程描述如下：

Step1.构造邻接无向图G.图G中有n个结点，每一个结点代表一篇文本.如果两个文本Xi和Xj属于同一类，则在结点i和j之间放一条边；否则，结点之间没有边连接.

Step2.建立相似矩阵W=(Wij)n×n.在Step1图G中，当两点之间没有边相连时，Wij=0；当两点之间有边相连时，采用Jaccard系数给定一个相似性Wij(权重).即

Wij={XTi·Xj‖Xi‖2+‖Xj‖2-XTi·Xj，(如果Xi和Xj属于同一个类别)

0，(如果Xi和Xj不属于同一个类别)

(1)

Step3.根据相似矩阵W=(Wij)，通过求解下面的最小化问题获得投影矩阵A=[a1,a2，……，aL]

argmina∑ni=1∑nj=1(aTXi-aTXj)2Wij

(2)

∑ni=1∑nj=1(aTXi-aTXj)2Wij=

∑ni=1∑nj=1aTXiWijXTia-2∑ni=1∑nj=1aTXiWijXTja+

∑ni=1∑nj=1aTXjWijXTja=2∑ni=1aTXiDiiXTia-

2∑ni=1∑nj=1aTXWijXTja=2aTX(D-W)XTa=

2aTXLXTa

(3)

其中X是数据矩阵D=diag(∑nj=1W1j，∑nj=1W2j,…，∑nj=1Wnj)；L=D-W称为拉普拉斯矩阵(Laplacian Matrix).

设定约束条件aTa=1,此时(3)式可改写成为：

J(a)=argminaaaTXLXTaaTa

(4)

利用拉格朗日乘子法，最小值出现在

∂∂a(aTXLXTa-λaTa-λ)=0

(5)

经过矩阵微分运算得：

XLXTa=λa

(6)

于是，问题转化为求解矩阵特征值和特征向量问题，取ai(i=1,2,…，l)为对应于特征值λi(λ1<λ2<…<λl)特征向量.

2 实验

2.1 实验数据

语料是文本分类领域中的Reuters-21578数据集.我们选择了6个类：trade，interest，wheat，corn，oilseed，gnp.训练集1334篇文本，测试集457篇文本.数据的分布如表1所示.

表1 实验数据的分布

2.2 实验结果

本文采用K近邻分类器(K=21).图1和2分别显示了实验数据集上宏平均和微平均的结果.可以看出，在文本分类性能上SLPI明显优于Original Features和LSI.

图1 实验数据上宏平均的结果

3 结束语

文本分析与处理过程中的一个基本问题是文本的表示和索引.鉴于经典的潜在语义索引方法属于无监督模式，本文提出了一种有监督局部保持索引的文本表示方法.此方法通过类别信息所求得的投影矩阵，将原有的文本表示转换成新的文本表示，即将高维空间中的问题转化到低维空间中处理。利用K近邻分类器，在Reuters-21578数据集上进行实验，结果表明文中所提出的文本表示方法对文本分类的性能有很大提高。

参考文献：

[1]F.Sebastiani.Machine learning in automated text categorization [J].ACM Computing Surveys,2002,34(1):1-47.

[2]R.Ando.Latent semantic space:Iterative scaling improves precision of inter-document similarity measurement[C]//In:Proceedings of the ACM/SIGIR Conference on Information Retrieval,2000.

[3]R.Ando and L.Lee.Iterative residual rescaling:An analysis and generalization[C]//In:Proceedings of the ACM/SIGIR Conference on Information Retrieval,2001.

[4]E.Bingham and H.Mannila.Random projection in dimensionality reduction: applications to image and text data[C]//In:Proceedings of the 7th ACM/SIGKDD International Conference on Knowledge Discovery and Data Mining,2003:245-250.

[5]S.C.Deerwester,S.T.Dumais,T.K.Landauer,G.W.Furnas,and R.A.harshman.Indexing by latent semantic analysis[J].Journal of the American Society of Information Science,1990,41(6):391-407.

[6]X.He and P.Niyogi.Locality Preserving Projections[C]//In:Advances in Neural Information Processing Systems 16, Vancouver, Canada, 2003.