一種改進(jìn)的基于神經(jīng)網(wǎng)絡(luò)的文本分類算法

摘要：提出并實(shí)現(xiàn)了一種結(jié)合前饋型神經(jīng)網(wǎng)絡(luò)和K最近鄰的文本分類算法。其中，在選取特征項(xiàng)時考慮到Web文本不同標(biāo)簽組所代表的意義和權(quán)重有所區(qū)別，采用了一種改進(jìn)的TFIDF特征選擇法。最后對設(shè)計(jì)的分類器進(jìn)行了開放性測試，實(shí)驗(yàn)結(jié)果表明該分類器顯著地提高了文本分類的查全率和查準(zhǔn)率。

關(guān)鍵詞：文本分類； 神經(jīng)網(wǎng)絡(luò)； K最近鄰； 特征選擇

中圖分類號：TP183文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)06－1639－03

0引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)上的電子文檔數(shù)量也迅速增長。如何有效地、更好地幫助用戶查找、過濾、管理這些海量數(shù)據(jù)顯得越來越重要，因此，Web文本挖掘技術(shù)應(yīng)運(yùn)而生。文本挖掘從功能上可以分為分類、聚類、趨勢預(yù)測等。其中，文本分類是指在給定分類體系下，根據(jù)文本內(nèi)容自動確定文本類別的過程。從數(shù)學(xué)的角度看，文本分類是一個映射的過程，它將未標(biāo)明類別的文本映射到已有的類別中。

20世紀(jì)90年代以來，出現(xiàn)了構(gòu)建文本自動分類器的一種新方法，即基于機(jī)器學(xué)習(xí)的文本自動分類器。在這種方法中，一般是通過歸納文本集的特征自動創(chuàng)建一個分類器。這些文檔集合事先被領(lǐng)域?qū)＜胰斯さ胤值礁黝恈i中，類集C={c1，…，cm}，對每一個類ci∈C構(gòu)建的分類器相互之間獨(dú)立，每一個分類器都可作為一個規(guī)則決定文檔dj是否屬于類ci。如果類集C被更新，或者系統(tǒng)被轉(zhuǎn)移到完全不同的領(lǐng)域中，所要做的只是從新的人工分類文檔集合出發(fā)，通過機(jī)器學(xué)習(xí)自動地構(gòu)造一個新的分類器，而不要求領(lǐng)域?qū)＜以僦匦陆槿隱1]。

文本自動分類根據(jù)應(yīng)用需求的不同可以劃分為基于分類體系的自動分類和基于信息過濾的自動分類。基于分類體系的自動分類其需求是面向特定語言環(huán)境，通過獲取主題詞及其權(quán)值來進(jìn)行歸類。它的計(jì)算復(fù)雜性和涉及的語料范圍都有一定限制。目前這種分類方法很具有實(shí)用性。基于信息過濾的自動分類通過過濾海量的網(wǎng)絡(luò)文本資源，給不同類別的用戶提供其感興趣的信息，它要處理的語料數(shù)量和語言的深度是極其巨大的[2]。目前應(yīng)用最廣泛的文本表示方式是向量空間模型(vector space model，VSM)，基于該模型的文本分類算法有多種，如簡單向量距離分類法、樸素貝葉斯分類法、K最近鄰分類法等[3]。這三種分類算法雖然有一定的效果，但受語料庫和外部環(huán)境的影響較大，如KNN算法的分類精確度受訓(xùn)練集的類別分布情況的干擾，而且也沒有考慮到關(guān)鍵詞的匹配。本文提出的是一種結(jié)合人工神經(jīng)網(wǎng)絡(luò)算法和K最近鄰算法的新的分類算法，能有效地彌補(bǔ)兩種算法各自的缺陷。

