馬慧芳，邢玉瑩，王 雙，張旭鵬

(1.西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州 730070;2.桂林電子科技大學(xué)廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

1 引言

隨著微博、社交網(wǎng)站等應(yīng)用的發(fā)展，越來(lái)越多的信息以短文本的形式存在且呈爆炸式增長(zhǎng)?？焖儆行У貜暮Ａ慷涛谋緮?shù)據(jù)中獲取所需要的關(guān)鍵信息，短文本挖掘技術(shù)發(fā)揮著非常重要的作用。短文本特征極度稀疏且難以提取。通常來(lái)說(shuō)，特征獲取主要有兩大類方法：一類稱為特征選擇[1]，指的是從原有的特征中提取出少量的、具有代表性的特征，但特征的類型不發(fā)生變化；另一類稱為特征抽取[2]，是指從原有的特征中重構(gòu)出新的特征，新的特征具有更強(qiáng)的代表性。

傳統(tǒng)的詞條加權(quán)方法主要分為兩種：無(wú)監(jiān)督的詞頻TF(Term Frequency)、詞頻-逆文件頻率TF*IDF(Term Frequency*Inverse Document Frequency)[3,4]和有監(jiān)督的tf*χ2(term frequency*chi-square)、tf*ig(term frequency*information gain)[5]等。采用無(wú)監(jiān)督的方法能夠給詞條加權(quán)，卻忽略了短文本的類別信息。有監(jiān)督的詞條加權(quán)方法[6,7]將其考慮進(jìn)來(lái)，并在一定程度上提高了短文本特征提取的表現(xiàn)力。

與長(zhǎng)文本相比，短文本具有特征高度稀疏的特點(diǎn)。從詞項(xiàng)共現(xiàn)角度來(lái)看，兩個(gè)詞項(xiàng)的關(guān)聯(lián)性可從詞項(xiàng)共現(xiàn)的角度體現(xiàn)，且短文本所包含的詞語(yǔ)稀少，兩詞項(xiàng)之間相隔詞項(xiàng)的距離對(duì)語(yǔ)義信息的計(jì)算也造成了一定的影響；從類別信息的角度來(lái)看，特征詞在類間的分布以及在類內(nèi)部文檔中的分布情況可以考慮進(jìn)來(lái)進(jìn)行綜合加權(quán)。一方面，若特征詞在各個(gè)類間分布比較均勻，這樣的詞對(duì)分類基本沒(méi)有貢獻(xiàn)，若特征詞比較集中地分布在某個(gè)類中，而在其它類中幾乎不出現(xiàn)，這樣的詞就能夠很好地代表這個(gè)類的特征。如何將這種詞語(yǔ)的類別信息挖掘出來(lái)是至關(guān)重要的。

基于以上考慮，本文提出了一種新的短文本特征提取方法，即融合詞語(yǔ)之間的共現(xiàn)距離和類別信息的短文本特征提取方法CDCISE(Combining term co-occurrence Distance and Category Information for Short text feature Extraction)。首先，計(jì)算詞項(xiàng)之間共現(xiàn)距離相關(guān)度，同時(shí)結(jié)合詞項(xiàng)在整個(gè)文本的共現(xiàn)區(qū)分度，并以此為依據(jù)對(duì)詞項(xiàng)進(jìn)行加權(quán)；其次，改進(jìn)期望交叉熵計(jì)算方法，充分考慮短文本的類別信息，使得在對(duì)短文本進(jìn)行特征提取時(shí)更加合理；再次，將共現(xiàn)區(qū)分度和類別信息結(jié)合計(jì)算詞條權(quán)重，避免了傳統(tǒng)的基于詞頻的文本特征提取方法表現(xiàn)力較差的問(wèn)題；最后，使用該方法分別在中文、英文的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該方法有效地提高了短文本特征提取的效果。

2 相關(guān)理論

2.1 特定文本中詞項(xiàng)的相關(guān)度

給定短文本集合D={d1,d2,…,dm}和詞項(xiàng)集T={t1,t2,…,tn},詞項(xiàng)ti與詞項(xiàng)tj在特定短文本ds中的相關(guān)度的計(jì)算公式如下：

