基于资源分配网络和语义特征选取的文本分类*

何晓亮，宋 威，梁久祯

(1.江南大学物联网工程学院，江苏 无锡 214122;2.公安部交通管理科学研究所，江苏 无锡 214151)

基于资源分配网络和语义特征选取的文本分类*

何晓亮1,2，宋 威1，梁久祯1

(1.江南大学物联网工程学院，江苏 无锡 214122;2.公安部交通管理科学研究所，江苏 无锡 214151)

针对资源分配网络(RAN)算法存在隐含层节点受初始学习数据影响大、收敛速度低等问题，提出一种新的RAN学习算法。通过均值算法确定初始隐含层节点，在原有的“新颖性准则”基础上增加RMS窗口，更好地判定隐含层节点是否增加。同时，采用最小均方(LMS)算法与扩展卡尔曼滤波器(EKF)算法相结合调整网络参数，提高算法学习速度。由于基于词向量空间文本模型很难处理文本的高维特性和语义复杂性，为此通过语义特征选取方法对文本输入空间进行语义特征的抽取和降维。实验结果表明，新的RAN学习算法具有学习速度快、网络结构紧凑、分类效果好的优点，而且，在语义特征选取的同时实现了降维，大幅度减少文本分类时间，有效提高了系统分类准确性。

RAN学习算法;径向基函数;语义特征选取;扩展卡尔曼滤波器算法;最小均方算法;文本分类

1 引言

文本是当前最主要的非结构化信息资源。文本自动分类技术TC(Text Categorization)能够有效地将文本信息组织起来，极大地提高文本检索的效率。目前文本自动分类已经成为一个研究热点，并在国内外出现了一系列与之相关的分类方法。其中，较为著名的文档分类方法有支持向量机(SVM)[1]、K最近邻(KNN)[2]、神经网络[3]、贝叶斯(Bayes)算法[4]和决策树[5]等。

人工神经网络具有极强的自学习和分类能力，在模式识别领域[6～10]得到广泛应用。与传统的BP神经网络相比，径向基函数RBF(Radial Basis Function)网络以其简单的结构、优良的全局逼近性能[11]引起了学者们的广泛关注。构造RBFNN(RBF Neural Networks)的关键是网络隐含层单元数的确定[12]，隐含层节点过多或过少将直接影响到网络的决策能力。但是，目前仍没有一种有效的方法来确定适当的隐含层节点个数。比较常用的学习方法是在学习过程中根据某种准则动态地添加或删除隐节点，以达到网络结构适当的要求。其中最著名的方法是Platt[13]提出的资源分配网络RAN(Resource Allocating Network)学习算法。

RAN学习算法是基于径向基的单隐含层神经网络模型，它通过判断“新颖性准则”来动态地增加隐含层节点的数目。而“新颖性准则”受初始化数据的影响非常大，这就极易增加网络的学习时间和计算复杂度，而且易导致检验效果降低的状况[14]；其次，RAN算法参数调整时采用了最小均方LMS(Least Mean Squares)算法，使网络存在收敛速度过慢的缺点。Kadirkamanathan V和Niranjan M[15]提出利用扩展的卡尔曼滤波器EKF(Extended Kalman Filter)算法代替最小均方算法进行参数调整，从而提高了收敛速度，但EKFRAN算法增加了网络的复杂性与计算负担。针对上述问题，本文提出一种改进的RAN算法：首先，采用基于均值聚类的方法确定隐含层初始中心；其次，在原始RAN的“新颖性准则”中加入RMS滑动窗口RMSSW(Root Mean Squaer Sliding Window)[16]后，利用LMS算法使RAN网络进行初步学习，得到初始网络(如网络隐含节点数、网络初始参数等)；最后，在初始网络参数的基础上运用扩展卡尔曼滤波器再进行参数优化。该模型能有效地提高网络精度以及RAN网络的性能。改进后的RAN算法具有学习速度快、网络结构紧凑的优点。

