李純果，李海峰

(1.河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北保定　071002；2.河北大學(xué)黨委組織部，河北保定　071002)

無監(jiān)督排序?qū)W習(xí)算法的一致性比較

李純果1，李海峰2

(1.河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北保定071002；2.河北大學(xué)黨委組織部，河北保定071002)

摘要：對(duì)于無監(jiān)督的排序?qū)W習(xí)算法來說，排序結(jié)果的評(píng)價(jià)指標(biāo)是非常具有挑戰(zhàn)性的問題.從一致性的角度，比較了4種比較典型的無監(jiān)督排序?qū)W習(xí)方法，并在機(jī)器學(xué)習(xí)標(biāo)準(zhǔn)數(shù)據(jù)庫中進(jìn)行實(shí)驗(yàn)比較分析.結(jié)果顯示，RPC這種非線性的無監(jiān)督排序融合方法產(chǎn)生的排序結(jié)果有最小的Kendall距離和Spearman簡捷距離，體現(xiàn)了RPC在無監(jiān)督排序方法上的優(yōu)越性.

關(guān)鍵詞：啟發(fā)式排序；學(xué)習(xí)式排序；排序一致性；RPC

DOI：10.3969/j.issn.1000-1565.2015.02.013

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：志碼：A

文章編號(hào)：編號(hào)：1000-1565(2015)02-0182-06

Abstract:Unsupervised ranking has a big challenge that there is no standard metric to measure the ranking results. This paper tries to propose a comparison scheme for unsupervised ranking based on ranking consensus. Some metrics used in supervised ranking can be used here to measure unsupervised ranking consensus. However, these metrics are taken between ranking lists and attributes, rather than ranking lists and ranking labels. Experimental results on UCI datasets show that RPC, which is one kind of unsupervised ranking aggregation method, has the minimum Kendall Distance and Spearman Footrule Distance than the other representative unsupervised ranking methods.

收稿日期:2014-09-12

基金項(xiàng)目：河北省自然科學(xué)基金資助項(xiàng)目(F2013201060)

Comparison analysis on ranking consensus

LI Chunguo1, LI Haifeng2

(1. College of Mathematics and Information Science, Hebei University, Baoding 071002, China;

2. Department of Party Committee Organization, Hebei University, Baoding 071002, China)

Key words: heuristic ranking;learning to rank;ranking consensus;RPC

第一作者:李純果(1981-)，女，河北邯鄲人，河北大學(xué)講師，主要從事模式識(shí)別理論基礎(chǔ)與應(yīng)用、機(jī)器學(xué)習(xí)等研究.

E-mail:lichunguo@cmc.hbu.cn

排序問題是實(shí)際應(yīng)用中的一個(gè)很基礎(chǔ)的問題，比如說信息檢索中的網(wǎng)頁搜索問題[1-2].一般地，排序問題分為啟發(fā)式排序和學(xué)習(xí)式排序.啟發(fā)式排序是根據(jù)給定排序?qū)ο笤诙鄠€(gè)屬性上的觀測值，基于直觀或經(jīng)驗(yàn)構(gòu)造一種融合多屬性觀測值的方法，得到每個(gè)排序?qū)ο蟮脑u(píng)分.學(xué)習(xí)式排序是把機(jī)器學(xué)習(xí)的方法應(yīng)用到排序中，通過優(yōu)化一定的規(guī)則，得到每個(gè)排序?qū)ο蟮呐判蛭恢?對(duì)于具有連接結(jié)構(gòu)的排序?qū)ο髞碚f，基于啟發(fā)式的排序方法不再適用，而對(duì)于當(dāng)今大數(shù)據(jù)的局勢，更需要學(xué)習(xí)式的排序方法.

