随着关系数据库中信息量的快速增长，访问、查询关系数据库成为人们获取信息的重要途径之一^[1]。关键字查询以其简单易用的特点受到广泛关注，相比于传统的结构化查询方法(如SQL查询)，该方法不需要用户了解复杂的查询语言和数据库底层模式，为用户查询带来诸多便利^[2-3]。然而，关键字查询作为一种模糊查询方法，并不能精确地锁定数据库中与用户需求最相关的信息，而是将包含查询词的所有元组(元组单元)返回给用户。用户需要在大量查询结果中进一步筛选出自己所需要的信息。因此，按照重要性及相关性对查询结果进行排序显得尤为重要，成为关系数据库关键字查询领域的重要组成部分和研究热点之一^[4]。

近年来，一些学者已经对该领域进行初步研究，并提出多种关系数据库关键字查询结果排序方法。例如，Vagelis Hristidis等^[5]提出一种简单且直接的排序方法，根据查询结果所包含的元组数对结果进行排序。该方法虽然简单但排序准确率较低。Liu Fang等^[6]在此基础上将信息检索中成熟的相关性排序机制引入关系数据库中，进一步提高排序准确率。然而，随着排序结果的影响因素不断增多，排序函数日趋复杂。关于影响因子权重的调节缺少一种理论化指导方案，需要在大量实验和经验积累的基础上手动进行设置。因此，排序模型的准确率受到人为因素和实验环境等外界条件的影响。与此同时，学习排序作为一种新兴排序方法在信息检索和机器学习领域得到了广泛应用^[7]。该方法基于训练数据集，使用机器学习算法自动化排序过程。相对于传统排序方法而言，该方法避免了定义排序函数所需要的人力劳动并使排序模型在效率和准确率方面均有显著提高。受到信息检索中学习排序方法的启发，Joel Coffman等^[8]将学习排序方法SVM Rank应用到关系数据库关键字查询结果排序领域。然而，该方法也存在较为突出的问题。首先，SVM Rank是一种典型的虚拟文档对级排序方法^[9]，并未考虑到排序是对一列虚拟文档的预测工作；其次，当面对海量训练数据时，该方法的训练过程需要大量时间开销。因此算法的效率和准确率均存在较大的提升空间^[10]。

在上述研究的基础上，本文将学习排序模型引入关系数据库领域，并作进一步的改进与完善，提出一种基于虚拟文档列表的并行学习排序方法Parallel AdaRdbRank-Hierarchy(PARR-H)用以解决关系数据库关键字查询结果的排序问题。

1 基于虚拟文档列表的学习排序算法

算法ARR-H是一种虚拟文档列表级的学习排序算法，与文献[8]中基于虚拟文档对的算法相比，该算法充分考虑虚拟文档间的序列关系并直接对虚拟文档列表进行优化，因此在排序模型的准确率方面有了较大提高。另外，该算法使用分层的弱排序器构建策略：首先，根据特征的重要性及特征间的相似性，使用贪婪算法构建候选弱排序器集合S_k；其次，根据候选弱排序器的排序性能从集合S_k 中选取得分最高的候选弱排序器作为本次迭代的弱排序器。使用以上分层思想构建弱排序器，能够有效地避免冗余弱排序器的产生。具体实现如算法1所示。

算法1  ARR-H

输入：S′={q_i, vd_i, y_i}_i=1ⁿ，c，E，k，T(T≤k)；

输出：f(x)=f_T(x)；

步骤：

1) 初始化D(i)=1/n，S₀=φ；

2) 找到特征集合X={x_M}_M=1^m；

3) 计算{E(x_M)}_M=1^m，{A(x_kx_f)}_{xk, xf∈X}；

4) 使用{E(x_M)}_M=1^m，{A(x_kx_f)}_{xk, xf∈X}构建无向图G₀；

5) For i=1 to k do

6) 对{E(x_M)}_M=1^m降序排序，x_g←argmax E(x_M)；

7) E(x_j)←E(x_j)-A(x_gx_j)*2c，j≠g

8) S_i=S_i-1∪{x_g}，G_i=G_i-1\{x_g}；

9) EndFor

10)For t=1 to T do

11)计算

E(x_k)={$\sum\limits_{i = 1}^n {} $D_t(i)E(Π(q_i, vd_i, x_k), y_i)} _xk∈Sk；

