文本分類中基于位置和類別信息的一種特征降維方法

摘 要：從文本特征項(xiàng)所處的位置角度提出了特征項(xiàng)基于位置的降維方法；同時(shí)結(jié)合特征的類別分布進(jìn)行了二次特征降維。這種基于位置和類別相結(jié)合的特征降維方法在最大程度減少信息損失的條件下，實(shí)現(xiàn)了特征維數(shù)的有效壓縮。實(shí)驗(yàn)表明，該方法有較高的文本分類效率。

關(guān)鍵詞：文本分類； 特征選擇； 特征降維； 位置加權(quán)； 類別分布

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695(2008)08-2292-03

Method of feature reduction in text classification

based on position and sort information

LIU Hai-fenga，b， WANG Yuan-yuana， ZHANG Xue-renb， YAO Ze-qingb

(a. Institute of Command Automation， b.Institute of Sciences， PLA University of Science Technology， Nanjing 210007， China)

Abstract:From the position of the terms， this paper put forward a method to reduce the dimensionality. Meanwhile， combined with the sorts distributing， it once more reduced the feature dimension. Therefore，in precondition of the information loss least， connecting with the two aspects， used this method to complete the text feature decrease smartly. The test shows that this method has better precision in the text categorization.

Key words：text categorization; feature selection; feature reduce; positionweight; sort distribution

Internet的迅猛發(fā)展改變了人們的生活方式，人類社會(huì)步入了以網(wǎng)絡(luò)為信息載體的全新信息時(shí)代。伴隨著Web信息量的指數(shù)形式增長(zhǎng)，在享受著信息“海洋”所提供的便利的同時(shí)，“信息迷航”的困境使得人們對(duì)如何獲取有效信息提出了更高的要求。作為信息處理技術(shù)的重要內(nèi)容之一，文本自動(dòng)分類技術(shù)已成為文本挖掘的研究熱點(diǎn)之一。文本分類是指在給定的分類體系下，根據(jù)文本內(nèi)容自動(dòng)確定文本所屬類別的過(guò)程。將文本分類技術(shù)與搜索引擎、信息過(guò)濾等信息處理技術(shù)相結(jié)合，能夠有效地提高信息服務(wù)的質(zhì)量，它是文本挖掘的一個(gè)重要組成部分，在情報(bào)檢索、信息過(guò)濾等許多方面有重要現(xiàn)實(shí)意義和廣闊的應(yīng)用前景。

1 文本分類的主要問(wèn)題及其處理方法

總的說(shuō)來(lái)，文本分類方法可分為基于知識(shí)和基于距離兩種。基于知識(shí)的方法是指借助專家的經(jīng)驗(yàn)知識(shí)，構(gòu)建分類專家系統(tǒng)作為分類器進(jìn)行分類。由于這種模式費(fèi)時(shí)費(fèi)力，并且擴(kuò)展性差，難以適用于大規(guī)模的文本分類，特別是基于Web的文本分類要求。目前普遍采用的是基于距離分類的方法，如樸素貝葉斯方法、決策樹(shù)方法、k-近鄰方法、回歸模型方法、神經(jīng)網(wǎng)絡(luò)方法以及支持向量機(jī)方法等^[1]。文本自動(dòng)分類的關(guān)鍵問(wèn)題是文本的合理表示、特征降維以及分類器的構(gòu)造。

1.1 向量空間模型及其主要問(wèn)題

在文本表示方法上基于向量空間模型的分類模式具有概念簡(jiǎn)單、應(yīng)用方便等優(yōu)點(diǎn)，是主流的文本分類模型之一。在向量空間算法模型中，文本dj被映射為一個(gè)特征向量：

 ，需分類的文本為dj，兩者的相似度可用向量之間的夾角來(lái)度量，夾角越小說(shuō)明相似度越高。相似度計(jì)算可以使用常用的向量夾角余弦公式:

sim(di，dj)=∑nk=1wikwjk/∑nk=1w2ik∑nk=1w2ik（3）

