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

袁曉峰

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

關(guān)鍵詞： HNC理論； 語(yǔ)義相似度； VSM； 文本相似度

中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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技術(shù)的飛速發(fā)展，文本相似度的研究得到了廣泛研究。文本相似度的計(jì)算通常應(yīng)用于信息檢索、主題抽取、文本分類、情感分析等領(lǐng)域[1-2]。目前文本相似度計(jì)算方法繁蕪叢雜，歸納起來(lái)通常有：基于統(tǒng)計(jì)學(xué)的、基于知識(shí)庫(kù)的、基于本體論的等等。但最廣為接受和認(rèn)可的是基于向量空間的，即：用向量空間模型（VSM）表示文檔，向量中每一個(gè)值為文檔中每一個(gè)詞語(yǔ)的權(quán)重；然后利用向量的夾角余弦值作為兩個(gè)文本的相似度[3]。然而這種方法僅僅用某個(gè)詞語(yǔ)在文檔中出現(xiàn)的頻率以及逆向文檔頻率作為VSM中的權(quán)重，沒(méi)有考察同一篇文檔中特征詞之間的關(guān)系。另外，由于計(jì)算兩個(gè)文本向量的夾角余弦值時(shí)需要將兩個(gè)文本向量的維數(shù)對(duì)齊，這樣就造成了計(jì)算維數(shù)過(guò)高，計(jì)算過(guò)于復(fù)雜等缺點(diǎn)。

本文提出一種改進(jìn)算法，在VSM的基礎(chǔ)之上，考慮同一篇文檔中特征詞之間的相關(guān)度，利用文本中另一詞語(yǔ)對(duì)特征詞貢獻(xiàn)的相關(guān)度重新計(jì)算特征詞的TF*IDF值，從而起到降維、簡(jiǎn)化計(jì)算的目的。黃曾陽(yáng)先生創(chuàng)立的知識(shí)庫(kù)HNC理論從三個(gè)方面描述詞語(yǔ)的含義，直接從詞語(yǔ)角度、句子角度甚至整個(gè)篇章的語(yǔ)境的角度，用符號(hào)理論描述詞語(yǔ)的概念，為計(jì)算中文詞義相似度提出了一種可行的方法。本文利用基于HNC理論計(jì)算詞語(yǔ)相似度的方法來(lái)完成VSM中TF/IDF值的重新計(jì)算，降低VSM中的維數(shù)。

1 HNC和VSM簡(jiǎn)介

HNC是一個(gè)描述語(yǔ)言概念空間的符號(hào)理論體系，它包含了三部分內(nèi)容：①概念基元符號(hào)體系，對(duì)應(yīng)語(yǔ)言系統(tǒng)的詞語(yǔ)；②句類基元符號(hào)體系，對(duì)應(yīng)語(yǔ)言系統(tǒng)的語(yǔ)句；③語(yǔ)境基元符號(hào)體系，對(duì)應(yīng)語(yǔ)言系統(tǒng)的句群直至篇章[4]。

根據(jù)公式就可以把兩個(gè)HNC符號(hào)之間比較量化計(jì)算轉(zhuǎn)化為一個(gè)關(guān)于概念基元相關(guān)度的多項(xiàng)式。語(yǔ)義相關(guān)度的量化計(jì)算方法如下[5]：

⑴ 輸入兩個(gè)詞語(yǔ)w1和w2；

⑵ 在詞語(yǔ)知識(shí)庫(kù)中查找這兩個(gè)詞語(yǔ)的HNC映射符號(hào)HNCS1和HNCS2，用hnccs1i和hnccs2j表示不同義項(xiàng)的HNC映射符號(hào)，其中1?i?p，i∈N，1?j?q，j∈N，p和q分別為兩個(gè)詞語(yǔ)對(duì)應(yīng)的義項(xiàng)數(shù)；

⑶ 分別求解兩個(gè)詞語(yǔ)的各個(gè)hnccs1i和hnccs2j之間的相關(guān)度R（hnccs1i，hnccs2j）；

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

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

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

Wtd=TFtd×IDFt ⑴

