1 vs 1 投票:如何计算评分(Flickchart.com)

16

与其使用1到10的分数来评估物品,我更喜欢使用1对1“比赛”的方式。两个项目并排显示,您选择更喜欢的那一个。根据这些“比赛”结果,算法应计算每个项目的评级。

您可以在Flickchart.com上看到这种方法,该网站使用此方法评估电影。

它看起来像这样:

Screenshot

如您所见,如果一个项目赢得了“比赛”,它会向上移动。排名始终基于“比赛”结果而不断变化。但是这不能仅基于胜利引用(此处为54%),因为与“泰坦尼克号”相比,对抗“第25个小时”之类的电影更难取胜。

有几件事情对我来说还不太清楚: - 评级是如何计算的?如何决定哪部电影在排名中位居第一?您必须考虑项目获胜的频率以及被打败的项目的质量。 - 如何选择哪些项目进行“比赛”?

当然,您不能告诉我Flickchart究竟是如何做到这一切的。但也许您可以告诉我该如何完成。先行致谢!


2
你的问题的前半部分可能与后半部分不同,因为如何做可能与Flickchart的做法不同。最佳算法(或它们的组合)取决于您的目标的一些附加细节:结果是否仅表示全局偏好?它们是否表示您的偏好?两者都是吗?您是否打算根据排名进行推荐?如果是这样,您是否还要评估其他用户与您的相似程度?如果Bob的兴趣恰好与我的相反,那么将他的偏好纳入考虑可能就没有意义,等等。 - charstar
谢谢,非常好的问题。Flickchart的做法可能不是最好的,但这绝对是一种方法。所以对于我的目的来说,这样做是可以的。应该有一个全球排名和一个只属于我的排名。所有投票都会影响全球排名,但我的排名只受我的投票影响。推荐并不是主要目标,但有它们会很好。 - caw
遗憾的是,投了-1票的选民:这是一个非常有趣的问题,请编辑一下,这样我就可以改成赞同票了... - Charles Stewart
9个回答

9
这可能不是flickchart正在做的事情,但您可以使用类似于棋类(和其他体育运动)中使用的ELO算法的变体,因为这些基本上是他们赢得/输掉的战斗/游戏。
基本上,所有电影都从0胜利/失败开始,每次获胜时都会获得一定数量的积分。您通常平均约为20(但任何数字都可以),并且与自己评分相同的电影比赛将确切地给出那20分。赢得一部烂片可能会获得约10分,而赢得一部更好的电影可能会给您30分。反过来,输给一部好电影只会失去10分,但如果输给一部烂片,则会失去30分。
算法的具体细节在维基百科链接中。

1
谢谢!但这只能是算法的一小部分。想象一下,你已经评价了20部电影 - 每部电影都评价了几次。在第5名是“泰坦尼克号”。然后你可以选择“泰坦尼克号”和“怪物史莱克”。你还没有评价过“怪物史莱克”。但你更喜欢这里的“怪物史莱克”。根据你的评分系统,“怪物史莱克”只能进入排名第11左右。但它必须在“泰坦尼克号”之前,对吧? - caw
1
我假设你想要所有人的评分,而不仅仅是你自己的。对于你的“个人”最佳电影列表,你需要更多的东西,否则你将不得不为每部电影打更多次分才能准确 :) - Christian P.
1
当我看到这个问题时,你提供的答案和我想到的一样。ELO对于类似于国际象棋的1对1战斗非常有用。 - Andrew
好的。所以ELO似乎是一个不错的解决方案,也许不是最好的,但它肯定可以与ELO一起使用。:) 但是:物品A赢得了很多战斗,并根据ELO排名第一。物品B只赢了几次,但输了很多次,但它击败了物品A。根据ELO,物品B应该在底部。但是根据另一个模型,物品B应该排在第一位!? - caw
2
胜利次数并不决定你的排名,而是你战胜了谁。想象一下,在网球世界排名中排名第100。如果你连续三次击败第一名,你不仅会上升几个名次,而是会飞速上升。如果你连续三次击败第99名,你最多只能上升1-2个名次。 - Christian P.
显示剩余2条评论

5
评分是如何计算的?您如何决定哪部电影在排名中位居第一?您必须考虑某个项目获胜的频率以及被击败的项目有多好。

