一種基于同義詞發(fā)現(xiàn)的文本擴(kuò)充算法

李 波，石慧霞，王 毅

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

文本分類表示將未知文本與數(shù)據(jù)庫(kù)中已分類文本進(jìn)行相似度匹配，從而將未知文本劃分到對(duì)應(yīng)類別的過程［1］。目前，文本分類已經(jīng)在知識(shí)提取、用戶興趣模式挖掘、郵件過濾等領(lǐng)域得到了廣泛應(yīng)用［2-5］。針對(duì)文本分類時(shí)準(zhǔn)確率不高的缺陷，國(guó)內(nèi)外學(xué)者展開了大量深入細(xì)致的研究。文獻(xiàn)［6］在Latent Semantic Index(LSI)模型基礎(chǔ)上融入了分類時(shí)的特征信息來提高文檔之間的區(qū)分能力。文獻(xiàn)［7］試圖識(shí)別文本中的模式短語(yǔ)并用于特征信息表示，以一種遞歸的方式將互信息選擇準(zhǔn)則用于模式短語(yǔ)的權(quán)值定義。文獻(xiàn)［8］針對(duì)分類算法本身，提出迭代修正質(zhì)心的策略來提高分類算法的準(zhǔn)確率。文獻(xiàn)［9］針對(duì)神經(jīng)網(wǎng)絡(luò)算法在分類時(shí)收斂速度的不足，引入聚類算法中的理念，提出基于樣本中心的徑向基神經(jīng)網(wǎng)絡(luò)來改善神經(jīng)網(wǎng)絡(luò)算法反向傳播時(shí)收斂速度慢的缺點(diǎn)。文獻(xiàn)［10］和［11］試圖從文本中篩選出能準(zhǔn)確反映文本特征的屬性。

目前的研究主要集中在訓(xùn)練文本中特征選擇和文本分類算法自身的改進(jìn)上，缺乏對(duì)待分類文本的深入研究。由于待分類文本包含的關(guān)鍵詞非常有限，存在嚴(yán)重的關(guān)鍵詞稀疏問題，因此如何根據(jù)有限的關(guān)鍵詞來準(zhǔn)確反映待分類的主題特征對(duì)于提高文本分類的準(zhǔn)確率有著非常重要的意義。

本文提出一種有效的同義詞發(fā)現(xiàn)算法，針對(duì)待分類文本中所有關(guān)鍵詞，根據(jù)知網(wǎng)在詞語(yǔ)組織上的層次架構(gòu)，對(duì)待分類文本中關(guān)鍵詞進(jìn)行定位標(biāo)識(shí)。在知網(wǎng)結(jié)構(gòu)中遍歷尋找與該關(guān)鍵詞位于同一路徑的所有知網(wǎng)義原(即同義詞)，引入層次衰減函數(shù)來處理知網(wǎng)不同層次間義原縱向含義的變化，引入知網(wǎng)層次中義原的密度信息來處理知網(wǎng)同層次間義原橫向含義的變化。關(guān)鍵詞和所有同義詞之間的關(guān)聯(lián)性通過相關(guān)系數(shù)來反映，相關(guān)系數(shù)通過層次衰減函數(shù)和義原之間的密度信息來定義。同義詞發(fā)現(xiàn)算法獲得的同義詞的權(quán)值通過關(guān)鍵詞權(quán)值和相關(guān)系數(shù)乘積計(jì)算得到，將新獲得的同義詞用于擴(kuò)充待分類文本。實(shí)驗(yàn)結(jié)果證明了本文提出的算法在文本分類的準(zhǔn)確率以及F1值方面都有明顯的提高。

1 HowNet簡(jiǎn)介

本文引入HowNet的概念，根據(jù)HowNet的層次架構(gòu)關(guān)系定位關(guān)鍵詞。HowNet［12-13］是一個(gè)以漢語(yǔ)和英語(yǔ)的詞語(yǔ)所代表的概念為描述對(duì)象，以揭示概念與概念之間以及概念所具有的屬性之間的關(guān)系為基本內(nèi)容的常識(shí)知識(shí)庫(kù)。HowNet被廣泛應(yīng)用在文本聚類、文本分類、文本檢索、查詢擴(kuò)展、敏感信息過濾等領(lǐng)域。HowNet中有兩個(gè)重要的概念。