由于機(jī)器學(xué)習(xí)方法是根據(jù)一定的學(xué)習(xí)目標(biāo)來進(jìn)行排序，對(duì)象的排序順序根據(jù)學(xué)習(xí)目標(biāo)不同而不同.對(duì)于監(jiān)督學(xué)習(xí)來說，NDCG(normalized discount cumulative gain)和MAP(mean average precision)是應(yīng)用的2種比較多的排序優(yōu)化目標(biāo)函數(shù).在文本檢索中，NDCG是歸一化的累計(jì)折扣相關(guān)值[3]，當(dāng)NDCG達(dá)到最大時(shí)，會(huì)給出與檢索文本排序最相關(guān)的網(wǎng)頁順序；而MAP計(jì)算的是網(wǎng)頁評(píng)分對(duì)檢索文本的平均值[4]. 對(duì)于沒有真實(shí)的排序?qū)ο箜樞虻臅r(shí)候，也就是無監(jiān)督學(xué)習(xí)排序，NDCG和MAP都不能用做優(yōu)化排序目標(biāo)進(jìn)行學(xué)習(xí).無監(jiān)督學(xué)習(xí)排序算法面臨很多挑戰(zhàn)，由于沒有真實(shí)排序順序作為參照，因而最重要的挑戰(zhàn)就是“如何保證所得到的排序順序的合理性”.例如，在大學(xué)排名中，根據(jù)多個(gè)選定指標(biāo)的統(tǒng)計(jì)數(shù)據(jù)，Times,QS,ARWU,Webometrics的做法基本上都是線性加權(quán)和的方式，即給每個(gè)指標(biāo)賦予一定權(quán)重值，然后計(jì)算把多指標(biāo)觀測數(shù)據(jù)計(jì)算加權(quán)算術(shù)平均，得到平均分值.然而這種加權(quán)算術(shù)平均的方式往往會(huì)根據(jù)權(quán)重的不同改變排序?qū)ο蟮呐判蝽樞?，?quán)重值是根據(jù)不同的專家給定，就會(huì)存在權(quán)重比較不客觀問題.因此，對(duì)于無監(jiān)督的排序方法，需要選擇合理適用的排序目標(biāo)，或者說是如何選擇評(píng)價(jià)無監(jiān)督排序結(jié)果的客觀指標(biāo).

對(duì)于無監(jiān)督排序結(jié)果的評(píng)價(jià)指標(biāo)，有些學(xué)者提出了用排序一致性的指標(biāo)來評(píng)價(jià)，即當(dāng)沒有真實(shí)的排序順序作為參照時(shí)，最終得到的排序結(jié)果希望與根據(jù)各個(gè)指標(biāo)得到的排序結(jié)果盡可能的一致.早在最早的排序問題中，例如Borda計(jì)數(shù)法[5]，就是排序結(jié)果保持大多數(shù)的一致性所提出的.

1一致性衡量方法

假設(shè)無監(jiān)督的排序?qū)ο鬄锳={a1,a2,…,an}，排序?qū)ο笤赿個(gè)屬性V={v1,v2,…,vn}上的觀測結(jié)果記為X={x1,x2,…,xn}.對(duì)A中的元素進(jìn)行排序，轉(zhuǎn)換為對(duì)X的n個(gè)向量進(jìn)行排序，即需要根據(jù)觀測值，給出ai1≤ai2…≤ain，其中i1,i2,…,in是一組{1,2,…,n}的排列，記為τ.無監(jiān)督排序的任務(wù)就是根據(jù)排序?qū)ο笤赿個(gè)屬性上的觀測結(jié)果，學(xué)習(xí)到一個(gè)最接近于真實(shí)存在的排列τ.

無論是監(jiān)督排序?qū)W習(xí)方法還是無監(jiān)督排序?qū)W習(xí)方法，首先都要確定一個(gè)評(píng)價(jià)排序的量化指標(biāo)，例如NDCG，MAP，等等.在此指標(biāo)的指導(dǎo)下，來評(píng)價(jià)一個(gè)排序?qū)W習(xí)算法的優(yōu)劣.指標(biāo)的選取，或者是發(fā)現(xiàn)現(xiàn)有指標(biāo)存在的問題并對(duì)其改進(jìn)，得到新的指標(biāo)，或者是定義排序指標(biāo)公理(不證自明的結(jié)論)并找到符合所有公理的指標(biāo). Kumar曾在2010年就提出了選擇排序指標(biāo)的5條公理[6].