1人工神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)是由具有適應(yīng)性的簡單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它是基于連接學(xué)說構(gòu)造的智能仿生模型，其組織能夠模擬生物神經(jīng)系統(tǒng)對真實(shí)世界物體所作出的交互反應(yīng)[4]。人工神經(jīng)網(wǎng)絡(luò)是一種并行的分布式信息處理結(jié)構(gòu)，它通過稱為連接的單向信號通路將一些處理單元(具有局部存儲和執(zhí)行局部信息的處理能力)互連而成。每一個處理單元都有一個單輸出到所期望的連接并且分別傳送各自的輸出信號。每一個處理單元中執(zhí)行的信息處理在它必須完全是局部的限制下可以被任意定義，即它必須只依賴于處理單元所接受的輸入激勵信號的當(dāng)前值和處理單元本身所存儲的值[5]。

人工神經(jīng)網(wǎng)絡(luò)技術(shù)可以很好地解決傳統(tǒng)文本分類方法在實(shí)現(xiàn)過程中遇到的一些難題。例如[2]：

a)在系統(tǒng)輸出結(jié)果與實(shí)際結(jié)果相差太大時自動學(xué)習(xí)，它的學(xué)習(xí)算法會自動調(diào)整系統(tǒng)本身，改變知識的存儲。同時由于采用了神經(jīng)網(wǎng)絡(luò)技術(shù)，系統(tǒng)能自然地實(shí)現(xiàn)模糊推理功能。

b)具有很強(qiáng)的魯棒性和容錯性，善于聯(lián)想、概括、類比和推廣，任何局部的操作均不會影響整體效果。

c)自適應(yīng)性神經(jīng)網(wǎng)絡(luò)技術(shù)能根據(jù)所提供的數(shù)據(jù)，通過學(xué)習(xí)找出與輸出結(jié)果之間的內(nèi)在聯(lián)系，從而求得問題的解答，而不僅僅依靠對問題的先驗(yàn)知識和規(guī)則，因而它具有很好的適應(yīng)性。

d)人工神經(jīng)元網(wǎng)絡(luò)具有并行處理的特點(diǎn)，運(yùn)行速度快，因而一方面可存儲大量的知識，另一方面又可保持較高的運(yùn)行速度。

2實(shí)驗(yàn)設(shè)計(jì)與結(jié)果

2．1文本特征維度約簡

文本分類的最大困難之一是特征空間的高維性，因此需要選擇合適的特征來表示文檔。常用的維度約簡方法有詞條特征選擇法和基于空間變換的特征選擇法[6]。在文本分類中使用較多的詞條特征選擇法有文檔頻率法(document frequency，DF)、互信息法(mutual information，MI)、信息增益法(information gain，IG)、χ²統(tǒng)計(jì)法、期望交叉熵法等。傳統(tǒng)的TFIDF法是靠統(tǒng)計(jì)詞條在文本集中出現(xiàn)的次數(shù)來決定其重要性。但這種方法存在明顯的不足，它的計(jì)算過程沒有考慮到特征項(xiàng)在類間和類內(nèi)的分布情況，而且容易導(dǎo)致信息的遺失。本文采用一種改進(jìn)的TFIDF特征選擇法來對文本向量進(jìn)行降維。

由于特征項(xiàng)在Web文檔不同位置出現(xiàn)所代表的意義不同，可以考慮對不同的標(biāo)簽組賦予不同的權(quán)重。本文將〈Title〉〈/Title〉標(biāo)簽組中的特征項(xiàng)的權(quán)重因子設(shè)定為4，〈Font〉〈/Font〉設(shè)定為2，〈Strong〉〈/Strong〉設(shè)定為0．4，〈Big〉〈/Big〉設(shè)定為0．4，〈B〉〈/B〉設(shè)定為0．3，〈I〉〈/I〉設(shè)定為0．2。經(jīng)權(quán)重因子調(diào)整后的TFIDF公式為

