于麗， 亞森·艾則孜

(新疆警察學(xué)院 信息安全工程系， 新疆 烏魯木齊 830011)

采用相關(guān)反饋和文檔相似度的維吾爾語檢索詞加權(quán)方法

于麗， 亞森·艾則孜

(新疆警察學(xué)院 信息安全工程系， 新疆 烏魯木齊 830011)

針對維吾爾語Web文檔的有效檢索問題，提出一種基于相關(guān)反饋和文檔相似度的檢索詞加權(quán)方法.首先，對維吾爾語文檔進(jìn)行預(yù)處理，獲得相應(yīng)的詞干集.然后，當(dāng)用戶輸入多個檢索詞時，執(zhí)行初始檢索，并基于局部相關(guān)反饋思想提取出排名靠前的N個文檔.接著，利用TF-IDF算法計(jì)算檢索詞與反饋文檔之間的詞頻相似度，通過余弦距離計(jì)算文檔之間的相似度，并以此對檢索詞進(jìn)行兩次加權(quán).最后，根據(jù)加權(quán)后的檢索詞進(jìn)行文檔檢索.實(shí)驗(yàn)結(jié)果表明:該方法能夠準(zhǔn)確地檢索出用戶所需的文檔，并將其靠前排序.

維吾爾語； 文檔檢索； 檢索詞加權(quán)； 相關(guān)反饋； 文檔相似度

隨著國家對新疆地區(qū)投入的增加，大量維吾爾語等少數(shù)民族語種的文字信息開始以數(shù)字化形式呈現(xiàn)[1].若能迅速準(zhǔn)確地從維吾爾語書寫的Web文檔數(shù)據(jù)中獲得所需文檔，將會為新疆地區(qū)的文化發(fā)展作出一定的貢獻(xiàn).在文檔檢索中，用戶經(jīng)常會輸入多個檢索詞.在傳統(tǒng)檢索中，各檢索詞的權(quán)重一致.但由于用戶初始查詢時，其信息需求通常比較模糊，從而無法準(zhǔn)確地反饋實(shí)際需求的文檔[2].目前，提高檢索系統(tǒng)性能的方法主要包括概率和語言模型方法[3]、檢索分類方法[4]及檢索修正方法[5].其中，檢索修正技術(shù)是通過改善用戶的初始檢索詞來提高檢索性能.檢索修正技術(shù)[6]主要分為檢索詞重新加權(quán)(retrieval word re-weighting)和查詢擴(kuò)展(query expansion).檢索詞重新加權(quán)方法是根據(jù)初步檢索反饋信息，對用戶輸入的多個檢索詞進(jìn)行重要性加權(quán).針對檢索詞重新加權(quán)技術(shù)，學(xué)者提出了多種方法.Sembok等[7]基于N-gram的向量空間模型和語境分析對檢索詞進(jìn)行重新加權(quán)，但其沒有通過反饋機(jī)制獲得頂級文檔，而是計(jì)算所有文檔，計(jì)算量較大.Zhou等[8]提出了基于加權(quán)信息增益(weighted information gain,WIG)檢索詞重新加權(quán)方法，利用單一檢索詞和檢索詞組的距離特征估計(jì)頂級檢索文檔的質(zhì)量.然而，其沒有考慮不同反饋文檔對檢索詞加權(quán)具有不同的重要性.本文主要研究維吾爾語文檔檢索中的檢索詞重新加權(quán)技術(shù).

1 維吾爾語文檔預(yù)處理

維吾爾語文檔預(yù)處理主要包括文檔過濾和詞干提取.其中，文檔過濾用于過濾文檔中非維吾爾語文字和停用詞，通過和事先準(zhǔn)備好的停用詞表進(jìn)行比對，過濾掉停用詞.停用詞為對文檔主題沒有貢獻(xiàn)，不包含文章類別信息的詞，如介詞、副詞、代詞等.去掉停留詞能夠?qū)崿F(xiàn)特征降維，提高檢索精度[9].

表1 維吾爾詞語變體Tab.1 Uighur word variations

詞干提取過程中，根據(jù)維吾爾語單詞與單詞間的空格符進(jìn)行分詞.由于維吾爾語單詞是由字母拼寫而成的，通過將不同的詞綴粘貼到單詞的頭部實(shí)現(xiàn)語法功能，所以提取文檔中代表真實(shí)含義的詞匯是困難的.在維吾爾語中，同一詞干可以演變?yōu)楹芏嗖煌x的詞語，雖然這些詞語的詞形不同，但詞義卻不會有很大的區(qū)別[10].一個典型的例子，如表1所示.為了提取單詞的詞義，考慮特征的數(shù)量，以詞干(學(xué)校)作為特征詞，從文檔中提取出詞干集.

