Склон один - Slope One - Wikipedia

Склон один семейство алгоритмов, используемых для совместная фильтрация, представленный в статье Даниэля Лемира и Анны Маклахлан в 2005 году.^[1] Возможно, это простейшая форма нетривиального совместная фильтрация на основе элементов на основе рейтингов. Их простота позволяет легко реализовать их эффективно, в то время как их точность часто не уступает более сложным и дорогостоящим в вычислительном отношении алгоритмам.^[1][2] Они также использовались как строительные блоки для улучшения других алгоритмов.^{[3][4][5][6][7][8][9]} Они являются частью основных библиотек с открытым исходным кодом, таких как Apache Mahout и Easyrec.

Совместная фильтрация оцененных ресурсов и переобучения на основе элементов

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

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

В этом контексте совместная фильтрация на основе элементов ^[10][11] прогнозирует оценки по одному элементу на основе оценок по другому элементу, обычно используя линейная регрессия (${\displaystyle f(x)=ax+b}$). Следовательно, если имеется 1000 элементов, можно изучить до 1 000 000 линейных регрессий, а значит, до 2 000 000 регрессоров. Этот подход может иметь серьезные переоснащение^[1] если мы не выберем только пары элементов, для которых несколько пользователей оценили оба элемента.

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

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

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

Нам не всегда выставляют оценки: когда пользователи предоставляют только двоичные данные (товар был куплен или нет), то Slope One и другой алгоритм, основанный на рейтинге, не применяются^{[нужна цитата ]}. Примеры совместной фильтрации на основе бинарных элементов включают Amazon от предмета к предмету запатентованный алгоритм^[12] который вычисляет косинус между двоичными векторами, представляющими покупки в матрице пользовательских товаров.

Алгоритм Item-to-Item, который, возможно, проще, чем даже Slope One, предлагает интересную точку отсчета. Рассмотрим пример.

Пример статистики покупок

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

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

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

Косинус между пунктами 1 и 3 равен:

${\displaystyle {\frac {(1,0,0)\cdot (1,1,0)}{\Vert (1,0,0)\Vert \Vert (1,1,0)\Vert }}={\frac {1}{\sqrt {2}}}}$,

В то время как косинус между пунктами 2 и 3 равен:

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

Следовательно, пользователь, посещающий элемент 1, получит элемент 3 как рекомендацию, пользователь, посещающий элемент 2, получит элемент 3 как рекомендацию, и, наконец, пользователь, посещающий элемент 3, получит элемент 1 (а затем элемент 2) в качестве рекомендации. Модель использует один параметр для каждой пары элементов (косинус), чтобы сделать рекомендацию. Следовательно, если есть п предметы, до п (п-1) / 2 косинусы необходимо вычислить и сохранить.

Наклонная одна совместная фильтрация для оцененных ресурсов

Чтобы резко сократить переоснащение, повысить производительность и упростить внедрение, Склон один семейство легко реализуемых предметов на основе рейтинга совместная фильтрация предложены алгоритмы. По сути, вместо использования линейной регрессии от оценок одного элемента к рейтингам другого элемента (${\displaystyle f(x)=ax+b}$), он использует более простую форму регрессии с одним свободным параметром (${\displaystyle f(x)=x+b}$). Свободный параметр - это просто средняя разница между рейтингами двух элементов. Было показано, что в некоторых случаях она намного точнее линейной регрессии,^[1] и занимает половину памяти или меньше.

Пример:

1. Пользователь A поставил 1 баллу I и 1,5 баллу J.
2. Пользователь B поставил 2 баллу I.
3. Как вы думаете, как пользователь B оценил элемент J?
4. Ответ на наклон 1 - 2,5 (1,5–1 + 2 = 2,5).

Для более реалистичного примера рассмотрим следующую таблицу.

Образец рейтинговой базы данных

Покупатель	Пункт А	Пункт B	Пункт C
Джон	5	3	2
отметка	3	4	Не оценил
Люси	Не оценил	2	5

В этом случае средняя разница в рейтингах между пунктом B и A составляет (2 + (- 1)) / 2 = 0,5. Следовательно, в среднем элемент A имеет рейтинг выше элемента B на 0,5. Точно так же средняя разница между заданием C и A составляет 3. Следовательно, если мы попытаемся предсказать рейтинг Люси по пункту A, используя ее рейтинг по пункту B, мы получим 2 + 0,5 = 2,5. Точно так же, если мы попытаемся предсказать ее рейтинг по пункту A, используя ее рейтинг по пункту C, мы получим 5 + 3 = 8.

