魏 露，李書琴，李偉男，李新樂

（西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊凌712100）

0 引 言

跨語言查詢擴展主要是為了解決詞不匹配問題，在初始查詢詞的基礎(chǔ)上，加入若干相關(guān)詞，使文檔相關(guān)性信息更全面［1，2］。文獻 ［3，4］使用基于潛在語義分析的跨語言查詢擴展方法進行檢索，減輕了翻譯的歧義性。但是，該方法還存在一定缺陷。首先，在建立雙語空間時，用奇異值分解法對矩陣進行分解，得到的矩陣元素存在負數(shù)，致使一些有用的語義信息丟失，降低了檢索精度。其次，降維時根據(jù)經(jīng)驗來選取1個維度值d，d值的選取對檢索結(jié)果有重要影響，若d值偏小，則得到的雙語空間丟失語義信息；若d值偏大，則計算量加大，且會出現(xiàn)過擬合現(xiàn)象［5］。最后，用跨語言擴展避免擴展詞翻譯帶來的歧義問題時，使用k－means進行聚類，k－means算法雖然有簡單快速等優(yōu)點，但是它對于噪聲和孤立點是敏感的，少量該類型數(shù)據(jù)就會對平均值產(chǎn)生極大影響，從而降低檢索精度。

本文跨語言查詢擴展研究將對以上不足進行改進。首先，采用奇異值分解 （singular value decomposition，SVD）與非負矩陣分解 （non－negative matrix factorization，NMF）［6］相結(jié)合的方法對矩陣進行分解，使得到的雙語空間不含負數(shù)，避免了因為矩陣中存在負數(shù)而導(dǎo)致語義的信息丟失。其次，提出擇優(yōu)模型，建立多個d值模型，再選取最優(yōu)的模型進行計算，以此降低因d值過大或過小而導(dǎo)致的信息丟失和過擬合問題。最后，使用k－medoid進行聚類，避免聚類過程中出現(xiàn)孤立點和噪聲，提高擴展文本集合的精度，進而提高檢索精度。

1 擇優(yōu)模型

建立雙語空間時，需要對最初的詞條文本矩陣進行降維，通常降維因子d都是在100～300中選取單一值，導(dǎo)致語義丟失或過擬合問題。擇優(yōu)模型是指在100～300之間選取多個維度值d分別建模，給每個模型都賦予一個信任度AIC （akaike information criterion），AIC主要是用來計算總文檔的相似度，選擇相似度最大時的d作為降維的維度，采用擇優(yōu)模型可以彌補單一維度值的缺陷。AIC指多個不同維度模型與未知準(zhǔn)確模型之間的距離［7］

式中：l——模型中的參數(shù)量，l＝rd＋l－d （d－l）／2，r——矩陣M的秩。lnL （Ud｜M）——d維潛在語義模型的對數(shù)似然函數(shù)

lnL（Ud｜M）＝λ1＋ … ＋λd－nlogZ（Ud｜M） （2）式中：Ud——矩陣M進行SVD分解 （M＝USVT）和NMF分解 （M＝UV）后的矩陣U。λd——矩陣 M’M的前d個特征值，Z——分割函數(shù)

求相似度時，設(shè)A為包含多個不同d維模型的集合，然后根據(jù)A分別計算SVD和NMF分解以及2種方法結(jié)合時查詢文檔的相似度

式中：ωd——d維SVD矩陣分解模型的信任度，與AIC成反比，Ud、Sd和Vd——奇異值分解降維后的矩陣。

式中：ωd——d維NMF矩陣分解模型的信任度，Ud——非負矩陣分解降維后的矩陣

式中：ωd1和ωd2——d維SVD矩陣分解模型d維NMF矩陣分解模型的信任度。

2 跨語言查詢擴展

跨語言查詢擴展［8］整體流程可分為以下幾個部分，本體 （ontology）擴展、跨語言擴展、翻譯、權(quán)重計算以及檢索。具體流程如圖1所示。

2.1 ontology擴展

本文使用英文的 WordNet［9］和中文的同義詞林［10］2種語義詞典來構(gòu)建查詢詞的擴展詞，步驟如下：

步驟1 采用WordNet和同義詞林作為本體擴展資源，使用protege本體構(gòu)建工具構(gòu)建一個簡單本體庫；

