company_banner

Item-based коллаборативная фильтрация своими руками

    Робот-рекомендатель

    Одной из наиболее популярных техник для построения персонализированных рекомендательных систем (RS, чтобы не путать с ПиСи) является коллаборативная фильтрация. Коллаборативная фильтрация бывает двух типов: user-based и item-based. User-based часто используется в качестве примера построения персонализированных RS [на хабре, в книге Т.Сегаран,...]. Тем не менее, у user-based подхода есть существенный недостаток: с увеличением количества пользователей RS линейно увеличивается сложность вычисления персонализированной рекомендации.

    Когда количество объектов для рекомендаций большое, затраты на user-based подход могут быть оправданы. Однако во многих сервисах, в том числе и в ivi.ru, количество объектов в разы меньше количества пользователей. Для таких случаев и придуман item-based подход.

    В этой статье я расскажу, как за несколько минут можно создать полноценную персонализированную RS на основе item-based подхода.

    Немного теории


    Рассмотрим получение k персонализированных рекомендаций (top-k) для некоторого пользователя A. В случае с user-based подходом, для построения рекомендаций находятся так называемые пользователи-соседи (neighbors) пользователя A. Соседи пользователя А — это пользователи, наиболее похожие на него с точки зрения истории просмотров/рейтингов. Количество соседей варьируется в зависимости от реализации и требований к RS, но обычно не превышает 50. Зная предпочтения соседей и историю просмотров пользователя А, RS строит top-k рекомендаций. Такой подход предполагает, что пользователю A понравятся те же объекты, что и пользователям-соседям.

    В случае с item-based подходом пользователь A характеризуется объектами objsA, которые он просмотрел или оценил. Для каждого объекта из objsA определяется m объектов-соседей, т.е. находятся m наиболее похожих объектов с точки зрения просмотров/оценок пользователей. При построении RS для фильмов, m принимает значения от 10 до 30. Все объекты-соседи объединяются во множество из которого исключаются объекты, просмотренные или оцененные пользователем A. Из оставшегося множества строится top-k рекомендаций. Таким образом, при item-based подходе в создании рекомендаций участвуют все пользователи, которым понравился тот или иной объект из objsA.

    В нашем случае для получения top-k рекомендаций используется простейший вариант алгоритма Deshpande M. и Karypsis G.. Рекомендации строятся на основе рейтингов зарегистрированных пользователей ivi.ru.

    Реализация


    Описанный ниже код позволяет получать рекомендации по фильмам для некоторого пользователя A по его истории рейтингов. Данные о рейтингах пользователей ivi.ru (за последние 30 дней) и названиях фильмов для удобства были предварительно выкачены в sqlite БД — ivi_rates.db.

    RS построена на Python с использованием пакетов: numpy, scipy, scikit-learn. Некоторые участки кода могут показаться «дикими» вследствие оптимизации, для них есть комментарии.

    Подготовка матрицы item-user

    Item-user матрица является исходной матрицей как для user-based, так и для item-based коллаборативной фильтрации. Строке данной матрицы соответствует объект, в нашем случае фильм. Столбцу соответствует пользователь. В ячейках матрицы расположены рейтинги.

    Для уменьшения шума в рекомендациях и увеличения их точности используются только данные о фильмах с количеством просмотров/рейтингов не менее определенного значения (confidence value). В нашем случае в построении item-user матрицы будут участвовать фильмы минимум c 10 рейтингами. Также, для уменьшения размерности пространства пользователей, мы исключим из построения всех пользователей, которые оценили только один фильм.

    Матрица item-user будет сильно разрежена, поэтому и хранить её мы будем соответствующим образом.

    import sqlite3
    conn = sqlite3.connect('ivi_rates.db')
    cursor = conn.cursor()
    
    # строим индекс user_id -> col_id, где col_id - идентификатор столбца в матрице
    # берем пользователей, оценивших не менее 2 фильмов
    users_sql = """
        SELECT user_id
        FROM rates
        WHERE rate IS NOT NULL
        GROUP BY user_id HAVING count(obj_id) >= 2
    """
    cursor.execute(users_sql)
    user_to_col = {}
    for col_id, (user_id,) in enumerate(cursor):
        user_to_col[user_id] = col_id
    
    # строим индекс obj_id -> row_id, где row_id - идентификатор строки в матрице
    # берем только фильмы, которые оценили не менее 10 пользователей
    objs_sql = """
        SELECT obj_id
        FROM rates
        WHERE rate IS NOT NULL AND user_id IN (
            SELECT user_id
            FROM rates
            WHERE rate IS NOT NULL
            GROUP BY user_id HAVING count(obj_id) >= 2
        )
        GROUP BY obj_id HAVING count(user_id) >= 10 
    """
    cursor.execute(objs_sql)
    obj_to_row = {}
    for row_id, (obj_id,) in enumerate(cursor):
        obj_to_row[obj_id] = row_id
        
    print u"Количество пользователей:", len(user_to_col)
    print u"Количество объектов:", len(obj_to_row)
    

    Количество пользователей: 353898
    Количество объектов: 7808

    Индексы нужны для быстрого преобразования идентификаторов пользователей/фильмов в идентификаторы столбцов/строк. Зная количество фильмов и пользователей, можно упростить процесс создания и заполнения матрицы item-user.

    from scipy.sparse import lil_matrix
    
    sql = """
        SELECT obj_id, user_id, rate
        FROM rates
        WHERE rate IS NOT NULL
    """
    cursor.execute(sql)
    
    matrix = lil_matrix((len(obj_to_row), len(user_to_col)))  # создаем матрицу нужных размеров
    # заполняем матрицу
    for obj_id, user_id, rate in cursor:
        row_id = obj_to_row.get(obj_id)
        col_id = user_to_col.get(user_id)
        if row_id is not None and col_id is not None:
            matrix[row_id, col_id] = min(rate, 10)
            
    percent = float(matrix.nnz) / len(obj_to_row) / len(user_to_col) * 100
    print u"Процент заполненности матрицы: %.2f%%" % percent
    

    Процент заполненности матрицы: 0.17%

    Подготовка матрицы item-item

    Основной матрицей для item-based подхода является матрица item-item. Строкам и столбцам этой матрицы соответствуют объекты. В ячейках хранится значение схожести объектов. Для определения схожести двух объектов используется метрика косинусной меры угла. Список рекомендаций вычисляется путем перемножения матрицы item-item на вектор просмотров/рейтингов пользователя A.

    В item-item матрице все значения по диагонали равны 1 (объект на 100% похож на себя). Чтобы исключить диагональ из рекомендаций, ее обычно зануляют.

    При стабильном интересе пользователей к объектам, матрица item-item также является стабильной. Под стабильностью интересов подразумевается следующее: если пользователю B нравятся фильмы, понравившиеся пользователю A, то велика вероятность, что пользователю B понравится еще один фильм из списка фильмов, понравившихся пользователю A. Стабильность матрицы означает, что с появлением новых просмотров/рейтингов значения внутри ячеек матрицы будут почти неизменны. Стабильность позволяет не перестраивать матрицу каждый раз при появлении новых рейтингов.

    Scipy, numpy, scikit позволяют выполнять матричные операции очень быстро (скорее всего, быстрее, чем любая самописная итерация). При использовании матриц лучше использовать функции из этих пакетов.

    from sklearn.preprocessing import normalize
    from scipy.sparse import spdiags
    
    # косинусная мера вычисляется как отношение скалярного произведения векторов(числитель) 
    # к произведению длины векторов(знаменатель)
    
    # нормализуем исходную матрицу 
    # (данное действие соответствует приведению знаменателя в формуле косинусной меры к 1)
    normalized_matrix = normalize(matrix.tocsr()).tocsr()
    # вычисляем скалярное произведение
    cosine_sim_matrix = normalized_matrix.dot(normalized_matrix.T)
    
    # обнуляем диагональ, чтобы исключить ее из рекомендаций
    # быстрое обнуление диагонали
    diag = spdiags(-cosine_sim_matrix.diagonal(), [0], *cosine_sim_matrix.shape, format='csr')
    cosine_sim_matrix = cosine_sim_matrix + diag
    
    percent = float(cosine_sim_matrix.nnz) / cosine_sim_matrix.shape[0] / cosine_sim_matrix.shape[1] * 100
    print u"Процент заполненности матрицы: %.2f%%" % percent
    print u"Размер в МБ:", cosine_sim_matrix.data.nbytes / 1024 / 1024
    

    Процент заполненности матрицы: 45.54%
    Размер в МБ: 211

    На самом деле, в каждой строке полученной матрицы item-item хранится список соседей объекта, соответствующего данной строке. Как уже было сказано ранее, для item-based подхода достаточно хранить m наиболее похожих объектов-соседей (top-m). Так как мы работаем с фильмами, то возьмем m равным 30.

    from scipy.sparse import vstack
    import numpy as np
    
    cosine_sim_matrix = cosine_sim_matrix.tocsr()
    m = 30
    
    # построим top-m матрицу в один поток
    rows = []
    for row_id in np.unique(cosine_sim_matrix.nonzero()[0]):
        row = cosine_sim_matrix[row_id]  # исходная строка матрицы
        if row.nnz > m:
            work_row = row.tolil()
            # заменяем все top-m элементов на 0, результат отнимаем от row
            # при большом количестве столбцов данная операция работает быстрее, 
            # чем простое зануление всех элементов кроме top-m
            work_row[0, row.nonzero()[1][np.argsort(row.data)[-m:]]] = 0
            row = row - work_row.tocsr()
        rows.append(row)
    topk_matrix = vstack(rows) 
    # нормализуем матрицу-результат
    topk_matrix = normalize(topk_matrix)
    
    percent = float(topk_matrix.nnz) / topk_matrix.shape[0] / topk_matrix.shape[1] * 100
    print u"Процент заполненности матрицы: %.2f%%" % percent
    print u"Размер в МБ:", topk_matrix.data.nbytes / 1024 / 1024
    

    Процент заполненности матрицы: 0.38%
    Размер в МБ: 1

    Согласно работе Deshpande M. и Karypsis G. рекомендации получаются лучше при нормализации конечной матрицы.

    Полученная top-m матрица является сильно разреженой и ее размер составляет всего 1 МБ. Т.е. в нашем случае для построения рекомендаций на основании данных о 353898 пользователях и 7808 объектах достаточно хранить матрицу размером всего 1 МБ.

    Получение рекомендаций


    Теперь, когда у нас есть матрица item-item, мы можем построить персонализированные рекомендации для пользователя А.

    Получение рекомендаций состоит из трех этапов:
    1. перемножить матрицу item-item и вектор просмотров/рейтингов пользователя A;
    2. в векторе-результате занулить ячейки, соответствующие фильмам, которые пользователь A уже просмотрел или оценил;
    3. отсортировать фильмы в порядке убывания значений, оставшихся в ячеках вектора-результата, и получить top-k рекомендованных фильмов.

    # индекс для преобразования row_id -> obj_id, где row_id - идентификатор строки в матрице
    row_to_obj = {row_id: obj_id for obj_id, row_id in obj_to_row.iteritems()}
    
    # заранее собираем индекс obj_id -> title
    title_sql = """
        SELECT obj_id, obj_title
        FROM rates
        GROUP BY obj_id, obj_title
    """
    cursor.execute(title_sql)
    obj_to_title = {}
    for obj_id, title in cursor:
        obj_to_title[obj_id] = title
    

    #подготавливаем вектор рейтингов пользователя:
    user_vector = lil_matrix((len(obj_to_row), 1))
    user_vector[7780, 0] = 7  # Скорый «Москва-Россия»
    user_vector[7755, 0] = 10 # Отель «Гранд Будапешт»
    user_vector[7746, 0] = 8  # Мстители
    user_vector[7657, 0] = 8  # Охотники за сокровищами
    user_vector[6683, 0] = 7  # 300 спартанцев: Расцвет империи
    user_vector[7656, 0] = 9  # Невероятная жизнь Уолтера Митти
    user_vector[7356, 0] = 9  # Одинокий рейнджер
    user_vector[7296, 0] = 8  # Елки 3
    user_vector[6839, 0] = 7  # Легенда №17
    user_vector[4190, 0] = 7  # 21 и больше
    user_vector[7507, 0] = 9  # Покорители волн
    user_vector[6938, 0] = 9  # Кон-Тики
    user_vector[4230, 0] = 10 # Карты, деньги, два ствола
    user_vector[3127, 0] = 8  # 13
    user_vector = user_vector.tocsr()
    

    # 1. перемножить матрицу item-item и вектор рейтингов пользователя A
    x = topk_matrix.dot(user_vector).tolil()
    # 2. занулить ячейки, соответствующие фильмам, которые пользователь A уже оценил
    for i, j in zip(*user_vector.nonzero()):
        x[i, j] = 0
        
    # превращаем столбец результата в вектор
    x = x.T.tocsr()    
        
    # 3. отсортировать фильмы в порядке убывания значений и получить top-k рекомендаций (quorum = 10)
    quorum = 10
    data_ids = np.argsort(x.data)[-quorum:][::-1]
    
    result = []
    for arg_id in data_ids:
        row_id, p = x.indices[arg_id], x.data[arg_id] 
        result.append({"obj_id": row_to_obj[row_id], "weight": p})
    
    result
    

    Результат
    [{'obj_id': 1156180, 'weight': 8.4493290509843408},
    {'obj_id': 978100, 'weight': 6.4337821664936943},
    {'obj_id': 1143770, 'weight': 5.5038366682680451},
    {'obj_id': 978120, 'weight': 5.4203284682159421},
    {'obj_id': 985220, 'weight': 5.2386991677359047},
    {'obj_id': 1033040, 'weight': 5.0466735584390117},
    {'obj_id': 1033290, 'weight': 4.8688497271055011},
    {'obj_id': 1046560, 'weight': 4.6880514059004224},
    {'obj_id': 984040, 'weight': 4.6199406111214927},
    {'obj_id': 960770, 'weight': 4.5788899365020477}]

    Ура! Мы построили рекомендации для пользователя. Однако в таком виде они мало о чем говорят. Хорошо, когда RS объясняет пользователю, почему ему рекомендуют тот или иной объект. Существует множество способов объяснения рекомендаций, полученных с использованием коллаборативной фильтрации (подробнее можно почитать у J.Herlocker, J.Konstan, J.Riedl). Здесь приведен один из способов объяснения рекомендаций, который легко реализуется с учетом имеющихся матриц и данных.

    Каждый рекомендованный фильм будет объясняться так: Мы рекомендуем Вам "%(title)s", так как он нравится пользователям, просмотревшим "%(impact)s". Вы оценили "%(impact)s" на %(impact_value)s.

    # фильмы, которые мы рекомендуем, и их связь с фильмами, которые оценил пользователь
    result = []
    for arg_id in data_ids:
        row_id, p = x.indices[arg_id], x.data[arg_id]
        obj_id = row_to_obj[row_id]
        
        # определяем, как повлиял на рекомендуемый фильм каждый из оцененных пользователем фильмов.
        # topk_matrix[row_id] - вектор соседей рекомендованного фильма obj_id
        # .multiply(user_vector.T) - зануляет все фильмы, которые пользователь не оценивал
        # impact_vector - вес просмотренных пользователем фильмов при подсчете метрики рекомендации obj_id
        impact_vector = topk_matrix[row_id].multiply(user_vector.T)
        
        # наиболее значимый фильм - ячейка с наибольшим значением в impact_vector
        impacted_arg_id = np.argsort(impact_vector.data)[-1]
        impacted_row_id = impact_vector.indices[impacted_arg_id]
        impact_value = user_vector[impacted_row_id, 0]
        impacted_obj_id = row_to_obj[impacted_row_id]  # наиболее значимый фильм
        
        rec_item = {
            "title": obj_to_title[obj_id],
            "weight": p,
            "impact": obj_to_title[impacted_obj_id],
            "impact_value": impact_value
        }
        result.append(rec_item)
        print u'''Мы рекомендуем Вам "%(title)s", так как он нравится пользователям, просмотревшим "%(impact)s". Вы оценили "%(impact)s" на %(impact_value)s.''' % rec_item
    

    Результат
    Мы рекомендуем Вам «Кухня в Париже», так как он нравится пользователям, просмотревшим «Скорый «Москва-Россия»».
    Вы оценили «Скорый «Москва-Россия»» на 7.0.
    **************************
    Мы рекомендуем Вам «Невозможное», так как он нравится пользователям, просмотревшим «Кон-Тики».
    Вы оценили «Кон-Тики» на 9.0.
    **************************
    Мы рекомендуем Вам «Приключения мистера Пибоди и Шермана», так как он нравится пользователям, просмотревшим «Скорый «Москва-Россия»».
    Вы оценили «Скорый «Москва-Россия»» на 7.0.
    **************************
    Мы рекомендуем Вам «Паркер», так как он нравится пользователям, просмотревшим «Карты, деньги, два ствола».
    Вы оценили «Карты, деньги, два ствола» на 10.0.
    **************************
    Мы рекомендуем Вам «Бойфренд из будущего», так как он нравится пользователям, просмотревшим «Одинокий рейнджер».
    Вы оценили «Одинокий рейнджер» на 9.0.
    **************************
    Мы рекомендуем Вам «Волк с Уолл-стрит», так как он нравится пользователям, просмотревшим «Невероятная жизнь Уолтера Митти».
    Вы оценили «Невероятная жизнь Уолтера Митти» на 9.0.
    **************************
    Мы рекомендуем Вам «Горько!», так как он нравится пользователям, просмотревшим «Елки 3».
    Вы оценили «Елки 3» на 8.0.
    **************************
    Мы рекомендуем Вам «Стив Джобс. Потерянное интервью», так как он нравится пользователям, просмотревшим «Кон-Тики».
    Вы оценили «Кон-Тики» на 9.0.
    **************************
    Мы рекомендуем Вам «Техасская резня бензопилой 3D», так как он нравится пользователям, просмотревшим «Отель «Гранд Будапешт»».
    Вы оценили «Отель «Гранд Будапешт»» на 10.0.
    **************************
    Мы рекомендуем Вам «Хоббит: Пустошь Смауга», так как он нравится пользователям, просмотревшим «Невероятная жизнь Уолтера Митти».
    Вы оценили «Невероятная жизнь Уолтера Митти» на 9.0.
    **************************

    В приведенном примере построения RS не используется нормализация рейтингов, так как тема нормализации данных достойна отдельной статьи.

    Описанный способ построения персонализированной RS позволяет показать, что item-based подход является мощным инструментом для построения RS. В то же время, стоит понимать, что современные RS используют несколько персонализированных и неперсонализированных методов для построения рекомендаций. Комбинированное использование различных методов позволяет создавать хорошие рекомендации независимо от количества данных о пользователе или объекте.

    Онлайн-кинотеатр ivi

    79,00

    Компания

    Поделиться публикацией

    Похожие публикации

    Комментарии 13
      0
      Спасибо за статью!

      А вы вроде раньше какой-то сторонний сервис использовали для этого? :)
        +1
        Да, и до сих пор используем. Но он перестает удовлетворять нашим требованиям, поэтому решили написать свой.
        +2
        Кто такой Пользователь: это 1) залогиненный юзер, или 2) просто сессия на девайсе?

        Понимаю, что процесс эволюции может быть не быстрым. Посему пример для моего вопроса: На моём рабочем планшете есть приложение с аккаунтом, и там будет работать подборка. В телевизоре тоже приложение, но на телике ребёнок смотрит мультики. Что будет в вашем случае алгоритм показыать?
          0
          Вот это кстати важный вопрос =)
            +2
            Если пользователь — залогиненный юзер, то у него есть «постоянная» история просмотров/рейтингов/и т.д… Если история действий достаточно информативна, то персонализированные рекомендации строятся по ней.

            Если пользователь не залогинен, то у него «временная» история, которая истечет по завершению сессии. Рекомендации строятся по «временной» истории, если она достаточно информативна.

            Если истории не информативна или ее нет, то вместо персонализированных рекомендаций обычно используют тематические блоки или «популярное».
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              а почему именно коллаборативная фильтрация, а не ассоциативные правила, FPG, например?
                0
                Ассоциативные правила обычно используются для определения какие объекты смотрятся совместно с каким-то (т.е ассоциируются). Поэтому ассоциативные правила чаще используют для построения неперсонализированных рекомендаций. А в топике описана только персонализированная RS.

                Про FPG до это не слышал, буду благодарен, если поделитесь ссылкой.
              0
              Item-вектора, которые мы получаем из User-Item матрицы и на основании которых мы потом считаем косинус угла, тоже разрежены как и сама матрица. Встает вопрос, что делать с пустыми позициями векторов. Есть два решения, которые лежат «на поверхности» (заполнять нулями или брать только позиции заполненные в обоих векторах), но оба они по-своему плохи. Интересно, как поступаете вы?
                0
                Мне кажется, что плох, только случай забора позиций заполненный в обоих векторах.

                При подсчете схожести важно, чтобы похожими считались фильмы у которых почти одинаковые наборы пользователей. При этом важно избежать «эффекта Гарри Поттера», когда фильм, который просмотрели все пользователи был бы сильно похож на каждый фильм в коллекции.

                В обоих предложенных вариантах(заполнять нулями или брать только позиции заполненные в обоих векторах) при вычислении косинусной меры числитель будет одинаковым. Знаменатель будет разный, но только в первом случае он позволит избежать описанные выше эффект.
                  0
                  «Проблема» с cosine similarity в моем понимании заключается в консервативности самой метрики. Проще наверное продемонстрировать на примере:

                  • пара Item-векторов {0, 5} и {0, 5} имеет cosine similarity = 1;
                  • пара Item-векторов {5, 5} и {0, 5} имеет cosine similarity = 1/sqrt(2);

                  Во-втором случае вектора, дальше друг от друга (item'ы менее похожи). Но это, на мой вгляд не совсем правомерно, ведь у нас просто нет оценки по одному Item'у. Потенциально, там могла быть 5-ка, что опять нас привело бы к единичной косинусной мере. Возможно, хорошей альтернативой было бы не занулять, а «засреднять» оценки. То есть, заполнять пустые ячейки матрицы средней оценкой Item'а, или средней оценкой целовека (по всем item'ам). Это должно сделать алгоритм не таким консервативным к отсутствующим оценкам.
                    0
                    Ок, рассмотрим ситуацию. Есть контент, который вам совсем не нравится. И, так как вы его не ищите и не смотрите, оценка у него — None. Усредненное значение рейтинга — это попытка найти границу между тем, что вам нравится или не нравится. Т.е указание некоторого безразличия относительно объекта. Таким образом мы строим вам рекомендации, основываясь на фильме, который система считает нейтральным, а вам он не нравится. Мне кажется, что это так себе решение.

                    Другое дело, что рейтингов может быть мало и схожесть посчитается плохо. Но это можно исправить кучей способов, например:
                    • оценивать два фильма только если у них не менее X общих рейтингов;
                    • предлагать пользователям пооценивать фильмы с маленьким количеством рейтингов;
                    • учитывать просмотры пользователя. тут, кстати, можно использовать средний рейтинг пользователя, если он просмотрел фильм, но не оценил его;
                    • использовать демпфирование;
                    • и т.д.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое