Форум АНТИЧАТ - Пишем свою систему рекоммендаций

Пишем свою систему рекомендаций

Примечание: в статье приводится код на языке python, однако он будет понятен человеку, владеющему любым другим языком программирования, ввиду простоты и краткости листингов.

Intro
Сбор информации
Подбор похожих пользователей
__Евклидово расстояние
__Коэффициент корреляции Пирсона
Сортировка похожих пользователей
Рекомендация предметов
Outro
Приложение

Intro

Многие из вас пользуются или слышали о таких ресурсах, как last.fm, amazon.com, ozon.ru, afisha.ru, digg.com, habrahabr.ru. Что же их объединяет? Они все обладают собственной системой рекомендаций, используя которую, могут советовать вам купить тот или иной товар, прочитать статью или посмотреть фильм.

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

Сбор информации

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

Код:

# Вложенный словарь, содержащий данные об оценках пользователей ряда статей

Data = {

        'User1' : 

            { 'Article1' : 3.0, 'Article2' : 2.5, 'Article3' : 4.0, 'Article4' : 2.5, 'Article5' : 3.5 },

        'User2' :

            { 'Article1' : 1.5, 'Article2' : 3.0, 'Article3' : 5.0, 'Article4' : 2.5, 'Article5' : 2.5 },

        'User3' :

            { 'Article1' : 2.5, 'Article2' : 3.0, 'Article4' : 4.5, 'Article5' : 2.0 },

        'User4' :

            { 'Article2' : 3.5, 'Article3' : 2.0, 'Article4' : 4.0, 'Article5' : 3.0 },

        'User5' :

            { 'Article1' : 3.0, 'Article2' : 4.0 },

        'User6' :

            { 'Article1' : 2.0, 'Article2' : 2.5, 'Article4' : 4.0, 'Article5' : 4.5 }

        }

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

Пример работы кода
Помещаем файл с кодом (recommendation.py) в папку с интерпретатором Python.
>>> from recommendation import Data
>>> Data['User1']
{'Article1' : 3, 'Article2' : 2.5, 'Article3' : 4.0, 'Article4' : 2.5, 'Article5' : 3.5}
>>> Data['User2']['Article3']
5.0

Примечание: в реальных проектах, конечно, выгоднее и удобнее использовать базу данных, нежели чем обычный словарь.
Разумеется, возможно использования не только данных оценок, но и других вариантов. Например, на amazon.ru вы можете наблюдать систему, которая подбирает рекомендации исходя из системы купил/не купил (1/0).

Подбор похожих пользователей

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

Евклидово расстояние

Простейший из способов отыскания похожих пользователей - это евклидово расстояние. Представим себе статьи (или любые другие предметы, которые оценивали пользователи) в виде координатных осей. Простейший случай - в декартовой системе координат.

http://img7.imageshost.ru/imgs/09080...3382/fbb8a.jpg

Все очень наглядно - чем ближе точки, тем более схожи вкусы пользователей, которые им соответствуют. Как известно из курса 7 класса многим из вас, чтобы найти расстояние между двумя точками на данной плоскости нужно возвести в квадрат разности соответствующих координат этих точек, а затем сложить и извлечь квадратный корень из суммы. Напишем простейшую функцию, вычисляющую коэффициент подобия между двумя пользователями.

Код:

import math

# Функция возвращает коэффициент подобия по евклидовому расстоянию между Person1 и Person2, используя словарь с данными об оценках 

def Similarity ( Data, Person1, Person2 ):

    # Генерируем список оцененных обоими пользователями статей

    Both_Marked = [ item for item in Data[Person1] if item in Data[Person2] ]

    # Если отмеченных обоими пользвателями статей не найдено, возвращаем 0

    if len ( Both_Marked ) == 0: return 0 

    # Чем больше похожи пользователи, тем больше полученное от функции число ( оно лежит в диапазоне от 0 до 1 )

    return 1 / ( 1 + math.sqrt ( sum ( [ (Data[Person1][item] - Data[Person2][item]) ** 2 for item in Both_Marked ] ) ) )

Пример работы кода
>>> import recommendation
>>> recommendation.Similarity ( recommendation.Data, 'User2', 'User3' )
0.30383243470068705