12) h_t←$\mathop {\arg \max }\limits_{{x_{k \in }}{S_k}} \sum\limits_{i = 1}^n {} $D_t(i)E(Π(q_i, vd_i, x_k), y_i)；

13)选择${\partial _t}$

14)${\partial _t} = \frac{1}{2}\ln \frac{{\sum\nolimits_{i = 1}^n {{D_t}\left( i \right)\left\{ {1 + E\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{h_t}} \right),{y_i}} } \right)} \right\}} }}{{\sum\nolimits_{i = 1}^n {{D_t}\left( i \right)\left\{ {1 - E\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{h_t}} \right),{y_i}} } \right)} \right\}} }}$；

15)构建f_t

16) f_t(x)=$\sum\limits_{k = 1}^n {{\partial _k}} $h_k(x)；

17)更新D_(t+1)

18)${D_{\left( {t + 1} \right)}}\left( i \right) = \frac{{\exp \left\{ { - E\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{f_t}} \right),{y_i}} } \right)} \right\}}}{{\sum\nolimits_{c = 1}^n {\exp \left\{ { - E\left( {\prod {\left( {{q_c},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_c},{f_t}} \right),{y_j}} } \right)} \right\}} }}$；

19)EndFor

20)输出排序模型：f(x)=f_T(x)；

算法1的输入为训练集S′={q_i, vd_i, y_i}_i=1ⁿ，其中q_i表示查询，vd_i表示与查询q_i相关的虚拟文档列表，y_i表示理想的虚拟文档排序列表；k表示候选弱排序器集合中的元素个数；c为弱排序器重要性和相似性间的平衡因子；T表示循环次数，实验中当排序模型的排序性能不再发生变化时，循环结束；E为排序模型的排序性能指标，可以使用NDCG@n或MAP值进行衡量。首先为每个训练实例赋予相同的权重D(i)=1/n，其中n为训练实例总数，初始化候选弱排序器集合S₀=φ。算法2)~9)步计算特征的重要性和特征间的相似性，并使用贪婪算法构建候选弱排序器集合S_k；10)~12)步为弱排序器分层构建的第2阶段，计算候选弱排序器的排序性能，进而确定本次迭代的整体弱排序器。每次循环选择排序性能最好的弱排序器作为本次循环的整体排序器；弱排序器分层构建算法的具体实现细节将在第3节详细介绍；13)~16)步计算本次迭代弱排序器的权重并将其加入当前的排序模型；17)~18)步根据当前排序模型的排序性能得分对当前训练实例的权重分布进行更新。算法经过T次循环输出排序模型f(x)=f_T(x)。算法1)步和2)步的时间复杂度分别为O(n)和O(m)；3)~4)步的时间复杂度为O(m)+O(m(m-1)/2)；5)~9)步的时间复杂度为O(km)；10)~19)步的时间复杂度为O(T(n+k))；由于k＜n所以算法的整体复杂度为O(m²+nT)，其中m为特征总数。

算法ARR-H采用虚拟文档列表级的学习排序思想，同时结合分层弱排序器构建策略，初步解决了关系数据库关键字查询结果的排序问题。然而，随着训练样本规模的不断扩大，该算法的训练效率面临严峻挑战，需要对以上算法作进一步改进，以提高算法的效率。因此，提出并行学习排序算法PARR-H。

2 并行学习排序算法

在算法ARR-H的基础上，加入并行框架如图 1所示。

假设有K个节点，每个节点并行地在各自的局部数据上训练局部弱排序器并计算所需要的信息。中心节点收集所有节点上的信息，并进行统计综合，得到整体弱排序器。中心节点将得到的排序模型返回给每个子节点，子节点使用此排序模型进行训练以得到下次迭代所需要的信息。经过T次循环后，得到最终的排序公式f，当新数据到来时使用公式f对其进行排序得到排序结果。由于训练实例分布在K个节点上同时进行训练，使得训练效率有了显著提高。具体实现见算法2。

算法2   PARR-H

输入：K，S′={q_i, vd_i, y_i}_i=1^nK，E，T；

输出：f(x)=f_T(x)；

步骤：

1) 初始化D₁(i)=1/nK；

2) 调用算法3并行构建候选弱排序器集S_k；

3) For t=1 to T do

4) For j=1 to K (in parallel) do

