Interested Article - Slope One

Slope One — семейство алгоритмов для коллаборативной фильтрации (используемой в рекомендательных системах ) для анализа различных мнений и пожеланий пользователей и выработки персональных рекомендаций.

Существует как минимум 2 класса коллаборативной фильтрации:

фильтрация по схожести пользователей ( англ. user-based filtration ), базирующаяся на измерении подобия пользователей;
фильтрация по схожести предметов ( англ. item-based filtration ), сравнивающая оценки, данные различными пользователями.

Slope One был представлен в статье Даниелем Лемайром ( англ. Daniel Lemire ) и Анной Маклахлан ( англ. Anna Maclachlan ). Утверждается, что это один из самых простых способов коллаборативной фильтрации по схожести предметов на основании оценок пользователей. Эта простота значительно облегчает внедрение данных алгоритмов, а их точность сравнима с точностью более сложных и ресурсоёмких алгоритмов . Slope One также часто дополняет другие алгоритмы. .

Фильтрация по схожести предметов и переобучение

Если доступны оценки предмета - к примеру, пользователям дана возможность проголосовать за предмет (например, выставить оценку от 1 до 5), - то коллаборативная фильтрация пытается предсказать оценку, которую даст пользователь новому предмету на основании его предыдущих оценок и базы данных оценок других пользователей.

Пример : Можем ли мы предсказать оценку конкретного пользователя на новый альбом Селин Дион , если мы знаем, что он оценил The Beatles на 5 баллов?

В этом случае коллаборативная фильтрация по схожести предметов предсказывает оценку предмета на основе оценок другого предмета, используя чаще всего регрессионный анализ ( $f(x)=ax+b$ ). Следовательно, если имеется 1000 предметов, то может быть до 1000000 линейных регрессий для изучения и до 2000000 регрессоров. Такой подход может быть неэффективным из-за переобучения , поэтому необходимо выбирать пары предметов, для которых известны оценки нескольких пользователей.

Лучшей альтернативой может быть использование упрощённого предиктора (например, $f(x)=x+b$ ): экспериментально показано, что использование такого простого предиктора (называемого Slope One) иногда превосходит регрессионный анализ, при этом имея в два раза меньше регрессоров. К тому же у этого способа низкие требования к памяти и большая скорость.

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

Коллаборативная фильтрация по предметам на основании статистики покупок

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

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

{\mbox{similarity}}({\vec {A}},{\vec {B}})=\cos({\vec {A}},{\vec {B}})={\frac {{\vec {A}}\cdot {\vec {B}}}{\Vert {\vec {A}}\Vert *\Vert {\vec {B}}\Vert }}

Этот алгоритм, возможно, даже проще чем Slope One. Рассмотрим его работу на примере:

Статистика покупок
Покупатель	Предмет 1	Предмет 2	Предмет 3
Джон	Купил	Не покупал	Купил
Марк	Не покупал	Купил	Купил
Люси	Не покупала	Купила	Не покупала

В этом случае косинус между «Предмет 1» и «Предмет 2» рассчитывается так:

${\frac {(1,0,0)\cdot (0,1,1)}{\Vert (1,0,0)\Vert *\Vert (0,1,1)\Vert }}=0$ ,

между «Предмет 1» и «Предмет 3»:

${\frac {(1,0,0)\cdot (1,1,0)}{\Vert (1,0,0)\Vert *\Vert (1,1,0)\Vert }}={\frac {1}{\sqrt {2}}}\approx 0.71$ ,

и между «Предмет 2» и «Предмет 3»:

${\frac {(0,1,1)\cdot (1,1,0)}{\Vert (0,1,1)\Vert *\Vert (1,1,0)\Vert }}={\frac {1}{2}}=0.5$ .

Таким образом, пользователь, находящийся на странице описания «Предмета 1», получит «Предмет 3» в качестве рекомендации; на странице «Предмета 2» — «Предмет 3» и на странице «Предмета 3» — «Предмет 1» (и затем «Предмет 2»). В данном алгоритме используется один коэффициент на каждую пару предметов (косинус), на основании которого и создаются рекомендации. То есть для n предметов потребуется рассчитать и сохранить n(n-1)/2 косинусов.

Коллаборативная фильтрация Slope One для предметов с оценками