其中：Wik代表特征項(xiàng)k在文檔i中的權(quán)重；W0代表每個文檔的缺省權(quán)值；fik(title)代表特征項(xiàng)k在文檔i中〈Title〉〈/Title〉標(biāo)簽組內(nèi)出現(xiàn)的次數(shù)；W（title）代表〈Title〉〈/Title〉標(biāo)簽組的權(quán)重因子；N代表分類文檔的總數(shù)；nk代表出現(xiàn)特征項(xiàng)k的文檔數(shù)；α代表一個較小的常量。另外，長文獻(xiàn)由于各種因素的影響，比短文獻(xiàn)有更大的機(jī)會與查詢進(jìn)行匹配。為了抵消這種篇幅帶來的影響，經(jīng)常要對特征項(xiàng)權(quán)重進(jìn)行規(guī)范化處理，本文利用的是歐式距離長度w21+w22+…+w2n來處理。

2．2BP－KNN分類器的實(shí)現(xiàn)

本文設(shè)計(jì)的BP－KNN分類器是結(jié)合兩種常用分類方法的一種綜合算法。其中，神經(jīng)網(wǎng)絡(luò)模塊采用的是三層前饋型BP網(wǎng)絡(luò)來進(jìn)行知識的自動獲取，如圖1所示。BP網(wǎng)絡(luò)有三個基本層，即輸入層、隱含層和輸出層。每層都包含若干節(jié)點(diǎn)(神經(jīng)元)。輸入層的節(jié)點(diǎn)數(shù)通常為輸入矢量的個數(shù)，輸出層節(jié)點(diǎn)數(shù)為輸出矢量的個數(shù)，確定適當(dāng)?shù)碾[含層節(jié)點(diǎn)很重要，它直接影響網(wǎng)絡(luò)的性能，一般是根據(jù)經(jīng)驗(yàn)來確定。層與層之間的每個連接都有一個可以調(diào)整的權(quán)值，它是根據(jù)訓(xùn)練數(shù)據(jù)不斷計(jì)算而得到的系數(shù)， 決定了一個輸入矢量對輸出矢量的影響。

人工神經(jīng)網(wǎng)絡(luò)的分類過程主要分為訓(xùn)練和測試兩個部分，如圖2所示。

1)訓(xùn)練階段[7]

a)定義類別集合C={c1，…，ci，…，cn}，這些類別可以是層次式的，也可以是并列式的。

b)給出訓(xùn)練文檔集合S={s1，…，sj，…，sm}，每個訓(xùn)練文檔sj被標(biāo)上所屬的類別標(biāo)志ci。

c)統(tǒng)計(jì)S中所有文檔的特征矢量V(Sj)，確定代表C中每個類別的特征矢量V(ci)。

2)分類階段

a)對于測試文檔集合T={d1，…，dk，…，dr}中的每個待分類文檔dk，計(jì)算其特征矢量V(dk)與每個V(ci)之間的相似度sim(dk，ci)。

b)選取相似度最大的一個類別max sim(dk，ci)作為dk的類別。其中：ci∈C。

這里假定神經(jīng)元j的凈輸入是Ij；凈輸出是Oj；誤差為errj；實(shí)際輸出為Tj；偏置為θj；單元i和j之間的權(quán)值為Wij；激勵函數(shù)采用S型函數(shù)fj(S)；學(xué)習(xí)率為l。具體算法如下：

輸入：訓(xùn)練樣本、測試樣本；

輸出：一個訓(xùn)練好的、有較好分類效果的分類器。

a) 初始化整個網(wǎng)絡(luò)的權(quán)值和各神經(jīng)元的偏置；

b)while 所有的權(quán)值增值ΔWij都大于閾值ε{

c)for 每個訓(xùn)練樣本 {

d)利用改進(jìn)的TFIDF權(quán)重算法計(jì)算文檔向量，作為網(wǎng)絡(luò)輸入值

e)for隱含層和輸出層的每個單元j{

f)Ij=iWij 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)kerrkWjk