5) 计算

E_{t, l, j}(x_k)={$\sum\limits_{i = 1}^{{m_j}} {} $D_{t, j}(i)E_{t, l, j}(Π(q_i, vd_i, x_k), y_i)} _xk∈Sk；

6) EndFor

7) 计算E_{t, g}(x_k)=$\left\{ {\frac{1}{K}\sum\limits_{j = 1}^K {{E_{t,l,j}}\left( {{x_M}} \right)} } \right\}$_xk∈Sk；

8) h_t←$\mathop {\arg \max }\limits_{{x_{k \in }}{S_k}} \sum\limits_{i = 1}^{nK} {} $D_t(i)E_{t, g}(Π(q_i, vd_i, x_k), y_i)；

9) 选择${\partial _t}$

10) ${\partial _t} = \frac{1}{2} \cdot $

$\ln \frac{{\sum\nolimits_{i = 1}^{nK} {{D_t}\left( i \right)\left\{ {1 + {E_{t,g}}\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{h_t}} \right),{y_i}} } \right)} \right\}} }}{{\sum\nolimits_{i = 1}^{nK} {{D_t}\left( i \right)\left\{ {1 - {E_{t,g}}\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{h_t}} \right),{y_i}} } \right)} \right\}} }}$；

11)创建f_t

12) f_t(x)=$\sum\limits_{k = 1}^t {{\partial _k}} $h_k(x)；

13)For j=1 to K (in parallel) do

14)更新D_{(t+1), j}

15) D_{(t+1), j}(i)=$\frac{{\exp \left\{ { - {E_{t,l,j}}\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{f_t}} \right),{y_i}} } \right)} \right\}}}{{\sum\nolimits_{c = 1}^{{m_j}} {\exp \left\{ { - {E_{t,l,j}}\left( {\prod {\left( {{q_c},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_c},{f_t}} \right),{y_j}} } \right)} \right\}} }}$；

16)EndFor

17)更新D_(t+1)

18)

D_(t+1)(i)=$\frac{{\exp \left\{ { - {E_{t,g}}\left( {\prod {\left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{f_t}} \right),{y_i}} } \right)} \right\}}}{{\sum\nolimits_{c = 1}^{nK} {\exp \left\{ { - {E_{t,g}}\left( {\prod {\left( {{q_c},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_c},{f_t}} \right),{y_j}} } \right)} \right\}} }}$；

19)EndFor

20)输出排序模型：f(x)=f_T(x)；

在算法2中，数据被随机分布在K个节点上，这样训练任务可并发执行，从而减少训练的时间开销；2)步调用算法3并行地构建候选弱排序器集合S_k，包含k个候选弱排序器，其详细的实现过程将在第3节算法3中具体介绍；3)~6)步在子节点上并行计算候选弱排序器的局部重要性，并将此信息发送给中心节点；7)~8)步中心节点整合从子节点获得的所有信息，构建此次迭代的整体弱排序器；9)~12)步根据整体弱排序器的排序性能E计算弱排序器的权重，并将其加入现有的排序模型；13)~16)步，中心节点将此次迭代后形成的排序模型返回到每个子节点，子节点根据此排序模型对训练实例的局部权重分布进行更新；17)~18)步对训练实例的全局权重分布进行更新；经过T次循环，最终得到排序模型f(x)=f_T(x)。算法1)步的时间复杂度为O(n)；2)步的时间复杂度为O(n+m²)；3)~19)步的时间复杂度为O((m+n)T)；因此算法2的时间复杂度为O(nT+m²)，其中n为子节点上的训练实例数，T为循环次数，m为特征总数。

3 弱排序器分层构建策略

通过对算法PARR-H的分析可知，经过T次循环，该算法最终输出的排序模型f(x)=f_T(x)是多个弱排序器及其权重的线性组合。而在每次循环中，弱排序器的选择直接影响了训练效率和排序模型的有效性。因此，本节将会对弱排序器的构建进行深入研究，并提出一种基于贪婪算法和整体排序性能的分层构建策略。该策略既能保证较高的排序性能，同时可有效避免冗余排序器的产生。分为两个阶段：1)构建候选弱排序集合S_k；2)根据弱排序器的排序性能，从集合S_k中进一步选择每次循环中的弱排序器。在阶段1中，子节点并行地计算特征的局部重要性和局部相似性。并将其传送给中心节点，中心节点整合以上信息得到每个特征的全局重要性及特征间的全局相似性。以特征为顶点，全局重要性为节点权重，全局相似性为边权重构建全局特征关联图G₀。使用贪婪算法在图G₀上进行搜索得到候选弱排序器集合S_k。特征的全局重要性和全局相似性计算过程如下：