Для существенного уменьшения эффекта переобучения, увеличения производительности и облегчения внедрения было предложено семейство алгоритмов Slope One . Основное отличие от регрессионного анализа отношения рейтингов двух предметов ( $f(x)=ax+b$ ) состоит в использовании упрощённой формы регрессии всего с одним предиктором ( $f(x)=x+b$ ). Таким образом, предиктор - это просто средняя разница между оценками обоих предметов. Авторы продемонстрировали, что такой подход в некоторых случаях более точный, чем линейная регрессия и требует в 2 раза меньше памяти.

Пример :

Джо выставил оценку 1 для Селин Дион и 1.5 для Линдси Лохан .
Джил оценила Селин Дион на 2 балла.
Какую оценку выставит Джил для Линдсм Лохан?
Ответ алгоритма Slope One: 2.5 (1.5-1+2=2.5).

Рассмотрим более сложный пример:

Таблица оценок
Посетитель	Предмет 1	Предмет 2	Предмет 3
Джон	5	3	2
Марк	3	4	-
Люси	-	2	5

Согласно этой таблице, средняя разница в оценках предмета 1 и 2 равна (2+(-1))/2=0.5. Таким образом, в среднем предмет 1 оценивается на 0.5 балла выше, чем предмет 2. Аналогично и для предметов 3 и 1: средняя разница в оценках 3.

Если сейчас мы попробуем предсказать оценку Люси для предмета 1, используя её оценку для предмета 2, мы получим 2+0.5 = 2.5. Аналогично предсказываем её оценку для предмета 1, используя оценку, данную предмету 3: 5+3=8. Поскольку у нас есть несколько предполагаемых оценок (Люси голосовала 2 раза), итоговую оценку мы получим как взвешенное среднее. Для весовых коэффициентов будем использовать количество пользователей, давших оценку предмету:

${\frac {2\times 2.5+1\times 8}{2+1}}={\frac {13}{3}}=4.33$

Чтобы применить алгоритм Slope One для заданных n предметов, надо рассчитать и сохранить среднюю разницу и количество голосов для каждой из n ² пар предметов.

Оценка сложности алгоритма

Программное обеспечение с открытым исходным кодом, использующее Slope One

Python :

по реализации Slope One на Python.

Java :

: a java-based collaborative library with support for Enterprise Java Beans ( )
, реализующий Slope One.
The supports Slope One algorithms (documentation is so-so)

PHP :

Библиотека поддерживает алгоритмы Slope One
поддерживает алгоритмы Slope One
к отчёту об использовании алгоритмов Slope One
для Drupal CMS реализующий Slope One.
реализует алгоритмы Slope One на чистом PHP и MySQL.

Erlang :

Philip Robinson на Erlang.

Haskell :

Bryan O’Sullivan на Haskell.

Visual Basic :

(недоступная ссылка) Microsoft Excel реализующая Slope One при помощи VBA (требуется включить макросы).

C# :

Kuber с C#.

T-SQL :

Charlie Zhu на T-SQL.

Примечания

↑ Daniel Lemire, Anna Maclachlan, от 30 марта 2010 на Wayback Machine , In SIAM Data Mining (SDM’05), Newport Beach, California, April 21-23, 2005. (англ.)
Pu Wang, HongWu Ye, , IIS '09, 2009. (англ.)
DeJia Zhang, , ISECS '09, 2009. (англ.)
Slobodan Vucetic, Zoran Obradovic: Collaborative Filtering Using a Regression-Based Approach. Knowl. Inf. Syst. 7(1): 1-22 (2005) (англ.)
Badrul M. Sarwar, George Karypis, Joseph A. Konstan, John Riedl: Item-based collaborative filtering recommendation algorithms. WWW 2001: 285—295 (англ.)
(недоступная ссылка с 16-01-2015 [3288 дней])
Greg Linden, Brent Smith, Jeremy York, "Amazon.com Recommendations: Item-to-Item Collaborative Filtering, " IEEE Internet Computing, vol. 07, no. 1, pp. 76-80, Jan/Feb, 2003 (англ.)
B.M. Sarwarm et al., "Analysis of Recommendation Algorithms for E-Commerce, " ACM Conf. Electronic Commerce, ACM Press, 2000, pp.158-167. (англ.)
Daniel Lemire, Sean McGrath, 11 февраля 2010 года. , Technical Report D-01, January 2005.