(1)

其中,distds(ti,tj)為詞項(xiàng)ti與詞項(xiàng)tj在短文本ds中的共現(xiàn)距離[8]，由這兩個(gè)詞項(xiàng)之間相隔的詞項(xiàng)數(shù)計(jì)算得出，即|j-i|-1。例如，短文本d1“社交網(wǎng)絡(luò)環(huán)境下的隱私保護(hù)策略”在經(jīng)過(guò)停用詞過(guò)濾、文本分詞的預(yù)處理過(guò)程后變?yōu)椤吧缃?網(wǎng)絡(luò) 環(huán)境 隱私 保護(hù) 策略”，詞項(xiàng)“社交”與詞項(xiàng)“隱私”之間的共現(xiàn)距離distd1(社交，隱私)=2。傳統(tǒng)的距離計(jì)算方法在計(jì)算兩個(gè)詞項(xiàng)之間的距離時(shí)忽略了兩詞項(xiàng)與其相隔詞項(xiàng)之間的語(yǔ)義聯(lián)系，采用共現(xiàn)距離的計(jì)算方法，將詞項(xiàng)的上下文語(yǔ)境考慮進(jìn)來(lái)，使得計(jì)算結(jié)果更為可靠。利用詞項(xiàng)之間的共現(xiàn)距離來(lái)計(jì)算兩個(gè)詞項(xiàng)之間的相關(guān)度與傳統(tǒng)的計(jì)算相關(guān)度的方法[9]相比也顯得更為合理。由于計(jì)算公式(1)時(shí)需要遍歷語(yǔ)料庫(kù)中所有詞項(xiàng)，因此計(jì)算的時(shí)間復(fù)雜度為O(n2)。

2.2 期望交叉熵

期望交叉熵ECE(Expected Cross Entropy)是一種基于信息論的特征選擇方法，它反映了文本類別的概率分布以及在包含某個(gè)特征詞時(shí)文本類別概率之間的距離，考慮了詞頻以及詞項(xiàng)和類別之間的關(guān)系。ECE值越大，表明該特征詞越能表示一個(gè)類的特征，即該特征詞對(duì)類別分布的影響越大。詞項(xiàng)ti的ECE值計(jì)算公式如下：

(2)

其中，P(ti,ds)表示詞項(xiàng)ti在短文本ds中出現(xiàn)的概率；P(Cr)表示Cr類短文本在短文本集D中出現(xiàn)的概率；P(Cr|ti)表示短文本ds包含詞項(xiàng)ti時(shí)屬于類別Cr的概率。

3 融合詞語(yǔ)共現(xiàn)距離和類別信息的短文本特征提取方法

3.1 基于詞語(yǔ)共現(xiàn)距離的詞條加權(quán)方法

短文本特征提取是短文本挖掘技術(shù)的關(guān)鍵步驟，可以幫助人們快速有效地從海量數(shù)據(jù)中獲取關(guān)鍵信息。

特征提取實(shí)質(zhì)上是一個(gè)文本降維[10]的過(guò)程，其目的是通過(guò)剔除決策意義不大的詞項(xiàng)進(jìn)而提高短文本分類的準(zhǔn)確性和效率。傳統(tǒng)的詞條加權(quán)方法未充分考慮詞語(yǔ)之間的語(yǔ)義信息和類別分布信息，本文提出的融合詞語(yǔ)共現(xiàn)距離和類別信息的短文本特征提取方法的總體流程如圖1所示，具體由如下幾個(gè)步驟構(gòu)成：

步驟1對(duì)k類測(cè)試短文本集合D′進(jìn)行預(yù)處理得到k類短文本集合D和詞集T；

步驟2利用詞語(yǔ)之間的共現(xiàn)距離計(jì)算每個(gè)詞項(xiàng)的關(guān)聯(lián)權(quán)重；

步驟3利用期望交叉熵對(duì)某個(gè)類中的每個(gè)詞項(xiàng)計(jì)算其ECE″值；