对文本进行预处理时，目前广泛使用向量空间模型VSM(Vector Space Model)来表示文本，由文献[17]可知，它是基于文本特征间相互独立的前提假设，对每个特征进行独立评估并计算权值，按权值大小排序，然后根据预定的阈值或特征数目选取最佳特征子集。但是，由于自然语言中存在大量一词多义和多词同义现象，词与词之间很多时候存在着一定的相关性，导致由向量空间模型得到的文本特征向量具有高维度、复杂相关性和非线性等特性。本文采用一种基于语义特征选取SFS(Semantic Feature Selection)[18]的方法对文本预处理过程进行优化，达到对文本矩阵降维且消减词和文档之间语义模糊度的目的，以便更有利于文本分类。

2 原始RAN学习算法

RAN学习算法启动时面对的是一个无隐含层神经元的RBF网络，通过第一对输入样本(x0,y0)初始化网络参数，然后对每一对训练数据都进行新颖性判定，若满足新颖性则增加隐含节点，否则利用LMS算法对当前网络调整网络参数(包括隐含层神经元中心和网络权值)。RAN网络结构如图1所示。

Figure 1 Three-tier structure of RAN neural network图1 RAN神经网络的三层结构

RAN神经网络采用三层结构模型，设输入向量为n维，输出向量为m维，整个网络相当于一个由n维输入空间向m维输出空间的一个映射。在该网络中，输入层为X=(x1,x2,…,xn)，隐含层为C=(c1,c2,…,ch)，b=(b1，b2,…,bm)则为输出层偏置项，输出层为Y=(y1,y2,…,ym)。隐含层神经元采用的是高斯函数，输出层对隐含层神经元的输出进行线形加权组合，可表示为：

(1)

其中，h和m分别表示隐含层和输出层神经元个数，x为样本输入，wij为隐含层第i个神经元和输出层第j个神经元之间的连接权值,Φ(xi)为隐含层高斯函数。

(2)

其中,ci、σi分别为隐含层第i个神经元的中心和中心宽度。

3 改进的RAN学习算法

3.1 初始隐含层中心的选取

对于给定的文档数据集：D=(d1,d2,d3,…,dl)，聚类后簇的集合定义为：C=(c1,c2,c3,…,ck)，l为文档的总数，k为文档聚类个数。本文采用改进之后的K-means算法求得隐含层中心ci和中心宽度σi，算法流程如下：

步骤1采取r次取样，尽量使得取样后的数据样本集中的数据既不失真，又能体现数据的原始分布特性。样本大小为l/r，其中，l为文本集中文本的个数，r的取值为每次抽取的样本大小，应该能装入主存，并尽可能满足r次提取的样本之和等于原始文本集。r个样本向量可表示为：S=(s1,s2,s3,…,sr)，对每个样本集采用K-means算法进行聚类分析，产生一组k′(k′>k)个聚类中心的文本簇，较大的k′值可以使得孤立点附近无初值依附，本文算法中取k′=1.5×k，即k′值为实际聚类个数的1.5倍。对于r次取样操作，共生成r×k′个聚类中心。

步骤2利用凝聚的层次聚类算法average-linkage算法对新生成的m×k′个聚类中心进行聚类。凝聚的层次聚类是一种自底向上的策略，首先将每个对象作为一个簇，将最相似的两个簇合并为一个簇，直到剩下只有k′个簇为止，作为聚类中心。

步骤3将步骤2中获得的k′个聚类中心作为RAN算法隐含层初始神经元，通过式(3)获取相应的σi，该值表示为ci与属于该类的各训练样本之间的距离之和的均值，即:

(3)

其中，Ni为所属类ci的样本总数。

3.2 新颖性准则

整个RAN网络是否增加隐含层节点，Platt提出的RAN算法利用“新颖性准则”来判断，该准则同时考虑了输入与输出空间的特征，并通过以下公式进行描述：

(4)

(5)

其中，h为当前第i个样本输入时网络隐含层节点的数目，di为当前mi个隐含层节点中距离xi最近的隐含层节点的欧氏距离。δi=max{γiδmax,δmin}，其中δmax与δmin分别为输入数据xi之间的最大与最小距离。γi为衰减系数，取值为0～1，其值随着输入数据的增加成指数级减小，直至满足以下条件：γiδmax≤δmin。

