Вступ

Магістерська робота присвячена актуальній науковій задачі задоволення запитів користувачів шляхом аналізу даних. Алгоритми які вирішують подібні завдання називаються рекомендаційними.

Основне завдання рекомендаційних алгоритмів – аналізувати запити користувача і на основі цих даних передбачати його дії.

1. Актуальність теми

У сервісах які пропонують великий вибір товарів або контенту існує проблема довгого хвоста. Дана проблема походить під категорію розподілу Парето (відношення 20% до 80%), представленого на малюнку 1. Так наприклад 20% видів товарів в інтернет магазині заробляють 80% виручки. Користувачі купують в основному популярні товари, а про існування решти 80% товарів користувач може навіть не знати. Таким чином з'являється проблема, коли користувач може не знати про існування товару тільки тому, що він не популярний серед більшостей. Для вирішення даної проблеми створено алгоритми рекомендацій які персоналізують пропозиції виходячи з даних про користувачів[1].

Малюнок 1. Проблема довгого хвоста.

На даний момент існує цілий ряд практичних напрямків в даній сфері:

• Конфіденційність. Необхідно убезпечити доступ до приватних даних користувачів. Важливо виключити можливість ідентифікувати особисті дані користувачів виходячи з роботи алгоритму[2];
• Захист від зловмисників. Необхідний захистити алгоритм від атак зловмисників, які можуть подати неправильні дані в якості вихідних даних, тим самим набагато зменшивши його ефективність[3];
• Визначення важливості дій користувачів. При перегляді і при покупці товару користувач проявляє свій інтерес до даного продукту, проте важливість покупки набагато вище ніж важливість перегляду[4];
• Соціальність. Активний розвиток соціальних мереж дає можливість дізнатися інформацію про інтереси не тільки конкретного користувача, а й інтереси його друзів і знайомих[5];
• Мобільні платформи. Розвиток операційних мобільних операційних систем дало можливість збирати більше інформації про користувачів, а також істотно збільшило кількість даних про поточний контексті користувача[6];
• Оптимізація алгоритмів. З розвитком технологій з'явилася можливість збирати великі масиви інформації. Через це необхідно оптимізувати алгоритми таким чином, щоб використовувалося менше оперативної пам'яті і процесорного часу, при умова збільшення ефективності алгоритму[7];
• Об'єднання алгоритмів. За 15 років розвитку сфери було створено велику кількість алгоритмів, які використовують різні вихідні дані про користувача і рекомендовані товари, а також мають різні підходи до їх обробки. Таким чином існує кілька способів отримати передбачення в кожній ситуації. Завдання полягатиме в обьеденения декількох методів для більш точного прогнозу[8].

В даний момент дана сфера активно розвивається завдяки тому, що з'явилися технлогої які збирають велику кількість інформації про користувачів. Від його поточного місцезнаходження і до списку його покупок в магазині.

Регулярно проводяться чемпіонати для пошуку рішення для найбільш важливих проблем[9].

2. Мета і задачі дослідження та заплановані результати

Основне завдання – розробити алгоритм для передбачення цікавих йому мобільних додатків на основі вже встановлених додатків на його пристрої. Алгоритм повинен також враховувати інформацію про властивості додатків і зворотний зв'язок від користувача для поліпшення результату

Додаткові завдання дослідження:

• Аналіз підходів для створення систем задовольняють запити користувачів;
• Оцінка рекомендаційних алгоритмів;
• Вивчення технологій аналізу великих масив інфмораціі;
• Об'єднання кілька рекомендаційних алгоритмів в один;
• Оцінка результатів ефективності алгоритмів.

Об'єкт дослідження : Системи задоволення запитів користувачів.

Предмет дослідження : Об'єднання різних алгоритмів рекомендацій для задоволення запитів користувачів у сфері рекомендації мобільних додатків.

У рамках магістерської роботи планується отримання актуальних наукових результатів за наступними напрямками:

1. Оптимізація алгоритмів заснованих на дії користувачів для застосування у сфері рекомендацій мобільних додатків.
2. Оптимізація алгоритмів заснованих на властивостях об'єктів для застосування у сфері рекомендацій мобільних додатків.
3. Оптимізація алгоритмів заснованих на знаннях для застосування у сфері рекомендацій мобільних додатків.
4. Оптимізація об'єднання підходів в гібридний алгоритм.

Для експериментальної оцінки отриманих теоретичних результатів і формування фундаменту наступних досліджень, в якості практичних результатів планується розробка систему рекомендацій мобільних додатків з наступними властивостями:

• Доступна інформація про об'єкти передбачення (жанр, категорія, і т.д.);
• Доступна інформація про користувачів і їх безлічі даних;
• Об'єкт передбачення мають оцінку експертів (від 0 до 5);
• Алгоритм повинен вказувати які дані найбільш сильно вплинули на передбачення, для того, щоб користувачеві було простіше зробити свій вибір;
• Алгоритм повинен працювати в режимі реального часу і надавати передбачення користувачеві в перебігу декількох секунд;
• Алгоритм повинен враховувати зворотний зв'язок від користувачів (сподобалося пророкування чи ні, які дані для пророкувань важливі, і т.д.);
• Алгоритм повинен збирати нові дані від користувачів і зворотний зв'язок під час роботи прогнозів, і використовувати ці дані оновлюючи основну матрицю відстаней (не обов'язково в режимі реального часу, наприклад раз на добу).

3. Огляд досліджень і розробок

Даная сфера науки почала активно розвиватися порівняно недавно, ориентировачно з 2007 року, коли був оголошений конкурс Netflix на 1 000 000 $ щодо поліпшення їх рекомендаційної системи.

3.1 Огляд міжнародних джерел

Існує велика кількість наукових публікацій пов'язаних з система задоволення запитів користувачів і технологій Big Data. Найбільш вагомий внесок у дану сферу внесли вчені з США та Західної Європи.

Публікація Jeffrey Dean і Sanjay Ghemawat MapReduce: Simplified Data Processing on Large Clusters містить аналіз технології MapReduce. MapReduce є підходом у програмуванні, який пов'язаний з реалізацією обробки та генерації великих масивів даних[2].

Публікація Jorge Aranda, Inmar Givoni, Jeremy Handcock, Danny Tarlow An Online Social Network-based Recommendation System містить аналіз системи, яка використовує дані профілю користувача і його соціальні зв'язки[3].

Публікація Yehuda Koren Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model містить інформацію про особливості алгоритмів рекомендацій заснованих на факторизації матриць[4].

Публікація Michael Hahsler recommenderlab: A Framework for Developing and Testing Recommendation Algorithms містить інформацію про особливості роботи з фреймворком recommenderlab, який використовують при створенні рекомендаційних систем[5].

Публікація Ruslan Salakhutdinov, Andriy Mnih, Geoffrey Hinton Restricted Boltzmann Machines for Collaborative Filtering містить інформацію про пріменененіе машин Больцмона в алгоритмах рекомендацій[6].

Публікація Silva N.B. A graph-based friend recommendation system using Genetic Algorithm містить інформацію про особливості алгоритму рекомендацій, який заснований на генетичних алгоритмах[7] .

Публікація Songjie Gong Learning User Interest Model for Content-based Filtering in Personalized Recommendation System містить інформацію про особливості алгоритмів рекомендацій основаних на властивостях об'єктів[8].

Публікація Wahidah Husain, Lam Yih Dih A Framework of a Personalized Location-based Traveler Recommendation System in Mobile Application містить інформацію про про особливості алгоритмів рекомендацій основаних на геолокації[9].

3.2 Огляд національних джерел

Наукових публікацій у національному науковому товаристві не дуже багато і вони в більшій ступені сістематізаіруют вже существуюіе підходи. Це пов'язано з тим, що сфера великих масивів інформації і рекомендаційних систем тільки починає розвиватися. Основні роботи опубліковані працівниками Київського та Московського університетів.