其中：Wtd表示該特征項(xiàng)在文檔中的重要程度；TFtd指特征項(xiàng)在文檔d中出現(xiàn)的次數(shù)。Salton將IDFt表示成：

IDFt=log（N/nt） ⑵

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

夾角余弦公式：

⑶

2 相似度計(jì)算

設(shè)文檔集中有N篇文檔，執(zhí)行以下步驟。

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

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

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

⑷ 計(jì)算余弦值。

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

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

為了簡(jiǎn)化實(shí)驗(yàn)，我們從文本集中隨機(jī)挑取11篇文檔，計(jì)算其中的一篇（不妨稱為零號(hào)文檔）與其他10篇文檔的相似度。首先統(tǒng)計(jì)每篇文檔中的特征詞的個(gè)數(shù)，統(tǒng)計(jì)零號(hào)文檔與其他文檔相同詞的個(gè)數(shù)。通過(guò)計(jì)算同一篇文檔中詞語(yǔ)之間的相似度，選取零號(hào)文檔與其他各篇文檔之間相同詞作為特征向量，同一篇文檔中的其他詞以其與特征詞相似度對(duì)特征詞的權(quán)重做貢獻(xiàn)。經(jīng)過(guò)比較我們發(fā)現(xiàn)，選取相同詞作為特征詞使得向量空間的維數(shù)降低很多，同時(shí)可以令向量空間的維數(shù)趨于平穩(wěn)，極大地降低對(duì)計(jì)算余弦值的干擾。向量中特征詞在未降維和降維后的維度如圖1所示。

圖1 降維前后向量維數(shù)對(duì)比

從圖1中我們可以看出，改進(jìn)前文檔對(duì)應(yīng)的VSM維數(shù)比較高，并且文檔之間的跳躍性很大，降維后維數(shù)明顯降低，但是并沒(méi)有因?yàn)榫S數(shù)降低而導(dǎo)致相似度計(jì)算的準(zhǔn)確率降低。

召回率是實(shí)際識(shí)別出的正確結(jié)果（正確歸入）與文本集中總的正確結(jié)果（應(yīng)有文本數(shù)）的百分比；正確率是返回結(jié)果（實(shí)際歸入）中正確結(jié)果的百分比。比較結(jié)果如表1所示。表1中各類第一行為改進(jìn)前的結(jié)果，第二行為改進(jìn)后的結(jié)果。

表1 相似度比較結(jié)果

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

歸入＼&實(shí)際

歸入＼&應(yīng)有

文本數(shù)＼&正確率

（%）＼&召回率

（%）＼&環(huán)境＼&大氣污染的危害＼&8＼&12＼&12＼&66.7＼&66.7＼&＼&＼&9＼&12＼&12＼&75.0＼&75.0＼&＼&珍惜資源保護(hù)環(huán)境＼&5＼&12＼&8＼&41.7＼&62.5＼&＼&＼&7＼&10＼&8＼&70.0＼&87.5＼&健康＼&大學(xué)生心理健康＼&7＼&15＼&13＼&46.7＼&53.8＼&＼&＼&12＼&16＼&13＼&75.0＼&92.3＼&＼&大學(xué)生身體素質(zhì)＼&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＼&＼&美國(guó)教育理念＼&6＼&12＼&10＼&50.0＼&60.0＼&＼&＼&8＼&13＼&10＼&61.5＼&80.0＼&軍事＼&日本解禁自衛(wèi)權(quán)＼&14＼&18＼&20＼&77.8＼&70.0＼&＼&＼&16＼&19＼&20＼&84.2＼&80.0＼&]

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

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

參考文獻(xiàn)：

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

應(yīng)用研究，2008.25（11）：3256-3257

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

究與實(shí)現(xiàn)，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] 黃曾陽(yáng).HNC（概念層次網(wǎng)絡(luò)）理論—計(jì)算機(jī)理解語(yǔ)言研究的新思路[M].

清華大學(xué)出版社，1998.

[5] 張運(yùn)良，張全.基于HNC理論的語(yǔ)義相關(guān)度計(jì)算方法.[J]計(jì)算機(jī)工程

與應(yīng)用，2005.34：1-3

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

文，2006.