在“新颖性准则”控制隐节点个数的前提下，为了减少噪声信息对整个网络的影响，本文引入了RMS滑动窗方法，将M记为滑动窗的宽度(M一般取40～50)，该变化等价于在输入样本的“新颖性准则”中新增了如下约束：

(6)

其中,Ei为第i个样本和之前M个样本的输出误差的均方根，ξ为事先设定的误差阈值。

“新颖性准则”引入公式(6)之后，使得输入样本在进入网络时，必须同时满足公式(4)～公式(6)，才进行隐含层节点的添加，否则利用LMS算法对当前网络调整网络参数。公式(6)的引入能有效防止那些受突发噪声影响严重的输入样本点成为隐含层神经元，从而大大提高了所训练网络的泛化性能。

3.3 LMS算法进行参数调整

当输入样本满足公式(4)～公式(6)时，说明该输入样本满足“新颖性准则”，即该样本与各输入中心均不相似，则需要给此网络增加一个隐含层神经元，其参数设置如下：

(7)

其中,κ为0～1的比例系数，cnearest是距离xi最近的隐含层中心。当xi不满足式公(4)～公式(6)时，则采用下式对隐含层中心及宽度进行调整：

(8)

其中，cj(i)为cj的第i个分量，Φ(xi)为高斯基公式，wsj为网络第j个隐含层节点到第s个输出节点的连接权值，n、h、m分别为当前神经网络的输入节点、隐含层节点和输出节点的个数，Nj为各类样本的个数，η为学习速率，αj是一个表征与cj相似度的参数。αj的定义如下：

(9)

其中，cfarthest为距离输入样本xi最远的中心，而cnearest为距离xi最近的中心。

权值bj与wj的调整如下式：

(10)

3.4 EKF算法进行参数调整

(11)

其中,Ki为卡尔曼增益向量，计算方式如下：

(12)

(13)

其中，Q0为比例因子，Ri为测量噪声方差，di为函数f(x)相对于参数向量ϖ在ϖi-1上的梯度，如下式：

(14)

Pi是估计误差方差阵，是一个p×p维的正定对称矩阵，p的值与参数个数相关。

根据上述探讨，本文改进的RAN学习算法如下：

步骤1利用多次取样数据集二次聚类获得训练文档的一个初始聚类，利用聚类的结果得到隐含层初始中心和宽度，对网络结构进行初始化。

步骤2输入训练数据，计算神经网络的输出。

步骤3利用公式(4)～公式(6)进行“新颖性准则”判断,若满足“新颖性准则”，则利用公式(7)添加一个新的隐含层节点；若不满足“新颖性准则”，则利用公式(8)～公式(10)对网络参数进行调整，跳转到步骤2。

步骤4得到网络的初始结构以及网络参数之后，利用扩展卡尔曼滤波器对神经网络的参数进行进一步调整。

4 语义特征选取

4.1 向量空间模型

对文本进行分类，首要工作是把文本表示成计算机可识别的形式。

目前对文本信息处理使用较多的方法是基于向量空间模型的表示方法。在这个模型中，文本空间被看作是由一组正交词条向量组成的向量空间，每个文本表示为其中一个范化特征向量。给定文本，即：Di={(ti,1,wi,1),(ti,2,wi,2),…,(ti,n,wi,n)}，其中，ti,j为某一特征词条，wi,j为文本Di中特征词条ti,j的权重。

4.2 语义特征向量

(15)

本文中采用的语义特征提取是利用矩阵A的转置矩阵D与Uk相乘，结构如下所示：

即得到新的语义特征向量模型表示的文本矩阵，即:

C=D×Uk

(16)

通过语义特征选取得到的文档矩阵不仅仅在维数上得到了很大的降低，同时也使词和文档之间的语义关系更加清晰。

5 实验结果与分析

5.1 实验数据集

