排名聚合算法在少量長列表聚合中的性能比較分析*

陳玟宇 朱章黔 王曉蒙 賈韜?

1)(西南大學計算機與信息科學學院 軟件學院,重慶 400715)

2)(中國人民解放軍陸軍勤務學院國防經濟系,重慶 500106)

排名聚合將多個排名列表聚合成一個綜合排名列表,可應用于推薦系統(tǒng)、鏈路預測、元搜索、提案評選等.當前已有工作從不同角度對不同排名聚合算法進行了綜述、比較,但存在算法種類較少、數(shù)據統(tǒng)計特性不清晰、評價指標不夠合理等局限性.不同排名聚合算法在提出時均聲稱優(yōu)于已有算法,但是用于比較的方法不同,測試的數(shù)據不同,應用的場景不同,因此何種算法最能適應某一任務在很多情況下仍不甚清楚.本文基于Mallows模型,提出一套生成統(tǒng)計特性可控的不同類型的排名列表的算法,使用一個可應用于不同類型排名列表的通用評價指標,介紹9種排名聚合算法以及它們在聚合少量長列表時的表現(xiàn).結果發(fā)現(xiàn)啟發(fā)式方法雖然簡單,但是在排名列表相似度較高、列表相對簡單的情況下,能夠接近甚至超過一些優(yōu)化類方法的結果;列表中平局數(shù)量的增長會降低聚合排名的一致性并增加波動;列表數(shù)量的增加對聚合效果的影響呈現(xiàn)非單調性.整體而言,基于距離優(yōu)化的分支定界方法(FAST)優(yōu)于其他各類算法,在不同類型的排名列表中表現(xiàn)非常穩(wěn)定,能夠很好地完成少量長列表的排名聚合.

1 引 言

排序是在復雜系統(tǒng)的研究中經常使用的方法,例如通過節(jié)點中心性對重要節(jié)點排序[1,2],鏈路預測中對可能存在的邊排序[3,4].在很多場景中,我們會面對基于不同參數(shù),采用不同機制所得到的不同排名,如不同人群對候選者給出的投票排名,不同推薦系統(tǒng)給出的推薦排名,不同算法給出的鏈路預測排名.將多個排名列表聚合成一個綜合排名列表,就是排名聚合(rank aggregation,RA)要解決的問題.排名聚合也稱為Kemeny排名聚合[5]、偏好聚合[6]、共識排名問題[7],可以應用于推薦系統(tǒng)、元搜索、期刊排名、提案評選、復雜網絡等領域[2,3,8-20].作為一個研究主題,排名聚合已有超過兩百多年的研究歷史,最早可追溯至1781年法國數(shù)學家Borda[21]解決的法國科學院選舉問題.基于“總體大于各部分之和”的基本思想[22],不同研究領域提出了大量排名聚合方法,大致可分為啟發(fā)式方法和優(yōu)化類方法.啟發(fā)式方法基于某種直觀經驗或規(guī)則將多個排名綜合為一個排名,具有簡單、快速的特點.優(yōu)化類方法通過優(yōu)化某一目標函數(shù),得到一個與已有排名之間存在某種優(yōu)化量的排名.雖然優(yōu)化類方法在理論上更加完備,但是因為其對應的優(yōu)化問題是NP(non-deterministic polynomial)難的,難以保證得到最優(yōu)解.對不同排名聚合方法進行對比分析,能幫助在不同應用場景和數(shù)據條件下選擇最合適的聚合方法,提高效率和可信度,具有非常重要的意義.

少量長列表的排名聚合是很多實際場景中需要解決的問題,這些排名列表相互不等長,且可能包含平局,例如不同機構給出的大學排名、基于不同基因數(shù)據庫的靶點預測排名、不同搜索引擎對相關主題給出的推薦排名.選擇何種算法能最好地處理少量長列表的排名聚合尚沒有明確的答案.雖然當前已有綜述類工作[23,24]對不同聚合算法進行了列舉和介紹,但是一般缺少不同方法之間的性能比較.一些工作[25-30]雖然涉及了一部分排名聚合算法的性能比較,但是用于比較的聚合算法較少,使用的排序列表類型不夠豐富,評價指標也有不夠合理之處.同時,當前的絕大多數(shù)算法對比工作均是基于少量實證數(shù)據,由于數(shù)據的統(tǒng)計特征缺失,難以區(qū)分算法優(yōu)劣是源自特定數(shù)據集,還是基于一系列數(shù)據集的共同統(tǒng)計特征,算法性能的泛化能力難以估測.最后,不同的聚合方法在提出時,均會聲稱優(yōu)于已有的算法,但是用于比較基礎算法不盡相同,用于測試的數(shù)據也往往大相徑庭,使得我們往往無法真實知曉在具體應用場景下何種算法性能最佳.