Публікація Гомзіна А.Г. і Коршунова О.В. Системы рекомендаций: обзор современных подходов містить огляд існуючих підходів при створенні систем рекомендацій. Наведено і систематизовано основні ідеї кожного з підходів, а також проведено їх порівняльний аналіз[10].

Публікація Зайцева І.Б. Методика наивного Байесовского классификатора для задачи совместной фильтрации в системах рекомендации містить докладний аналіз математичного апарату алгоритмів рекомендацій, які використовують найвний Байєсівський підхід для спільної фільтрації. Даний метод на практиці використовується в алгоритмах пошукових движків[11].

Публікація Дьяконова А.Г. Алгоритмы для рекомендательной системы: технология LENKOR містить опис алгоритмів, які посіли перші місця на Міжнародному змаганні «ECML / PKDD Discovery Challenge 2011 (VideoLectures.Net Recommender System Challenge) з написання рекомендаційної системи для ресурсу VideoLectures.net (наукового репозітаріялекцій)[12].

Публікація Хашковского В.В. і Шкурко А.Н. Современные подходы в организации систем обработки больших объемов данных. Обговорюються сучасні підходи до організації систем обробки великих обсягів по мов даних на прикладі інтегрованих систем відомих виробників, і модульних рішень незалежних постачальників. Основну увагу приділено методам отримання та источ никам інформації для систем обробки даних. Наведено основні методи і джерела отримання вихідної інформації та дана їх коротка характеристика[13].

Публікація Соболя А.С. Построение и адаптация newsql субд в частном облаке. Аналізуються питання побудови NewSQL СУБД в приватному сервері з урахуванням обмежень БД. Формалізуються вимоги до майбутньої NewSQL СУБД, в якій планується обслуговувати систему електронного документообігу (СЕД) і систему бізнес-аналітики підприємства[14].

3.3 Огляд локальних джерел

Наукових публікацій пов'язаних непосрдественно зі створенням рекомендаційних систем знайдено не було, однак студенти та викладачі ДонНТУ мають цілий ряд наукових публікацій пов'язаних з аналізом даних та використанням технології Big Data, які пов'язані з темою дипломної роботи.

Робота магістра ДонНТУ Філонова В.А. Розробка моделі персоналізації і алгоритму управління контентом веб-сайту з урахуванням постійних і поточних потреб користувача під керівництвом Шелепова В.Ю. пов'язана з вирішенням проблеми персоналізації web-сторінок на основі даних про користувача шляхом застосування алгоритму CLOPE[15].

Робота магістра ДонНТУ Михнюк Д.В. Розробка і дослідження алгоритмічного забезпечення інтелектуальної системи формування рекомендацій на основі методів коллаборатівной фільтрації під керівництвом Егошин А.А. присвячена аналізу та модифікації алгоритмів коллаборатівной фільтрації для задоволення запитів користувачів[16].

Робота магістра ДонНТУ Чуприн В.І. Підвищення ефективності реалізації моделі розподілених обчислень MapReduce в рамках програмного каркаса Hadoop під керівництвом Дмитрієвої О.А. присвячена модифікації технології Big Data – MapReduce на основі фреймворку Hadoop[17].

Робота магістра ДонНТУ Дрига В.В. Розробка та дослідження алгоритму побудови зважених навчальних вибірок на основі методів кластеризації даних під керівництвом Волченко В.В. присвячена проблемі кластеризації великих масивів даних на групи схожих об'єктів[18].

Робота магістра ДонНТУ Носова А.С. Дослідження соціально-економічного розвитку країн світу з використанням середовища аналізу R і багатовимірна візуалізація під керівництвом Аверіна Г.В. присвячена проблемі візуалізації даних за допомогою інструменту аналізу даних R[19].

Робота магістра ДонНТУ Петц А.О. Попередня обробка даних і відбір факторів в задачах нейромережевої класифікації та прогнозування під керівництвом Хмелевого С.В. присвячена проблемі прогнозування на основі масивів даних за допомогою нейронних мереж[20].

4. Аналіз підходів при створенні систем задовольняють запити користувачів

