張小川，于旭庭，張宜浩

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 重慶 400054)

一種改進(jìn)的向量空間模型的文本表示算法

張小川，于旭庭，張宜浩

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 重慶 400054)

文本表示是將可閱讀的文字轉(zhuǎn)換成計(jì)算機(jī)可識(shí)別的數(shù)據(jù)結(jié)構(gòu)的過(guò)程，是文本信息處理領(lǐng)域中關(guān)注的基礎(chǔ)性問(wèn)題。針對(duì)向量空間模型中文本表示的tf-idf算法僅考慮了詞項(xiàng)特征與文檔之間的關(guān)系，沒(méi)有考慮與類別關(guān)聯(lián)性的問(wèn)題，引入數(shù)理統(tǒng)計(jì)卡方分布方法，以此改進(jìn)了tf-idf算法，構(gòu)成為新算法tf-idf-cθ。該算法將詞項(xiàng)的卡方分布值c作為文本表示的一個(gè)因子，用該c值來(lái)衡量詞項(xiàng)在文本類中分布的差異，并且引入詞性因子θ，得到改進(jìn)向量空間模型的表示文本。對(duì)改進(jìn)前后的2個(gè)算法進(jìn)行文本分類實(shí)驗(yàn)，結(jié)果表明:改進(jìn)后的算法得到了提升，部分解決了詞項(xiàng)特征與類別的關(guān)聯(lián)性。

文本表示；向量空間模型；卡方分布；tf-idf

近年來(lái)互聯(lián)網(wǎng)時(shí)代方興未艾，國(guó)家也開(kāi)始大力發(fā)展“互聯(lián)網(wǎng)+”，網(wǎng)上信息越來(lái)越豐富，其中許多都是文本信息。如何有效處理這些信息是文本挖掘、信息檢索等領(lǐng)域的研究熱點(diǎn)。

目前，大部分學(xué)者更關(guān)注此領(lǐng)域中的具體問(wèn)題，例如文本分類、信息檢索、自動(dòng)摘要生成、推薦用戶新聞、問(wèn)答系統(tǒng)等算法的提出和改進(jìn)。但是，文本表示同樣也是文本信息檢索過(guò)程中不容忽視的關(guān)鍵。文本表示是將可閱讀的文字轉(zhuǎn)換成計(jì)算機(jī)可識(shí)別的數(shù)據(jù)結(jié)構(gòu)的過(guò)程，是文本信息處理領(lǐng)域中的基礎(chǔ)性問(wèn)題。

當(dāng)前文本表示模型主要有布爾模型(Boolean model)、概率模型(probabilistic model)和向量空間模型(vector space model)[1]。文獻(xiàn)[2]第1次提出自動(dòng)文本檢索和信息檢索的概念。文獻(xiàn)[3]提出的向量空間模型是信息檢索領(lǐng)域最為經(jīng)典的分析模型之一。在該模型中，文檔以向量的形式表示，實(shí)現(xiàn)自然語(yǔ)言在文本分類、相似度計(jì)算、模式識(shí)別等各個(gè)具體領(lǐng)域中的可計(jì)算性。因此，基于向量空間模型的文檔表示算法是進(jìn)行任何自然語(yǔ)言處理的基礎(chǔ)和前提[4]。

針對(duì)向量空間模型中詞項(xiàng)權(quán)重的經(jīng)典計(jì)算算法tf-idf(term frequency-inverse document frequency)未考慮詞項(xiàng)在類間分布情況的不足，提出一種改進(jìn)算法tf-idf-cθ，對(duì)改進(jìn)模型生成的相似度矩陣進(jìn)行分類驗(yàn)算，結(jié)果表明:tf-idf-cθ算法具有一定的可行性和有效性。

1 向量空間模型的構(gòu)造

1.1 向量空間模型的基本概念

向量空間模型(VSM)是將文檔表示成n個(gè)無(wú)序特征詞項(xiàng)對(duì)應(yīng)權(quán)值組成的向量空間，以此把文本處理轉(zhuǎn)化為向量運(yùn)算[5]。

該模型的基本概念如下：

1) 文檔(document)：文本或文本中的段落、句子集合。

2) 詞項(xiàng)(term)：通過(guò)若干個(gè)基本語(yǔ)言單位(字、詞、短語(yǔ)等)表示文檔內(nèi)容，這些語(yǔ)言單位稱為詞項(xiàng)。

3) 權(quán)重(term weight)：表示每個(gè)詞項(xiàng)在文檔中重要程度。

