融合語義與圖結(jié)構(gòu)的短文本特征提取算法

馬慧芳,劉曉倩,馬 蘭,伍詩萌

1(西北師范大學 計算機科學與工程學院,蘭州 730070)2(桂林電子科技大學 廣西可信軟件重點實驗室,廣西 桂林 541004) E-mail:mahuifang@yeah.net

1 引 言

隨著信息時代的飛速發(fā)展,微博、微信、說說、新聞、團購、郵件、手機短信等大量互聯(lián)網(wǎng)平臺興起,給人們帶來便利的交流環(huán)境,同時也將多種形式的短文本數(shù)據(jù)大量的引入到了人們的日常生活之中.與傳統(tǒng)文本不同,這些短文本主要表現(xiàn)為簡略的描述說明、觀點評論、簡單對答或情感抒發(fā)等,文本長度一般不超過140個字符.當前社會中短文本的數(shù)量多,信息量大,其中包羅了人們對各類社會現(xiàn)象或商品的反映、評價,對眾多領(lǐng)域有著非常重要的作用,因此從海量的短文本數(shù)據(jù)中快速并準確地獲取有用的信息,特征提取技術(shù)發(fā)揮著非常重要的作用[1].

傳統(tǒng)的特征提取算法大多適用于長文本,且短文本較之長文本具有信息量巨大、特征稀疏等顯著特點,因此提出一種有效的針對短文本的特征提取算法至關(guān)重要.現(xiàn)有的短文本特征提取算法可歸納為以下三類:

1)基于統(tǒng)計信息的算法:主要從詞頻、位置等角度考慮特征詞的重要性,常見的算法有TFIDF算法[2,3],N-Gram算法[4]等.楊震等[5]提出一種基于通過詞出現(xiàn)間距的內(nèi)在與外在模式的信息熵差進行關(guān)鍵詞排序的方法,該方法認為特征詞的出現(xiàn)受話題中的關(guān)鍵詞位置的統(tǒng)計特征和文本中話題簇的統(tǒng)計屬性兩方面影響.已有的工作[6]將同一短文本中兩個詞語之間的間隔詞數(shù)作為共現(xiàn)距離[7],計算詞語之間相關(guān)度進而體現(xiàn)詞語間語義關(guān)聯(lián).但其不足之處在于未考慮到詞語間的隱含語義;

2)基于圖的特征提取算法:該類算法建立在詞頻統(tǒng)計基礎(chǔ)上,將詞語及其語義關(guān)系映射到文本結(jié)構(gòu)圖,提取出若干重要的頂點即為關(guān)鍵詞.劉嘯劍等[8]利用LDA主題模型,計算出詞與詞之間的相似性作為詞與詞之間的權(quán)重,并構(gòu)建一個帶權(quán)無向詞圖,選擇短語作為圖的節(jié)點從而提取出特征詞項.該方法的缺點在于僅僅考慮了圖的結(jié)構(gòu),而忽略了像節(jié)點屬性之類的外部信息;

3)基于語義的算法:采用語義詞典或者詞匯鏈方法來獲取詞匯間的語義知識來提取文本特征詞項.該算法提高了提取的準確率,但是依賴于背景知識庫、詞典、詞表等,無法提取出不包含于知識庫的詞或詞組,對文本格式要求嚴格.

針對現(xiàn)有方法的不足,本文提出一種融合語義與圖結(jié)構(gòu)的短文本特征提取算法(Short Text Feature Extraction Algorithm Based on Semantic and Graph Structure,SFESGS),該算法以構(gòu)造圖的方式來表示文本,并利用語義耦合關(guān)系以及圖結(jié)構(gòu)特征計算詞對間的相似度對文本圖中的邊加權(quán),然后設(shè)計一種隨機游走的方法將兩種邊的加權(quán)方案有效地結(jié)合起來進行迭代計算出節(jié)點的重要性,實現(xiàn)對文本特征的提取.最后,本文選取中英文短文本作為實驗數(shù)據(jù)集,對算法進行了驗證.實驗結(jié)果表明,本文所提出的算法可行且有效.

2 相關(guān)理論

2.1 詞對內(nèi)部語義耦合

詞對內(nèi)部語義耦合[9]是為了研究詞項之間的顯式語義關(guān)系.假設(shè)出現(xiàn)在同一文本中的詞語具有共現(xiàn)關(guān)系,如果詞對的共現(xiàn)頻率越高,它們的關(guān)聯(lián)性越強.因此,詞項之間的顯式關(guān)系可以通過它們在所有文本(文本集)中的共現(xiàn)頻率進行估計.

