信息檢索中一種句子相似度的計算方法

劉云芳，楊燕，賈真，尹紅風(fēng)，楊宇飛

西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川成都 610031

信息檢索是指根據(jù)用戶提出的問題從大量文檔資源集合中自動地找到與用戶查詢請求相關(guān)的各種信息［1］，即為使用戶的查詢句子或詞語與文檔集信息匹配的一個過程，其實(shí)質(zhì)就是對自然語言進(jìn)行相關(guān)的處理，從而使匹配的效果達(dá)到令人相對滿意的程度［2］。信息檢索的主要目的是獲取用戶所需的全面的且精確的信息，這就需要對信息檢索中運(yùn)用的技術(shù)進(jìn)行相應(yīng)的改進(jìn)與完善。信息索引技術(shù)主要涉及信息詞語切分和詞語語法分析、進(jìn)行詞性標(biāo)注及相關(guān)自然語言處理、建立索引項(xiàng)索引、檢索結(jié)果處理技術(shù)，其中檢索結(jié)果處理技術(shù)是關(guān)鍵技術(shù)，其核心是依據(jù)計算結(jié)果與查詢語句的相關(guān)程度來排序。檢索結(jié)果排序則應(yīng)用到了句子相似度計算等技術(shù)。關(guān)于句子相似度的計算，不同的學(xué)者提出了不同的方法。如文獻(xiàn)［3］主要依據(jù)分詞以及詞性標(biāo)注技術(shù)對句子表面相似度進(jìn)行了計算。文獻(xiàn)［4］通過比較兩句相同詞的個數(shù)及其位置關(guān)系，得到兩句的詞形相似度和詞序相似度，再通過詞形相似度和詞序相似度計算句子的相似度。文獻(xiàn)［5］主要根據(jù)編輯距離與依存文法對句子進(jìn)行相似度計算。文獻(xiàn)［6］則是基于知網(wǎng)的句子相似度計算方法，而文獻(xiàn)［7］中基于本體的句子相似度方法與文獻(xiàn)［6］有異曲同工之效。由于對句子的分析角度不同，可以將句子相似度計算方法分為2種，一種是基于向量空間模型的計算方法，也就是句子表面相似度的計算方法，另一種是基于句法和語義的句子相似度計算方法。由于在信息檢索中用戶使用的查詢語句較短，有時還缺乏必要的語境，因此單純的使用關(guān)鍵詞進(jìn)行匹配并不能令人滿意。為解決這一問題，有學(xué)者提出了查詢擴(kuò)展技術(shù)［8］，即在對查詢語句進(jìn)行擴(kuò)展的基礎(chǔ)上再進(jìn)行句子相似度的計算。由于以上方法中對句子主成分的分析較少且不明確，因此文中依據(jù)句法依存樹對用戶問句進(jìn)行了處理，并依此來確定句子中的關(guān)鍵字詞以及其對應(yīng)的權(quán)重。同時，文中在句子相似度計算方面提出了一種新的基于二叉樹帶權(quán)路徑長度計算的方法。二叉樹的帶權(quán)路徑長度計算即是計算每個葉子節(jié)點(diǎn)的權(quán)值與結(jié)點(diǎn)到根結(jié)點(diǎn)距離的乘積之和，而在文中中，葉子節(jié)點(diǎn)的權(quán)值即為句子中關(guān)鍵詞的權(quán)重。最后計算句子間二叉樹帶權(quán)路徑長度的比值，得到句子間的相似度。由于在信息檢索中主要還是對有標(biāo)題且標(biāo)題總結(jié)性比較強(qiáng)的信息進(jìn)行檢索，所以文中在對關(guān)鍵字詞進(jìn)行擴(kuò)展時只考慮了同義詞近義詞擴(kuò)展。

1 算法原理

1.1 句子分析以及關(guān)鍵詞提取

首先對句子進(jìn)行依存句法分析，依存句法分析是將句子由一個線性序列轉(zhuǎn)化為結(jié)構(gòu)化的依存樹，即利用依存標(biāo)注表示出各詞匯之間的關(guān)系，同時對每個詞匯做了詞性標(biāo)注、詞義消歧、命名實(shí)體等處理［9］。如句子“劉德華的電影有哪些”經(jīng)過分詞處理、詞性標(biāo)注以及句法分析后的結(jié)果如表1。