概念 對(duì)詞匯語(yǔ)義的一種描述，每一個(gè)詞可以對(duì)應(yīng)多個(gè)概念?！案拍睢笔怯靡环N“知識(shí)表示語(yǔ)言”來描述的，這種“知識(shí)表示語(yǔ)言”所用的“詞匯”叫做“義原”。

義原 用于描述一個(gè)“概念”的最基本的、不易于再分割的意義的最小單位。

與一般的語(yǔ)義詞典(WordNet、同義詞詞林)不同，HowNet并不是簡(jiǎn)單的將所有的“概念”歸結(jié)到一個(gè)樹狀的概念層次體系中，而是試圖用一系列的“義原”來對(duì)每一個(gè)“概念”進(jìn)行描述。

HowNet中所有的義原組成了一個(gè)義原層次樹，這些義原之間存在著很多種關(guān)系:上下位關(guān)系、對(duì)義關(guān)系、同義關(guān)系、反義關(guān)系、宿主-屬性關(guān)系等。本文主要針對(duì)義原之間上下位關(guān)系展開研究［14］。

2 基于同義詞發(fā)現(xiàn)的文本擴(kuò)充算法

現(xiàn)有的文本分類時(shí)常因待分類文本中關(guān)鍵詞稀疏而導(dǎo)致分類的準(zhǔn)確率不高。本文以HowNet為基礎(chǔ)，利用HowNet中義原之間的層次關(guān)聯(lián)進(jìn)行同義詞發(fā)現(xiàn)，利用義原之間層次衰減函數(shù)和密度差異來計(jì)算待分類文本中關(guān)鍵詞和發(fā)現(xiàn)的同義詞之間的相關(guān)系數(shù)，通過相關(guān)系數(shù)對(duì)發(fā)現(xiàn)的同義詞的權(quán)值進(jìn)行定義，所有發(fā)現(xiàn)的同義詞協(xié)同作用完成對(duì)分類文本的關(guān)鍵詞擴(kuò)充。

2.1 同義詞發(fā)現(xiàn)

HowNet中義原按照上下位關(guān)系構(gòu)建義原層次樹［15］，如圖1所示。圖1中，義原層次樹中的低層節(jié)點(diǎn)是高層節(jié)點(diǎn)詞義的細(xì)化，因此，高層節(jié)點(diǎn)詞義相對(duì)抽象，低層節(jié)點(diǎn)義原詞義相對(duì)具體?，F(xiàn)作如下定義:

定義1 義原子集:義原層次樹中位于指定位置義原低層的所有義原集合，記為SetA。

定義2 義原父集:義原層次樹中位于指定位置義原高層的所有義原集合，記為SetB。

本文在義原層次樹的基礎(chǔ)上定義同義詞發(fā)現(xiàn)算法，具體算法如下:

采用向量空間模型［16］，對(duì)于待分類T，則T表示為T=(t1.t2，…，tn)，其中:ti(1≤i≤n)表示待分類文本關(guān)鍵詞，n表示文本T中的關(guān)鍵詞總數(shù)。

For ti(1≤i≤n)，在義原層次樹中進(jìn)行遍歷搜索，定位關(guān)鍵詞ti在義原層次樹中匹配義原并獲得匹配義原的位置p及所處層數(shù)i。記匹配義原為基準(zhǔn)義原。

以位置p和層數(shù)i為搜索起始點(diǎn)，向義原層次樹高層進(jìn)行搜索，得到匹配義原所有父節(jié)點(diǎn)義原并加入義原父集SetB中。

以位置p和層數(shù)i為搜索起始點(diǎn)，向義原層次樹低層進(jìn)行搜索，得到匹配義原所有子節(jié)點(diǎn)義原并加入到義原子集SetA中。

所有發(fā)現(xiàn)同義詞集合為義原父集SetB和義原子集SetA的并集，記為Set=SetB∪SetA。同義詞集合中的每個(gè)義原稱為同義詞義原。

圖1 義原層次樹

2.2 同義詞權(quán)重計(jì)算

