Slope One
Slope One — семейство алгоритмов для коллаборативной фильтрации (используемой в рекомендательных системах) для анализа различных мнений и пожеланий пользователей и выработки персональных рекомендаций.
Существует как минимум 2 класса коллаборативной фильтрации:
- фильтрация по схожести пользователей (англ. user-based filtration), базирующаяся на измерении подобия пользователей;
- фильтрация по схожести предметов (англ. item-based filtration), сравнивающая оценки, данные различными пользователями.
Slope One был представлен в статье [www.daniel-lemire.com/fr/abstracts/SDM2005.html Slope One Predictors for Online Rating-Based Collaborative Filtering] Даниелем Лемайром (англ. Daniel Lemire) и Анной Маклахлан (англ. Anna Maclachlan). Утверждается, что это один из самых простых способов коллаборативной фильтрации по схожести предметов на основании оценок пользователей. Эта простота значительно облегчает внедрение данных алгоритмов, а их точность сравнима с точностью более сложных и ресурсоёмких алгоритмов[1]. Slope One также часто дополняет другие алгоритмы.[2][3].
Содержание
- 1 Фильтрация по схожести предметов и переобучение
- 2 Коллаборативная фильтрация по предметам на основании статистики покупок
- 3 Коллаборативная фильтрация Slope One для предметов с оценками
- 4 Оценка сложности алгоритма
- 5 Рекомендательные системы, использующие Slope One
- 6 Программное обеспечение с открытым исходным кодом, использующее Slope One
- 7 Примечания
Фильтрация по схожести предметов и переобучение
Если доступны оценки предмета, к примеру, пользователям дана возможность проголосовать за предмет (например, выставить оценку от 1 до 5), то коллаборативная фильтрация пытается предсказать оценку, которую даст пользователь новому предмету на основании его предыдущих оценок и базы данных оценок других пользователей.
Пример: Можем ли мы предсказать оценку конкретного пользователя на новый альбом Селин Дион, если мы знаем, что он оценил The Beatles на 5 баллов?
В этом случае коллаборативная фильтрация по схожести предметов[4][5] предсказывает оценку предмета на основе оценок другого предмета, используя чаще всего регрессионный анализ (<math>f(x)=ax+b</math>). Следовательно, если имеется 1000 предметов, то может быть до 1000000 линейных регрессий для изучения и до 2000000 регрессоров. Такой подход может быть неэффективным из-за переобучения[1], поэтому необходимо выбирать пары предметов, для которых известны оценки нескольких пользователей.
Лучшей альтернативой может быть использование упрощённого предиктора (например, <math>f(x)=x+b</math>): экспериментально показано, что использование такого простого предиктора (называемого Slope One) иногда превосходит[1] регрессионный анализ, при этом имея в два раза меньше регрессоров. К тому же у этого способа низкие требования к памяти и большая скорость.
Коллаборативная фильтрация по схожести предметов — это только один вид коллаборативной фильтрации. В случае использования коллаборативной фильтрации по схожести пользователей, анализируются отношения между пользователями, выясняется подобие их интересов. Но фильтрация по схожести предметов менее ресурсоёмка и имеет бо́льшую эффективность при наличии большого числа пользователей.
Коллаборативная фильтрация по предметам на основании статистики покупок
Далеко не всегда у пользователей есть возможность выставлять оценки предметам. То есть для коллаборативной фильтрации могут быть доступны всего лишь двоичные данные (покупал пользователь предмет или нет). В таких случаях Slope One и другие алгоритмы, зависящие от оценок предметов, неэффективны.
Примером алгоритма коллаборативной фильтрации по предметам, работающего с двоичными данными, является запатентованный[6] алгоритм [doi.ieeecomputersociety.org/10.1109/MIC.2003.1167344 Item-to-Item] использующийся в онлайн-магазине Amazon[7]. Этот алгоритм рассчитывает подобие предметов как косинус между векторами покупок в матрице пользователей и предметов[8]:
- <math>\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 }</math>
Этот алгоритм, возможно, даже проще чем Slope One. Рассмотрим его работу на примере:
| Покупатель | Предмет 1 | Предмет 2 | Предмет 3 |
|---|---|---|---|
| Джон | Купил | Не покупал | Купил |
| Марк | Не покупал | Купил | Купил |
| Люси | Не покупала | Купила | Не покупала |
В этом случае косинус между «Предмет 1» и «Предмет 2» рассчитывается так:
<math>\frac{(1,0,0)\cdot (0,1,1) }{ \Vert (1,0,0)\Vert * \Vert (0,1,1)\Vert }= 0</math>,
между «Предмет 1» и «Предмет 3»:
<math>\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 </math>,
и между «Предмет 2» и «Предмет 3»:
<math>\frac{(0,1,1)\cdot (1,1,0)}{ \Vert (0,1,1)\Vert * \Vert (1,1,0)\Vert }= \frac{1}{2} = 0.5 </math>.
Таким образом, пользователь, находящийся на странице описания «Предмета 1», получит «Предмет 3» в качестве рекомендации; на странице «Предмета 2» — «Предмет 3» и на странице «Предмета 3» — «Предмет 1» (и затем «Предмет 2»). В данном алгоритме используется один коэффициент на каждую пару предметов (косинус), на основании которого и создаются рекомендации. То есть для n предметов потребуется рассчитать и сохранить n(n-1)/2 косинусов.
Коллаборативная фильтрация Slope One для предметов с оценками
Для существенного уменьшения эффекта переобучения, увеличения производительности и облегчения внедрения было предложено семейство алгоритмов Slope One. Основное отличие от регрессионного анализа отношения рейтингов двух предметов (<math>f(x)=ax+b</math>) состоит в использовании упрощённой формы регрессии всего с одним предиктором (<math>f(x)=x+b</math>). Таким образом, предиктор - это просто средняя разница между оценками обоих предметов. Авторы продемонстрировали, что такой подход в некоторых случаях более точный, чем линейная регрессия[1] и требует в 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 раза), итоговую оценку мы получим как взвешенное среднее. Для весовых коэффициентов будем использовать количество пользователей, давших оценку предмету:
<math>\frac{2 \times 2.5 + 1 \times 8 }{2+1} = \frac{13 }{3} = 4.33</math>
Чтобы применить алгоритм Slope One для заданных n предметов, надо рассчитать и сохранить среднюю разницу и количество голосов для каждой из n² пар предметов.
Оценка сложности алгоритма
 |
