Как порекомендовать следующее достижение

Question

Краткая версия:

У меня аналогичная установка для StackOverflow. Пользователи получают Достижения. У меня есть много других достижений, чем SO, скажем, порядка 10k, и каждый пользователь имеет в 100-х достижений. Теперь, как бы вы порекомендовали (рекомендовать) следующее достижение для пользователя, чтобы попробовать?

Длинная версия:

объекты моделируются, как это в Джанго (показывать только важные части):

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, count) как один оператор SQL. Как и сейчас, вы выпускаете много запросов и суммируете тысячи строк в Python, задача которой вы должны делегировать БД. Например, код

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 к себе на основе идентификатора псевдонима, отличающегося друг от друга, и идентификатора достижения одинакового. Затем вы группируете идентификатор достижения и запускаете счет.

В нижеприведенном запросе таблица «B» - это достижения других пользователей, а «Achiever» - наши достижения. Если любой другой пользователь разделяет достижение, они появляются один раз в «B» для каждого достижения, которое они разделяют. Затем мы группируем их по alias_id и подсчитываем количество раз, когда они появляются, и вы получаете хороший идентификатор, подсчитываете таблицу.

Очень очень грубый код (не 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, который использует один выше, как «внутренний выбор» - называть его пользователями. Вы присоединяетесь к этому с помощью таблицы достижений и вашей таблицы Achiever для текущего пользователя. Возможно, вы захотите проигнорировать всех, кроме первых 10 пользователей, похожих на текущего пользователя.

У меня нет времени, чтобы написать хороший запрос прямо сейчас, но посмотрите на инструкцию JOIN для вашей БД, которая объединяется в success_id между назначенными 10 пользователями и текущим пользователем, установив этот идентификатор в NULL, если он не существует. Фильтр только для строк, где он оказался NULL (не достигнутые достижения).