對(duì)于待分類文本T中的關(guān)鍵詞，關(guān)鍵詞權(quán)值可采用目前常用的tf-idf權(quán)值計(jì)算方法［17］。對(duì)于文本T中關(guān)鍵詞t、t的權(quán)值如式(1)所示。

其中:wt為關(guān)鍵詞t在文本T中的權(quán)值;tf(t，T)為關(guān)鍵詞t在文本T中出現(xiàn)的次數(shù);N為文本集中文本總數(shù);nt為文本集包含關(guān)鍵詞t的文本數(shù)目;0.01為數(shù)據(jù)平滑因子。

采用同義詞發(fā)現(xiàn)算法，得到待分類文本中關(guān)鍵詞的眾多同義詞，得到的同義詞需要進(jìn)行權(quán)值定義。本文引入相關(guān)系數(shù)的概念，待分類文本中關(guān)鍵詞權(quán)值與相關(guān)系數(shù)的乘積作為同義詞權(quán)值。相關(guān)系數(shù)通過計(jì)算關(guān)鍵詞和同義詞在義原層次樹中的詞語(yǔ)相似度獲得。目前HowNet中義原之間相似度［18］的計(jì)算見式(2)。

其中:dis(p1，p2)表示義原p1和義原p2在義原層次樹中的路徑距離;α為可調(diào)節(jié)參數(shù)，表示相似度為0.5時(shí)的詞語(yǔ)距離值。

義原層次樹中高層節(jié)點(diǎn)比低層節(jié)點(diǎn)表達(dá)的詞義更為抽象。取“動(dòng)物”為基準(zhǔn)義原節(jié)點(diǎn)，則其父義原為“物質(zhì)”，子義原為“獸”、“人”。顯然，子義原與基準(zhǔn)義原的詞義更為相近。義原層次樹中，越往高層位置，詞義衰減得越明顯;越往低層，詞義衰減得越緩慢。因此，義原之間詞義差異隨著層次距離變化呈非線性趨勢(shì)。經(jīng)過大量實(shí)驗(yàn)與數(shù)據(jù)擬合，得到基于義原層次差異的義原相似度(如式(4)所示)。

式(3)中:f1(x)表示層次衰減函數(shù);l(p1)和l(p2)分別為基準(zhǔn)義原p1和同義詞義原p2在義原層次樹中所處的層數(shù);|l(p1)-l(p2)|表示義原p1和p2之間的層次差異。

義原層次樹中同一層的義原密度不一定相同。例如“獸”與“莊稼”位于同一層次，但“莊稼”位于高密度區(qū)域，高密度區(qū)域往往分類比較精細(xì)，義原之間的詞義差異性相比低密度區(qū)域較大。因此，基準(zhǔn)義原與同義詞義原之間的相似度會(huì)隨著同義詞義原所在層數(shù)的密度不同而發(fā)生差異。同義詞義原所在層的密度越大，相似度會(huì)趨于降低，同義詞義原所在層的密度越小，相似度會(huì)趨于偏高?；诿芏刃畔⒌牧x原相似度計(jì)算如下:

其中:N(p2)為同義詞義原p2所在層的義原數(shù)目，即密度信息;N(Set)為同義詞義原集合中所有義原的數(shù)目;N(pi)表示同義詞義原集合Set中義原pi所在層的義原數(shù)目表示對(duì)同義詞義原p2的密度信息做均衡化。

將基于密度信息的義原相似度作為待分類文本中關(guān)鍵詞和同義詞之間的相關(guān)系數(shù)。相關(guān)系數(shù)記為c，則對(duì)于文本T中關(guān)鍵詞t，t經(jīng)過同義詞擴(kuò)展后得到同義詞義原集合Set。對(duì)任一同義詞義原 p，p∈Set，則同義詞義原 p權(quán)值為

2.3 待分類文本擴(kuò)展

對(duì)于待分類文本T，T的初始表示形式為T=(t1.t2，…，tn)。對(duì)于文本 T中關(guān)鍵詞 ti(1≤i≤n)，使用同義詞發(fā)現(xiàn)算法，得到關(guān)鍵詞ti的同義詞集合Seti，則待分類文本T可表示為

