基于改進(jìn)TFIDF算法的文本分類(lèi)研究

鄭 霖，徐德華

(同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092)

0 引言

隨著信息技術(shù)與互聯(lián)網(wǎng)的迅速發(fā)展，用戶(hù)通過(guò)網(wǎng)絡(luò)獲取的信息量增長(zhǎng)迅速，而龐大的網(wǎng)絡(luò)數(shù)據(jù)資源中，絕大多數(shù)的數(shù)據(jù)仍是文本數(shù)據(jù)。如何讓用戶(hù)在海量數(shù)據(jù)中，快速找到自己所感興趣的數(shù)據(jù)，成為了一個(gè)亟待解決的問(wèn)題。文本分類(lèi)作為信息處理的重要研究方向，是處理大量文本數(shù)據(jù)的有效途徑。通過(guò)對(duì)文本數(shù)據(jù)進(jìn)行分類(lèi)，將相似文本集中在一起進(jìn)行管理，可以提高用戶(hù)檢索的效率，快速找到其感興趣的類(lèi)別文本。

文本分類(lèi)(Text Classification)是在給定的分類(lèi)模型下，根據(jù)文本內(nèi)容判斷文本所屬類(lèi)別的過(guò)程。通常情況下，文本不僅包括網(wǎng)頁(yè)、郵件，還包括短信、微博和論壇帖子等。在文本分類(lèi)的過(guò)程中，核心的部分就是將文本表示成向量空間模型［1］(VSM:Vector Space Model)。在建立文本空間向量模型的過(guò)程中，首先是對(duì)文本進(jìn)行分詞，將文本表示成向量形式，但是這樣產(chǎn)生的向量維數(shù)巨大，產(chǎn)生“維度災(zāi)難”。因此，在文本分詞結(jié)束后，首先進(jìn)行特征選擇和權(quán)重的計(jì)算，降低文本向量的維數(shù)，形成一個(gè)低維的空間向量。

在建立空間向量模型的過(guò)程中，權(quán)重的表示尤為重要，常用的有布爾權(quán)重、詞頻權(quán)重和TFIDF權(quán)重等，特征項(xiàng)的權(quán)重表示在很大程度上會(huì)影響文本分類(lèi)的準(zhǔn)確性。在權(quán)重的眾多表示方法中，TFIDF權(quán)重表示因?yàn)橄鄬?duì)簡(jiǎn)單，有較高的準(zhǔn)確率和召回率，一直是一種使用最廣泛的權(quán)重表示方法。

為了進(jìn)一步提升文本分類(lèi)的效果，本文分析了傳統(tǒng)文本分類(lèi)權(quán)重計(jì)算方法的優(yōu)點(diǎn)和不足，并對(duì)經(jīng)典的TFIDF算法做了改進(jìn)，最后將改進(jìn)的算法用在實(shí)驗(yàn)文本的分類(lèi)上，取得了分類(lèi)效果上的提升，證明了改進(jìn)策略的可行性。

1 文本分類(lèi)國(guó)內(nèi)外發(fā)展現(xiàn)狀

文本分類(lèi)研究始于自動(dòng)分類(lèi)研究，20世紀(jì)50年代，H.P.Luhn在這一領(lǐng)域進(jìn)行了開(kāi)創(chuàng)性研究，他提出詞頻統(tǒng)計(jì)思想主要用于自動(dòng)分類(lèi)［2］。1960年，Maron發(fā)表了關(guān)于自動(dòng)分類(lèi)算法的論文，隨后，以Kspark、G.Salton以及 K.S.Jones等人為代表的眾多學(xué)者在這一領(lǐng)域進(jìn)行了卓有成效的研究工作［3］。國(guó)外當(dāng)前流行的基于統(tǒng)計(jì)的分類(lèi)方法有 Na?ve Bayes［4］、KNN［5］和支持向量機(jī)［6］等。國(guó)外的文本分類(lèi)研究工作已經(jīng)從基礎(chǔ)實(shí)驗(yàn)性研究轉(zhuǎn)入實(shí)用階段。