1)簡單性：容易理解；

2)廣泛的容納性：不僅支持基于分?jǐn)?shù)的排序融合，還支持基于排序的排序融合；

3)普適性：可以退化到普通的度量指標(biāo)；

4)滿足基本性質(zhì)：具有尺度不變性，不因標(biāo)簽改變而改變，三角不等式，等等；

5)與其他度量相關(guān)聯(lián)：指導(dǎo)排序的方式相似，可以選擇最適合的度量.

并且提出Kendall距離(Kendall tau distance)[7]和Spearman簡捷距離(Spearman’s footrule distance)[8]就符合這5條公理.

根據(jù)觀測結(jié)果X對(duì)對(duì)象進(jìn)行排序，可以直接采用啟發(fā)式的排序融合方法，例如基于分值的排序融合，對(duì)各屬性賦予權(quán)重值，每個(gè)對(duì)象的得分為對(duì)象i在各屬性上的觀測值的加權(quán)平均；或者采用基于排序的融合方法，把根據(jù)各屬性值得到的排序表進(jìn)行融合.但是這些融合方式都是啟發(fā)式的，在無監(jiān)督排序?qū)W習(xí)中，由于沒有排序標(biāo)簽可以參考，沒有辦法衡量哪一種排序結(jié)果的可信度更高一些，所以需要尋求一定的衡量方法.此時(shí)可以考慮用一致性的衡量：如果排序的結(jié)果與根據(jù)屬性值排序的結(jié)果都一致，則是一種理想的排序結(jié)果；如果兩者有很大差異，說明排序算法沒有遵循一致性的排序宗旨，導(dǎo)致排序結(jié)果不具有可信性.

1.1　NDCG

DCG(discounted cumulative gain)[3-4]是一種衡量排序效果的度量，常用來測量網(wǎng)絡(luò)搜索引擎算法的有效性.對(duì)于一個(gè)給定的搜索結(jié)果，DCG通過搜索結(jié)果對(duì)輸入關(guān)鍵詞的相關(guān)性的排序，并根據(jù)排序位置對(duì)相關(guān)性打折(Discounted)，計(jì)算該搜索結(jié)果的累積增益,稱之為累積折扣增益.給定{1,2,…,n}的一個(gè)排列τ，其DCG定義為

其中，τ(i)是第i個(gè)元素在τ中的排列位置.由于有的數(shù)據(jù)集大小的不同，所以可能導(dǎo)致搜索引擎的DCG有所不同.為了避免由于測試數(shù)據(jù)集而產(chǎn)生的不同的DCG，定義了NDCG：

其中，Zn是歸一化常數(shù).NDCG使得搜索引擎的測試效果不隨測試集的大小而改變.

在信息檢索中，NDCG把相關(guān)分為多個(gè)級(jí)別，高度相關(guān)的文章比部分相關(guān)的文檔更有價(jià)值，其在評(píng)價(jià)中應(yīng)該賦予更大的權(quán)值[9].文檔在序列中的位置越靠后，這個(gè)文檔的價(jià)值越小，從用戶的角度考慮，由于時(shí)間、精力等原因，用戶可能根本不會(huì)去看這些文檔.NDCG還可以用來衡量排序結(jié)果的一致性.例如，按照每個(gè)屬性值，可以對(duì)排序?qū)ο笞鲆粋€(gè)排列順序，而對(duì)于每個(gè)排序?qū)ο蟮目傇u(píng)分值(score label)得到的排序結(jié)果，相對(duì)于每個(gè)屬性值的排序結(jié)果，可以得到一個(gè)一致性檢測.比較2個(gè)搜索引擎在同一個(gè)搜索集上的NDCG的大小，可以確定哪一個(gè)搜索引擎給排序?qū)ο蟮脑u(píng)分值更遵從一致性的原則.

1.2　SRCC

