基于詞性特征的特征權重計算方法①

胡雯雯,高俊波,施志偉,劉志遠

(上海海事大學 信息工程學院,上海 201306)

1 引言

面對大規模短文本形式的數據,快速并準確地獲取所需的關鍵信息以及提高聚類的效率、準確率一直都是人們關注的重點.但短文本固有的特點,使得傳統的特征權重計算方法無法準確計算.因此,學者們采用不同的方法去解決這一缺陷,總體分為三個方面,一用特征子集評價方法從特征空間上改進,包括信息增益[1]、卡方檢驗(CHI-sqare,CHI)[2]、期望交叉熵(Expected Cross Entropy,ECE)[3]等,這些評價算法在給定閾值的情況下,通過計算文本集中每個特征項的權重值,選擇特征項的權重值大于閾值的特征加入特征子集或選擇權重值最大的特征項子集直到滿足特征子集大小閾值.例如李凱齊,刁興春等[4]提出一種改進的特征權重計算方法,通過引入信息論中信息增益的概念,實現對短文本特征分布具體維度的綜合考慮,克服傳統公式存在的不足.實驗結果表明,改進后的特征權重計算算法在計算特征權重時更加有效.二在搜索空間策略上進行改進,包括順序選擇算法、遺傳算法、粒子群算法等,這些算法通過搜索疊加的方式在實現特征空間降維的同時提高算法自身的準確率.例如杜坤,劉懷亮等[5]考慮特征項間的語義關聯構造復雜網絡并進行特征選擇,定義類別相關系數并結合特征選擇結果,提出一種改進的特征權重計算方法,并進行中文文本分類實驗.實驗結果表明,改進后的算法較TFIDF算法有更好的分類效果.三從特征屬性上進行改進,包括詞頻[6]、特征在文本中的位置[7]、詞共現分析等,以上特征屬性作為影響因子加入實驗中.例如李欣蓬等[8],提出雙維度特征關系和特征位置對類別學習的影響,實驗結果反映了詞性對于特征權重的積極影響.

多種實驗表明從特征屬性上改進特征權重要優于其他兩種方法[9-11].其中于海燕等[12]提出一種基于詞性嵌入的特征權重計算方法,從詞性對情感分類的貢獻度嵌入到 TF-IDF 算法中.Gang Wang,Zhu Zhang 等[13]提出基于詞性情緒分類的PSO-RS算法,實驗表明POS-RS情緒分類可以作為一個可行的方法,有可能被成功地應用于其他文本分類問題.這些研究表明詞性對于特征權重上的改進能夠提高后續驗證實驗的準確率,對于本文的研究有重大意義.本文從詞性屬性出發,提出一種新的基于詞性特征的特征權重計算算法(Translation Decision Model Of Quantum-behaved Particle Swarm Optimization,TDQO).在特征選擇階段中將詞性引入到翻譯決策模型(Translation Decision Model,TD)中,以改進后的TDQO算法對聚類的效率與準確性進行改善.

2 傳統的特征權重計算方法

傳統的特征權重計算方法有很多,例如TF算法、TF-IDF算法、PageRank算法等等.其中TF算法僅從文本詞頻的角度考慮,一方面考慮到了高詞頻所帶來的高權重,另一方面卻暴露其大量無意義詞所產生的高冗余、高復雜度等缺點.另外PageRank算法是根據網頁中的超鏈接鏈入的網頁數來判斷某個網頁是否重要.本文語料為文本數據,為了使初始化的特征權重有較好的可信度,本文在計算初始權重計算方法上選擇TF-IDF算法.

2.1 TF-IDF算法

TF-IDF算法在計算特征權重時考慮三點:詞頻(tf)、反文檔頻率(idf)以及歸一化(normalization).其中詞頻tf表示特征在該文檔中出現的頻率;反文檔頻率表示特征在各個文檔中的區分能力;歸一化(normalization)用來防止偏向長文檔.考慮三個條件,TF-IDF公式可以表示如下:

其中tf(tk,di)表示特征tk在文檔di中出現的頻率.N表示為文檔總數.m表示文檔中的特征數.nk表示包含特征tk的文檔數.

2.2 TF-IDF算法的缺陷

TFIDF認為一個特征出現的文檔頻率越小,則區分類別文檔的能力越大.逆文本頻度IDF在一定程度上抑制無意義特征,但在另一方面重要特征的凸顯也造成無意義標注.而TFIDF的計算為IDF對于TF的權重調整,IDF本身無法有效區分重要特征及無意義特征分布,使得TFIDF計算特征權重的精度并不是很高.