定義1.(TPF-IDF)TPF是一對詞項出現(xiàn)在同一文本的次數(shù),IDF表示一對詞項至少出現(xiàn)一次的文本數(shù),TPF-IDF反映了成對詞項在語料庫中對一個文本的重要性.其加權(quán)方案計算公式如下:

TPF-IDF((ti,tj),d,D)=TPF((ti,tj),d)×IDF((ti,tj),D)

(1)

(2)

其中(ti,tj) 代表一對詞項,|D|是文本總數(shù),d是文本集D中一個單一的文本.

對于?(tk,ti)∈D(k,i∈[1,N],k≠i),可以得出:

(3)

表示詞對(tk,ti)在文本集D中的概率,TPF-IDF(tk,ti) 表示詞對(tk,ti)的TPF-IDF.

則所有詞對中給定詞語Ti的概率分布定義如下:

PIa(ti)=(PIa(t1|ti),PIa(t2|ti),
K,PIa(tk|ti),K,PIa(tN|ti))

(4)

定義2.(詞對內(nèi)部耦合)給定一個文本集D,(ti,tj)為文本集D中的詞對,則詞對(ti,tj)的內(nèi)部的耦合關(guān)系(IaR)表示如下:

IaR(ti,tj)=RS(PIa(ti),PIa(tj))

(5)

其中RS為關(guān)系強度函數(shù),本文選擇余弦相似度作為關(guān)系強度函數(shù)來計算詞對間的耦合關(guān)系.

2.2 圖的結(jié)構(gòu)特征

受到文獻[10]的啟發(fā),頂點的屬性不僅可以從外部數(shù)據(jù)獲得,還可以從圖的內(nèi)部結(jié)構(gòu)信息中獲得.基于結(jié)構(gòu)特征的相似度計算方法允許將圖的結(jié)構(gòu)信息(例如距離兩步的鄰居頂點的總和)直接建模到屬性中以提高性能.對于每個頂點,本文選擇了4個內(nèi)部屬性計算詞項間的相似度,詳見表1.

表1 文本圖結(jié)構(gòu)內(nèi)部屬性
Table 1 Internal properties of textual structure

屬性說明屬性1同配性(同配性=頂點的度鄰居頂點度的平均值)屬性2頂點的度屬性3距離2的鄰居頂點數(shù)屬性4距離3的鄰居頂點數(shù)

為了避免大數(shù)值,本文取所有內(nèi)部屬性的對數(shù)值.

3 融合語義與圖結(jié)構(gòu)的短文本特征提取算法

本文在語義耦合及圖結(jié)構(gòu)特征相結(jié)合的啟發(fā)下,提出了一種融合語義與圖結(jié)構(gòu)的短文本特征提取算法.如圖1所示.

圖1 融合語義與圖結(jié)構(gòu)的短文本特征提取算法總流程Fig.1 Short text feature extraction algorithm based on semantic and graph structure

首先進行文本預(yù)處理,包括分詞、詞性標注等;然后根據(jù)所有鄰邊規(guī)則構(gòu)建文本圖、根據(jù)詞性對文本圖的頂點權(quán)重進行初始化;接著利用詞語間內(nèi)部耦合及外部耦合關(guān)系以及文本圖的結(jié)構(gòu)特征計算詞語間的相似度作為文本圖中邊的權(quán)值;最后設(shè)計一種隨機游走方法將兩種邊的加權(quán)方法有效地綜合起來進行迭代提取出文本集的特征詞項排序結(jié)果.本方法不僅通過語義耦合充分捕獲文本詞語間表面的和潛在的語義信息,而且考慮到了文本圖的結(jié)構(gòu)特征,并將二者有效地結(jié)合起來,通過迭代計算得到詞語的排名情況.

3.1 文本圖構(gòu)建

在文本圖構(gòu)建過程中,一個標記對應(yīng)一個頂點,邊定義了標記之間的共現(xiàn)關(guān)系.給定一個標記集T來定義圖G=(V,E)的頂點和邊,其中V={t1,t2,…,tn}表示頂點集,E={e1,1,e2,2,…,ei,j}表示邊集.頂點分配是對屬性向量進行完整的讀取并為每個標記創(chuàng)建一個頂點的過程.本文中,文本圖的邊根據(jù)所有鄰邊[10]規(guī)則進行構(gòu)建:在一個任意大小的窗口中創(chuàng)建所有能夠連接標記的邊,即對于給定的某個窗口內(nèi)的每個標記間都需要創(chuàng)建一個邊.同時,這些標記的讀取順序跟它們出現(xiàn)在原始文本中的序列相同.

