Коллаборативная фильтрация

    В современном мире часто приходится сталкиваться с проблемой рекомендации товаров или услуг пользователям какой-либо информационной системы. В старые времена для формирования рекомендаций обходились сводкой наиболее популярных продуктов: это можно наблюдать и сейчас, открыв тот же Google Play. Но со временем такие рекомендации стали вытесняться таргетированными (целевыми) предложениями: пользователям рекомендуются не просто популярные продукты, а те продукты, которые наверняка понравятся именно им. Не так давно компания Netflix проводила конкурс с призовым фондом в 1 миллион долларов, задачей которого стояло улучшение алгоритма рекомендации фильмов (подробнее). Как же работают подобные алгоритмы?

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



    Входные данные

    Допустим, у нас имеется матрица оценок, выставленных пользователями продуктам, для простоты изложения продуктам присвоены номера 1-9:


    Задать её можно при помощи csv-файла, в котором первым столбцом будет имя пользователя, вторым — идентификатор продукта, третьим — выставленная пользователем оценка. Таким образом, нам нужен csv-файл со следующим содержимым:
    alex,1,5.0
    alex,2,3.0
    alex,5,4.0
    ivan,1,4.0
    ivan,6,1.0
    ivan,8,2.0
    ivan,9,3.0
    bob,2,5.0
    bob,3,5.0
    david,3,4.0
    david,4,3.0
    david,6,2.0
    david,7,1.0
    

    Для начала разработаем функцию, которая прочитает приведенный выше csv-файл. Для хранения рекомендаций будем использовать стандартную для python структуру данных dict: каждому пользователю ставится в соответствие справочник его оценок вида «продукт»:«оценка». Получится следующий код:
    import csv
    def ReadFile (filename = "<csv_file_location>"):
        f = open (filename)
        r = csv.reader (f)
        mentions = dict()
        for line in r:
            user    = line[0]
            product = line[1]
            rate    = float(line[2])
            if not user in mentions:
                mentions[user] = dict()
            mentions[user][product] = rate
        f.close()
        return mentions
    


    Мера схожести

    Интуитивно понятно, что для рекомендации пользователю №1 какого-либо продукта, выбирать нужно из продуктов, которые нравятся каким-то пользователям 2-3-4-etc., которые наиболее похожи по своим оценкам на пользователя №1. Как же получить численное выражение этой «похожести» пользователей? Допустим, у нас есть M продуктов. Оценки, выставленные отдельно взятым пользователем, представляют собой вектор в M-мерном пространстве продуктов, а сравнивать вектора мы умеем. Среди возможных мер можно выделить следующие:
    1. Косинусная мера
    2. Коэффициент корреляции Пирсона
    3. Евклидово расстояние
    4. Коэффициент Танимото
    5. Манхэттенское расстояние и т.д.

    Более подробно различные меры и аспекты их применения я собираюсь рассмотреть в отдельной статье. Пока же достаточно сказать, что в рекомендательных системах наиболее часто используются косинусная мера и коэффициент корреляции Танимото. Рассмотрим более подробно косинусную меру, которую мы и собираемся реализовать. Косинусная мера для двух векторов — это косинус угла между ними. Из школьного курса математики мы помним, что косинус угла между двумя векторами — это их скалярное произведение, деленное на длину каждого из двух векторов:

    Реализуем вычисление этой меры, не забывая о том, что у нас множество оценок пользователя представлено в виде dict «продукт»:«оценка»
    def distCosine (vecA, vecB):
        def dotProduct (vecA, vecB):
            d = 0.0
            for dim in vecA:
                if dim in vecB:
                    d += vecA[dim]*vecB[dim]
            return d
        return dotProduct (vecA,vecB) / math.sqrt(dotProduct(vecA,vecA)) / math.sqrt(dotProduct(vecB,vecB))
    

    При реализации был использован факт, что скалярное произведение вектора самого на себя дает квадрат длины вектора — это не лучшее решение с точки зрения производительности, но в нашем примере скорость работы не принципиальна.

    Алгоритм коллаборативной фильтрации

    Итак, у нас есть матрица предпочтений пользователей и мы умеем определять, насколько два пользователя похожи друг на друга. Теперь осталось реализовать алгоритм коллаборативной фильтрации, который состоит в следующем:
    1. Выбрать L пользователей, вкусы которых больше всего похожи на вкусы рассматриваемого. Для этого для каждого из пользователей нужно вычислить выбранную меру (в нашем случае косинусную) в отношении рассматриваемого пользователя, и выбрать L наибольших. Для Ивана из таблицы, приведенной выше, мы получим следующие значения:
    2. Для каждого из пользователей умножить его оценки на вычисленную величину меры, таким образом оценки более «похожих» пользователей будут сильнее влиять на итоговую позицию продукта, что можно увидеть в таблице на иллюстрации ниже
    3. Для каждого из продуктов посчитать сумму калиброванных оценок L наиболее близких пользователей, полученную сумму разделить на сумму мер L выбранных пользователей. Сумма представлена на иллюстрации в строке «sum», итоговое значение в строке «result»

      Серым цветом отмечены столбцы продуктов, которые уже были оценены рассматриваемым пользователем и повторно предлагать их ему не имеет смысла

    В виде формулы этот алгоритм может быть представлен как

    где функция sim — выбранная нами мера схожести двух пользователей, U — множество пользователей, r — выставленная оценка, k — нормировочный коэффициент:


    Теперь осталось только написать соответствующий код
    import math
    def makeRecommendation (userID, userRates, nBestUsers, nBestProducts):
        matches = [(u, distCosine(userRates[userID], userRates[u])) for u in userRates if u <> userID]
        bestMatches = sorted(matches, key=lambda(x,y):(y,x), reverse=True)[:nBestUsers]
        print "Most correlated with '%s' users:" % userID
        for line in bestMatches:
            print "  UserID: %6s  Coeff: %6.4f" % (line[0], line[1])    
        sim = dict()
        sim_all = sum([x[1] for x in bestMatches])
        bestMatches = dict([x for x in bestMatches if x[1] > 0.0])        
        for relatedUser in bestMatches:
            for product in userRates[relatedUser]:
                if not product in userRates[userID]:
                    if not product in sim:
                        sim[product] = 0.0
                    sim[product] += userRates[relatedUser][product] * bestMatches[relatedUser]
        for product in sim:
            sim[product] /= sim_all
        bestProducts = sorted(sim.iteritems(), key=lambda(x,y):(y,x), reverse=True)[:nBestProducts]
        print "Most correlated products:"
        for prodInfo in bestProducts:    
            print "  ProductID: %6s  CorrelationCoeff: %6.4f" % (prodInfo[0], prodInfo[1])
        return [(x[0], x[1]) for x in bestProducts]
    


    Для проверки его работоспособности можно выполнить следующую команду:
    rec = makeRecommendation ('ivan', ReadFile(), 5, 5)
    

    Что приведет к следующему результату:


    Заключение

    Мы рассмотрели на примере и реализовали один из простейших вариантов коллаборативной фильтрации с использованием косинусной меры сходства. Важно понимать, что существуют другие подходы к коллаборативной фильтрации, другие формулы для вычисления оценок продуктов, другие меры схожести (статья, раздел «See also»). Дальнейшее развитие этой идеи можно вести в следующих направлениях:
    1. Оптимизация используемых стуктур данных. При хранении данных в python в виде dict, при каждом обращении к конкретному значению производится вычисление хэша и ситуация становится тем хуже, чем длинее строки названий. В практических задачах для хранения данных можно использовать разреженные матрицы, а вместо текстовых имен пользователей и названий продуктов использовать числовые идентификаторы (пронумеровать всех пользователей и все продукты)
    2. Оптимизация производительности. Очевидно, что вычислять рекомендацию при каждом обращении пользователя — занятие крайне затратное. Есть несколько вариантов обхода этой проблемы:
      • Кластеризация пользователей и вычисление меры схожести только между пользователями, принадлежащими одному кластеру
      • Вычисление коэффициентов схожести продукт-продукт. Для этого нужно транспонировать матрицу пользовать-продукт (получится матрица продукт-пользователь), после чего для каждого из продуктов вычислить набор наиболее схожих продуктов, используя ту же косинусную меру и запомнив k ближайших. Это достаточно трудоемкий процесс, поэтому производить его можно один раз в M часов/дней. Но теперь у нас есть список продуктов, похожих на данный, и умножив оценки пользователя на значение меры схожести продуктов, мы получим рекомендацию за O(N*k), где N — количество оценок пользователя
    3. Подбор меры сходства. Косинусная мера является одной из часто используемых, но выбор меры нужно производить только по результатам анализа данных системы
    4. Модификация алгоритма фильтрации. Возможно, другой алгоритм фильтрации даст более точные рекомендации в конкретной системе. Опять же, сравнение различных алгоритмов можно производить только в применении к конкретной системе

    Литература

    1. Программируем коллективный разум
    2. Коллаборативная фильтрация на вики
    3. Косинусная мера
    4. Разреженные матрицы

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 20

    • UFO just landed and posted this here
        0
        Не профит. При небольшом объеме данных от пользователя, круг рекомендаций будет очень узкий. Допустим, если меня спросят топ10 любимых фильмов, там скорее всего не будет комедий или приключений. Соотвественно, даже оценивая то, что мне будет предлагаться, таким способом, до комедий я могу вообще не добраться.

        С другой стороны, при небольшом количестве оценок от пользователей, этот метод показывает гораздо более адекватные результаты.

        Лучше смешивать. Пока данных мало, брать похожие по вашему алгоритму, когда становится больше — добавлять вес данным на основе предпочлений пользователей. Со временем, превалировать должны последние.
          +1
          есть такие рекомендационные системы, которые учитывают метаданные и даже пытаются делать что-то умное с темантическими онтологиями. Но я еще не видел, чтобы такие рекомендации рвали в клочья более традиционные и тупые подходы вроде колл.фильтрации
            0
            *тематическими
          +4
          > Не так давно компания Netflix проводила конкурс с призовым фондом в 1 миллион долларов, задачей которого стояло улучшение алгоритма рекомендации фильмов (подробнее).

          в 2007м году. я даже писал обзорный реферат, чтобы сдать «современные проблемы прикладной математики», в котором кратко максимально простым языком попытался описать:
          Регулярное разложение по сингулярным значениям (RSVD – regularized singular value decomposition)
          Улучшенный RSVD
          Оценка с помощью кластеризации методом K-средних
          Пост-обработка результатов RSVD с помощью поиска ближайших соседей
          Пост-обработка результатов RSVD с помощью регуляризации Тихонова (kernel ridge regression)
          Ограниченная машина Больцмана

          если кому интересно
            0
            эх, хорошо, но можно было бы и потщательнее пережевать :)
            +3
            Подробнее про решение Bellkor, выигравших Netflix Prize

            Мне понравились их регрессионные модели, т.к. у меня диплом был на эту тем.

            Время быстро летит, казалось вот только недавно 2009 был :)
              +2
              Интересно, что решение, выигравшее миллион долларов, так и не было внедрено в production, подробнее в статье:
              «If you followed the Prize competition, you might be wondering what happened with the final Grand Prize ensemble that won the $1M two years later. This is a truly impressive compilation and culmination of years of work, blending hundreds of predictive models to finally cross the finish line. We evaluated some of the new methods offline but the additional accuracy gains that we measured did not seem to justify the engineering effort needed to bring them into a production environment. Also, our focus on improving Netflix personalization had shifted to the next level by then. In the remainder of this post we will explain how and why it has shifted.»
              +1
              спасибо за статью, я все ещё пишу свой рекомендательный сервис и решил поспрашивать

              Давайте рассмотрим Алекса, Ивана и Давида
              Группа №1: у Алекса и Ивана одно пересечение №1, оценки 5 и 4 соответственно
              Группа №2: у Алекса и Давида одно пересечение №6, оценки 1 и 2 соответственно

              Первой группе обоим нравится один фильм, а второй обоим один фильм не нравится

              Косинусная мера считает, что Группа №1 в десять раз более схожая, чем Группа №2
              Мне кажется, что тут явная логическая ошибка… Как бы вы могли прокомментировать данное поведение(если можно с живыми примерами)?

                0
                Тут явная математическая ошибка, причем у вас, а не у автора: вы забыли поделить на произведение модулей.
                  0
                  А, все, понял о чем вы. Все-таки у автора ошибка… Модуль надо считать только на общем базисе, а не на всем наборе оценок.

                  def distCosine (vecA, vecB):
                      def dotProduct (x, y):
                          d = 0.0
                          for dim in vecA:
                              if dim in vecB:
                                  d += x[dim]*y[dim]
                          return d
                      return dotProduct (vecA,vecB) / math.sqrt(dotProduct(vecA,vecA)) / math.sqrt(dotProduct(vecB,vecB))
                  


                  Вот так правильнее будет.
                    0
                    В предыдущем топике автора я уже поднимал вопрос странности косинусной метрики:
                    Мои данные
                    __Id_|__Косинусная метрика_|_Евклидово расстояние
                    (11382, (0.9945617655513243, 6.0))
                    (25881, (0.9946889722415817, 10.44030650891055))
                    (32657, (0.9948579893001871, 4.58257569495584))
                    (11642, (0.9949290831814581, 4.898979485566356))
                    (29796, (0.9950464316093013, 5.656854249492381))
                    (31417, (0.9951124675317691, 6.782329983125268))
                    (40530, (0.9952102629001573, 4.58257569495584))
                    (8311, (0.9952136477352348, 5.830951894845301))
                    (37772, (0.995641393209143, 4.47213595499958))
                    (11087, (0.9964597867088298, 4.795831523312719))
                    (9641, (0.996734136199907, 3.7416573867739413))
                    (9651, (0.9969863072847556, 30.04995840263344))
                    (22462, (0.9972173920027746, 3.3166247903554))
                    (6309, (0.9999999999999999, 0.0))

                    Почему-то появился объект 9651(третий с конца) хотя у него оценки сильно разнятся
                    Автор ответил:
                    По поводу использования метрик: предположим, у нас есть три вектора (10, 10, 1), (1, 1, 0) и (0, 0, 1). Согласно евклидовому расстоянию наиболее близки вектора 2 и 3, а по косинусной метрике — 1 и 2, что более корректно.
                    Выбор метрики обусловлен конкретной задачей

                    я так и не понял почему это более коректно

                      0
                      Это более корректно, так как (1, 1, 0) и (0, 0, 1) вообще не имеют общих оценок. Допустим, один человек посмотрел фильмы «Аватар» и «Бэтмен» и поставил им оценку «1», а другой — фильм «Начало» и поставил ему «1». И первому порекомендуют посмотреть фильм «Начало» на основании данных второго пользователя, хотя они смотрят совсем разные фильмы и вкусы из скорее всего расходятся
                      В данном случае под «0» понимается не какая-либо оценка, а отсутствие оценки — это допущение, которое необходимо для работы косинусной меры и евклидова расстояния. Если при вычислении расстояния использовать только совпадающие оценки, не будет учитываться общее количество оценок, и пользователь с оценками (1, 0, 0, 0, 0, 0, 0) будет одинаково похож как на (1, 1, 0, 0, 0, 0, 0), так и на (1, 1, 1, 1, 1, 1, 1)
                      0
                      В целом, косинусная мера — это именно косинус угла между векторами, а для вычисления его используется полная длина векторов, а не только длина по совпадающим измерениям
                      Вопрос выбора метрики нетривиален, его я хочу описать в отдельной статье. Это, действительно, один из недостатков косинусной меры. Вместо неё можно использовать тот же коэффициент корреляции Пирсона, но и он не идеален: так как боб поставил всего две оценки и обе они являются пятерками, то дисперсия его оценок равна нулю и коэффициент корреляции не определен, так что в формулу вычисления коэффициента корреляции придется добавлять сглаживающие коэффициенты.
                      Также можно произвести бинаризацию оценок: оценки больше или равные мат. ожиданию оценки данного пользователя заменяются на «1», а меньшие на «0». После этого можно будет применить одну из следующих мер: Жаккарда, Танимото и т.д.
                      В целом, выбор меры зависит от конкретной задачи, а корректность выбранной меры можно проверить тем же k-Fold + RMSE. Иногда оказывается полезно использовать линейную комбинацию нескольких мер + средний рейтинг продукта, коэффициенты можно подобрать при помощи линейной регрессии
                        0
                        Если рассматривать оценку на шкале от 1 до 5 звездочек и считать оценку 5 за «отлично», а 1 за «ужасно», то перед использованием косинусной меры можно произвести нормализацию оценок, вычтя из оценки мат. ожидание. Если принять мат. ожидание за 3.0 и не обращать внимание на проблему с нулевым вектором предпочтений для человека, который всем продуктам ставит 3.0, то мы получим следующий код:
                        def distCosine (vecA, vecB):
                            def dotProduct (x, y):
                                d = 0.0
                                for dim in x:
                                    if dim in y:
                                        d += (x[dim]-3.0)*(y[dim]-3.0)
                                return d
                            return dotProduct (vecA, vecB) / math.sqrt(dotProduct(vecA,vecA)) / math.sqrt(dotProduct(vecB,vecB))
                        

                        Он показывает схожесть Ивана с Алексом 0.3651, а с Дэвидом 0.3333

                        В то же время нужно понимать, что рекомендательные системы могут строиться на основании разных данных, и если в одной задаче мы оперируем с оценками «от 1 до 5 звездочек», то в другой задаче это может быть «1 для просмотра и 2 для покупки», в третьей — «количество фактов оказания услуги». В каждой из таких систем должен быть свой подход к подготовке данных и выбору меры сходства
                      0
                      я не сделал ни одного математического действия
                      я ошибся во второй группе, там Иван и Давид(у Алекса и Давида вообще нет пересечений)
                      все остальные числа из статьи:
                      схожесть группы №1 = 0.51
                      схожесть группы №2 = 0.06
                        0
                        Согласен. В обоих случаях разница в 1 балл, но в разную сторону. При этом влияние мнения Алекса отличается на порядок, благодаря чему, предлагается то, что рекомендует Алекс.

                    0
                    Сразу видно, что вы читали книгу Тоби Сегарана. Это очень хорошая и даже в какой-то степени уникальная книга
                    Правда в коде есть существенные опечатки, особенно в разделе про вычисление коэффициента подобия используя евклидову метрику.
                      0
                      О, спасибо, записал ISBN 5932861193.
                    • UFO just landed and posted this here

                      Only users with full accounts can post comments. Log in, please.