一種改進的基于神經網絡的文本分類算法
2008-01-01 00:00:00丁振國黎靖張卓
計算機應用研究 2008年6期
摘要：提出并實現了一種結合前饋型神經網絡和K最近鄰的文本分類算法。其中，在選取特征項時考慮到Web文本不同標簽組所代表的意義和權重有所區別，采用了一種改進的TFIDF特征選擇法。最后對設計的分類器進行了開放性測試，實驗結果表明該分類器顯著地提高了文本分類的查全率和查準率。
關鍵詞：文本分類； 神經網絡； K最近鄰； 特征選擇
中圖分類號：TP183文獻標志碼：A
文章編號：1001－3695(2008)06－1639－03
0引言
隨著網絡技術的發展，網絡上的電子文檔數量也迅速增長。如何有效地、更好地幫助用戶查找、過濾、管理這些海量數據顯得越來越重要，因此，Web文本挖掘技術應運而生。文本挖掘從功能上可以分為分類、聚類、趨勢預測等。其中，文本分類是指在給定分類體系下，根據文本內容自動確定文本類別的過程。從數學的角度看，文本分類是一個映射的過程，它將未標明類別的文本映射到已有的類別中。
20世紀90年代以來，出現了構建文本自動分類器的一種新方法，即基于機器學習的文本自動分類器。在這種方法中，一般是通過歸納文本集的特征自動創建一個分類器。這些文檔集合事先被領域專家人工地分到各類ci中，類集C={c1，…，cm}，對每一個類ci∈C構建的分類器相互之間獨立，每一個分類器都可作為一個規則決定文檔dj是否屬于類ci。如果類集C被更新，或者系統被轉移到完全不同的領域中，所要做的只是從新的人工分類文檔集合出發，通過機器學習自動地構造一個新的分類器，而不要求領域專家再重新介入[1]。
文本自動分類根據應用需求的不同可以劃分為基于分類體系的自動分類和基于信息過濾的自動分類。基于分類體系的自動分類其需求是面向特定語言環境，通過獲取主題詞及其權值來進行歸類。它的計算復雜性和涉及的語料范圍都有一定限制。目前這種分類方法很具有實用性。基于信息過濾的自動分類通過過濾海量的網絡文本資源，給不同類別的用戶提供其感興趣的信息，它要處理的語料數量和語言的深度是極其巨大的[2]。目前應用最廣泛的文本表示方式是向量空間模型(vector space model，VSM)，基于該模型的文本分類算法有多種，如簡單向量距離分類法、樸素貝葉斯分類法、K最近鄰分類法等[3]。這三種分類算法雖然有一定的效果，但受語料庫和外部環境的影響較大，如KNN算法的分類精確度受訓練集的類別分布情況的干擾，而且也沒有考慮到關鍵詞的匹配。本文提出的是一種結合人工神經網絡算法和K最近鄰算法的新的分類算法，能有效地彌補兩種算法各自的缺陷。
1人工神經網絡
神經網絡是由具有適應性的簡單單元組成的廣泛并行互連的網絡，它是基于連接學說構造的智能仿生模型，其組織能夠模擬生物神經系統對真實世界物體所作出的交互反應[4]。人工神經網絡是一種并行的分布式信息處理結構，它通過稱為連接的單向信號通路將一些處理單元(具有局部存儲和執行局部信息的處理能力)互連而成。每一個處理單元都有一個單輸出到所期望的連接并且分別傳送各自的輸出信號。每一個處理單元中執行的信息處理在它必須完全是局部的限制下可以被任意定義，即它必須只依賴于處理單元所接受的輸入激勵信號的當前值和處理單元本身所存儲的值[5]。
人工神經網絡技術可以很好地解決傳統文本分類方法在實現過程中遇到的一些難題。例如[2]：
a)在系統輸出結果與實際結果相差太大時自動學習，它的學習算法會自動調整系統本身，改變知識的存儲。同時由于采用了神經網絡技術，系統能自然地實現模糊推理功能。
b)具有很強的魯棒性和容錯性，善于聯想、概括、類比和推廣，任何局部的操作均不會影響整體效果。
c)自適應性神經網絡技術能根據所提供的數據，通過學習找出與輸出結果之間的內在聯系，從而求得問題的解答，而不僅僅依靠對問題的先驗知識和規則，因而它具有很好的適應性。
d)人工神經元網絡具有并行處理的特點，運行速度快，因而一方面可存儲大量的知識，另一方面又可保持較高的運行速度。
2實驗設計與結果
2．1文本特征維度約簡
文本分類的最大困難之一是特征空間的高維性，因此需要選擇合適的特征來表示文檔。常用的維度約簡方法有詞條特征選擇法和基于空間變換的特征選擇法[6]。在文本分類中使用較多的詞條特征選擇法有文檔頻率法(document frequency，DF)、互信息法(mutual information，MI)、信息增益法(information gain，IG)、χ2統計法、期望交叉熵法等。傳統的TFIDF法是靠統計詞條在文本集中出現的次數來決定其重要性。但這種方法存在明顯的不足，它的計算過程沒有考慮到特征項在類間和類內的分布情況，而且容易導致信息的遺失。本文采用一種改進的TFIDF特征選擇法來對文本向量進行降維。
由于特征項在Web文檔不同位置出現所代表的意義不同，可以考慮對不同的標簽組賦予不同的權重。本文將〈Title〉〈/Title〉標簽組中的特征項的權重因子設定為4，〈Font〉〈/Font〉設定為2，〈Strong〉〈/Strong〉設定為0．4，〈Big〉〈/Big〉設定為0．4，〈B〉〈/B〉設定為0．3，〈I〉〈/I〉設定為0．2。經權重因子調整后的TFIDF公式為
其中：Wik代表特征項k在文檔i中的權重；W0代表每個文檔的缺省權值；fik(title)代表特征項k在文檔i中〈Title〉〈/Title〉標簽組內出現的次數；W（title）代表〈Title〉〈/Title〉標簽組的權重因子；N代表分類文檔的總數；nk代表出現特征項k的文檔數；α代表一個較小的常量。另外，長文獻由于各種因素的影響，比短文獻有更大的機會與查詢進行匹配。為了抵消這種篇幅帶來的影響，經常要對特征項權重進行規范化處理，本文利用的是歐式距離長度w21+w22+…+w2n來處理。
2．2BP－KNN分類器的實現
本文設計的BP－KNN分類器是結合兩種常用分類方法的一種綜合算法。其中，神經網絡模塊采用的是三層前饋型BP網絡來進行知識的自動獲取，如圖1所示。BP網絡有三個基本層，即輸入層、隱含層和輸出層。每層都包含若干節點(神經元)。輸入層的節點數通常為輸入矢量的個數，輸出層節點數為輸出矢量的個數，確定適當的隱含層節點很重要，它直接影響網絡的性能，一般是根據經驗來確定。層與層之間的每個連接都有一個可以調整的權值，它是根據訓練數據不斷計算而得到的系數， 決定了一個輸入矢量對輸出矢量的影響。
人工神經網絡的分類過程主要分為訓練和測試兩個部分，如圖2所示。
1)訓練階段[7]
a)定義類別集合C={c1，…，ci，…，cn}，這些類別可以是層次式的，也可以是并列式的。
b)給出訓練文檔集合S={s1，…，sj，…，sm}，每個訓練文檔sj被標上所屬的類別標志ci。
c)統計S中所有文檔的特征矢量V(Sj)，確定代表C中每個類別的特征矢量V(ci)。
2)分類階段
a)對于測試文檔集合T={d1，…，dk，…，dr}中的每個待分類文檔dk，計算其特征矢量V(dk)與每個V(ci)之間的相似度sim(dk，ci)。
b)選取相似度最大的一個類別max sim(dk，ci)作為dk的類別。其中：ci∈C。
這里假定神經元j的凈輸入是Ij；凈輸出是Oj；誤差為errj；實際輸出為Tj；偏置為θj；單元i和j之間的權值為Wij；激勵函數采用S型函數fj(S)；學習率為l。具體算法如下：
輸入：訓練樣本、測試樣本；
輸出：一個訓練好的、有較好分類效果的分類器。
a) 初始化整個網絡的權值和各神經元的偏置；
b)while 所有的權值增值ΔWij都大于閾值ε{
c)for 每個訓練樣本 {
d)利用改進的TFIDF權重算法計算文檔向量，作為網絡輸入值
e)for隱含層和輸出層的每個單元j{
f)Ij=iWij Oi+θj
g)Oj=1/(1+l-Ij)}
h)for 輸出層每個單元j
i)errj=Oj(1-Oj)(Tj-Oj)
j)for 隱含層的每個單元j
k)errj=Oj(1-Oj)kerrkWjk
l)for 網絡中的每個權值 Wij{
m)ΔWij=(l)errjOj
n)Wij=Wij+ΔWij}
o)for每個神經元的偏置θj {
p)Δθj=(l)errj
q)θj=θj+Δθj}
r) }//while結束，訓練完畢
s)對每個待分類文本計算其特征項權值作為網絡的輸入向量，對網絡輸出的每個節點的值乘以0．618作為最終權值的一部分；
t)同時將要分類的文本向量放入由訓練文本向量集組成的空間中，利用K最近鄰法定位其所屬類別，并將每個類別的權值乘以0．382；
u)將通過BP網絡的輸出值與K最近鄰算法得出的結果相加，哪個類別對應的權值最大則該文檔就屬于此類別。
其中：K最近鄰算法中K值的確定可依據經驗取K=q，q為訓練集的樣本數；也可以按照商業上的普遍取法以10為標準。當神經網絡訓練完畢后，對每個待分類文檔只需要重復執行步驟s)~u)便能得到最終的分類。
2．3實驗結果
實驗中使用的訓練數據來自哈爾深工業大學譚松波的分類訓練集和北京大學天網2006年10月~2007年3月的訓練集，它包括11個大類共計5 582篇文檔；測試集來自北大天網提供的1 000個網頁實例以及哈工大提供的2 269個提取過的Web文檔。樣本集中類別及實例數量的分布情況如表1所示。
常用的評價文本分類性能的指標有查全率(recall)、查準率(precision)、F1值、宏觀F1值、微觀F1值。其中，查全率是指人工分類結果應有的文本中與分類系統分類結果一致的文本所占的比率；查準率是分類系統的結果中與人工分類相吻合的文本所占的比率。用公式表示如下：
查全率：Ri=NCRi/NCi；查準率：Pi=NCRi/NPi；
F1值：F1=2RiPi/（Ri+Pi）；宏觀F1值：macroF1=(1/m)∑mi=1F1i;
微觀F1值：microF1=(2×∑mi=1Pi×∑mi=1Ri)/[(∑mi=1Pi+∑mi=1Ri)×m]
其中：NCRi是正確分類到Ci類的文檔數；NCi是實際屬于Ci類的訓練文檔數；NPi是分類器預測為Ci類的文檔數；N是文檔總數；m是類別總數。經測試，本文設計的BP－KNN分類器的分類情況如表2所示。
從表2所示的數據可以看出，本文設計的分類器的整體性能比較令人滿意。其中，對科技類的文本分類效果最好，對就業類的文本分類效果最差。分析原因可能是因為就業類的訓練文檔較少，并且代表該類別的特征詞范圍較窄。對宏觀F1值和微觀F1值來說，訓練樣本數目的多少也直接影響它們的數值。本文通過不斷追加訓練文本來測試分類器的性能，測試結果如圖3所示。
從圖3可以看出，當訓練樣本集的數目大于5 500時，分類器的macroF1達到穩態，而microF1仍在增加，但上升幅度趨于平緩。同時通過實驗發現，訓練文本中特征項的選取也不是越多越好，在本文設計的分類器中，每篇文檔大約取50左右的特征項分類效果達到局部最優。
單純的前饋型神經網絡算法分類精度較高，但對訓練終止閾值的選取要求很高，而且訓練集的類別要盡可能服從均值分布，在訓練過程中也經常會出現自擬合的情況。KNN分類法的最大缺點就是分類精度不高，而且對K值的取值比較靈敏，一般的商業做法是以10作為默認值。本文設計的BP－KNN分類器將兩種分類算法的優勢有效結合起來，較好地克服了它們各自的缺陷，其分類性能也得到大幅提高。圖4對比了KNN分類法和BP－KNN分類法的分類質量。其中橫坐標代表本文提到的11個文本類別。
從圖4不難看出，本文設計的BP－KNN分類器的分類結果在大部分領域要優于KNN分類的結果，只是在體育類別(橫坐標為5)上分類質量較差一些。這主要是由于在該類中分類準確率較低造成的，分析其原因可能是在訓練階段分類器出現了自擬合，導致無法進一步學習體育類中的其余特征詞，從而無法準確辨別該類別的文本。
3結束語
本文采用BP神經網絡分類算法與KNN分類算法相結合的方法，設計了一種分類效果良好的文本分類器。在該分類器中，選取特征項時考慮到Web文本不同標簽組中的特征詞所代表的意義和權重有所區別，提出了一種改進的TFIDF特征選擇方法。通過實驗證明，該方法能有效地提高分類精度。本文最后還比較了BP－KNN分類器與傳統的KNN分類法在分類性能上的差異，得出的結論是BP－KNN的分類結果要整體優于傳統的分類算法所得到的結果，但在個別領域內的分類結果還不盡如人意。如何克服BP－KNN分類器的自擬合現象，進一步完善其分類效果，最大限度地提升分類器的性能，這將是本文下一步的工作。
參考文獻：
［1］郭昭輝，劉紹翰，武港山.基于神經網絡的中文文本分類中的特征選擇技術[J].計算機應用研究，2006，23(7):161－164.
[2]姚松源．文本自動分類系統的研究與實現[D].北京：北京工業大學，2003．
[3]劉鋼，胡四泉，范植華，等．神經網絡在文本分類上的一種應用[J].計算機工程與應用，2003，39（36）:73－74，92．
[4]陳世福，陳兆乾．人工智能與知識工程[M]． 南京：南京大學出版社，1997．
[5]SEBASTIANI F．Machine learning in automated text categorization[J].ACM Computing Surveys，2002，34(1):15－18.
[6]AAS K，EIKVIL L. Text categorization:a survey，NR 941[R].Norway:Norwegian Computing Center，1999．
[7]符燕華．Web文本數據挖掘研究[D].上海：同濟大學，2006．
[8]李曉明，閆宏飛，王繼民.搜索引擎——原理、技術與系統[M].北京：科學出版社，2005．
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
