基于資源分配網絡和語義特征選取的文本分類*

何曉亮，宋 威，梁久禎

(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