1.2 向量空間模型的步驟

文檔生成向量空間模型通常包括5個(gè)步驟。

第1步 分詞 因?yàn)橹形臎](méi)有明顯的切分標(biāo)志，采用相應(yīng)的分詞算法[6]將文檔分解，生成由詞項(xiàng)組成的集合。

第2步 去停用詞 根據(jù)停用詞表，過(guò)濾在文本中頻繁出現(xiàn)，但又無(wú)法表示特征的詞項(xiàng)，譬如“的”、“了”、“您好”等。

第3步 特征詞項(xiàng)選擇 從原始的詞項(xiàng)集合中選擇1個(gè)含有顯著類別信息的特征詞項(xiàng)子集[7]。

第4步 計(jì)算權(quán)重 對(duì)特征詞項(xiàng)進(jìn)行賦值：

(1)

其中:wij表示特征詞項(xiàng)j在文檔i中的權(quán)重值;n為特征詞項(xiàng)總個(gè)數(shù);N為文檔總個(gè)數(shù)。

第5步 歸一化 將特征向量標(biāo)準(zhǔn)化為單位向量：

(2)

第5步的歸一化是通過(guò)標(biāo)準(zhǔn)化各個(gè)分量，消除文檔長(zhǎng)度對(duì)文本表示的可能影響。

由圖1可知，改進(jìn)步驟4中的計(jì)算權(quán)重算法可使表示文本的向量空間模型更準(zhǔn)確。

在產(chǎn)生向量空間模型的過(guò)程中，常見(jiàn)的有詞頻權(quán)值計(jì)算、布爾權(quán)值計(jì)算、tf-idf權(quán)值計(jì)算,其中tf-idf算法應(yīng)用最廣泛。tf(term frequency)是詞項(xiàng)頻率，表示該詞項(xiàng)在文檔中出現(xiàn)的頻率；idf(inverse document frequency)是倒置文檔頻率，反映該詞項(xiàng)在文檔數(shù)據(jù)集中的重要程度[8]。具體公式如下：

(3)

(4)

(5)

圖1 向量空間模型的產(chǎn)生步驟Fig.1 Produce steps of VSM

結(jié)合式(2)～(5)得出tf-idf計(jì)算權(quán)重的公式：

(6)

雖然tf-idf算法得到廣泛的應(yīng)用，但也存在較明顯的缺點(diǎn)[9]：它把整個(gè)文檔語(yǔ)料庫(kù)作為衡量目標(biāo)，沒(méi)有考慮詞項(xiàng)與類別的關(guān)聯(lián)性，即詞項(xiàng)在類間的分布情況[10]。文獻(xiàn)[11]從詞項(xiàng)權(quán)重和特征向量旋轉(zhuǎn)的角度說(shuō)明了反文檔頻率的值不能很好地反映詞項(xiàng)的重要程度。文獻(xiàn)[12]提出一種改進(jìn)的文本實(shí)時(shí)分類模型，該方法通過(guò)特征聚合和增量訓(xùn)練算法，改進(jìn)了VSM的特征提取策略，進(jìn)一步對(duì)特征詞進(jìn)行加權(quán)處理，可更好地劃分類別界限。文獻(xiàn)[13]提出一種WAKNN加權(quán)方法，該方法通過(guò)逐一嘗試權(quán)值，達(dá)到給每個(gè)特征詞加權(quán)的目的，但是該方法增加了計(jì)算代價(jià)。

本文引入卡方分布值c獲得最大限度區(qū)分不同文檔的能力，并且融入詞性因子θ到權(quán)值計(jì)算中。

2 改進(jìn)文本表示算法——tf-idf-cθ函數(shù)

如以上所述，tf-idf函數(shù)僅考慮了特征與文檔之間的關(guān)系，沒(méi)有反映特征與類別的關(guān)聯(lián)性。本文首先引入卡方分布，彌補(bǔ)tf-idf算法的不足。實(shí)際上通過(guò)卡方分布值能夠反映出詞項(xiàng)在文本分類中的重要程度，進(jìn)行量化后，定義為因子c，見(jiàn)式(7)，即將因子c引入式(6)。

(7)

其中：A表示Ci類包含t詞項(xiàng)的文檔數(shù)量；B表示非Ci類包含t詞項(xiàng)的文檔數(shù)量；C表示Ci類不包含t詞項(xiàng)的文檔數(shù)量；D表示非Ci類不包含t詞項(xiàng)的文檔數(shù)量；N表示文檔的總數(shù)量。c的值越大，說(shuō)明詞項(xiàng)和類之間的關(guān)聯(lián)度越大。