國(guó)內(nèi)在文本分類(lèi)方面的研究比國(guó)外起步晚，但是也取得了巨大的進(jìn)步。國(guó)內(nèi)在中文文本分類(lèi)方面的研究始于上個(gè)世紀(jì)的80年代，歷經(jīng)了4個(gè)主要過(guò)程:學(xué)習(xí)和借鑒國(guó)外的研究成果;構(gòu)建中文語(yǔ)料庫(kù);創(chuàng)建開(kāi)放的中文文本分類(lèi)實(shí)驗(yàn)平臺(tái);自主研發(fā)具體的應(yīng)用系統(tǒng)等［7］。隨著中文自然語(yǔ)言理解技術(shù)特別是中文自動(dòng)分詞和詞性標(biāo)注技術(shù)的日漸成熟，中文文本分類(lèi)技術(shù)的研究發(fā)展很快，已經(jīng)逐步從可行性探索向?qū)嵱没_(kāi)始轉(zhuǎn)變［8］，例如百度等搜索引擎?？傮w來(lái)說(shuō)，中文文本分類(lèi)還處于不斷的發(fā)展之中，正確分類(lèi)率約為60%～90%，已經(jīng)向商業(yè)化的軟件應(yīng)用靠攏，并且已經(jīng)嘗試開(kāi)發(fā)了一批自動(dòng)分類(lèi)系統(tǒng)［9］。

在文本分類(lèi)的過(guò)程中，非常重要的部分就是分詞后詞條的權(quán)重表示。常用的權(quán)重表示方法有布爾權(quán)重、詞頻權(quán)重和TFIDF權(quán)重等。

1)布爾(Boolean)權(quán)重:在計(jì)算詞條權(quán)重時(shí)，根據(jù)詞條是否在文本中出現(xiàn)來(lái)決定，詞條在文檔中至少出現(xiàn)過(guò)一次，權(quán)重為1，否則為0。該方法形式簡(jiǎn)潔，容易實(shí)現(xiàn)，但是不能很好地體現(xiàn)詞條在文檔中出現(xiàn)的次數(shù)。

2)詞頻(Term Frequency，TF)權(quán)重:在計(jì)算時(shí)將詞條在文檔中出現(xiàn)的次數(shù)作為權(quán)重值。該方法實(shí)現(xiàn)方便，但是容易受到文本長(zhǎng)度的影響，在一定程度上影響了分類(lèi)的效果。

3)TFIDF權(quán)重。

Salton在1973年提出了TFIDF(Term Frequency＆ Inverse Documentation Frequency)算法［10］。該算法綜合考慮了詞條的詞頻TF以及逆文檔率IDF，其主要思想是:如果一個(gè)詞條在特定的文本中出現(xiàn)的頻率越高，說(shuō)明它在區(qū)分該文本內(nèi)容屬性方面的能力越強(qiáng);如果一個(gè)詞條在文本中出現(xiàn)的范圍越廣，即每個(gè)類(lèi)別中出現(xiàn)次數(shù)相當(dāng)，說(shuō)明該詞條區(qū)分文本內(nèi)容的能力越弱。其經(jīng)典計(jì)算公式為:

其中，tfij是指詞條tj在文檔di中出現(xiàn)的次數(shù)，idfj是指出現(xiàn)詞條tj的反文檔數(shù)，N表示總文檔數(shù)，nj是指出現(xiàn)詞條tj的文檔數(shù)。