1) 特征的全局重要性。

将特征x_i作为一个排序模型分别在K个机器节点上对训练实例进行排序。得到K个局部的排序模型准确率评分E_{l, j}(x_i)=$\sum\limits_{i = 1}^{{m_j}} {} $D_j(i)E_{l, j}(Π(q_i, vd_i, x_i), y_i)，中心节点对上述信息进行求和取平均得到特征x_i的全局重要性E_g(x_i)=$\frac{1}{K}\sum\limits_{j = 1}^K {} $E_{l, j}(x_i)。

2) 特征的全局相似性。

将每个特征作为一个排序模型，并由此得到不同的排序结果。使用排序结果间的相似性作为特征间的相似性，本文选取皮尔森相关系数对排序结果相似性进行度量。相似性的计算：

$\begin{array}{l} \quad \quad \quad \quad \quad \quad {A_{l,j}}\left( {{x_k}{x_f}} \right) = \\ {\left\{ {{\mathop{\rm cov}} \left( {\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_{{x_k}}},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_{{x_f}}}} \right)/\sqrt {{\mathop{\rm var}} \left( {\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_{{x_k}}}} \right){\mathop{\rm var}} \left( {\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_{{x_f}}}} \right)} } \right\}_{{x_k},{x_f} \in X}}\\ {A_{\rm{g}}}\left( {{x_k}{x_f}} \right) = {\left\{ {\frac{1}{K}\sum\limits_{j = 1}^K {{A_{l,j}}\left( {{x_k}{x_f}} \right)} } \right\}_{{x_k},{x_f} \in X}} \end{array}$

(1)

式中：x_k和x_f为任意两个不同的特征，K为节点数，A_{l, j}(x_kx_f)表示在节点j上特征x_k和x_f间的局部相似性，A_g(x_kx_f)表示在K个节点上特征x_k和x_f间的全局相似性。cov(vd_xk, vd_xf)为根据特征x_k和x_f所得排序结果的协方差，var(vd_xk)为根据特征x_k所得排序结果的方差。

算法3   PCAWR(parallel construction algorithm of candidate weak rankers S_k)

输入：K，D_j，k，c；

输出：候选弱排序器集S_k；

步骤：

1) 初始化D_j=1/n(每个节点包含n个实例)，S₀=φ；

2) For j=1 to K (in parallel) do

3) 使用节点j上的数据和分布D_j找到特征集合X={x_M}_M=1^m；

4) 得到

$\begin{array}{l} \quad \quad \quad \quad \quad \quad \quad {E_{l,j}}\left( {{x_M}} \right) = \\ \left\{ {\sum\limits_{i = 1}^n {{D_j}\left( i \right){E_{l,j}}\left( {\prod \left( {{q_i},\mathit{\boldsymbol{v}}{\mathit{\boldsymbol{d}}_i},{x_M}} \right),{y_i}} \right)} } \right\}_{M = 1}^m\left( {{x_M} \in X} \right),\\ \quad \quad \quad \quad {A_{l,j}}\left( {{x_k}{x_f}} \right) = \left\{ {{\mathop{\rm cov}} \left( {{x_{*k}},{x_{*f}}} \right)/} \right.\\ {\left. {\quad \quad \quad \quad \sqrt {{\mathop{\rm var}} \left( {{x_{*k}}} \right){\mathop{\rm var}} \left( {{x_{*f}}} \right)} } \right\}_{{x_k},{x_f} \in X}}; \end{array}$

5) EndFor

6) 计算E_g(x_M)={$\frac{1}{K}\sum\limits_{j = 1}^K {} $E_{l, j}(x_M)} _M=1^m，A_g(x_kx_f)={$\frac{1}{K}\sum\limits_{j = 1}^K {} $A_{l, j}(x_kx_f)} _{xk, xf∈X}；