利用因子c改進(jìn)式(6)：

wik=tf*idf*c=

(8)

此外，本文引入詞性系數(shù)因子θ來(lái)量化不同詞性對(duì)于文本的重要程度。改進(jìn)式(8)得到式(9)。θ定義如下：

其中0≤ω≤β≤α≤1。根據(jù)經(jīng)驗(yàn)，設(shè)置名詞的詞性因子最大，動(dòng)詞、形容詞、副詞其次，其他最小。

改進(jìn)的tf-idf-cθ函數(shù)如下：

(9)

式中：N表示文檔的總數(shù)量；nk表示包含詞項(xiàng)k的文檔數(shù)量；ck表示詞項(xiàng)k對(duì)應(yīng)的卡方值；θk表示詞項(xiàng)k對(duì)應(yīng)的詞性因子。另外，將tfik改進(jìn)為(log(tfik)+1)是因?yàn)橐延袑?shí)驗(yàn)表明，對(duì)詞項(xiàng)頻率tf取對(duì)數(shù)，會(huì)比直接使用更有效。并且為保證頻率為1的詞項(xiàng)具有非0權(quán)值，因此詞項(xiàng)頻率修正為log(tfik)+1。

式(9)的tf-idf-cθ算法內(nèi)涵是融合詞項(xiàng)k在文檔和類中的比例分布情況，當(dāng)c值很大時(shí)，k值就大。這也意味著詞項(xiàng)k的權(quán)值與c值的類別特征成正比，說(shuō)明詞項(xiàng)k描述類的能力越大，文本類區(qū)分權(quán)值就越大。同理，詞性因子θ也一樣。

當(dāng)通過(guò)tf-idf-cθ函數(shù)計(jì)算權(quán)值時(shí)，在原先只是將詞項(xiàng)頻率和逆文檔頻率相乘的基礎(chǔ)上，還考慮到了詞項(xiàng)在類中的分布比例問(wèn)題，并且引入詞性因素。tf-idf-cθ算法綜合考慮這些影響因素，不增加其他的計(jì)算和分析難度，有很強(qiáng)的實(shí)用性。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集的選擇

由于常用的語(yǔ)料庫(kù)某些文章的篇幅較長(zhǎng)，因此本文以復(fù)旦大學(xué)日月光華BBS站精華區(qū)文章為短文本實(shí)驗(yàn)數(shù)據(jù)源，選取表1中的7個(gè)大類進(jìn)行實(shí)驗(yàn)。

表1 實(shí)驗(yàn)數(shù)據(jù)集分布Table 1 Distribution of experimental data set

針對(duì)表1的7個(gè)類別，每個(gè)類別隨機(jī)選擇800篇文本，共5 600篇文本進(jìn)行實(shí)驗(yàn)。

3.2 評(píng)價(jià)指標(biāo)的設(shè)置

實(shí)驗(yàn)采用準(zhǔn)確率(precision)和召回率(recall)為實(shí)驗(yàn)對(duì)比指標(biāo)，其中準(zhǔn)確率考察分類的精確度，而召回率考察分類的完整性[14]。兩者定義見(jiàn)式(10)、(11)。

(10)

(11)

其中:n(i,j)表示在分類結(jié)果j中包含預(yù)定義類別i的文本個(gè)數(shù)；nj表示分類結(jié)果j中文本的個(gè)數(shù)；ni表示預(yù)定義類別i中文本的個(gè)數(shù)。

3.3 實(shí)驗(yàn)結(jié)果的分析

為了驗(yàn)證式(9)tf-idf-cθ算法改進(jìn)的有效性，設(shè)計(jì)兩組對(duì)比實(shí)驗(yàn)：

第1組實(shí)驗(yàn)，將tf-idf-cθ算法同傳統(tǒng)tf-idf算法、未考慮詞性因子的tf-idf-c算法進(jìn)行文本分類比較，以觀察卡方分布值c和詞性因子θ對(duì)分類結(jié)果的影響。

第2組實(shí)驗(yàn)，通過(guò)測(cè)試3組詞性因子的值，觀察采用tf-idf-cθ的分類效果，得到最佳詞性因子取值組合。

同時(shí)為保證實(shí)驗(yàn)的公平性，兩組實(shí)驗(yàn)都采用相同的KNN分類算法。