從TFIDF的經(jīng)典公式可以看出，tfij越大，即詞條tj在特征文本中出現(xiàn)的次數(shù)越多，權(quán)重wij越大，區(qū)分該文本的能力越強(qiáng);nj越大，即詞條tj在語(yǔ)料集中出現(xiàn)的文檔數(shù)越多，權(quán)重wij越小，區(qū)分該文本的能力越弱。實(shí)際上，如果詞條tj在某一個(gè)類(lèi)的文檔中頻繁出現(xiàn)，則說(shuō)明該詞條能夠很好代表這個(gè)類(lèi)的文本的特征，這樣的詞條應(yīng)該給它們賦予較高的權(quán)重，但是詞條tj在某一個(gè)類(lèi)的文檔中頻繁出現(xiàn)，會(huì)使nj增大，從而導(dǎo)致wij減少，這就是傳統(tǒng)TFIDF算法的問(wèn)題所在。它將文檔集作為整體來(lái)考慮，其中IDF的計(jì)算并沒(méi)有考慮到特征項(xiàng)在類(lèi)間的分布情況，導(dǎo)致在類(lèi)別之間分布均勻?qū)︻?lèi)別區(qū)分度不大的特征項(xiàng)賦予了很高的權(quán)值，而且IDF的計(jì)算也沒(méi)有考慮到特征項(xiàng)在類(lèi)內(nèi)的分布情況，導(dǎo)致在一個(gè)類(lèi)別內(nèi)部只集中在某幾個(gè)文本的特征項(xiàng)賦予了很高的權(quán)值。

2 改進(jìn)的TFIDF算法

針對(duì)傳統(tǒng)算法的上述不足，很多研究者都進(jìn)行了算法的改進(jìn)。張保富(2011年)等［11］提出了一種結(jié)合詞條在類(lèi)間和類(lèi)內(nèi)的信息分布熵來(lái)調(diào)整TFIDF計(jì)算的方法，改善了文本分類(lèi)的效果。張建娥(2012年)［12］通過(guò)詞語(yǔ)關(guān)聯(lián)度修正了TFIDF算法的誤差，使算法的平均召回率有了一定提升。李學(xué)明(2012年)等［13］在前人的基礎(chǔ)上，提出了一種基于信息增益與信息熵的TFIDF算法(TFIDFIGE)，對(duì)于文本集合內(nèi)部的詞條分布通過(guò)信息熵來(lái)對(duì)詞條的權(quán)重進(jìn)行調(diào)整。這2種算法雖然在一定程度上克服了傳統(tǒng)算法的缺點(diǎn)，但是大大增加了算法的復(fù)雜度。張玉芳(2006年)等［16］將IDF的計(jì)算改為IDF=log(×N)(m為類(lèi)C內(nèi)包含詞條t的文檔數(shù)，k為除類(lèi)C外包含詞條t的文檔數(shù))，這樣就考慮到了詞條t在類(lèi)間與類(lèi)內(nèi)的分布，也在一定程度上克服了傳統(tǒng)算法的不足，但是用類(lèi)C內(nèi)包含詞條t的文檔數(shù)m和類(lèi)C外包含詞條t的文檔數(shù)k直接計(jì)算，可能會(huì)由于類(lèi)C外的文檔數(shù)比類(lèi)C的文檔數(shù)多，而使k值較大，從而削弱了m的影響。

基于此，本文提出一種新的TFIDF改進(jìn)算法。新算法的核心思想是用類(lèi)C內(nèi)包含詞條t的文檔占比和類(lèi)C外包含t的文檔占比來(lái)衡量詞條t在類(lèi)間和類(lèi)內(nèi)的分布，修改了IDF的計(jì)算方法:

其中，m為類(lèi)C內(nèi)包含詞條t的文檔數(shù)，j為類(lèi)C內(nèi)不包含詞條t的文檔數(shù)，k為非類(lèi)C內(nèi)包含詞條t的文檔數(shù)，i為非類(lèi)C內(nèi)不包含詞條t的文檔數(shù)。

1)驗(yàn)證1:詞條t在類(lèi)C文檔集中出現(xiàn)越頻繁，即m值越大，則詞條t對(duì)類(lèi)C的區(qū)分能力越強(qiáng)，因此IDF'的值應(yīng)該越大。

所以IDF'是關(guān)于m的增函數(shù)，隨m值的增大而增大。

