胡雯雯,高俊波,施志偉,劉志遠(yuǎn)
(上海海事大學(xué) 信息工程學(xué)院,上海 201306)
面對(duì)大規(guī)模短文本形式的數(shù)據(jù),快速并準(zhǔn)確地獲取所需的關(guān)鍵信息以及提高聚類的效率、準(zhǔn)確率一直都是人們關(guān)注的重點(diǎn).但短文本固有的特點(diǎn),使得傳統(tǒng)的特征權(quán)重計(jì)算方法無(wú)法準(zhǔn)確計(jì)算.因此,學(xué)者們采用不同的方法去解決這一缺陷,總體分為三個(gè)方面,一用特征子集評(píng)價(jià)方法從特征空間上改進(jìn),包括信息增益[1]、卡方檢驗(yàn)(CHI-sqare,CHI)[2]、期望交叉熵(Expected Cross Entropy,ECE)[3]等,這些評(píng)價(jià)算法在給定閾值的情況下,通過(guò)計(jì)算文本集中每個(gè)特征項(xiàng)的權(quán)重值,選擇特征項(xiàng)的權(quán)重值大于閾值的特征加入特征子集或選擇權(quán)重值最大的特征項(xiàng)子集直到滿足特征子集大小閾值.例如李凱齊,刁興春等[4]提出一種改進(jìn)的特征權(quán)重計(jì)算方法,通過(guò)引入信息論中信息增益的概念,實(shí)現(xiàn)對(duì)短文本特征分布具體維度的綜合考慮,克服傳統(tǒng)公式存在的不足.實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的特征權(quán)重計(jì)算算法在計(jì)算特征權(quán)重時(shí)更加有效.二在搜索空間策略上進(jìn)行改進(jìn),包括順序選擇算法、遺傳算法、粒子群算法等,這些算法通過(guò)搜索疊加的方式在實(shí)現(xiàn)特征空間降維的同時(shí)提高算法自身的準(zhǔn)確率.例如杜坤,劉懷亮等[5]考慮特征項(xiàng)間的語(yǔ)義關(guān)聯(lián)構(gòu)造復(fù)雜網(wǎng)絡(luò)并進(jìn)行特征選擇,定義類別相關(guān)系數(shù)并結(jié)合特征選擇結(jié)果,提出一種改進(jìn)的特征權(quán)重計(jì)算方法,并進(jìn)行中文文本分類實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的算法較TFIDF算法有更好的分類效果.三從特征屬性上進(jìn)行改進(jìn),包括詞頻[6]、特征在文本中的位置[7]、詞共現(xiàn)分析等,以上特征屬性作為影響因子加入實(shí)驗(yàn)中.例如李欣蓬等[8],提出雙維度特征關(guān)系和特征位置對(duì)類別學(xué)習(xí)的影響,實(shí)驗(yàn)結(jié)果反映了詞性對(duì)于特征權(quán)重的積極影響.
多種實(shí)驗(yàn)表明從特征屬性上改進(jìn)特征權(quán)重要優(yōu)于其他兩種方法[9-11].其中于海燕等[12]提出一種基于詞性嵌入的特征權(quán)重計(jì)算方法,從詞性對(duì)情感分類的貢獻(xiàn)度嵌入到 TF-IDF 算法中.Gang Wang,Zhu Zhang 等[13]提出基于詞性情緒分類的PSO-RS算法,實(shí)驗(yàn)表明POS-RS情緒分類可以作為一個(gè)可行的方法,有可能被成功地應(yīng)用于其他文本分類問題.這些研究表明詞性對(duì)于特征權(quán)重上的改進(jìn)能夠提高后續(xù)驗(yàn)證實(shí)驗(yàn)的準(zhǔn)確率,對(duì)于本文的研究有重大意義.本文從詞性屬性出發(fā),提出一種新的基于詞性特征的特征權(quán)重計(jì)算算法(Translation Decision Model Of Quantum-behaved Particle Swarm Optimization,TDQO).在特征選擇階段中將詞性引入到翻譯決策模型(Translation Decision Model,TD)中,以改進(jìn)后的TDQO算法對(duì)聚類的效率與準(zhǔn)確性進(jìn)行改善.
傳統(tǒng)的特征權(quán)重計(jì)算方法有很多,例如TF算法、TF-IDF算法、PageRank算法等等.其中TF算法僅從文本詞頻的角度考慮,一方面考慮到了高詞頻所帶來(lái)的高權(quán)重,另一方面卻暴露其大量無(wú)意義詞所產(chǎn)生的高冗余、高復(fù)雜度等缺點(diǎn).另外PageRank算法是根據(jù)網(wǎng)頁(yè)中的超鏈接鏈入的網(wǎng)頁(yè)數(shù)來(lái)判斷某個(gè)網(wǎng)頁(yè)是否重要.本文語(yǔ)料為文本數(shù)據(jù),為了使初始化的特征權(quán)重有較好的可信度,本文在計(jì)算初始權(quán)重計(jì)算方法上選擇TF-IDF算法.
TF-IDF算法在計(jì)算特征權(quán)重時(shí)考慮三點(diǎn):詞頻(tf)、反文檔頻率(idf)以及歸一化(normalization).其中詞頻tf表示特征在該文檔中出現(xiàn)的頻率;反文檔頻率表示特征在各個(gè)文檔中的區(qū)分能力;歸一化(normalization)用來(lái)防止偏向長(zhǎng)文檔.考慮三個(gè)條件,TF-IDF公式可以表示如下:
其中tf(tk,di)表示特征tk在文檔di中出現(xiàn)的頻率.N表示為文檔總數(shù).m表示文檔中的特征數(shù).nk表示包含特征tk的文檔數(shù).
TFIDF認(rèn)為一個(gè)特征出現(xiàn)的文檔頻率越小,則區(qū)分類別文檔的能力越大.逆文本頻度IDF在一定程度上抑制無(wú)意義特征,但在另一方面重要特征的凸顯也造成無(wú)意義標(biāo)注.而TFIDF的計(jì)算為IDF對(duì)于TF的權(quán)重調(diào)整,IDF本身無(wú)法有效區(qū)分重要特征及無(wú)意義特征分布,使得TFIDF計(jì)算特征權(quán)重的精度并不是很高.
舉例說(shuō)明該算法的不足.假設(shè)總文檔量為100篇.在 2000 特征詞的文檔中“親情”,“友情”,“的”,“魅力”分別出現(xiàn) 30,90,100,5 次,“親情”出現(xiàn)在 20 篇文檔中,“友情”出現(xiàn)在90篇文檔中,“的”出現(xiàn)在100篇文檔中,“魅力”出現(xiàn)在 5 篇文檔中.在其 TF,IDF,TF-IDF 數(shù)據(jù)如表1.
從表1可以分析出“友情”與“的”權(quán)重最低,但是卻表示兩個(gè)極端,“的”對(duì)于特征來(lái)說(shuō)是無(wú)意義的特征,只會(huì)增加特征冗余,而“友情”卻是每篇文檔的主題詞,經(jīng)文本聚類可以將文檔歸為一類.由此可見TF-IDF算法在特征的重要程度上無(wú)法準(zhǔn)確判斷.
表1 特征在 TF,IDF,TF-IDF 上的表現(xiàn)
TDQO算法在TF-IDF算法的基礎(chǔ)上引入詞性加權(quán)權(quán)重(TDF)以及特征詞作為某種詞性出現(xiàn)概率(PF),由此改進(jìn)TF-IDF算法.其中TDF加權(quán)了詞性特征權(quán)重,例如在文本中名詞相對(duì)于動(dòng)詞、形容詞更能代表一篇文檔的主題特征,對(duì)于詞性加權(quán)有效權(quán)衡了詞性所帶來(lái)的權(quán)重影響.而PF有效抑制大量某一種詞性權(quán)重影響.
詞性加權(quán)公式如下:
其中n為特征作為粒子的總?cè)簲?shù),xi表示第i個(gè)特征粒子,j={1,2,3}表示某種詞性.
特征詞為某種詞性概率公式如下:
其中tj表示特征t出現(xiàn)的詞性特征.
大多數(shù)的短文本在文本預(yù)處理階段,通過(guò)詞性篩選,保留下所需要的詞性,李英[14]提出基于詞性的特征預(yù)處理方法,在文本預(yù)處理環(huán)節(jié)過(guò)濾掉副詞、嘆詞等貢獻(xiàn)度很小的詞性,只保留對(duì)分類貢獻(xiàn)較大的名詞、動(dòng)詞、縮略詞等,實(shí)驗(yàn)證明這一方法有效的降低了文本空間的特征維度.特征權(quán)重計(jì)算為特征空間中的文本向量的每一維確定合適的數(shù)值,以表達(dá)對(duì)應(yīng)特征在文本的重要程度.特征ti在文本di中的權(quán)重表示為wi,j=w(ti,di),文本di的權(quán)重向量表示為wj=w(dj).
在特征選擇算法之后進(jìn)行詞性篩選,只保留名詞、動(dòng)詞、形容詞.一方面更好地通過(guò)詞性將詞頻中較高的干擾詞性過(guò)濾掉,另一方面可以通過(guò)觀察哪些詞性的詞本身雖不具有特征屬性,但對(duì)權(quán)重產(chǎn)生影響,比如標(biāo)題中一些權(quán)重較高的詞.
本文在不同詞性上進(jìn)行不同程度的加權(quán),得出一種基于詞性的權(quán)重計(jì)算方法公式如下:
其中PF*TDF表示為特征t在改進(jìn)后的量子粒子群優(yōu)化算法的最優(yōu)詞性加權(quán)總值.
TDQO算法在量子粒子群算法的基礎(chǔ)上引入TD模型,它的范圍搜索能力極大高于一般QPSO算法.以下介紹TDQO算法具體實(shí)現(xiàn)過(guò)程.
(1)初始化粒子速度與位置.圖1模塊①為TDF的計(jì)算通過(guò)迭代不斷判斷局部極值pBest和全局極值gBest[15]來(lái)更新自己的速度及位置,最終找到最優(yōu)解.粒子根據(jù)公式(5)(6)來(lái)優(yōu)化自己的速度和位置,公式(7)為詞性加權(quán)權(quán)重,即TDF.
其中,i表示第i個(gè)粒子,j為粒子的第i維,t為進(jìn)化代數(shù),C1,C2為加速方向常數(shù),r1,r2為[0,1]上均勻分布的隨機(jī)數(shù).
(2)以 (0,1)隨機(jī)函數(shù)賦值Xi,并將其作為初始特征權(quán)重,Vi=2.0,初始化每個(gè)粒子,使用 k-means 聚類算法,計(jì)算聚類準(zhǔn)確率作為粒子的適應(yīng)度值.粒子在迭代過(guò)程中,當(dāng)前位置的適應(yīng)度值大于局部或全局最優(yōu)解的適應(yīng)度值,則更新為粒子當(dāng)前位置,否則繼續(xù)迭代,最終輸出計(jì)算的詞性加權(quán)權(quán)重.
(3)建立翻譯決策模型,將每個(gè)特征作為粒子,并標(biāo)注詞性及對(duì)應(yīng)的布爾值.圖1模塊②中TDQO算法中建立的TD模型是最大熵[16]模型的分支模型,也是PF計(jì)算的過(guò)程.其中TD模型函數(shù)的建立用來(lái)計(jì)算PF值,即特征作為某種詞性出現(xiàn)概率.其公式如下:
其中λi初始化為 0,fi(x,y)表示定義的特征函數(shù),x表示特征,y表示對(duì)應(yīng)詞性.
(4)計(jì)算當(dāng)前模型分布期望,計(jì)算最優(yōu)估計(jì),最終得到粒子作為詞性權(quán)重的加權(quán)權(quán)重.
TDQO算法流程圖如圖1.
使用爬蟲工具在豆瓣小說(shuō)上獲取22篇小說(shuō)書評(píng),共計(jì) 24 450 條評(píng)論.經(jīng)預(yù)處理剩有 17 765 個(gè)詞,通過(guò)TF-IDF計(jì)算初始權(quán)重,并設(shè)置閾值為0.01,過(guò)濾大量冗余特征.此時(shí)剩有2215個(gè)詞作為后續(xù)對(duì)比實(shí)驗(yàn)的初始特征集,根據(jù)建模需要,需再次對(duì)詞性進(jìn)行降維,只保留名詞、動(dòng)詞、形容詞,最終特征選擇的詞剩有1816個(gè).
為了驗(yàn)證詞性對(duì)文本的貢獻(xiàn)度有助于提高聚類的準(zhǔn)確率,本文通過(guò)TF-IDF算法、QPSO算法、TDQO算法進(jìn)行對(duì)比實(shí)驗(yàn).其中TF-IDF方法得到特征向量并直接進(jìn)行聚類輸出;QPSO算法中不標(biāo)記詞性,通過(guò)粒子迭代得到最優(yōu)加權(quán)權(quán)重,其中粒子個(gè)數(shù)為39 952個(gè),迭代次數(shù)為100次,得到未加權(quán)詞性的特征權(quán)重,進(jìn)而進(jìn)行聚類輸出;TDQO算法實(shí)驗(yàn)在QPSO算法實(shí)驗(yàn)的基礎(chǔ)上,引入TD模型,加權(quán)計(jì)算特征作為某種詞性出現(xiàn)的概率并聚類輸出.實(shí)驗(yàn)環(huán)境為Windows 8 操作系統(tǒng),2 GB 內(nèi)存,利用 MATLAB 及 PYTHON 開發(fā).
圖1 TDQO 算法流程圖
輸入:TF-IDF算法權(quán)重?cái)?shù)據(jù)標(biāo)記粒子詞性,粒子總數(shù)輸出:改進(jìn)后的特征權(quán)重加權(quán),改進(jìn)前后的F值(1)使用中國(guó)科學(xué)院計(jì)算技術(shù)研究所ICTCLAS2014分詞器對(duì)原始語(yǔ)料進(jìn)行分詞處理;(2)使用TF-IDF算法對(duì)詞頻進(jìn)行排序,選取詞頻在0.01以上的詞作為新的特征集;此處是避免大量的非有效特征增加特征冗余;(3)對(duì)新的特征集進(jìn)行詞性篩選,只保留名詞、動(dòng)詞、形容詞;(4)引入TD模型的量子粒子群優(yōu)化算法.通過(guò)TD模型建模函數(shù)得到特征作為詞性出現(xiàn)的概率加權(quán)到粒子迭代中,當(dāng)前位置的適應(yīng)度值大于局部或全局最優(yōu)解的適應(yīng)度值,則更新為粒子當(dāng)前位置,否則繼續(xù)迭代,最終輸出計(jì)算的詞性最優(yōu)加權(quán)權(quán)重;(5)將得到的加權(quán)后的數(shù)據(jù)經(jīng)k-means聚類,通過(guò)修改k值,在不同類別中使用三種方法進(jìn)行實(shí)驗(yàn)并得出結(jié)論.
為驗(yàn)證提出方法的有效性,將TF-IDF算法、QPSO算法及TDQO算法三種方法進(jìn)行聚類實(shí)驗(yàn),以檢驗(yàn)它們?cè)谖谋就诰蛑械谋憩F(xiàn).實(shí)驗(yàn)采用聚類領(lǐng)域常用的F-measure作為指標(biāo)來(lái)評(píng)價(jià)文檔聚類方法的效果.
F-measure[17]是一種結(jié)合了precision和recall的聚類評(píng)價(jià)指標(biāo).F-measure 的取值范圍為[0,1].對(duì)應(yīng)的檢索粒子分布表如表2.
表2 檢測(cè)粒子分布
在翻譯決策模型建模中,將特征轉(zhuǎn)化成隨機(jī)粒子.根據(jù)文檔粒子采用分散規(guī)則賦值,轉(zhuǎn)化的粒子共39952個(gè),與之相對(duì)應(yīng)產(chǎn)生39952個(gè)初始權(quán)重,相同的特征在分散文檔中的權(quán)重也會(huì)有所不同,因而在建模過(guò)程中,特征用集中的權(quán)重表示,并用TRUE和FALSE 標(biāo)注.TRUE 的情況以二進(jìn)制 1 代表,FALSE的情況以二進(jìn)制0代表,粒子詞性特征以三維向量表示,并轉(zhuǎn)化成相應(yīng)十進(jìn)制,取值為 rand(2,4,6),同時(shí)量子粒子群算法仍然使用分散初始權(quán)重生成向量作為輸入.初始化粒子速度與位置同步進(jìn)行,設(shè)置位置xi=(0,1),速度vi=2.0,迭代次數(shù) MAXGEN=100,加速常數(shù)C1,C2均為2.0.
為了驗(yàn)證在引入翻譯決策模型的量子粒子群優(yōu)化算法對(duì)聚類的準(zhǔn)確度,將三種方法計(jì)算出特征權(quán)重構(gòu)造特征向量,并進(jìn)行聚類上的評(píng)價(jià)比較.其中聚類類別k=[3,7],實(shí)驗(yàn)數(shù)據(jù) recall值及 F 值上的比較如表3、表4所示.
表3 三種權(quán)重計(jì)算方法在聚類上 recall比較
表3、表4中的3種實(shí)驗(yàn)算法在聚類指標(biāo)recall值及F-measure值上均表現(xiàn)出無(wú)論k取何值,TDQO算法始終要優(yōu)于前兩種算法.
根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)F值繪制成折線圖如圖2所示.
表4 三種權(quán)重計(jì)算方法在聚類上 F-measure 比較
圖2 三種權(quán)重計(jì)算方法在F值走勢(shì)圖
從圖2折線趨勢(shì)圖可以明顯看出,使用QPSO算法提高了聚類準(zhǔn)確率,而本文提出的TDQO算法更加有效地提高了聚類準(zhǔn)確率.當(dāng)類別越大或越小時(shí),QPSO算法準(zhǔn)確率雖然與TF-IDF算法準(zhǔn)確率很接近,但是整體準(zhǔn)確率有所提高;當(dāng)聚類類別數(shù)為5時(shí),準(zhǔn)確率提高最大(7.85%).TDQO算法在各個(gè)類別上的準(zhǔn)確率均大大高于QPSO算法的準(zhǔn)確率,這證明了不同的詞性對(duì)于文本聚類的貢獻(xiàn)度是有影響的.從整體上來(lái)看,當(dāng)聚類類別從3開始,聚類效果呈上升趨勢(shì),當(dāng)類別數(shù)超過(guò)5 時(shí),普遍的呈下降趨勢(shì).所以聚類k值為 5 時(shí),聚類準(zhǔn)確率達(dá)到最高.
此時(shí),將k設(shè)定5作為不變量,測(cè)試用三種不同方法在不同特征維度中的聚類效果.具體實(shí)驗(yàn)數(shù)據(jù)如圖3-圖5所示.
圖3 TF-IDF 算法在各維度上聚類效果
從圖3和圖4可以看出共同點(diǎn):在低特征維度上聚類分布改善不明顯,在高特征維度上,聚類分布效果較好.區(qū)別在于 TF-IDF 算法在[1500,1800]高維度區(qū)間上的聚類效果要好于QPSO算法,而QPSO算法在[600,1000]區(qū)間上展現(xiàn)了較好的聚類效果.
從圖5得出結(jié)論:隨著特征維數(shù)的增大,聚類分布顯著.與圖3和圖4比較來(lái)看,TDQO算法在[200,1800]區(qū)間的聚類分布依然表現(xiàn)出良好的聚類效果.本文提出的TDQO算法一方面提高聚類準(zhǔn)確率,另一方面在不同特征維度也展現(xiàn)了較好的聚類效果,同時(shí)具有更廣泛的應(yīng)用范圍.
圖4 QPSO 算法在各維度上聚類效果
圖5 TDQO 算法在各維度上聚類效果
目前短文本在特征權(quán)重計(jì)算的方法上很大程度上仍按照長(zhǎng)文本的特征計(jì)算方法,然而短文本在特征屬性上更具有貢獻(xiàn)度,傳統(tǒng)的方法會(huì)降低其準(zhǔn)確率.本文在現(xiàn)有的特征權(quán)重計(jì)算方法的基礎(chǔ)上,提出了TDQO算法[18].該算法引入某種詞性作為特征出現(xiàn)時(shí)的概率,并將粒子作為特征在迭代中尋找最優(yōu)權(quán)重配比.實(shí)驗(yàn)表明該算法在聚類中準(zhǔn)確率有所提高,因此也證明了詞性權(quán)重對(duì)于聚類結(jié)果是有影響的.另外,對(duì)于聚類類別k值的選取也會(huì)對(duì)實(shí)驗(yàn)結(jié)果有所影響.對(duì)于本文的算法依然還存在改進(jìn)的地方,可以在實(shí)驗(yàn)的不同環(huán)節(jié)或者算法內(nèi)部提高效率.
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 李凱齊,刁興春,曹建軍.基于信息增益的文本特征權(quán)重改進(jìn)算法.計(jì)算機(jī)工程,2011,37(1):16–18.
5 杜坤,劉懷亮,郭路杰.結(jié)合復(fù)雜網(wǎng)絡(luò)的特征權(quán)重改進(jìn)算法研究.現(xiàn)代圖書情報(bào)技術(shù),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 李欣蓬.雙維度特征關(guān)系和特征位置對(duì)類別學(xué)習(xí)的影響[碩士學(xué)位論文].天津:天津師范大學(xué),2009.
9 黃文濤,徐凌宇,李嚴(yán),等.基于柔性區(qū)間的多文本融合提取方法.計(jì)算機(jī)工程,2007,33(24):217–219.[doi:10.3969/j.issn.1000-3428.2007.24.076]
10 吳光遠(yuǎn),何丕廉,曹桂宏,等.基于向量空間模型的詞共現(xiàn)研究及其在文本分類中的應(yīng)用.計(jì)算機(jī)應(yīng)用,2003,23(S1):138–140.
11 許建潮,胡明.中文Web文本的特征獲取與分類.計(jì)算機(jī)工程,2005,31(8):24–25,39.
12 于海燕,陸慧娟,鄭文斌.情感分類中基于詞性嵌入的特征權(quán)重計(jì)算方法.計(jì)算機(jī)工程與應(yīng)用,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 李英.基于詞性選擇的文本預(yù)處理方法研究.情報(bào)科學(xué),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 常鵬,馬輝.高效的短文本主題詞抽取方法.計(jì)算機(jī)工程與應(yīng)用,2011,47(20):126–128,154.[doi:10.3778/j.issn.1002-8331.2011.20.036]
18 奚茂龍,盛歆漪,孫俊.基于多維問題的交叉算子量子粒子群優(yōu)化算法.計(jì)算機(jī)應(yīng)用,2015,35(3):680–684.[doi:10.11772/j.issn.1001-9081.2015.03.680]