一種基于HNC理論的文本相似度算法

袁曉峰

摘 要： 計算文本相似度常用基于向量空間計算夾角余弦的方法，該方法忽視了同一文本中詞與詞之間的語義相似度，因而造成了文本表示模型的高維性以及計算的高復雜性。為此，提出了一種文本相似度算法，利用HNC理論先計算特征詞之間的語義相似度，進行必要的降維，進一步計算每個文本向量中的TF*IDF值，最后計算兩個向量的空間夾角余弦值并將其作為兩個文本之間的相似度。將實驗結果與直接計算余弦值的結果比較發現，改進后的算法中VSM的維數明顯比改進前小得多，改進后的算法提高了召回率和準確率。因此，改進后的算法是切實有效的。

關鍵詞： HNC理論； 語義相似度； VSM； 文本相似度

中圖分類號：TP391.1 文獻標志碼：A 文章編號：1006-8228（2014）11-40-02

Word relativity algorithm based on HNC

Yuan Xiaofeng

（School of Information Science and technology， Yancheng Teachers College， Yancheng， Jiangsu 224002， China）

Abstract： The method to calculate text similarity based on VSM is widely used， which causes high dimension of VSM and complexity of calculation because it ignores the relationship between words in the same text. HNC theory is applied to calculate the weight of VSM and the similarity between texts. The practice shows that the dimension is smaller than before， the recall rate and precision of the algorithm have improved.

Key words： HNC theory； semantic similarity； VSM； text similarity

0 引言

隨著Web技術的飛速發展，文本相似度的研究得到了廣泛研究。文本相似度的計算通常應用于信息檢索、主題抽取、文本分類、情感分析等領域[1-2]。目前文本相似度計算方法繁蕪叢雜，歸納起來通常有：基于統計學的、基于知識庫的、基于本體論的等等。但最廣為接受和認可的是基于向量空間的，即：用向量空間模型（VSM）表示文檔，向量中每一個值為文檔中每一個詞語的權重；然后利用向量的夾角余弦值作為兩個文本的相似度[3]。然而這種方法僅僅用某個詞語在文檔中出現的頻率以及逆向文檔頻率作為VSM中的權重，沒有考察同一篇文檔中特征詞之間的關系。另外，由于計算兩個文本向量的夾角余弦值時需要將兩個文本向量的維數對齊，這樣就造成了計算維數過高，計算過于復雜等缺點。

本文提出一種改進算法，在VSM的基礎之上，考慮同一篇文檔中特征詞之間的相關度，利用文本中另一詞語對特征詞貢獻的相關度重新計算特征詞的TF*IDF值，從而起到降維、簡化計算的目的。黃曾陽先生創立的知識庫HNC理論從三個方面描述詞語的含義，直接從詞語角度、句子角度甚至整個篇章的語境的角度，用符號理論描述詞語的概念，為計算中文詞義相似度提出了一種可行的方法。本文利用基于HNC理論計算詞語相似度的方法來完成VSM中TF/IDF值的重新計算，降低VSM中的維數。

1 HNC和VSM簡介

HNC是一個描述語言概念空間的符號理論體系，它包含了三部分內容：①概念基元符號體系，對應語言系統的詞語；②句類基元符號體系，對應語言系統的語句；③語境基元符號體系，對應語言系統的句群直至篇章[4]。

根據公式就可以把兩個HNC符號之間比較量化計算轉化為一個關于概念基元相關度的多項式。語義相關度的量化計算方法如下[5]：

⑴ 輸入兩個詞語w1和w2；

⑵ 在詞語知識庫中查找這兩個詞語的HNC映射符號HNCS1和HNCS2，用hnccs1i和hnccs2j表示不同義項的HNC映射符號，其中1?i?p，i∈N，1?j?q，j∈N，p和q分別為兩個詞語對應的義項數；

⑶ 分別求解兩個詞語的各個hnccs1i和hnccs2j之間的相關度R（hnccs1i，hnccs2j）；

⑷ 按公式R（w1，w2）=R（HNCS1，HNCS2）=Max（R（hnccs1i，hnccs2j）），其中1?i?p1，1?j?q求解詞語語義相關度；

⑸ 按公式Runi=R（w1，w2）/Sqrt（R（w1，w1）×R（W2，W2））若R（W1，W2）>0；Runi=ε若R（w1，w2）=0進行歸一化或者修正操作，其中ε為一個充分小的正數。

向量空間模型（VSM）是目前信息檢索領域中廣泛使用的效果比較好的一種模型。其基本思想是：假設詞與詞之間是不相關的，以向量來表示文本，從而簡化了文本中關鍵詞之間的復雜關系，使得模型具備了可計算性[6]中，文本表示為詞的向量，向量中的值為文本中每個詞的TF/IDF權重。

Wtd=TFtd×IDFt ⑴

其中：Wtd表示該特征項在文檔中的重要程度；TFtd指特征項在文檔d中出現的次數。Salton將IDFt表示成：

IDFt=log（N/nt） ⑵

其中：N表示文檔集合張所有文檔的數目；nt表示所有文檔集合中t出現的次數，稱為特征項的文檔頻率。IDF反映特征項在整個文檔集合中的分布情況，在一定程度上體現了該特征項的區分能力；TF反映特征項在文檔內部的分布情況。TF-IDF算法可以排除那些高頻、低區分度的詞，因此TF-IDF是一種有效的權重定義方法。