步驟4結(jié)合步驟2和步驟3的計(jì)算結(jié)果得到某個(gè)類別中所有詞項(xiàng)的權(quán)重值，分別將不同類別中的詞項(xiàng)按權(quán)重值進(jìn)行降序排序，取前K個(gè)作為特征詞，構(gòu)造出新的特征詞項(xiàng)集合。

Figure 1 Flow diagram for short text feature extraction combining term co-occurrence distance and category information圖1 融合詞語(yǔ)共現(xiàn)距離和類別信息的短文本特征提取方法流程圖

傳統(tǒng)的詞條加權(quán)方法在計(jì)算詞項(xiàng)共現(xiàn)情況時(shí)沒(méi)有考慮到詞項(xiàng)之間的距離，本文提出的利用詞項(xiàng)共現(xiàn)距離的方法來(lái)計(jì)算某個(gè)詞項(xiàng)的關(guān)聯(lián)權(quán)重可以有效地解決這一問(wèn)題。本階段用到的符號(hào)定義如表1所示。

由公式(1)可計(jì)算：

(3)

Table 1 Notation definition表1 符號(hào)定義表

(4)

則詞項(xiàng)ti在特定短文本ds中的關(guān)聯(lián)權(quán)重計(jì)算公式如下：

(5)

(6)

(7)

其中，cowr(ti)反映了詞項(xiàng)ti在第Cr類短文本集中關(guān)聯(lián)權(quán)重的整體情況。

3.2 構(gòu)造特征詞典

如何從短文本中選取最能代表類別特征的詞項(xiàng)作為特征詞項(xiàng)是構(gòu)造特征詞典的關(guān)鍵。所選的特征詞應(yīng)該滿足以下兩個(gè)條件：一是能夠較好地概括短文本的內(nèi)容信息；二是有較好的局部指示性，即該詞項(xiàng)能較好地揭示短文本所在類別的信息。第一個(gè)條件采用關(guān)聯(lián)性加權(quán)策略即可滿足，第二個(gè)條件可以采用ECE"值[11]來(lái)權(quán)衡所選的特征詞的局部指示性。

在公式(2)中，詞項(xiàng)ti在所有的類別中具有綜合的權(quán)重值。然而，在大多數(shù)情況下，一個(gè)能代表A類信息的詞項(xiàng)，很有可能對(duì)類別B分布的影響不大。因此，應(yīng)該將該詞項(xiàng)在不同類別中的權(quán)重值考慮在內(nèi)。詞項(xiàng)ti在類別Cr中的權(quán)重值計(jì)算公式如下：

(8)

由公式(8)可知，當(dāng)P(Cr|ti)的值越大，即詞項(xiàng)ti和類別Cr相關(guān)性越強(qiáng)時(shí)，P(Cr|ti)/P(Cr)越大，則詞項(xiàng)ti對(duì)類別Cr的作用就越大。當(dāng)詞項(xiàng)ti與某一類別強(qiáng)相關(guān)，且與其他類別的相關(guān)性較弱時(shí)，被選中的可能性也就越大。詞項(xiàng)ti在除類別Cr外的其它類中的權(quán)重值計(jì)算公式[12]如下：

(9)

其中，ECE′(ti,Cj)表示詞項(xiàng)ti在剩下k-1個(gè)類別中的平均權(quán)重。

(10)

其中，ECE″(ti,Cr)反映了詞項(xiàng)ti在類別Cr中的整體權(quán)重值。該值越大，說(shuō)明詞項(xiàng)ti對(duì)類別Cr的指示性越強(qiáng)。利用公式(10)對(duì)類別Cr中的所有詞項(xiàng)計(jì)算其ECE″值。在類別Cr中詞項(xiàng)ti的最終權(quán)重計(jì)算公式如下：

Wti=cowr(ti)×ECE″(ti,Cr)×idf(ti)

(11)

(12)