表1 例句處理結(jié)果

句子的依存樹結(jié)構(gòu)如圖1所示。

圖1 句子的依存樹結(jié)構(gòu)

國內(nèi)部分學(xué)者研究得出有90%左右的用戶輸入的中文檢索單字為2～6個，其中2個字詞的占58%，4個字詞的約占18%，3個字詞約占14%。因此可以只對中文單句進(jìn)行分析。

根據(jù)語言學(xué)知識，對中文單句進(jìn)行分析可知，除了單個字詞外，幾乎每個句子都包含主語、謂語、賓語這些主要成分，有些還包含了修飾的部分，即定語、狀語、補(bǔ)語等。句子的主要成分毫無疑問對句子的貢獻(xiàn)度是比較大的，而這些成分中的詞不可能包含所有詞性的詞，如連詞等，因此，在保留句子關(guān)鍵詞時，選擇了保留部分詞性的詞，保留規(guī)則如下:

1)保留詞性標(biāo)注為 a、b、g、i、j、m、x、r、ws、v 以及以n開頭的詞語，但一般不保留動詞“是、有”等。

2)若句首的詞語的依存關(guān)系為HED，且詞性為v的則去除。

由于在句子中，謂語是起到了承上啟下的橋梁作用，而主語和賓語對句子的語義貢獻(xiàn)度較大，因此，選出貢獻(xiàn)度最大的詞語對計算句子相似度有很大的幫助，查找貢獻(xiàn)度最大的詞語的規(guī)則如下:

1)若句中含依存關(guān)系為SBV的詞，且詞性標(biāo)注不為r，則為貢獻(xiàn)度最大的詞語。

2)若句中不含依存關(guān)系為SBV的詞，含有依存關(guān)系為POB的詞，則依存關(guān)系為POB的詞為貢獻(xiàn)度最大的詞語。

3)若依存關(guān)系不包含SBV和POB的詞，含有依存關(guān)系為VOB且詞性標(biāo)注是以n開頭的詞，則為貢獻(xiàn)度最大的詞語。

4)若句子中不包含依存關(guān)系為SBV、POB以及VOB的詞，且依存關(guān)系為HED的詞的詞性不為動詞或疑問代詞，則該詞為貢獻(xiàn)度最大的。如句子“劉德華的電影有哪些”經(jīng)過處理后保留關(guān)鍵詞“劉德華”、“電影”、“哪些”，根據(jù)以上規(guī)則可知貢獻(xiàn)度最大的關(guān)鍵詞為“電影”。

1.2 樹的帶權(quán)路徑長度算法

帶權(quán)路徑長度(weighted path length of tree，WPL)算法是用在樹結(jié)構(gòu)中的一種算法，該算法包含了結(jié)點(diǎn)的權(quán)值、結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)的帶權(quán)路徑長度。

結(jié)點(diǎn)的權(quán)值:在一些應(yīng)用中賦予樹中結(jié)點(diǎn)的一個有某種意義的實(shí)數(shù)。

結(jié)點(diǎn)到樹根之間的路徑長度:樹根層數(shù)為0時，結(jié)點(diǎn)所在的層數(shù)。

結(jié)點(diǎn)的帶權(quán)路徑長度:結(jié)點(diǎn)到樹根之間的路徑長度與該節(jié)點(diǎn)權(quán)值的乘積。

WPL:樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和。

文中主要用到了最優(yōu)二叉樹的帶權(quán)路徑長度的計算方法。

如一組數(shù)(2，4，5，7，8，9)形成的最優(yōu)二叉樹結(jié)構(gòu)如圖2所示。

圖2 最優(yōu)二叉樹結(jié)構(gòu)

該二叉樹由下而上葉子結(jié)點(diǎn)的權(quán)值是由小到大的。圖2中二叉樹的帶權(quán)路徑長度計算公式為

2 實(shí)現(xiàn)方法

方法流程如圖3。算法實(shí)現(xiàn)主要步驟包括句子預(yù)處理、關(guān)鍵詞權(quán)重設(shè)置、關(guān)鍵詞擴(kuò)展、二叉樹帶權(quán)路徑長度計算以及問句與標(biāo)題句的相似度計算。