向量空間模型的優(yōu)點(diǎn)在于將非結(jié)構(gòu)化的文本表示為向量形式，使得各種數(shù)學(xué)處理成為可能。但是其不足之處也很明顯:

a）該模型假定特征項(xiàng)之間相互獨(dú)立，然而實(shí)際情況是一詞多義和多詞同義現(xiàn)象在文本中非常普遍。這種詞語(yǔ)之間關(guān)系相互獨(dú)立的基本假設(shè)在實(shí)際應(yīng)用中很難得到滿足，因此影響了該模式對(duì)文本表示的準(zhǔn)確性。

b）文本的向量表示帶來(lái)的另一個(gè)困難是文本向量維數(shù)太高，這給基于自動(dòng)分類模式下機(jī)器的存儲(chǔ)及運(yùn)算帶來(lái)了很大開(kāi)銷。從矩陣A的列向量看，每個(gè)列向量的構(gòu)成元素為文本的特征項(xiàng)（通常為詞或詞組），而文本中對(duì)表達(dá)其所屬類別有比較強(qiáng)說(shuō)服力的詞匯是非常多的。目前漢語(yǔ)的常用詞有幾萬(wàn)個(gè)，還有不少專業(yè)名詞和技術(shù)名詞，也就是說(shuō)一個(gè)普通的文本經(jīng)過(guò)分詞處理（包括去除停用詞、特高頻詞、特低頻詞等）后會(huì)有幾千甚至上萬(wàn)個(gè)詞，一個(gè)篇幅較長(zhǎng)的文本其特征空間維數(shù)通常是幾千甚至上萬(wàn)維。再?gòu)男邢蛄靠矗谋緛?lái)自于文本集，一般說(shuō)來(lái)，用于文本自動(dòng)分類的訓(xùn)練集中的文本不能太少，通常也要有1 000~3 000篇，否則類別信息不足。這樣行的維數(shù)也很高。分類器的算法和實(shí)現(xiàn)的復(fù)雜度都會(huì)隨著矩陣維數(shù)的增加而增加，而A的維數(shù)之高使得大多數(shù)機(jī)器學(xué)習(xí)算法無(wú)法承受。

c)訓(xùn)練文本類別分布的傾斜現(xiàn)象在文本分類中也是一個(gè)突出的問(wèn)題。即使是著名的文本分類語(yǔ)料Reuters-21578的ApteMod版本^[3]，其類別分布也非常不均。最大類含有2 877個(gè)文本，但是82%的類中文本數(shù)低于100個(gè)，并且33%的類中甚至低于10個(gè)。在特征降維時(shí)一些小類的樣本常常會(huì)作為噪聲而被刪除。這種條件下其模式識(shí)別的復(fù)雜度較高，以至于難以取得非常理想的分類效果。

能否進(jìn)行有效的降維處理對(duì)文本分類的訓(xùn)練時(shí)間、分類準(zhǔn)確性都有顯著的影響，所以降維過(guò)程是提高文本分類準(zhǔn)確率和有效率的關(guān)鍵。

1.2 文本特征降維常用的方法

特征選擇和特征抽取(feature extraction) 是文本特征降維中的主要方法。特征選擇一般是指依據(jù)某個(gè)準(zhǔn)則從眾多原始特征中選擇部分最能反映模式類別統(tǒng)計(jì)特性的相關(guān)特征，即要找到能反映文本內(nèi)容的特征集的最優(yōu)解子集，本質(zhì)上是對(duì)特征集合的約簡(jiǎn)。目前用于特征選擇的方法大致有文檔頻度、特征頻度、特征熵、互信息、信息增益、χ2統(tǒng)計(jì)量、特征權(quán)、期望交叉熵、文本證據(jù)權(quán)、幾率比等，這些模型由于構(gòu)造相對(duì)簡(jiǎn)單、易于理解而得到廣泛應(yīng)用。