表2為tf-idf算法分別加入因子c(式(8))和因子c、θ(式(9))進(jìn)行實(shí)驗(yàn)的結(jié)果。表2是采用3種不同算法得到的文本分類結(jié)果對(duì)比。其中詞性因子θ取值分別為：α= 0.5，β=0.3，ω=0.2。

表2 3種算法準(zhǔn)確率和召回率比較情況

%

Table 2 Accuracy and recall rate of 3 algorithms

文本類別tf-idf算法PRtf-idf-c算法PRtf-idf-cθ算法PR交通31.241.135.750.239.152.4計(jì)算機(jī)55.340.256.143.657.346.3環(huán)境43.133.952.338.652.643.6經(jīng)濟(jì)33.343.539.646.441.249.4教育47.630.247.835.149.839.1藝術(shù)32.226.333.639.734.342.0體育40.038.747.241.551.845.7平均值40.436.244.642.146.645.5

從表2中可以看出:tf-idf算法的準(zhǔn)確率和召回率最低，改進(jìn)的tf-idf-c算法在文本分類結(jié)果的準(zhǔn)確率和召回率兩個(gè)方面均有3%～6%的提升，而考慮了詞性因子的tf-idf-cθ算法，準(zhǔn)確率進(jìn)一步提高，召回率也有一定的提高。利用柱形圖圖2、圖3能進(jìn)一步直觀地反映準(zhǔn)確率和召回率的對(duì)比情況。

圖2 3種算法的準(zhǔn)確率比較Fig.2 Accuracy rate cmparison of 3 algorithms

圖3 3種算法的召回率比較Fig.3 Recall rate comparison of 3 algorithms

從圖2、圖3可以看出:tf-idf-cθ算法對(duì)于個(gè)別類的召回率改進(jìn)效果比較明顯，但在對(duì)不同類別分類結(jié)果的準(zhǔn)確率和召回率提高效果不同，說(shuō)明tf-idf-cθ算法在文本內(nèi)容分類方面有一定程度的改善。

圖 4是第2組的實(shí)驗(yàn)結(jié)果，展示了不同詞性因子取值組合對(duì)文本分類結(jié)果的影響。

從圖4可以看出：當(dāng)組合為α= 0.5，β=0.3，ω=0.2時(shí)，文本分類的平均準(zhǔn)確率最高，這也是針對(duì)第1組實(shí)驗(yàn)采用該詞性因子取值組合的原因。

圖4 不同詞性因子組合的分類結(jié)果比較Fig.4 The classification results comparison of different factor combination

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

為了解決tf-idf算法對(duì)詞項(xiàng)在類間分布情況的不足問(wèn)題，引入卡方分布方法，融合考慮了詞項(xiàng)在類中的分布比例和詞性因素，提出了改進(jìn)的算法tf-idf-cθ。實(shí)驗(yàn)結(jié)果表明：文本表示算法效果得到提升。盡管改進(jìn)后的文本表示算法有較好效果，但針對(duì)整個(gè)文本分類問(wèn)題仍存在進(jìn)一步的提升空間，比如可結(jié)合具體處理文本領(lǐng)域中的相似度計(jì)算等方法，這也是后續(xù)的研究方向。

[1] 徐濤，于洪志，加羊吉.基于改進(jìn)卡方分布量的藏文文本表示算法[J].計(jì)算機(jī)工程，2014，40(6)：185-189.XU Tao,YU Hongzhi,JIA Yangji.Tibetan Document Representation Method Based on ImprovedChi-squared Statistic[J].Computer Enginnering,2014,40(6):185-189.[2] LEONG M K,ZHOU H.Preliminary Qualitative Analysis of Segmented vs Bigram Indexing in Chinese：Trec,1997[C]//Gaithersburg,Maryland.1997：551-557.

[3] SALTON G,WONG A,YANG C S.A Vector Space Model for Automatic Indexing[J].Communications of the ACM,1975,18(11)：613-620.

[4] SUN Shuang,HE Liang,YANG Jing,et al.An Improved Algorithm for Weighting Keywords in Web Documents[J].Journal of Shanghai University(English Edition),2008,12(3)：235-239.

[5] MICHAEL W.Berry,Murry Brovme,Understanding Search Engines Mathematical Modeling and Text Retrieval[D].USA：University of Tennessee,1995：31-39.

[6] 宋庭勇.基于語(yǔ)義的中文短文本模糊譜分類[D].上海：華東師范大學(xué)，2015.

