Использование коэффициента Танимото для поиска людей с одинаковыми предпочтениями

Решая упражнения к книге «Программируем коллективный разум», я решил поделиться реализацией одного из алгоритмов упомянутого в этой книге (Глава 2 — Упражнение 1).

Исходные условия следующие: пусть мы имеем словарь с оценками критиков:

critics={'Lisa Rose'{'Superman Returns'3.5'You, Me and Dupree'2.5'The Night Listener'3.0}
           'Gene Seymour'
{'Superman Returns'5.0'The Night Listener'3.5'You, Me and Dupree'3.5}}

Чем выше оценка, тем больше нравится фильм.
Надо вычислить: насколько схожи интересы критиков для того, например, чтобы можно было на основе оценок одного рекомендовать фильмы другому?



Коэффициент Танимото – описывает степень схожести двух множеств. В интернете я нашел несколько вариантов формулы для его вычисления. И решил остановиться на следующем:

, где k — коэффициент Танимото (число от 0 до 1), чем он ближе к 1, тем более схожи множества;
a — количество элементов в первом множестве;
b — количество элементов во втором множестве;
c — количество общих элементов в двух множествах;
Теперь нам надо сравнить оценки двух критиков.
Сразу хочу прояснить один момент. Что следует считать общим элементом в двух наших множествах? Понятно, что представление оценки в текущем виде не позволит достаточно точно определить людей со схожими интересами. Ведь, по сути своей, одинаковые оценки 3,5 и 4.0 для этого алгоритма — совершенно разные цифры. Поэтому коэффициент Танимото, на мой взгляд, стоит использовать, если количество вариантов оценок не больше 2-3 (например, «понравилось-не понравилось» или «рекомендую-не смотрел-не рекомендую») Я решил немного изменить словарь для более удобной работы и применил к оценкам следующее преобразование: Если оценка меньше 3, значит фильм не понравился (оценка становится — 0), иначе – понравился (оценка становится — 1). Данные в таком виде являются более подходящими для нашего эксперимента.
def prepare_for_tanimoto(critics_arr):
    arr = critics_arr.copy()
    for critic in arr:
        for film in arr[critic]:
            if arr[critic][film] < 3:
                arr[critic][film] = 0
            else:
                arr[critic][film] = 1
    return arr

На выходе мы получим следующий словарь:

critics={'Lisa Rose'{'Superman Returns'1'You, Me and Dupree'0'The Night Listener'1}
           'Gene Seymour'
{'Superman Returns'1'The Night Listener'1'You, Me and Dupree'1}}

А затем мы напишем функцию, которая вычисляет коэффициент сходства оценок двух критиков.

def tanimoto(critics_arr, critic1, critic2):
    arr = prepare_for_tanimoto(critics_arr)
 
    a = len(arr[critic1])
    b = len(arr[critic2])
    c = 0.0
 
    for film in arr[critic1]:
        if arr[critic1][film] == arr[critic2][film]:
            c = c + 1
 
    koef = c / (a + b - c)
    return koef


Проверим работоспособность функции tanimoto.

>>>print tanimoto(critics, 'Gene Seymour', 'Lisa Rose')
>>>0.5

По моему, результат верен. Надо заметить, что при увеличении количества оценок у каждого критика, увеличится и точность подсчета коэффициента сходства.

Если бы у нас была база данных оценок, можно было бы подсчитать коэффициенты сходства интересов людей и начинать давать рекомендации по методу Танимото.

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