其中，cowr(ti)揭示了對(duì)于第Cr類短文本集而言詞項(xiàng)ti的重要程度；ECE″(ti,Cr)反映了詞項(xiàng)ti對(duì)短文本所屬類別的指示性；idf(ti)為詞項(xiàng)ti的逆向文檔頻率，表現(xiàn)了詞項(xiàng)ti對(duì)短文本的區(qū)分程度，可以由第Cr類的短文本總數(shù)|Dr|除以其中包含詞項(xiàng)ti的短文本數(shù)，再將得到的商值取對(duì)數(shù)計(jì)算可得。如果包含詞項(xiàng)ti的短文本數(shù)越少，則idf(ti)的值越大，說(shuō)明詞項(xiàng)ti對(duì)類別區(qū)分的能力也越強(qiáng)。

對(duì)類別Cr中的詞項(xiàng)按Wti值進(jìn)行降序排列，取前K個(gè)詞項(xiàng)作為特征詞項(xiàng)。對(duì)短文本集中的每個(gè)類別進(jìn)行相同的處理，并把得到的每一類別的特征詞項(xiàng)進(jìn)行合并構(gòu)造出新的特征詞典。

隨著特征詞典大小的增長(zhǎng)，本文方法的計(jì)算時(shí)間會(huì)呈現(xiàn)出指數(shù)的增長(zhǎng)趨勢(shì)。這是由于在詞項(xiàng)集中，每計(jì)算一個(gè)詞項(xiàng)與其余詞項(xiàng)之間的相關(guān)度與共現(xiàn)度需要遍歷一次文本庫(kù)，故在特征詞典長(zhǎng)度為n時(shí)，該算法的時(shí)間復(fù)雜度為O(n2)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集及預(yù)處理

為了驗(yàn)證本文提出方法的有效性，分別收集中國(guó)計(jì)算機(jī)學(xué)會(huì)CCF(China Computer Federation)會(huì)議推薦列表中的A類會(huì)議與B類會(huì)議中的15類共750篇文章標(biāo)題作為英文數(shù)據(jù)集，中國(guó)科學(xué)引文數(shù)據(jù)庫(kù)CSCD(Chinese Science Citation Database)中的5類共12 534篇文章標(biāo)題作為中文數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。本文采用5折交叉驗(yàn)證的方法，將所有類別中的數(shù)據(jù)樣本隨機(jī)劃分成五個(gè)大小相等的子樣本，交叉驗(yàn)證過(guò)程重復(fù)五次。每次一個(gè)樣本被保留作為測(cè)試集的驗(yàn)證數(shù)據(jù),其余四個(gè)樣本作為訓(xùn)練數(shù)據(jù)。訓(xùn)練集主要用來(lái)訓(xùn)練使用本文方法學(xué)習(xí)所得的模型，測(cè)試集主要用來(lái)驗(yàn)證本文方法是否能對(duì)短文本進(jìn)行準(zhǔn)確分類。

對(duì)短文本集進(jìn)行預(yù)處理,包括數(shù)據(jù)去噪、文本分詞、停用詞過(guò)濾等處理。其中對(duì)中文分詞的處理采用了jieba中文分詞工具。得到新的短文本特征詞項(xiàng)集后，將實(shí)驗(yàn)中的短文本以向量形式進(jìn)行表示并采用支持向量機(jī)SVM(Support Vector Machine)與k-NN(k-Nearest Neighbor)分類器進(jìn)行分類。其中，SVM采用Libsvm包,將k-NN中的近鄰數(shù)設(shè)置為61進(jìn)行比較。

4.2 評(píng)價(jià)指標(biāo)

本文涉及的評(píng)價(jià)指標(biāo)包括準(zhǔn)確率Accuracy和F1-measure[13]，其定義如下：

(13)

其中，TP、TN、FP、FN分別為真正(事實(shí)上是正樣本，被判定為正樣本)、真負(fù)(事實(shí)上是正樣本，被判定為負(fù)樣本)、假正(事實(shí)上是負(fù)樣本，被判定為正樣本)、假負(fù)(事實(shí)上是負(fù)樣本，被判定為負(fù)樣本)。P是精確率，R是召回率，其計(jì)算公式如下:

(14)

(15)

4.3 實(shí)驗(yàn)結(jié)果與相關(guān)分析

