基于類別特征向量表示的中文文本分類算法

摘要:采用一種無須分詞的中文文本分類方法，以二元漢字串表示文本特征，與需要利用詞典分詞的分類模型相比，避免了分詞的復(fù)雜計(jì)算;為提高以bi－gram項(xiàng)表示文本特征的分類算法的準(zhǔn)確率，提出了基于類別特征向量表示的中文文本分類算法。通過實(shí)驗(yàn)結(jié)果及理論分析，驗(yàn)證了該算法的有效性。

關(guān)鍵詞:中文文本分類; 向量空間模型; 評價(jià)函數(shù); 特征提取

中圖分類號:TP301.6文獻(xiàn)標(biāo)志碼:A

文章編號:1001－3695(2008)02－0337－02

隨著網(wǎng)絡(luò)傳輸技術(shù)的迅速發(fā)展，互聯(lián)網(wǎng)上每天流動著海量的數(shù)據(jù)信息。如何處理和組織其中大量的文檔數(shù)據(jù)，從中快速準(zhǔn)確地獲取所需要的信息，成為一項(xiàng)重要而緊迫的研究課題。文本自動分類是其中的核心任務(wù)之一。

對英文文本分類而言，由于詞之間有空格分隔，可以直接以詞為單位生成文本特征，特征抽取比較簡單。對于中文文本，由于單詞之間沒有明顯的分隔符，如何生成文本特征是分類必須首先解決的問題。目前，生成中文文本特征主要有分詞和不分詞兩類方法。分詞的方法需要對文本進(jìn)行詞干抽取來表示文本特征，這種方法雖然得到的文本特征語義明確#65380;分類精確性高，但是分詞增加了算法復(fù)雜度;不分詞的方法通常使用N－gram項(xiàng)作為文本特征，其顯著特點(diǎn)在于算法簡單#65380;效率較高，但分類準(zhǔn)確率相對較低。在文獻(xiàn)[1]所做的比較實(shí)驗(yàn)中，同等分類條件下，采用詞典分詞生成文本特征項(xiàng)，分類準(zhǔn)確率達(dá)到92.73%，而用bi－gram方法分類準(zhǔn)確率僅為88.89%。

1中文文本分類的關(guān)鍵問題

1.1文本向量表示

目前，文本的表示主要采用向量空間模型(vector space model，VSM)。經(jīng)典的向量空間模型是Salton等人于20世紀(jì)60年代末提出的，并成功應(yīng)用于著名的SMART系統(tǒng)[2]，已成為最簡便高效的文本表示模型之一。它將文檔D看做由一組特征項(xiàng)(t1，t2，…，ti)和相應(yīng)的權(quán)重(w1，w2，…，wi)構(gòu)成，即用向量D=(t1，w1;t2，w2;…;tn，wn)表示文檔D，并且規(guī)定ti互不相同，向量D=(w1，w2，…，wn)被稱為文檔D的向量表示。這樣，將分類過程簡化為空間向量的運(yùn)算，使得問題復(fù)雜度大大降低。

1.2文本預(yù)處理及向量表示

首先要對文本進(jìn)行句子邊界識別，通常的方法是以標(biāo)點(diǎn)符號作為句子分界的標(biāo)志;其次是剔除文本中一些常見的功能詞，如“地”“的”“得”“而且”“雖然”等，此外往往還要剔除數(shù)字#65380;英文符號串等詞匯;最后以向量空間模型表示文本。

要將中文文本表示成向量形式，首先要對文本分詞，由這些詞作為向量的維來表示文本。為了避免詞典分詞過程中的復(fù)雜算法，采用bi－gram語法模型直接對文本進(jìn)行切分，由切分所得的二元漢字串構(gòu)成文本的特征項(xiàng)。下面是bi－gram切分示例。

例1一家瑞士的參展公司。

利用bi－gram模型切分后得到的二元漢字串有:

B一一家家瑞瑞士士的的參參展展公公司司E

其中:B和E分別表示句子的開始和結(jié)尾。這樣，文本在高維空間被表示。其中空間的每一維都表示文檔中的一個(gè)單詞，即特征項(xiàng)。特征項(xiàng)權(quán)值是指特征項(xiàng)ti代表文檔D的能力大小。這里的計(jì)算方法主要運(yùn)用TF－IDF思想。TF(term frequency)代表某詞在文檔中出現(xiàn)的頻度;DF(document frequency)代表某詞在多少個(gè)文檔中出現(xiàn)，出現(xiàn)得越多，越不重要。式(1)是一種普遍采用的 TF－IDF定義方法。

最終，經(jīng)過預(yù)處理后的文本被表示為以特征項(xiàng)權(quán)值表示的向量形式。

1.3評價(jià)函數(shù)及特征提取