1)句子預(yù)處理:該部分包含了分詞處理和句法分析2個部分，主要是對用戶問句中關(guān)鍵詞權(quán)重的設(shè)置做基礎(chǔ)。

2)關(guān)鍵詞權(quán)重設(shè)置:根據(jù)問句中關(guān)鍵詞的詞性以及在句子中的依存關(guān)系，為每個關(guān)鍵詞設(shè)置權(quán)重。

3)關(guān)鍵詞擴(kuò)展:由于有些詞有同義詞和近義詞，為了更準(zhǔn)確的與標(biāo)題句進(jìn)行相似度的計算，對問句中的關(guān)鍵詞進(jìn)行了相應(yīng)的同義詞近義詞擴(kuò)展。

4)二叉樹帶權(quán)路徑長度計算:將用戶中的所有關(guān)鍵詞對應(yīng)的權(quán)重以最優(yōu)二叉樹的形式表示出來，并計算該二叉樹的帶權(quán)路徑長度。

5)問句與標(biāo)題句的相似度計算:根據(jù)問句的帶權(quán)路徑長度和標(biāo)題句中包含的關(guān)鍵詞，對問句與標(biāo)題句之間的相似度進(jìn)行計算。

圖3 算法實(shí)現(xiàn)步驟

2.1 句子預(yù)處理

在對用戶問句進(jìn)行句法分析之前，要對問句進(jìn)行分詞以及詞性標(biāo)注處理，同時也要對標(biāo)題句進(jìn)行分詞處理，文中主要運(yùn)用了西南交通大學(xué)思維與智慧研究所的耶寶分詞系統(tǒng)。由于耶寶分詞具有超大規(guī)模的語料庫和分詞詞庫，以及較準(zhǔn)確的歧義和未登錄詞識別，分詞準(zhǔn)確率較高，因此能對句子進(jìn)行較準(zhǔn)確的分詞［10］，為后面句子相似度的計算做了良好的鋪墊。

文中在使用分詞系統(tǒng)以及句法分析系統(tǒng)時也做了一些處理。由于西南交大的分詞系統(tǒng)中應(yīng)用的是北大的詞性標(biāo)注，而哈工大的句法分析系統(tǒng)應(yīng)用的是863詞性標(biāo)注，所以在用西南交大的分詞系統(tǒng)進(jìn)行分詞后又將詞性標(biāo)注轉(zhuǎn)換成了哈工大句法分析系統(tǒng)中的詞性標(biāo)注，以保證依存關(guān)系的準(zhǔn)確性。

2.2 關(guān)鍵詞權(quán)重的設(shè)置

由主觀判斷，認(rèn)為一個句子中貢獻(xiàn)度最大的詞的權(quán)重將占整個句子權(quán)重的一半以上，而疑問詞對句子信息的貢獻(xiàn)度極小，可賦予一個很小的權(quán)重值，并經(jīng)過多個單句之間相似度計算的測試，對關(guān)鍵詞的權(quán)重設(shè)置運(yùn)用了如下一些規(guī)則，即句中若含有貢獻(xiàn)度最大的詞，根據(jù)經(jīng)驗(yàn)值將其權(quán)重設(shè)置為0.5，若剩下的關(guān)鍵詞中含有詞性為r或v的個數(shù)為m，設(shè)每個詞的權(quán)重為x，其余的詞個數(shù)為n，設(shè)權(quán)重為y，則求權(quán)重公式為

2.3 同義詞近義詞擴(kuò)展

文中對用戶問句進(jìn)行處理后提取句中關(guān)鍵詞，并找出每個關(guān)鍵詞的同義詞、近義詞，組成不同的向量，關(guān)鍵詞與其同義詞對應(yīng)的權(quán)重相同。其中，同義詞、近義詞的擴(kuò)展主要依據(jù)一個已經(jīng)建立的同義詞、近義詞庫，該庫中的同義詞、近義詞不僅包含了同義詞詞林中的同義詞近義詞對，同時也包含了在大量的百度百科詞條中基于規(guī)則抽取出的同義詞對。