l)for 網(wǎng)絡(luò)中的每個權(quán)值 Wij{

m)ΔWij=(l)errjOj

n)Wij=Wij+ΔWij}

o)for每個神經(jīng)元的偏置θj {

p)Δθj=(l)errj

q)θj=θj+Δθj}

r) }//while結(jié)束，訓(xùn)練完畢

s)對每個待分類文本計(jì)算其特征項(xiàng)權(quán)值作為網(wǎng)絡(luò)的輸入向量，對網(wǎng)絡(luò)輸出的每個節(jié)點(diǎn)的值乘以0．618作為最終權(quán)值的一部分；

t)同時將要分類的文本向量放入由訓(xùn)練文本向量集組成的空間中，利用K最近鄰法定位其所屬類別，并將每個類別的權(quán)值乘以0．382；

u)將通過BP網(wǎng)絡(luò)的輸出值與K最近鄰算法得出的結(jié)果相加，哪個類別對應(yīng)的權(quán)值最大則該文檔就屬于此類別。

其中：K最近鄰算法中K值的確定可依據(jù)經(jīng)驗(yàn)取K=q，q為訓(xùn)練集的樣本數(shù)；也可以按照商業(yè)上的普遍取法以10為標(biāo)準(zhǔn)。當(dāng)神經(jīng)網(wǎng)絡(luò)訓(xùn)練完畢后，對每個待分類文檔只需要重復(fù)執(zhí)行步驟s)~u)便能得到最終的分類。

2．3實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中使用的訓(xùn)練數(shù)據(jù)來自哈爾深工業(yè)大學(xué)譚松波的分類訓(xùn)練集和北京大學(xué)天網(wǎng)2006年10月~2007年3月的訓(xùn)練集，它包括11個大類共計(jì)5 582篇文檔；測試集來自北大天網(wǎng)提供的1 000個網(wǎng)頁實(shí)例以及哈工大提供的2 269個提取過的Web文檔。樣本集中類別及實(shí)例數(shù)量的分布情況如表1所示。

常用的評價文本分類性能的指標(biāo)有查全率(recall)、查準(zhǔn)率(precision)、F1值、宏觀F1值、微觀F1值。其中，查全率是指人工分類結(jié)果應(yīng)有的文本中與分類系統(tǒng)分類結(jié)果一致的文本所占的比率；查準(zhǔn)率是分類系統(tǒng)的結(jié)果中與人工分類相吻合的文本所占的比率。用公式表示如下：

查全率：Ri=NCRi/NCi；查準(zhǔn)率：Pi=NCRi/NPi；

F1值：F1=2RiPi/（Ri+Pi）；宏觀F1值：macroF1=(1/m)∑mi=1F1i;

微觀F1值：microF1=(2×∑mi=1Pi×∑mi=1Ri)/[(∑mi=1Pi+∑mi=1Ri)×m]

其中：NCRi是正確分類到Ci類的文檔數(shù)；NCi是實(shí)際屬于Ci類的訓(xùn)練文檔數(shù)；NPi是分類器預(yù)測為Ci類的文檔數(shù)；N是文檔總數(shù)；m是類別總數(shù)。經(jīng)測試，本文設(shè)計(jì)的BP－KNN分類器的分類情況如表2所示。

從表2所示的數(shù)據(jù)可以看出，本文設(shè)計(jì)的分類器的整體性能比較令人滿意。其中，對科技類的文本分類效果最好，對就業(yè)類的文本分類效果最差。分析原因可能是因?yàn)榫蜆I(yè)類的訓(xùn)練文檔較少，并且代表該類別的特征詞范圍較窄。對宏觀F1值和微觀F1值來說，訓(xùn)練樣本數(shù)目的多少也直接影響它們的數(shù)值。本文通過不斷追加訓(xùn)練文本來測試分類器的性能，測試結(jié)果如圖3所示。

從圖3可以看出，當(dāng)訓(xùn)練樣本集的數(shù)目大于5 500時，分類器的macroF1達(dá)到穩(wěn)態(tài)，而microF1仍在增加，但上升幅度趨于平緩。同時通過實(shí)驗(yàn)發(fā)現(xiàn)，訓(xùn)練文本中特征項(xiàng)的選取也不是越多越好，在本文設(shè)計(jì)的分類器中，每篇文檔大約取50左右的特征項(xiàng)分類效果達(dá)到局部最優(yōu)。

單純的前饋型神經(jīng)網(wǎng)絡(luò)算法分類精度較高，但對訓(xùn)練終止閾值的選取要求很高，而且訓(xùn)練集的類別要盡可能服從均值分布，在訓(xùn)練過程中也經(jīng)常會出現(xiàn)自擬合的情況。KNN分類法的最大缺點(diǎn)就是分類精度不高，而且對K值的取值比較靈敏，一般的商業(yè)做法是以10作為默認(rèn)值。本文設(shè)計(jì)的BP－KNN分類器將兩種分類算法的優(yōu)勢有效結(jié)合起來，較好地克服了它們各自的缺陷，其分類性能也得到大幅提高。圖4對比了KNN分類法和BP－KNN分類法的分類質(zhì)量。其中橫坐標(biāo)代表本文提到的11個文本類別。

從圖4不難看出，本文設(shè)計(jì)的BP－KNN分類器的分類結(jié)果在大部分領(lǐng)域要優(yōu)于KNN分類的結(jié)果，只是在體育類別(橫坐標(biāo)為5)上分類質(zhì)量較差一些。這主要是由于在該類中分類準(zhǔn)確率較低造成的，分析其原因可能是在訓(xùn)練階段分類器出現(xiàn)了自擬合，導(dǎo)致無法進(jìn)一步學(xué)習(xí)體育類中的其余特征詞，從而無法準(zhǔn)確辨別該類別的文本。

3結(jié)束語

本文采用BP神經(jīng)網(wǎng)絡(luò)分類算法與KNN分類算法相結(jié)合的方法，設(shè)計(jì)了一種分類效果良好的文本分類器。在該分類器中，選取特征項(xiàng)時考慮到Web文本不同標(biāo)簽組中的特征詞所代表的意義和權(quán)重有所區(qū)別，提出了一種改進(jìn)的TFIDF特征選擇方法。通過實(shí)驗(yàn)證明，該方法能有效地提高分類精度。本文最后還比較了BP－KNN分類器與傳統(tǒng)的KNN分類法在分類性能上的差異，得出的結(jié)論是BP－KNN的分類結(jié)果要整體優(yōu)于傳統(tǒng)的分類算法所得到的結(jié)果，但在個別領(lǐng)域內(nèi)的分類結(jié)果還不盡如人意。如何克服BP－KNN分類器的自擬合現(xiàn)象，進(jìn)一步完善其分類效果，最大限度地提升分類器的性能，這將是本文下一步的工作。

參考文獻(xiàn)：

［1］郭昭輝，劉紹翰，武港山.基于神經(jīng)網(wǎng)絡(luò)的中文文本分類中的特征選擇技術(shù)[J].計(jì)算機(jī)應(yīng)用研究，2006，23(7):161－164.

[2]姚松源．文本自動分類系統(tǒng)的研究與實(shí)現(xiàn)[D].北京：北京工業(yè)大學(xué)，2003．

[3]劉鋼，胡四泉，范植華，等．神經(jīng)網(wǎng)絡(luò)在文本分類上的一種應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（36）:73－74，92．

[4]陳世福，陳兆乾．人工智能與知識工程[M]． 南京：南京大學(xué)出版社，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文本數(shù)據(jù)挖掘研究[D].上海：同濟(jì)大學(xué)，2006．

[8]李曉明，閆宏飛，王繼民.搜索引擎——原理、技術(shù)與系統(tǒng)[M].北京：科學(xué)出版社，2005．

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文