Коэффициент корреляции Пирсона

Немного более сложный способ определения степени схожести предпочтений пользователей дает нам коэффициент корреляции Пирсона. Коэффициент корреляции - мера того, насколько хорошо два набора данных ложатся на прямую. Алгоритм менее очевиден, однако во многих случаях показывает более удачные результаты. В данном случае в роли координатных осей выступают уже пользователи, а статьи или любые другие предметы отмечаются точками с соответствующими их оценкам координатами.

http://img7.imageshost.ru/imgs/09080...0ac8/28528.jpg

На рисунке мы видим прямую линию, она называется линией наилучшего приближения, потому что проходит настолько близко ко всем точкам, насколько это только возможно. При полном совпадении интересов пользователей, она прошла бы через все точки и начало координат. Коэффициент корреляции в таком случае был бы равен 1. Основным преимуществом коэффициента Пирсона над евклидовым расстоянием является то, что даже если один пользователь из двух постоянно выставляет оценки ниже другого, однако разница в оценках постоянна, коэффициент корреляции будет достаточно высок, так как их интересы все же схожи. Евклидово расстояние в данном случае показало бы нам абсолютно другой результат. Напишем функцию вычисления коэффициента Пирсона.

Код:

# Функция возвращает коэффициент Пирсона между Person1 и Person2

def Similarity_Pearson ( Data, Person1, Person2 ):

    # Генерируем список оцененных обоими пользователями статей

    Both_Marked = [ item for item in Data[Person1] if item in Data[Person2] ]

    # Количество статей, оцененных обоими

    count = len ( Both_Marked )

    # Если общих статей нет, возвращаем 0

    if not count: return 0

    

    # Далее следует алгоритм, он не столь интересен, чтобы его комментировать :)

    Sum1 = sum ( [ Data[Person1][item] for item in Both_Marked ] )

    Sum2 = sum ( [ Data[Person2][item] for item in Both_Marked ] )

    Sum1_sqr = sum ( [ Data[Person1][item] ** 2 for item in Both_Marked ] )

    Sum2_sqr = sum ( [ Data[Person2][item] ** 2 for item in Both_Marked ] )

    Sum = sum ( [ Data[Person1][item] * Data[Person2][item] for item in Both_Marked ] )

    

    N = Sum - ( Sum1 * Sum2 ) / count

    D = math.sqrt ( ( Sum1_sqr - ( Sum1 ** 2 ) / count ) * ( Sum2_sqr - ( Sum2 ** 2 ) / count ) )

    

    if D == 0: return 0

    else:

        # Аналогично, чем больше схожесть пользователей, тем больше число, полученное от функции ( оно лежит в диапазоне от 0 до 1 )

        return ( N / D + 1 ) / 2

Пример работы кода
>>> import recommendation
>>> recommendation.Similarity_Pearson ( recommendation.Data, 'User1', 'User2' )
0.8037120361098036

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

Сортировка похожих пользователей

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

Код:

# Функция возвращает список наиболее подходящих к данному пользователей

def Top_Similarity ( Data, Person, Count = 3, Function = Similarity_Pearson ):

    # Генерируем список, содержащий коэффициенты подобия и пользователей, соответствующих им

    Result = [ ( Function ( Data, Person, Other ), Other ) for Other in Data if Other != Person ]

    # Сортируем в удобном для нас виде

    # Это можно оформить ввиде функции, так как повторяется дважды в идентичном виде, однако для наглядности оставлено так  ( Get_Result - см ниже )

    # Get_Result ( Result, Count )

    Result = sorted ( Result, reverse = True )

    tmp = []

    # Возвращаем первые несколько записей наиболее подходящих пользователей ( количество выводимых записей задано Count )

    for _ in range ( 0, Count ):

        tmp.append ( Result[_][1] )

    return tmp

Пример работы кода
>>> import recommendation
>>> recommendation.Top_Similarity ( recommendation.Data, 'User1', 2 )
['User2', 'User6']
>>> recommendation.Top_Similarity ( recommendation.Data, 'User2' )
['User5', 'User1', 'User6']

Рекомендация предметов

