評估數(shù)據(jù)融合中得分規(guī)整的方法

1、目錄評估數(shù)據(jù)融合中得分歸一化的方法21 Abstract22 Introduction23數(shù)據(jù)融合44 不同得分歸一化方法對數(shù)據(jù)融合效果的影響61.method62.result105 在不同的分數(shù)秩區(qū)間內(nèi)相關(guān)文件的分布情況12線性轉(zhuǎn)化：12實驗過程136 Conclusion15評估數(shù)據(jù)融合中得分歸一化的方法1 AbstractIn data fusion, score normalization is a step to make scores, which are obtained from different component systems for all documents, c

2、omparable to each other. It is an step for effective data fusion algorithms such as CombSum and CombMNZ to combine them. In this paper, we evaluate four linear score normalization methods, namely the fitting method, Zero-one, Sum, and ZMUV, through extensive experiments. The experimental results sho

3、w that the fitting method and Zero-one appear to be the two leading methods.數(shù)據(jù)融合把多個信息系統(tǒng)的數(shù)據(jù)融合到一起，形成一致性的數(shù)據(jù)模型；評分歸一化是數(shù)據(jù)融合算法不可缺少的一步，是打分過程的一個步驟，我們從所有文件不同的系統(tǒng)成分中獲取分數(shù)并相互比較。在本篇文獻中，評估四種線性評分規(guī)一化方法，即，the fitting method, Zero-one, Sum, and ZMUV，通過大量的實驗結(jié)果證明the fitting method and Zero-one是兩種更好的方法。2 Introduction在信息檢索

4、中，數(shù)據(jù)融合是被很多研究者研究和建立的好的方法數(shù)據(jù)融合就是把多個信息系統(tǒng)的數(shù)據(jù)融合到一起，形成一致性的數(shù)據(jù)模型。數(shù)據(jù)融合的主要思想是整合多重信息檢索系統(tǒng)中得到的檢索文件到一個列表中，通過給定的檢索，我們能更準確的評估所有相關(guān)的文件。它為運行有效的信息檢索系統(tǒng)提供一種選擇。它也被用來在萬維網(wǎng)環(huán)境中，作為一種元搜索引擎，從其他的搜索引擎中融合合成的文件。元搜索引擎在接受用戶查詢請求時，同時在其他多個引擎上進行搜索，并將結(jié)果返回給用戶。元搜索：隨著互聯(lián)網(wǎng)的迅猛發(fā)展，Web信息成爆炸式增長的趨勢，如何更好、更全、更快地從中獲取對我們有價值的信息，成為信息檢索領域研究的最主要任務。然而任何一個普通的搜索

5、引擎都無法覆蓋所有的Web信息，因此，在檢索時，希望能夠同時使用不同的搜索引擎來提高檢索的覆蓋率以及查全率，獲取更多、更好的有價值結(jié)果。為此，元搜索引擎在這種需求驅(qū)使下誕生并發(fā)展起來。元 搜索指的是通過向多個搜索引擎發(fā)送搜索請求，將所得到的結(jié)果進行合并，以試圖得到更好的結(jié)果列表呈現(xiàn)給用戶的一種搜索方式?？紤]到針對一個搜索，每個通用搜索引擎能夠給出很多相關(guān)的文檔，元搜索可以通過將多個通用搜索引擎結(jié)果合并比較來發(fā)現(xiàn)其中更為相關(guān)的文檔，從而提升前k個結(jié)果中的精確度和相關(guān)度。當前元搜索主要研究的問題有以下三個方面。（1）數(shù)據(jù)庫/搜索引擎選擇問題（database selection problem）該

6、問題主要研究對于一個給定的query，如何選擇那些更有可能返回相關(guān)度更高文檔的搜索引擎進行檢索。（2）文檔選擇問題（Document selection problem）該問題主要研究對于選擇的搜索引擎，需要從這些搜索引擎中選取多少文檔。（3）結(jié)果合并問題（Result merging problem）該問題主要研究如何將從各個搜索引擎得到的結(jié)果進行合并，以給出更好的檢索排序。對于用戶提交的查詢，元搜索會將查詢query提交給不同的成員搜索引擎。由于不同成員搜索引擎返回的結(jié)果不僅數(shù)量多，且存在重復的問題，如何選擇返回的查詢結(jié)果以及對選擇的結(jié)果進行合并排序，直接影響到元搜索搜索引擎的整體性能。目

