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

李 波，石慧霞，王 毅

(重慶理工大學計算機科學與工程學院，重慶 400054)

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

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

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

1 HowNet簡介

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

概念 對詞匯語義的一種描述，每一個詞可以對應多個概念。“概念”是用一種“知識表示語言”來描述的，這種“知識表示語言”所用的“詞匯”叫做“義原”。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 義原層次樹

2.2 同義詞權重計算

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

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

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

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

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

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

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

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

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

2.3 待分類文本擴展

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

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

3 實驗與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

［2］柴寶仁，谷文成，牛占云，等.基于Boosting算法的垃圾郵件過濾方法研究［J］.北京理工大學學報，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］.計算機學報，2013，36(3):664-670.

［5］秦寶寶，宋繼偉，董尹，等.競爭情報系統(tǒng)中一種自動文本分類策略［J］.圖書情報工作，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］.北京航空航天大學學報，2013，39(2):269-274.

［9］朱云霞.集合聚類思想神經(jīng)網(wǎng)絡文本分類技術研究［J］.計算機應用研究，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］董振東，董強.知網(wǎng)［EB/OL］.(1999-09-23)［2004-03-06］.http://www.keenage.com..

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

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

［15］葛斌，李芳芳，郭絲路，等.基于知網(wǎng)的詞匯語義相似度計算方法研究［J］.計算機應用研究，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)絡博文傾向性分析算法研究［J］.計算機應用研究，2013，30(4):1095-1098.

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