步驟2 在本體庫中找到查詢詞ti，根據(jù)實體相關(guān)度計算公式計算各詞與ti之間相關(guān)度［11］，得到與ti相關(guān)的概念集Seti，計算Seti中的每個概念與ti之間的相似度，若相似度大于某一閾值 （此處取0.7），則把Setij加入到ti的候選擴展概念集中；

步驟3 重復(fù)步驟2至原始查詢式S0＝ ｛t1t2…tm｝中所有查詢詞的候選擴展概念集均被找到；

步驟4 用邏輯或把所有的查詢詞和它們的候選擴展概念集結(jié)合起來，利用FirteX2開源搜索引擎檢索出初始結(jié)果；

步驟5 選出初始查詢結(jié)果中的前N篇文檔構(gòu)成局部文檔集P，利用局部共現(xiàn)分析法計算詞語—概念對的共現(xiàn)度權(quán)值；

步驟6 對候選擴展詞組進行篩選，把符合條件的擴展詞作為qi的ontology擴展，并加入到初始查詢式中。擴展后的查詢式為

S1＝ ｛t1t2…tmtm＋1，…tm1，m ≤m1≤2 m｝

2.2 建立雙語空間

由語料得到最初的中英詞條文本矩陣M

權(quán)值cij和eij結(jié)合使用對數(shù)詞頻法和熵方法

式中：tfij——詞i在文檔j中出現(xiàn)的頻度，gfi——詞i在整個文檔中的出現(xiàn)頻度，pij＝tfij／gfi，n——總文檔數(shù)。

結(jié)合SVD和NMF對M進行分解，采用擇優(yōu)模型對M進行建模，選取相似度最大時的d值，截取V的前d列，最終得到雙語空間Vd。

2.3 跨語言擴展

跨語言擴展需要用聚類提高擴展精度，本文采用k－me－doid聚類算法，它屬于劃分方法，在存在孤立點的情況下，算法魯棒性好［12］。

跨語言擴展是在ontology擴展的基礎(chǔ)上，結(jié)合雙語空間和k－medoid聚類來完成，具體步驟如下：

步驟1 將ontology擴展得到的查詢式S1用fold－in方法構(gòu)成d維文本向量qd；

步驟2 計算Vd中各文本與qd之間的相似度，找出前T個相似度最大的文本；

步驟3 對這T個文本進行k－medoid聚類，找出和qd距離最近的簇，將該簇中的所有文本形成雙語查詢擴展文本集合ET＝ ｛d1，d2，…，dt，t＜T｝；

步驟4 對ET中的所有目標(biāo)語言詞匯用熵方法進行全局信息計算找出最大的me個詞，記為

S＇＝ ｛q1，q2，…，qme｝

S’就是我們得到的跨語言查詢擴展詞組。

2.4 翻 譯

S’已經(jīng)是目標(biāo)語言形式的查詢式，所以只要對S1進行翻譯，借助雙語詞典，使用雙向翻譯模型［13］對S1進行翻譯，得到目標(biāo)語種查詢式

2.5 權(quán)重計算

在跨語言查詢擴展中，原始查詢S0最直接體現(xiàn)查詢意圖，為之分配最大權(quán)重。擴展詞指的是與原查詢相關(guān)的語詞，它是原查詢的語義上的補充和完善，其重要性比原查詢語詞稍低。為了體現(xiàn)這種思想，在進行查詢擴展時，本文將原查詢詞的權(quán)重值置為2，擴展詞的權(quán)重采用Rocchio方法，為0到1之間的值。

2.6 檢 索

把跨語言擴展得到的查詢詞組S’加入到S2中，得到最終的目標(biāo)語言查詢式

3 實驗設(shè)計和結(jié)果分析

實驗所用的數(shù)據(jù)是從中國知網(wǎng)等數(shù)據(jù)庫中隨機抽取的1000篇農(nóng)業(yè)專利相關(guān)論文中的中英文摘要，將這些信息建立成雙語空間，用于查詢、翻譯和擴展。

評測指標(biāo)MAP指查詢集中每個查詢準(zhǔn)確率的算術(shù)平均值，輔助評測指標(biāo)P＠X指某個查詢S檢索出前X篇文檔的準(zhǔn)確率。

本文共設(shè)計5個實驗 （NMF，C－B，NMFC－B，K－MD，INTEG）和一個對比實驗SVD。SVD采用最傳統(tǒng)的基于潛在語義分析方法進行跨語言查詢擴展；NMF降維時結(jié)合使用SVD矩陣分解與NMF矩陣分解；C－B使用擇優(yōu)模型計算5個模型 （d＝100，d＝150，d＝200，d＝250，d＝300）的相似度，并且選取相似度最大時的d值作為降維的維度；NMFC－B使用了C－B的方法，同樣建立5個模型 （d＝100，d＝150，d＝200，d＝250，d＝300），但同時采用了NMF非負矩陣分解的方法。K－MD和SVD的區(qū)別在于，它在跨語言擴展時用k－medoid聚類代替k－means聚類提高聚合精度；INTEG結(jié)合NMFC－B和K－MD方法。實驗結(jié)果見表1、表2。

表1 英文檢索中文準(zhǔn)確率

表2 中文檢索英文準(zhǔn)確率

在召回不同條記錄時，使用不同方法對應(yīng)的準(zhǔn)確率情況見表1、表2，其隨召回條數(shù)變化趨勢如圖2、圖3所示。

實驗結(jié)果表明，使用 NMF、C－B、NMFC－B、K－MD、INTEG均能提高跨語言查詢擴展精度，INTEG效果最佳，下面具體分析其原因。

實驗SVD采用傳統(tǒng)基于潛在語義分析的查詢擴展模型，奇異值分解時存在負數(shù)，造成信息表示不全面；d值選取單一，不能使所有查詢都最優(yōu)，d值過大會導(dǎo)致計算量大，從而出現(xiàn)過擬合現(xiàn)象，d值過小則丟失很多有用的信息；使用k－means聚類，產(chǎn)生噪聲和孤立點。在多重因素的影響下，檢索精度降低。

圖2 英文檢索中文召回準(zhǔn)確率曲線

圖3 中文檢索英文召回準(zhǔn)確率曲線

實驗C－B中，擇優(yōu)模型選取不同的d值，建立多個模型，允許每個模型都對相關(guān)文檔的相似度產(chǎn)生影響，給每個模型都賦予一個信任度進而計算整體文檔相似度，它避免了信息丟失和過擬合問題，降低了單一模型的風(fēng)險，檢索精度自然也得到了提升。

實驗NMFC－B運用模型擇優(yōu)的思想，通過每個模型的信任度將2種矩陣分解模型相結(jié)合，綜合考慮2種矩陣分解方法的結(jié)果。由于NMF分解后的矩陣不存在負值，語義結(jié)構(gòu)向量表示的物理意義明確，不會丟失語義信息。因此，將2種矩陣分解模型結(jié)合起來后，能較好地彌補SVD矩陣分解模型存在的語義結(jié)構(gòu)向量表示受負值影響所造成的誤差。

實驗K－MD不用k－means算法進行聚類，而采用k－medoid對文本進行聚類，這種方法避免了SVD中存在的噪聲和孤立點問題，提高了檢索精度。

實驗INTEG結(jié)合了以上所有方法的優(yōu)點，既避免了信息丟失和過擬合，又消除了噪聲和孤立點，因此精度最高。

4 結(jié)束語

本文使用潛在語義跨語言查詢擴展方法對農(nóng)業(yè)專利進行擴展查詢，結(jié)合NMF和SVD矩陣分解方法使獲得的雙語空間不含負數(shù)，極大削弱了存在負值時語義表示不全面帶來的負面影響；加入擇優(yōu)模型，消除了信息不全面與過擬合現(xiàn)象；使用k－medoid聚類對文本進行聚類，消除了噪聲和孤立點。實驗結(jié)果表明，該改進方法能明顯提高檢索性能。

［1］QU Guozhong.Query expansion technology research ［D］.Wuhan：Huazhong Normal University：Computer Software and Theory，2007（in Chinese）.［瞿國忠.查詢擴展技術(shù)研究 ［D］.武漢：華中師范大學(xué)：計算機軟件與理論，2007.］

［2］LI Weijiang，ZHAO Tiejun，WANG Xiangang.A SMT－based approach for query expension in information retrieval ［J］.Journal of Electronics ＆ Information Technology，2008，30（3）：725－729 （in Chinese）.［李衛(wèi)疆，趙鐵軍，王憲剛.基于統(tǒng)計機器翻譯模型的查詢擴展 ［J］.電子與信息學(xué)報，2008，30 （3）：725－729.］