7) 使用E_g(x_M)={$\frac{1}{K}\sum\limits_{j = 1}^K {} $E_{l, j}(x_M)} _M=1^m和A_g(x_kx_f)={$\frac{1}{K}\sum\limits_{j = 1}^K {} $A_{l, j}(x_kx_f)} _{xk, xf∈X}构建无向图G₀；

8) For i=1 to k do

9) 对E_g(x_M)降序排序，x_g←argmax E_g(x_M)；

10) E_g(x_j)←E_g(x_j)-A_g(x_gx_j)*2c，j≠g

11)S_i=S_i-1∪{x_g}，G_i=G_i-1\{x_g}；

12)EndFor

13)输出S_k

算法3描述了弱排序器构建的第一阶段：并行构建候选弱排序器集合S_k。算法1)步初始化，分别为每个节点上的训练实例赋予相同的权重分布，初始化候选弱排序器集合S₀=φ；2)~5)步在每个子节点上并行地计算特征的局部重要性和特征间的局部相似性，并将结果返回给中心节点；6)~7)步中心节点计算特征的全局重要性和全局相似性，进而构建全局特征关联图G₀；8)~12)步选择全局重要性最大的特征，将其加入候选弱排序器集合S，并对特征全局关联图进行更新。k次循环后得到包含k个特征的候选弱排序集合S_k。算法1)步的时间复杂度为O(n)；第2~5步的时间复杂度为O(m)+O(m(m-1)/2)；6)~7)步的时间复杂度为O(m)+O(m(m-1)/2)；8)~12)步的时间复杂度为O(k·m)。综上所述算法3的时间复杂度O(n+m²)，其中n为子节点上的训练实例数，m为特征总数。

4 实验结果与分析

在数据集IMDB^[11]和Wikipedia^[12]上进行实验，通过与基准方法SVM Rank进行比较分析，验证算法ARR-H和PARR-H的有效性和效率。选择SVM Rank算法作为基准方法，因为该算法是关系数据库领域中最为经典的学习排序方法，并且Joel Coffman等^[8]已经通过多组对比实验验证了该学习排序方法在排序准确率方面优于传统的信息检索式排序方法。

4.1 实验设置

分别抽取原始数据集IMDB和Wikipedia的子集作为本次实验的数据集。表 1记录了关于该数据集的统计结果。另外，实验包括1个主节点和4个子节点。其中每个节点的配置为Intel(R)Core(TM)i5-4570 CPU 3.20 GHz，内存容量4G，硬盘容量1 TB，操作系统WIN 10(64 bit)。在进行实验之前，需要对原始数据集进行预处理。分别在数据集IMDB和Wikipedia上随机生成250个查询，基于三个系统BANKS、DISCOVER、SPARK得到与查询相关联的查询结果，这里统称为虚拟文档。针对每个查询，从3个系统返回的结果中选取top-100虚拟文档放入数据池，并由此产生实验所需的训练实例。使用五折交叉验证实验减小评分函数过拟合的风险。将数据池中的数据随机分为5个子集合，每个子集合包含50个查询及其对应的虚拟文档。其中4个子集合用于训练，剩余1个子集合用于测试。注意，在算法PARR-H执行过程中，训练集的4个子集合被分布在4个子节点上，主节点使用测试集对训练结果进行测试。表 2和表 3分别显示实验中的查询划分以及五折交叉验证中的数据集划分，其中QID为查询ID号。

4.2 有效性

使用MAP和NDCG两种度量指标作为排序模型的效果评估标准。给定查询q，第i位上的NDCG值计算如下

${\rm{NDCG}}@i = {n_i}\sum\limits_{j = 1}^i {\left( {{2^{r\left( j \right)}} - 1} \right)} /\log \left( {1 + j} \right)$

式中：r(j)为第j位虚拟文档的相关度等级，n_i为归一化因子。

查询q的平均准确率计算如下：