7、前主流的對搜索結(jié)果合并排序的方法主要有兩種，一種是基于相關(guān)性評分（relevance score）的方法；一種是基于返回結(jié)果的rank值的方法。（1）基于相關(guān)性評分的方法該方法的主要思路是依據(jù)不同的成員搜索引擎對于固定的查詢詞與文檔集之間一一對應的相關(guān)性評分的值，來確定最終返回給用戶的文檔排序結(jié)果。在計算最終返回給用戶的文檔集與查詢的相關(guān)性評分的方法中，有基于評分的最大值（CombMAX）、最小值（CombMIN）、和值（CombSUM）、平均值（CombAVG）以及CombMNZ（multiply-by-number-non-zero）等。設搜索引擎集合為D，i表示其中第i個搜索引擎，對于C

8、ombSUM、CombAVG以及CombMNZ有統(tǒng)一形式的計算公式，即對于某個query，其中reli(d)為成員搜索引擎i中，文檔d與query的相關(guān)性評分；表示相關(guān)性評分中非零值的數(shù)目。對于不同的r值，表示不同的計算方法，r=0時，即是上面求和值的方法CombSUM；r=1時，表示上面CombMNZ的方法;r=1時，表示求平均值CombAVG的方法。上面方法中，由于不同的成員搜索引擎對于查詢與文檔的相關(guān)性評分的標準不同，所以在進行上述計算之前需要對相關(guān)性評分進行歸一化處理。求取查詢與文檔的相關(guān)性評分后，按照相關(guān)性評分的大小對文檔進行排序，返回給用戶排序的結(jié)果。除了上述計算方法外，基于相關(guān)性

9、評分的合并排序，還有對各成員搜索引擎相關(guān)性評分進行線性組合的方法（linear combination）。 上述的處理方法中并沒有對不同成員搜索引擎的性能進行區(qū)分，實際上，不同搜索引擎在搜索性能上還是存在差距的，線性組合的方法考慮到這種差距，對來自不同成員搜索引擎的相關(guān)性評分增加不同的權(quán)重，相對于上述簡單的求取某個平均值或者是和值，這種方法更加合理。其計算公式如下式中ai表示不同成員搜索引擎的權(quán)重，這種權(quán)重的獲取方式很多，典型的有取不同搜索引擎訓練集的平均準確率（AP）。（2）基于返回結(jié)果的rank值的方法這種方法的主要思路是依據(jù)不同成員搜索引擎對某個查詢返回文檔集的rank位置排序，并不需要

10、原始的成員搜索引擎的相關(guān)性評分。基于相關(guān)性評分的算法總體上會比基于返回結(jié)果的rank位置的性能更好。但是從算法的成本上來說，基于相關(guān)性評分的算法需要事先知道成員搜索引擎的相關(guān)性評分，這個在實際搜索引擎中是存在很大困難的，而獲取返回結(jié)果的rank位置排序是容易的。因此在實際的應用當中，基于返回結(jié)果的rank位置的合并排序算法更受青睞。3數(shù)據(jù)融合數(shù)據(jù)融合是一個框架，采集并集成各種信息源、多媒體和多格式信息，它是一個把多源信息通過合適的方法結(jié)合起來得到一個更滿意的結(jié)果的過程。傳感器是數(shù)據(jù)的來源，傳感器不一定是物理形式的，數(shù)據(jù)源或者信息源甚至人工數(shù)據(jù)都稱為傳感器;融合是一種數(shù)據(jù)加工過程，算法將隨著數(shù)據(jù)

11、源的不同以及融合的目標的不同而不同。對于數(shù)據(jù)融合算法有幾種因素需要考慮：在這三方面已經(jīng)做了很多的研究。對于一個component result（整合結(jié)果），它包含一組秩序列的文件，有時基于信息的需要我們通常用每一個文件關(guān)聯(lián)的分數(shù)來表示文件的評估相關(guān)性，而不是用秩數(shù)。本篇文獻我們假設所有整合系統(tǒng)（搜索引擎）為檢索的文件提供分數(shù)，不同的整合系統(tǒng)用不同的打分機制，這種不同不僅是范圍也是分布的不同。因此一個有效的數(shù)據(jù)融合算法有必要進行分數(shù)的標準化。例如 Fox and Shaw 設計的 CombSum和CombMNZ算法就整合了評分的歸一化.兩者的區(qū)別：而Lee 介紹了一種線性轉(zhuǎn)換的得分歸一化的方法本