2 檢索詞重新加權(quán)方法

由于用戶輸入的檢索詞具有多個單詞，若按照均等權(quán)重搜索文檔，不能精確地搜索到所需文檔，所以，需要對用戶檢索詞進(jìn)行重新加權(quán).文中基于局部相關(guān)反饋思想，首先，根據(jù)初始檢索詞進(jìn)行檢索，并獲得初始檢索文檔；然后，在初始檢索文檔中選出排名靠前的N個頂級檢索文檔，并利用相關(guān)性模型計(jì)算各檢索詞與頂級文檔的相關(guān)性，以此對檢索詞進(jìn)行重要性重新加權(quán).

利用Q表示用戶輸入的初始檢索詞集，Q={q1,q2,…}，其中,qi(i=1,2,…)表示第i個檢索詞.將每個檢索詞qi的最終權(quán)重大小定義為

(2)

2.1 基于TF-IDF的第一次加權(quán)

(3)

2.2 基于文檔相似度的第二次加權(quán)

上述過程通過反饋文檔中檢索詞的TF-IDF信息對檢索詞進(jìn)行加權(quán)，只考慮了詞頻信息.不同的文檔與用戶實(shí)際需要的相關(guān)性不同，相關(guān)性較大的文檔給出的詞頻信息的重要性也應(yīng)該較大.為此，需要根據(jù)文檔與用戶的相關(guān)程度對該文檔給出的詞頻進(jìn)行進(jìn)一步加權(quán).

為了計(jì)算一個文檔在初始檢索中的重要性，通過評估每個文檔與檢索集合中其他文檔的距離，測量每個文檔與用戶所需信息之間的相關(guān)性.通過余弦相似度函數(shù)Sim()，計(jì)算每個頂級文檔與集合中其他頂級文檔之間的相似度，并以此給出第二次加權(quán)項(xiàng)，即

(4)

式(4)中：N為從初始檢索文檔中選取的頂級文檔個數(shù);dk和dj分別表示文檔集合中的第k個和第j個文檔的歐式向量，文中利用向量空間模型(vector space modal,VSM)對文檔進(jìn)行表示.將每個文檔dj作為一個向量dj=(w1,j，w2,j,wm,j,…,wM,j).其中,第m個組件wm,j為該文檔中第m個詞干的權(quán)重.第m個詞干的wm,j根據(jù)TF-IDF算法，通過計(jì)算該詞干在文檔dj中的詞頻和在反饋文檔中的逆文檔頻率獲得.Sim()用于評估dk和dj間相似度的余弦函數(shù)cos()，典型的余弦相似度表達(dá)式為

(5)

余弦相似度衡量的是向量空間2個向量的夾角，更加體現(xiàn)了方向上的差異[12-15].向量夾角的余弦值越大，表明兩者之間的相似度越大.余弦相似度的另一個重要特征是其獨(dú)立于文檔的長度.因此，余弦相似度在向量空間模型中是一種較為有效的相似性度量.

那么，利用式(2),(3)可得

最后，利用log標(biāo)準(zhǔn)化計(jì)算值,即

(7)

式(7)中：添加了一個常量值，這樣可以避免算法獲取零值.利用式(7)對檢索詞進(jìn)行了二次加權(quán)，其中,Wqi的大小與頂級文檔中檢索詞的頻率和整個集合中檢索詞的IDF成正比.

式(4)中，當(dāng)一個頂級文檔與所有其他頂級文檔的距離都較小時，該頂級文檔的權(quán)重較大.即一個文檔到聚類中心的距離越近，則這個文檔的權(quán)重值越大.但這是一個簡化的通用假設(shè)，即不考慮檢索的實(shí)際行為.當(dāng)模糊檢索結(jié)果中包含的內(nèi)容不止一個時，其結(jié)果集中可能包含多個文檔聚類.

為了解決這個問題，將與用戶初始檢索具有較高相似度的文檔分配一個較大的影響權(quán)重值，即該文檔對檢索詞加權(quán)的影響程度較大.因此，只要文檔的主題與初始檢索的主題足夠貼近，那么，不同聚類中的文檔可以獲取較大的權(quán)重.在這種直觀判斷基礎(chǔ)之上，可以將式(4)改寫為

