学习元素排序的算法(理想情况下是Java)

Question

我有许多有序列表,大多数都包含相同的元素.我想从列表(样本)中找到最可能的元素顺序.

例:

l1={ a, b, f, h, z }
l2={ c, e, h, x, z }
l3={ a, e, y, z }
l4={ b, e, f, z }

结果应该是:

R={a, b, c, e, f, h, x, y, z}; or 
R={ a,b,c,e,f,h,y,x,z }

元素没有关于其自然顺序的信息.应该从列表中学习订单,在某些情况下,列表中的订单可能与其他列表相矛盾,因此我需要最可能的订单.我有大约175,000个列表,大约180万个元素(总数,260k唯一),每个列表的元素数量各不相同.

我已经尝试构建有向图,其中边具有以这种顺序连接顶点的列表数,然后遍历所有路径以找到最可能的序列.这种方法适用于小问题,但对于这么大的问题来说太复杂了.

欢迎提出任何指示,我们将不胜感激.

谢谢.

胡安

Answer 1

我认为你的问题与开发多人游戏玩家评级系统的问题非常相似。不幸的是，我没有看到一个简单的答案，特别是考虑到您的数据量。我倾向于将 N 个元素的每个列表视为 N-1 个两人游戏，每个游戏记录一个玩家和列表中位于其上方的玩家之间的比赛。如果您负担得起，您可以将每个列表视为 N(N-1)/2 两人游戏，记录列表中的所有比较。无论哪种情况，您都可以为两人游戏应用评级系统，例如https://en.wikipedia.org/wiki/Elo_ rating_system。

另一种方法是为任何排序的拟合优度写下惩罚函数，然后尝试最小化惩罚。有许多函数可以相互比较两个列表，例如https://en.wikipedia.org/wiki/Spearman 's_rank_correlation_coefficient 和https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient。肯德尔的排名相关性仅基于成对比较的数量，如果您使用另一个列表作为预测变量，则在一个列表中您可能会出错，因此它可能具有一些不错的属性。您可以决定对整个列表的惩罚是当您依次将整个列表与每个输入列表进行比较时计算的所有惩罚的总和。

最小化这种惩罚的一种方法是从随机排序开始，然后重复地从排序中删除一个项目，并将其放回最小化惩罚函数的位置，直到这种改变没有改善问题为止。不幸的是，考虑到您的数据量，我认为您负担不起。

如果您准备将数据转化为实力未知的玩家之间的两人游戏列表，那么您可以采取多种方法。如果用单个向量表示所有玩家的优势，例如 (strengthA,strengthB,strengthC,...)，那么 A 击败 B 的概率可能取决于该向量与向量 (1, - 1, 0, ....）。这表明您可以尝试使用逻辑回归、基于感知器的模型或支持向量机找到合适的方法。