針對這些局限性,本文基于Mallows模型提出一套用于生成統(tǒng)計特性可控的不同類型的排名列表的算法,使用一個可應用于不同類型排名列表的通用評價指標,介紹9種排名聚合算法,比較它們在少量長列表排名聚合下的表現(xiàn).結果發(fā)現(xiàn)啟發(fā)式方法雖然簡單,但是在排名列表相似度較高、列表相對簡單的情況下,能夠接近甚至超過一些優(yōu)化類方法的結果;列表中平局數(shù)量的增長會降低聚合排名的一致性并增加波動;列表數(shù)量的增加對各聚合結果的影響呈現(xiàn)非單調性.整體而言,基于距離優(yōu)化的分支定界方法(FAST)優(yōu)于其他各類算法,在不同類型的排名列表中表現(xiàn)非常穩(wěn)定,能夠很好地完成少量長列表的排名聚合.

2 基本概念

給定包含|S|個對象的集合S,一個塊序列(bucket order)是一種可傳遞二元關系?,存在塊集合B1,···,Bt(1≤t≤|S|)分割S,即塊數(shù)量為t.如果x∈Bi,稱Bi是x的塊.如果i＜j,則稱塊Bi位于Bj之前.對象x?y當且僅當對于i＜j有x∈Bi且y∈Bj.如果一個給定塊中包含多個對象,則形成一個平局,即塊內的對象具有相同的位置.直觀上看,一個塊序列就是一個可能包含平局的嚴格線性序列,塊中對象x的位置定義為即采用“1224”列表類型來表達對象的排名偏好信息,而非采用塊中對象的平均位置[31].“1224”列表類型表示為第2和第3個對象具有相同的位置,形成一平局.本工作主要針對少量長列表的聚合,根據相關應用場景,主要針對如下3種類別的列表[32].

完全列表(full list,FL): 塊序列中所有塊大小均為1且 t=|S|,即包含S中所有對象且不含平局;

平局列表(full list with ties,TL): 塊序列中至少有一個塊的大小大于1且 1 ≤t≤|S|,即包含S中所有對象且存在平局;

不完全列表(incomplete list,IL): 由S中部分對象形成的塊序列,可能包含平局.

例如,假設S包含A,B,C和D四個對象,現(xiàn)有如下5個塊序列:

塊序列1: [A],[B],[C],[D];

塊序列2: [A],[B,C],[D];

塊序列3: [A],[C];

塊序列4: [A],[B],[D];

塊序列5: [B],[C,A],

其中,一個“[ ]”代表一個塊,即一個位置.塊序列1包含S中所有對象,并且塊數(shù)量等于S中對象數(shù),因此是FL類型.塊序列2包含S中所有對象,但B與C都在塊2中,即B與C形成一平局,是TL類型.塊序列3—5都只包含S中部分對象,均為IL類型.

3 相關研究

Ali和Meila[25]重點探討了不同排名聚合方法在搜索時間與結果表現(xiàn)之間的均衡性,發(fā)現(xiàn)決定均衡的重要因素是數(shù)據集的一致程度(degree of consensus).Schalekamp和Zuylen[26]也針對相似問題開展了工作,并且將平局情況引入比較過程,給出多個聚合方法表現(xiàn)的下界,但是在計算過程中一些方法沒有考慮打破平局的代價.上述兩個工作均使用真實數(shù)據集測試不同算法,但是所使用數(shù)據量較小.Brancotte等[27]針對平局比較了一系列排名聚合方法,標注了不同方法是否適用于TL數(shù)據,研究了平局等數(shù)據集特征對所討論方法的影響.但是以上幾個工作都沒有考慮更為復雜的IL數(shù)據.

Cohen-boulakia等[29]基于廣義肯德爾距離,提出了一個新的啟發(fā)式排名聚合算法,此方法可適用于所有列表類型,但是算法驗證和對比僅僅基于一個小型生物醫(yī)學數(shù)據集和人工數(shù)據(4—8個對象).Lin[24]從排名聚合方法在生物信息學中的應用角度,綜述和對比了多個聚合算法,但是該工作使用的數(shù)據較小并且對IL數(shù)據的情況考慮不充分.Sculley[33]比較了不同算法在大量短列表聚合下表現(xiàn),但是其比較的方法較少,且均為啟發(fā)式算法;Xiao等[30]基于其提出的數(shù)據生成模型對四種排名聚合算法進行了比較,并通過一個預設的真實排名(ground truth ranking)比較不同算法結果的質量.由于該數(shù)據生成模型對于平局數(shù)量、IL數(shù)據生成過程不可控,同時真實排名在現(xiàn)實場景中難以獲得,其算法質量評估在真實場景中的應用具有局限性.