斯皮爾曼相關(guān)系數(shù)(Spearman rank correlation coefficients, 簡稱SRCC)是衡量2個(gè)變量的依賴性的非參數(shù)指標(biāo).2個(gè)變量x和y的SRCC定義為

其中，di是第i個(gè)元素在x和y的排列中的位置差.SRCC利用單調(diào)方程評(píng)價(jià)2個(gè)統(tǒng)計(jì)變量的相關(guān)性，如果數(shù)據(jù)沒有重復(fù)值，并且當(dāng)2個(gè)變量完全單調(diào)相關(guān)時(shí)，SRCC為+1或-1.根據(jù)這個(gè)特性，SRCC可以用來衡量排序結(jié)果是否與屬性的排序結(jié)果的一致性.如果排序?qū)ο蟾鶕?jù)屬性值得到的排序結(jié)果與根據(jù)屬性值排序的結(jié)果是完全一樣的，說明排序算法可以得到與屬性值一致的排序結(jié)果，SRCC的絕對(duì)值接近于1.排序算法的SRCC越接近于1，說明排序結(jié)果與屬性值排序結(jié)果越一致.

1.3　Kendall距離

Kendall距離(Kendall tau distance)是指2個(gè)排序表中2個(gè)對(duì)象的排序位置不同的對(duì)象對(duì)的個(gè)數(shù)[7].如果2個(gè)排序表完全一致，Kendall距離達(dá)到最小為零；而2個(gè)排序表中的對(duì)象的位置越混亂，Kendall距離越大.因此，Kendall距離可以用來衡量排序的一致性，作為無監(jiān)督排序結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)之一.給定2個(gè){1,2,…,n}的排列τ和κ，τ和κ的Kendall距離定義為

K(τ,κ)=|{(i,j):iκ(j))∨(τ(i)>τ(j)∧κ(i)<κ(j))}|，

其中，τ(i)和κ(i)分別是第i個(gè)排序?qū)ο笤陉?duì)列τ和κ中的排列位置.

1.4　Spearman簡捷距離

Spearman簡捷距離(Spearman’s footrule distance)計(jì)算了第i個(gè)排序?qū)ο笤?個(gè)排列中的位置的絕對(duì)距離之和，定義為[8]

其中，τ(i)和κ(i)分別是第i個(gè)排序?qū)ο笤陉?duì)列τ和κ中的排列位置.

2排序方法比較

針對(duì)綜合評(píng)價(jià)問題，基于一維流形的思想，Li等人[10]基于一維流形綜合評(píng)價(jià)方法，提出了排序主曲線(ranking principal curves，RPC)無監(jiān)督排序模型.該模型通過非線性融合排序?qū)ο笤谂判蛴^測指標(biāo)上的觀測值，給出每個(gè)排序?qū)ο笠粋€(gè)綜合評(píng)分結(jié)果.一維流形綜合評(píng)價(jià)方法是主成分分析方法(principal component analysis, PCA)的非線性推廣(圖1)，根據(jù)研究對(duì)象的各評(píng)價(jià)指標(biāo)的多屬性觀測數(shù)據(jù)，用機(jī)器學(xué)習(xí)的方法確定穿過數(shù)據(jù)中心的一條曲線，即為面向排序的一維流形.根據(jù)研究對(duì)象的觀測數(shù)據(jù)在一維流形上的投影點(diǎn)可以確定一個(gè)索引值為研究對(duì)象的綜合評(píng)價(jià)分值，根據(jù)此分值可以確定研究對(duì)象的綜合排名.RPC的學(xué)習(xí)排序過程如圖2所示.

圖1　PCA與RPC排序方法Fig.1　Ranking methods of PCA and RPC

圖2　RPC學(xué)習(xí)流程　Fig.2　Learning scheme of RPC