2.4 問句的二叉樹帶權(quán)路徑長度計算

根據(jù)式(2)計算出所有關(guān)鍵詞的權(quán)重，然后根據(jù)權(quán)重向量進(jìn)行問句的二叉樹帶權(quán)路徑長度的計算。計算方法如下:

1)若問句中只有1個或2個詞，則設(shè)其二叉樹的帶權(quán)路徑長度qw=1。

2)若問句中的詞如圖4所示含有2個以上關(guān)鍵詞，則可將其左邊的向量轉(zhuǎn)化成最優(yōu)二叉樹，然后計算二叉樹的帶權(quán)路徑長度qw。

2.5 問句與標(biāo)題句之間的相似度計算

對檢索內(nèi)容的標(biāo)題進(jìn)行處理，處理方法如下:

1)若標(biāo)題中不含有問句中的關(guān)鍵詞或關(guān)鍵詞的同義詞近義詞，則其二叉樹的帶權(quán)路徑長度aw=0。

2)若標(biāo)題中只含1個詞或只含2個詞且均為問句中的關(guān)鍵詞或關(guān)鍵詞的同義詞，則其帶權(quán)路徑長度aw=qw。

3)若標(biāo)題中含有2個以上問句中的關(guān)鍵詞或關(guān)鍵詞的同義詞近義詞，去除句中停用詞后總的詞的個數(shù)為i，與問句中關(guān)鍵詞或關(guān)鍵詞的同義詞近義詞相同的詞數(shù)為j，則標(biāo)題中詞的權(quán)重設(shè)置方法如下:

a)與問句中關(guān)鍵詞或關(guān)鍵詞的同義詞相同的詞的權(quán)重為

weightq(m)為與問句中關(guān)鍵詞或關(guān)鍵詞的同義詞相同的詞在問句中的權(quán)重。

b)與問句中關(guān)鍵詞或關(guān)鍵詞的同義詞不相同的詞的權(quán)重如下:

根據(jù)式(1)可計算出此標(biāo)題句對應(yīng)的二叉樹帶權(quán)路徑長度aw

最后把標(biāo)題句的權(quán)重視為其與問句之間的句子相似度Sim(a)。

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

3.1 實(shí)驗(yàn)步驟

實(shí)驗(yàn)主要步驟如下:

1)運(yùn)用分詞系統(tǒng)以及句法分析系統(tǒng)對問句進(jìn)行分析;

2)對問句中的關(guān)鍵詞進(jìn)行擴(kuò)展，并設(shè)置權(quán)重，計算句子的二叉樹帶權(quán)路徑長度;

3)對標(biāo)題句進(jìn)行去停用詞以及提取關(guān)鍵詞處理;

4)對標(biāo)題中的詞設(shè)置權(quán)重，并計算對應(yīng)的二叉樹帶權(quán)路徑，然后得到句子對應(yīng)的權(quán)重，即與問句之間的相似度。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

從哈工大信息檢索研究室問答系統(tǒng)問題集中抽取104個問句，并對這104句中的關(guān)鍵詞進(jìn)行同義詞近義詞擴(kuò)展，每個問句擴(kuò)展出一個或以上相同相似的句子，然后在保證每個句子都有相似句子的情況下保留530個問句形成新的問題集。

由于百度是最大的中文搜索引擎，因此文中選擇在百度搜索引擎中為這530個句子搜索出相應(yīng)的答案，由于搜索結(jié)果的量較大，且統(tǒng)計用戶翻閱答案的量是有限的，因此文中只選取了每個問題對應(yīng)的搜索結(jié)果的前200個，又由于百度搜索存在競價排名，所以會在搜索結(jié)果中的最前面出現(xiàn)廣告干擾，文中將予以去除。同時所得搜素結(jié)果將包含標(biāo)題句、網(wǎng)頁鏈接以及對應(yīng)網(wǎng)頁的主要內(nèi)容。其中主要內(nèi)容的抽取文中首先利用正則表達(dá)式將網(wǎng)頁中主要部分即＜body＞＜/body＞中的內(nèi)容抽取出來，然后對已抽取內(nèi)容進(jìn)行分詞以及詞性標(biāo)注處理，只保留詞性標(biāo)注不為 vyou、vshi且不以 w、u、c、p、d 以及 r開頭的詞，由于除了主要內(nèi)容可能會含有英文單詞外，網(wǎng)頁源碼中也存在很多英文單詞，因此在處理詞性標(biāo)注以x開頭的詞時，根據(jù)網(wǎng)頁結(jié)構(gòu)，只保留了其前面詞性標(biāo)注以及后面的詞性標(biāo)注不同時為w或x的詞，一般中文網(wǎng)頁中大量的英文介紹內(nèi)容很少，因此這種方法對主要內(nèi)容的抽取影響不大，但網(wǎng)頁噪聲如廣告等會對網(wǎng)頁主要內(nèi)容產(chǎn)生一些影響，文中不對該方面做深入研究。然后經(jīng)過網(wǎng)頁去重處理，最后形成含502173個搜索結(jié)果的信息檢索結(jié)果集。

