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


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



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



Intro

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

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


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

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

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

Пример работы кода
Помещаем файл с кодом (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).


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

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


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

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



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

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


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

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



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


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

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


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

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

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


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

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

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

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


Outro

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


Приложение

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



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


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