在評價指標的選擇上,大多數(shù)工作使用斯皮爾曼等級相關系數(shù)或肯德爾 τ 距離.這兩個經典量只適用于排名列表包含所有對象的情況,不能應用在IL數(shù)據中,同時它們也沒有考慮不同排名位置的不同權重.在真實場景中,靠前的排名應比靠后的排名具有更高的權重,例如第1名和第2名、第50名與51名之間均只相差1個排位,但前者的排名差距權重比后者更大.

綜上所述,當前很多排名聚合算法比較工作存在數(shù)據量小、評估指標不夠合理、數(shù)據統(tǒng)計特征缺失或列表類型單一等問題.針對以上問題,本文提出一個數(shù)據生成模型,生成列表類型、列表長度(即對象數(shù)量)、列表數(shù)量、一致程度等特征可控數(shù)據用于算法比較.本文同時采用更為合理的評價指標,更好地處理平局、排序權重等之前工作中未能充分考慮的問題,從而更合理地比較不同算法在不同情況下的表現(xiàn).

4 排名聚合方法及其分類

排名聚合方法可根據相關特征從不同角度進行分類[23,24,27,31,34].文獻[23]是最早對排名聚合方法進行分類的排名聚合公理派綜述文章,將排名聚合方法分為啟發(fā)式方法和優(yōu)化類方法兩類.文獻[24]將所有排名聚合方法分為基于分布的方法、啟發(fā)式方法和隨機搜索方法三類.文獻[27]從能否處理平局的角度分為基于廣義肯德爾距離的方法、基于傳統(tǒng)肯德爾距離的方法和位置類方法三類.文獻[31]按是否需要訓練數(shù)據分為監(jiān)督類方法[35,36]和非監(jiān)督類方法兩類.本文采用第一種分類標準.

4.1 啟發(fā)式方法

4.1.1 KwikSort

KwikSort[37]是一種分治算法,其核心思路是給定一組對象,隨機選擇一個對象作為中心點,并將其他所有對象按照一定規(guī)則置于該中心點前后的兩個塊中,從而使每一個對象與該中心點的違例數(shù)最少(為與下文排名聚合方法MVR中違例數(shù)相區(qū)分,此處違例數(shù)定義為對于兩個對象,如果其在兩個列表中的相對位置不一致,則形成一個違例).van Zuylen和Williamson[38]提出了 KwikSort去隨機化版本.事實上,對象有一定概率與中心點形成平局.Brancotte等[27]通過這種策略對KwikSort進行了改進使其可以處理平局.

4.1.2 FaginSmall

Fagin等[31]針對平局提出幾種指標并利用動態(tài)規(guī)劃方法提出一種新的近似算法.Cohenboulakia等[29]對上述方法做了修改得到FaginLarge和FaginSmall,前者得到的結果包含平局,而后者不包含平局,因此,本文選用FaginSmall.

4.1.3 BioConsert

給定M個對象和N個排名列表Rμ1,···,RμN(μ1,···,μN是每個列表對應的排名機制),通用目標函數(shù)為

其中w是權重向量,用于指定有關排名列表相對重要性或可靠性的先驗信息.本文取為元素全為1的向量,以表征所有排名列表一樣重要,此時該問題也稱為Kemeny排名聚合問題.本文不考慮最終得到的聚合排名中包含平局的情況,所以U表示由這M個對象組成的所有FL集合,則|U|=M!.d是某種距離函數(shù),如肯德爾τ距離[39]、斯皮爾曼簡捷距離[40]、KS距離[23]以及Hausdorff距離[41]等.RC在本文中叫聚合排名,而在社會選擇和離散數(shù)學文獻中叫共識排名(consensus ranking),在統(tǒng)計學文獻中稱為中值排名(median ranking).

BioConsert[29]的主要思路是從一個初始排名列表R開始,通過不斷迭代選擇執(zhí)行兩類操作以減少上述通用目標函數(shù)值.當任何操作均不能再減少目標函數(shù)值時,則將此時的排名列表作為最終的聚合排名.這兩類操作是: 1)將一個對象從原來的塊中取出放入另一個塊中;2)將一個對象從原來的塊中取出并在另一個新的位置新建單對象塊.如果執(zhí)行上述某一操作后目標函數(shù)變小,則執(zhí)行該操作;反之,則不執(zhí)行.不同初始排名列表R會產生不同的聚合排名結果,極大影響算法的表現(xiàn)[27].本文選用波達計數(shù)法的聚合排名RC作為初始排名列表.

4.1.4 波達計數(shù)法(BordaCount)