特征抽取就是基于特征項(xiàng)之間的語(yǔ)義相關(guān)性、類別特征集對(duì)類內(nèi)文本聚合程度、類間離散程度的影響力等方面考量而對(duì)文本特征集的一種壓縮。在中文文本分類中，這種模式著眼于解決特征選擇方法所遇到的文本特征項(xiàng)之間的一詞多義、多詞同義、近義等現(xiàn)象所引起的特征壓縮瓶頸。常用的特征抽取方法可以分為主成分分析、潛在語(yǔ)義標(biāo)引、非負(fù)矩陣分解等^[4]。這些方法從不同的角度度量特征對(duì)文本分類所起的作用，但多數(shù)還是以文本特征項(xiàng)矩陣A為基礎(chǔ)而進(jìn)行的一系列降維模式研究。但是這些模式的一個(gè)顯著問(wèn)題是沒(méi)有利用特征項(xiàng)的位置信息，使得不同位置的特征項(xiàng)在文本中的不同作用沒(méi)有顯現(xiàn)出來(lái)。

本文從文本類和特征項(xiàng)的位置因素結(jié)合方面對(duì)文本分類方法進(jìn)行探討。2 類別—特征項(xiàng)向量模型的相關(guān)概念及文本分類算法

2.1 使用類別—特征項(xiàng)模型進(jìn)行矩陣維數(shù)壓縮

與文本—特征項(xiàng)矩陣A的構(gòu)成相似，筆者考慮建立類別—特征項(xiàng)矩陣體系用于文本分類。具體說(shuō)來(lái)，類似于構(gòu)建文本—特征項(xiàng)矩陣A用來(lái)表示文本，現(xiàn)在建立的矩陣可以設(shè)為^[5]

2.2 使用特征選擇方法對(duì)矩陣維數(shù)進(jìn)行二次壓縮

本文將特征項(xiàng)在文本中的位置作為考量因素再?gòu)男械慕嵌冗M(jìn)行降維。如前所述，一個(gè)普通的文本經(jīng)過(guò)分詞處理后有幾千甚至上萬(wàn)個(gè)詞可以作為特征項(xiàng)，一個(gè)篇幅較長(zhǎng)的文本的特征空間維數(shù)是幾千甚至幾萬(wàn)維是常有的現(xiàn)象。對(duì)于分類器來(lái)說(shuō)，仍然很難處理以這種模式構(gòu)成的類別—特征項(xiàng)矩陣B。但是，特征詞對(duì)文本分類的作用是不同的，文本的不同部位對(duì)文本的主題表達(dá)能力是有區(qū)別的。從針對(duì)文獻(xiàn)整體的檢準(zhǔn)率的角度看，文獻(xiàn)題名中的詞最有用，其次為文獻(xiàn)中的小標(biāo)題或章節(jié)名或文獻(xiàn)的摘要，最后為文獻(xiàn)正文中的詞^[8]。將特征項(xiàng)在文本中的位置作為確定其權(quán)重的因素之一，再結(jié)合詞頻進(jìn)行權(quán)值的確定，就是通常所說(shuō)的位置加權(quán)法。無(wú)論哪種類型的文本，其標(biāo)題部分所含有的特征信息都多于文章其余部分。但是，單純從標(biāo)題中抽取特征信息對(duì)文本進(jìn)行分類是不夠的，還應(yīng)該考慮摘要部分;而對(duì)沒(méi)有摘要的文章，從正文的標(biāo)題和子標(biāo)題中抽取特征信息的效果也要優(yōu)于單純從正文標(biāo)題中抽取^[9]。文獻(xiàn)[10]通過(guò)對(duì)涉及經(jīng)濟(jì)、教育、文學(xué)和心理學(xué)四個(gè)領(lǐng)域的1 800篇文本進(jìn)行分析、實(shí)驗(yàn)，對(duì)Web文本所含有的12個(gè)信息分布位置——網(wǎng)頁(yè)題名(title 項(xiàng))、文章標(biāo)題(bt)、第一段首句(ds1)、第一段尾句(dw1)、第二段首句(ds2) 、第二段尾句(dw2)、 第三段首句(ds3)、 第三段尾句(dw3)、首段(sd)、尾段(wd)、其他段(qt，即除去sd、wd，并且不包括ds2、dw2、ds3、dw3 之外的文本其他部分)、html 標(biāo)記(html)等對(duì)文本的表達(dá)能力進(jìn)行了詳細(xì)的統(tǒng)計(jì)分析，得到各個(gè)位置對(duì)主題表達(dá)能力的先后順序并建議位置權(quán)重方案為^[10]

