數(shù)據(jù)融合中基于聚類的成員系統(tǒng)選擇算法*

張 振 張 芳

（江蘇大學計算機科學與通信工程學院 鎮(zhèn)江 212013）

1 引言

隨著信息技術的發(fā)展，大量的信息內(nèi)容推動了信息檢索系統(tǒng)［1］的開發(fā)，由于檢索系統(tǒng)中檢索模型［2］存在差異，因此生成的結果列表也有差異。數(shù)據(jù)融合的出現(xiàn)很好地解決了進一步提升檢索結果的問題，在略讀效應［3］、合唱效應［4］的作用下整合多個檢索結果列表以增強檢索性能。研究表明［5］參與融合成員系統(tǒng)的增加，有利于融合性能的提升。但成員系統(tǒng)過多時，融合過程的時間復雜度增加，冗余和質量差的成員系統(tǒng)影響［6］影響了融合效果進一步提升。因此，如何在大規(guī)模成員系統(tǒng)中選擇一組合適的成員系統(tǒng)參與融合并使最終的融合性能明顯提升，是一項具有挑戰(zhàn)性的任務。Antonio［7～8］等提出了一種啟發(fā)式選擇方法QV，但是這種方法只能應用于成員系統(tǒng)較少時。

由幾何框架［9］理論可知，只有滿足差異性和互補性的結果列表才能有效地提高融合性能。本文提出了一種基于變色龍層次聚類［10］和序列前向的成員系統(tǒng)選擇算法（RFS），該算法首先定義檢索結果列表之間的相似度度量，得到的距離矩陣后用于變色龍層次聚類，然后采用貪婪策略選出k 個來自不同簇的成員系統(tǒng)用于數(shù)據(jù)融合。

2 相關理論

2.1 數(shù)據(jù)融合技術

數(shù)據(jù)融合［11］就是一種能夠把多個信息檢索系統(tǒng)返回的結果合并，重新排序生成一個性能更優(yōu)的檢索結果的技術，使用合適的數(shù)據(jù)融合方法能夠有效地提升檢索性能。將參與融合的檢索系統(tǒng)稱之為成員系統(tǒng)，成員系統(tǒng)對查詢進行檢索產(chǎn)生成員結果。數(shù)據(jù)融合的基本流程如圖1所示。

圖1 數(shù)據(jù)融合基本流程

對于用戶查詢q，在給定文檔集中含有m 個成員系統(tǒng)，根據(jù)各自的檢索策略搜索與查詢相關的文檔，返回各自的結果列表R1，R2，…，Rm。接下來對著m個結果進行規(guī)范化［12］操作，之后使用某種融合算法將m個規(guī)范化后的檢索結果合并、重排生成最終檢索結果。本文采用常用的數(shù)據(jù)融合方法CombSUM、CombMNZ和MR［13］進行融合操作。

2.2 成員結果列表相似度測定

在信息檢索領域中，某些情況下我們需要度量兩個檢索列表的距離，或者說相似程度［14］。本文采用基于集合的度量［15］（Set Based Measure）來衡量結果列表之間的相似度。

基于集合的度量主要通過計算兩個不同排序列表，在不同深度時對應集合的交集大小來計算排序列表的相似度。計算出不同深度的交集比例后，通過交集比例的分布來量化兩個列表的相似程度，最簡單的方法就是直接計算交集比例的平均值。但是隨著列表長度的不斷增加，距離值有可能會無窮大。同時，在比較兩個排序列表的相似性時，要考慮不同位置的元素權重，尤其是top 元素的相對位置權重。為解決上述問題，我們給每個深度的交集比例定義了一個權重系數(shù)，計算加權和，稱為偏差重疊排名(RBO)。設S 和T 為兩個無限長度的排序列表，Si為列表S 的第i 個元素，Sc:d={Si:c≤i≤d}表示列表中從位置c到位置d的所有元素組合的集合。在深度為d 時，列表S 和T 的交集為

交集的元素個數(shù)稱之為列表S 與T 在深度為d時的交疊，該交疊相對于深度d 的比值稱之為列表S與T的一致度。

則RBO距離度量定義為

其中，p為一個預先定下的參數(shù)，0 ＜p＜1。

2.3 變色龍層次聚類

變色龍聚類是一種利用動態(tài)模型的兩階段層次聚類算法，其考慮不同簇間的信息，克服了傳統(tǒng)層次聚類靜態(tài)建模的局限性［16］。變龍算法的聚類步驟如圖2。

圖2 變色龍聚類步驟

第一階段，首先Chameleon 計算數(shù)據(jù)集的距離矩陣和相應的權重矩陣，然后采用KNN 方法來構建一個稀疏圖，圖的每一個頂點代表一個數(shù)據(jù)對象，如果一個對象是另一個對象的k 個最相似的對象之一，那么這兩個頂點（對象）之間就存在一條邊（這些邊加權后反映對象間的相似度）；最后，Chameleon使用hMetis圖劃分算法，把k-個最近鄰圖劃分成大量相對較小的子簇，使得邊割最小。

第二階段，計算子簇兩兩間相對互連度RI 和相對近似度RC，并以此計算其相似度F，迭代選取相似度最大的兩個子簇合并，直到子簇個數(shù)小于設定值或相似性最大值小于閾值時結束。相對互連度RI和相對近似度RC的公式如下所示：