您想要的是加权评分,也称为贝叶斯估计。

我认为IMDB的Top 250电影是制作排名网站的更好起点。有些电影拥有300,000+的投票,而其他电影则不到50,000。IMDB使用贝叶斯估计来比较电影,而不会给热门电影带来不公平的权重。算法在页面底部给出:
“加权评分(WR)=(v÷(v+m))× R +(m÷(v+m))× C”,其中: R =电影平均值(平均数)=(评分) v =电影的投票数=(投票) m =必须列入前250名的最低投票数(目前为3000) C =整个报告的平均投票(目前为6.9) 仅考虑常规选民的投票。对于前250名,只考虑常规选民的投票。”
“我不知道IMDB是如何选择3000作为他们的最低选票的。他们本可以选择1000或10000,列表可能会更多或更少相同。也许他们正在使用“上映6周后的平均选票数”,或者他们正在使用试错法。”
“在任何情况下,这并不重要。上面的公式几乎是规范化排名网站上的投票的标准,我几乎可以肯定Flickrchart在后台使用类似的东西。”
该公式的运作效果很好,因为它会将评分“拉”向平均值,所以高于平均值的评分会稍微降低,低于平均值的评分会稍微增加。然而,这种影响的强度与电影获得的投票数成反比。因此,投票数较少的电影会比拥有大量投票的电影更积极地被拉向平均值。以下是两个数据点来展示这一特性:
Rank  Movie            Votes            Avg Rating        Weighted Rating
----  -----            -----            ----------        ---------------
219   La Strada        15,000+          8.2               8.0
221   Pirates of the   210,000+         8.0               8.0
      Caribbean 2

两部电影的评分都有所下降,但对于《拉斯特拉达》,由于它的投票数较少,因此不如《加勒比海盗》的评分代表性那么强,因此其下降幅度更加戏剧化。
针对您的具体情况,您有两个项目在“争斗”中。您应该按照以下方式设计您的表格:
Items
-----
ItemID (pk)
FightsWon (int)
FightsEngaged (int)

平均评分为FightsWon / FightsEngaged。加权评分使用上述公式计算。
当用户选择战斗中的获胜者时,将获胜项的FightsWon字段增加1,将两个项的FightsEngaged字段都增加1。
希望这可以帮到你! - 朱丽叶

1
请记住,IMDB用户自行选择他们投票的电影,因此在对La Strada和The Dark Knight进行排名时,并不存在同等可能性。一个“斗争”网站可能会使两个项目之间的斗争同等可能,而不像IMDB电影的自我选择投票 - 但是,您可能会看到新添加的项目对平均值产生显着的拉动,仅仅因为它们没有太多时间参与战斗。高评分的新项目 应该随着时间的推移自我纠正,通常在获得前10名最低投票的5倍后。 - Juliet
谢谢你的额外解释,朱丽叶。你在IMBB上的算法非常适用于普通投票,我可以自己选择要投票的项目。但对于我的目的——1对1的比赛,我认为它不是最好的选择。 - caw
@cda:假设我们有A、B、C和D:B在70%的时间内战胜A,D在100%的时间内战胜C,D在100%的时间内战胜B,而C在70%的时间内战胜A。你能正确地得出D > B > C > A的结论吗?不行,除非知道打斗次数的信息。如果A、B和C已经参加了成千上万次的打斗,而D只与D和B进行了一次打斗(因此记录完美),那么你不能得出关于D相对实力的任何结论。当图形表示法添加了10个1000个节点后,它是否真的会与贝叶斯估计器有所不同呢? - Juliet
1
@Juliet 在这种情况下,使用贝叶斯方法只能确定全局排名。OP正在谈论用户的明确偏好链(而不是健康/强度/表现度量)。考虑一下:用户对A到Y进行投票,除了他比A更喜欢的Z之外,其他都按字母顺序喜欢。这只是一个参与和一个胜利,但用户期望Z不会排在首位(“在我投票的所有电影中,这部甚至比当前排名第一的还要好”)。 - charstar
谢谢Charstar,这正是这个答案所缺少的。但对于其他目的,这个答案非常好。这段代码有很多用途。非常感谢你,Juliet! - caw
显示剩余2条评论