當(dāng)用戶提出問題時，首先運(yùn)用關(guān)鍵詞匹配以及tfidf算法對檢索結(jié)果集進(jìn)行檢索和排序，然后再用文中算法對已檢索結(jié)果進(jìn)行二次排序。

文中采取平均查全率(mean of average recall，MAR)，查準(zhǔn)率(mean of average precision，MAP)以及前30個返回的網(wǎng)頁的查準(zhǔn)率(precision of return results of top 30，PRRT30)作為檢索結(jié)果的評測標(biāo)準(zhǔn)。

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

可先用如下實(shí)驗(yàn)結(jié)果來說明文中的句子相似度計算方法的效果。用戶問句為“兒童電影有哪些”。文中根據(jù)搜索引擎給出的搜索結(jié)果設(shè)置了幾個標(biāo)題句，并利用不同方法對標(biāo)題句與問句的相似度進(jìn)行了計算與分析，計算結(jié)果如表2所示。

表2 相似度對比

方法1是一種基于詞語共現(xiàn)統(tǒng)計的方法，利用了北大計算語言所提出的一種句子相似度計算公式:2c/(m+n)，式中:m、n分別為2個句子的詞的個數(shù)，c是2個句子中相同詞的個數(shù)［11］。

方法2是一種基于知網(wǎng)的句子相似度計算方法，利用了文獻(xiàn)［6］中句子的表層相似度與語義偏移量相似度相結(jié)合的方法，其中用到的詞語間相似度利用了文獻(xiàn)［12］的詞語間語義相似度的計算方法。

方法3是文中句子相似度計算方法，即對句子進(jìn)行了分詞，詞性標(biāo)注以及句法分析處理后，對句中的關(guān)鍵詞進(jìn)行抽取以及加權(quán)處理，然后基于帶權(quán)路徑長度計算方法計算句子間的相似度。

文中是對搜索結(jié)果進(jìn)行二次排序，為獲取更準(zhǔn)確的信息，只對問句中的關(guān)鍵詞做了同義詞以及近義詞擴(kuò)展處理。

對表2進(jìn)行分析可知，方法1中從標(biāo)題句6到標(biāo)題句9與問句1的相似度均為0，這顯然是不合理的，因?yàn)閺臉?biāo)題句6到標(biāo)題句8中均含有問句中貢獻(xiàn)度最大的詞“電影”的同義詞，而標(biāo)題句9則含有“兒童”的同義詞，方法3即文中方法用了關(guān)鍵詞的同義詞近義詞擴(kuò)展的方法，使以上含同義詞近義詞的句子之間的相似度計算結(jié)果更合理。標(biāo)題句2在語義上與問題句1的相似度更大，因?yàn)椴]有其他的限定詞語，而標(biāo)題句3中就含有限定詞“經(jīng)典”，所以標(biāo)題句2與問句1的相似度應(yīng)大于標(biāo)題句3與問句1的相似度，而方法2中卻是相反的，同時在方法2中標(biāo)題句9與問句1之間的語義相似度和標(biāo)題句10與問句1之間的語義相似度太大，而實(shí)際上標(biāo)題句10與問句之間幾乎沒有聯(lián)系，因此方法2是不符合實(shí)際的，文中方法則利用詞性標(biāo)注以及句法分析對句子進(jìn)行分析處理，并采用二叉樹帶全路徑長度計算方法對句子相似度進(jìn)行計算使以上句子之間的語義相似度更符合人們的直觀感受，如標(biāo)題句10與問句1之間的相似度就比較合理。由以上分析可以看出，文中提出的計算方法更符合實(shí)際，具有一定的實(shí)用性。