3.2 頂點權(quán)重初始化

構(gòu)建完文本圖之后,需要計算出頂點重要性的權(quán)值.SFESGS算法根據(jù)詞語詞性賦予初始權(quán)值.

一篇文本中,名詞和動詞構(gòu)成了它的核心,它們的簡單組合可以作為整個文本的簡單表示.另外,形容詞和副詞對文本內(nèi)容的表達也起到一定的作用.因此,名詞、動詞、形容詞和副詞被視作能表達文本內(nèi)容的內(nèi)容詞,其中名詞和動詞的權(quán)重大于形容詞和副詞的權(quán)重.詞性因子的量化公式如公式(6)所示:

(6)

即當詞語為名詞或者動詞時,則該詞初始權(quán)重為0.8;當詞語為形容詞或者副詞時,該詞的初始權(quán)重為0.6;當詞語為其他詞性時,該詞的初始權(quán)重為0.

3.3 文本圖中邊的權(quán)值計算

本文提出了兩種對邊的加權(quán)方法:基于語義耦合的詞項間相似度計算和基于結(jié)構(gòu)特征的詞項間相似度計算,計算得出的詞項間相似度即為兩頂點之間邊的權(quán)值.

3.3.1 基于語義耦合的相似度計算

假定一個文本集由邊和頂點組成的圖來反映詞語之間的關(guān)系,2.1節(jié)中介紹的詞對內(nèi)部耦合僅僅捕獲了圖中相鄰兩個頂點間的顯式關(guān)系,未考慮到全圖中其他詞語間的相互作用.因此,提出一種基于圖論的捕獲詞項間隱式關(guān)系的方法.

對于?(tk,ti)∈D(k,i∈[1,N],k≠i),有:

(7)

(8)

公式(7)體現(xiàn)了詞ti與詞tk的相似程度,距離越近,詞ti與詞tk之間越相似,pL(ti,tk)表示詞ti與詞tk之間的最短路徑.

對于給定的ti其概率分布如下:

PIe(ti)=(PIe(t1|ti),PIe(t2|ti),K,PIe(tk|ti),K,PIe(tN|ti))

(9)

前文中提到詞對(ti,tj)的內(nèi)部耦合關(guān)系(IaR)表示如下:

IaR(ti,tj)=RS(PIa(ti),PIa(tj))

(10)

其中RS為關(guān)系強度函數(shù),本文選擇余弦相似度作為關(guān)系強度函數(shù)來計算詞對間的耦合關(guān)系.

定義3.(詞對外部耦合)給定一個文本集D,在文本集D中的詞對(ti,tj)之間的外部耦合(IeR)表示如下:

IeR(ti,tj)=RS(PIe(ti),PIe(tj))

(11)

詞對間內(nèi)部耦合表征兩個詞在同一篇文本中的相關(guān)性大小,而詞對間外部耦合挖掘出兩個詞不在同一篇文本中出現(xiàn)但可能相關(guān)的特性.所以,通過綜合詞對間的內(nèi)部耦合和外部耦合,可以充分挖掘出詞語間全部的語義信息.文本集D中詞對(ti,tj)的語義耦合相似度計算見公式(12).

SCS(ti,tj)=(1-α)×IaR(ti,tj)+α×IeR(ti,tj)

(12)

其中,IaR(ti,tj)和IeR(ti,tj)分別表示詞對(ti,tj)的內(nèi)部耦合關(guān)系和外部耦合關(guān)系,α∈[0,1]是決定內(nèi)部耦合關(guān)系和外部耦合關(guān)系權(quán)重的參數(shù).本文α的取值設(shè)定為0.65.

SCS(ti,tj)的值在0-1之間,0表明兩個詞之間是完全沒有關(guān)系的,1表示兩個詞是完全一樣的,SCS(ti,tj)的值越高兩個詞之間的相似度越高.

3.3.2 基于圖結(jié)構(gòu)特征的相似度計算

基于結(jié)構(gòu)特征的相似度計算過程中,頂點(ti,tj)之間邊的權(quán)重用相應(yīng)頂點屬性(xi,xj)之間的相似度Sij來表示,Sij>0.

本文選擇徑向基核函數(shù)(RBF)作為頂點屬性之間的相似度定義:

(13)

其中正參數(shù)γ控制屬性距離的影響,RBF核函數(shù)相當于先從xi和xj投影的兩個無限維矢量的內(nèi)積φ(xi)Tφ(xj).因此Sij可以捕獲xi和xj之間的非線性相似性.

3.4 特征提取

