1.一种基于Monroe规则的元搜索排序Top‑k聚合方法,其特征在于:Step1:采用Borda规则将各独立搜索引擎对检索元素的排序关系构造为独立搜索引擎‑检索元素匹配度矩阵;
Step2:借鉴Monroe比例代表思想将元搜索排序Top‑k聚合问题建模为寻找最大化所有独立搜索引擎总体匹配度的元素集合的优化问题;
Step3:采用贪心算法对该优化问题进行求解,将所得检索元素集合作为元搜索排序Top‑k聚合结果;
Step2具体为:
Step2.1:将独立搜索引擎按比例动态地分为k组,每组最多包含 个搜索引擎,每个搜索引擎分别被分配给一个检索元素作为该搜索引擎的代表并计算搜索引擎匹配度,且每个元素最多只能代表 个搜索引擎,或者不能作为代表,寻找在分配过程中最大化独立搜索引擎总体匹配度的k个元素作为元搜索排序结果;
Step2.2:独立搜索引擎总体匹配度计算为:
其中,Φ表示局部分配任务,Φ(i)表示能代表独立搜索引擎si的检索元素,posi(Φ(i))表示能代表独立搜索引擎si的元素在独立搜索引擎si的排序中的位置,目标为最大化独立搜索引擎总体匹配度maxl(Φ)。
2.根据权利要求1所述的基于Monroe规则的元搜索排序Top‑k聚合方法,其特征在于Step1具体为:Step1.1:设独立搜索引擎集合为S={si|i=1,2,...,n},检索元素集合为E={ej|j=
1,2,...,m},其中,n表示独立搜素引擎的数量,m表示检索元素数量;
Step1.2、独立搜素引擎si根据其特定排序算法对检索元素的排序定义为所有独立搜素引擎对应的检索结果的排序关系集合定义为R={βi|i=1,2,...,n};
其中,er(1)>ier(2)表示在独立搜索引擎si对检索元素的排序中,元素er(1)优于元素er(2),βi表示独立搜索引擎si对t个元素的某种潜在排列,即从m个元素中取出t个元素进行的无重复线性排序,r(t)表示排序的序号,参数t控制独立搜索引擎对元素排序的完整程度,且t≤m;
当t=m时,βi表示独立搜索引擎si给出对所有元素的完整偏好排序;
当t<m时,βi表示独立搜索引擎si只对最偏爱的Top‑t个检索元素进行部分截断排序;
Step1.3:记独立搜索引擎si对检索元素ej的匹配度分数为Matij,即独立搜索引擎si对选择元素ej作为元搜索排序Top‑k聚合结果的匹配程度,将独立搜索引擎对元素的匹配度分数表示为矩阵Mat=[Matij]n×m;
Step1.4:匹配度分数Matij通过Borda规则计算,用参数t控制独立搜索引擎对检索元素排序的完整程度,并将不包含于独立搜索引擎的截断排序Top‑t中的元素均记为e',当t=m时表示独立搜索引擎si对元素有完整的排序时,独立搜索引擎si对元素的匹配度计算为:Matij=m‑posi(ej) (1)
当t<m时表示独立搜索引擎si仅对其偏爱的前t个检索元素进行部分排序,若元素ej包含在独立搜索引擎si的Top‑t排序中,则获取该元素在对应排序中的位置并计算匹配度;
若元素ej不在独立搜索引擎si的Top‑t排序中,则将该元素记为e',且默认posi(e')=m,独立搜索引擎si对元素ej的匹配度计算为:其中,posi(ej)表示在检索元素ej在独立搜索引擎si的排序中的位置。
3.根据权利要求2所述的基于Monroe规则的元搜索排序Top‑k聚合方法,其特征在于Step3具体为:Step3.1:根据贪心算法建立一个迭代解决方案,在每次迭代过程中选择某个未被分配过的元素ej,并将最佳匹配元素ej的 个独立搜索引擎分配给元素ej,即把这 个独立搜索引擎分配给元素ej得到的匹配度最大;
Step3.2:在每次迭代过程中,遍历未被分配过的元素列表,根据规则对独立搜索引擎进行排序并存在数组engines中;
所述规则为:若元素ej在独立搜索引擎si排序中的位置小于或等于其在独立搜索引擎si’中的位置,即posi(ej)≤posi'(ej),则认为独立搜索引擎si优于si’;
Step3.3:截取独立搜索引擎数组engines中前 个搜索引擎;
Step3.4:根据公式(1)分别计算集合E中每个元素分配给数组engines中的n/k个独立搜索引擎所得到的匹配度分数;
Step3.5:取使得这n/k个独立搜索引擎匹配度最大的元素,并将该元素和其对应的独立搜索引擎匹配度分数存放于字典bests中;
Step3.6:将字典bests中的元素加入数组W中,
Step3.7:重复以上步骤,根据检索用户输入的k取值建立k次迭代,并将数组W中的k个元素作为Top‑k元搜索排序的聚合结果。