基于命名實(shí)體n-gram圖的文本相似性度量

于 營(yíng)，周顯春，賈樹文

（1.三亞學(xué)院信息與智能工程學(xué)院，三亞 572000；2.三亞學(xué)院容淳銘院士工作站，三亞 572000；3.三亞學(xué)院盛寶金融科技商學(xué)院，三亞 572000）

0 引言

文本比較算法是自然語(yǔ)言處理和文本挖掘任務(wù)的關(guān)鍵，如文本聚類、文本分類和自動(dòng)文本摘要等。然而，理解兩篇文章是在談?wù)撏恢黝}還是以某種方式相關(guān)，仍然是自然語(yǔ)言處理面臨的一個(gè)挑戰(zhàn)。

自動(dòng)文本比較的主要困難是詞的語(yǔ)義歧義、句子之間的詞匯和句法差異。Stavrianou等提出，在文本預(yù)處理過(guò)程中必須考慮到以下情況對(duì)文本相似性的影響：停用詞和噪聲數(shù)據(jù)（如拼寫錯(cuò)誤的單詞）的去除、詞干提取、詞性標(biāo)注、多詞術(shù)語(yǔ)搭配、詞語(yǔ)切分和文本表示。本研究的文本預(yù)處理旨在通過(guò)減少語(yǔ)義歧義和特征空間的維度來(lái)減少文檔中的信息量。

向量空間模型（vector space model，VSM）把對(duì)文本內(nèi)容的處理簡(jiǎn)化為向量運(yùn)算，以空間上的相似度（如余弦相似度）來(lái)表達(dá)語(yǔ)義的相似度，常用于信息過(guò)濾、信息獲取、信息索引，以及詞的語(yǔ)義相關(guān)性的評(píng)估。潛在語(yǔ)義分析（laten semantic analysis，LSA）是一種文本話題分析的方法，特點(diǎn)是可以通過(guò)矩陣分解（SVD或者NMF）來(lái)發(fā)現(xiàn)文本與單詞之間的基于話題的語(yǔ)義關(guān)系。此外，使用n-gram模型做文本表示的研究也有很多。n-gram是一種基于統(tǒng)計(jì)語(yǔ)言模型的算法，其基本思想是將文本內(nèi)容按照字節(jié)進(jìn)行大小為n的滑動(dòng)窗口操作，形成了長(zhǎng)度為n的字節(jié)片段序列。每一個(gè)字節(jié)片段稱為gram，對(duì)所有g(shù)ram的出現(xiàn)頻度進(jìn)行統(tǒng)計(jì)，并按照事先設(shè)定好的閾值進(jìn)行過(guò)濾，形成關(guān)鍵gram列表，也就是這個(gè)文本的向量特征空間，列表中的每一種gram就是一個(gè)特征向量維度。

本文將命名實(shí)體的信息量與n-gram模型的表示能力相結(jié)合，以捕獲詞序列信息，并定義一個(gè)新的基于n-gram模型的文本相似性度量方法。本研究使用兩個(gè)不同的數(shù)據(jù)集評(píng)估該方法在文本聚類任務(wù)中的性能。結(jié)果表明，術(shù)語(yǔ)選擇可以提高n-gram相似性的性能，命名實(shí)體可以成為使用TD-IDF（term frequency-inverse document frequency，詞頻-逆文本頻率指數(shù)）加權(quán)方案選擇的術(shù)語(yǔ)集的有效補(bǔ)充。

1 相關(guān)研究

近年來(lái)，文本相似性度量的相關(guān)研究有很多。Giannakopoulos和Karkaletsis使用長(zhǎng)度為n的滑動(dòng)窗口將文本表示為n-gram模型，通過(guò)將相鄰的n-gram與表示它們?cè)诮o定文本窗口內(nèi)共現(xiàn)頻率的邊連接起來(lái)，捕獲文本中的詞序，并檢測(cè)文本形態(tài)中的部分相似性。該方法具有一定的抗噪能力，并且無(wú)需預(yù)處理。

盡管n-gram在文本挖掘任務(wù)中表現(xiàn)出了良好的性能，但對(duì)于大文本，其復(fù)雜性顯著增加。為了解決這個(gè)問(wèn)題，往往只關(guān)注信息量較大的術(shù)語(yǔ)，例如具有最高TD-IDF的術(shù)語(yǔ)或命名實(shí)體，從而在不丟失重要信息的情況下降低模型的復(fù)雜性。Kumaran等使用命名實(shí)體術(shù)語(yǔ)來(lái)提高“新事件檢測(cè)”任務(wù)的性能，Toda等使用命名實(shí)體來(lái)聚類搜索結(jié)果，而Sinoara等和Montalvo等人在文本聚類中使用命名實(shí)體作為特權(quán)信息。Gomaa對(duì)文本相似性度量進(jìn)行了調(diào)查，將其分為三類：基于字符序列的字符串度量，基于語(yǔ)料庫(kù)的度量，基于知識(shí)的度量。Mihalcea等也使用了來(lái)自外部語(yǔ)義網(wǎng)絡(luò)的信息，并為短文本定義了基于知識(shí)的相似性度量，與其他基于向量的相似度度量相比，文本語(yǔ)義識(shí)別的錯(cuò)誤率降低了13%。Friburger等發(fā)現(xiàn)，使用“命名實(shí)體”向量和“所有詞”向量并增加實(shí)體向量的權(quán)重，具有最佳的整體性能。Schenker等人使用圖表示模型和基于圖的相似性度量來(lái)執(zhí)行文本聚類和分類任務(wù)。

與國(guó)外學(xué)者相比，國(guó)內(nèi)學(xué)者在文本相似性度量方面的研究開展的較晚。金希茜基于VSM模型提出對(duì)文本進(jìn)行特征提取，通過(guò)詞匯的語(yǔ)義相似度進(jìn)行文本特征提取，采用遞歸算法判斷文本相似度。華秀麗通過(guò)《知網(wǎng)》對(duì)詞頻較高的文本特征項(xiàng)進(jìn)行語(yǔ)義分析，達(dá)到獲取文本語(yǔ)義相似度的效果。針對(duì)同義詞，該方法采用將同義詞進(jìn)行詞義合并，以某一個(gè)詞來(lái)替代所以該類別的詞，但該方法計(jì)算較復(fù)雜。唐凌志針對(duì)這個(gè)問(wèn)題，采用本體相似性方法中的語(yǔ)義密度因子作為調(diào)節(jié)因子應(yīng)用到文本相似性計(jì)算中，達(dá)到降低計(jì)算復(fù)雜度的效果。

本文在Giannakopoulos和Karkaletsis提出的文本相似性度量標(biāo)準(zhǔn)的基礎(chǔ)上，通過(guò)TF-IDF區(qū)分命名實(shí)體和頻數(shù)較高的術(shù)語(yǔ)，并相應(yīng)地對(duì)n-gram模型進(jìn)行加權(quán)。

2 研究方法

本文定義了一種文本比較方法，該方法識(shí)別文本中出現(xiàn)的命名實(shí)體，并將文本表示為ngram模型，使用圖比較操作符進(jìn)行比較。

2.1 算法原理

對(duì)于每一對(duì)輸入文本T,T，相似度函數(shù)f將輸出一個(gè)分?jǐn)?shù)s=f(T,T)，其中，{s∈R|0≤s≤1}表示兩文本的相似程度。s的值接近1，表示文本之間高度相似；當(dāng)s接近0時(shí)，文本不相似。過(guò)程如圖1所示。

圖1 算法原理

首先是信息提取，從文本中提取命名實(shí)體和使用TF-IDF權(quán)值較大的術(shù)語(yǔ)兩種類型的術(shù)語(yǔ)，命名實(shí)體的提取使用Open Calais API完成；接下來(lái)是文本表示，所有實(shí)體都被替換為哈希值，該哈希值允許多詞實(shí)體在詞圖表示中顯示為單個(gè)詞模型，其余的詞都替換為占位符，本研究中選擇大寫字母“A”作為占位符。單個(gè)占位符的使用使得所有不重要的單詞在詞圖中只有一個(gè)節(jié)點(diǎn)，這顯著降低了n-gram的大小和比較運(yùn)算的復(fù)雜度。同樣，命名實(shí)體到哈希值的映射進(jìn)一步減少了模型的內(nèi)存占用，因?yàn)樵诖蠖鄶?shù)情況下，哈希值比完整實(shí)體名占用更少的內(nèi)存。