3 本文算法

本文針對大規(guī)模數(shù)據(jù)集，首先在數(shù)據(jù)預處理階段將不正常數(shù)據(jù)對象去除，生成初始數(shù)據(jù)集，利用變色龍聚類算法將數(shù)據(jù)集依據(jù)相似性分成若干簇，之后采用貪婪策略順次從不同簇中挑選出若干融合性能好的成員結果，最終找出最佳成員系統(tǒng)組合。

算法1 基于變色龍層次聚類的分組算法

4 實驗結果及分析

本文采用的TREC（Text REtrieval Conference）提交的結果作為數(shù)據(jù)集，采用的數(shù)據(jù)集為

TREC2017 Precision Medicine Track Scientific Abstracts Task，此數(shù)據(jù)集中含有125 組檢索結果，遠多于其他的主題數(shù)據(jù)集，有利于測試選擇方法的可靠性。經(jīng)過初步挑選后有108 個成員系統(tǒng)檢索結果可用。

在聚類完成后，使用二折交叉驗證將每組成員系統(tǒng)中的查詢按編號分為奇偶兩組。首先，使用貪婪策略將簇中偶數(shù)組使用順序前向算法選擇出成員系統(tǒng)組，之后將其在對應成員系統(tǒng)組中的奇數(shù)查詢上進行融合測試，使用CombSUM 作為來計算評價指標，然后再反過來測試。實驗中采用分別用CombSUM、CombMNZ、MR 作為選擇后融合方法，MAP 值作為融合性能評價指標。實驗共分為兩個部分。

1）小規(guī)模數(shù)據(jù)集選擇算法性能對照實驗

文獻［7］提出的QV 選擇算法只適合在參與融合的成員系統(tǒng)較少時，為了與本實驗提出的RFS算法進行對照，故從實驗集截取了MAP 值較優(yōu)的50個成員系統(tǒng)進行實驗。實驗中RFS 方法將成員系統(tǒng)分成10 個簇，依次選擇2～10 個成員系統(tǒng)。之后使用分別CombSUM、CombMNZ、MR 進行融合實驗。AllList 表示所有成員系統(tǒng)參與融合后的結果。實驗結果如圖3所示。

圖3 RFS選擇算法與QV選擇算法的性能曲線圖（評價指標MAP）

分析圖3發(fā)現(xiàn)，隨著選擇系統(tǒng)個數(shù)的增加，RFS算法和QV 算法的性能都先增加再降低，在選擇的成員系統(tǒng)個數(shù)為6 左右時取得最佳性能，且RFS 算法的性能遠由于QV算法。

2）RFS算法在大數(shù)據(jù)集上的性能實驗

為了說明RFS算法在大規(guī)模數(shù)據(jù)集上的效果，本節(jié)實驗使用含有108 個成員系統(tǒng)的數(shù)據(jù)集來測試，經(jīng)過試驗測試，數(shù)據(jù)集被分成21 簇個數(shù)，故選取不同的組數(shù)（從2 組～21 組）進行融合實驗，同時引入了其他幾種選擇算法。GA是使用遺傳算法來選擇成員系統(tǒng)；TopIR 選擇算法，根據(jù)MAP 表依次選取MAP 值較大的成員系統(tǒng)參與融合；TopCha 選擇算法則是在完成聚類后，依次選取每個簇中MAP值最大的成員系統(tǒng)參與融合；Bsetcomb是RFS選擇的成員系統(tǒng)進行融合之前最優(yōu)成員系統(tǒng)性能。將這四種算法分別運用在實驗數(shù)據(jù)集上，并分別使用CombSUM、CombMNZ、MR 作選擇成員系統(tǒng)組的融合方法。結果如圖4～6所示。

觀察圖4、圖5、圖6可以得出，在所有提出的選擇算法中，隨著選擇的成員系統(tǒng)增加，融合性能也逐步提升。其中性能最好的是RFS 選擇算法，Top-Cha 選擇算法次之。在使用CombSUM、CombMNZ、MR 進行融合時，RFS 分別在成員系統(tǒng)個數(shù)n=15、16、16時MAP取得最大值0.3607、0.3451、0.3608。

圖4 不同選擇算法情況下的融合曲線圖（融合方法：combSUM）

圖5 不同選擇算法情況下的融合曲線圖（融合方法：combMNZ）

圖6 不同選擇算法情況下的融合曲線圖（融合方法：MR）

將其與所有成員系統(tǒng)結果融合的結果（All-List）進行對照，如圖7 所示，通過RFS 選擇算法得到成員結果列表融合后的性能高于所有成員結果列表的融合性能，同時個數(shù)大大較少，因此有效地降低了時間復雜度，提升了融合效率。

圖7 選擇成員系統(tǒng)和所有成員系統(tǒng)融合的性能比較

5 結語

本文提出了一種新的成員系統(tǒng)選擇算法，通過上述實驗表明該算法通過降低成員結果的冗余度，不僅能大大縮減參與融合的成員系統(tǒng)個數(shù)，而且這些選擇的成員系統(tǒng)結果融合后性能也明顯提升，同時本算法也明顯優(yōu)于其他的選擇算法。下一步研究重點是如何改進聚類算法，從而使簇間的成員系統(tǒng)相似度更低，以有利于下一步的篩選。