為了驗(yàn)證本文方法的有效性，共設(shè)計(jì)了三個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1使用SVM和k-NN分類器來(lái)驗(yàn)證使用本文方法獲取到的特征詞典的大小對(duì)短文本分類準(zhǔn)確性的影響；實(shí)驗(yàn)2將本文方法與其他方法得到的特征詞典進(jìn)行對(duì)比；實(shí)驗(yàn)3將不同方法得到的特征詞典應(yīng)用到SVM分類器中，驗(yàn)證使用不同策略的特征提取方法對(duì)短文本分類的影響。本文將只考慮類別信息不考慮詞語(yǔ)之間的共現(xiàn)距離的特征提取方法CISE(combining Category Information for Short text feature Extraction)、考慮共現(xiàn)距離但不考慮類別信息的特征提取方法CDSE(Combining term co-occurrence Distance for Short text feature Extraction)、考慮詞語(yǔ)之間的共現(xiàn)情況但不考慮類別信息的特征提取方法TCSE(combining Term co-occurrence Condition for Short text feature Extraction)以及TF*IDF方法與本文方法得到的特征詞項(xiàng)集進(jìn)行比較，驗(yàn)證使用本文方法所構(gòu)造的特征詞典對(duì)短文本進(jìn)行分類的高效性。

選擇以上四種特征提取方法作為對(duì)比方法是基于以下幾點(diǎn)考慮:(1)本文的方法是在傳統(tǒng)的特征提取方法基礎(chǔ)上通過(guò)融合詞項(xiàng)之間的共現(xiàn)情況以及短文本的類別信息改進(jìn)而來(lái)的,CDSE方法和CISE方法與本文的方法最為相似；(2)選用CISE方法將短文本的類別信息考慮進(jìn)來(lái)而不考慮詞項(xiàng)之間的共現(xiàn)情況可以顯示出類別信息對(duì)構(gòu)建特征詞典的重要性；(3)TF*IDF方法則是將共現(xiàn)距離與類別信息均忽略的傳統(tǒng)特征提取方法。

4.3.1 特征詞典大小對(duì)短文本分類的影響

為了驗(yàn)證使用本文方法獲取到的特征詞典的長(zhǎng)度對(duì)短文本分類造成的影響，分別取特征詞項(xiàng)集中的前30、40、50、60、70、80、90、100、110、130、160、180、200、230、250、280和300個(gè)特征詞項(xiàng)構(gòu)造特征詞典，在SVM和k-NN分類器上進(jìn)行分類測(cè)試。其中，SVM分類器使用了Libsvm-3.2.1版本的插件，通過(guò)調(diào)整相應(yīng)參數(shù)并最終選用非啟發(fā)式線性核函數(shù)作為訓(xùn)練支持向量機(jī)模型的主要函數(shù)。在使用k-NN分類器進(jìn)行模型訓(xùn)練時(shí)，通過(guò)調(diào)整K近鄰數(shù)發(fā)現(xiàn)當(dāng)特征詞典長(zhǎng)度一定時(shí)，以20為基數(shù)，步長(zhǎng)為2的速度增長(zhǎng)所得到的準(zhǔn)確率和F1-measure值在近鄰數(shù)為61時(shí)能較好地反映出所訓(xùn)練模型的高效性。

如圖2所示，在SVM和k-NN兩種分類器上，使用本文方法得到的特征詞典均可以有效地對(duì)短文本進(jìn)行分類且使用SVM分類器的分類效果明顯優(yōu)于k-NN分類器的。

Figure 2 Effect of feature dictionary size on short text classification圖2 特征詞典大小對(duì)短文本分類的影響

在使用SVM訓(xùn)練出的分類模型進(jìn)行短文本分類時(shí)，隨著特征詞項(xiàng)數(shù)目從30增加到300，準(zhǔn)確率和F1-measure值均呈現(xiàn)出先增長(zhǎng)后下降的波動(dòng)走勢(shì)直至趨于穩(wěn)定，且當(dāng)Top值在60時(shí)達(dá)到峰值，分類效果最佳。在使用k-NN訓(xùn)練出的分類模型進(jìn)行短文本分類時(shí)，準(zhǔn)確率和F1-measure值呈現(xiàn)出先增長(zhǎng)后下降的波動(dòng)趨勢(shì)且特征詞典長(zhǎng)度為80時(shí)分類效果最佳。

