Рекомендаційні системи Частина 1
Принципи роботи рекомендаційних механізмів Інтернету
Серія контенту:
Цей контент є частиною # із серії # статей: Рекомендаційні системи
Цей контент є частиною серії:
Слідкуйте за виходом нових статей цієї серії.
Де можна зустріти рекомендаційну систему
Рекомендаційні системи є на багатьох веб-сайтах, які ви використовуєте щодня, включаючи такі відомі сайти.
Amazon - популярний сайт електронної комерції - використовує рекомендації на основі контенту. Коли відвідувач вибирає для покупки будь-який товар, Amazon на основі цього вихідного товару рекомендує відвідувачу інші товари, придбані іншими користувачами (за допомогою матриці покупки наступного товару на основі його схожості з попередньою покупкою). Компанія Amazon запатентувала цей підхід під назвою item-to-item collaborative filtering (колаборативна фільтрація від елемента до елемента).
Крім того, рекомендаційні механізми використовуються на таких сайтах як Facebook, Twitter, Google, MySpace, Last.fm, Del.icio.us, Pandora, Goodreads, а також на вашому улюбленому сайті онлайнових новин. Використання того чи іншого рекомендаційного механізму стає стандартним елементом сучасного веб-представництва.
Рекомендаційні системи змінили способи взаємодії неживих веб-сайтів зі своїми користувачами. Замість надання статичної інформації, коли користувачі шукають і, можливо, купують продукти, рекомендаційні системи збільшують ступінь інтерактивності для розширення можливостей, що надаються користувачеві. Рекомендаційні системи формують рекомендації незалежно длякожного конкретного користувача на основі його минулих покупок та пошуків, а також на основі поведінки інших користувачів. У цій статті описуються рекомендаційні системи та реалізовані в них алгоритми. У другій статті цього циклу розглядаються пропозиції з відкритим кодом для створення рекомендаційних систем.
Базові підходи
У більшості рекомендаційних систем застосовується один із двох базових підходів: колаборативна фільтрація (collaborative filtering) та контентна фільтрація (content-based filtering). Існують також інші підходи (у тому числі гібридні).
Колаборативна фільтрація
Колаборативна фільтрація виробляє рекомендації, що базуються на моделі попередньої поведінки користувача. Ця модель може бути побудована виключно на основі поведінки даного користувача або, що більш ефективно, з урахуванням поведінки інших користувачів зі схожими характеристиками. У тих випадках, коли колаборативна фільтрація бере до уваги поведінку інших користувачів, вона використовує знання групи (group knowledge) для вироблення рекомендацій з урахуванням подоби користувачів. По суті рекомендації базуються на автоматичному співробітництві безлічі користувачів і виділення (методом фільтрації) тих користувачів, які демонструють схожі переваги чи шаблони поведінки.
Як приклад припустимо, що ви створюєте веб-сайт, щоб пропонувати відвідувачам рекомендації щодо блогів. На основі інформації від багатьох користувачів, які підписуються на блоги та читають їх, ви можете згрупувати цих користувачів за їх перевагами. Наприклад, ви можете об'єднати в одну групу користувачів, які читають кілька одних і тих самих блогів. За цією інформацією виідентифікуєте найпопулярніші блоги серед тих, що читають учасники цієї групи. Потім – конкретному користувачеві цієї групи – ви рекомендуєте найпопулярніший блог із тих, на які він ще не підписаний і які він не читає.
Рисунок 1. Простий приклад колаборативної фільтрації
Тепер ви зможете ідентифікувати певні відмінності у межах кожного кластера і сформувати значні рекомендації. У кластері 1 Марк прочитав 10 статей з блогу про продукти з відкритим вихідним кодом, а Еліза не прочитала жодної такої статті; Еліза прочитала одну статтю в блозі за Agile-технологіями, а Марк не прочитав жодної такої статті. Отже, з рис. 1, Елізі можна порекомендувати блог за продуктами з відкритим вихідним кодом. Для Марка неможливо сформувати жодних рекомендацій, оскільки невелика різниця між ним та Елізою за кількістю прочитань блогу за Agile-технологіями з великою ймовірністю буде відфільтрована. У кластері 2 Джилл прочитала три статті в блозі по продуктах з відкритим вихідним кодом, а Меган не прочитала жодної такої статті; Меган прочитала 3 статті в блозі з Linux, а Джилл не прочитала жодної такої статті. Таким чином, для учасників кластера 2 можна сформувати наступні дві рекомендації: учаснику Джилл рекомендується блог по Linux, а учаснику Меган - блог за продуктами з відкритим вихідним кодом.
Інший спосіб розгляду цих відносин заснований на їх схожості та відмінності, як ілюструє діаграма Венна на рис. 2. Подібності визначають, за якими ознаками (за допомогою відповідного алгоритму) слід групувати користувачів, які мають схожі інтереси. Відмінності - це можливості, які можуть бути використані для вироблення рекомендацій, наприклад, за допомогою застосування фільтра популярності.
Малюнок 2. Подібності та відмінності, що використовуються в колаборативній фільтрації
Хоча на рис. 2 показана спрощена картина (яка до того ж страждає від розрідженості даних через використання лише двох зразків), таке уявлення дуже зручно.
Контентна фільтрація
Повернемося до мал. 1 та розглянемо користувача з ім'ям Еліза. Припустимо, що ви застосовуєте ранжування блогів, яке вказує на те, що користувачі, які читали статті по Linux, можуть зацікавитися хмарними обчисленнями та продуктами з відкритим вихідним кодом. У цьому випадку ви зможете легко порекомендувати Елізі — на основі її поточних читацьких звичок — блог по продуктах з відкритим вихідним кодом. Цей підхід проілюстрований на рис. 3, спирається виключно на контент, якого звертається один користувач, а не на поведінку інших користувачів в системі.
Рисунок 3. Ранжований список відмінностей, який використовується у контентній фільтрації
Діаграму Венна (див. рис. 2 можна застосувати і в цьому випадку: якщо одна сторона - це користувач Еліза, а інша - це ранжований набір подібних блогів, то подібності ігноруються (оскільки Еліза вже прочитала відповідні блоги), а ранжовані відмінності створюють можливості для вироблення рекомендацій.
Гібридні підходи
Гібридні підходи, які поєднують колаборативну та контентну фільтрацію, також підвищують ефективність (і складність) рекомендаційних систем. Простий приклад гібридної системи міг би використати підходи, показані на рис. 1 та на рис. 3. Поєднання результатів колаборативної та контентної фільтрації потенційно дозволяє підвищити точність рекомендації. Крім того, гібридний підхід може бути корисним, якщо застосування колаборативноїфільтрація починається при значній розрідженості даних (т.з. холодний старт). Гібридний підхід дозволяє спочатку зважувати результати згідно з контентною фільтрацією, а потім зміщувати ці ваги у напрямку до колаборативної фільтрації (у міру "визрівання" доступного набору даних конкретного користувача).
Алгоритми, які використовуються рекомендаційними системами
Відомий підхід, застосований у конкурсі Netflix prize, наочно демонструє, що в рекомендаційних механізмах можуть бути використані різні алгоритми. Отримані результати можуть відрізнятися залежно від проблеми, на вирішення якої спроектований конкретний алгоритм, і зажадав від відносин, які у даних. Багато з цих алгоритмів прийшли з галузі машинного навчання (яка, у свою чергу, є підобластю штучного інтелекту), яка займається алгоритмами для навчання, прогнозування та прийняття рішень.
Кореляція Пірсона
Кореляція Пірсона, яка широко застосовується у дослідницької діяльності, є дуже популярним алгоритмом у сфері колаборативної фільтрації.
Алгоритми кластеризації
Існує безліч алгоритмів кластеризації. Найпростішим є алгоритм k-середніх (k-means), який розділяє елементи на k кластерів. Спочатку елементи розподіляються за цими кластерами у довільному порядку. Потім кожного кластера обчислюється центр мас (чи навіть центр) як функція його членів. Після цього перевіряється відстань кожного члена кластера від центру кластера. Якщо за результатами цієї перевірки член виявляється ближче до іншого кластера, він переміщається до цього кластеру. Після перевірки всіх відстаней всім членів центри кластерів обчислюються заново. При досягненністабільного стану (у процесі чергової ітерації члени не переміщалися) набір вважається належним чином кластеризованим, і алгоритм зупиняється.
Обчислення відстані між двома об'єктами може бути складним для візуалізації. Один із поширених методів вирішення цього завдання полягає в тому, щоб розглядати кожен член кластера як багатовимірний вектор і обчислювати для нього т.зв. Евклідова відстань.
Існує безліч інших різновидів кластеризації, зокрема теорія адаптивного резонансу (Adaptive Resonance Theory), нечітка кластеризація методом C-середніх (Fuzzy C-means), імовірнісна кластеризація за допомогою EM-алгоритму (Expectation-Maximization) і т.д.
Інші алгоритми
У рекомендаційних механізмах може застосовуватися безліч алгоритмів (а якщо враховувати варіації, їх ще більше). Перерахую деякі успішно застосовувані алгоритми.
- Байєсівські мережі довіри (Bayesian Belief Nets) — візуально можуть бути представлені як орієнтований ациклічний граф, ребра якого представляють пов'язані ймовірності змінних.
- Ланцюга Маркова (Markov chains) - засновані на такому ж підході, як у байєсовських мереж довіри, але вирішують проблему вироблення рекомендації як послідовну оптимізацію, а не як просте прогнозування.
- Класифікація за методом Роккіо (Rocchio classification) (заснована на векторній моделі) - використовує відгуки про релевантність елементів для підвищення точності рекомендацій.
Проблеми рекомендаційних систем
Можливості збору даних, які надає Інтернет, суттєво спростили використання "мудрості натовпу" за допомогою колаборативної фільтрації. З іншого боку, безліч доступних даних ускладнюєреалізацію цієї можливості. Наприклад, поведінка деяких користувачів цілком піддається моделюванню, але інші користувачі не демонструють типової поведінки. Наявність таких користувачів може призводити до зміщення результатів рекомендаційної системи та зниження її ефективності. Крім того, користувачі можуть задіяти рекомендаційну систему для підвищення переваг одного продукту щодо іншого продукту — наприклад, за допомогою відправки позитивних відгуків про один продукт і негативних відгуків про його конкурентів. Хороша рекомендаційна система повинна справлятися з цими проблемами.
Ще одна проблема, властива великим рекомендаційним системам, пов'язана з масштабованістю. Традиційні алгоритми добре працюють із порівняно невеликими обсягами даних, проте зі зростанням цих наборів отримання результатів на колишньому рівні якості за допомогою традиційних алгоритмів може стати проблематичним. У разі офлайнової обробки це може не становити великої проблеми, проте для сценаріїв реального часу потрібні більш спеціалізовані підходи.