式(8)中：I為初始檢索Q的歐式向量；變量K和L為常數(shù)，通過大量實(shí)驗(yàn)經(jīng)驗(yàn)，設(shè)定K=0.7，L=3.

將式(8)代替式(7)中的vdj，可得

(9)

為了減弱qi與dj關(guān)系對權(quán)重的影響，定義Ii為

Ii=I-{qi}.

()

因此，若將I中的qi省略，則可以獲取Ii.那么,在式(9)中利用Ii代替I,可以減少這種關(guān)系計(jì)算的次數(shù)，得到

(11)

最后，利用Wmax對每個檢索中的最終權(quán)重項(xiàng)歸一化到[0,1]，Wmax表示這次檢索中最大的權(quán)重項(xiàng).

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

3.1 實(shí)驗(yàn)設(shè)置

為了評估文中方法的性能，構(gòu)建一個實(shí)驗(yàn)平臺，配置有Intel酷睿i5 CPU，主頻為2.4 GHz，應(yīng)用Windows 7系統(tǒng)，利用Matlab 2011進(jìn)行實(shí)驗(yàn)，對檢索方法進(jìn)行性能評估.

對于維吾爾語的檢索應(yīng)用，目前還沒有可使用的標(biāo)準(zhǔn)文檔集.文中從人民網(wǎng)維吾爾語版和天山網(wǎng)等主流維吾爾語網(wǎng)站上收集了包含政治、經(jīng)濟(jì)、體育、旅游、教育和文化等領(lǐng)域的2 000篇文檔. 首先，對維吾爾語文檔集進(jìn)行預(yù)處理，為了方便后續(xù)處理，把文檔轉(zhuǎn)換成UTF-8二進(jìn)制編碼格式.然后，過濾掉文檔中的非維吾爾語字符和停用詞.預(yù)處理結(jié)束后，獲得一個初始詞集.最后，進(jìn)行詞干提取，將同一詞根演變而來的單詞進(jìn)行聚合，獲得文檔的詞干集合.

根據(jù)所收集的文檔內(nèi)容，自行擬定了10組檢索詞組，分別如表2所示.表2中：每個檢索詞組至少有30個文檔的內(nèi)容與其相關(guān).另外，為了評估檢索性能，通過人工方式，將與該10組檢索詞較為相關(guān)的30個文檔進(jìn)行相關(guān)性標(biāo)注，并標(biāo)注出最相關(guān)的10個文檔.

表2 10種檢索詞組Tab.2 Ten kinds of search team groups

3.2 實(shí)驗(yàn)指標(biāo)

為了評估檢索詞重新加權(quán)方法的有效性，將文中方法與平均權(quán)重的傳統(tǒng)檢索方法、文獻(xiàn)[11]提出的基于WIG檢索詞重新加權(quán)的檢索方法進(jìn)行比較.

實(shí)驗(yàn)最終檢索出30個相關(guān)文檔.以召回率和準(zhǔn)確率為評估標(biāo)準(zhǔn)，召回率為系統(tǒng)正確檢索的文檔占用戶所需文檔的比例，準(zhǔn)確度為系統(tǒng)正確檢索的文檔占系統(tǒng)所檢索出的文檔總數(shù)的比例.同時，統(tǒng)計(jì)了平均準(zhǔn)確率均值(mean average precision,MAP)和前10個檢索結(jié)果的準(zhǔn)確率(P@10).MAP為所有查詢的平均準(zhǔn)確率的算術(shù)平均，用來衡量檢索系統(tǒng)對多個查詢的平均檢索質(zhì)量；P@10為檢索結(jié)果的前10個位置中，出現(xiàn)標(biāo)注為最相關(guān)文檔的數(shù)量比例，最能反映實(shí)際應(yīng)用情況.另外，實(shí)驗(yàn)中的數(shù)據(jù)都為10次實(shí)驗(yàn)的平均值.

3.3 頂級文檔數(shù)量參數(shù)的確定

圖1 不同頂級文檔數(shù)量下的檢索性能Fig.1 Retrieval performance under different number of top documents

在初始檢索中，初始檢索反饋的頂級文檔數(shù)量N對檢索詞加權(quán)性能具有至關(guān)重要的影響.為此，首先進(jìn)行實(shí)驗(yàn)確認(rèn)最優(yōu)的N值.設(shè)置N的范圍為[10,100]，測試檢索性能，并記錄MAP值，結(jié)果如圖1所示.