2

就 flickchart 而言,我玩了一下,感觉它的评分系统相当简单。我的猜测是,它的伪代码看起来大概是这样的:

if rank(loser) == null and rank(winner) == null
    insert loser at position estimated from global rank
    insert winner at position estimated from global rank
else if rank(winner) == null or rank(winner) < rank(loser)
    then advance winner to loser's position and demote loser and all following by 1

我为什么这样认为呢?首先,我完全相信他们的贝叶斯先验不是基于对我以前选择的仔细挖掘。他们似乎无法猜测,因为我喜欢《星球大战6:绝地归来》,所以我会喜欢《星球大战5:帝国反击战》。事实上,他们无法想出,因为我看过《小鬼当家2》,所以我可能已经看过《小鬼当家1》。在数百次评分之后,这个选择从未出现。

其次,如果你查看上面的代码,你可能会发现一个小错误,在网站上肯定会注意到。你可能会注意到,有时你会做出选择,而获胜者会向前滑动一位。这似乎只会在输家之前没有被添加时发生。我猜正在发生的是,失败者被添加得比赢家高。

除此之外,你会注意到排名根本不会改变,除非一个低排名电影直接打败了一个高排名电影我不认为有任何真实的分数被保留:该网站似乎完全没有记忆,除了每部电影的序数排名和你最近的评分。


你的伪代码中好像忘记了一些闭合括号,是吗?而且在两个语句中都有rank(winner)==null,这真的没有意义。你认为这很容易吗? - caw
1
我没有使用任何开括号...那为什么会有闭括号呢?我用伪代码为什么要用括号呢?有一些括号的问题,我会修复它们。我不声称这是一个好的算法,我声称这就是flick-chart的工作方式。你可以尝试一下,并提供一个反例。如果它更复杂一些,难道你不认为当你比较A和B时,C有可能发生变化(不仅仅是向下移动一个位置)吗? - David Berger
抱歉,我想说的是括号。这就是我的意思。 ;) 我会测试你的代码。非常感谢! - caw
你的算法似乎是正确的。但我会用“将失败者降低1个位置”替换为“将后面所有项目降低1个位置”。另外,如果获胜者在你自己的排名中,但失败者还没有进入排名,则获胜者将向前进一位。 - caw
另一个有趣的问题是:如何计算全球排名?这非常重要,因为您的算法使用它。 - caw
@marco92w "如果赢家在你的排名中,但输家还没有,那么赢家将向前进一位。" 令人惊讶的是,不是这样!我见过相反的情况发生! 输家只是被插入(我认为是基于全局,但这只是一个猜测),经常比赢家更高的位置。 这是我第一次发现算法并不是那么复杂的原因。 - David Berger

2
我一直在思考如何通过逐对比较来排列物品的问题,想花点时间描述一下我目前想出的想法。
目前我只是按照<获胜次数>/<总次数>进行排序,优先选择最高的。如果你是唯一的投票者或有很多人投票,则此方法可行。否则,它很快就会变得不准确。
一个问题是如何选择哪两个物品应该互相比较。一个看起来效果不错(主观)的方法是让迄今为止获胜次数最少的物品随机与另一个物品进行比较。这会导致每个物品的比赛次数相对均匀(-> 准确性),但可能会让投票者感到无聊。他们经常会将最新的物品与其他物品进行比较,这有点无聊。为缓解这种情况,您可以选择计数最低的n个物品,并随机选择其中一个作为第一个竞争者。
您提到您希望对强劲的对手取得的胜利比对弱势对手的胜利更有价值。如其他帖子中所述,用于象棋等游戏的评分系统(Elo、Glicko)可能有效。个人认为,我喜欢使用微软的TrueSkill,因为它似乎是最准确的,并且还提供了一种好的方式来挑选两个项目进行比较 - 由TrueSkill计算出的具有最高平局概率的那些项目。但遗憾的是,我的数学理解不足以真正理解和实施该系统的详细信息,而且也可能要支付许可费用...

如果您需要更多信息/灵感,Collective Choice: Competitive Ranking Systems提供了几种不同的评级系统的概述。

除了评级系统外,您还可以尝试各种简单的梯队系统。一个例子:

将列表随机排列,使它们排名从1到n。
随机选择两个项目并让它们竞争。
如果胜者排名高于输家:什么都不做。
如果输家排名高于胜者:
- 如果输家直接在胜者上方:交换它们。 - 否则:将胜者向上移动“x”%以接近本次比赛的输家。
回到步骤2。
这种方法在开始时相对不稳定,但随着时间的推移应该会改善。然而,它永远不会停止波动。
希望我至少能提供一些帮助。

谢谢,你帮了很多忙。 :) 这些都是有趣的问题(如何选择物品等)。 - caw
你的胜利次数/总战斗次数,其中总战斗次数是指该特定电影参加的战斗次数,实际上是最好的指标,可以给出非常稳定的结果,这也是判断哪部电影最好的最佳方法(请参见我的答案)。你认为它有什么问题? - KernelJ
1
我明白你的意思了,我的系统假设每个人只能在某些随机事情上投一次票。这对于单个用户反复投票是微不足道的。如果有几个用户,您需要向系统图中添加另一个复杂级别,以使每个用户具有相同的权重,但如果许多人没有进行很多投票,则可能不准确。解决方法是sumoverallusers(fightswon/totalfights),即为所有用户记录投票历史,并将所有分数相加。如果totalfights为0,则可以假定fightswon/totalfights为默认值0.5。 - KernelJ

1

1
不会立即生效:PageRank假定一个无向循环图,而这些评级给出了一个二分图。这意味着算法没有任何依据来确定选民对链接价值的贡献。虽然想出解决方法并不难,但在你这样做之前,算法是不完整的。 - Charles Stewart
谢谢您提供的信息。所以您需要将一个电影定义为“好”的,才能进行其余电影的计算吗? - caw
2
据我所理解,你会得到一个有向图(电影a比b好)。它不一定是二分图—可能会有三角形。但我认为算法应该是制作矩阵: " A,其(i,j)条目为1,如果网站j链接到网站i,则否则为0 " 然后, " 你将找到它的特征向量,并寻找所有条目具有相同符号的向量。最大的条目将告诉您第一名团队,下一个最大的条目将属于第二名团队 " - HH321
1
@Charles Stewart PageRank不假设一个无向图。链接是有向边:http://en.wikipedia.org/wiki/PageRank#Simplified_algorithm - charstar
1
@Charles Stewart 我认为你把用户包括在图中作为节点有点偏离了。要将一个用户建模,您可以像PageRank一样从获胜者到失败者建立边缘。对于多个用户,您可能可以做同样的事情,但是基于用户平均值的边缘权重。我不确定这是否一定可解决,所以这只是一个想法。 - David Berger
显示剩余3条评论

1

经过深思熟虑,这个电影排名的最佳解决方案如下。

所需数据:

  • 每对电影投票数。
    • 以基数排序方式分组的排序版本数据
  • 每部电影在每对电影投票中被投票次数

可选数据:

  • 每位用户在每次投票中参与的电影次数

如何为用户选择投票:

  • 从使用最少的基数组中的排序列表中随机选择一个投票选择
  • 可选:使用用户的个人投票统计信息过滤他们被要求投票太多次的电影,如果没有合适的内容,则可能转向更高的基数桶。

如何计算电影的排名分数:

  • 将分数设为0
  • 遍历系统中的每部电影
    • 获得的票数/总票数与该电影相加以计算分数
      • 如果这两部电影之间没有投票记录,则添加0.5 (当然,这是假设您希望新电影在排名中始终保持平均水平)

注意:可选内容只是为了防止用户感到无聊,但对于其他统计数据也可能很有用,特别是如果您包括他们投票给该电影而不是另一部电影的次数。

确保尽快收集新添加电影的统计信息,并在所有现有电影中均匀分布投票,对于保持其余电影的正确统计非常重要。最好分批输入一组新电影以避免排名中的临时故障(虽然不会立即或严重)。

===这是原始答案===