SONG Tingyong.The Short Text Fuzzy Spectral Clustering Based on Semantic[D].Shanghai: East China Normal University,2015.

[7] 平源.基于支持向量機(jī)的分類及文本分類研究[D].北京：北京郵電大學(xué)，2012.

PING Yuan.Rearch on Clustering and Text Categorization Based on Support Verctor Machine[D].Beijing: Beijing University of Posts Telecommunications,2012.

[8] ROBERTSON S.Understanding inverse document frequency：on theoretical arguments for IDF[J].Journal of documentation,2004,60(5)：503-520.

[9] 張蕓.基于BTM主題模型特征擴(kuò)展的短文本相似度計(jì)算[D].合肥：安徽大學(xué)，2014.

ZHANG Yun.A Short Text Similarity Calculation Method Based on Feature Extension using BTM Topic Model[D].Hefei: Anhui University,2014.

[10]羅成飛.結(jié)合卡方分布與特征分類的文本特征降維方法[D].廣州：華南理工大學(xué)，2015.

LUO Chengfei.Based on CHI and feature clustering text feature reduction[D].Guangzhou:South China University of Technology,2015.

[11]雷軍程，黃同成，柳小文.一種基于權(quán)重的文本特征選擇算法[J].計(jì)算機(jī)科學(xué)，2012，39(7)：250-275.

LEI Juncheng,HUANG Tongcheng,LIU Xiaowen.Improved Text Feature Selection Method Based on Text Feature Weight[J].Computer Science,2012,39(7):250-275.

[12]張曉輝，李瑩，常桂然，等.適于Internet新聞文本實(shí)時(shí)分類的動(dòng)態(tài)向量空間模型DVSM[J].計(jì)算機(jī)科學(xué)，2004，31(6)：64-67.

ZHANG Xiaohui,LI Ying,CHANG Guiran,et al.A Dynamic Vector Space Model for Internet News Textual Categorization[J].Computer Science,2004,31(6):64-67.

[13]HAN E H,GEORGE K.VIPIN K.Text categorization using weight adjusted k-nearest neighbor classification[R].Minnesota：Computer Science Department,2000.

[14]王有華，陳笑蓉.基于Kolmogorov復(fù)雜性的文本分類算法改進(jìn)[J].計(jì)算機(jī)科學(xué)，2016，43(5)：243-246.

WANG Youhua,CHEN Xiaorong.Improved Text Clustering Algorithm Based on Kolmogorov Complexity[J].Computer Science,2016,43(5):243-246.

(責(zé)任編輯 楊黎麗)

Text Representation Based on Improved Vector Space Model

ZHANG Xiao-chuan，YU Xu-ting，ZHANG Yi-hao

(College of Computer Science and Engineering, Chongqing University of Technology,Chongqing 400054, China)

Text representation transfers the readable text into computer-identifiable data structure, and it is a fundamental problem in text information processing field. As a text representation approach in Vector Space Model(VSM), tf-idf algorithm just considers the relevancy between term feature and document, but class. In order to solve this problem, the paper introduce the Chi-square concept of mathematical statistics, and propose a text representation algorithm——tf-idf-cθ.And the algorithm takes the termcvalue as a factor of a text representation, andcvalue measures the term distribution difference in classes, and also considers the term characteristic asθvalue to produce the corresponding text representation based on the improved VSM. Last, it classifies short text using two algorithms above, and the experiment results show that the modified method is more effective, and partly solve the relevancy between term feature and class.

text representation; VSM; CHI; tf-idf

2016-10-12

國(guó)家自然科學(xué)基金資助項(xiàng)目(61502064)；重慶市“121”科技支撐示范工程項(xiàng)目(cstc2014fazktjcsf40009)

張小川(1965—),男,教授,主要從事人工智能、計(jì)算機(jī)軟件研究，E-mail:zxc@cqut.edu.cn；于旭庭(1990—),女,碩士研究生,主要從事人工智能、計(jì)算機(jī)軟件研究，E-mail:1527593026@qq.com。

張小川，于旭庭，張宜浩.一種改進(jìn)的向量空間模型的文本表示算法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，2017(1):87-92.

format：ZHANG Xiao-chuan，YU Xu-ting，ZHANG Yi-hao.Text Representation Based on Improved Vector Space Model[J].Journal of Chongqing University of Technology(Natural Science)，2017(1):87-92.

10.3969/j.issn.1674-8425(z).2017.01.014

TP391

A

1674-8425(2017)01-0087-06