Найти похожего пользователя, как вы надеюсь догадываетесь, это всего лишь половина дела. Главное для нас - научиться рекомендовать некий предмет на основе предпочтений похожих пользователей. Проще всего было бы, конечно, просто посоветовать те предметы, которые понравились понравились схожему пользователю, однако этот путь приводит к проблемам. Что если этот предмет, так понравившийся схожему пользователю, не понравился всем остальным, или же предмет, который мог бы ему понравится, не был оценен похожим пользователем? Избежать этих проблем поможет нам ранжирование предметов и сумма оценок пользователей. Нам нужна некая взвешенная сумма оценок всех пользователей, и в то же время нам нужно, чтобы похожий пользователь вносил больший вклад в общую оценку, нежели чем непохожий. Берем каждого пользователя и умножаем его оценку на коэффициент подобия с данным, а затем суммируем полученные числа. Чтобы уравнять шансы предметов, которые оценило разное количество пользователей (надеюсь вы понимаете, что сумма в случае когда оценок было больше, будет почти всегда выше), мы делим полученное число на сумму коэффициентов подобия пользователей, оценивших предмет.

Код:

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

def Get_Recommendation ( Data, Person, Count = 1, Function = Similarity_Pearson ):

    # Здесь будут хранится данные о сумме произведений коэффициентов подобия и оценок для определенной статьи

    Total = {}

    # А здесь сумма коэфициентов для определенной статьи

    Sum = {}

    # Для каждого пользователя

    for Other in Data:

        # Кроме заданного 

        if Other == Person: continue

        # Берем статью

        for item in Data[Other]:

            # И, если статья не была оценена заданным пользователем

            if item not in Data[Person] or Data[Person][item] == 0:

                # Создаем в словарях ключи, определяющие статью, со значение 0, если их еще нет

                Total.setdefault ( item, 0 )

                Sum.setdefault ( item, 0 )

                # Вычисляем нужные нам данные

                Total[item] += Data[Other][item] * Function ( Data, Person, Other )

                Sum[item] += Function ( Data, Person, Other )

    # Получаем список со статьями и соответствующими им вычисленными по алгоритму взвешенными оценками

    Result = [ ( value / Sum[item], item ) for item, value in Total.items () ]

    # Сортируем в удобном для нас виде

    # Это можно оформить ввиде функции, так как повторяется дважды в идентичном виде, однако для наглядности оставлено так ( Get_Result - см ниже )

    # Get_Result ( Result, Count )

    Result = sorted ( Result, reverse = True )

    tmp = []

    # Возвращаем первые несколько записей наиболее подходящих статей ( количество выводимых записей задано Count ) 

    for _ in range ( 0, Count ):

        tmp.append ( Result[_][1] )

    return tmp

Пример работы кода
>>> import recommendation
>>> recommendation.Get_Recommendation ( recommendation.Data, 'User5' )
['Article3']

Мы построили полную систему рекомендования предметов :)

Outro

Хочу заметить, что мы создали систему рекомендаций таким образом, что для ее работы нам понадобятся оценки, выставленные каждым пользователем. Для небольшого количества пользователей и предметов это, несомненно, будет работать, однако при большом количестве данных сравнение пользователя со всеми, вычисление коэффициентов подобия и ранжирование предметов займет недопустимо много времени. Более того при большом количестве предметов перекрытие вкусов станет столь мало, что сложно будет определить похожих пользователей. В данном случае нам поможет процедура фильтрации по схожести образцов. Главная ее идея заключается в том, что изначально для каждого предмета создается список похожих на него. Тогда для выработки рекомендаций, нам остается только отобрать предметы, которые пользователь оценил максимально высоко, и отобрать для них ряд похожих. Кроме того, пользоваться этим набором похожих элементов можно долгое время не меняя его.
Экспериментируя, вы сможете подобрать методику, наиболее всего подходящую для вашего ресурса. Удачи (:

Приложение

Код:

def Get_Result ( Result, Count ):

   Result = sorted ( Result, reverse = True )

   tmp = []

   for _ in range ( 0, Count ):

       tmp.append ( Result[_][1] )

   return tmp

Скачать архив с файлами, содержащими примеры работы кода и сам код, вы можете по этим ссылкам:
Например здесь
Или здесь

(c) fata1ex 25 июля 2009 года
Копирование материала статьи только с разрешения автора.

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