本文提出的特征提取算法是設(shè)計一種隨機游走方法將3.3節(jié)中提到的兩種對邊的加權(quán)方法有效地綜合起來進行迭代計算,得到文本特征詞項集合排序的結(jié)果.

對于已經(jīng)構(gòu)建好的文本圖G,將頂點間的相似度作為頂點間邊的權(quán)重,利用語義耦合的方法計算頂點間的相似度得到圖G1,利用結(jié)構(gòu)特征的方法計算頂點間的相似度得到圖G2,分別計算圖G1和G2的轉(zhuǎn)移矩陣P和Q.由于圖G1和G2皆為無向圖,則將圖G1和G2中的邊(i,j)可以視為兩個有向邊(i,j)和(j,i),P和Q為L*L維的矩陣,其中P(i,j)為語義耦合計算得出的相似度,Q(i,j)為結(jié)構(gòu)特征計算得出的相似度.然后進行隨機游走迭代計算每個頂點的權(quán)值,權(quán)值的大小由高到低進行排序,取前k個作為文本集的特征詞項集合,則頂點權(quán)值計算公式為:

π(t+1)=(1-d)Qπ(t)+dPπ(t)

(14)

(15)

d表示阻尼系數(shù),一般取0.85,起到了平滑整個算法的作用,每一次頂點之間的跳轉(zhuǎn),都有d的概率按照頂點連接關(guān)系繼續(xù)跳轉(zhuǎn).

由于本文中圖中頂點被賦予了初始權(quán)重,因此π0=?′,?′為歸一化后的?.πt為迭代t次后的特征詞項權(quán)重向量.

4 實 驗

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

實驗數(shù)據(jù)分別選用了CSCD中的5類共2450篇文章標題作為中文數(shù)據(jù)集,CCF會議推薦列表中的A類會議與B類會議中的5類共2000篇文章標題,作為英文數(shù)據(jù)集進行實驗.

對數(shù)據(jù)集進行預(yù)處理,包括數(shù)據(jù)去噪、分詞、停用詞過濾、詞干提取、詞性標注等處理.其中,中文分詞和詞性標注是通過java調(diào)用中科院分詞系統(tǒng)(NLPIR)的函數(shù)來實現(xiàn),詞干提取采用經(jīng)典的波特算法.本文方法得出的結(jié)果以特征詞向量形式表示,且采用k-NN和SVM分類器對實驗結(jié)果進行分類驗證.

4.2 評價指標

本文選擇F值(F-measure)作為算法的評價指標:

(16)

(17)

其中Pr為精確率,Re為召回率,其計算公式如下:

(18)

(19)

其中,TP、TN、FP、FN分別為真正(事實上是正樣本,被判定為正樣本)、真負(事實上是正樣本,被判定為負樣本)、假正(事實上是負樣本,被判定為正樣本)、假負(事實上是負樣本,被判定為負樣本).

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

為了驗證本文提出方法的有效性,實驗主要從以下兩個方面進行首先比較本文方法與其他特征提取方法得到的特征詞集;然后,將不同方法提取出的特征詞集應(yīng)用到SVM和k-NN分類器中,得到不同算法對短文本分類的結(jié)果.

本文選擇只考慮語義耦合不考慮圖結(jié)構(gòu)特征的特征提取方法、只考慮圖結(jié)構(gòu)特征但不考慮語義耦合的特征提取方法以及TKG2|W1|cc[11]方法與本文方法得到的特征集合進行比較,驗證使用本文所提出的特征提取算法的有效性.

本文選擇以上三種方法作為本文方法的對比方法是基于以下考慮:

1)由于本文方法是通過融合詞對語義耦合關(guān)系以及文本圖結(jié)構(gòu)特征改進而來的,只考慮語義耦合不考慮圖結(jié)構(gòu)特征的特征提取方法與只考慮圖結(jié)構(gòu)特征但不考慮語義耦合的特征提取方法與本文方法最為相似;

2)TKG2|W1|cc方法也是一種基于圖的特征的提取算法,且本文方法構(gòu)建文本圖的規(guī)則與文獻[11]中TKG2方法的構(gòu)建規(guī)則相同.

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

為驗證得出的關(guān)鍵詞集對短文本分類的影響,本文分別取特征詞項集中的前30、60、100、110、130、160、180、200、230、250、280和300個特征詞項作為特征詞典,并分別利用SVM和k-NN分類器進行測試.SVM分類中采用線性核函數(shù)libsvm網(wǎng)格參數(shù)尋優(yōu)對訓練參數(shù)進行優(yōu)化,使模型更為契合.k-NN分類器訓練模型過程中,特征詞典大小一定時,近鄰數(shù)為80時得到的模型分類性能較好.