Если пользователь оценил несколько элементов, прогнозы просто объединяются с использованием средневзвешенного значения, где хорошим выбором веса является количество пользователей, оценивавших оба элемента. В приведенном выше примере Джон и Марк оценили элементы A и B, следовательно, вес 2, и только Джон оценил оба элемента A и C, следовательно, вес 1, как показано ниже. мы бы прогнозировали следующую оценку Люси по пункту А как:

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

Следовательно, учитывая п элементов, чтобы реализовать Slope One, все, что необходимо, - это вычислить и сохранить средние различия и количество общих оценок для каждого из п² пары предметов.

Алгоритмическая сложность Slope One

Предположим, есть п Предметы, м пользователи и N рейтинги. Для вычисления средней разницы рейтингов для каждой пары элементов требуется до п (п-1) / 2 единиц хранения, и до m n² временные шаги. Эта расчетная оценка может быть пессимистичной: если мы предположим, что пользователи оценили до у элементов, то можно вычислить различия не более чем в п²+мой². Если пользователь вошел Икс рейтинги, для прогнозирования одного рейтинга требуется Икс шагов по времени, и для прогнозирования всех его недостающих оценок требуется до (п-х)Икс временные шаги. Обновление базы данных, когда пользователь уже вошел Икс рейтинги, и входит в новый, требует Икс временные шаги.

Можно уменьшить требования к хранилищу, разделив данные (см. Раздел (база данных) ) или с использованием разреженного хранилища: пары элементов, у которых нет (или несколько) пользователей, занимающихся сортировкой, могут быть опущены.

Сноски

1. Даниэль Лемир, Анна Маклахлан, Предикторы первого порядка для совместной фильтрации на основе рейтингов в Интернете, В SIAM Data Mining (SDM'05), Ньюпорт-Бич, Калифорния, 21–23 апреля 2005 г.
2. Фидель Качеда, Виктор Карнейро, Диего Фернандес и Врейксо Формозо. 2011 г. Сравнение алгоритмов совместной фильтрации: ограничения текущих методов и предложений для масштабируемых, высокопроизводительных рекомендательных систем. ACM Trans. Веб 5, 1, статья 2
3. Пу Ван, Хун У Е, Алгоритм персонализированных рекомендаций, сочетающий схему Slope One и совместную фильтрацию на основе пользователей, IIS '09, 2009.
4. ДеЦзя Чжан, Алгоритм рекомендаций совместной фильтрации на основе элементов, использующий сглаживание схемы первого наклона, ISECS '09, 2009.
5. Мин Гаоа, Чжунфу Вуб и Фэн Цзян, Userrank за рекомендацию по совместной фильтрации на основе элементов, Письма об обработке информации, том 111, выпуск 9, 1 апреля 2011 г., стр. 440-446.
6. Ми, Чжэньчжэнь и Сюй, Цунфу, Рекомендуемый алгоритм, сочетающий метод кластеризации и схему первого наклона, конспект лекций по информатике 6840, 2012, стр. 160-167.
7. Данило Менезес, Анисио Ласерда, Лейла Сильва, Адриано Велозо и Нивио Зивиани. 2013. Пересмотр взвешенных предикторов наклона 1. В материалах 22-й международной конференции по компаньону World Wide Web (WWW '13 Companion). Руководящий комитет международных конференций по всемирной паутине, Республика и кантон Женева, Швейцария, 967-972.
8. Сунь, З., Луо, Н., Куанг, В., Одна система персонализированных рекомендаций в реальном времени на основе алгоритма Slope One, FSKD 2011, 3, ст. нет. 6019830, 2012, с. 1826-1830.
9. Гао М., Ву З., Персонализированная контекстно-зависимая совместная фильтрация на основе нейронной сети и первого наклона, LNCS 5738, 2009, стр. 109-116.
10. Слободан Вучетич, Зоран Обрадович: Совместная фильтрация с использованием подхода, основанного на регрессии. Знай. Инф. Syst. 7 (1): 1-22 (2005).
11. Бадрул М. Сарвар, Джордж Карипис, Джозеф А. Констан, Джон Ридл: алгоритмы рекомендаций совместной фильтрации на основе элементов. WWW 2001: 285-295
12. Грег Линден, Брент Смит, Джереми Йорк, «Рекомендации Amazon.com: совместная фильтрация элементов данных», IEEE Internet Computing, vol. 07, нет. 1, стр. 76-80, январь / февраль 2003 г.