甄志龍，于 非，王海鵑

(通化師范學(xué)院 計(jì)算機(jī)科學(xué)系，吉林 通化 134002)

隨著計(jì)算機(jī)、網(wǎng)絡(luò)以及通信技術(shù)的迅猛發(fā)展，如何有效地組織和管理信息，并且快速、準(zhǔn)確、全面地找到用戶所需要的信息是當(dāng)前信息技術(shù)領(lǐng)域面臨的一大挑戰(zhàn).文本分類可以在較大程度上解決信息雜亂現(xiàn)象，而且在信息檢索、信息過濾、搜索引擎等領(lǐng)域都有廣泛的應(yīng)用.文本分類是依據(jù)文本的內(nèi)容，將每篇文本自動(dòng)歸入到一個(gè)或多個(gè)預(yù)先定義好的類別中[1].在文本分類過程中經(jīng)常會(huì)遇到高維的特征空間，特征向量的維數(shù)可達(dá)數(shù)萬維甚至十幾萬維，眾多的特征項(xiàng)中可能含有大量的冗余或噪聲，這不僅會(huì)影響到分類的精度，還會(huì)導(dǎo)致過高的計(jì)算復(fù)雜度，使某些分類算法變得不可行.因此，許多維數(shù)約減方法[2,3,4]已應(yīng)用于文本的表示和索引.考慮到文本中的詞與詞之間存在某種聯(lián)系，即存在某種潛在的語義結(jié)構(gòu)，文獻(xiàn)[5]中提出了經(jīng)典的潛在語義索引(Latent Semantic Indexing，LSI)文本表示方法.傳統(tǒng)的向量空間模型是假設(shè)詞條間相互獨(dú)立，事實(shí)上，詞語之間存在著關(guān)聯(lián)性，出現(xiàn)了“斜交”現(xiàn)象，這必然會(huì)影響文本處理的結(jié)果.本文提出了一種有監(jiān)督保局索引(Supervised Locality Preserving Indexing，SLPI)的方法，SLPI的目標(biāo)是找出高維特征空間中的樣本對(duì)應(yīng)在低維空間中的文本表示，從而提高文本分類的性能.

1 有監(jiān)督保局索引(SLPI)

SLPI的核心思想是基于He[6]等人提出的LPP方法.但是在監(jiān)督模式、鄰接圖的構(gòu)造、邊的權(quán)重和約束條件上都與LPP不同.

算法的具體過程描述如下：

Step1.構(gòu)造鄰接無向圖G.圖G中有n個(gè)結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)代表一篇文本.如果兩個(gè)文本Xi和Xj屬于同一類，則在結(jié)點(diǎn)i和j之間放一條邊；否則，結(jié)點(diǎn)之間沒有邊連接.

Step2.建立相似矩陣W=(Wij)n×n.在Step1圖G中，當(dāng)兩點(diǎn)之間沒有邊相連時(shí)，Wij=0；當(dāng)兩點(diǎn)之間有邊相連時(shí)，采用Jaccard系數(shù)給定一個(gè)相似性Wij(權(quán)重).即

Wij={XTi·Xj‖Xi‖2+‖Xj‖2-XTi·Xj，(如果Xi和Xj屬于同一個(gè)類別)

0，(如果Xi和Xj不屬于同一個(gè)類別)

(1)

Step3.根據(jù)相似矩陣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是數(shù)據(jù)矩陣D=diag(∑nj=1W1j，∑nj=1W2j,…，∑nj=1Wnj)；L=D-W稱為拉普拉斯矩陣(Laplacian Matrix).

設(shè)定約束條件aTa=1,此時(shí)(3)式可改寫成為：

J(a)=argminaaaTXLXTaaTa

(4)

利用拉格朗日乘子法，最小值出現(xiàn)在

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

(5)

經(jīng)過矩陣微分運(yùn)算得：

XLXTa=λa

(6)

于是，問題轉(zhuǎn)化為求解矩陣特征值和特征向量問題，取ai(i=1,2,…，l)為對(duì)應(yīng)于特征值λi(λ1<λ2<…<λl)特征向量.

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)

語料是文本分類領(lǐng)域中的Reuters-21578數(shù)據(jù)集.我們選擇了6個(gè)類：trade，interest，wheat，corn，oilseed，gnp.訓(xùn)練集1334篇文本，測試集457篇文本.數(shù)據(jù)的分布如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)的分布

2.2 實(shí)驗(yàn)結(jié)果

本文采用K近鄰分類器(K=21).圖1和2分別顯示了實(shí)驗(yàn)數(shù)據(jù)集上宏平均和微平均的結(jié)果.可以看出，在文本分類性能上SLPI明顯優(yōu)于Original Features和LSI.

圖1 實(shí)驗(yàn)數(shù)據(jù)上宏平均的結(jié)果

3 結(jié)束語

文本分析與處理過程中的一個(gè)基本問題是文本的表示和索引.鑒于經(jīng)典的潛在語義索引方法屬于無監(jiān)督模式，本文提出了一種有監(jiān)督局部保持索引的文本表示方法.此方法通過類別信息所求得的投影矩陣，將原有的文本表示轉(zhuǎn)換成新的文本表示，即將高維空間中的問題轉(zhuǎn)化到低維空間中處理。利用K近鄰分類器，在Reuters-21578數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明文中所提出的文本表示方法對(duì)文本分類的性能有很大提高。

參考文獻(xiàn)：

[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.