雖然KPCA(kernel principal curve analysis)也是PCA的非線性推廣[11]，但KPCA是把原數(shù)據(jù)點(diǎn)映射到高維數(shù)據(jù)空間，在高維空間中進(jìn)行PCA操作，所以KPCA的實(shí)質(zhì)仍是PCA，而主曲線才是真正的從學(xué)習(xí)動(dòng)機(jī)上非線性推廣了PCA，即從線性x=λμ+μ0到非線性x=f(λ)+μ0的推廣,其中，μ0是數(shù)據(jù)的中心點(diǎn)，μ是PCA第一主成分方向，λ是在主成分上的值，f是非線性函數(shù)向量.本文把RPC得到的排序結(jié)果與KPCA和PCA的排序結(jié)果進(jìn)行了一致性比較.

排序融合是另一種應(yīng)用很廣泛的無監(jiān)督排序方式[5].通常情況下，這種排序方式都是啟發(fā)式的融合，例如Borda計(jì)數(shù)法，Condorcet方法，Kemeny方法.這些方法通常應(yīng)用在選舉中，使得選舉結(jié)果符合大多數(shù)人的排序結(jié)果，也是一種一致性的排序融合.本文采用了基于序列的排序融合方法(RankAgg)，每個(gè)屬性都有相同的排序權(quán)重，根據(jù)每個(gè)屬性值對(duì)排序?qū)ο笈判?，然后取位置的中間值作為排序?qū)ο蟮淖罱K得分，并依據(jù)得分進(jìn)行排名.

3一致性比較

首先，比較了PCA，KPCA，RankAgg和RPC 4種方法的Kendall距離和Spearman簡捷距離，實(shí)驗(yàn)結(jié)果如圖3所示.由于無監(jiān)督排序方法沒有排序標(biāo)簽，通過UCI數(shù)據(jù)庫中的回歸數(shù)據(jù)，把回歸分值作為每條記錄的綜合評(píng)價(jià)分值.將4種方法產(chǎn)生的排序結(jié)果與評(píng)價(jià)分值的結(jié)果做對(duì)比，來評(píng)價(jià)RPC方法在無監(jiān)督排序上的效果.

圖3　4種無監(jiān)督排序方法在Kendall距離和Spearman簡捷距離上的比較Fig.3　Comparisons on Kendall Distances and Spearman Footrule Distances of four unsupervised methods

從圖3可以看出，在選擇的1個(gè)人工數(shù)據(jù)集和4個(gè)UCI數(shù)據(jù)集上，KPCA幾乎在所有數(shù)據(jù)集上的排序結(jié)果與目標(biāo)排序標(biāo)簽的Kendall距離和Spearman距離最大，這也從側(cè)面說明了Kernel技術(shù)把觀測樣本從原數(shù)據(jù)空間映射到高維空間，映射不具有保序性.雖然KPCA可以實(shí)現(xiàn)非線性降維，但是不適用于排序的非線性降維，這是因?yàn)榈途S到高維的映射沒有保持?jǐn)?shù)據(jù)間的序關(guān)系.對(duì)于其他的非線性降維，類似于LPP，Isomap，LEE等方法，都存在類似的問題.

PCA與基于MedianAgg的RankAgg方法具有類似的排序融合方式.從排序融合的角度看，PCA是學(xué)習(xí)融合權(quán)重的分值融合方法，而RankAgg是基于序列的融合方法.2類方法都是線性融合方法，對(duì)于隱含數(shù)據(jù)結(jié)構(gòu)為非線性的數(shù)據(jù)不適用.由于數(shù)據(jù)本身的數(shù)據(jù)結(jié)構(gòu)未知，所以不能貿(mào)然選擇線性或非線性的排序融合方法.如果排序的應(yīng)用對(duì)象是網(wǎng)絡(luò)搜索和信息檢索，排序?qū)ο蟮囊?guī)模較大，簡單的排序融合就比較有效率，因?yàn)橐笏阉饕嫘枰诳扇萑痰臅r(shí)間內(nèi)搜索結(jié)果.而本文討論的排序?qū)ο笫庆o態(tài)的，排序?qū)ο蟮膫€(gè)數(shù)和排序指標(biāo)都是確定的，所以，不同于網(wǎng)絡(luò)搜索和信息檢索對(duì)排序速度的要求，這里討論的排序要求盡可能的尊重事實(shí).