2.2 n-gr am的創(chuàng)建和比較

為了創(chuàng)建單詞n-gram圖，使用JInsect工具箱。JInsect工具箱是一個(gè)基于Java的工具箱和庫(kù)，它支持在自然語(yǔ)言處理應(yīng)用程序中使用n元語(yǔ)法圖，支持自動(dòng)摘要，摘要評(píng)估，以及文本分類和索引，支持字符和詞n-gram圖并實(shí)現(xiàn)了多種圖的相似性度量。

單詞n-gram圖是在單詞上使用大小為n的滑動(dòng)窗口創(chuàng)建的，這表示為文本中的每個(gè)單詞或術(shù)語(yǔ)哈希值創(chuàng)建一個(gè)節(jié)點(diǎn)，并且圖的邊連接比較接近的單詞（節(jié)點(diǎn)）。當(dāng)距離≤d時(shí)，使用d=n表示。該圖是加權(quán)的，權(quán)重表示在滑動(dòng)窗口的距離內(nèi)，兩個(gè)單詞彼此靠近的次數(shù)。

為了比較兩個(gè)圖，我們稱它們?yōu)镚和G，使用了四個(gè)相似性度量：值相似度、大小相似度、包含相似度和歸一化值相似度，四個(gè)度量值的取值范圍均為[0,1]。圖G和G的比較描述如下：

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)準(zhǔn)備與處理

在實(shí)驗(yàn)中，使用了兩個(gè)數(shù)據(jù)集。分別為：①AG_news數(shù)據(jù)集，含2000多個(gè)新聞源的新聞文章，其中包括120000條訓(xùn)練樣本和7600條測(cè)試樣本，每一條樣本都是短文本，有4個(gè)類別（World、Sports、Business、Sci/Tec）。②MultiLing 2019_wiki數(shù)據(jù)集，多語(yǔ)言模型（42種）進(jìn)行命名實(shí)體識(shí)別，直接挑選實(shí)體作為詞條。對(duì)AG_news數(shù)據(jù)集，進(jìn)一步排除掉OpenCalais API不支持或OpenCalais API處理超時(shí)的文檔，最終的數(shù)據(jù)集中含10837個(gè)文本集；對(duì)MultiLing 2019_wiki數(shù)據(jù)集，篩選出英文版本的文檔，得到3793個(gè)文本集。

本文使用k-Means聚類算法評(píng)估所提出的算法在文本聚類中的性能。該算法的輸入是一個(gè)文本相似度矩陣，文本相似度矩陣通過(guò)以下方法創(chuàng)建：

（1）對(duì)文本數(shù)據(jù)進(jìn)行過(guò)濾，提取命名實(shí)體與TF-IDF權(quán)值較大的文本。

（2）對(duì)獲取的文本文件進(jìn)行數(shù)據(jù)清洗，并將待處理的字符串分成單詞序列，增加到n-gram模型中。

（3）使用TF-IDF和余弦相似度計(jì)算相似度模型VSM。

其中，命名實(shí)體是采用OpenCalais提取的，TF-IDF是Java程序計(jì)算的，n-gram圖是通過(guò)JINSECT庫(kù)構(gòu)建的，使用JINSECT的圖相似性度量功能對(duì)構(gòu)建的n-gram圖進(jìn)行比較，以創(chuàng)建文檔相似性矩陣。

3.2 聚類有效性指標(biāo)

為了實(shí)現(xiàn)最優(yōu)類簇?cái)?shù)和最優(yōu)劃分的選取，應(yīng)當(dāng)選擇合適的聚類的有效性評(píng)價(jià)指標(biāo)。一般來(lái)說(shuō)，聚類有效性指標(biāo)可以分內(nèi)部有效性指標(biāo)和外部有效性指標(biāo)。內(nèi)部有效性指標(biāo)主要基于數(shù)據(jù)集的幾何結(jié)構(gòu)，從信息的緊湊性、分離性、連通性和重疊度等方面對(duì)聚類效果進(jìn)行評(píng)價(jià)；外部有效性指標(biāo)是指當(dāng)數(shù)據(jù)集的外部信息可用時(shí)，通過(guò)比較聚類劃分與外部準(zhǔn)則的匹配度，可以評(píng)價(jià)不同聚類算法的性能。