［3］WANG Yang.The intelligent search technology based on latent semantic analysis ［D］.Heilongjiang：Harbin Engineering University：School of Computer Science and Technology，2010（in Chinese）.［王洋.基于潛在語義分析的智能搜索技術(shù)研究［D］.黑龍江：哈爾濱工程大學(xué)：計算機科學(xué)與技術(shù)學(xué)院，2010.］

［4］BI Jianting，SU Yidan.Expansion method for languagescrossed query based on latent semantic analysis ［J］.Computer Engineering，2009，35 （10）：59－53 （in Chinese）.［閉劍婷，蘇一丹.基于潛在語義分析的跨語言查詢擴展方法 ［J］.計算機工程，2009，35 （10）：59－53.］

［5］NING Jian，LIN Hongfei.Cross－language information retrieval based on improved latent semantic indexing ［J］.Journal of Chinese Information Processing，2010，24 （3）：105－111 （in Chinese）.［寧健，林鴻飛.基于改進潛在語義分析的跨語言檢索 ［J］.中文信息學(xué)報，2010，24 （3）：105－111.］

［6］LI Ersen，ZHANG Baoming，YANG Na，et al.Discussion of the NMF’s application for hyperspectral imagery unmixing［J］.Bulletin of Surveying and Mapping，2011，57 （3）：7－10（in Chinese）.［李二森，張保明，楊娜，等.非負矩陣分解在高光譜圖像解混中的應(yīng)用探討 ［J］.測繪通報，2011，57（3）：7－10.］

［7］JIANG Hao，TONG Shenjia，LI Gang，et al.The simulation of wind speed time series by the AIC ［J］.Technology ＆ Economy in Areas of Communications，2008，47 （3）：10－11（in Chinese）.［姜浩，童申家，李綱，等.基于AIC準(zhǔn)則的脈動風(fēng)速時程模擬 ［J］.交通科技與經(jīng)濟，2008，47 （3）：10－11.］

［8］GUO Wen，CHEN Yidong，ZHAO Xin.Query expansion in cross－language information retrieval［J］.The Mind and Calculation，2009，3 （1）：1－8 （in Chinese）.［郭文，陳毅東，趙欣.跨語言信息檢索中的查詢擴展 ［J］.心智與計算，2009，3 （1）：1－8.］

［9］ZHAO Tianzhong，MIAO Zhuang，ZHANG Yafei，et al.Reusing WordNet for building domain ontology ［J］.Journal of System Simulation，2007，19 （19）：4583－4586 （in Chinese）.［趙天忠，苗壯，張亞非，等.基于WordNet重用的領(lǐng)域本體構(gòu)建方法 ［J］.系統(tǒng)仿真學(xué)報，2007，19 （19）：4583－4586.］

［10］TIAN Jiule，ZHAO Wei.Words similarity algorithm based on tongyici cilinin semantic Web adaptive learning system ［J］.Journal of Jilin University （Information Science Edition），2010，28 （6）：602－608 （in Chinese）.［田久樂，趙蔚.基于同義詞詞林的詞語相似度計算方法 ［J］.吉林大學(xué)學(xué)報（信息科學(xué)版），2010，28 （6）：602－608.］

［11］WANG Xuyang，XIAO Bo.Query expansion method based on ontology and local contextual analysis ［J］.Computer En－gineering，2012，38 （7）：57－59 （in Chinese）.［王旭陽，蕭波.基于本體和局部上下文分析的查詢擴展 ［J］.計算機工程，2012，38 （7）：57－59.］

［12］SUN Sheng，WANG Yuanzhen.Kernel－based adaptive K－medoid clustering ［J］.Computer Engineering and Design，2009，30 （3）：674－675 （in Chinese）.［孫勝，王元珍.基于核的自適應(yīng) K－medoid聚類 ［J］.計算機工程與設(shè)計，2009，30 （3）：674－675.］

［13］CHEN Qin.Cross language information retrieval establishment of bilingual dictionaries and translation method ［J］.Computer Applications and Software，2010，27 （7）：107－109 （in Chinese）.［陳琴.跨語言信息檢索中雙語詞典的建立和翻譯方法 ［J］.計算機應(yīng)用與軟件，2010，27 （7）：107－109.］