波達計數(shù)法[21]是最簡單直觀的排名聚合方法:在每個排名列表中,根據排名順序對每個對象賦值一個分數(shù),將每個列表中該對象分數(shù)相加并對每個對象總分數(shù)進行排序就得到了最終的聚合排名.同一對象在不同排名列表中的總分數(shù)除使用簡單相加以外,也可使用其他聚合函數(shù),例如中值函數(shù)、幾何平均函數(shù)、p范數(shù)等[24].本文采用最簡單的波達計數(shù)法,即某一列表中對象分數(shù)為該對象所擊敗的對象數(shù)量(例如在長度為M的排列中,第1名的分數(shù)為M-1,而第M名的分數(shù)為0),并采用求和的方法計算各對象總分數(shù).

4.1.5 MedRank

MedRank[42]的核心思路是給定閾值q∈[0,1],逐一并行讀取所有N個排名列表,一旦有對象出現(xiàn)次數(shù)首次超過N×q,則根據對象出現(xiàn)的先后順序依次添加至最終排名列表,直至達到指定列表長度.本文將閾值q取為0.5.

4.1.6 馬爾科夫鏈方法(MC3)

Dwork等[11]使用成對比較信息,基于馬爾科夫鏈提出了一系列的排名聚合方法,其核心思路是將所有對象當作狀態(tài),構建一各態(tài)歷經的馬爾科夫鏈轉移矩陣,從而其穩(wěn)態(tài)分布會給予排在前面的狀態(tài)更高的概率,對象轉移概率的不同賦值方法取決于我們的目標.Lin[24]對上述方法進行改進以使其可以適用于不同類型列表.本文采用文獻[24]中的MC3方法,給定M個對象和N個排名列表Rμ1,···,RμN(μ1,···,μN是每個列表對應的排名機制),對于u,v屬于M,且u不等于v,則u→v的概率為

其中當I(·)所包含的條件滿足時,I(·)=1,否則I(·)=0.此時,定義同時,對象轉移概率與將待轉向對象排在當前對象前面的列表數(shù)量成正比.根據(2)式建立相應的狀態(tài)之間的概率轉移矩陣,同時建立以狀態(tài)為節(jié)點,狀態(tài)間轉移概率作為邊權重的加權有向圖 G(V,E),V為狀態(tài)集合,E為邊集合,此時,將問題轉變?yōu)閷ふ易畲蟮挠邢蚍茄h(huán)連通子圖.

4.1.7 PageRank

依據經典PageRank算法[43]的排名聚合算法PageRank[44]的主要思想是給定排名列表構造圖G(V,E),V為節(jié)點集合,E為邊集合,將每個對象看作圖G中一個節(jié)點,對于每一個排名,如果對象u排名高于對象v,則建立一條加權有向邊e(v,u),其權重為所有給定排名列表的差值.此外,對所有權重進行歸一化處理,以便每個節(jié)點的出度邊權重總和為1.對每個節(jié)點u構建Pg(u)值作為排名得分,Pg(u)定義為

4.2 優(yōu)化類方法

上述啟發(fā)式方法盡管在運算速度上有優(yōu)勢,但是并不能在理論上保證最終排名的性能最優(yōu)性.針對這一不足,一些學者提出了優(yōu)化類方法,通過優(yōu)化基于某一性能指標的目標函數(shù),獲得聚合排名.在衡量兩個排名之間一致性情況下,采用不同的性能指標(如距離函數(shù)、等級相關系數(shù)和違例數(shù)等)會得到不同的優(yōu)化方法[7,12,13,45-47].不同性能指標之間有時可相互轉化,比如在FL情況下,KS距離和肯德爾 τ 距離完全等價[48];此外,KS距離函數(shù)和τx等級相關系數(shù)是等價的,具有線性變換關系[45].

4.2.1 分支定界方法(FAST)

肯德爾提出了 τa和τb等級相關系數(shù)[39],前者適用于FL,而后者還適用于TL.因為 τb在處理平局方面存在問題,Emond和Mason[45]基于 τb提出τx等級相關系數(shù).在一個包含M個對象的列表中,定義分數(shù)矩陣A為一個方陣,對于任意兩個對象u和v,如果u排在v前面或者與v形成平局,則auv=1;如果 u排在 v后面,則 auv=-1;如果u和v相等,則 auv=0,即A對角線上元素始終為0.因此,τb在處理平局時將其分數(shù)矩陣對應元素置為0,而 τx置為1,故而分數(shù)矩陣中除對角線以外的0元素表征無比較信息.給定兩個列表Rμ1和等級相關系數(shù)定義為

Emond和Mason[45]基于 τx提出一個分支定界算法來尋找聚合排名,即尋找一個聚合排名RC使平均加權 τx等級相關系數(shù)最大(或平均加權KS距離最小),其目標函數(shù)為

注意: 此處的目標函數(shù)與通用目標函數(shù)(1)式是一致的,因為 τx與KS距離具有線性變換關系.本文所有基礎排名列表的權重都取1,以表征所有基礎排名列表一樣重要.上述目標函數(shù)化簡為