基于已處理的數(shù)據(jù)集對文中方法進(jìn)行評測，評測結(jié)果如表3所示。在未對問句進(jìn)行擴(kuò)展時，檢索結(jié)果的查全率、查準(zhǔn)率以及前30個檢索結(jié)果的查準(zhǔn)率較低，而對問句進(jìn)行擴(kuò)展后，都有所提高，最后再用文中方法對檢索結(jié)果進(jìn)行二次排序，在查全率不變的情況下檢索結(jié)果的查準(zhǔn)率有所提高。這說明文中方法在保證信息檢索結(jié)果的查全率的情況下，能有效地提高信息檢索結(jié)果的查準(zhǔn)率，是可行的。

表3 評測結(jié)果對比

4 結(jié)束語

句子相似度的計算在自然語言處理領(lǐng)域中起到了不可或缺的作用，在文本聚類、機(jī)器問答等領(lǐng)域也占有重要地位。文中在對問句進(jìn)行分詞以及句法分析處理的基礎(chǔ)上，利用了二叉樹的帶權(quán)路徑長度的計算方法來計算問句與檢索內(nèi)容的標(biāo)題句間的相似度，對檢索結(jié)果進(jìn)行了二次排序。由實(shí)驗(yàn)結(jié)果可知，文中提出的句子相似度計算方法比較符合人們的主觀判斷，能夠很好地被運(yùn)用到信息檢索中檢索結(jié)果的二次排序中去。在對句子處理方面文中運(yùn)用到了句法分析系統(tǒng)，而句法分析系統(tǒng)分析句子結(jié)果的準(zhǔn)確性和處理句子的速度都存在一些問題，因此文中在問句的處理上還存在一定的局限性。在下一步的工作中準(zhǔn)備用其他的方法對問句中貢獻(xiàn)度大的詞進(jìn)行提取。

［1］李立.中文信息檢索系統(tǒng)研究［D］.武漢:華中師范大學(xué)，2008:15-28.

［2］王品，黃廣源.信息檢索中的句子相似度計算［J］.計算機(jī)工程，2011，37(12):38-40.

［3］周法國，楊炳儒.句子相似度計算新方法及在問答系統(tǒng)中的應(yīng)用［J］.計算機(jī)工程與應(yīng)用，2008，44(1):165-167.

［4］呂學(xué)強(qiáng)，任飛亮，黃志丹，等.句子相似模型和最相似句子查找算法［J］.東北大學(xué)學(xué)報:自然科學(xué)版，2003，24(6):531-534.

［5］劉寶艷，林鴻飛，趙晶.基于改進(jìn)編輯距離和依存文法的漢語句子相似度計算［J］.計算機(jī)應(yīng)用與軟件，2008，25(7):33-34.

［6］程傳朋，吳志剛.一種基于知網(wǎng)的句子相似度計算方法［J］.計算機(jī)工程與科學(xué)，2012，34(2):172-175.

［7］劉宏哲.一種基于本體的句子相似度計算［J］.計算機(jī)科學(xué)，2013，40(1):251-256.

［8］LISA BALLEDTEROS，BRUCE CROFT W.Statistical methods for cross-language information retrieval［M］.Boston:Kluwer Academic Publisers，1998:23-40.

［9］CHE W X，LI Z H，LIU T.A Chinese language technology platform［C］//Proc of the Coling 2010，Beijing.2010:13-16.

［10］西南交通大學(xué)中文分詞系統(tǒng)［CP/OL］.［2013－12－25］.http://www.yebol.com.cn.

［11］王榮波，池哲儒，常寶寶，等.基于詞串力度及權(quán)值的漢語句子相似度衡量［J］.計算機(jī)工程，2005，31(13):142-144.

［12］夏天.漢語詞語語義相似度計算研究［J］.計算機(jī)工程，2007，33(6):191-193.