0
  • 有 N 个独特的项目。
  • 有K个排序列表，每个列表由项目的一小部分组成，每个列表不包含多次相同的项目。
  • 输入是未排序的项目列表。
  • 该算法应根据 K 个排序列表对列表进行排序。

这是一个例子：

  • 有 100 项：item1, item2, ..., item100
  • 有一些可用的排名列表：List1：Item1>Item2>Item12，List2：Item12>item93>Item7，List3：Iterm1>Item3>Iterm97，List4：Iterm1>Iterm7>Item2

输入为：Iterm1、Item2、Iterm7 和 Item98。该算法应根据这些列表对输入进行排序。

在机器学习方面，我正在寻找一种算法，该算法可以基于许多部分排序的项目列表的训练集预测项目列表（AKA 活动列表）的“正确”顺序，每个部分排序的项目列表可能包含活动列表不包含的其他项目。

4

3 回答 3

4

构造一个以输入元素为节点的有向无环图 (DAG)，当且仅当 Itemi 在某个列表中紧接在 Itemj 之前出现时，才从 Itemi 和 Itemj 定义一条边。然后，您可以通过对 DAG进行拓扑排序来获得所需的顺序。

于 2012-09-12T15:56:21.453 回答
1

我将从输入（A> B 之间的链接数是权重）组成一个加权图，将其放入 N*N 矩阵，并在矩阵上执行幂迭代（GIYF）。

于 2012-09-14T09:49:19.827 回答
1

我认为您的意思是排序列表定义了部分排序，是吗？即，如果 Item1 在其中一个列表中出现在 Item2 之前，则应将其视为“更大”。

如果这是正确的，那么要走的路是首先以更方便的形式表示它，例如矩阵M，这样M[1][2]==1如果 Item1 在列表之一中位于 Item2 之前。然后我们有一个简单的比较器函数：

if M[X][Y] == 1:
    return 1 # X > Y
elif M[Y][X] == 1:
    return -1 # Y > X
else
    return 0 # the elements are not comparable

我们现在可以根据这个比较器对输出进行排序。

在排序之前，您可能希望在此矩阵上运行传递闭包（Warshall 算法），例如，如果有列表 Item1>Item3 和 Item3>Item2，但没有列表 Item2 将与 Item1 一起出现。传递闭包允许人们从两个列表中推断出 Item1 应该在 Item2 之前。

于 2012-09-12T15:57:02.143 回答