无监督排序学习算法的一致性比较
李纯果1，李海峰2
【摘 要】摘 要：对于无监督的排序学习算法来说，排序结果的评价指标是非常具有挑战性的问题.从一致性的角度，比较了4种比较典型的无监督排序学习方法，并在机器学习标准数据库中进行实验比较分析.结果显示，RPC这种非线性的无监督排序融合方法产生的排序结果有最小的Kendall距离和Spearman简捷距离，体现了RPC在无监督排序方法上的优越性. 【期刊名称】河北大学学报（自然科学版） 【年(卷),期】2015(035)002 【总页数】6
【关键词】启发式排序；学习式排序；排序一致性；RPC 基金项目：河北省自然科学基金资助项目(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-)，女，河北邯郸人，河北大学讲师，主要从事模式识别理论基础与应用、机器学习等研究. E-mail:lichunguo@cmc.hbu.cn
排序问题是实际应用中的一个很基础的问题，比如说信息检索中的网页搜索问题[1-2].一般地，排序问题分为启发式排序和学习式排序.启发式排序是根据给定排序对象在多个属性上的观测值，基于直观或经验构造一种融合多属性观测值的方法，得到每个排序对象的评分.学习式排序是把机器学习的方法应用到排序中，通过优化一定的规则，得到每个排序对象的排序位置.对于具有连接结构的排序对象来说，基于启发式的排序方法不再适用，而对于当今大数据的局势，更需要学习式的排序方法.
由于机器学习方法是根据一定的学习目标来进行排序，对象的排序顺序根据学习
目
标
不
同
而
不
同
.对
于
监
督
学
习
来
说
，和
NDCG(normalized discount cumulative gain)
MAP(mean average precision)是应用的2种比较多的排序优化目标函数.在文本检索中，NDCG是归一化的累计折扣相关值[3]，当NDCG达到最大时，会给出与检索文本排序最相关的网页顺序；而MAP计算的是网页评分对检索文本的平均值[4]. 对于没有真实的排序对象顺序的时候，也就是无监督学习排序，NDCG和MAP都不能用做优化排序目标进行学习.无监督学习排序算法面临很多挑战，由于没有真实排序顺序作为参照，因而最重要的挑战就是“如何保证所得到的排序顺序的合理性”.例如，在大学排名中，根据多个选定指标的统计数据，Times,QS,ARWU,Webometrics的做法基本上都是线性加权和的方式，即给每个指标赋予一定权重值，然后计算把多指标观测数据计算加权算术平均，得到平均分值.然而这种加权算术平均的方式往往会根据权重的不同改变排序对象的排序顺序，权重值是根据不同的专家给定，就会存在权重比较不客观问题.因此，对于无监督的排序方法，需要选择合理适用的排序目标，或者
说是如何选择评价无监督排序结果的客观指标.
对于无监督排序结果的评价指标，有些学者提出了用排序一致性的指标来评价，即当没有真实的排序顺序作为参照时，最终得到的排序结果希望与根据各个指标得到的排序结果尽可能的一致.早在最早的排序问题中，例如Borda计数法[5]，就是排序结果保持大多数的一致性所提出的.
1 一致性衡量方法
假设无监督的排序对象为A={a1,a2,…,an}，排序对象在d个属性V={v1,v2,…,vn}上的观测结果记为X={x1,x2,…,xn}.对A中的元素进行排序，转换为对X的n个向量进行排序，即需要根据观测值，给出ai1≤ai2…≤ain，其中i1,i2,…,in是一组{1,2,…,n}的排列，记为τ.无监督排序的任务就是根据排序对象在d个属性上的观测结果，学习到一个最接近于真实存在的排列τ. 无论是监督排序学习方法还是无监督排序学习方法，首先都要确定一个评价排序的量化指标，例如NDCG，MAP，等等.在此指标的指导下，来评价一个排序学习算法的优劣.指标的选取，或者是发现现有指标存在的问题并对其改进，得到新的指标，或者是定义排序指标公理(不证自明的结论)并找到符合所有公理的指标. Kumar曾在2010年就提出了选择排序指标的5条公理[6]. 1)简单性：容易理解；
2)广泛的容纳性：不仅支持基于分数的排序融合，还支持基于排序的排序融合； 3)普适性：可以退化到普通的度量指标；
4)满足基本性质：具有尺度不变性，不因标签改变而改变，三角不等式，等等； 5)与其他度量相关联：指导排序的方式相似，可以选择最适合的度量.
并且提出Kendall距离(Kendall tau distance)[7]和Spearman简捷距离
无监督排序学习算法的一致性比较