其中:關(guān)鍵詞 ti(1≤i≤n)的權(quán)值為wti;同義詞義原piN(Seti)的權(quán)值為wpiN(Seti)。

3 實(shí)驗(yàn)與分析

將本文的文本擴(kuò)充算法運(yùn)用于文本分類，文本分類采用Naive Bayes算法。以20Newsgroups和Reuters21578 Top10為測(cè)試數(shù)據(jù)集，分別比較本文算法、未做待分類文本擴(kuò)充的傳統(tǒng)算法和文獻(xiàn)［19］中的算法的分類準(zhǔn)確率和F1值。其中，F(xiàn)1=表示召回率 )。

3.1 20Newsgroups數(shù)據(jù)集

20Newsgroups數(shù)據(jù)集是目前文本分類領(lǐng)域比較常用的數(shù)據(jù)集。該數(shù)據(jù)集共分為20個(gè)類別，每個(gè)類別中大約有1 000個(gè)文檔，如表1所示。

表1 20Newsgroups數(shù)據(jù)集

在表1中選取每個(gè)類別中70%的文檔作為訓(xùn)練文本，剩余的30%作為測(cè)試文本，分別比較本文算法、傳統(tǒng)算法、文獻(xiàn)［19］中的算法的分類準(zhǔn)確率和F1值，實(shí)驗(yàn)結(jié)果如圖2、3所示。

圖2 本文算法、傳統(tǒng)算法與文獻(xiàn)［19］算法基于20Newsgroups數(shù)據(jù)集的分類準(zhǔn)確率比較

圖2中，本文算法和文獻(xiàn)［19］算法在進(jìn)行文本分類時(shí)都保持了較高的分類準(zhǔn)確率。相對(duì)而言，本文算法的準(zhǔn)確率更高，達(dá)到86.03%，相比文獻(xiàn)［19］算法提高了1.01%。傳統(tǒng)算法的準(zhǔn)確率相對(duì)較低，保持在80.99%左右。圖3中，本文算法的F1值的平均值為0.85左右，文獻(xiàn)［19］算法的F1值的平均值為0.84左右，傳統(tǒng)算法的F1值的平均值為0.80左右。本文算法的F1值相對(duì)其他兩種方法有不同程度的提高。

圖3 本文算法、傳統(tǒng)算法和文獻(xiàn)［19］算法基于20Newsgroups數(shù)據(jù)集的F1值比較

3.2 Reuters21578 Top10數(shù)據(jù)集

Reuters21578數(shù)據(jù)集也是使用較為廣泛的測(cè)試集。該數(shù)據(jù)集分為topics，organizations，exchanges，places和people 5個(gè)大類，135個(gè)子類別，共有21 578個(gè)文檔。最常用的10個(gè)子類別稱為Reuters21578 Top10，如表2所示。

表2 Reuters21578 Top10數(shù)據(jù)集

與20Newsgroups數(shù)據(jù)集相同，在表2中選取每個(gè)類別70%的數(shù)據(jù)作為訓(xùn)練文本，其余30%作為測(cè)試文本。分別比較本文算法、傳統(tǒng)算法和文獻(xiàn)［19］算法在分類時(shí)的分類準(zhǔn)確率，如圖4所示。

圖4中，選用Reuters21578 Top10數(shù)據(jù)集的文本分類準(zhǔn)確率如下:本文算法為88.09%，文獻(xiàn)［19］算法為87.38%，傳統(tǒng)算法為82.61%。3種算法的F1值如圖5所示。

圖4 本文算法、傳統(tǒng)算法與文獻(xiàn)［19］算法基于Reuters21578 Top10數(shù)據(jù)集的分類準(zhǔn)確率比較

圖5中，本文算法的F1值在0.87左右，文獻(xiàn)［19］算法在0.86左右，傳統(tǒng)算法在0.82左右，同基于20Newsgroups數(shù)據(jù)集所得的結(jié)果基本一致。

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