為了得出最適合本文的分類器,本文以中文數(shù)據(jù)集為例對分類器的效果進行比較.由圖2所示,本文方法得出的關(guān)鍵詞集在SVM和k-NN分類器兩種分類器上均可以對短文本進行有效分類且SVM分類器的分類效果更佳,與本文方法更為符合.隨著特征詞典長度逐漸增加,使用訓練出的模型進行分類,準確率和F-measure值先呈現(xiàn)增長趨勢后在特征詞典數(shù)目為200時達到峰值并趨于穩(wěn)定.使用k-NN分類器訓練出的模型分類,準確率和F-measure值呈現(xiàn)出先增長后下降的波動趨勢,在特征詞典數(shù)目為110時達到峰值.

圖2 特征詞典大小對短文本分類的影響Fig.2 Effect of feature dictionary size for short text classification

4.3.2 特征詞典對比

本文將4種特征提取方法得到的特征詞典在文本分類任務(wù)上進行對比,以此來驗證本文方法得到的特征詞典的準確性.以處理后的軟件工程和通信安全為例,選取前10個詞為例,如表2和表3給出了不同算法分別在中英文數(shù)據(jù)集上抽取出的特征詞項.可以看出,KEGS方法得到的特征詞典由于未考慮語義信息,效果較差,并不能代表短文本類別特征.KES方法和TKG2|W1|cc算法將詞項表示為文本圖形式但卻都忽略了文檔本身所攜帶的結(jié)構(gòu)屬性因素,得到的結(jié)果也有待提升.由此可以證明詞項之間的語義信息與詞語本身的屬性特征均不容忽視.顯然,本文算法充分考慮了詞語間的隱含語義并綜合考慮了文本圖自身的結(jié)構(gòu)特征,得到的結(jié)果相比之下更為合理.

表2 中文數(shù)據(jù)集上不同算法抽取出的特征詞項Table 2 Feature terms extracted by different algorithms on Chinese datasets

表3 英文數(shù)據(jù)集上不同算法抽取出的關(guān)鍵詞
Table 3 Keywords extracted by different algorithms on
English datasets

方法KESKEGS TKG2|W1|CcSKESGS1designtwo-jointactivityattack2networkimpacttopicprobabilistic3baseseminallyelasticcluster4optimalsubpixelopticallive5interactvisual inter-actfemtocellsensor6learnmechanicradioencrypt7datarepetitioncooperativemechanic8analyzetransmittalefficiencydevice9modelnotecomputerlayer10efficiencysphericalfirewallimpact

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

由4.3.1可知,本文方法在SVM分類器上分類效果優(yōu)于k-NN分類器且在特征詞典長度為200時分類準確率最高.故本文選取SVM分類器分別在中英文數(shù)據(jù)集上進行實驗,驗證特征詞項數(shù)目為200時不同方法對短文本分類的影響,其F-measure值如表4.

表4 不同特征提取算法的分類性能
Table 4 Classification performance of different feature extraction method

(a)中文數(shù)據(jù)集(b)英文數(shù)據(jù)集方法方法 F1-Measure方法 F1-MeasureKES0.6283KES0.4659KEGS0.5918KEGS0.3973TKG2|W1|Cc0.6297TKG2|W1|Cc0.4725SKESGS0.6594SKESGS0.6263

本文方法在中英文數(shù)據(jù)集上的分類F-measure值均大于其余3種方法,足以證明本文方法對短文本分類更為有效且適用于多種語言.由此可得,詞語之間的隱含語義和文本圖中其自身的結(jié)構(gòu)特征對短文本分類的影響較大,且使用本文方法得出的特征詞項也更為準確.

5 結(jié)束語

針對現(xiàn)有的短文本特征提取算法未充分考慮詞語之間的隱含語義以及圖的結(jié)構(gòu)特征,本文提出一種新的短文本特征提取算法,即融合語義與圖結(jié)構(gòu)的短文本特征提取算法.該方法利用詞語間的共現(xiàn)關(guān)系和詞語在文本集中距離來計算兩個詞語之間的語義相關(guān)度,解決了傳統(tǒng)短文本特征提取算法忽略詞語間內(nèi)在語義關(guān)聯(lián)的問題,并結(jié)合圖的結(jié)構(gòu)特征,使詞語間的相關(guān)度更為貼切.最后,分別在中、英文數(shù)據(jù)集上實驗,證明該方法提取出的特征詞項能對短文本實現(xiàn)有效地分類.