2)驗(yàn)證2:詞條在類(lèi)C文檔集中出現(xiàn)越少，即j值越大，則詞條t對(duì)類(lèi)C的區(qū)分能力越弱，因此IDF'的值應(yīng)該越小。

所以IDF'是關(guān)于j的減函數(shù)，隨j的增大而減小。

3)驗(yàn)證3:詞條t在非類(lèi)C文檔集中出現(xiàn)越頻繁，即k值越大，則詞條t對(duì)類(lèi)C的區(qū)分能力越弱，因此IDF'的值應(yīng)該越小。

所以IDF'是關(guān)于k的減函數(shù)，隨k的增大而減小。

4)驗(yàn)證4:詞條t的非類(lèi)C文檔集中出現(xiàn)越少，即i值越大，則詞條對(duì)類(lèi)C的區(qū)分能力越強(qiáng)，因此IDF'的值應(yīng)該越大。

所以IDF'是關(guān)于i的增函數(shù)，隨i的增大而增大。

通過(guò)上述4個(gè)驗(yàn)證發(fā)現(xiàn)，改進(jìn)后的算法在理論上符合文本分類(lèi)的實(shí)際，可以應(yīng)用于文本分類(lèi)時(shí)的權(quán)重計(jì)算。

3 特征選擇及分類(lèi)策略

1)特征選擇。

在中文文本分類(lèi)中，對(duì)語(yǔ)料集中的文本進(jìn)行分詞，去停用詞后，形成的特征詞集合，稱(chēng)之為初始特征集。在初始特征集中，特征詞的個(gè)數(shù)可能是成千上萬(wàn)的。也就是說(shuō)經(jīng)過(guò)分詞，去停用詞后所形成的特征空間的維數(shù)是非常大的。高維的特征空間給文本分類(lèi)的效率帶來(lái)了很大的影響［7］。特征選擇就是用于高維特征空間的降維處理。常用特征選擇的方法有文檔頻率(DF:Document Frequency)、信息增益(IG:Information Gain)、互信息(MI:Mutual Information)、χ2統(tǒng)計(jì)量(CHI:Chi-square)等［14］。

本文在后續(xù)的實(shí)驗(yàn)驗(yàn)證過(guò)程中，特征采用的是χ2統(tǒng)計(jì)量。χ2統(tǒng)計(jì)量方法是度量詞條t與類(lèi)C之間的相關(guān)性，認(rèn)為兩者的關(guān)系近似服從自由度為1的χ2分布，χ2統(tǒng)計(jì)值越大，詞條t與類(lèi)C相關(guān)性越大。計(jì)算公式如下:

其中，N表示語(yǔ)料中的文檔總數(shù)，A表示屬于類(lèi)C且包含詞條t的文檔數(shù)，B表示不屬于類(lèi)C但包含詞條t的文檔數(shù)，C表示屬于類(lèi)C但不包含詞條t的文檔數(shù)，D表示不屬于類(lèi)C且不包含詞條t的文檔數(shù)。

2)分類(lèi)策略—Rocchio方法［15］。

該方法根據(jù)算術(shù)平均為每類(lèi)文本集生成一個(gè)代表該類(lèi)的中心向量，然后在新文本到來(lái)時(shí)，確定新文本向量，計(jì)算該向量與每類(lèi)分類(lèi)中心的距離(相似度)，則判定該文本屬于與其距離最近的那個(gè)類(lèi)。相似度的計(jì)算公式如下［16］:

其中，Sim(Di，Dj)表示待分類(lèi)文檔與指定類(lèi)別的相似度，Di為待分類(lèi)文檔，Dj為第j類(lèi)文檔的中心向量，M為特征向量的維數(shù)，Wk為向量的第k維(即第k個(gè)詞條的權(quán)重)。本文在后續(xù)實(shí)驗(yàn)中也采用這種分類(lèi)計(jì)算的方法。

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