舉例說明該算法的不足.假設總文檔量為100篇.在 2000 特征詞的文檔中“親情”,“友情”,“的”,“魅力”分別出現 30,90,100,5 次,“親情”出現在 20 篇文檔中,“友情”出現在90篇文檔中,“的”出現在100篇文檔中,“魅力”出現在 5 篇文檔中.在其 TF,IDF,TF-IDF 數據如表1.

從表1可以分析出“友情”與“的”權重最低,但是卻表示兩個極端,“的”對于特征來說是無意義的特征,只會增加特征冗余,而“友情”卻是每篇文檔的主題詞,經文本聚類可以將文檔歸為一類.由此可見TF-IDF算法在特征的重要程度上無法準確判斷.

表1 特征在 TF,IDF,TF-IDF 上的表現

3 TDQO 特征權重改進算法

TDQO算法在TF-IDF算法的基礎上引入詞性加權權重(TDF)以及特征詞作為某種詞性出現概率(PF),由此改進TF-IDF算法.其中TDF加權了詞性特征權重,例如在文本中名詞相對于動詞、形容詞更能代表一篇文檔的主題特征,對于詞性加權有效權衡了詞性所帶來的權重影響.而PF有效抑制大量某一種詞性權重影響.

3.1 詞性加權權重

詞性加權公式如下:

其中n為特征作為粒子的總群數,xi表示第i個特征粒子,j={1,2,3}表示某種詞性.

3.2 特征作為某種詞性概率

特征詞為某種詞性概率公式如下:

其中tj表示特征t出現的詞性特征.

3.3 TDQO算法

大多數的短文本在文本預處理階段,通過詞性篩選,保留下所需要的詞性,李英[14]提出基于詞性的特征預處理方法,在文本預處理環節過濾掉副詞、嘆詞等貢獻度很小的詞性,只保留對分類貢獻較大的名詞、動詞、縮略詞等,實驗證明這一方法有效的降低了文本空間的特征維度.特征權重計算為特征空間中的文本向量的每一維確定合適的數值,以表達對應特征在文本的重要程度.特征ti在文本di中的權重表示為wi,j=w(ti,di),文本di的權重向量表示為wj=w(dj).

在特征選擇算法之后進行詞性篩選,只保留名詞、動詞、形容詞.一方面更好地通過詞性將詞頻中較高的干擾詞性過濾掉,另一方面可以通過觀察哪些詞性的詞本身雖不具有特征屬性,但對權重產生影響,比如標題中一些權重較高的詞.

本文在不同詞性上進行不同程度的加權,得出一種基于詞性的權重計算方法公式如下:

其中PF*TDF表示為特征t在改進后的量子粒子群優化算法的最優詞性加權總值.

3.3.1 TDQO 算法流程

TDQO算法在量子粒子群算法的基礎上引入TD模型,它的范圍搜索能力極大高于一般QPSO算法.以下介紹TDQO算法具體實現過程.

(1)初始化粒子速度與位置.圖1模塊①為TDF的計算通過迭代不斷判斷局部極值pBest和全局極值gBest[15]來更新自己的速度及位置,最終找到最優解.粒子根據公式(5)(6)來優化自己的速度和位置,公式(7)為詞性加權權重,即TDF.

其中,i表示第i個粒子,j為粒子的第i維,t為進化代數,C1,C2為加速方向常數,r1,r2為[0,1]上均勻分布的隨機數.

(2)以 (0,1)隨機函數賦值Xi,并將其作為初始特征權重,Vi=2.0,初始化每個粒子,使用 k-means 聚類算法,計算聚類準確率作為粒子的適應度值.粒子在迭代過程中,當前位置的適應度值大于局部或全局最優解的適應度值,則更新為粒子當前位置,否則繼續迭代,最終輸出計算的詞性加權權重.

(3)建立翻譯決策模型,將每個特征作為粒子,并標注詞性及對應的布爾值.圖1模塊②中TDQO算法中建立的TD模型是最大熵[16]模型的分支模型,也是PF計算的過程.其中TD模型函數的建立用來計算PF值,即特征作為某種詞性出現概率.其公式如下:

其中λi初始化為 0,fi(x,y)表示定義的特征函數,x表示特征,y表示對應詞性.

(4)計算當前模型分布期望,計算最優估計,最終得到粒子作為詞性權重的加權權重.

TDQO算法流程圖如圖1.

4 實驗與分析

使用爬蟲工具在豆瓣小說上獲取22篇小說書評,共計 24 450 條評論.經預處理剩有 17 765 個詞,通過TF-IDF計算初始權重,并設置閾值為0.01,過濾大量冗余特征.此時剩有2215個詞作為后續對比實驗的初始特征集,根據建模需要,需再次對詞性進行降維,只保留名詞、動詞、形容詞,最終特征選擇的詞剩有1816個.

