МЕТОДЫ ФОРМИРОВАНИЯ И ОЦЕНИВАНИЯ ГРУППОВЫХ РЕКОМЕНДАЦИЙ

Аннотация: Проанализированы методы формирования групповых рекомендаций. Предложена метрика оценивания качества представленных моделей. Проведено исследование качества моделей с помощью предложенной метрики.

Ключевые слова: групповые рекомендательные системы, теория принятия решений, методы голосования, профиль пользователя.

Технічні науки

УДК 519.816

Метелиця Марія Андріївна

студентка

Національний технічний університет України

«Київський політехнічний інститут»

Метелица Мария Андреевна

студентка

Национальный технический университет Украины

«Киевский политехнический институт»

Metelytsia M.

student

National Technical University of Ukraine “Kyiv Polytechnic Institute”

МЕТОДИ ФОРМУВАННЯ ТА ОЦІНЮВАННЯ ГРУПОВИХ РЕКОМЕНДАЦІЙ

МЕТОДЫ ФОРМИРОВАНИЯ И ОЦЕНИВАНИЯ ГРУППОВЫХ РЕКОМЕНДАЦИЙ

DESIGN AND EVALUATION OF GROUP RECOMMENDATIONS

Анотація: Проаналізовано методи формування групових рекомендацій. Запропоновано метрику оцінювання якості представлених моделей. Проведено дослідження якості моделей за допомогою запропонованої метрики.

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

Аннотация: Проанализированы методы формирования групповых рекомендаций. Предложена метрика оценивания качества представленных моделей. Проведено исследование качества моделей с помощью предложенной метрики.

Ключевые слова: групповые рекомендательные системы, теория принятия решений, методы голосования, профиль пользователя.

Summary: The methods for group recommendations formation were investigated. A quality evaluation metric was suggested. A study of the models quality using the proposed metric was conducted.

Key words: group recommender systems, decision theory, voting methods, user profile.

Вступ. Групові рекомендаційні системи мають на меті виявлення вподобань визначеної групи користувачів, на основі їх індивідуальних вподобань та інших факторів. Широкомасштабні дослідження у цій галузі проводились фахівцями з різних країн світу. Професор Джудіт Мастгофф (Judith Masthoff), у своїх роботах [1] та [4] представляє і емпірично оцінює ряд стратегій соціального вибору для рекомендації телевізійних програм групам з невеликою кількістю користувачів. В даних роботах було проаналізовано ці стратегії з метою використання деяких з них у процесі агрегування індивідуальних вподобань користувачів. Італійський вчений Франческо Річі (Francesco Ricci) аналізує як індивідуальні рекомендаційні системи так і загальні підходи до створення групових рекомендацій [2].

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

Мета роботи. Проаналізувати та порівняти методи формування групових рекомендацій, засновані на теорії групового вибору та запропонувати метрику оцінювання таких методів.

Основна частина. У даній роботі задача надання групових рекомендацій розглядається у контексті об'єднання (агрегування) індивідуальних вподобань користувачів групи [3]. У практичному дослідженні індивідуальні вподобання визначалися за допомогою алгоритму колаборативної фільтрації за сусідством користувачів [5].

Постановка задачі

Вихідними даними в задачі є N векторів розмірності M з передбаченими за алгоритмом колаборативної фільтрації [5] рейтингами для кожного користувача групи за всіма фільмами за бази даних:

де N – кількість користувачів в групі;

M – загальна кількість фільмів;

 - M-розмірний вектор, елементами якого є передбачені рейтинги для j-го користувача за кожним фільмом. Рейтинги лежать в інтервалі від 1 до 10.

В задачі необхідно отримати вектор групових вподобань – групових рейтингів для кожного фільма:

де M – загальна кількість фільмів.

Методи формування групових рекомендацій

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

Адитивна утилітарна стратегія (Additive utilitarian strategy)

Мультиплікативна утилітарна стратегія (Multiplicative utilitarian strategy)

Стратегія середнього (Average strategy)

Стратегія середнього без страждань (Average without misery strategy)

Стратегія мінімальних страждань (Least misery strategy)

Стратегія максимального задоволення (most pleasure strategy)

Стратегія справедливості (Fairness strategy)

Алгоритм визначення групової оцінки наступний.