bt ∶html ∶sd ∶ds1 ∶title ∶dw1 ∶qt ∶wd ∶ds2 ∶dw2 ∶ds3 ∶dw3 =

5∶5∶5∶4∶4∶4∶2∶2∶2∶2∶2∶2（7）

本文考慮用文本中較為重要的部分，即文章標(biāo)題、html 標(biāo)記（如果文本為Web上的html文本）、關(guān)鍵詞、摘要、首段；第一段首句、網(wǎng)頁(yè)題名、第一段尾句等所含有的特征項(xiàng)為矩陣B中的特征項(xiàng)來(lái)表示文本。相比較整篇文本中的特征項(xiàng)個(gè)數(shù)，這部分內(nèi)容所含有的特征項(xiàng)個(gè)數(shù)要少得多。具體的基于位置加權(quán)處理方法是：

H1={Ti|Ti為文章標(biāo)題、html標(biāo)記、關(guān)鍵詞中特征項(xiàng)}

H2={Ti|Ti為摘要、第一段首句、網(wǎng)頁(yè)題名中特征項(xiàng)}（8）

定義矩陣B中的元素為

w＾ij=6wij 若Ti∈H1∩Sj

4wij 若Ti∈H2∩Sj

5wij 若Ti∈H1∩H2∩Sj(9)

在此基礎(chǔ)上，將待分類的文本d在每個(gè)類別Sj中表示成由上述特征項(xiàng)的相應(yīng)權(quán)值構(gòu)成的向量Sj=(w＾1j，w＾2j，…，w＾mj)T（j=1，2，…，n）；按照類別將Sj各分量相加，其和作為文本d在Sj中的類屬權(quán)重，權(quán)重最大者所對(duì)應(yīng)的類別即為文本d所屬類別。 綜上所述，本文提出一種基于類別和位置的特征降維方法。

2.3 基于類別—特征項(xiàng)模型的文本分類算法及其特點(diǎn)

類別—特征項(xiàng)模型對(duì)文本進(jìn)行分類的主要步驟為：

a）對(duì)待分類文本d進(jìn)行分詞、過(guò)濾；按照式（8）抽取特征項(xiàng)。

b）根據(jù)式（6）、（10）計(jì)算類別—特征項(xiàng)矩陣B中的元素w＾ij，構(gòu)造矩陣B。

c）將矩陣B的每個(gè)列向量Sj=(w＾1j，w＾2j，…，w＾mj)T(j=1，2，…，n)的各分量相加求和：

vj=∑mi=1w＾ij; j=1，2，…，n(10)

d）判別類屬，若vk=max{v1，v2，…，vn}，則將d劃歸到類別Sk中。

相比傳統(tǒng)的向量空間模型，類別—特征項(xiàng)向量模型具有以下兩個(gè)顯著特點(diǎn)：

a）類別—特征項(xiàng)矩陣B相比較文本—特征項(xiàng)矩陣A來(lái)說(shuō)，其維數(shù)的下降幅度非常大，易于各種分類器的處理。

b）在傳統(tǒng)的向量空間模型中，就某一文本而言，特征項(xiàng)出現(xiàn)與否具有偶然性，使得矩陣A中的數(shù)據(jù)呈現(xiàn)稀疏現(xiàn)象；而在類別—特征項(xiàng)矩陣B中，對(duì)于特定的一個(gè)具體類別而言，其具有代表性的特征項(xiàng)非常穩(wěn)定，一些名詞特別是一些類別的專有名詞、技術(shù)名詞等常常用于描述該類別的特征，而文本的作者也往往傾向于使用類別中頻率較高的詞語(yǔ)^[6]。也就是說(shuō)，大量的同類文本中，其代表性詞語(yǔ)是相對(duì)固定的。

3 實(shí)驗(yàn)結(jié)果及其分析