通過(guò)網(wǎng)絡(luò)爬蟲(chóng)從新浪新聞中抓取了財(cái)經(jīng)、房產(chǎn)、教育、軍事和體育5大類(lèi)的新聞作為本次實(shí)驗(yàn)的語(yǔ)料庫(kù)。每個(gè)大類(lèi)分別抓取了500篇新聞，共2500篇文檔作為總語(yǔ)料庫(kù)，其中每個(gè)類(lèi)取400篇，共2000篇作為訓(xùn)練集，形成分類(lèi)器，每個(gè)類(lèi)別剩下的100篇，共500篇作為測(cè)試集，測(cè)試改進(jìn)后TFIDF算法的效果。表1為實(shí)驗(yàn)數(shù)據(jù)中訓(xùn)練集與測(cè)試集的類(lèi)別分布情況。

表1 實(shí)驗(yàn)數(shù)據(jù)中訓(xùn)練集與測(cè)試集的類(lèi)別分布情況

通常采用召回率和準(zhǔn)確率來(lái)評(píng)價(jià)文本分類(lèi)效果的優(yōu)劣。對(duì)于某一特定的類(lèi)別，召回率R(Recall，查全率)定義為:被正確分類(lèi)的文檔數(shù)和被測(cè)試文檔總數(shù)的比例，即該類(lèi)樣本被分類(lèi)器正確識(shí)別的概率。準(zhǔn)確率P(Precision，查對(duì)率)定義為:正確分類(lèi)的文檔數(shù)與被分類(lèi)器識(shí)別為該類(lèi)別的文檔數(shù)比率，即分類(lèi)器做出正確決策的概率。為了從召回率和查全率2個(gè)方面綜合考慮，一般用F值進(jìn)行分類(lèi)效果評(píng)價(jià)，其計(jì)算公式:F=，F(xiàn)值越大，反映出分類(lèi)效果越好，說(shuō)明改進(jìn)的TFIDF算法越優(yōu)越。

本文分別用了傳統(tǒng) TFIDF算法、文獻(xiàn)［6］的TFIDF算法及筆者改進(jìn)的TFIDF算法對(duì)文本數(shù)據(jù)進(jìn)行了分類(lèi)，分類(lèi)效果用F值評(píng)價(jià)，實(shí)驗(yàn)的大致流程如圖1所示。

圖1 文本分類(lèi)實(shí)驗(yàn)流程圖

為了更好地確定卡方選取特征值的個(gè)數(shù)，本文對(duì)3種不同算法分別取每個(gè)類(lèi)別卡方值前60，70，80，90，100等，然后分別進(jìn)行文本分類(lèi)，觀(guān)察文本的總體分類(lèi)效果，結(jié)果如圖2所示。

圖2 不同卡方取值下文本分類(lèi)的效果

從圖2中可以看出，當(dāng)取每個(gè)類(lèi)別卡方值的前80個(gè)詞條作為特征項(xiàng)時(shí)，文本分類(lèi)的效果最佳。于是本文選取80個(gè)特征項(xiàng)進(jìn)行分類(lèi)，具體結(jié)果如表2所示。

表2 不同TFIDF算法的分類(lèi)效果評(píng)價(jià)

從表2的實(shí)驗(yàn)數(shù)據(jù)中可以看出，傳統(tǒng)TFIDF算法的F1值較小，而文獻(xiàn)［6］改進(jìn)的TFIDF算法確實(shí)對(duì)文檔分類(lèi)的效果有了一定改善，但筆者改進(jìn)的TFIDF算法對(duì)文檔分類(lèi)效果則有了較大的提升。實(shí)驗(yàn)證明，通過(guò)改進(jìn)IDF算法，充分考慮了詞條t在類(lèi)間與類(lèi)內(nèi)的分布，對(duì)文檔分類(lèi)的準(zhǔn)確率和召回率都有一定提高，有助于改善文檔分類(lèi)的效果。

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