在當(dāng)前實(shí)驗(yàn)數(shù)據(jù)中，“ground truth”是對(duì)數(shù)據(jù)文檔的實(shí)際分類，因此將“ground truth”選為外部指標(biāo)。由于所有實(shí)驗(yàn)都是使用相同的聚類算法k-Means完成的，影響聚類質(zhì)量的唯一因素是文本相似性度量，因此結(jié)果具有可比性。為了評(píng)估生成的聚類方案的有效性，本實(shí)驗(yàn)主要采用了查準(zhǔn)率（Precision）、查全率（Recall）和F1度量值（F1-measure）指標(biāo)。

3.3 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)使用4種不同的相似性度量方法來(lái)評(píng)估k-Means生成的聚類，即：

（1）使用TF-IDF算法計(jì)算的詞頻向量余弦相似度（TF-IDFVSM）。

（2）使用所有詞的n-gram圖相似度（All_graph）。

表2 MultiLing 2019_wiki數(shù)據(jù)集的聚類性能

（3）提取的命名實(shí)體的n-gram圖相似性度（Ent_graph）。

（4）命名實(shí)體與TF-IDF權(quán)值較大的術(shù)語(yǔ)的結(jié)合方法（Ent&tf-idf_graph）。

表1總結(jié)了新聞組數(shù)據(jù)集的結(jié)果。從表中可以看出，所有方法的在查準(zhǔn)率和F1值上都表現(xiàn)出較低的性能，這主要由于類別較多以及詞的特征空間的稀疏性。但Ent_gragh仍然優(yōu)于原始的TF-IDF VSM和All_graph方法；Ent&tfidf_graph更是在查準(zhǔn)率和F1值上明顯優(yōu)于TFIDF VSM方法。采用在實(shí)體n-gram圖中添加一些與高TF-IDF值相對(duì)應(yīng)的節(jié)點(diǎn)的方法，顯著改進(jìn)了VSM和簡(jiǎn)單n-gram圖模型的結(jié)果，且所有值都是在95%置信區(qū)間計(jì)算的。

表1 AG_news數(shù)據(jù)集的聚類性能

在MultiLing的多語(yǔ)言數(shù)據(jù)集中，Ent_graph方法在查全率Recall和F1值明顯優(yōu)于所有其他方法，命名實(shí)體似乎比文本中的其他詞對(duì)結(jié)果的影響更為突出。這體現(xiàn)了本文所提出的基于圖的相似性度量的一個(gè)主要優(yōu)勢(shì)，即處理多種語(yǔ)言文本的能力。實(shí)體提取機(jī)制僅將特征空間減少到命名實(shí)體，這些實(shí)體在語(yǔ)言之間經(jīng)常保持不變，從而降低特征空間的稀疏性。另外，當(dāng)TF-IDF權(quán)值比較高的術(shù)語(yǔ)添加到圖中時(shí)，性能反而會(huì)下降，這是因?yàn)檫@些跨語(yǔ)言翻譯的術(shù)語(yǔ)不匹配，從而降低了相應(yīng)文檔的圖的相似性。

4 結(jié)語(yǔ)

本文提出了一種基于圖的文本相似性度量方法，該方法利用命名實(shí)體的信息，提高了文本聚類任務(wù)的有效性。使用命名實(shí)體和TF-IDF權(quán)值較高的術(shù)語(yǔ)來(lái)構(gòu)建的n-gram圖，與全文ngram圖相比，復(fù)雜度降低，更為簡(jiǎn)單，從而提高了使用所有文檔信息的n-gram圖相似性度量的復(fù)雜度。結(jié)果表明，該方法在文檔中命名實(shí)體較多且實(shí)體空間重疊的情況下效果更加明顯，這是因?yàn)閷?shí)體的密度會(huì)降低特征矩陣的稀疏性。需要注意的是，該方法適用于多語(yǔ)言文本集合，因?yàn)榕c文檔中的不同的詞相比，命名實(shí)體受翻譯的影響較小。當(dāng)命名實(shí)體從一種語(yǔ)言翻譯成另外一種語(yǔ)言時(shí)，語(yǔ)義差異很小，所以容易被詞n-gram圖模型捕獲。