本文對(duì)上述方法的分類效果進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)為新浪網(wǎng)上下載的3 376篇文本，分為房地產(chǎn)（550篇）、金融（512篇）、體育（530篇）、計(jì)算機(jī)（602篇）、音樂(lè)（495篇）以及旅游（687篇）。實(shí)驗(yàn)時(shí)采用四分交叉實(shí)驗(yàn)法，將3 580篇文本平均分為四份，三份為訓(xùn)練集，一份為測(cè)試集；每份輪流作為測(cè)試集循環(huán)測(cè)試四次，取平均值為測(cè)試結(jié)果。剔除特高頻詞、低頻詞以及停用詞等對(duì)文本進(jìn)行預(yù)處理，效果評(píng)估函數(shù)使用常用的查準(zhǔn)率、查全率和F1測(cè)試值：

查準(zhǔn)率=分類的正確文本數(shù)/實(shí)際分類文本數(shù)

查全率=分類的正確文本數(shù)/應(yīng)有文本數(shù)

F1=（查準(zhǔn)率×查全率×2）/（查準(zhǔn)率+查全率）

分類結(jié)果統(tǒng)計(jì)如表1所示。

表1 文本分類實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)%類別房地產(chǎn)金融體育計(jì)算機(jī)音樂(lè)旅游查準(zhǔn)率84.3 87.292.387.484.288.2查全率85.2 80.485.292.183.790.4F1值84.783.788.689.783.989.3從表1中可以得到，平均查準(zhǔn)率為87.3%，查全率為86.2%;測(cè)試值為86.7 %。使用本文提到的特征降維方法對(duì)文本進(jìn)行分類，分類效果還是令人滿意的。

4 結(jié)束語(yǔ)

本文提出的類別—特征項(xiàng)文本分類模型，從類別和特征位置兩個(gè)方面先后兩次對(duì)文本矩陣維數(shù)進(jìn)行壓縮，在盡量保留分類信息的同時(shí)解決了文本分類中最困難的特征降維問(wèn)題。其高效的降維效率使得各種文本分類器能有效工作，有效地解決了數(shù)據(jù)存儲(chǔ)、分類開(kāi)銷等傳統(tǒng)的向量空間模型很難解決的問(wèn)題。今后的工作重點(diǎn)是在本系統(tǒng)的基礎(chǔ)上，更深入地結(jié)合機(jī)器學(xué)習(xí)、自然語(yǔ)言處理等理論知識(shí)，嘗試其他分類算法，進(jìn)一步提高分類查全率和查準(zhǔn)率。

參考文獻(xiàn)：

[1]蘇金樹(shù)，張博鋒，徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào)，2006，17（9）：1848-1859.

[2]劉海峰，王元元.基于向量模型的文本檢索若干問(wèn)題研究[J].情報(bào)雜志，2006，25(10):57-62.

[3]YANG Yi-ming， LIU Xin. A re-examination of text categorization methods[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press，1999:42-49.

[4]陳濤，謝陽(yáng)群.文本分類中的特征降維方法綜述[J].情報(bào)學(xué)報(bào)，2005，24(6):690-695.

[5]黃冉.郭嵩山.基于類別空間模型的文本分類系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2005，22(8):60-63.

[6]劉海峰，王元元，王倩.基于分類的VSM模式下文本檢索若干問(wèn)題研究[J]. 情報(bào)科學(xué)，2006，24(11):1700-1703.

[7]寇莎莎，魏振軍.自動(dòng)文本分類中權(quán)值公式的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005，26(6):1616-1618.

[8]張琪玉.情報(bào)語(yǔ)言學(xué)基礎(chǔ)[M]. 武漢:武漢大學(xué)出版社，1997.

[9]劉海峰，王倩，王元元.基于Web的文本檢索位置加權(quán)模型研究[J]. 情報(bào)科學(xué)，2007，25（3）：451-455.

[10]侯漢清，章成志.Web概念挖掘中標(biāo)引源加權(quán)方案初探[J].情報(bào)學(xué)報(bào)，2005，24(1):87-92.

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