1. Перший користувач вибирається випадковим чином. Розглядаються його перші L вподобань.
2. Для кожного з L об’єктів визначається мінімальна оцінка за всіма користувачами.
3. З усіх об’єктів, які отримали мінімальні оцінки вибирається той, мінімальна оцінка якого найбільша і він отримує групову оцінку рівну M – кількості об’єктів. На K-й ітерації оцінка буде дорівнювати M-K (якщо першу ітерацію назвати нульовою). Перехід на наступну ітерацію (п.1)

Нижче наведено формалізацію.

         k-та ітерація:

Мажоритарна стратегія (Plurality voting strategy)

Алгоритм наступний:

1. Перший користувач вибирається випадковим чином (тут в якості модифікації можна ввести додатковий параметр – порядок впливовості користувачів у групі). Розглядаються його перші L вподобань.
2. Для кожного з L об’єктів визначається сума оцінок за всіма користувачами, крім того, що зараз розглядається.
3. Об’єкт, сумарна оцінка якого виявилась найбільшою, отримує групову оцінку рівну M – кількості об’єктів. На K-й ітерації оцінка буде дорівнювати M-K (якщо першу ітерацію назвати нульовою). Перехід на наступну ітерацію (п.1)

Формалізацію наведено нижче.

k-та ітерація:

Стратегія голосування за згодою (Approval voting strategy)

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

Стратегія Борда (Borda count strategy)

Алгоритм проходить в два етапи:

1. Для всіх користувачів оцінки об'єктів замінєється на нові бали за наступним принципом: об'єкт з мінімальною оцінкою отримує нуль, наступний – 1 і так далі. У тому випадку, коли користувач однаково оцінив декілька об'єктів, ставиться середня з потенціально можливих оцінок.
2. Далі отримані бали сумуються, та отримані значення і є групові оцінки.

Позначення для вищенаведених формул:

груповий рейтинг для m-го фільму;

N – кількість користувачів в групі;

M – загальна кількість фільмів;

 рейтинг m-го фільму для n-го користувача;

T – порогове значення.

Метрика оцінювання якості

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

де  оцінка ранжування для n-го користувача;

місце в загальному рейтингу фільмів для групи;

середній рейтинг для n-го користувача ;

загальна кількість фільмів у матриці вихідних даних.

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

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

Формула для групової оцінки ранжування за принципом мінімального задоволення:

Це означає, що за групову задоволеність приймається ступінь задоволеності найменш щасливого її учасника.

Результати дослідження. На основі запропонованої метрики ранжування було досліджено методи агрегування індивідуальних вподобань користувачів групи. На стовчастій діаграмі на рис. 1 зображено групові оцінки ранжування при кожному з методів для групп різного розміру (3, 6 та 9 користувачів). На діаграмі на рис. 2 зображено групові оцінки ранжування при кожному з методів для вибірок різного об'єму.

Рисунок 1 - Порівняння стратегій суспільного вибору за оцінкою ранжування для груп різного розміру

Рисунок 2 - Порівняння стратегій суспільного вибору за оцінкою ранжування для різних вибірок

З графіків видно, що при інших рівних умовах (фіксована вибірка і фіксований розмір групи) найбільш ефективними в сенсі оцінки ранжування виявилися методи Середнього без страждань (Average without misery), Голосування за згодою (Approval Voting) і стратегія Справедливості (Fairness strategy).

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

Література:

1. Masthoff, J. Group Modeling: Selecting a Sequence of Television Items to Suit a Group of Viewers / J. Masthoff // User Modeling and User-Adapted Interaction. – 2004. - №14. – P. 37-85.
2. Recommender Systems Handbook / [Ricci, F., Rokach, L., Shapira, B., Kantor, P.B.].  – New York City : Springer, 2011. – 842 p.
3. Masthoff, J. Group Recommender Systems: Combining Individual Models / J Masthoff. // Recommender Systems Handbook. - New York : Springer, 2011. - P. 677—702.
4. Masthoff, J. The Pursuit of Satisfaction: Affective State in Group Recommender Systems / J Masthoff. – Aberdeen :  University of Aberdeen, 2005. - 306 p.
5. Segaran, T. Programming Collective Intelligence / T. Segaran. – Sebastopol : O’Reilly Media, 2007. – 362 p.