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

李純果，李海峰

(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)

摘要：對于無監(jiān)督的排序?qū)W習(xí)算法來說，排序結(jié)果的評價指標是非常具有挑戰(zhàn)性的問題.從一致性的角度，比較了4種比較典型的無監(jiān)督排序?qū)W習(xí)方法，并在機器學(xué)習(xí)標準數(shù)據(jù)庫中進行實驗比較分析.結(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

中圖分類號：TP181

文獻標志碼：志碼：A

文章編號：編號：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

基金項目：河北省自然科學(xué)基金資助項目(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é)講師，主要從事模式識別理論基礎(chǔ)與應(yīng)用、機器學(xué)習(xí)等研究.

E-mail:lichunguo@cmc.hbu.cn

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

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

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

1一致性衡量方法

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

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

1)簡單性：容易理解；

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

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

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

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

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

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

1.1　NDCG

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

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

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

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

1.2　SRCC

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

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

1.3　Kendall距離

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

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

其中，τ(i)和κ(i)分別是第i個排序?qū)ο笤陉犃笑雍挺手械呐帕形恢?

1.4　Spearman簡捷距離

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

其中，τ(i)和κ(i)分別是第i個排序?qū)ο笤陉犃笑雍挺手械呐帕形恢?

2排序方法比較

針對綜合評價問題，基于一維流形的思想，Li等人[10]基于一維流形綜合評價方法，提出了排序主曲線(ranking principal curves，RPC)無監(jiān)督排序模型.該模型通過非線性融合排序?qū)ο笤谂判蛴^測指標上的觀測值，給出每個排序?qū)ο笠粋€綜合評分結(jié)果.一維流形綜合評價方法是主成分分析方法(principal component analysis, PCA)的非線性推廣(圖1)，根據(jù)研究對象的各評價指標的多屬性觀測數(shù)據(jù)，用機器學(xué)習(xí)的方法確定穿過數(shù)據(jù)中心的一條曲線，即為面向排序的一維流形.根據(jù)研究對象的觀測數(shù)據(jù)在一維流形上的投影點可以確定一個索引值為研究對象的綜合評價分值，根據(jù)此分值可以確定研究對象的綜合排名.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ù)點映射到高維數(shù)據(jù)空間，在高維空間中進行PCA操作，所以KPCA的實質(zhì)仍是PCA，而主曲線才是真正的從學(xué)習(xí)動機上非線性推廣了PCA，即從線性x=λμ+μ0到非線性x=f(λ)+μ0的推廣,其中，μ0是數(shù)據(jù)的中心點，μ是PCA第一主成分方向，λ是在主成分上的值，f是非線性函數(shù)向量.本文把RPC得到的排序結(jié)果與KPCA和PCA的排序結(jié)果進行了一致性比較.

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

3一致性比較

首先，比較了PCA，KPCA，RankAgg和RPC 4種方法的Kendall距離和Spearman簡捷距離，實驗結(jié)果如圖3所示.由于無監(jiān)督排序方法沒有排序標簽，通過UCI數(shù)據(jù)庫中的回歸數(shù)據(jù)，把回歸分值作為每條記錄的綜合評價分值.將4種方法產(chǎn)生的排序結(jié)果與評價分值的結(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個人工數(shù)據(jù)集和4個UCI數(shù)據(jù)集上，KPCA幾乎在所有數(shù)據(jù)集上的排序結(jié)果與目標排序標簽的Kendall距離和Spearman距離最大，這也從側(cè)面說明了Kernel技術(shù)把觀測樣本從原數(shù)據(jù)空間映射到高維空間，映射不具有保序性.雖然KPCA可以實現(xiàn)非線性降維，但是不適用于排序的非線性降維，這是因為低維到高維的映射沒有保持數(shù)據(jù)間的序關(guān)系.對于其他的非線性降維，類似于LPP，Isomap，LEE等方法，都存在類似的問題.

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

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

4總結(jié)

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

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

參考文獻:

[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é)任編輯：孟素蘭)