夾角余弦公式：

⑶

2 相似度計算

設文檔集中有N篇文檔，執行以下步驟。

⑴ 統計詞頻。待求相似度的兩篇文檔進行分詞，去除停用詞，得到詞集合Wi={wi1，wi2，…，wim}。其中，i表示所在文本序號。對Wi中的詞進行詞頻統計，記為TFWi={TFwi1， TFwi2， TFwi3，…， TFwim}。

⑵ 特征項選取。計算出兩篇文檔詞語相同的集合：TSij={ts1，ts2， …，tsk}，其中，tsi∈{Ti∩Tj}。

⑶ 構造VSM。計算TFtsi=TF（1+）、IDFtsi=log（N/nt），令wtsi=TFtsi×IDFtsi， 則I篇文檔可用VSM表示為Wi={wts1，wts2，…，wtsk}。

⑷ 計算余弦值。

3 實驗

我們從新浪網站下載80篇新聞網頁，分為軍事、體育、教育、時事政治四個主題。將這80篇網頁整理成不帶格式的文本文件，然后進行分詞、去停用詞等預處理過程得到測試集。對基于傳統的VSM和改進的VSM計算文檔相似度方法進行比較，我們從VSM維數、召回率、準確率三個方面進行衡量。

為了簡化實驗，我們從文本集中隨機挑取11篇文檔，計算其中的一篇（不妨稱為零號文檔）與其他10篇文檔的相似度。首先統計每篇文檔中的特征詞的個數，統計零號文檔與其他文檔相同詞的個數。通過計算同一篇文檔中詞語之間的相似度，選取零號文檔與其他各篇文檔之間相同詞作為特征向量，同一篇文檔中的其他詞以其與特征詞相似度對特征詞的權重做貢獻。經過比較我們發現，選取相同詞作為特征詞使得向量空間的維數降低很多，同時可以令向量空間的維數趨于平穩，極大地降低對計算余弦值的干擾。向量中特征詞在未降維和降維后的維度如圖1所示。

圖1 降維前后向量維數對比

從圖1中我們可以看出，改進前文檔對應的VSM維數比較高，并且文檔之間的跳躍性很大，降維后維數明顯降低，但是并沒有因為維數降低而導致相似度計算的準確率降低。

召回率是實際識別出的正確結果（正確歸入）與文本集中總的正確結果（應有文本數）的百分比；正確率是返回結果（實際歸入）中正確結果的百分比。比較結果如表1所示。表1中各類第一行為改進前的結果，第二行為改進后的結果。

表1 相似度比較結果

[類別＼&主題文本＼&正確

歸入＼&實際

歸入＼&應有

文本數＼&正確率

（%）＼&召回率

（%）＼&環境＼&大氣污染的危害＼&8＼&12＼&12＼&66.7＼&66.7＼&＼&＼&9＼&12＼&12＼&75.0＼&75.0＼&＼&珍惜資源保護環境＼&5＼&12＼&8＼&41.7＼&62.5＼&＼&＼&7＼&10＼&8＼&70.0＼&87.5＼&健康＼&大學生心理健康＼&7＼&15＼&13＼&46.7＼&53.8＼&＼&＼&12＼&16＼&13＼&75.0＼&92.3＼&＼&大學生身體素質＼&4＼&10＼&7＼&40.0＼&57.1＼&＼&＼&5＼&9＼&7＼&55.6＼&71.4＼&教育＼&家庭教育＼&6＼&9＼&10＼&66.7＼&60.0＼&＼&＼&7＼&10＼&10＼&70.0＼&70.0＼&＼&美國教育理念＼&6＼&12＼&10＼&50.0＼&60.0＼&＼&＼&8＼&13＼&10＼&61.5＼&80.0＼&軍事＼&日本解禁自衛權＼&14＼&18＼&20＼&77.8＼&70.0＼&＼&＼&16＼&19＼&20＼&84.2＼&80.0＼&]

4 結束語

本文中，我們首先計算文檔所有詞語的權重，然后將兩篇文檔中同時出現的詞作為特征向量，利用HNC理論計算其余詞與特征向量之間的相關度，將相關度加到特征向量的TF值中。計算TF*IDF，構造VSM，計算文檔之間的夾角余弦值并將其作為文檔之間的相似度。實驗表明，改進后的方法極大地降低了VSM的維數，降低了噪音的干擾，進而提高了召回率和準確率。

參考文獻：

[1] 郭慶琳，李艷梅，唐琦.基于VSM的文本相似度計算的研究[J].計算機

應用研究，2008.25（11）：3256-3257

[2] 李連，朱愛紅，蘇濤.一種改進的基于向量空間文本相似度算法的研

究與實現，2012.29（2）：282-283

[3] Dagan I， Marcus S. Contextual word similarity and estimation from

sparse data[A]. Collins M. Processing of the Annual Meeting of the Association for Computational Linguistics[C]. New Mexico： American Association for Artificial Intelligence，1993：164-171

[4] 黃曾陽.HNC（概念層次網絡）理論—計算機理解語言研究的新思路[M].

清華大學出版社，1998.

[5] 張運良，張全.基于HNC理論的語義相關度計算方法.[J]計算機工程

與應用，2005.34：1-3

[6] 王秀娟.文本檢索中若干問題的研究[D].北京郵電大學博士學位論

文，2006.