為了驗證詞性對文本的貢獻度有助于提高聚類的準確率,本文通過TF-IDF算法、QPSO算法、TDQO算法進行對比實驗.其中TF-IDF方法得到特征向量并直接進行聚類輸出;QPSO算法中不標記詞性,通過粒子迭代得到最優加權權重,其中粒子個數為39 952個,迭代次數為100次,得到未加權詞性的特征權重,進而進行聚類輸出;TDQO算法實驗在QPSO算法實驗的基礎上,引入TD模型,加權計算特征作為某種詞性出現的概率并聚類輸出.實驗環境為Windows 8 操作系統,2 GB 內存,利用 MATLAB 及 PYTHON 開發.

圖1 TDQO 算法流程圖

輸入:TF-IDF算法權重數據標記粒子詞性,粒子總數輸出:改進后的特征權重加權,改進前后的F值(1)使用中國科學院計算技術研究所ICTCLAS2014分詞器對原始語料進行分詞處理;(2)使用TF-IDF算法對詞頻進行排序,選取詞頻在0.01以上的詞作為新的特征集;此處是避免大量的非有效特征增加特征冗余;(3)對新的特征集進行詞性篩選,只保留名詞、動詞、形容詞;(4)引入TD模型的量子粒子群優化算法.通過TD模型建模函數得到特征作為詞性出現的概率加權到粒子迭代中,當前位置的適應度值大于局部或全局最優解的適應度值,則更新為粒子當前位置,否則繼續迭代,最終輸出計算的詞性最優加權權重;(5)將得到的加權后的數據經k-means聚類,通過修改k值,在不同類別中使用三種方法進行實驗并得出結論.

4.1 實驗數據分析

為驗證提出方法的有效性,將TF-IDF算法、QPSO算法及TDQO算法三種方法進行聚類實驗,以檢驗它們在文本挖掘中的表現.實驗采用聚類領域常用的F-measure作為指標來評價文檔聚類方法的效果.

F-measure[17]是一種結合了precision和recall的聚類評價指標.F-measure 的取值范圍為[0,1].對應的檢索粒子分布表如表2.

表2 檢測粒子分布

在翻譯決策模型建模中,將特征轉化成隨機粒子.根據文檔粒子采用分散規則賦值,轉化的粒子共39952個,與之相對應產生39952個初始權重,相同的特征在分散文檔中的權重也會有所不同,因而在建模過程中,特征用集中的權重表示,并用TRUE和FALSE 標注.TRUE 的情況以二進制 1 代表,FALSE的情況以二進制0代表,粒子詞性特征以三維向量表示,并轉化成相應十進制,取值為 rand(2,4,6),同時量子粒子群算法仍然使用分散初始權重生成向量作為輸入.初始化粒子速度與位置同步進行,設置位置xi=(0,1),速度vi=2.0,迭代次數 MAXGEN=100,加速常數C1,C2均為2.0.

為了驗證在引入翻譯決策模型的量子粒子群優化算法對聚類的準確度,將三種方法計算出特征權重構造特征向量,并進行聚類上的評價比較.其中聚類類別k=[3,7],實驗數據 recall值及 F 值上的比較如表3、表4所示.

表3 三種權重計算方法在聚類上 recall比較

表3、表4中的3種實驗算法在聚類指標recall值及F-measure值上均表現出無論k取何值,TDQO算法始終要優于前兩種算法.

根據評價標準F值繪制成折線圖如圖2所示.

表4 三種權重計算方法在聚類上 F-measure 比較

圖2 三種權重計算方法在F值走勢圖

從圖2折線趨勢圖可以明顯看出,使用QPSO算法提高了聚類準確率,而本文提出的TDQO算法更加有效地提高了聚類準確率.當類別越大或越小時,QPSO算法準確率雖然與TF-IDF算法準確率很接近,但是整體準確率有所提高;當聚類類別數為5時,準確率提高最大(7.85%).TDQO算法在各個類別上的準確率均大大高于QPSO算法的準確率,這證明了不同的詞性對于文本聚類的貢獻度是有影響的.從整體上來看,當聚類類別從3開始,聚類效果呈上升趨勢,當類別數超過5 時,普遍的呈下降趨勢.所以聚類k值為 5 時,聚類準確率達到最高.

此時,將k設定5作為不變量,測試用三種不同方法在不同特征維度中的聚類效果.具體實驗數據如圖3-圖5所示.

圖3 TF-IDF 算法在各維度上聚類效果