4.3.2 特征詞典比較

為了驗(yàn)證使用本文方法得到的特征詞典對(duì)短文本分類的高效性，對(duì)比了上述5種特征提取方法所得到的特征詞典。以處理后的人工智能與模式識(shí)別這一類別3 598個(gè)詞項(xiàng)中的前30個(gè)詞項(xiàng)為例，如表2所示，使用CDSE方法得到的特征詞項(xiàng)與TCSE方法得到的特征詞項(xiàng)相比，前者較能表示該類的特征，說(shuō)明使用詞語(yǔ)之間的共現(xiàn)距離來(lái)衡量?jī)蓚€(gè)詞項(xiàng)之間的共現(xiàn)情況更為有效。

顯然，與本文方法相比，使用CISE與CDSE方法得到的特征詞典均有欠缺，證明了詞語(yǔ)之間的共現(xiàn)距離與類別信息這兩個(gè)因素都不可忽視，而將兩個(gè)因素均未考慮在內(nèi)的TF*IDF方法得到的特征詞項(xiàng)效果最差。該實(shí)驗(yàn)說(shuō)明了與其它4種方法相比，使用本文方法提取出來(lái)的特征詞項(xiàng)能更好地表示特征且使用這種方法得到的結(jié)果也更為合理。

4.3.3 不同特征提取方法對(duì)短文本分類的影響

為了驗(yàn)證使用不同策略的特征提取方法對(duì)短文本分類造成的影響，選取不同長(zhǎng)度的特征詞典在Libsvm中訓(xùn)練分類模型，實(shí)驗(yàn)1的結(jié)果顯示使用SVM分類器在特征詞典長(zhǎng)度為60時(shí)分類準(zhǔn)確度最高，效果最好且使用該分類器的波動(dòng)程度與k-NN分類器比較而言較為穩(wěn)定。所以，選取SVM分類器并在中英文數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，觀察特征詞項(xiàng)數(shù)目為60時(shí)各個(gè)方法得到的特征詞典對(duì)短文本分類準(zhǔn)確性的影響，其準(zhǔn)確率和F1-measure值如表3所示。

使用本文方法在中英文數(shù)據(jù)集上進(jìn)行短文本分類時(shí)得到的準(zhǔn)確率和F1-measure值均大于其它4種方法，說(shuō)明本文方法更能有效地對(duì)短文本進(jìn)行分類且本文提出的特征提取方法適用于不同種類的語(yǔ)言。

此外，詞語(yǔ)之間的共現(xiàn)情況較類別信息而言對(duì)短文本分類造成的影響更大，且使用共現(xiàn)距離來(lái)衡量詞項(xiàng)之間的共現(xiàn)程度明顯優(yōu)于傳統(tǒng)共現(xiàn)情況計(jì)算方法。然而，采用傳統(tǒng)的特征提取方法對(duì)短文本進(jìn)行分類時(shí)，其準(zhǔn)確率和F1-measure值最低，分類效果最差。

Table 2 Comparison of different feature dictionaries表2 不同特征詞典的比較

Table 3 Classification performance of the feature extraction methods表3 不同特征提取方法的分類性能

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

針對(duì)傳統(tǒng)的詞條加權(quán)方法沒(méi)有充分考慮到詞語(yǔ)之間的語(yǔ)義信息和類別分布信息，本文提出了一種新的短文本特征提取方法，即融合詞語(yǔ)共現(xiàn)距離和類別信息的短文本特征提取方法。該方法利用詞語(yǔ)之間的共現(xiàn)距離計(jì)算相關(guān)度，避免了傳統(tǒng)方法無(wú)法判斷一個(gè)特征是否有區(qū)分度以及區(qū)分度是否足夠的缺點(diǎn)，并將詞條的類別信息充分考慮在內(nèi)，使得對(duì)文本提取的特征更加合理。在中文、英文數(shù)據(jù)集上的實(shí)驗(yàn)說(shuō)明，該方法能顯著提高短文本特征提取的效果。