4.1 Алгоритми засновані на діях користувачів (user-based).

Cистеми використовують тільки інформацію про дії користувача. Основна ідея наступна – якщо протягом п'яти років користувачі U1 і U2 купили книгу B1, а користувач U2 купив ще й книгу B2, то логічно припустити, що книга B2 буде також цікава користувачеві U1.

Варто зауважити, що дані системи не враховують знання і дані про властивості користувачів і предметів рекомендацій. Тобто неважливо якого саме жанру будуть куплені книги і також не має значення що користувач вказав у своєму профілі що йому цікаві книги певного автора.

4.2 Алгоритми засновані на властивостях об'єктів (item-based).

Системи даного типу не використовують дані про дії користувача і тільки аналізують властивості рекомендованих предметів і властивості поточного користувача.

Дані властивості можуть бути введені вручну (наприклад користувач вказує який жанр книг йому цікавий або адміністратор сайту вводить інформацію про книгу: жанр, автор, рік видання, і т.д.), автоматично вилучатись з рекомендованих предметів (наприклад аналіз довжини текстів в книгах і поділу їх на групи: короткі, середні, довгі) і знаходження нових ознак за допомогою алгоритмів кластеризації аналізуючи вихідні дані.

4.3 Алгоритми засновані на знаннях (knowledge-based recommendations).

Системи з цієї групи використовують знання про сферу предпологает продуктів. Дані системи дуже схожі на системи основані на властивостях користувача і предметів рекомендацій, і в деяких джерелах даний тип систем є підтипом систем заснованих на властивостях.