为了验证本文算法的有效性，我们采用了两个文本语料数据集：reuters-21578标准语料库(数据集1)以及20-newsgroup语料集(数据集2)。在数据集1中，本文选取了1 500篇文章用于实验，其中包含了10个类别，分别为：Acq、Coffee、Crude、Earn、Grain、Interest、Money-fx、Ship、Sugar和Trade；在数据集2上，本文选取了1 200篇文章，其中所取的文章分别来自于以下10个类别：Alt.atheism、Comp.windows.x、Sci.crypt、Rec.motorcycl-es、Rec.sporthockey、Misc.forsale、Talk.politics.guns、Talk.politics.mideast、Sci.space和Sci.med。对于两个数据集的文档，本文均采用2/3用于训练，剩余1/3用于测试。

在进行验证实验前，为了使文本数据数学化表示，需要对数据样本进行预处理加工。其一般化的做法是：去除停用词，计算词频，并利用向量空间算法将文档集用文本特征矩阵表示。经过预处理之后，数据集1包含7 856个特征词，可表示为D1j=〈Fj,1,Fj,2,…,Fj,7856〉 ，数据集2则含13 642个特征词，可表示为d2j=〈Fj,1,Fj,2,…,Fj,13642〉 。其中Fj,i表示第i个特征词在文档j中的权重。权值计算公式采用okapi公式[20]：

wij=tfij/(tfij+0.5+1.5·dl/avgdl)·idfj

(17)

idfj=log(N/q)

(18)

然后分别对新的文本特征矩阵再用语义特征选取的方法进行处理，维度k的值分别取40、50、60、80、100、120、150、200、250、300、350、400、450、500、550和600。

5.2 评估标准

为了对本文算法性能进行评价，文本分类系统的评价标准包含两个指标：准确率(precision) 和查全率(recall)，其中:

precision(i,r)=nir/nr

(19)

recall(i,r)=nir/ni

(20)

其中，nir是类别r包含类别i中的文本的个数，nr是分类类别r中实际对象的数目， ni是原来预定义类别i应有的文本数。

公式(19)、(20)反映了分类质量的两个不同方面，为了将两者加以综合考虑，本文采用F-measure来评估分类效果,其值越大，说明分类效果越好。F-measure计算方法是：

(21)

同时，本文还采用了误差平均值MAE(Mean Absolute Error)作为一个评判标准，如下式所示：

(22)

其中，q为文本数量，m为输出层节点个数。

5.3 实验结果分析

图2的横坐标是利用语义特征选取、对实验数据集1进行处理之后产生的不同维度下的文本特征空间，对本文改进的RAN算法、IRAN算法、EKFRAN学习算法、LMSRAN学习算法、Clustering RBF算法、BPNN算法所得到的F-measure值进行对比实验。对于数据集1，在文本维度达到300维之前，六种分类算法的F-measuer值都在逐渐增大，当300维的时候分别都达到极值点，而300维之后F-measure值有所下降。

Figure 2 F-measure of data set 1图2 数据集1的F-measure值

图3是六种神经网络分类算法通过数据集2语义特征选取所获得的不同维度下的分类结果，在200维之前的维度，F-measure值都在不断增大；在200维的时候，六种分类算法的F-measure值都达到极值点；在200维之后，F-measure值曲线下滑。从图2、图3中不难看出，本文改进的RAN算法，在选取的每个文本向量维度，F-measure值都要比其他的五种RAN算法的好，这充分说明了本文改进的RAN算法的有效性。

Figure 3 F-measure of data set 2图3 数据集2的F-measure值

本文改进的RAN算法在数据集1下的向量空间模型1 000维中的运行时间为331.2 s，而原始的LMSRAN算法的运行时间为522.5 s；在语义特征选取300维中，改进RAN运行时间为61.8 s，LMSRAN算法运行时间为140.9 s。同样地，在数据2向量空间模型1 200维和语义特征选取200维中，本文算法运行时间为312.8 s和45 s；LMSRAN算法运行时间为545.5 s和98.2 s。由此可得出，本文改进RAN算法提高了网络的学习速度。

对于图2和图3中F-measure曲线的变化趋势，当采用语义特征选取算法进行降维时，如果维度过低，会造成文本原始特征集信息丢失，造成文本表示不充分，难以达到有效描述文本内容的目的，进一步地，则对分类效果产生干扰。但是，当文本维度过高之后F-measure值反而下降，原因是过高的维度使得表示文本的语义特征又会产生过多的冗余特征，造成一定的噪声干扰，使得文本的相关性又变得复杂。所以，对于本文采用的实验数据集1，k值取300最佳，数据集2的k值取200最有效。