文本的特征項(xiàng)數(shù)量往往是非常龐大的，通常達(dá)到上萬維。為此需要進(jìn)行維數(shù)壓縮工作，這樣做的目的主要有兩個(gè):為了提高程序效率和運(yùn)行速度;并非所有詞匯對文本分類都具有區(qū)分意義。一些通用的#65380;各個(gè)類別均普遍存在的詞匯對分類的貢獻(xiàn)非常小;在某特定類中出現(xiàn)比重大而在其他類中出現(xiàn)比重小的詞匯對分類的貢獻(xiàn)大。為了提高分類精度，對于每一類，應(yīng)去除那些表現(xiàn)力不強(qiáng)的詞匯，篩選出針對該類的特征項(xiàng)集合。所以，對于文本分類最重要的問題是特征評價(jià)函數(shù)的選擇。一般情況下，可以直接采用TF*IDF值作為評價(jià)函數(shù)，通過排序后提取特征項(xiàng)。這種算法結(jié)構(gòu)簡單#65380;復(fù)雜度低#65380;耗時(shí)少。

1.4分類算法

文本分類本質(zhì)上是一個(gè)映射過程，它將未標(biāo)明類別的文本映射到已有的類別中。用數(shù)學(xué)式表示為f ∶A→B。其中:A為待分類的文本集合;B為分類體系中的類別集合。

文本分類的映射規(guī)則是系統(tǒng)根據(jù)已經(jīng)掌握的每類若干樣本的數(shù)據(jù)信息，總結(jié)出分類的規(guī)律性而建立的，這就是訓(xùn)練過程;在遇到新文本時(shí)，根據(jù)總結(jié)出的判別規(guī)則確定文本相關(guān)的類別，即測試過程。

訓(xùn)練和測試過程是分類算法的核心部分。在訓(xùn)練過程中，由評價(jià)函數(shù)從文本特征的全集中抽取一個(gè)最優(yōu)的特征子集，由特征子集所表示的訓(xùn)練文本構(gòu)造分類器。在分類過程中，首先將測試文本用最優(yōu)特征子集表示，再經(jīng)分類器分類，得到測試文本所屬類別。目前存在多種基于向量空間模型的訓(xùn)練和測試算法。常見的有支持向量機(jī)算法#65380;K－近鄰方法和貝葉斯方法等。

2基于類別特征詞向量的分類算法

2.1評價(jià)函數(shù)

理論上講，按照式(2)計(jì)算出特征項(xiàng)在各類別中的權(quán)值。若在某一類別中權(quán)值越大，在其他類別中權(quán)值越小，則說明該特征項(xiàng)對該類別越有區(qū)分能力。但是，由于采用bi－gram方法切分文本會產(chǎn)生大量無意義的特征項(xiàng)，如果直接采用TF*IDF值作為評價(jià)函數(shù)，根據(jù)實(shí)驗(yàn)觀察，這些無意義特征項(xiàng)在整個(gè)訓(xùn)練集中通常僅出現(xiàn)一次。其在某一類別中權(quán)值為1.0，在其他類別中權(quán)值為0。然而這些詞卻并不能很好地代表類別特征。同時(shí)，一些在多個(gè)類別中都出現(xiàn)，而在某一類別中權(quán)值為0.75~1.0的特征項(xiàng)，往往能夠起到很好的類別區(qū)分作用，如表1所示。

表1為選取的部分在藝術(shù)類中權(quán)值較高的特征項(xiàng)。分析表1可以得出，“蹈團(tuán)，團(tuán)翩，翩躚”這些特征項(xiàng)雖然在藝術(shù)類中權(quán)值為1.0，但是不如“藝術(shù)，表演，舞蹈”這些類別權(quán)值較高而小于1.0的特征項(xiàng)更能起到類別區(qū)分作用。由此，本文并不以TF*IDF計(jì)算出的權(quán)值排序提取特征項(xiàng)。給出并采用如下的評價(jià)函數(shù)，以過濾無區(qū)分能力的特征項(xiàng):

tezheng(t，ci)=weight(t，ci)1>weight(t，ci)>0.75

0.5weight(t，ci)=1.0

0weight(t，ci)=其他

其中:weight(t，ci)為式(2)求得的權(quán)值。按照tezheng(t，ci)值排序后，選取前n維作為類別向量。

2.2算法描述

分類算法在構(gòu)造文檔特征向量時(shí)，首先選取訓(xùn)練集中全部bi－gram項(xiàng)作為特征詞集合構(gòu)成特征向量;然后根據(jù)式(2)分別計(jì)算各特征詞在各類別中的權(quán)值，得到特征詞相應(yīng)權(quán)值;最后按照評價(jià)函數(shù)排序后提取一定數(shù)量的特征詞表示各類別向量。將這種類別向量稱為類別特征詞向量;特征詞以相應(yīng)權(quán)值表示則稱為類別特征詞權(quán)向量。

本文采用基于類別特征詞向量的方法構(gòu)造分類器。在這種方法中，訓(xùn)練過程分別為每類建立起一個(gè)類別向量，對測試文本，通過計(jì)算新文本向量與各類別向量之間的距離來判斷它所屬的類別。分類算法模型如圖1所示。

1)訓(xùn)練過程對已標(biāo)注類別文本進(jìn)行訓(xùn)練，提取類別向量。

a)提取bi－gram項(xiàng)和文本向量化。對文本進(jìn)行邊界識別和功能詞剔除后，采用bi－gram切分文本，得到所有二元漢字串作為文本特征項(xiàng)，以特征向量形式表示文檔。

