Slope One

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

Существует как минимум 2 класса коллаборативной фильтрации:
 фильтрация по схожести пользователей (), базирующаяся на измерении подобия пользователей;
 фильтрация по схожести предметов (), сравнивающая оценки, данные различными пользователями.

Slope One был представлен в статье Slope One Predictors for Online Rating-Based Collaborative Filtering Даниелем Лемайром () и Анной Маклахлан (). Утверждается, что это один из самых простых способов коллаборативной фильтрации по схожести предметов на основании оценок пользователей. Эта простота значительно облегчает внедрение данных алгоритмов, а их точность сравнима с точностью более сложных и ресурсоёмких алгоритмов. Slope One также часто дополняет другие алгоритмы..

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

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

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

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

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

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

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

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

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

,

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

,

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

.

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

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

Пример:
 Джо выставил оценку 1 для Селин Дион и 1.5 для Линдси Лохан.
 Джил оценила Селин Дион на 2 балла.
 Какую оценку выставит Джил для Линдсм Лохан?
 Ответ алгоритма Slope One: 2.5 (1.5-1+2=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 раза), итоговую оценку мы получим как взвешенное среднее. Для весовых коэффициентов будем использовать количество пользователей, давших оценку предмету:

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

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

Рекомендательные системы, использующие Slope One 

 hitflip - система рекомендаций DVD.
 Value Investing News - новостной сайт фондовых бирж.

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

Java:
 Taste: a java-based collaborative library with support for Enterprise Java Beans (code sample)
 класс Java, реализующий Slope One.
 The Cofi: A Java-Based Collaborative Filtering Library supports Slope One algorithms (documentation is so-so)

PHP:
 Библиотека Vogoo поддерживает алгоритмы Slope One
 Aspedia ECM API поддерживает алгоритмы  Slope One
 Исходный код на PHP к отчёту об использовании алгоритмов Slope One
 Модуль для Drupal CMS реализующий Slope One.
 OpenSlopeOne реализует алгоритмы Slope One на чистом PHP и MySQL.

Erlang:
 Philip Robinson реализовал Slope One на Erlang.

Haskell:
 Bryan O’Sullivan реализовал Slope One на Haskell.

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

C#:
 Kuber реализовал Weighted Slope One с C#.

T-SQL:
 Charlie Zhu реализовал Weighted Slope One на T-SQL.

Примечания 

Коллективный интеллект
Машинное обучение