Основний принцип робота даних систем заснований на активному взаімодейтсвіе з користувачем (отримання зворотного зв'язку) і знаннях про сфери рекомендації. Даний тип систем использут в тому випадку, коли тип 1 і 2 використовувати неможливо через невеликі кількості даних. Прикладом може слухаючи система рекомендації фотоапаратів. Як правило, люди купують новий фотоапарат тільки раз на кілька років, тому в кожного конкретного магазину буде недостатньо даних для рекомендації на основі дій користувача. Також фотоапарати мають велику кількість характеристик, котрі мають різну важливість для користувачів. Для фотографоф які знімають у студії найбільш важлива якість зйомки, в теж час для фотографів які знімають на вулиці і ведуть активний спосіб життя також важлива вага фотоапарата, зручність перенесення, розмір пам'яті і час автономної роботи.

Система рекомендацій даного типу активно взаємодіє з користувачем, але не просить ввести всі параметри користувача вручну. У прикладі з фотоапаратами система буде питати користувача де буде відбувається зйомка, портретну або пейзажну зйомку воліє користувач. Результат з відповідей користувача система визначити найбільш важливі для даного користувача властивості та їх оптимальні значення. Знання про сферу рекоммендаций початкової встановлює адміністратор системи.

4.4 Гібридні алгоритми (hybrid).

Наведені вище системи використовують різні підходи до аналізу даних і передбачення результату, тим самим вирішую завдання паралельно. На практиці, не один із способів поодинці не може рекомендувати товари або контент з великою ймовірністю. Тому реальні системи рекомендацій завжди використовують кілька підходів до аналізу та до рекомендаціям.

Гібридні системи об'еденіяют всі описані підходи в єдиний алгоритм і мають найбільшу ефективність. Також дані системи наиболе складні в реалізації та проектуванні. Складність полягає в адаптації алгоритмів до конкретної сфери застосування рекомендаційною сістемми. Так наприклад в сферах де кожен користувач сам оцінює запропонований контент (каталог фільмів з оцінками) найбільш важливою частиною є оцінки користувачів і аналіз їх дій. А при використанні рекомендаційної системи на сайті інтернет магазинів найбільш важливими завданнями для адміністратора системи є увелечение прибутку, а значить при створенні рекомендації необхідно враховувати фактор ціни товарів і необхідності їх продати.

4.5 Порівняння підходів.

Порівняння алгоритмів представлено в таблиці 1.

Таблиця 1. Порівняння підходів до створення рекомендаційних систем.

5. Аналіз структури рекомендаційних систем

Діаграма роботи абстрактної рекомендаційної системи представлена на малюнку 2.

Малюнок 2. Діаграма роботи абстрактної рекомендаційної системи.

(Анімація Розмір: 42 Kb; Кількість кадрів: 9; Кількість повторів: 5)

Висновки

Існує кілька способів реалізації алгоритму рекомендацій. Однак не один зі способів поодинці не може дати добрих результатів. Тому на практиці завжди необхідно використовувати гібридну систему яка об'єднує кілька способів.

Алгоритм рекомендацій буде створює з декількох подмодулей працюють незалежно один від одного на першому етапі. Тому можна розглядаються дані підмодулі як самостійні алгоритми і розробляти їх окремо.

Найбільш складною частиною розроблюваного алгоритму є адаптація узагальнених алгоритмів в контекст рекомендація і об `єднання модулів алгоритмів в єдине целое.Контекст застосував алгоритму є головні критерієм при виборі алгоритмів пророкувань, метрик, оцінки ефективності.

Перед створенням алгоритму необхідно вивчити контекст його застосування і проаналізувати готові безлічі за допомогою Інстурмент статітісікі (R, Weka і т.д.). Це необхожімо для визначення найбільш ефективних алгоритмів в даній ситуації.

Для реалізації алгоритму можна використовувати готові фреймворки з відкритим вихідним кодом. Це істотно скоротить час розробки. При виборі фреймворку і мови програмування найбільш важливим фактором є контекст застосування алгоритму рекоммендаций сферу застосування. Фреймворки надають реалізацію базових алгоритмів, які необхідно змінити в відповідності з контекстом. Однак фреймворки також накладають суттєві обмеження на структуру алгоритму. Якщо необхідна повна свобода в плані проектування алгоритму, то найкращим способом буде написання системи рекомендацій без використання фреймворків.

Необхідно використовувати різні безлічі даних для оцінки ефективності алгоритму. Безлічі даних розділяються на навчальні та тестові підмножини. Шляхом порівняння порівняння передбачень алгоритму або модуля алгоритму на основі яких навчають підмножин і порівняння результатів з тестовим безліччю виявляється чисельна оцінка алгоритму. Оцінку алгоритму необхідно проводити під час розробки системи, для визначення суттєвості змін який були введені між поточною і минулої оцінкою. А також оцінка необхідна для фінального визначення ефективності алгоритму і порівняння його з іншими алгоритмами.

Також необхідно враховувати важливість пояснення результатів при роботі алгоритму рекомендацій. Щоб користувач довіряв алгоритму бажано вказувати на основі яких даних був отриманий результат. Так наприклад якщо запропонувати користувачеві два фільми на вибір: передбачення першого було засновано на переглянуті фільми в стилі бойовиків, а передбачення другого на основі документальних фільмів. І користувач зможе сам вибрати який саме фільм йому зараз більш цікавий.

Перелік посилань

1. Leskovec J., Rajaraman A., Ullman J. Mining of Massive Datasets // The MOOC. – 2014. [URL]: http://www.mmds.org/.
2. Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters // Google, Inc. – 2004. [URL]: http://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf
3. Aranda J., Givoni I., Handcock J., Tarlow D. An Online Social Network-based Recommendation System // University of Toronto – 2007. [URL]: http://www.cs.toronto.edu/syslab/courses/csc2231/07au/projects/2/aranda.pdf
4. Koren Y. Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model // University of Toronto – 2007. [URL]: http://research.yahoo.com/files/kdd08koren.pdf
5. Hahsler M. recommenderlab: A Framework for Developing and Testing Recommendation Algorithms // Southern Methodist University – 2008. [URL]: http://cran.r-project.org/web/packages/recommenderlab/vignettes/recommenderlab.pdf
6. Salakhutdinov R., Mnih A., Hinton G. Restricted Boltzmann Machines for Collaborative Filtering // Southern Methodist University // Proceeding – 2007.
7. Silva N.B. A graph-based friend recommendation system using Genetic Algorithm // Southern Methodist University // Evolutionary Computation – 2010.
8. Gong S. Learning User Interest Model for Content-based Filtering in Personalized Recommendation System // Zhejiang Business Technology Institute – 2010.
9. Husain W., Dih L.Y. A Framework of a Personalized Location-based Traveler Recommendation System in Mobile Application // Universiti Sains Malaysia – 2012.
10. Гомзин А.Г., Коршунов А.В. Системы рекомендаций: обзор современных подходов // Труды ИСП РАН . 2012. №. [URL]: http://cyberleninka.ru/article/n/sistemy-rekomendatsiy-obzor-sovremennyh-podhodov (дата обращения: 28.05.2015).
11. Зайцев И.Б. Методика «наивного» Байесовского классификатора для задачи совместной фильтрации в системах рекомендации // ДНА . 2005. №2. [URL]: http://cyberleninka.ru/article/n/metodika-naivnogo-bayesovskogo-klassifikatora-dlya-zadachi-sovmestnoy-filtratsii-v-sistemah-rekomendatsii (дата обращения: 28.05.2015).
12. Дьяконов А.Г. Алгоритмы для рекомендательной системы: технология LENKOR // Бизнес-информатика . 2012. №1 (19). [URL]: http://cyberleninka.ru/article/n/algoritmy-dlya-rekomendatelnoy-sistemy-tehnologiya-lenkor (дата обращения: 28.05.2015).
13. Хашковский В.В., Шкурко А.Н. Современные подходы в организации систем обработки больших объемов данных // Известия ЮФУ. Технические науки . 2014. №8. [URL]: http://cyberleninka.ru/article/n/sovremennye-podhody-v-organizatsii-sistem-obrabotki-bolshih-obemov-dannyh (дата обращения: 28.05.2015).
14. Соболь А.С. Построение и адаптация newsql субд в частном облаке // Вестник СибГАУ . 2013. №4 (50). [URL]: http://cyberleninka.ru/article/n/postroenie-i-adaptatsiya-newsql-subd-v-chastnom-oblake (дата обращения: 28.05.2015).
15. Филонова В.А. Разработка модели персонализации и алгоритма управления контентом веб-сайта с учетом постоянных и текущих потребностей пользователя // Портал магистров ДонНТУ, 2014 - [URL]: http://masters.donntu.ru/2014/fknt/filonova/diss/index.htm (дата обращения: 28.05.2015).
16. Михнюк Д.В. Разработка и исследование алгоритмического обеспечения интеллектуальной системы формирования рекомендаций на основе методов коллаборативной фильтрации // Портал магистров ДонНТУ, 2014 - [URL]: http://masters.donntu.ru/2014/fknt/mihnyuk/ (дата обращения: 28.05.2015).
17. Чуприн В.И. Повышение эффективности реализации модели распределённых вычислений MapReduce в рамках программного каркаса Hadoop // Портал магистров ДонНТУ, 2014 - [URL]: http://masters.donntu.ru/2014/fknt/chuprin/diss/index.htm (дата обращения: 28.05.2015).
18. Дрига В.В. Разработка и исследование алгоритма построения взвешенных обучающих выборок на основе методов кластеризации данных // Портал магистров ДонНТУ, 2013 - [URL]: http://masters.donntu.ru/2013/fknt/driga/index.htm (дата обращения: 28.05.2015).
19. Носов А.С. Исследование социально-экономического развития стран мира с использованием среды анализа R и многомерная визуализация // Портал магистров ДонНТУ, 2013 - [URL]: http://masters.donntu.ru/2013/fknt/nosov/diss/index.htm (дата обращения: 28.05.2015).
20. Петце А.О. Предварительная обработка данных и отбор факторов в задачах нейросетевой классификации и прогнозирования // Портал магистров ДонНТУ, 2013 - [URL]: http://masters.donntu.ru/2013/fknt/pettse/diss/index.htm (дата обращения: 28.05.2015).

Примітки

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2015 року. Повний текст роботи і матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.