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

前端之家收集整理的这篇文章主要介绍了学习元素排序的算法(理想情况下是Java)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

例:

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

结果应该是:

R={a,c,z}; or 
R={ a,z }

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

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

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

谢谢.

胡安

最佳答案
我认为你的问题非常类似于开发多人游戏的玩家评级系统.不幸的是,我没有看到一个简单的答案,特别是考虑到你的数据量.我倾向于将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.Kendall的等级相关性仅仅是基于成对比较的数量,如果您使用另一个作为预测因子,则会在一个列表中出错,所以它可能有一些不错的属性.您可以决定对整体列表的惩罚是您将整个列表与每个输入列表依次进行比较时计算的所有惩罚的总和.

最小化这种惩罚的一种方法是从随机排序开始,然后重复从排序中移除一个项目并将其放回到最小化惩罚函数的任何地方,直到没有这样的改变改善了事项.不幸的是,鉴于您的数据量,我认为您无法承受这一点.

如果您准备将数据转换为未知优势的玩家之间的双人游戏列表,那么您可以采取多种方法.如果你通过单个向量表示所有玩家的优势,例如(strengthA,strengthB,strengthC,…)那么A击败B的概率可能取决于该向量与向量的点积(1,– 1,……).这表明你可以尝试通过逻辑回归,基于感知器的模型或支持向量机来找到一个好的拟合.

原文链接:https://www.f2er.com/java/437409.html

猜你在找的Java相关文章