由圖1可知：不同頂級文檔數(shù)量下的檢索性能不同.這是因?yàn)楫?dāng)反饋文檔數(shù)量較少時，檢索詞加權(quán)過程中可用的相關(guān)文檔數(shù)量太少，不能反映整個文檔集的屬性.當(dāng)反饋文檔數(shù)量較多時，會存在一些無關(guān)或噪聲文檔，使用這些文檔對檢索詞進(jìn)行加權(quán)會降低加權(quán)質(zhì)量.綜合考慮加權(quán)質(zhì)量和計(jì)算量，設(shè)定頂級文檔數(shù)量N取值為50.

3.4 實(shí)驗(yàn)比較

首先，在查詢文檔集中，輸入10種檢索詞組，利用文中方法，通過相關(guān)反饋和文檔相似度對檢索詞進(jìn)行重新加權(quán)，加權(quán)結(jié)果如表3所示.需要注意的是，各種檢索詞所分配的權(quán)重與文檔集內(nèi)容息息相關(guān).

表3 文中方法中檢索詞的加權(quán)值Tab.3 Weighted value of term in proposed method

在實(shí)驗(yàn)文檔集中，執(zhí)行3種檢索方法，記錄各種檢索詞組下的檢索準(zhǔn)確率，結(jié)果如表4所示.由表4可知：不同的檢索詞具有不同的檢索性能.這是因?yàn)椴煌臋z索詞組中，能夠反映用戶意圖的檢索詞信息清晰度不同.其中，文中方法在各個檢索詞組下的準(zhǔn)確率比WIG和傳統(tǒng)方法都高.這是因?yàn)槲闹懈鶕?jù)檢索詞和反饋文檔的相似度對檢索詞進(jìn)行了合理的重新加權(quán)，這有效提高了檢索精度.

傳統(tǒng)檢索、WIG方法和文中方法在文檔集上檢索的準(zhǔn)確率(ηa)-召回率(ηr)曲線，如圖2所示.由圖2可知：文中方法在相同召回率情況下，檢索精確率都高于其他方法.這說明對檢索詞合理加權(quán)能夠有效地提高檢索性能.

圖2 3種方法在文檔集上檢索的準(zhǔn)確率-召回率曲線Fig.2 Retrieval accuracy-recall rate curve of three methods on document collection

表4 3種方法在10種檢索詞組下的準(zhǔn)確率Tab.4 Accuracy of three methods in 10 kinds of retrieval words

3種檢索方法的MAP和P@10性能比較，如表5所示.由表5可知：文中方法可以有效地提升檢索性能.其中，文中方法的MAP達(dá)到了52.7%，比傳統(tǒng)檢索和WIG加權(quán)方法分別提高了42%和20%.在P@10指標(biāo)上，文中方法達(dá)到了60.8%，比傳統(tǒng)檢索和WIG加權(quán)方法分別提高了31.6%和9.3%.這說明文中方法能夠更好地為用戶提供所需的查詢文檔，并將其排序到靠前位置.

表5 各種檢索方法的性能比較Tab.5 Performance comparison of various retrieval methods

4 結(jié)論

提出一種用于維吾爾語Web文檔檢索的檢索詞重新加權(quán)方法.基于局部相關(guān)反饋思想，對文檔執(zhí)行初始檢索，并反饋N個頂級文檔.采用TF-IDF算法計(jì)算檢索詞與反饋文檔之間的詞頻相似度，利用余弦距離計(jì)算文檔之間的相似度，并以此對檢索詞進(jìn)行兩次加權(quán)，使檢索詞更能反映用戶的實(shí)際需求.與現(xiàn)有重新加權(quán)方法相比，文中方法能合理地為檢索詞進(jìn)行加權(quán)，使其能夠精確地檢索用戶所需文檔.

另外，文中提出的檢索方法應(yīng)用于維吾爾語文檔，但其主體思想也可用于其他語言文檔的檢索，其不同點(diǎn)在于文檔的預(yù)處理.文中方法在維吾爾語文檔預(yù)處理中，考慮了維吾爾語的特征，提取了詞干.若將文中方法應(yīng)用到其他語言中，則需要根據(jù)具體語言特征提取有效詞干.

文中認(rèn)為更加精致的加權(quán)算法將有助于獲取更高的性能.因此，在以后的研究中，將嘗試采用一些概率框架進(jìn)一步加權(quán)檢索詞.

[1] 阿麗亞·艾爾肯,哈力旦·阿布都熱依木.KNN和SVM分類器對維吾爾文文本分類性能的比較研究[J].新疆大學(xué)學(xué)報(自然科學(xué)維文版),2015,32(2):59-65.

