计算机应用 ›› 2011, Vol. 31 ›› Issue (07): 1740-1743.DOI: 10.3724/SP.J.1087.2011.01740

• 数据库技术 • 上一篇    下一篇

基于pairwise的改进ranking算法

程凡1,2,仲红1   

  1. 1. 安徽大学 计算机科学与技术学院,合肥 230039
    2. 中国科学技术大学 计算机科学与技术学院,合肥 230027
  • 收稿日期:2010-12-21 修回日期:2011-03-03 发布日期:2011-07-01 出版日期:2011-07-01
  • 通讯作者: 程凡
  • 作者简介:程凡(1979-),男,安徽合肥人,讲师,博士研究生,主要研究方向:信息检索、机器学习、智能计算;仲红(1965-),女,安徽合肥人,教授,主要研究方向:信息检索、信息安全、密码学。
  • 基金资助:

    安徽省自然科学基金资助项目;安徽省自然科学基金青年基金资助项目;安徽大学“211工程” 资助项目

Improved ranking algorithm based on pairwise method

CHENG Fan1,2,Hong ZHONG3   

  1. 1. College of Computer Science and Technology, Anhui University, Hefei Anhui 230039, China
    2. School of Computer Science and Technology, University of Science and Technology of China, Hefei Anhui 230027, China
    3. School of Computer Science and Technology, Anhui University, Hefei Anhui 230039, China
  • Received:2010-12-21 Revised:2011-03-03 Online:2011-07-01 Published:2011-07-01
  • Contact: CHENG Fan

摘要: 传统基于pairwise的ranking算法,学习后得到的模型在用NDCG这样的ranking标准评价时效果并不好,对此提出了一种新型ranking算法。该算法也是使用样本对作为训练数据,但定义了一个面向NDCG评估标准的目标函数。针对此目标函数非平滑、难以直接优化的特点,提出使用割平面算法进行学习,不仅解决了上述问题,而且使算法迭代的次数不再依赖于训练样本对数。最后基于基准数据集的实验证明了算法的有效性。

关键词: ranking算法, pairwise方法, 支持向量机, NDCG, 割平面

Abstract: The model learned by ranking algorithm based on traditional pairwise method does not work well by ranking measure, such as Normalized Discounted Cumulative Gain (NDCG). To solve this problem, a novel ranking algorithm is proposed. The algorithm uses the same train data as the traditional way, what different is defining a new object function faced to NDCG. For the problem that the function is non-smooth, difficult to directly optimize, the algorithm presents to use the cutting plane algorithm which not only solve the problem above but also make the number of iteration not depending on the training size. Experimental results on the benchmark datasets prove the effectiveness of the proposed algorithm.

Key words: ranking algorithm, pairwise method, Support Vector Machine (SVM), Normalized Discounted Cumulative Gain (NDCG), improved cutting plane algorithm

中图分类号: