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

張 振 張 芳

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

1 引言

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

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

2 相關(guān)理論

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

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

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

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

2.2 成員結(jié)果列表相似度測定

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

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

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

則RBO距離度量定義為

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

2.3 變色龍層次聚類

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

圖2 變色龍聚類步驟

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

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

3 本文算法

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

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

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

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

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

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

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

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

圖3 RFS選擇算法與QV選擇算法的性能曲線圖（評價(jià)指標(biāo)MAP）

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

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

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

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

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

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

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

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

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

5 結(jié)語

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