從圖3和圖4可以看出共同點:在低特征維度上聚類分布改善不明顯,在高特征維度上,聚類分布效果較好.區別在于 TF-IDF 算法在[1500,1800]高維度區間上的聚類效果要好于QPSO算法,而QPSO算法在[600,1000]區間上展現了較好的聚類效果.

從圖5得出結論:隨著特征維數的增大,聚類分布顯著.與圖3和圖4比較來看,TDQO算法在[200,1800]區間的聚類分布依然表現出良好的聚類效果.本文提出的TDQO算法一方面提高聚類準確率,另一方面在不同特征維度也展現了較好的聚類效果,同時具有更廣泛的應用范圍.

圖4 QPSO 算法在各維度上聚類效果

圖5 TDQO 算法在各維度上聚類效果

5 結束語

目前短文本在特征權重計算的方法上很大程度上仍按照長文本的特征計算方法,然而短文本在特征屬性上更具有貢獻度,傳統的方法會降低其準確率.本文在現有的特征權重計算方法的基礎上,提出了TDQO算法[18].該算法引入某種詞性作為特征出現時的概率,并將粒子作為特征在迭代中尋找最優權重配比.實驗表明該算法在聚類中準確率有所提高,因此也證明了詞性權重對于聚類結果是有影響的.另外,對于聚類類別k值的選取也會對實驗結果有所影響.對于本文的算法依然還存在改進的地方,可以在實驗的不同環節或者算法內部提高效率.

1 Reineking T.Active classification using belief functions and information gain maximization. International Journal of Approximate Reasoning,2016,(72):43 –54.[doi:10.1016/j.ijar.2015.12.005]

2 Rempala GA,Wesolowski J.Double asymptotics for the chisquare statistic.Statistics &Probability Letters,2016,(119):317–325.

3 Zhong RX,Fu KY,Sumalee A,et al.A cross-entropy method and probabilistic sensitivity analysis framework for calibrating microscopic traffic models. Transportation Research Part C:Emerging Technologies,2016,(63):147 –169.[doi:10.1016/j.trc.2015.12.006]

4 李凱齊,刁興春,曹建軍.基于信息增益的文本特征權重改進算法.計算機工程,2011,37(1):16–18.

5 杜坤,劉懷亮,郭路杰.結合復雜網絡的特征權重改進算法研究.現代圖書情報技術,2015,31(11):26–32.[doi:10.11925/infotech.1003-3513.2015.11.05]

6 lbrahim A,Cowell PE,Varley RA.Word frequency predicts translation asymmetry.Journal of Memory and Language,2017,(95):49–67.[doi:10.1016/j.jml.2017.02.001]

7 Kao CY.The effects of stimulus words ’ positions and properties on response words and creativity performance in the tasks of analogical sentence completion.Learning and Individual Differences,2016,(50):114–121.[doi:10.1016/j.lindif.2016.07.015]

8 李欣蓬.雙維度特征關系和特征位置對類別學習的影響[碩士學位論文].天津:天津師范大學,2009.

9 黃文濤,徐凌宇,李嚴,等.基于柔性區間的多文本融合提取方法.計算機工程,2007,33(24):217–219.[doi:10.3969/j.issn.1000-3428.2007.24.076]

10 吳光遠,何丕廉,曹桂宏,等.基于向量空間模型的詞共現研究及其在文本分類中的應用.計算機應用,2003,23(S1):138–140.

11 許建潮,胡明.中文Web文本的特征獲取與分類.計算機工程,2005,31(8):24–25,39.

12 于海燕,陸慧娟,鄭文斌.情感分類中基于詞性嵌入的特征權重計算方法.計算機工程與應用,2016,53(22):121–125.

13 Wang G,Zhang Z,Sun JS,et al.POS-RS:A random subspace method for sentiment classification based on partof-speech analysis.Information Processing &Management,2015,51(4):458–479.

14 李英.基于詞性選擇的文本預處理方法研究.情報科學,2009,27(5):717–719,738.

15 Sun J,Xu WB,Feng B.A global search strategy of quantumbehaved particle swarm optimization.Proceedings of 2004 IEEE Conference on Cybernetics and Intelligent Systems.Singapore,Singapore.2004.111–115.

16 Li R,Tao X,Tang L,et al.Using maximum entropy model for Chinese text categorization. Journal of Computer Research &Development,2005,42(1):578–587.

17 常鵬,馬輝.高效的短文本主題詞抽取方法.計算機工程與應用,2011,47(20):126–128,154.[doi:10.3778/j.issn.1002-8331.2011.20.036]

18 奚茂龍,盛歆漪,孫俊.基于多維問題的交叉算子量子粒子群優化算法.計算機應用,2015,35(3):680–684.[doi:10.11772/j.issn.1001-9081.2015.03.680]