如何推荐下一步的成就

Question

简短版本：

我有一个类似于StackOverflow的设置。用户获得成就。我有更多的成就，比方说10k的数量级，每个用户都有100s的成就。现在，你将如何推荐(推荐)用户尝试的下一项成就？

长版本：

在django中对象是这样建模的(只显示重要的部分)：

class User(models.Model):
    alias = models.ForeignKey(Alias)

class Alias(models.Model):
    achievements = models.ManyToManyField('Achievement', through='Achiever')

class Achievement(models.Model):
    points = models.IntegerField()

class Achiever(models.Model):
    achievement = models.ForeignKey(Achievement)
    alias = models.ForeignKey(Alias)
    count = models.IntegerField(default=1)

我的算法只是找到与登录用户有共同成就的每个其他用户，然后查看他们的所有成就并按出现次数排序：

def recommended(request) :
    user = request.user.get_profile()

    // The final response
    r = {}

    // Get all the achievements the user's aliases have received 
    // in a set so they aren't double counted
    achievements = set()
    for alias in user.alias_set.select_related('achievements').all() :
        achievements.update(alias.achievements.all())

    // Find all other aliases that have gotten at least one of the same
    // same achievements as the user
    otherAliases = set()
    for ach in achievements :
        otherAliases.update(ach.alias_set.all())

    // Find other achievements the other users have gotten in addition to
    // the shared ones.
    // And count the number of times each achievement appears
    for otherAlias in otherAliases :
        for otherAch in otherAlias.achievements.all() :
            r[otherAch] = r.get(otherAch, 0) + 1

    // Remove all the achievements that the user has already gotten
    for ach in achievements :
        r.pop(ach)

    // Sort by number of times the achievements have been received
    r = sorted(r.items(), lambda x, y: cmp(x[1], y[1]), reverse=True)

    // Put in the template for showing on the screen
    template_values = {}
    template_values['achievements'] = r

但是它永远需要运行，并且总是返回整个列表，这是不必要的。用户只需要前几个成就就可以了。

因此，我欢迎对其他算法和/或代码改进的建议。我将在我的系统中为您提供推荐算法的成果:)

Answer 1

你可以推荐的一种方法是，看看你的用户中有多少人已经取得了这些成就，然后推荐那些流行的。当他们实现了这些目标后，你可以从列表中向下推荐稍微不太受欢迎的。然而，这有一个天真的假设，即每个人都想追求流行的成就。它可能会导致流行的成就更受欢迎和更不受欢迎，那么……令人欣慰的是，这不会占用太多资源，而且运行速度可能会非常快。(只需要保存一个成就列表+实现的次数)

另一种方法(试图根据用户已经取得的成就来猜测他可能追求的成就)是使用一些机器学习算法。我认为k-nearest neighbor algorithm在这里会有很好的表现。选择一个阈值，然后输出超过该阈值的所有内容。现在，我不知道这是否会比你已经拥有的运行得更快，但是你应该在每次用户取得新的成就时运行一次推荐引擎，存储前五个(比方说)，并在需要推荐的时候将其输出给用户。

我希望这能帮到你。=)

Answer 2

我建议您将前三个步骤(成就、otherAliases、计数)作为一条SQL语句来执行。现在，您正在使用Python发出大量查询并汇总数千行数据，这是您应该委托给DB的一项任务。例如，代码

for otherAlias in otherAliases : #For every single other user
    for otherAch in otherAlias.achievements.all() : #execute a query
        r[otherAch] = r.get(otherAch, 0) + 1

执行数千个巨大的查询。

取而代之的是，你可以使用SQL来连接Achiever本身，基于别名id不同而成就id相同。然后按成就id分组并运行计数。

在下面的查询中，表"B“是其他用户的成绩，"Achiever”是我们的成绩。如果任何其他用户分享了一项成就，他们分享的每项成就都会在"B“中出现一次。然后我们根据alias_id对它们进行分组，并计算它们出现的次数，这样您就可以得到一个很好的id，count表。

非常非常粗糙的代码(这里没有可用的SQL )

SELECT B.Alias_id, COUNT(B.achievement_id) 
  FROM Achiever, Achiever as B 
  WHERE Achiever.achievement_id == B.achievement_id 
     AND Achiever.Alias_id == <insert current user alias here>;
  GROUP BY B.Alias_id

如果以我认为的方式工作，您将获得一个包含其他用户别名的表，以及他们与当前用户共享的成果数量。

您要做的下一件事是一条SQL语句，它使用上面的语句作为“内部select”-称为用户。您可以将其与您的成就表和当前用户的Achiever表连接起来。您可能希望忽略与当前用户相似的前10个用户之外的所有用户。

我现在没有时间写一个好的查询，但是看看您的数据库的JOIN语句，它在achievement_id上连接指定的10个用户和当前用户-如果id不存在，则将其设置为NULL。过滤器只过滤到其结果为NULL (未实现的成就)的行。