4.2.2 最少違例數(shù)方法(MVR)

在給定對象兩兩比較信息情況下,Pendings等[49]利用0—1線性整數(shù)規(guī)劃來尋找一個聚合排名以使對象不一致數(shù)量最少.如果一個方陣每一行從左到右元素依次增大,每一列從上至下依次減小,那么該方陣就稱為坡型矩陣.對于一個方陣,違反坡型結構的元素對數(shù)就是違例數(shù)(注意:此處違例數(shù)與KwikSort違例數(shù)[27]定義不一樣).MVR旨在盡可能尋找這樣一個坡型結構,從而使違例數(shù)最少.MVR目標函數(shù)為

其中方陣X是決策矩陣,其值xij=1表示將mi置于mj前面,否則置于后面,并且需滿足三個條件:1)xij∈{0,1};2)xij+xji=1;3)xij+xjk+xki≤2.方陣C用于計算與坡型矩陣的違例數(shù).對任意i和j,cij=#{k|dik＜djk}+#{k|dki＞dkj},其中前面的列表數(shù)量與將mj排在mi前面的列表數(shù)量的差值,以衡量輸入排名列表之間的一致程度.值得注意的是,MVR采用對象成對比較方式來表達偏好信息,其最原始的應用場景是各類循環(huán)賽,但在排名聚合背景下,可將基礎排名列表轉換為兩兩比較信息.如果出現(xiàn)平局或比較的兩個對象至少有一個并未參與某一排名,則不計算這兩個對象在該排名中的得分,因為未參與該排名,故而無法得知孰強孰弱.

4.3 算法比較

本文主要基于Mallows模型生成的完全列表、包含平局的列表和不完全列表,利用相似性指標來考察不同類型的列表數(shù)據對算法的影響.從算法自身設計角度來說,除少數(shù)算法以外,多數(shù)都可以直接處理不同類型的列表.例如,除了Bio Count,Med Rank和MVR方法需要對列表作稍微調整外,其余方法均可以處理包含平局的列表;除Bio Consert,Borda Count和Med Rank需要對列表作稍微調整外,其余方法均能處理IL數(shù)據.

以上Kwik Sort,Fagin Small,Bio Consert,Borda Count和Med Rank聚合算法使用文獻[27]所提供的在線平臺進行相關實驗,MC3,Page Rank,FAST和MVR使用相關程序進行本地運算.

5 評價指標

為對比不同的排名聚合方法在不同列表類型上的表現(xiàn),需要一個通用評價指標來表征各排名之間的相似性.一個合理的相似性度量指標需要能夠處理對象未同時出現(xiàn)在排名中的情況,即列表不等長;賦予高排名對象比低排名對象更多的權重;同時相似度取值隨著排名列表長度的增長而最終收斂.在排名聚合領域,有大量指標可用于計算列表之間相似性[50-54],但是很多都不能同時滿足以上三個要求.比如,經常用于排名相似度計算的斯皮爾曼等級相關系數(shù)只能處理完全列表,當列表不等長或列表元素存在不同時不再適用;肯德爾τ距離以及廣義肯德爾距離都可計算將一個排名轉換為另一個排名所需的相鄰對象交換次數(shù),但是卻不能給排在前面的對象更高權重,同時取值隨著列表長度的增加而發(fā)散.Webber等[55]基于簡單概率用戶模型實現(xiàn)了一個滿足上述三個條件的指標—有偏等級重疊(rank-biased overlap,RBO).RBO通過在給定評估深度下計算一個基本分數(shù)(下界)和一個最大分數(shù)(上界)來提供單調性.需要點估計時,也可以計算出一個介于上下界之間的分數(shù).RBO∈[0,1],0表示兩個列表中對象完全不同,1表示兩個列表包含相同對象且相對順序一致.RBO中包含一個參數(shù)p,其決定對象被加權的程度,決定權重下降陡峭程度,p越小,指標對前面的對象加權越大.本文根據文獻[55],選取參數(shù)p=0.9.

為考察聚合算法的效能,本文根據不同的列表類型,使用2種指標.對于FL數(shù)據,由于列表生成模型基于一個中心排名均勻的產生隨機樣本,因此可以認為中心排名即為最佳的聚合排名.聚合排名與中心排名的差異性則體現(xiàn)出算法效能:

其中RC為聚合排名,R0為中心排名.

對于TL和IL數(shù)據,由于在添加平局和構造不等長列表的過程中,不可避免地使得列表不再基于中心排名列表隨機分布,(7)式不再適用.因此我們使用聚合排名與原排名的平均相似度來度量聚合效果:

其中RBO(Ri,RC)代表原排名列表Ri與聚合排名列表RC的相似度.這一度量也同樣適用于FL數(shù)據類型.