本文針對(duì)文本分類時(shí)待分類文本關(guān)鍵詞稀疏的問題，提出了一種基于同義詞發(fā)現(xiàn)的文本擴(kuò)充算法。該算法利用HowNet中的義原層次架構(gòu)關(guān)系，對(duì)待分類文本中的關(guān)鍵詞進(jìn)行同義詞發(fā)現(xiàn)，并利用義原層次樹中義原的層次特性和密度信息來反映關(guān)鍵詞和同義詞義原之間的相關(guān)性，通過相關(guān)性來對(duì)同義詞義原進(jìn)行權(quán)值定義。以20Newsgroups和Reuters21578 Top10為測(cè)試數(shù)據(jù)集，本文算法使得文本分類的準(zhǔn)確率分別提高了5.04%和5.48%，F(xiàn)1值提高了0.05。下一步工作將對(duì)基于知網(wǎng)的義原層次樹做進(jìn)一步研究，考慮強(qiáng)度方面的影響，使同義詞的計(jì)算更為精準(zhǔn)，進(jìn)一步提高義原之間相似度計(jì)算的準(zhǔn)確性。

［1］劉赫，張相洪，劉大有，等.一種基于最大邊緣相關(guān)的特征選擇方法［J］.計(jì)算機(jī)研究與發(fā)展，2012，49(2):354-360.

［2］柴寶仁，谷文成，牛占云，等.基于Boosting算法的垃圾郵件過濾方法研究［J］.北京理工大學(xué)學(xué)報(bào)，2013，33(1):79-83.

［3］Crammer K，Gentile C.Multiclass classification with bandit feedback using adaptive regularization ［J］.Machine Learning，2013，90:357-383.

［4］江雪，孫樂.用戶查詢意圖切分的研究［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36(3):664-670.

［5］秦寶寶，宋繼偉，董尹，等.競(jìng)爭(zhēng)情報(bào)系統(tǒng)中一種自動(dòng)文本分類策略［J］.圖書情報(bào)工作，2012，56(24):39-43.

［6］Wenbin Zheng，Lixin An，Zhanyi Xu.Dimensionality Reduction by Combining Category Information and Latent Semantic Index for Text Categorization［J］.Journal of Information ＆ Computational Science，2013，10(8):2463-2469.

［7］Bin Zhang，AlexMarin，Brian Hutchinson.Learning Phrase Patterns for Text Classification［J］.IEEE Transactions on audio，speech，and language processing，2013，21(6):1180-1189.

［8］王德慶，張輝.基于支持向量的迭代修正質(zhì)心文本分類算法［J］.北京航空航天大學(xué)學(xué)報(bào)，2013，39(2):269-274.

［9］朱云霞.集合聚類思想神經(jīng)網(wǎng)絡(luò)文本分類技術(shù)研究［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(1):155-157.

［10］Baccianella S，Esuli A，Sebastiani F.Using micro-documents for feature selection:The case of ordinal text classification［J］.Expert Systems with Applications，2013，40:4687-4696.

［11］Djeddi C，Siddiqi I，Souici-Meslati L.Text-independent writer recognition using multi-script handwritten texts［J］.Pattern Recognition Letters，2013，34:1194-1202.

［12］董振東，董強(qiáng).知網(wǎng)［EB/OL］.(1999-09-23)［2004-03-06］.http://www.keenage.com..

［13］傅向華，劉國(guó)，郭巖巖.中文博客多方面話題情感分析研究［J］.中文信息學(xué)報(bào)，2013，27(1):47-55.

［14］劉群，李素建.基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)算［J］.計(jì)算語(yǔ)言學(xué)及中文信息處理，2002，7:59-76.

［15］葛斌，李芳芳，郭絲路，等.基于知網(wǎng)的詞匯語(yǔ)義相似度計(jì)算方法研究［J］.計(jì)算機(jī)應(yīng)用研究，2010，27(9):3329-3333.

［16］Bahojb I M，Reza K M，Reza A.A novel embedded feature selection method:Acomparative study in the application of text categorization［J］.Applied Artificial Intelligence，2013，27(5):408-427.

［17］Wang Deqing，Zhang Hui.Inverse-category-frequency based supervised term weighting schemes for text categorization［J］.Journal of Information Science and Engineering，2013，29(2):209-225.

［18］龍瓏，鄧偉.綠色網(wǎng)絡(luò)博文傾向性分析算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(4):1095-1098.

［19］張愛科.基于改進(jìn)的最大熵均值聚類方法在文本分類中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(4):1297-1299.