结合图2、图3与表1可以看出，当数据集1用的文本向量维度为语义特征选取的300维的时候，六种分类算法的分类效果都要比各自在向量空间模型中选取的1 000维的效果好；同样地我们也发现，数据集2的文本向量维度采用语义特征选取后的200维时，六种分类算法的分类效果要高于各自在向量空间模型中选取的1 200维的效果。由此可以说明，采用语义特征选取方法进行降维，不仅仅可以降低文本向量的维度和文本分类的时间，而且还提高了文本分类的效果。从表1中还发现，通过对比六种分类算法的MAE值，也说明了本文改进的RAN算法所得分类效果较之于其余五种经典算法的分类效果有着本质的提升。

Table 1 Experiments results comparison between data set 1 vs data set 2in vector space model and semantic feature and selection model表1 数据集1、2在向量空间模型与语义特征选取模型下的实验效果对比

6 结束语

本文提出了一种新的RAN学习算法。通过采用多次取样数据集二次聚类确定初始隐含层节点数目，然后在原有的“新颖性准则”的基础上，增加了RMS滑动窗口作为新颖性判断条件来确定是否增加隐含层节点，并且通过LMS算法和EKF算法的先后优化，确定RAN算法的网络最终结构。实验结果表明了改进RAN算法的分类有效性。另外，本文采用的语义特征选取方法，不仅解决了文本数据维数过高的问题，初步实现根据语义进行分类，而且减少了整个分类算法的时间，提高了分类精度。实验表明，语义特征选取和改进RAN学习方法相结合能有效提高文本分类效果。

[1] Lin H T, Lin J C, Weng R C. A note on platt’s probabilistic outputs for support vector machines[J]. Machine Learning, 2007, 68(10):267-276.

[2] Plakua E K, Avraki L. Distributed computation of the KNN graph for large high-dimensional point sets[J]. Journal of Parallel and Distributed Computing, 2007, 67(3):346-359.

[3] Guo Zhao-hui,Liu Shao-han,Wu Gang-shan. Feature selection for neural network-based Chinese text categorization[J].Application Research of Computers, 2006,23(7):161-164.(in Chinese)

[4] Chen Jing-nian, Huang Hou-kuan, Tian Feng-zhan, et al.Method of feature selection for text categorization with Bayesian classifiers[J].Computer Engineering and Application,2008,44(13):24-27.(in Chinese)

[5] Wang Yu,Wang Zheng-ou. Text categorization rule extraction based on fuzzy decision tree[J].Computer Applications,2005,25(7):1634-1637.(in Chinese)

[6] Mao J, Jain K. Artificial neural networks for feature extraction and multivariate data projection[J]. IEEE Transactions on Neural Networks, 1995, 6(2):296-317.

[7] Song H H, Lee S W. A self-organizing neural Ttree for large-set pattern classification[J]. IEEE Transactions on Neural Networks, 1998, 9(5):369-380.

[8] Yuan J L, Fine T L. Neural-network design for small training sets of high dimension[J]. IEEE Transactions on Neural Networks, 1998, 9(1):266-280.

[9] Mukhopadhyay S, Roy A, Kim L S. A polynomial time algorithm for generating neural networks for pattern classification:Its stability properties and some test results[J]. Neural Computation, 1993, 5(2):317-330.

[10] Chen Q Y. Generating-shrinking algorithm for learning arbitrary classification[J]. Neural Networks, 1994, 7(9):1477-1489.

[11] Poggio T, Girosi F. Networks for approximation and learning[J]. Proceedings of the IEEE, 1990, 78(9):1481-1497.

[12] Parekh R, Yang J. Constructive neural-network learning algorithms for pattern classification[J]. IEEE Transactions on Neural Networks, 2000, 11(2):436-451.

[13] Platt J. A resource allocating network for function interpolation[J]. Neural Computation, 1991, 3(2):213-225.

[14] Manolis W, Nicolas T, Stefanos K. Intelligent initialization of resource allocating RBF networks[J]. Neural Networks, 2005, 18(2):117-122.

