Використання медіани Кемені в алгоритмі формування рекомендацій

The relevant nowadays question of development of the algorithmic support of recommender systems is considered. The article is devoted to the solution of the problem of forming recommendations to new users, which is based on the ideas of transition from the matrix "user-object" to t...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
Hauptverfasser:	Zhurakovska, Oksana, Kochubey, Illa
Format:	Artikel
Sprache:	Ukrainisch
Veröffentlicht:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020
Schlagworte:	рекомендаційна система узгоджене колективне ранжування медіана Кемені
Online Zugang:	https://journal.iasa.kpi.ua/article/view/228372
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	System research and information technologies
Завантажити файл:

Institution

System research and information technologies

_version_	1867334411738939392
author	Zhurakovska, Oksana Kochubey, Illa
author_facet	Zhurakovska, Oksana Kochubey, Illa
author_institution_txt_mv	[ { "author": "Oksana Zhurakovska", "institution": "Національний технічний університет України \"Київський політехнічний інститут імені Ігоря Сікорського\", Київ" }, { "author": "Illa Kochubey", "institution": "Національний технічний університет України \"Київський політехнічний інститут імені Ігоря Сікорського\", Київ" } ]
author_sort	Zhurakovska, Oksana
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2021-04-08T14:17:06Z
description	The relevant nowadays question of development of the algorithmic support of recommender systems is considered. The article is devoted to the solution of the problem of forming recommendations to new users, which is based on the ideas of transition from the matrix "user-object" to the ranking of objects and the formation of recommendations to the user of the active cluster based on the construction of the resulting ranking, which is a Kemeny median on a set of rankings. The choice of Kemeny median as the resulting ranking and the choice of algorithm for its construction are justified. To reduce the complexity of calculations, it is suggested to perform aggregation of information and to use it in forming of ranking recommendations, which are based on a set of "generalized experts" for this cluster. The efficiency of the developed algorithmic support was studied and the results and recommendations were given.
doi_str_mv	10.20535/SRIT.2308-8893.2020.4.05
first_indexed	2025-07-17T10:27:05Z
format	Article
fulltext	 О.С. Жураковська, І.Ю. Кочубей, 2020 Системні дослідження та інформаційні технології, 2020, № 4 59 TIДC ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ ТА МЕРЕЖІ УДК 004.021 DOI: 10.20535/SRIT.2308-8893.2020.4.05 ВИКОРИСТАННЯ МЕДІАНИ КЕМЕНІ В АЛГОРИТМІ ФОРМУВАННЯ РЕКОМЕНДАЦІЙ О.С. ЖУРАКОВСЬКА, І.Ю. КОЧУБЕЙ Анотація. Розглянуто актуальне питання розроблення алгоритмічного забез- печення рекомендаційних систем. Роботу присвячено вирішенню проблеми формування рекомендацій для нових користувачів, в основі якого лежать ідеї переходу від матриці «користувач–предмет» до ранжувань предметів та фор- мування рекомендацій для користувача активного кластера на основі побудови результуючого ранжування, що являє собою медіану Кемені на множині ран- жувань. Обґрунтовано вибір медіани Кемені як результуючого ранжування, а також вибір алгоритму її побудови. Для зменшення складності обчислень за- пропоновано здійснювати агрегацію інформації та використовувати під час формування рекомендації ранжування, побудовані для множини «узагальне- них експертів» для даного кластера. Досліджено ефективність розробленого алгоритмічного забезпечення, наведено результати та рекомендації. Ключові слова: рекомендаційна система, узгоджене колективне ранжування, медіана Кемені. ВСТУП У зв’язку з поширенням та розвитком електронної комерції, зумовленої роз- витком всесвітньої мережі Інтернет, актуальною постала проблема розроб- лення методів побудови рекомендаційних систем для завдань електронної комерції, метою яких є підвищення лояльності користувачів суб’єкта елект- ронної комерції та максимальне забезпечення потреб користувачів. Однією з найбільш поширених у світі моделей електронної комерції є модель біз- нес–споживач (Business–to–Consumer, В2С), до якої належать такі суб’єкти електронної комерції, як інтернет-магазини, електронні дошки оголошень тощо, які мають свої рекомендаційні системи [1]. Аналіз сучасного стану методів побудови рекомендаційних систем по- казує [2], [3], що актуальною залишається проблема формування рекомен- дацій для нових користувачів, особливо для нових рекомендаційних систем з огляду на велику розмірність та розрідженість матриці «предмет– користувач». Крім цього, зумовлене збільшенням кількості користувачів та предметів значне зростання розмірності рейтингової матриці «користувач– предмет», у свою чергу, впливає на істотне ускладнення обчислень. О.С. Жураковська, І.Ю. Кочубей ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 60 Зазвичай рекомендації часто формуються із застосуванням методів ко- лаборативної фільтрації, асоціативних правил [4, 5, 6]. У випадку формування рекомендацій для нового користувача можна або спочатку прогнозувати початкове наближення профілів оцінок, або сфор- мувати рекомендації, використовуючи узагальнений профіль оцінок корис- тувачів активного кластера. Для реалізації цього підходу необхідно викона- ти перехід від матриці «користувач–предмет» до ранжувань предметів і перейти до побудови узгодженого колективного ранжування на множині користувачів активного кластера. З огляду на достатньо велику кількість користувачів та предметів, на які повинні бути орієнтовані сучасні рекомен- даційні системи (наприклад, кількість користувачів може лежати в інтервалі 103–107, кількість предметів — 102–103 [7, 8]), актуальною залишається та- кож агрегація використовуваної інформації та підвищення швидкодії алго- ритмічного і програмного забезпечення як основи рекомендаційної системи. ПОСТАНОВКА ЗАДАЧІ Є множина користувачів системи, яка в результаті попереднього етапу клас- теризації розбита на множину кластерів за певними параметрами користува- чів [9, 10]. Для існуючих користувачів на основі виставлених ними оцінок предметів сформовано матрицю «користувач–предмет». Розглядається зада- ча формування рекомендацій для нового користувача активного кластера у вигляді ранжування на множині предметів на основі інформації про оці- нювання предметів користувачами цього кластера. Розв’язання поставленої задачі може бути реалізоване виконанням та- ких етапів:  побудувати розбиття на множині користувачів активного кластера для агрегації інформації про переваги користувачів;  для кожної підмножини користувачів з побудованого на попере- дньому етапі розбиття сформувати ранжування на множині предметів, яке під час формування рекомендацій буде враховуватись як ранжування «уза- гальненого експерта», який є представником вказаної підмножини користу- вачів;  для множини ранжувань, отриманої на попередньому етапі, сформувати результуюче ранжування, яке виражає колективну думку «узагальнених експертів» і може бути використане як рекомендації для нового користувача. Уведемо ряд позначень: ir = ( 1i A , 2i A , …, ni A ) — ранжування на множині альтернатив А = }{ iA , ni ,1 , для якого виконується умова: kjnknj  ,1,,1 : kj ii AA  , де ji — номер альтернативи, що в ранжуванні ir займає позицію j; ранжуванню ir відповідає відношення, задане матрицею iP = )( i jkp , nj ,1 , nk ,1 , де         ;якщо,1 ,якщо,0 ,якщо,1 kj kj kj i jk AA AA AA p   (1) Використання медіани Кемені в алгоритмі формування рекомендацій Системні дослідження та інформаційні технології, 2020, № 4 61 ),( 21 rrd — відстань між довільними ранжуваннями 1r і 2r :    ji ijij n ji ijij pppprrd 21 1, 21 21 2 1 ),( ; (2) maxd — максимально можлива відстань між ранжуваннями: )1(),(max , max  nnrrdd ji ji , (3) де n — кількість альтернатив; rd — сумарна відстань між ранжуванням r і ранжуваннями користу- вачів множини М: rd = ,),( 1   m i irrd (4) де ),( irrd — відстань між ранжуваннями r і ir , визначається за форму- лою (2). Отже, наведемо математичну постановку задачі. Задано множину М — користувачів активного кластера, Mm  — кі- лькість користувачів, А = }{ iA , ni ,1 — множину альтернатив (предметів) і матрицю «користувач–предмет» )( ijtT  , mi ,1 , nj ,1 , де ijt — оцінка користувачем i альтернативи j. Кожному користувачу Mk відповідає век- тор оцінок альтернатив kv )...,,,( 21 knkk ttt . Необхідно: 1) за множиною векторів оцінок }{ iv , mi ,1 сформувати множину ра- нжувань }{ ir , mi ,1 на множині A для всіх користувачів множини М; 2) визначити узгоджене колективне ранжування, розташоване на міні- мальній сумарній відстані від ранжувань для всіх користувачів множи- ни М: ,),(minarg 1 *    m i i r rrdr (5) де  — множина всіх можливих ранжувань на множині А; ),( irrd — від- стань між ранжуваннями r і ir , визначається за формулою (2). ОБГРУНТУВАННЯ МЕТОДУ РОЗВ’ЯЗАННЯ ЗАДАЧІ Вибір медіанного ранжування. Для пошуку групового консенсусного ран- жування ставиться задача знаходження ранжування, яке було б найближчим до всіх індивідуальних ранжувань за деякою введеною мірою відстані. У випадку, коли розв’язок такої задачі визначається співвідношенням (5), він є медіаною Кемені [11, 12]. Оскільки медіана Кемені вважається одним з най- більш коректних результуючих ранжувань, бо вона задовольняє умови 2–5 [11] узгодженого колективного вибору Ерроу (тобто умови універсальності множини допустимих відношень, монотонності, ненав’язуваності та відсут- О.С. Жураковська, І.Ю. Кочубей ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 62 ності диктатора), а також задовольняє принцип вибору Кондорсе, не при- зводячи до парадоксу Кондорсе [11], пропонується на третьому етапі запро- понованої вище схеми (побудови консенсусного медіанного ранжування) як результуючого ранжування будувати медіану Кемені. Задача знаходження медіани Кемені є важкорозв’язуваною комбінатор- ною задачею і належить до класу NP-повних задач [13, 14, 15, 16]. Існує ряд алгоритмів розв’язання цієї задачі, які базуються на методі гілок і меж, або належать до наближених та евристичних алгоритмів [11, 16, 17, 18, 19]. Оскільки необхідною умовою для алгоритму розв’язання поставленої задачі є можливість розв’язання задач великих розмірностей в режимі реа- льного часу, в запропонованому алгоритмі формування рекомендацій на етапі побудови результуючого ранжування використано евристичний алго- ритм, наведений у праці [11]. В алгоритмі для пошуку результуючого ран- жування за критерієм мінімізації сумарної відстані до ранжувань множини користувачів M необхідно сформувати матрицю втрат )( ijrR  , ni ,1 , nj ,1 , елементи якої визначаються співвідношенням ijr = ,),( 1   m k kij rrd (6) де           ,1якщо,2 ,0якщо,1 ,1якщо,0 ),( k ij k ij k ij kij p p p rrd k ijp — елемент матриці відношення, що ві- дповідає ранжуванню kr , визначається за формулою (1). Тоді для довільного ранжування r сумарна відстань до всіх ранжувань користувачів множини M (4) може бути визначена за матрицею втрат: rd = , 1 1    n i n j ijij pr де ijr — елемент матриці втрат (6); ijp — елемент матриці відношення, що відповідає ранжуванню r (1). Оцінювання отримуваних розв’язків. Досліджуючи роботу алгорит- му побудови медіанного ранжування для задач великої розмірності, доціль- но оцінити:  відхилення значення критерію (4) для розв’язку задачі (5), отримано- го на множині ранжувань «узагальнених експертів» (які отримано в резуль- таті агрегації інформації під час розбиття множини M на підмножини) від значення цього критерію для розв’язку, отриманого на множині ранжувань усіх користувачів з множини M. Значення відхилення дозволить оцінити доцільність агрегації інформації в межах підмножин розбиття, а також оці- нити кількість таких підмножин;  відносну відстань між вказаними ранжуваннями, використовуючи міру (2) і значення максимально можливої відстані (3). Це дозволить оціни- ти схожість розв’язків;  відхилення значення критерію (4) для розв’язку задачі (5), отримано- го на множині ранжувань «узагальнених експертів» від значення нижньої Використання медіани Кемені в алгоритмі формування рекомендацій Системні дослідження та інформаційні технології, 2020, № 4 63 границі критерію (4), яка визначається за матрицею втрат [11] таким спів- відношенням:   m i irrd 1 ),( minH = .},{min 1 1 1      n i n ij jiij rr (7) ДОСЛІДЖЕННЯ Опис алгоритму формування рекомендацій новому користувачу на основі побудови колективного ранжування На вхід алгоритму подається інформація:  M — множина користувачів кластера ( Mm  );  }{ iAA  , ni ,1 — множина альтернатив;  )( ijtT  , mi ,1 , nj ,1 — матриця «користувач–предмет»;  k — кількість підмножин, на які розбивається множина користувачів M з метою агрегації даних за користувачами. Визначається за результатами проведеного дослідження. Крок 1. Побудувати на множині користувачів M розбиття }{ iMM  , ki ,1 , де k —– кількість підмножин, що визначається кількістю користува- чів у кожній підмножині розбиття. Крок 2. Для кожної підмножини iM , ki ,1 , сформувати вектор iMY узагальнених оцінок як середнє арифметичне оцінок користувачів даної під- множини. Крок 3. Упорядкувати альтернативи множини А за спаданням їх оцінок у векторах iMY і за цим упорядкуванням сформувати ранжування iMR , ki ,1 , на кожній підмножині iM . Позначимо отриману множину ранжу- вань }{ iMRMR  , ki ,1 . Крок 4. Для кожного ранжування iMR , ki ,1 побудувати матрицю ві- дношення iMP за формулою (1). Крок 5. На основі матриць iMP , ki ,1 побудувати відношення MP для узгодженого колективного ранжування за допомогою евристичного ал- горитму побудови медіани Кемені. Крок 6. На основі відношення MP сформувати ранжування на мно- жині альтернатив А, що є рекомендацією для нового користувача кластера. Дослідження ефективності алгоритму формування рекомендацій для нового користувача на основі пошуку медіани Кемені Уведемо позначення: – алгоритм AE — евристичний алгоритм побудови медіани Кемені [11]; – Mr = }{ irMr  , mi ,1 — множина ранжувань усіх користувачів множини M; О.С. Жураковська, І.Ю. Кочубей ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 64 – 1r — медіана Кемені, знайдена алгоритмом AE на множині ранжу- вань Mr ; – 2r — медіана Кемені, знайдена алгоритмом AE на множині ранжу- вань MR; – minH — нижнє граничне значення критерію (4), знайдене за співвід- ношенням (7). – 1rd — значення критерію (4) для ранжування 1r , обчислене на мно- жині Mr ; – 2rd — значення критерію (4) для ранжування 2r , обчислене на мно- жині Mr ; Проведемо дослідження: – ефективності алгоритму AE для знаходження розв’язку на множині MR; – оцінювання кількості користувачів у кожній підмножині iM , ki ,1 , яка забезпечує найбільш відповідне співвідношення швидкодії алгоритму і точності результатів. Для оцінювання ефективності агрегації інформації (використання під- множин iM для формування ранжувань для «узагальнених експертів» у по- будові результуючого ранжування) будемо порівнювати процес формування ранжування 2r на множині MR та формування ранжування 1r на множині Mr за швидкодією та наближеністю результатів. Отже, для оцінювання ефективності розробленого алгоритму введемо такі критерії: 1) час роботи алгоритму AE на множині MR; 2) відношення часу роботи алгоритму AE для побудови ранжуваннь 1r і 2r ; 3) відхилення значень критеріїв 1rd і 2rd , обчислених на множині Mr для ранжуваннь 1r і 2r відповідно: 100 1 12    r rr d dd Z ; (7) відхилення значення критерію 2rd від minH : 100 min min2    H Hd Q r ; відносна відстань між ранжуваннями 1r і 2r : 100 )2,1( max  d rrd P , (8) де )2,1( rrd — відстань між ранжуваннями 1r і 2r (2); maxd — максима- льно можлива відстань між ранжуваннями (3). Наприклад, відносна відстань між двома ранжуваннями (2,3,1) і (1,2,3) за формулою (8) дорівнюватиме %67100)3/2( P . Обґрунтування розмірності задачі під час проведення досліджень Аналіз існуючих рекомендаційних систем показав [8], що кількість користу- вачів може змінюватись у діапазоні 103–107, а кількість користувачів у клас- тері — у діапазоні 102–104. Отже, виконаємо дослідження для кількісті ко- ристувачів у кластері 3200m , що відповідає реальним даним. Використання медіани Кемені в алгоритмі формування рекомендацій Системні дослідження та інформаційні технології, 2020, № 4 65 Опис задач дослідження Одна з сновних задач дослідження — це визначення розміру підмножин iM розбиття множини M для застосування алгоритму АЕ на множині MR. Необ- хідно оцінити максимальне збільшення розміру групи (підмножини iM ), за якого відхилення результатів алгоритму AE у побудові результуючих ран- жувань на множинах Mr і MR буде не більшим за 10%. Розмір групи буде- мо змінювати від 50 до 2/m користувачів. Для практичного застосування алгоритму AE необхідно оцінити відно- шення часу роботи алгоритму AE для побудови результуючих ранжувань на множинах Mr і MR. РЕЗУЛЬТАТИ ДОСЛІДЖЕННЯ 1. Відхилення значень критеріїв 1rd і 2rd (8), обчислених на множині Mr для ранжувань 1r і 2r , отриманих алгоритмом AE, а також відхилення значення критерію 2rd від minH (9) (залежно від кількості користувачів у множинах iM , ki ,1 ) показано на рис. 1. Як видно з графіка, ранжування 1r і 2r , отримані алгоритмом AE на множинах Mr і MR відповідно, за значенням критерію (4) відрізняються дуже мало (менше, ніж на 0,5%). Порівнюючи значення критерію (4) для ранжування 2r з нижньою границею minH , бачимо, що відхилення не пере- вищує 4%. Якщо розміри множин iM від m 8 1 до m 4 1 , то ці результати відрізняються не більше, ніж на 1%. Це дозволяє використовувати алгоритм AE на множині MR для побудови результуючого ранжування, яке буде вико- ристане у формуванні рекомендацій. Кількість користувачів у групі В ід но сн е ві дх ил ен ня ре зу ль та ті в ал го ри тм у А Е , % Рис. 1. Відносне відхилення критерію для результату алгоритму AE на множині MR (відхилення значень критеріїв 1rd і 2rd — пунктирна лінія, відхилення значення критерію 2rd від minH — суцільна лінія) О.С. Жураковська, І.Ю. Кочубей ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 66 2. Час роботи алгоритму AE для побудови результуючого ранжування на множині MR залежно від кількості користувачів у множинах iM , ki ,1 , показано на рис. 2. Результати досліджень, подані на рис. 2, дозволяють зробити висновок про можливість застосування алгоритму AE для побудови результуючого ранжування на множині MR за великих значень кількості користувачів у кластері, що відповідає реальним даним. Для визначеного в попередньому пункті дослідження розміру підмножини iM від m)8/1( до m)4/1( час ро- боти алгоритму AE на множині MR складає менше ніж 2 с. 3. Відношення часу роботи алгоритму AE для множини Mr і MR залежно від кількості користувачів у множинах iM , ki ,1 , подано на рис. 3. Кількість користувачів у групі Ч ас р об от и ал го ри тм у А Е , м с Рис. 2. Залежність часу роботи (мс) алгоритму АЕ для отримання ранжування на множині MR від розміру групи Кількість користувачів у групі В ід хи ле нн я ро бо ти а лг ор ит м у на р із ни х м но ж ин ах , р аз и Рис. 3. Відношення часу роботи алгоритму AE на множинах Mr і MR для різних розмірів груп Використання медіани Кемені в алгоритмі формування рекомендацій Системні дослідження та інформаційні технології, 2020, № 4 67 Порівнюючи час роботи алгоритму AE на множинах Mr і MR, бачимо, що ефективність побудови результуючого ранжування алгоритмом AE на множині MR від 100 до 350 разів вища за цим критерієм. 4. Відносну відстань між ранжуваннями 1r і 2r (10) зображено на рис. 4. Порівнявши відносну відстань між ранжуваннями, побудованими на множині ранжувань користувачів кластера (ранжування 1r ) і на множині ранжувань «узагальнених експертів» (ранжування 2r ), бачимо, що вона складає не більше ніж 10% для визначеного в попередніх пунктах дослі- дження розміру групи. А враховуючи істотно вищу швидкодію алгоритму AE на множині MR, робимо висновок про доцільність практичного викорис- тання алгоритму AE на множині MR під час формування узагальненого ран- жування, на основі якого формуються рекомендації для нового користувача. ВИСНОВКИ Проаналізовано проблеми формування рекомендацій в сучасних рекоменда- ційних системах. Показано, що проблема формування рекомендацій для но- вого користувача є актуальною. У зв’язку з великою кількістю користувачів та предметів рекомендаційних систем актуальною залишається проблема розроблення алгоритмічного забезпечення, яке дозволяє формувати рекоме- ндації в реальному часі. У роботі запропоновано алгоритм формування ре- комендацій, що вирішує проблему холодного старту. В основу покладено ідею використання як колективного ранжування медіани Кемені, на основі якого формуються рекомендації для нового користувача. Для підвищення швидкодії алгоритму формування рекомендацій запропоновано використо- вувати агреговану інформацію про переваги користувачів. Для цього слід розбивати множину користувачів на підмножини, розмірність яких визнача- ється в результаті проведеного дослідження. Проведено дослідження розробленого алгоритмічного забезпечення. Досліджено відхилення результатів під час побудови результуючого ранжу- вання на множині всіх користувачів та на множині узагальнених користува- чів. Показано, що в разі розбиття множини користувачів на підмножини роз- мірністю від 1/8 до 1/4 від кількісті користувачів кластера відносне відхилення результатів не перевищує 1%. Досліджено швидкодію запропо- Кількість користувачів у групі Р із ни ця м іж ра нж ув ан ня м и, % Рис. 4. Відносна відстань між ранжуваннями 1r і 2r для різних розмірів груп О.С. Жураковська, І.Ю. Кочубей ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 68 нованого алгоритму і показано, що з використанням агрегованої інформації за користувачами для формування узагальненого ранжування швидкодія алгоритму підвищується від 100 до 350 разів. Аналіз часу роботи розробле- ного алгоритму підтверджує можливість його використання на реальних даних у режимі реального часу. За результатами дослідження можна стверджувати про доцільність ви- користання розробленого алгоритму в рекомендаційних системах для вирі- шення проблеми формування рекомендацій новому користувачу. ЛІТЕРАТУРА 1. J. Lu, D. Wu, M. Mao, W. Wang, and G. Zhang, “Recommender system application developments: A survey”, Decision Support Systems, vol. 74, pp. 187–192, 2015. doi:10.1016/j.dss.2015.03.008. 2. C.A. Gomez-Uribe and N. Hunt, “The Netflix Recommender System: Algorithms, Business Value, and Innovation”, ACM Transactions on Management Information Systems, vol. 6, no. 4, pp. 1–19, 2015. doi:10.1145/2843948. 3. F. Ricci, L. Rokach, and B. Shapira, “Introduction to Recommender Systems Hand- book”, in Recommender Systems Handbook, Boston, MA: Springer, 2011, pp. 1–35. 4. P. Melville et al., “Content-Boosted Collaborative Filtering for Improved Recom- mendations”, in National Conference on Artificial Intelligence, Edmonton, Canada, 2016, pp. 187–192. 5. V. Srikar and R. Sudha, “Examining Lists on Twitter to Uncover Relationships Be- tween Following, Membership and Subscription”, in Proceedings of the 22nd inter- national conference on World Wide Web, Rio de Janeiro, Brazil, 2013, pp. 673–676. 6. I.Yu. Kochubey and O.S. Zhurakovska, “Modified algorithm of collaborative filter- ing for forming user recommendations”, KPI Science News, vol. 3, pp. 43–49, 2020. doi:10.20535/kpi-sn.2020.3.209842. 7. D.T. Pham, S.S. Dimov, and C.D. Nguyen, “Selection of K in K-means clustering”, Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Me- chanical Engineering Science, vol. 219 (1), pp. 103–119, 2005. doi:10.1243/ 095440605x8298. 8. W. Prinz et al., “PolyLens: A Recommender System for Groups of Users”, in Pro- ceedings of the Seventh European Conference on Computer-Supported Cooperative Work, Bonn, Germany, 2001, pp. 199–218. doi:10.1007/0-306-48019-0_11. 9. A. Shepitsen, J. Gemmell, B. Mobasher, and R. Burke, “Personalized Recommenda- tion in Social Tagging Systems Using Hierarchical Clustering”, in Proceedings of the ACM Conference on Recommender Systems — RecSys ’08, 2008, pp. 259–266. doi:10.1145/1454008.1454048. 10. C. Gentile et al., “On Context-Dependent Clustering of Bandits”, in Proceedings of the 34th International Conference on Machine Learning, 2017, pp. 1253–1262. 11. B. Litvak, Ekspertnaya informatsiya. Metody polucheniya i analiza [Expert information. Methods of obtaining and analysis]. Moscow, 2009 12. C. List and C. Puppe, “Judgement aggregation: a survey”, in Oxford handbook of ra- tional and social choice, Oxford, 2009, pp. 457–482. doi:10.1007/s11229-011-0025-3. 13. H. Bury and D. Vagner, “Judgement With Ties. Distance-Based Methods”, New Ap- proaches in Automation and Robotics, Vienna, 2008, pp. 153–172. 14. O. Hudry, “Complexity of computing median linear orders and variants”, Electronic Notes in Discrete Mathematics, vol. 42, pp. 57–64, 2013. doi:10.1016/j.endm. 2013.05.146. 15. O. Hudry, “NP-hardness results on the aggregation of linear orders into median orders”, Annals of Operations Research, vol. 163, pp. 63–88, 2008. doi:10.1007/s10479-008-0353-y 16. S. Amodio, A. D'Ambrosio, and R. Siciliano, “Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny Використання медіани Кемені в алгоритмі формування рекомендацій Системні дослідження та інформаційні технології, 2020, № 4 69 axiomatic approach”, Journal of Operational Research, vol. 249, pp. 667–676, 2015. doi:10.1016/j.ejor.2015.08.048. 17. E. Emond and D. Mason, “A new rank correlation coefficient with application to the consensus ranking problem”, Journal of Multi-Criteria Decision Analysis, vol. 11, pp. 17–28, 2002. 18. W.D. Cook, B. Golany, M. Penn, and T. Raviv, “Creating a consensus ranking of proposals from reviewers partial ordinal rankings”, Computers & Operations Re- search, vol. 43, pp. 954–965, 2007. 19. A. Alnur and M. Meila, “Experiments with Kemeny Ranking: What Works When?”, Mathematical Social Sciences, vol. 64, pp. 28–40, 2012. doi:10.1016/j.mathsocsci. 2011.08.008. Надійшла 09.10.2020 INFORMATION ON THE ARTICLE Oksana S. Zhurakovska, ORCID: 0000-0002-2804-5556, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: o.zhurakovska@kpi.ua Illa Yu. Kochubey, ORCID: 0000-0003-2520-6577, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: illa.kochubey1@gmail.com USE OF KEMENY MEDIAN IN THE ALGORITHM OF FORMING RECOMMENDATION / O.S. Zhurakovska, I.Yu. Kochubey Abstract. The relevant nowadays question of development of the algorithmic sup- port of recommender systems is considered. The article is devoted to the solution of the problem of forming recommendations to new users, which is based on the ideas of transition from the matrix «user-object» to the ranking of objects and the forma- tion of recommendations to the user of the active cluster based on the construction of the resulting ranking, which is a Kemeny median on a set of rankings. The choice of Kemeny median as the resulting ranking and the choice of algorithm for its con- struction are justified. To reduce the complexity of calculations, it is suggested to perform aggregation of information and to use it in forming of ranking recommenda- tions, which are based on a set of «generalized experts» for this cluster. The effi- ciency of the developed algorithmic support was studied and the results and recom- mendations were given. Keywords: recommender system, consensus ranking, Kemeny median. ИСПОЛЬЗОВАНИЕ МЕДИАНЫ КЕМЕНИ В АЛГОРИТМЕ ФОРМИРОВАНИЯ РЕКОМЕНДАЦИЙ / О.С. Жураковская, И.Ю. Кочубей Аннотация. Рассмотрен актуальный в настоящее время вопрос разработки ал- горитмического обеспечения рекомендательных систем. Робота посвящена решению проблемы формирования рекомендаций новым пользователям, в ос- нове которого лежат идеи перехода от матрицы «пользователь–предмет» к ра- нжированию предметов и формирования рекомендаций пользователю актив- ного кластера на основе построения результирующего ранжирования, которое представляет собой медиану Кемени на множестве ранжирований. Обоснован выбор медианы Кемени в качестве результирующего ранжирования, а также выбор алгоритма ее построения. Для снижения сложности вычислений пред- ложено осуществлять агрегацию информации и использовать при формирова- нии рекомендации ранжирования, построенные на множестве «обобщенных экспертов» для данного кластера. Исследована эффективность разработанного алгоритмического обеспечения, приведены результаты и рекомендации. Ключевые слова: рекомендательная система, согласованное коллективное ранжирование, медиана Кемени.
id	journaliasakpiua-article-228372
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:27:05Z
publishDate	2020
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/15/b1ff8575248b384b97f91e2bb6a70715.pdf
spelling	journaliasakpiua-article-2283722021-04-08T14:17:06Z Use of Kemeny median in the algorithm of forming recommendation Использование медианы Кемени в алгоритме формирования рекомендаций Використання медіани Кемені в алгоритмі формування рекомендацій Zhurakovska, Oksana Kochubey, Illa recommender system consensus ranking Kemeny median рекомендаційна система узгоджене колективне ранжування медіана Кемені рекомендательная система согласованное коллективное ранжирование медиана Кемени The relevant nowadays question of development of the algorithmic support of recommender systems is considered. The article is devoted to the solution of the problem of forming recommendations to new users, which is based on the ideas of transition from the matrix "user-object" to the ranking of objects and the formation of recommendations to the user of the active cluster based on the construction of the resulting ranking, which is a Kemeny median on a set of rankings. The choice of Kemeny median as the resulting ranking and the choice of algorithm for its construction are justified. To reduce the complexity of calculations, it is suggested to perform aggregation of information and to use it in forming of ranking recommendations, which are based on a set of "generalized experts" for this cluster. The efficiency of the developed algorithmic support was studied and the results and recommendations were given. Рассмотрен актуальный в настоящее время вопрос разработки алгоритмического обеспечения рекомендательных систем. Робота посвящена решению проблемы формирования рекомендаций новым пользователям, в основе которого лежат идеи перехода от матрицы "пользователь–предмет" к ранжированию предметов и формирования рекомендаций пользователю активного кластера на основе построения результирующего ранжирования, которое представляет собой медиану Кемени на множестве ранжирований. Обоснован выбор медианы Кемени в качестве результирующего ранжирования, а также выбор алгоритма ее построения. Для снижения сложности вычислений предложено осуществлять агрегацию информации и использовать при формировании рекомендации ранжирования, построенные на множестве "обобщенных экспертов" для данного кластера. Исследована эффективность разработанного алгоритмического обеспечения, приведены результаты и рекомендации. Розглянуто актуальне питання розроблення алгоритмічного забезпечення рекомендаційних систем. Роботу присвячено вирішенню проблеми формування рекомендацій для нових користувачів, в основі якого лежать ідеї переходу від матриці "користувач–предмет" до ранжувань предметів та формування рекомендацій для користувача активного кластера на основі побудови результуючого ранжування, що являє собою медіану Кемені на множині ранжувань. Обґрунтовано вибір медіани Кемені як результуючого ранжування, а також вибір алгоритму її побудови. Для зменшення складності обчислень запропоновано здійснювати агрегацію інформації та використовувати під час формування рекомендації ранжування, побудовані для множини "узагальнених експертів" для даного кластера. Досліджено ефективність розробленого алгоритмічного забезпечення, наведено результати та рекомендації. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-12-29 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/228372 10.20535/SRIT.2308-8893.2020.4.05 System research and information technologies; No. 4 (2020); 59-69 Системные исследования и информационные технологии; № 4 (2020); 59-69 Системні дослідження та інформаційні технології; № 4 (2020); 59-69 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/228372/227492
spellingShingle	рекомендаційна система узгоджене колективне ранжування медіана Кемені Zhurakovska, Oksana Kochubey, Illa Використання медіани Кемені в алгоритмі формування рекомендацій
title	Використання медіани Кемені в алгоритмі формування рекомендацій
title_alt	Use of Kemeny median in the algorithm of forming recommendation Использование медианы Кемени в алгоритме формирования рекомендаций
title_full	Використання медіани Кемені в алгоритмі формування рекомендацій
title_fullStr	Використання медіани Кемені в алгоритмі формування рекомендацій
title_full_unstemmed	Використання медіани Кемені в алгоритмі формування рекомендацій
title_short	Використання медіани Кемені в алгоритмі формування рекомендацій
title_sort	використання медіани кемені в алгоритмі формування рекомендацій
topic	рекомендаційна система узгоджене колективне ранжування медіана Кемені
topic_facet	recommender system consensus ranking Kemeny median рекомендаційна система узгоджене колективне ранжування медіана Кемені рекомендательная система согласованное коллективное ранжирование медиана Кемени
url	https://journal.iasa.kpi.ua/article/view/228372
work_keys_str_mv	AT zhurakovskaoksana useofkemenymedianinthealgorithmofformingrecommendation AT kochubeyilla useofkemenymedianinthealgorithmofformingrecommendation AT zhurakovskaoksana ispolʹzovaniemedianykemenivalgoritmeformirovaniârekomendacij AT kochubeyilla ispolʹzovaniemedianykemenivalgoritmeformirovaniârekomendacij AT zhurakovskaoksana vikoristannâmedíanikemenívalgoritmíformuvannârekomendacíj AT kochubeyilla vikoristannâmedíanikemenívalgoritmíformuvannârekomendacíj

Використання медіани Кемені в алгоритмі формування рекомендацій

Institution

Ähnliche Einträge