對于算法搜索時間比較方面,由于各方法使用不同的平臺、語言和優(yōu)化工具,本文不做比較.

6 數(shù)據生成模型

為評估和比較各種排名聚合方法,首先需要生成具有不同統(tǒng)計特征的數(shù)據集,包含多個相似但不相同的排名列表.TL和IL數(shù)據都可作為FL數(shù)據的變體,因此首先介紹FL數(shù)據的生成模型.當前已有多種FL類型數(shù)據生成模型[56-62],本文選用理論和應用研究中應用廣泛的Mallows模型[56,57],以更好地分析數(shù)據一致程度對排名聚合方法表現(xiàn)的影響.Mallows模型是一個基于排名列表之間距離的指數(shù)模型,包含兩個參數(shù): 中心排名 R0和離差散布參數(shù)θ .Mallows模型會給每一個排列賦予一個概率值

其中d代表某種距離函數(shù),如肯德爾τ距離、海明距離、Cayley距離和Ulam距離等[58].本文使用肯德爾τ距離.θ控制生成的排名與中心排名的距離.當θ=0時,生成的排名R與R0無關;θ越大,概率衰減越快,生成的排名R越集中于R0附近.

(9)式雖然理論上非常簡潔,但是在實際操作中卻存在難度,一方面歸一化常數(shù)的解析解難以獲得,另一方面也很難直接通過距離隨機地生成一個排名.因此在生成隨機排名樣本的過程中,我們具體使用公式

其中S(n,d)為中心列表長度為n時,所有與其距離為d的列表的數(shù)量.在樣本生成過程中,首先基于中心排名,窮舉出所有相關的排名列表組合,獲得S(n,d)(這一步驟通常為O(n3)的復雜度).根據(10)式隨機生成距離d,再從所有與中心排名距離為d的排名列表中隨機選擇一個排名.由于(10)式中的S(n,d)隨d增長,e-θd隨d下降,因此最終獲得的隨機樣本,與中心排名的距離應該滿足一鐘型分布,即概率存在一個峰值,并在峰值距離兩端迅速下降.

由于在Mallows模型中使用肯德爾τ距離生成排名序列,而在聚合效果的度量中使用RBO相似度,為驗證生成的排名序列在RBO度量下也具有同樣的統(tǒng)計特性,基于不同的參數(shù)θ生成3組序列,計算其與中心排名的相似度RBO(圖1),獲得了預期中的鐘形分布,隨著參數(shù)θ的增長,生成的隨機排名與中心排名相似度逐漸增加.

圖1 Mallows模型在RBO度量下的表現(xiàn)Fig.1.The Mallows model under the RBO metric.

圖2 FL2 TL示意圖Fig.2.An illustration of FL2TL.

基于Mallows模型生成的FL數(shù)據,本文提出兩種方法將其轉換為TL和IL類型數(shù)據.

1)FL2TL(rt)

由(10)式獲得長度為M的FL后,生成一隨機變量T～U[0,rt*M],作為列表中的平局總量,其中rt定義為平局比例,取值范圍為[0,1].令T′=T,在2至T′之間生成一隨機數(shù)t,將一平局子塊的長度設為min(t,T′-t).令T′=max(t,T′-t),重復以上步驟,直到T′≤3.假設總共獲得了n個和為T的隨機數(shù),代表著對總長度為T的平局塊的隨機劃分.將n個隨機數(shù)由小到大排序,獲得平局子塊長度序列{T1,T2,T3,···,Tn}.在排序列表中隨機選擇n個對象,按照排名先后獲得對象序列{P1,P2,P3,···,Pn}.結合序列Ti與Pi,將序列中排在Pi到Pi+Ti-1范圍內的對象設置為平局,若兩個平局之間存在相同的對象,則合并這兩個平局為一大平局.整個過程如圖2所示.

此方法在FL數(shù)據中加入了位置隨機、長度隨機的平局塊,并且兼顧了經驗規(guī)律: 排名位置靠后的對象更容易形成包含對象數(shù)量較多的平局.同時此方法只有一個參數(shù),便于進行相關分析.為驗證模型的可行性,我們基于不同的參數(shù) θ和rt生成100個排序,計算了平均平局對(平均的總個數(shù))和平局塊(平局集中出現(xiàn)在多少分塊中)的數(shù)量(圖3),發(fā)現(xiàn)通過控制 rt可以很好地控制平局對與平均塊的數(shù)量.作為驗證,我們也使用了一些多參數(shù)的復雜模型,控制平局塊長度和位置,發(fā)現(xiàn)不同的算法并不改變本文所獲得的聚合算法性能的整體結論.

2)TL2IL(rk,Δk)

