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

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

2)(中國(guó)人民解放軍陸軍勤務(wù)學(xué)院國(guó)防經(jīng)濟(jì)系,重慶 500106)

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

1 引 言

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

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

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

2 基本概念

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

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

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

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

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

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

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

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

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

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

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

3 相關(guān)研究

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

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

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

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

4 排名聚合方法及其分類

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

4.1 啟發(fā)式方法

4.1.1 KwikSort

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

4.1.2 FaginSmall

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

4.1.3 BioConsert

給定M個(gè)對(duì)象和N個(gè)排名列表Rμ1,···,RμN(yùn)(μ1,···,μN(yùn)是每個(gè)列表對(duì)應(yīng)的排名機(jī)制),通用目標(biāo)函數(shù)為

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

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

4.1.4 波達(dá)計(jì)數(shù)法(BordaCount)

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

4.1.5 MedRank

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

4.1.6 馬爾科夫鏈方法(MC3)

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

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

4.1.7 PageRank

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

4.2 優(yōu)化類方法

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

4.2.1 分支定界方法(FAST)

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

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

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

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

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

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

4.3 算法比較

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

以上Kwik Sort,Fagin Small,Bio Consert,Borda Count和Med Rank聚合算法使用文獻(xiàn)[27]所提供的在線平臺(tái)進(jìn)行相關(guān)實(shí)驗(yàn),MC3,Page Rank,FAST和MVR使用相關(guān)程序進(jìn)行本地運(yùn)算.

5 評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

6 數(shù)據(jù)生成模型

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

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

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

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

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

圖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ù)據(jù),本文提出兩種方法將其轉(zhuǎn)換為TL和IL類型數(shù)據(jù).

1)FL2TL(rt)

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

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

2)TL2IL(rk,Δk)

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

7 實(shí)驗(yàn)與討論

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

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

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

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

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

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

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

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

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

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

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

7.3 平局?jǐn)?shù)量對(duì)各方法表現(xiàn)的影響

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

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

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

對(duì)于一些不能直接處理IL類型數(shù)據(jù)的排名聚合算法,如 MedRank,BordaCount,BioConsert等,可以通過(guò)對(duì)數(shù)據(jù)的規(guī)范化處理,將IL數(shù)據(jù)變?yōu)門L數(shù)據(jù),使得這些算法可以發(fā)揮作用.一般而言有兩種規(guī)范化處理方法: Projection和unification.Projection只考慮同時(shí)出現(xiàn)在所有列表中的對(duì)象,將未同時(shí)出現(xiàn)在所有給定列表中的對(duì)象從每個(gè)列表中刪除.Unification將未出現(xiàn)在本列表中的對(duì)象全部放到一個(gè)塊中,置于該列表底部,形成一個(gè)多對(duì)象平局.例如2節(jié)示例中的塊序列3—5經(jīng)過(guò)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é)的性能比較中,為了使所有算法均可以參與比較,我們對(duì)排名列表進(jìn)行了unification處理,將不同算法應(yīng)用到unification后的數(shù)據(jù)進(jìn)行比較.對(duì)于不能處理IL數(shù)據(jù)的算法,利用unification處理數(shù)據(jù)是合理且必須的,但是對(duì)于可以處理IL數(shù)據(jù)的算法,unification可能會(huì)帶來(lái)算法性能的高估或低估.從另一個(gè)角度來(lái)看,初始數(shù)據(jù)決定著可用信息量,而經(jīng)過(guò)規(guī)范化或簡(jiǎn)單推理以后,實(shí)際上增加了一些人為規(guī)則信息,必然會(huì)影響最終的聚合排名結(jié)果.為探究unification規(guī)范化過(guò)程對(duì)算法表現(xiàn)的影響,我們選用可以處理IL數(shù)據(jù)的優(yōu)化類方法FAST和啟發(fā)式方法PageRank,分析在處理前和處理后的算法性能變化.

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

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

8 結(jié) 論

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