12、文的參考文獻介紹了四種線性標準化的方法：目標：評估四種線性標準化方法，(Zero-one, the fitting method, Sum and ZMUV)，一些實驗結(jié)果也有利于我們更好的從總體上了解分數(shù)標準化。4 不同得分歸一化方法對數(shù)據(jù)融合效果的影響1. method美國國家標準和科技機構(gòu) (National Institute of Standards and Technology, 簡稱 NIST)和美國情報局先進研發(fā)活動 (Advanced Research and Development Activity center of the U.S. Department of Defe

13、nse, 簡稱 DARDA 合作舉辦“文字檢索會議”(The Text REtrieval Conference, TREC3)  目標：其目的是在信息檢索社區(qū)的研究中為大規(guī)模評估文本檢索方法提供必要的基礎設施支持。TREC 7: TREC 8: TREC 9: TREC2001: 2.result對比在相同的融合算法中不同分數(shù)標準化方法得到融合結(jié)果的效率。The Fitting method 中，統(tǒng)一選取范圍0.06,0.6 CombMNZ算法中，因為ZMUV 半數(shù)結(jié)果為負值，故對每一個規(guī)范化分數(shù)加2，ZMUV方法換為，ZMUV2方法。選用四組結(jié)果，是TREC 7,8,9,2001

14、的子集，每一次查詢包含1000篇文件，平均準確率大于等于0.15，每組隨機選擇3-10個系統(tǒng)運用兩種算法的數(shù)據(jù)融合，200篇用來測試任何給定數(shù)目的結(jié)果。平均標準率被用來評估四種方法：四種規(guī)范化方法在兩種數(shù)據(jù)融合方法中有相似的效率，可以觀察到，所有方法中ZMUV2總是最差的，the fitting method0.06-0.6 ，和 Zero-one相對于其他兩種方法較好。5 在不同的分數(shù)秩區(qū)間內(nèi)相關(guān)文件的分布情況線性轉(zhuǎn)化：對于線性的轉(zhuǎn)換方法，它把所有值都放在一個范圍里：設置了兩Max和min表示標準化分數(shù)的最大最小值，r max 和r min分別表示原始分數(shù)的最大最小值。對于任何一個原始分數(shù)r

15、_s，用以下公式標準化：對于任何一種線性轉(zhuǎn)化方法都可以轉(zhuǎn)化為另一種線性方法相應的分數(shù)，例如：分數(shù)標準化的目的就是使不同的結(jié)果（results）具有可比性，理想情況下，如果在分數(shù)與相關(guān)概率之間有著線性的聯(lián)系，對于CombSum這樣的算法很有利。此時，我們對于從n個信息檢索系統(tǒng)中得到的n 個results有如下倆個條件： 實驗過程：接下來我們將進行實驗來驗證哪個得分規(guī)整的范圍符合上述兩個條件，過程如下：1、first, for a result, we normalize the scores of its documents using a given score normalization m

16、ethod. 2、Next we divide the whole range of scores into a certain number of intervals. Then for every interval, we count the number of relevant documents (num) and the total score (t score) obtained by all the documents in that interval. 3、In this way the ratio of num and t score can be defined for e

17、very interval. We compare these ratios to investigate if the score normalization method is a good method or not.在部分2，我們用相同的四組結(jié)果（results），用四種方法標準化，超過50次的查詢，the fitting method 0.06-0.6, Zero-one, Sum and ZMUV1 (a variation of ZMUV, which added 1 to every score normalized with ZMUV)ZMUV1是ZMUV的一種變化，在每一標

18、準分值上加1.對所有標準化的結(jié)果分為20組，每組對應一個間隔，那個組的所有文件的分值都會處于相同的間隔上。對于每一個間隔，我們獲得相關(guān)文件的數(shù)目 (num) 和總分數(shù) (t score) 并計算比值，比較這些比值來估計分數(shù)標準化方法的好壞。對于the fitting method, 我們劃分0.06,0.6 為20個相等的間隔 0.06,0.087), 0.087,0.114),., 0.573,0.6. 對于 Zero-one, 我們劃分 0,1 為 0,0.05), 0.05,0.1),., 0.95,1. 對于 Sum, 我們把 0,1 劃分為0,0.00005), 0.00005,0.0001), ., 0.00095,1, 由于在sum中所有的標準化分數(shù)都很小切大部分小于0.001。 對于 ZMUV1, 20個間隔 (-, 0.1), 0.1,0.2),., 1.9,+) 。對于每一組，我們計算相關(guān)文件的數(shù)目與總分數(shù)的比值。理想的情況是曲線應該平行與水平的軸線，這意味著在文件的相關(guān)性和分數(shù)之間有著線性的關(guān)系，同時也說明CombSum是一個很好的數(shù)據(jù)融合的方法。從上圖可以看出，在多種方法中，the fitting method 是最好的方法，所有的曲線大致是平的，其他方法的曲線也有平的趨勢，這證明線性函數(shù)是描述分數(shù)與文件相關(guān)性的好的選擇。對于Zero-one, S