问题实际上非常简单。我在这里假设您想按照对电影的投票偏好进行排序,即排名第一的电影最有可能在投票中被选择。如果您让每次投票都随机选择两部电影,那么您可以用简单的数学计算来计算这个问题。
首先,每次选择两部电影进行投票的概率是相等的,因此可以将每次投票的结果相加得到一个分数(这样可以避免在每个计算中都乘以1/nC2)。显然,某个特定电影对另一个特定电影的投票概率就是votesforthisfilm / numberofvotes
因此,要计算一个电影的得分,只需为它可以与之匹配的每部电影求和votesforthisfilm / numberofvotes
如果您添加了一部新电影,但它还没有与所有其他电影进行过足够数量的投票,那么您可能希望在排名中将其排除,直到积累了足够的投票。
===以下内容大多不正确,主要是为了历史背景而存在===

这种评分方法是从您的投票系统的马尔可夫链中推导出来的,假设所有可能的投票问题同等可能。[这个第一句话是错误的,因为在马尔可夫链中使所有投票问题同等可能会得到有意义的结果] 当然,事实并非如此,实际上您也可以修复它,因为您知道每个投票问题的可能性,只是已经对该问题进行了多少次投票![获得特定投票问题的概率实际上是无关紧要的,因此这并没有帮助] 通过这种方式,使用相同的图形,但边缘由完成的投票加权...

给定它被包含在投票中的每部电影的概率与获得每部电影和它被包含在投票中的概率相同,除以它被包含在投票中的概率。这等于 sumoverallvotes((votesforthisfilm / numberofvotes) * numberofvotes) / totalnumberofvotes 除以 sumoverallvotes(numberofvotes) / totalnumberofvotes。通过大量的取消,这变成了 votesforthisfilmoverallvotes / numberofvotesinvolvingthisfilm。这真的很简单!


非常感谢!将投票数除以投票数再乘以投票数有意义吗?您的方法没有考虑哪些项目被击败。因此,如果itemA在80%中击败了弱项,而itemB在70%中击败了强项,哪个更好?应该是itemB... - caw
这可能是计算全球指数的好方法...但它并不能帮助确定个人的偏好。我目前在Flickchart上有大约300部电影,并投票1000次。但是有300*299/2种可能的匹配组合。每部电影参与了大约6次投票。当所有投票总数都是1、2、3、4、5或6时,我该如何排名300部电影?更不用说大多数电影还没有配对,那些已经配对的电影也只配对了一次。 - David Berger
@David:我完全同意,这从来不是我的意图。随着投票数量的增加,这种方法会收敛到正确的答案。对于单个人来说,他们不会真的费心去投票足够多次以获得有意义的结果。然而,每个用户要存储的数据量非常小,因此您应该能够获得相当准确的全球排名。如果可以使用马尔可夫链方法通过对人进行刻板印象来猜测个人排名,或者任何仅基于每部电影总数的方法,那将是很有趣的。确实,这对于建议您应该看哪些电影是绝妙的! - KernelJ
@marco92w:*numberofvotes来自于numberofvotes/totalnumberofvotes这个因子,它代表了这个特定投票选择被选中的概率,正如前一段所讨论的那样。我将totalnumberofvotes放在外面是因为它不依赖于实际的投票选择。所以,这确实是有意义的。我的后一种解决方案取决于服务器试图通过尝试使所有投票选择的numberofvotes相等来维护投票选择的有效随机性(在第一个解决方案中保证)。这意味着新添加的电影将经常与随机电影进行比较。 - KernelJ
@KernelJ “通过给人们贴标签来猜测个人排名”这是Netflix大部分研发资金的投入方向,而且对于任何开发出比他们算法准确率高15%的人都有巨额现金奖励。 - David Berger
显示剩余2条评论

0

谢谢。在“BestThing算法”页面上,有一个关于算法所做的描述:展示两个项目,然后您选择您最喜欢的那个。这正是我正在寻找的。但是它真的那么简单吗?只需将胜利次数除以总战斗次数吗? - caw

0

我认为这种1对1的情况可能是一种叫做离散选择的联合分析类型。在市场研究的网络调查中,我经常看到这种情况。通常要求客户在两个或更多不同的功能集之间进行选择,以确定他们最喜欢哪一个。不幸的是,这对于像我这样的非统计学家来说相当复杂,所以您可能会有困难理解它。


谢谢你,d03boy。我认为这不是我正在寻找的算法。它在经济学中使用,但对于评估1对1战斗结果并不有用,对吧? - caw

-1

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接