[2] 亞力青·阿里瑪斯,哈力旦·阿布都熱依木,陳洋.基于向量空間模型的維吾爾文文本過濾方法[J].新疆大學(xué)學(xué)報(自然科學(xué)版),2015,32(2):221-226.

[3] HAN Tiantan,WANG Wendong,GONG Xiangyang,etal.Personal multimedia data retrieval query expansion and similarity algorithm improvement based wordNet[J].International Proceedings of Computer Science and Information Tech,2012,42(3):51-62.

[4] 陳雅蘭,胡小華,涂新輝,等.基于位置語言模型的中文信息檢索系統(tǒng)的研究[J].計(jì)算機(jī)科學(xué),2015,42(7):265-269.

[5] HAHM G J,YI M Y,LEE J H,etal.A personalized query expansion approach for engineering document retrieval[J].Advanced Engineering Informatics,2014,28(4):344-359.

[6] ATSUSHI F.Enhancing web document retrieval by the anchor text model and query classification[J].Ipsj Journal,2010,51(3):2330-2342.

[7] 李衛(wèi)疆,趙鐵軍,王憲剛.基于上下文的查詢擴(kuò)展[J].計(jì)算機(jī)研究與發(fā)展,2010,47(2):300-304.

[8] 陳志敏,姜藝,趙耀.基于用戶查詢擴(kuò)展的自動摘要技術(shù)[J].計(jì)算機(jī)應(yīng)用研究,2011,28(6):2188-2190.

[9] DANG E K F,LUK R W P,ALLAN J.Fast forward index methods for pseudo-relevance feedback retrieval[J].Acm Transactions on Information Systems,2015,33(4):1-33.

[10] SEMBOK T M T,BAKAR Z A.Characteristics and retrieval effectiveness of n-gram string similarity matching on Malay documents[C]∥Proceedings of the 10th WSEAS International Conference on Applied Computer and Applied Computational Science.Stevens Point:ACM Press,2011:165-170.

[11] ZHOU Yun,CROFT W B.Weighted information gain and user clicks on web search results[C]∥International ACM SIGIR Conference on Research and Development in Information Retrieval.Amsterdam:ACM Press,2012: 543-550.

[12] 年梅,張?zhí)m芳.維吾爾文網(wǎng)絡(luò)查詢擴(kuò)展詞的構(gòu)建研究[J].計(jì)算機(jī)工程,2015,41(4):187-189.

[13] 麥熱哈巴·艾力,姜文斌,王志洋,等.維吾爾語詞法分析的有向圖模型[J].軟件學(xué)報,2012,23(12):94-100.

[14] LEGOWO N,ROJALI S.Design of thesis topic search engine with information retrieval and vector space model of TF-IDF weighting[J].Australian Journal of Basic and Applied Sciences,2013,42(4):264-273.

[15] 彭凱,汪偉,楊煜普.基于余弦距離度量學(xué)習(xí)的偽K近鄰文本分類算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(6):2200-2203.

(責(zé)任編輯： 黃曉楠 英文審校： 吳逢鐵)

Uyghur Retrieval Word Weighting Scheme Using Relevance Feedback and Document Similarity

YU Li, YASEN·AIZEZI

(Department of Information Security Engineering, Xinjiang Police College, Urumqi 830011, China)

For the issue that the effective retrieval of Uyghur web documents, a Uyghur retrieval word weighting scheme based on the relevance feedback and document similarity is proposed. First of all, the Uyghur documents are pre-processed to obtain the corresponding stem set. Then, the initial search is executed when the user input a number of retrieval words, and it extracts the topNdocuments based on local relevance feedback. Follow, the TF-IDF algorithm is used to compute the frequency similarity between retrieval word and feedback documents. At the same time, the cosine distance is used to compute the similarity between documents, so as to make twice weighted for retrieval words. Finally, it performs document retrieval according to the weight of retrieval words. Experimental results show that the proposed method can accurately retrieve the documents required by the user, and can sort them in the front. Keywords：Uygur; document retrieval; weighted retrieval words; relevance feedback; document similarity

10.11830/ISSN.1000-5013.201703022

2016-05-10

亞森·艾則孜(1975-)，男，教授，主要從事信息安全、自然語言處理的研究.E-mail:yulixjpc@126.com.

新疆維吾爾自治區(qū)自然科學(xué)基金資助項(xiàng)目(2015211A016)

TP 391

A

1000-5013(2017)03-0408-06