[15] Kadirkamanathan V,Niranjan M.A function estimation approach to sequential learning with neural networks[J]. Neural Computation, 1993, 5(6):954-975.

[16] Li Bin.An Improvement of the RAN learning algorithm[J].Pattern Recognition and Artificial Intelligence,2006,19(2):220-226.(in Chinese)

[17] Su Jin-shu, Zhang Bo-feng, Xu Xin.Advances in machine learning based text categorization[J].Journal of Software, 2006,17(9):1848-1859.(in Chinese)

[18] Song Wei , Wang Shi-tong, Li Cheng-hua. Parametric and nonparametric evolutionary computing with a content-based feature selection approach for parallel categorization[J]. Expert System with Application, 2009, 36(9):737-743.

[19] Deerwester S C, Dumais S T, Landauer T K, et al. Indexing by latent semantic analysis[J]. Journal of the American Society of Information Science, 1990, 41(6):391-407.

[20] Li C H, Park S C. Combination of modified BPNN algorithms and an efficient feature selection method for text categorization[J]. Information Processing and Management, 2009, 45(3):329-340.

附中文参考文献：

[3] 郭昭辉,刘绍翰,武港山.基于神经网络的中文文本分类中的特征选择技术[J].计算机应用研究,2006,23(7):161-164.

[4] 陈景年,黄厚宽,田凤占，等.一种用于贝叶斯分类器的文本特征选择方法[J].计算机工程与应用, 2008, 44(13):24-27.

[5] 王煜,王正欧.基于模糊决策树的文本分类规则抽取[J].计算机应用,2005,25(7):1634-1637.

[16] 李彬.一种改进的RAN学习算法[J].模式识别与人工智能,2006,19(2):220-226.

[17] 苏金树，张博锋，徐昕.基于机器学习的文本分类技术研究进展[J].软件学报, 2006,17(9):1848-1859.

HEXiao-liang,born in 1988,MS,his research interests include information retrieval, and data mining.

Textcategorizationbasedonresourceallocatingnetworkandsemanticfeatureselection

HE Xiao-liang1,2，SONG Wei1，LIANG Jiu-zhen1

(1.School of IoT Engineering,Jiangnan University,Wuxi 214122;2.Traffic Management Research Institute,Ministry of Public Security,Wuxi 214151,China)

Confronted with the existence of hidden nodes affected by the initial learning data and the low convergence rate of RAN learning algorithm, a new Resource Allocating Network (RAN) learning algorithm is proposed. The initial hidden layer node, determined through K-means algorithm, adding the 'RMS window’ based on the novelty rule, can better judge whether to increase hidden layer nodes or not. Meanwhile, the network parameters are adjusted by combining Least Mean Squares algorithm and Extended Kalman Filter algorithm, thus improving the learning rate. Since it is rather difficult to deal with the high dimension characteristics and complex semantic character of texts through words space text categorization method, we reduce the dimension and extract the semantic character space to the text input space through the semantic feature selection method. The experimental results show that the new RAN algorithm has the advantage of high-speed learning, compact network structure and good classification. Moreover, semantic feature selection can not only achieve the reduction of dimension and categorization time, but also raise the accuracy of the categorizing system effectively.

RAN learning algorithm;radial basis function;semantic feature selection;extended Kalman filter algorithm;least mean squares algorithm;text categorization

2012-08-13;

：2012-10-08

国家自然科学青年基金资助项目(61103129);博士点新教师专项研究基金资助项目(20100093120004);中央高校基本科研业务费专项资金资助项目(JUSRP11130);江苏省自然科学基金资助项目(SBK201122266)

1007-130X(2014)02-0340-07

TP391

：A

10.3969/j.issn.1007-130X.2014.02.024

何晓亮(1988-),男,浙江金华人，硕士，研究方向为信息检索和数据挖掘。E-mail:slbhxl@163.com

通信地址：214151 江苏省无锡市滨湖区公安部交通管理科学研究所Address:Traffic Management Research Institute,Ministry of Public Security,Wuxi 214151,Jiangsu,P.R.China