Этот раздел ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться раздел, посвящённый анализу ресурсов, требуемых для работы алгоритма.
Вы можете помочь проекту, написав этот раздел. |
Рекомендательные системы, использующие Slope One
- [hitflip.de hitflip] - система рекомендаций DVD.
- [www.valueinvestingnews.com/content-recommendations-upgrade Value Investing News] - новостной сайт фондовых бирж.
Программное обеспечение с открытым исходным кодом, использующее Slope One
- [www.serpentine.com/blog/2006/12/12/collaborative-filtering-made-easy/ Пошаговая инструкция] по реализации Slope One на Python.
Java:
- [taste.sourceforge.net/ Taste]: a java-based collaborative library with support for Enterprise Java Beans ([blogs.sun.com/plamere/entry/open_source_recommendation_engine_in code sample])
- [www.daniel-lemire.com/fr/documents/publications/SlopeOne.java класс Java], реализующий Slope One.
- The [www.nongnu.org/cofi/ Cofi: A Java-Based Collaborative Filtering Library] supports Slope One algorithms (documentation is so-so)
PHP:
- Библиотека [www.vogoo-api.com Vogoo] поддерживает алгоритмы Slope One
- [www.aspedia.net Aspedia ECM API] поддерживает алгоритмы Slope One
- [www.daniel-lemire.com/fr/documents/publications/webpaper.txt Исходный код на PHP] к отчёту об использовании алгоритмов Slope One[9]
- [www.drupal.org/project/cre Модуль] для Drupal CMS реализующий Slope One.
- [code.google.com/p/openslopeone OpenSlopeOne] реализует алгоритмы Slope One на чистом PHP и MySQL.
- Philip Robinson [chlorophil.blogspot.com/2007/06/collaborative-filtering-weighted-slope.html реализовал Slope One] на Erlang.
- Bryan O’Sullivan [www.serpentine.com/blog/2007/08/27/weighted-slope-one-in-haskell-collaborative-filtering-in-29-lines-of-code/ реализовал Slope One] на Haskell.
- [www.geocities.com/videogameboy76/WeightedSlopeOneDemo.xls Таблица] Microsoft Excel реализующая Slope One при помощи VBA (требуется включить макросы).
C#:
- Kuber [www.cnblogs.com/kuber/articles/SlopeOne_CSharp.html реализовал Weighted Slope One] с C#.
- Charlie Zhu [blog.charliezhu.com/2008/07/21/implementing-slope-one-in-t-sql/ реализовал Weighted Slope One] на T-SQL.
Напишите отзыв о статье "Slope One"
Примечания
- ↑ 1 2 3 4 Daniel Lemire, Anna Maclachlan, [arxiv.org/abs/cs/0702144 Slope One Predictors for Online Rating-Based Collaborative Filtering], In SIAM Data Mining (SDM’05), Newport Beach, California, April 21-23, 2005. (англ.)
- ↑ Pu Wang, HongWu Ye, [doi.ieeecomputersociety.org/10.1109/IIS.2009.71 A Personalized Recommendation Algorithm Combining Slope One Scheme and User Based Collaborative Filtering], IIS '09, 2009. (англ.)
- ↑ DeJia Zhang, [ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5209738&isnumber=5209636 An Item-based Collaborative Filtering Recommendation Algorithm Using Slope One Scheme Smoothing], 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 (англ.)
- ↑ [www.google.com/patents/US6,266,649 U.S. Patent 6 266 649](недоступная ссылка с 16-01-2015 (3382 дня))
- ↑ 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, [www.daniel-lemire.com/fr/abstracts/TRD01.html Implementing a Rating-Based Item-to-Item Recommender System in PHP/SQL], Technical Report D-01, January 2005.
Отрывок, характеризующий Slope One
– Место удобное, – сказал эсаул.– Пехоту низом пошлем – болотами, – продолжал Денисов, – они подлезут к саду; вы заедете с казаками оттуда, – Денисов указал на лес за деревней, – а я отсюда, с своими гусаг'ами. И по выстг'елу…
– Лощиной нельзя будет – трясина, – сказал эсаул. – Коней увязишь, надо объезжать полевее…
В то время как они вполголоса говорили таким образом, внизу, в лощине от пруда, щелкнул один выстрел, забелелся дымок, другой и послышался дружный, как будто веселый крик сотен голосов французов, бывших на полугоре. В первую минуту и Денисов и эсаул подались назад. Они были так близко, что им показалось, что они были причиной этих выстрелов и криков. Но выстрелы и крики не относились к ним. Низом, по болотам, бежал человек в чем то красном. Очевидно, по нем стреляли и на него кричали французы.
– Ведь это Тихон наш, – сказал эсаул.
– Он! он и есть!
– Эка шельма, – сказал Денисов.
– Уйдет! – щуря глаза, сказал эсаул.
Человек, которого они называли Тихоном, подбежав к речке, бултыхнулся в нее так, что брызги полетели, и, скрывшись на мгновенье, весь черный от воды, выбрался на четвереньках и побежал дальше. Французы, бежавшие за ним, остановились.
– Ну ловок, – сказал эсаул.
– Экая бестия! – с тем же выражением досады проговорил Денисов. – И что он делал до сих пор?
– Это кто? – спросил Петя.
– Это наш пластун. Я его посылал языка взять.
– Ах, да, – сказал Петя с первого слова Денисова, кивая головой, как будто он все понял, хотя он решительно не понял ни одного слова.
Тихон Щербатый был один из самых нужных людей в партии. Он был мужик из Покровского под Гжатью. Когда, при начале своих действий, Денисов пришел в Покровское и, как всегда, призвав старосту, спросил о том, что им известно про французов, староста отвечал, как отвечали и все старосты, как бы защищаясь, что они ничего знать не знают, ведать не ведают. Но когда Денисов объяснил им, что его цель бить французов, и когда он спросил, не забредали ли к ним французы, то староста сказал, что мародеры бывали точно, но что у них в деревне только один Тишка Щербатый занимался этими делами. Денисов велел позвать к себе Тихона и, похвалив его за его деятельность, сказал при старосте несколько слов о той верности царю и отечеству и ненависти к французам, которую должны блюсти сыны отечества.
– Мы французам худого не делаем, – сказал Тихон, видимо оробев при этих словах Денисова. – Мы только так, значит, по охоте баловались с ребятами. Миродеров точно десятка два побили, а то мы худого не делали… – На другой день, когда Денисов, совершенно забыв про этого мужика, вышел из Покровского, ему доложили, что Тихон пристал к партии и просился, чтобы его при ней оставили. Денисов велел оставить его.
Тихон, сначала исправлявший черную работу раскладки костров, доставления воды, обдирания лошадей и т. п., скоро оказал большую охоту и способность к партизанской войне. Он по ночам уходил на добычу и всякий раз приносил с собой платье и оружие французское, а когда ему приказывали, то приводил и пленных. Денисов отставил Тихона от работ, стал брать его с собою в разъезды и зачислил в казаки.
Тихон не любил ездить верхом и всегда ходил пешком, никогда не отставая от кавалерии. Оружие его составляли мушкетон, который он носил больше для смеха, пика и топор, которым он владел, как волк владеет зубами, одинаково легко выбирая ими блох из шерсти и перекусывая толстые кости. Тихон одинаково верно, со всего размаха, раскалывал топором бревна и, взяв топор за обух, выстрагивал им тонкие колышки и вырезывал ложки. В партии Денисова Тихон занимал свое особенное, исключительное место. Когда надо было сделать что нибудь особенно трудное и гадкое – выворотить плечом в грязи повозку, за хвост вытащить из болота лошадь, ободрать ее, залезть в самую середину французов, пройти в день по пятьдесят верст, – все указывали, посмеиваясь, на Тихона.
– Что ему, черту, делается, меренина здоровенный, – говорили про него.
Один раз француз, которого брал Тихон, выстрелил в него из пистолета и попал ему в мякоть спины. Рана эта, от которой Тихон лечился только водкой, внутренне и наружно, была предметом самых веселых шуток во всем отряде и шуток, которым охотно поддавался Тихон.
– Что, брат, не будешь? Али скрючило? – смеялись ему казаки, и Тихон, нарочно скорчившись и делая рожи, притворяясь, что он сердится, самыми смешными ругательствами бранил французов. Случай этот имел на Тихона только то влияние, что после своей раны он редко приводил пленных.
Тихон был самый полезный и храбрый человек в партии. Никто больше его не открыл случаев нападения, никто больше его не побрал и не побил французов; и вследствие этого он был шут всех казаков, гусаров и сам охотно поддавался этому чину. Теперь Тихон был послан Денисовым, в ночь еще, в Шамшево для того, чтобы взять языка. Но, или потому, что он не удовлетворился одним французом, или потому, что он проспал ночь, он днем залез в кусты, в самую середину французов и, как видел с горы Денисов, был открыт ими.
Поговорив еще несколько времени с эсаулом о завтрашнем нападении, которое теперь, глядя на близость французов, Денисов, казалось, окончательно решил, он повернул лошадь и поехал назад.
– Ну, бг'ат, тепег'ь поедем обсушимся, – сказал он Пете.
Подъезжая к лесной караулке, Денисов остановился, вглядываясь в лес. По лесу, между деревьев, большими легкими шагами шел на длинных ногах, с длинными мотающимися руками, человек в куртке, лаптях и казанской шляпе, с ружьем через плечо и топором за поясом. Увидав Денисова, человек этот поспешно швырнул что то в куст и, сняв с отвисшими полями мокрую шляпу, подошел к начальнику. Это был Тихон. Изрытое оспой и морщинами лицо его с маленькими узкими глазами сияло самодовольным весельем. Он, высоко подняв голову и как будто удерживаясь от смеха, уставился на Денисова.
– Ну где пг'опадал? – сказал Денисов.
– Где пропадал? За французами ходил, – смело и поспешно отвечал Тихон хриплым, но певучим басом.
– Зачем же ты днем полез? Скотина! Ну что ж, не взял?..
– Взять то взял, – сказал Тихон.
– Где ж он?
– Да я его взял сперва наперво на зорьке еще, – продолжал Тихон, переставляя пошире плоские, вывернутые в лаптях ноги, – да и свел в лес. Вижу, не ладен. Думаю, дай схожу, другого поаккуратнее какого возьму.
– Ишь, шельма, так и есть, – сказал Денисов эсаулу. – Зачем же ты этого не пг'ивел?
– Да что ж его водить то, – сердито и поспешно перебил Тихон, – не гожающий. Разве я не знаю, каких вам надо?
– Эка бестия!.. Ну?..
– Пошел за другим, – продолжал Тихон, – подполоз я таким манером в лес, да и лег. – Тихон неожиданно и гибко лег на брюхо, представляя в лицах, как он это сделал. – Один и навернись, – продолжал он. – Я его таким манером и сграбь. – Тихон быстро, легко вскочил. – Пойдем, говорю, к полковнику. Как загалдит. А их тут четверо. Бросились на меня с шпажками. Я на них таким манером топором: что вы, мол, Христос с вами, – вскрикнул Тихон, размахнув руками и грозно хмурясь, выставляя грудь.
– То то мы с горы видели, как ты стречка задавал через лужи то, – сказал эсаул, суживая свои блестящие глаза.
Пете очень хотелось смеяться, но он видел, что все удерживались от смеха. Он быстро переводил глаза с лица Тихона на лицо эсаула и Денисова, не понимая того, что все это значило.
– Ты дуг'ака то не представляй, – сказал Денисов, сердито покашливая. – Зачем пег'вого не пг'ивел?
Тихон стал чесать одной рукой спину, другой голову, и вдруг вся рожа его растянулась в сияющую глупую улыбку, открывшую недостаток зуба (за что он и прозван Щербатый). Денисов улыбнулся, и Петя залился веселым смехом, к которому присоединился и сам Тихон.
– Да что, совсем несправный, – сказал Тихон. – Одежонка плохенькая на нем, куда же его водить то. Да и грубиян, ваше благородие. Как же, говорит, я сам анаральский сын, не пойду, говорит.
– Экая скотина! – сказал Денисов. – Мне расспросить надо…
– Да я его спрашивал, – сказал Тихон. – Он говорит: плохо зн аком. Наших, говорит, и много, да всё плохие; только, говорит, одна названия. Ахнете, говорит, хорошенько, всех заберете, – заключил Тихон, весело и решительно взглянув в глаза Денисова.
– Вот я те всыплю сотню гог'ячих, ты и будешь дуг'ака то ког'чить, – сказал Денисов строго.
– Да что же серчать то, – сказал Тихон, – что ж, я не видал французов ваших? Вот дай позатемняет, я табе каких хошь, хоть троих приведу.
– Ну, поедем, – сказал Денисов, и до самой караулки он ехал, сердито нахмурившись и молча.
Тихон зашел сзади, и Петя слышал, как смеялись с ним и над ним казаки о каких то сапогах, которые он бросил в куст.
Когда прошел тот овладевший им смех при словах и улыбке Тихона, и Петя понял на мгновенье, что Тихон этот убил человека, ему сделалось неловко. Он оглянулся на пленного барабанщика, и что то кольнуло его в сердце. Но эта неловкость продолжалась только одно мгновенье. Он почувствовал необходимость повыше поднять голову, подбодриться и расспросить эсаула с значительным видом о завтрашнем предприятии, с тем чтобы не быть недостойным того общества, в котором он находился.