Комментарии 22

    +17
    Я дико извиняюсь, но не проще ли посчитать Евклидово растояние в пространстве оценок? Это позволяет работать не с бинарными, а с числовыми оценками… степень похожести двух критиков исчисляется как:



    при этом если в каком-то компоненте вектора оценок c у них нет общих оценок (например, критик i оценил один фильм а критик j его не оценил) то это просто ноль. Можно попарно считать похожести, есть модные и мощные алгоритмы матричного расчета этого расстояния (искать по словам “Information Theory, Inference and Learning Algorithms”, pp. 284–292, David MacKay, Cambridge University Press, 2003.)
      +2
      Насколько я помню, в той книжке есть и этот метод — просто применяются для несколько разных вещей.
        +1
        Согласен, для таких исходных данных проще посчитать Евклидово расстояние. Я о чем то похожем написал в середине статьи:
        Поэтому коэффициент Танимото, на мой взгляд, стоит использовать, если количество вариантов оценок не больше 2-3 (например, «понравилось-не понравилось» или «рекомендую-не смотрел-не рекомендую»)

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

          а уж если, эксперты были прилежны и матрица полная, то намного лучше использовать не евклидово расстояние, а метрику Махаланобиса :)

          Даже если матрица дырявая я бы пробовал пробиваться в сторону PCA/Махаланобиса, ну а уж если матрица просто разряжённая, то тогда читаем вдумчиво эту статью и грустно бродим по ссылкам :)
            0
            Это требует вычисления covariance matrix, что влечет за собой дополнительные усложнения — а в простейшем случае диагональной единичной матрицы мы получаем все то же Евклидово растояние ;-)
              0
              разница между Махалонобисовской и Евклидовой метрикой может быть гиганской, в прикладном смысле особенно.
              вы можете быть удивлены что расстояние между женскими и мужскими интересами в Махаланобисовской метрике может оказаться огромным, в то время как в Евклидовой оно может быть довольно скромным ;)
                –3
                А нам разве так важен модуль разницы «интересов», или просто сам факт? Ведь всегда можно умножить на некий коефициент для получения нужной шкалы\масштаба.
          +5
          Какой смысл при расчете схожести интересов учитывать несовпадающие множества?

          Допустим, а = 1000, b = 100, c = 100 (то есть все 100 фильмов которые посмотрел b, также посмотрел и a, и также их оценил).
          По сути совпадение интересов = 100%. А по вашему коэффу = 100/(1000+100-100)=0.1, то есть совпадений якобы нет.
          Очевидно, что для данной цели алгоритм ошибочен.
            +3
            "-c" в знаменателе там явно лишнее, да и делается подобный расчет куда проще с помощью setов.

              critic_1 = set(['Film A', 'Film B'])
              critic_2 = set(['Film A'])
              print 1. * len(critic_1 & critic_2) / len(critic_1 & critic_2)
            

            "1." там для того, чтобы в float расчет шел.
              +3
              упс:
              print 1. * len(critic_1 & critic_2) / len(critic_1 | critic_2)

              там "|" должно быть в знаменателе
                +2
                да, все правильно, автор говорит про множества, а пользуется списками
              0
              Попробуйте применить метод на базе ru.wikipedia.org/wiki/Netflix_Prize — там есть база оценок, вполне можно попробовать и сравнить с результатами лучших алгоритмов.
              +4
              Я бы тупо посчитал корреляцию оценок по фильмам, оценённым обоими критиками.
              Особенности:
              • Симметричность (А похож на Б так же, как Б на А)
              • Устойчивость к константному смещению и множителю. Если я по душе очень критичен и в целом занижаю оценки даже хорошим вещам, а другой более лоялен и ставит всем на балл выше, мы всё равно коррелируем по вкусу.
              • Учёт антикорреляции. Если я оценил три фильма 1/3/5, а оппонент — 5/3/1, то корреляция скажет, что у нас абсолютно противоположные вкусы, а предложенный автором топика метод отметит сходство во втором фильме.
              • Не работает с теми, кто всем ставит одинаковые оценки (если подумать, это логично: такой критик вообще бесполезен).
              Пример:
                0
                Автор топика привёл лишь одну из методик, предложенных в упоминаемой им книге. В самой же книге есть способы определения того, действительно ли автор поставил «правильную» оценку или завысил/занизил. Для этого нужно больше данных и сравнений с другими пользователями, с целью получения более репрезентативной выборки.

                P.S. Смысла статьи не понял. Это простой «копипаст» из книги без какого-либо анализа предложенной методики и привнесения чего-то дополнительного. Наверное, достаточно было просто сказать, что есть такая замечательная книга, в которой описаны такие вот интересные методики для осуществления коллаборативной фильтрации данных.
                  0
                  Видимо у автора комментария какая-то другая версия книги. Никак не могу найти ту страницу в своей книге, которую я копипастил.
                    0
                    Прошу прощения, перепутал.
                0
                Не проще узнать величину разности общих элементов, деленную на их количество? Ну и потом нормализовать в зависимости от системы оценок.
                  0
                  думаю, в реальных применениях (типа имхонета) важна скорость. на сайт постоянно заходят сотни и тысячи человек, постоянно выставляют оценки (и, соответственно, если A и Б имели три дня назад общие оценки, сегодня один из них (А) посмотрел фильм, выставил оценку и она отличается от оценки другого (Б), так что теперь А и Б не похожи). Следовательно пересчитывать «похожесть» надо постоянно, а если у каждого из пользователей 500 оценок (вполне нормальное число для рейтинга фильмов), а пользователей у нас 10'000, то пересчитать схожесть по 500 позициями каждого с 10'000 других — слишком медленно должно быть.
                  +1
                  Pearson's r уже не катит?
                    0
                    Скромное мнение:
                    Самая большая проблема подобных расчётов — это шум. Чем проще алгоритм, тем менее он устойчив к шуму. То есть на мой взгляд и коэффициент Танимото и, любимое всеми комментаторами, Евклидово расстояние слишком прямолинейны.

                    Самый распространённый шум — отсутствие выбора. И отсутствие оценки фильма, и выбор значения по умолчанию. Это как дата рождения в формах регистрации — многие указывают только год или вообще не хотят ничего указывать и получается, что самая популярная дата дня рождения — первое января…
                      0
                      недавно давал подобную задачку своим студентам, решали через
                      коэффициент конкордации и коэффициенты парной ранговой корреляции

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

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