考慮到真實數(shù)據中,不同排名列表對靠前的排名個體差異并不大,因此使用前端截取的方法生成不完全列表.由1)中獲得長度為M的TL數(shù)據后,可以從列表前端截取一個長度為L的列表獲得IL數(shù)據,其中隨機變量L～U[rk×M-Δk,rk×M+Δk],rk∈[0,1]定義為列表長度比例.參數(shù)rk控制IL數(shù)據的平均長度,參數(shù)Δk控制列表長度的波動區(qū)間.

7 實驗與討論

本文主要討論少量不等長列表的聚合情況,如無特殊說明,則使用列表長度M=100,列表數(shù)量N=20,初始數(shù)據一致程度θ=0.7,rt=0.2,rk=0.8和Δk=0.2為參數(shù).本文對數(shù)據生成過程、聚合排名算法實現(xiàn)以及評價指標重復進行10次實驗,以確保結果更穩(wěn)定.由于Xiao等[30]探究了在不同 rk值下,列表長度不等長對排名聚合方法表現(xiàn)的影響,故本文不再考察 rk和Δ k 組合對聚合方法的影響.對于個別不能直接處理IL數(shù)據的算法,我們將IL數(shù)據進行了規(guī)范化(unification)處理,將其變換為算法可以處理的數(shù)據類型,再將結果與其他算法結果對比.在7.4節(jié)中將具體討論規(guī)范化處理對結果的影響.

圖3 (a)rt與平局對數(shù)量的關系;(b)rt與平局塊數(shù)量的關系Fig.3.(a)The relationship between rt and the number of ties;(b)the relationship between rt and the block number of ties.

圖4 θ 值對算法表現(xiàn)的影響Fig.4.Impact of the degree of consistency θ on the algorithm performance.

7.1 θ值對各方法表現(xiàn)的影響

整體而言,算法的表現(xiàn)主要由數(shù)據的發(fā)散程度決定.初始數(shù)據一致程度越高(θ 越大),列表的發(fā)散程度越低,最終的聚合效果也越好(圖4).對于FL數(shù)據類型,如以聚合排名與中心排名的距離作為衡量標準(圖4(a)),各算法之間的表現(xiàn)差異較大,即使在排名列表一致性較高的情況下,啟發(fā)式算法也有可能不能給出與中心排名相似的結果.優(yōu)化類算法MVR更適用于例如循環(huán)比賽成績綜合等列表長度短、數(shù)量多的場景,在少數(shù)長列表的情況下,表現(xiàn)較差,往往還不及啟發(fā)式算法.當 θ 過小時,列表非常發(fā)散,任何算法均無法獲得與中心排名相似的聚合排名.如以聚合排名與其他排名的平均距離作為衡量標準(圖4(b)—圖4(d)),在排名列表發(fā)散程度較低的情況下,平局的引入(由FL到TL)一定程度上減少了但是在發(fā)散程度較高的情況下,平局對于的影響較小.同時,對于TL和IL數(shù)據,考察聚合排名與中心排名的RBO值時,發(fā)現(xiàn)在不同的一致性程度下,得到了與類似的結論,這里只顯示了的結果.整體而言,優(yōu)化類方法FAST在不同參數(shù) θ 下,其表現(xiàn)均優(yōu)于其他算法.

7.2 N值對各方法表現(xiàn)的影響

為探究數(shù)據一致程度相同的情況下,列表數(shù)量N對聚合效果的影響,我們固定列表特征參數(shù)(M=100,θ=0.7,rt=0.2,rk=0.8,Δk=0.2),改變列表數(shù)量N,結果如圖5所示.

對于FL數(shù)據,聚合排名與中心排名的相似度基本隨列表數(shù)量的增加而增加.這與我們的直觀感知一致,數(shù)據量越大,則生成的排名列表越均勻,得到的綜合排名也越接近于中心排名.但也存在少數(shù)情況,如波達計數(shù)法(BordaCount)與MVR表現(xiàn)隨列表數(shù)量增加呈現(xiàn)不規(guī)則變化.對于TL和IL數(shù)據,聚合排名與中心排名的相似度與列表數(shù)量的關系與FL數(shù)據的結果類似,不能較好地體現(xiàn)聚合算法的差異,因此在考察N值對算法表現(xiàn)的影響時,主要考慮聚合排名與其他排名的平均相似度的變化情況.

圖5 N值對算法表現(xiàn)的影響Fig.5.Impact of the number of rank lists on the algorithm performance.

同時,對于所有列表類型,隨著列表數(shù)量的增加,各聚合算法之間的相對差異也逐漸減少.整體上優(yōu)化類方法FAST表現(xiàn)也都較為穩(wěn)定,R BO 與表現(xiàn)普遍更好.

圖6 rt 值對算法表現(xiàn)的影響Fig.6.Impact of the parameter rt on algorithm performance.

7.3 平局數(shù)量對各方法表現(xiàn)的影響

FL數(shù)據和TL數(shù)據的區(qū)別在于TL包含平局.在實際問題中,TL比FL更常見.我們調節(jié)參數(shù)rt以分析平局數(shù)量對聚合效果的影響,結果如圖6所示.

圖6(a)和圖6(b)分別表示在 θ=0.4和0.7下各聚合方法的最終結果.當 rt=0 時,對應數(shù)據類型是完全列表,隨著 rt逐漸增大,平局塊大小及其數(shù)量都在增加,聚合排名與其他排名的平均相似度逐漸下降,且波動性增加(方差增大).不同算法對平局情況的處理結果存在一定差異,例如FaginSmall方法受整體序列一致性程度影響較大,而波達計數(shù)法(BordaCount)在序列整體一致性較高但存在平局時的表現(xiàn)較弱,考慮到波達計數(shù)法被廣泛運用于簡單的投票統(tǒng)計,這也一定程度上說明為何一般投票中均沒有平局.

7.4 Unification規(guī)范化對算法表現(xiàn)的影響

對于一些不能直接處理IL類型數(shù)據的排名聚合算法,如 MedRank,BordaCount,BioConsert等,可以通過對數(shù)據的規(guī)范化處理,將IL數(shù)據變?yōu)門L數(shù)據,使得這些算法可以發(fā)揮作用.一般而言有兩種規(guī)范化處理方法: Projection和unification.Projection只考慮同時出現(xiàn)在所有列表中的對象,將未同時出現(xiàn)在所有給定列表中的對象從每個列表中刪除.Unification將未出現(xiàn)在本列表中的對象全部放到一個塊中,置于該列表底部,形成一個多對象平局.例如2節(jié)示例中的塊序列3—5經過unification處理后變?yōu)?

塊序列3: [A],[C],

塊序列3(unification): [A],[C],[B,D];

塊序列4: [A],[B],[D],

塊序列4(unification): [A],[B],[D],[C];

塊序列5: [B],[C,A],

塊序列5(unification): [B],[C,A],[D].

在7.1節(jié)與7.2節(jié)的性能比較中,為了使所有算法均可以參與比較,我們對排名列表進行了unification處理,將不同算法應用到unification后的數(shù)據進行比較.對于不能處理IL數(shù)據的算法,利用unification處理數(shù)據是合理且必須的,但是對于可以處理IL數(shù)據的算法,unification可能會帶來算法性能的高估或低估.從另一個角度來看,初始數(shù)據決定著可用信息量,而經過規(guī)范化或簡單推理以后,實際上增加了一些人為規(guī)則信息,必然會影響最終的聚合排名結果.為探究unification規(guī)范化過程對算法表現(xiàn)的影響,我們選用可以處理IL數(shù)據的優(yōu)化類方法FAST和啟發(fā)式方法PageRank,分析在處理前和處理后的算法性能變化.

為消除列表不等長對結果的影響,令 Δ k=0,改變參數(shù) rk,比較PageRank和FAST不執(zhí)行規(guī)范化和執(zhí)行規(guī)范化的結果(圖7).結果發(fā)現(xiàn),聚合排名與其他排名的RBO均值隨列表長度呈不規(guī)則變化,同時,不執(zhí)行規(guī)范化的結果總是優(yōu)于執(zhí)行規(guī)范化的結果,這也說明7.1節(jié)和7.2節(jié)中的結果,一定程度上低估了如FAST這類可以直接處理IL數(shù)據的算法,進一步說明了FAST算法在整體表現(xiàn)上的優(yōu)越性.與此同時,盡管是否進行unification所帶來的值差異不大,但是對于需要更精細結果的應用而言,謹慎處理初始數(shù)據和規(guī)范化也非常重要.

圖7 Unification對算法表現(xiàn)的影響Fig.7.Impact of unification on algorithm performance.

8 結 論

使用Mallows模型生成FL排名數(shù)據,并提出一套TL和IL數(shù)據生成機制以生成人工可控的排名數(shù)據,同時,結合有偏等級重疊指標來探究數(shù)據特征對不同排名聚合方法的影響.通過本文提出的數(shù)據生成機制,可以生成具有不同統(tǒng)計特征的可控數(shù)據集.實驗結果表明,啟發(fā)式方法雖然簡單,但是在排序列表相似度較高、列表相對簡單的情況下,能夠接近甚至超過一些優(yōu)化類方法的結果,例如在完全列表情況下,波達計數(shù)法簡單可行,最終結果也基本可以接受.整體而言,基于距離優(yōu)化的分支定界方法(FAST)優(yōu)于其他各類算法,在不同類型的排序列表中表現(xiàn)非常穩(wěn)定,能夠很好地完成少量長列表的排名聚合.