${\rm{AP = }}\sum\limits_{j = 1}^N {\left( {P\left( j \right) \times {\rm{pos}}\left( j \right)/{N_q}} \right.} $

式中：P(j)为排在前j位虚拟文档的查准率；pos(j)为二值函数，当第j位虚拟文档为相关文档时pos(j)=1，反之pos(j)=0；N为通过查询q返回的虚拟文档数; N_q为查询q相关的虚拟文档数。多个查询的AP值取平均即可得到MAP值。

4.2.1 数据集IMDB上的实验

本节使用数据集IMDB验证算法ARR-H和PARR-H的性能。这里，将算法SVM Rank记为‘SVM-R’。图 2中x轴为虚拟文档在文档序列中所在的位置，y轴为三种排序算法在各个位置上所对应的NDCG@n值。由图 2可知，算法ARR-H和PARR-H在NDCG@n上均优于算法SVM-R。具体来讲，当n=1时相对于SVM-R，ARR-H和PARR-H分别提高13.3%和8.2%。而关于NDCG@5，ARR-H和PARR-H相对于SVM-R分别提高9.1%和7.0%。另外，在该实验中算法SVM-R的MAP值为0.309，而ARR-H和PARR-H的MAP值分别为0.335、0.317，相对于SVM-R分别提高约8.4%和2.6%。产生上述实验结果的原因是：本文提出的算法ARR-H和PARR-H为虚拟文档列级的学习排序方法，与文档对级的排序方法SVM-R相比，以上两种方法不再将排序问题归纳为二元分类问题，而是直接优化排序评价指标，从而提高排序模型的精度。另外，算法ARR-H和PARR-H使用分层式弱排序器构建策略IS-BGEM(importance & similarity-based on global evealvation measure)，避免了冗余弱排序器的产生，进一步提高了排序模型的精度。而ARR-H的实验结果优于PARR-H，其主要原因是：将训练数据分散在不同节点上进行并行化处理，对排序模型精度方面造成一定程度的影响，一方面节点间的数据通信降低了模型的可靠性。另一方面，算法中特征的全局重要性和全局相似性以及训练样本的全局分布，均和实际单节点上的算法运行有所差异。本文方法在NDCG@1上的提高幅度最为显著，说明该方法适用于Web数据库，此应用环境强调位置靠前的结果。

4.2.2 数据集Wikipedia上的实验

在数据集Wikipedia上同样进行五折交叉验证实验。由图 3可以看出在数据集Wikipedia上的实验结果与数据集IMDB上的结果相类似。ARR-H的NDCG@n值优于其他两种排序算法。例如，与SVM-R相比，ARR-H的NDCG@5值提高6.6%，PARR-H的NDCG@5值提高5.2%。另外，SVM-R、ARR-H、PARR-H所对应的MAP值分别为0.443、0.473、0.452。其中，ARR-H的MAP值最大，相比于SVM-R提高6.8%。PARR-H的MAP值相比于SVM-R提高2.0%，而与ARR-H相比，有所降低。

4.3 训练效率

图 4给出随着训练实例规模的变化，3种排序算法训练时间的变化情况。由图 4可知，相对于另外两种排序算法，PARR-H的训练时间明显减少。当训练实例个数为10 000时，PARR-H的训练时间为4.9 min，而SVM-R和ARR-H的训练时间分别为25.5 min和16.1 min。通过对实验结果的分析可以发现，随着训练实例规模的不断增大，PARR-H算法效率提高越明显。当训练实例的个数达到20 000时，PARR-H的训练时间为51.2 min，而SVM-R的训练时间达到179.8 min。产生上述实验结果主要是由于PARR-H和ARR-H均为列表级的学习排序方法，其训练对象为查询相关的虚拟文档列表，更接近于实际意义上的排序操作。而SVM-R为文档对级的学习排序方法，其训练对象为查询相关的虚拟文档对，排序过程中着重考虑虚拟文档对间的偏序关系，而未考虑虚拟文档在整个文档列表中的序列关系。因此，PARR-H和ARR-H在排序性能上有较大提高。而PARR-H为学习排序加入并行框架，将训练样本分布在不同机器上并行化训练过程，因此学习排序模型的训练效率得到进一步提高。

5 结论

1) 提出一种列表级的学习排序算法ARR-H。该算法充分考虑虚拟文档间的序列关系，同时结合弱排序器分层构建思想，提高排序模型的有效性。

2) 构建一种并行学习排序框架PARR-H，并行化训练过程，有效解决了面对大规模训练实例时ARR-H算法训练效率低的问题。

3) 通过在数据集IMDB和Wikipedia上进行实验，验证本文学习排序算法ARR-H和PARR-H在有效性和效率方面均有显著提高，尤其当训练实例规模较大时，PARR-H在训练效率上的优势更为突出。

在未来的研究中，将在更大规模的数据集上进行实验，验证排序算法的可扩展性。