本文從文本分類(lèi)的研究現(xiàn)狀及意義出發(fā)，總結(jié)了文本分類(lèi)常用的幾種算法的優(yōu)缺點(diǎn)，并對(duì)其中最常用的TFIDF算法進(jìn)行改進(jìn)，通過(guò)修改IDF的計(jì)算方法，用類(lèi)C內(nèi)包含詞條t的文檔占比和類(lèi)C外包含t的文檔占比來(lái)衡量詞條t在類(lèi)間和類(lèi)內(nèi)的分布來(lái)計(jì)算IDF，從而充分考慮了詞條t在類(lèi)間與類(lèi)內(nèi)的分布。最后，本文還將改進(jìn)的TFIDF算法用在實(shí)驗(yàn)文本的分類(lèi)上，通過(guò)與傳統(tǒng) TFIDF算法的比較，改進(jìn)的TFIDF算法確實(shí)對(duì)文檔分類(lèi)的效果有了一定的提升。

下一步的研究方向可以針對(duì)向量空間模型的特征值選取方法做一些改進(jìn)，更有效率地選取出最具代表性的特征值，同時(shí)，在文本的分類(lèi)策略上，也可以做一些改進(jìn)，以期達(dá)到更好的文本分類(lèi)效果。

［1］Salton G，McGill M J.Introduction to Modern Information Retrieval［M］.McGraw-Hill，1983.

［2］Luhn H P.Auto-encoding of Documents for Information Retrieval Systems［M］//Modern Trends in Documentation.New York:Pergamon Press，1959:68-95.

［3］Salton G，Wong A，Yang C S.A vector space model for automate indexing［J］.Communications of ACM，1975，18(11):613-620.

［4］Lewis D D.Na?ve Bayes at forty:The independence assumption in information retrieval［C］//Proceedings of the 10th European Conference on Machine Learning.1998:4-15.

［5］李榮陸，胡運(yùn)發(fā).基于密度的KNN文本分類(lèi)器訓(xùn)練樣本裁剪方法［J］.計(jì)算機(jī)研究與發(fā)展，2004，41(4):539-545.

［6］Hsu C，Lin C.A comparison on methods for multi-class support vector machines［J］.IEEE Transactions on Neural Networks，2002，13(2):415-425.

［7］宋惟然.中文文本分類(lèi)中的特征選擇和權(quán)重計(jì)算方法研究［D］.北京:北京工業(yè)大學(xué)，2013.

［8］候敏.計(jì)算語(yǔ)言學(xué)與漢語(yǔ)自動(dòng)分析［M］.北京:北京廣播學(xué)院出版社，1999.

［9］苗奪謙，衛(wèi)志華.中文文本信息處理的原理與應(yīng)用［M］.北京:清華大學(xué)出版社，2007.

［10］Salton G.On the construction of effective vocabularies for information retrieval［C］//Proceedings of the 1973 Meeting on Programming Languages and Information Retrieval.1973:48-60.

［11］張保富，施化吉，馬素琴.基于TFIDF文本特征加權(quán)方法的改進(jìn)研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28(2):17-20.

［12］張建娥.基于TFIDF和詞語(yǔ)關(guān)聯(lián)度的中文關(guān)鍵詞提取方法［J］.情報(bào)科學(xué)，2012，30(10):1542-1555.

［13］李學(xué)明，李海瑞，薛亮，等.基于信息增益與信息熵的TFIDF算法［J］.計(jì)算機(jī)工程，2012，38(8):37-40.

［14］Cohen W，Singer Y.Context-sensitive learning methods for text categorization［J］.ACM Trans.Information Systems，1996，17(2):146-173.

［15］Han E H，Karypis G.Centroid-based document classification:Analysis＆ experim-ental results［C］//European Conference on Principles of Data Mining and Knowledge Discovery(PKDD).2000:424-431.

［16］張玉芳，彭時(shí)名，呂佳.基于文本分類(lèi)TFIDF方法的改進(jìn)與應(yīng)用［J］.計(jì)算機(jī)工程，2006，32(19):76-78.

［17］施聰鶯，徐朝軍，楊曉江.TFIDF算法研究綜述［J］.計(jì)算機(jī)應(yīng)用，2009，29(B6):167-170，180.