Slope One

Slope One

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

\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). Таким образом, предиктор - это просто средняя разница между оценками обоих предметов. Авторы продемонстрировали, что такой подход в некоторых случаях более точный, чем линейная регрессия[1] и требует в 2 раза меньше памяти.

Simplicity diagram.png

Пример:

  1. Джо выставил оценку 1 для Селин Дион и 1.5 для Линдсей Лохан.
  2. Джил оценила Селин Дион на 2 балла.
  3. Какую оценку выставит Джил для Линдсей Лохан?
  4. Ответ алгоритма 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

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

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

Python:

Java:

PHP:

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

Erlang:

Haskell:

Visual Basic:

C#:

T-SQL:

Примечания

  1. 1 2 3 4 Daniel Lemire, Anna Maclachlan, Slope One Predictors for Online Rating-Based Collaborative Filtering, In SIAM Data Mining (SDM’05), Newport Beach, California, April 21-23, 2005. (англ.)
  2. Pu Wang, HongWu Ye, A Personalized Recommendation Algorithm Combining Slope One Scheme and User Based Collaborative Filtering, IIS '09, 2009. (англ.)
  3. DeJia Zhang, An Item-based Collaborative Filtering Recommendation Algorithm Using Slope One Scheme Smoothing, ISECS '09, 2009. (англ.)
  4. Slobodan Vucetic, Zoran Obradovic: Collaborative Filtering Using a Regression-Based Approach. Knowl. Inf. Syst. 7(1): 1-22 (2005) (англ.)
  5. Badrul M. Sarwar, George Karypis, Joseph A. Konstan, John Riedl: Item-based collaborative filtering recommendation algorithms. WWW 2001: 285—295 (англ.)
  6. U.S. Patent 6 266 649
  7. 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 (англ.)
  8. B.M. Sarwarm et al., "Analysis of Recommendation Algorithms for E-Commerce, " ACM Conf. Electronic Commerce, ACM Press, 2000, pp.158-167. (англ.)
  9. Daniel Lemire, Sean McGrath, Implementing a Rating-Based Item-to-Item Recommender System in PHP/SQL, Technical Report D-01, January 2005.

Wikimedia Foundation. 2010.

Смотреть что такое "Slope One" в других словарях:

  • Slope One — Collaborative filtering is a technique used by recommender systems to combine different users opinions and tastes in order to achieve personalized recommendations. There are at least two classes of collaborative filtering: user based techniques… …   Wikipedia

  • Slope One — Este artículo está huérfano, pues pocos o ningún artículo enlazan aquí. Por favor, introduce enlaces hacia esta página desde otros artículos relacionados …   Wikipedia Español

  • Slope — is used to describe the steepness, incline, gradient, or grade of a straight line. A higher slope value indicates a steeper incline. The slope is defined as the ratio of the rise divided by the run between two points on a line, or in other words …   Wikipedia

  • Slope Day — is an annual day of celebration held at Cornell University during the last day of regular undergraduate classes. It usually falls on the first Friday of May and the official site of Slope Day is the Libe Slope, on the university campus. Though… …   Wikipedia

  • Slope side — is a term used in the North American ski lodging industry to describe any accommodation from which one can reasonably walk to the ski lifts. Such lodgings are usually at the bottom of, or right beside, the ski hill hence the term slope side . Due …   Wikipedia

  • Slope — Slope, n. [Formed (like abode fr. abide) from OE. slipen. See {Slip}, v. i.] 1. An oblique direction; a line or direction including from a horizontal line or direction; also, sometimes, an inclination, as of one line or surface to another. [1913… …   The Collaborative International Dictionary of English

  • Slope of a plane — Slope Slope, n. [Formed (like abode fr. abide) from OE. slipen. See {Slip}, v. i.] 1. An oblique direction; a line or direction including from a horizontal line or direction; also, sometimes, an inclination, as of one line or surface to another.… …   The Collaborative International Dictionary of English

  • slope — ► NOUN 1) a surface of which one end or side is at a higher level than another. 2) a part of the side of a hill or mountain, especially as a place for skiing. ► VERB 1) be inclined from a horizontal or vertical line; slant up or down. 2) informal …   English terms dictionary

  • One Hundred Famous Views of Edo — The Plum Garden in Kameido Artist Hiroshige Year 1856–58 Type ukiyo e One Hundred Famous Views of Edo (in Japanese 名所江戸百景 Meisho Edo Hyakkei ) is a series of …   Wikipedia

  • slope — [[t]slo͟ʊp[/t]] slopes, sloping, sloped 1) N COUNT: usu with supp A slope is the side of a mountain, hill, or valley. Saint Christo is perched on a mountain slope. ...the lower slopes of the Himalayas. 2) N COUNT: usu sing A slope is a surface… …   English dictionary

Книги

Другие книги по запросу «Slope One» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»