Spearman距離/cm圖4　RPC可以反映觀測值的微小區(qū)別Fig.4　RPC can detect the minor differences in numerical observations

4總結(jié)

對(duì)于排序?qū)W習(xí)，監(jiān)督的學(xué)習(xí)方法通常用NDCG，MAP等指標(biāo)來判別算法排序的結(jié)果與目標(biāo)排序標(biāo)簽的是否一致.而對(duì)于非監(jiān)督的排序?qū)W習(xí)算法的評(píng)價(jià)，一直是一個(gè)很有爭議的問題.已經(jīng)有相關(guān)學(xué)者提出，可以通過排序融合的方式融合屬性值或?qū)傩灾档呐判蛐蛄?，得到一個(gè)綜合的排序結(jié)果.排序算法在信息檢索、網(wǎng)絡(luò)搜索引擎方面已經(jīng)有了飛速的發(fā)展.

主要針對(duì)無監(jiān)督的排序方法，討論了4種排序方法對(duì)于排序一致性的比較.RPC的非線性排序融合方法不僅能處理線性數(shù)據(jù)結(jié)構(gòu)問題，也能處理非線性結(jié)構(gòu)問題，從而在Kendall距離和Spearman簡捷距離上體現(xiàn)了一定的優(yōu)勢.但是，RPC的排序融合方法潛在的要求是綜合評(píng)價(jià)分值與各屬性值成單調(diào)關(guān)系(單調(diào)遞增或單調(diào)遞減)，這也是大多數(shù)排序問題所滿足的條件，RPC正是充分利用了這個(gè)排序問題的先驗(yàn)知識(shí)而設(shè)計(jì)的非線性排序融合方法.對(duì)于不滿足這個(gè)先驗(yàn)知識(shí)的排序問題，RPC可以做相應(yīng)的調(diào)整，仍然利用RPC的學(xué)習(xí)架構(gòu)來進(jìn)行排序融合，具體的操作是未來的工作之一.未來的工作還包括通過敏感性分析來進(jìn)行無監(jiān)督排序?qū)W習(xí)的屬性選擇(feature selection)問題.

參考文獻(xiàn):

[1]DWORKC,KUMAR R, NAOR M, et al.Rank aggregation methods for the web[Z]. Proceedings of 10th International Conference on World Wide Web,Hong Kong, 2001.

[2]LI Hang. A short introduction to learning to rank [J].IEICE Transactions on Information Systems, 2011, E94-D(10):1-9.

[3]VOLKOVS M N, ZENEL R S. New learning methods for supervised and unsupervised preference aggregation [J]. Journal of Machine Learning Research, 2014, 15:1135-1176.

[4]PEDRONETTE D C G,TORRES R do S,CALUMBY R T. Using contextual spaces for image re-ranking and rank aggregation[J]. Multimedia Tools and Applications, 2014, 69(3): 689-716.

[5]LIN Shili. Rank aggregation methods [J]. Wiley Interdisciplinary Reviews: Computational Statistics, 2010, 2(5):555-570.

[6]KUMAR R, VASSILVITSKII S. Generalized distances between rankings [Z]. Proceedings of International Conference on World Wide Web,Raleigh,2010.

[7]KENDALL M. A new measure of rank correlation [J]. Biometrika, 1938, 30:81-89.

[8]CONTRERAS I. Emphasizing the rank positions in a distance-based aggregation procedure[J]. Decision Support Systems, 2011, 51(1): 240-245.

[9]BAEZA-YATES R, RIBEIRO-BETO B.Modern information retrieval [M].New York:ACM Press,1999.

[10]LI Chunguo,MEI Xing,HU Baogang.Unsupervised ranking on multi-attribute objects based on principal curves[J/OL].[2014-02-19].http://arxiv.org/pdf/1402.4542.pdf.

[11]BISHOP C. Pattern recognition and machine learning [M]. New York: Springer, 2006.

(責(zé)任編輯：孟素蘭)