b)提取類別特征詞。計(jì)算特征項(xiàng)在各類別中的權(quán)值，按照評價(jià)函數(shù)排序后提取前n維得到各類別特征詞向量。

c)構(gòu)造類別特征詞權(quán)向量。以特征詞相應(yīng)權(quán)值為分量替代特征詞作為類別向量表示。

2)測試過程輸入未標(biāo)注類別文檔，進(jìn)行類別判別。

a)新文本預(yù)處理。與訓(xùn)練階段相同，提取bi－gram項(xiàng)。

b)文本特征向量表示。將新文本表示成以bi－gram項(xiàng)為分量的向量，與訓(xùn)練階段得到的各類別特征詞向量進(jìn)行比較。若分量匹配，以類別特征詞相應(yīng)權(quán)值替換對應(yīng)新文本向量分量;若無匹配，以0替換。構(gòu)成新文本向量后，如維數(shù)大于n，按權(quán)值排序后取前n維;若維數(shù)小于n，設(shè)分量為0.001補(bǔ)足n維。

c)分類結(jié)果輸出。計(jì)算新文本特征向量與各類別向量間的相似度，將新文本分類到相似度值最大的類別中。相似度計(jì)算采用向量夾角余弦計(jì)算式[3]。

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

為驗(yàn)證本文提出的分類算法的有效性，選用復(fù)旦大學(xué)提供的語料中的1 860篇中文文本共6個(gè)類別作為實(shí)驗(yàn)數(shù)據(jù)。其中1 457篇已知類別文本作為訓(xùn)練數(shù)據(jù)，對403篇未分類文本進(jìn)行了算法測試，編程環(huán)境是Java 2。進(jìn)行分類前，對文本進(jìn)行了預(yù)處理，包括句子邊界的識別#65380;去除功能詞等。表2給出了實(shí)驗(yàn)具體情況的語料數(shù)據(jù);表3給出了算法的分類實(shí)驗(yàn)結(jié)果。

從表3可以看出，盡管本文使用的是以bi－gram項(xiàng)作為文本特征，并沒有采用精確更高的分詞算法，但是在分類效果上仍然取得了較高的準(zhǔn)確率。圖2給出了在特征向量維數(shù)n取值不同時(shí)，對分類準(zhǔn)確率的影響，并與以TF*IDF值直接排序提取特征項(xiàng)的分類算法結(jié)果進(jìn)行了對比。

圖2中，實(shí)線代表以本文提出評價(jià)函數(shù)提取特征項(xiàng)的算法實(shí)驗(yàn)結(jié)果;虛線代表以TF*IDF值提取特征項(xiàng)的算法實(shí)驗(yàn)結(jié)果。從圖2中可以看出，按照本文提出的算法得到的實(shí)驗(yàn)結(jié)果明顯優(yōu)于TF*IDF算法所得到的結(jié)果。

4結(jié)束語

傳統(tǒng)的中文文本分類算法在對待分類文本向量化時(shí)，首先要對文本進(jìn)行中文分詞。本文采用以bi－gram項(xiàng)表示特征，不需要分詞程序進(jìn)行中文分詞，降低了算法復(fù)雜度，提高了分類速度。但是采用bi－gram項(xiàng)表示特征的文本分類，往往效果并不理想，為此本文提出一種基于類別特征詞向量的分類算法，在未對文本分詞的情況下仍然具有較高的準(zhǔn)確率。通過在現(xiàn)實(shí)語料上進(jìn)行對比實(shí)驗(yàn)以及理論分析，驗(yàn)證了該算法的可行性和有效性。

參考文獻(xiàn):

[1]李榮陸，王建會，陳曉云，等.使用最大熵模型進(jìn)行中文文本分類[J].計(jì)算機(jī)研究與發(fā)展，2005，42(1):94－101.

[2]SALTON G， McGILL M J. Introdocution to modern information retrieval[M].New York:McGraw－Hill， 1983.

[3]龐建鋒，卜東坡，白碩.基于向量空間模型的文本自動分類系統(tǒng)的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2001，18(9):23－26.

[4]YANG Yi－ming. An evaluation of statistical approaches to text categorization[J]. Journal of Information Retrieval， 1999，1(1/2):67－88.

[5]LEWIS D D， RINGUETTE M. A comparison of two learning algorithms of text categorization[C]//Proc of the 3rd Annual Symposium on Document Analysis and Information Retrieval. Las Vegas:[s.n.]， 1994:81－93.

[6]CAVNAR W B， TRENKLE J M. N－gram－based text categorization[C]//Proc of the 3rd Annual Symposium on Document Analysis and Information Retrieval. Las Vegas:[s.n.]， 1994:161－176.

[7]MANNING C D， SCHTZE H. Foundations of statistical natural language processing[M].中文簡體版.北京:電子工業(yè)出版社，2002:355－375.

[8]王映，常毅，譚建龍，等.基于N元漢字串模型的文本表示和實(shí)時(shí)分類的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(5):88－91.

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