Дослідження можливостей швидкого обчислення медіаних консенсусних ранжувань

Автор(и)

  • Viktor Boltenkov Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044, Україна https://orcid.org/0000-0003-3366-974X
  • Varvara Kuvaieva Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044, Україна https://orcid.org/0000-0002-9350-1108
  • Oleg Galchonkov Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044, Україна https://orcid.org/0000-0001-5468-7299
  • Alesya Ishchenko Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044, Україна https://orcid.org/0000-0002-7882-4718

DOI:

https://doi.org/10.15587/1729-4061.2018.140686

Ключові слова:

колективне експертне оцінювання, медіанні консенсусні ранжирування, задача про призначення

Анотація

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

Досліджено можливість розрахунку медіан Кемені-Снелла і Кука-Сейфорда із застосуванням задачі про призначення методами комп'ютерного експерименту. Оцінено час рахунку медіанних ранжирувань чотирма різними алгоритмами рішення задачі про призначення. Встановлено, що запропонованим методом при помірній кількості альтернатив (n<50) медіанні ранжирування розраховуються в режимі часу, близькому до реального. Показано також, що на відміну від інших методів час обчислення медіанних ранжирувань за допомогою задачі про призначення не залежить від ступеня узгодженості індивідуальних експертних ранжирувань.

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

Біографії авторів

Viktor Boltenkov, Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044

Кандидат технічних наук, доцент

Кафедра інформаційних систем

Varvara Kuvaieva, Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044

Аспірант

Кафедра інформаційних систем

Oleg Galchonkov, Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044

Кандидат технічних наук, доцент

Кафедра інформаційних систем

Alesya Ishchenko, Інститут комп’ютерних систем Одеський національний політехнічний університет пр. Шевченка, 1, м. Одеса, Україна, 65044

Старший викладач

Кафедра прикладної математики та інформаційних технологій

Посилання

  1. Dopazo, E., Martínez-Céspedes, M. L. (2017). Rank aggregation methods dealing with ordinal uncertain preferences. Expert Systems with Applications, 78, 103–109. doi: https://doi.org/10.1016/j.eswa.2017.01.051
  2. Dodonov, A. G., Lande, D. V., Cyganok, V. V., Andreychuk, O. V., Kadenko, S. V., Grayvoronskaya, A. N. (2017). Raspoznavanie informacionnyh operaciy. Kyiv: OOO «Inzhiniring», 282.
  3. Gubanov, D., Korgin, N., Novikov, D., Raikov, A. (2014). E-Expertise: modern collective intelligence. Springer, 147. doi: https://doi.org/10.1007/978-3-319-06770-4
  4. Breslin, J., Bojars, U., Aleman-Meza, B., Boley, H., Mochol, M., Nixon, L. J. B. et. al. (2007). Finding experts using internet-based discussions in online communities and associated social networks. Proceedings of the 1st International Expert Finder Workshop at Knowledge Web General Assembly, 38–47.
  5. Wei, C.-P., Lin, W.-B., Chen, H.-C., An, W.-Y., Yeh, W.-C. (2015). Finding experts in online forums for enhancing knowledge sharing and accessibility. Computers in Human Behavior, 51, 325–335. 325–335. doi: https://doi.org/10.1016/j.chb.2015.04.055
  6. Kemeny, J. G., Snell, L. J. (1962). Preference ranking: an axiomatric approach, in: Mathematical Models in the Social Sciences. Ginn and Company, New York, 9–23.
  7. Cook, W. D., Seiford, L. M. (1978). Priority Ranking and Consensus Formation. Management Science, 24 (16), 1721–1732. doi: https://doi.org/10.1287/mnsc.24.16.1721
  8. Armstrong, R. D., Cook, W. D., Seiford, L. M. (1982). Priority Ranking and Consensus Formation: The Case of Ties. Management Science, 28 (6), 638–645. doi: https://doi.org/10.1287/mnsc.28.6.638
  9. Burkard, R. (2009). Assignment Problems. Society for Industrial and Applied Mathematics. Philadelphia, 382.
  10. Procaccia, A. D. (2011). Computational social choice. XRDS: Crossroads, The ACM Magazine for Students, 18 (2), 31. doi: https://doi.org/10.1145/2043236.2043249
  11. Moulin, H. (1983). The strategy of social choice. Vol. 18. Advanced Textbooks in Economics. Elsevier, 226.
  12. Heckelman, J., Miller, N. (2015). Handbook of social choice and voting. Edward Elgar Publishing, 424. doi: https://doi.org/10.4337/9781783470730
  13. Bartholdi, J., Tovey, C. A., Trick, M. A. (1989). Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6 (2), 157–165. doi: https://doi.org/10.1007/bf00303169
  14. Bury, H., Wagner, D. (2008). Group judgement with ties. Distance-based methods. New Approaches in Automation and Robotics, 153–172. doi: https://doi.org/10.5772/5393
  15. Ali, A., Meilă, M. (2012). Experiments with Kemeny ranking: What works when? Mathematical Social Sciences, 64 (1), 28–40. doi: https://doi.org/10.1016/j.mathsocsci.2011.08.008
  16. D’Ambrosio, A., Mazzeo, G., Iorio, C., Siciliano, R. (2017). A differential evolution algorithm for finding the median ranking under the Kemeny axiomatic approach. Computers & Operations Research, 82, 126–138. doi: https://doi.org/10.1016/j.cor.2017.01.017
  17. Aledo, J. A., Gámez, J. A., Molina, D. (2013). Tackling the rank aggregation problem with evolutionary algorithms. Applied Mathematics and Computation, 222, 632–644. doi: https://doi.org/10.1016/j.amc.2013.07.081
  18. Jackson, B. N., Schnable, P. S., Aluru, S. (2008). Consensus Genetic Maps as Median Orders from Inconsistent Sources. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5 (2), 161–171. doi: https://doi.org/10.1109/tcbb.2007.70221
  19. D'Ambrosio, A., Amodio, S., Iorio, C. (2015). Two algorithms for finding optimal solutions of the Kemeny rank aggregation problem for full rankings. Electronic Journal of Applied Statistical Analysis, 8 (2), 198–213. doi: https://doi.org/10.1285/i20705948v8n2p198
  20. Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., Rosamond, F. A. (2009). Fixed-parameter algorithms for Kemeny rankings. Theoretical Computer Science, 410 (45), 4554–4570. doi: https://doi.org/10.1016/j.tcs.2009.08.033
  21. Nápoles, G., Dikopoulou, Z., Papageorgiou, E., Bello, R., Vanhoof, K. (2015). Aggregation of Partial Rankings – An Approach Based on the Kemeny Ranking Problem. Lecture Notes in Computer Science, 343–355. doi: https://doi.org/10.1007/978-3-319-19222-2_29
  22. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1-2), 83–97. doi: https://doi.org/10.1002/nav.3800020109
  23. Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176 (2), 774–793. doi: https://doi.org/10.1016/j.ejor.2005.09.014
  24. Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5 (1), 32–38. doi: https://doi.org/10.1137/0105003
  25. Lelyakova, L. V., Haritonova, A. G., Chernyshova, G. D. (2017). Prikladnye zadachi o naznacheniyah (modeli, algoritmy resheniya). Vestnik VGU, Seriya: Sistemniy analiz i informacionnye tekhnologii, 2, 22–27.
  26. Samohvalov, Yu. Ya., Naumenko, E. M. (2007). Ekspertnoe ocenivanie. Metodicheskiy aspekt. Kyiv: DUIKT, 262.
  27. Boltenkov, V. A., Kuvaeva, V. I., Poznyak, A. V. (2017). Analiz mediannyh metodov konsensusnogo agregirovaniya rangovyh predpochteniy. Informatyka ta matematychni metody v modeliuvanni, 7 (4), 307–317.
  28. Mack, C. (1969). The Bradford method for the assignment problem. New Journal of Statistics and Operational Research, 1, 17–29.
  29. Jonker, R. (1989). Teaching linear assignment by Mack’s algorithm. Twenty-Five Years of Operations Research in the Netherlands: Papers Dedicated to Gijs de Leve, CWI Tract, 70, 54–60.
  30. Eddous, M., Stensfild, R.; Eliseeva, I. I. (Ed.) (1997). Metody prinyatiya resheniy. Moscow: Audit, YuNITI, 590.
  31. Ramshaw, L., Tarjan, R. E. (2012). On Minimum-Cost Assignments in Unbalanced Bipartite Graphs. HP Laboratories, HPL-2012-40R1, 91.
  32. Jonker, R., Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38 (4), 325–340. doi: https://doi.org/10.1007/bf02278710
  33. Brauner, N., Echahed, R., Finke, G., Gregor, H., Prost, F. (2004). A complete assignment algorithm and its application in constraint declarative languages. Cahier du laboratoire Leibniz No. 111, 60.
  34. Bast, H., Mehlhorn, K., Schafer, G., Tamaki, H. (2005). Matching Algorithms Are Fast in Sparse Random Graphs. Theory of Computing Systems, 39 (1), 3–14. doi: https://doi.org/10.1007/s00224-005-1254-y
  35. Amodio, S., D’Ambrosio, A., Siciliano, R. (2016). Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach. European Journal of Operational Research, 249 (2), 667–676. doi: https://doi.org/10.1016/j.ejor.2015.08.048
  36. Critchlow, D. E., Fligner, M. A., Verducci, J. S. (1991). Probability models on rankings. Journal of Mathematical Psychology, 35 (3), 294–318. doi: https://doi.org/10.1016/0022-2496(91)90050-4
  37. Farhadzade, E. M., Muradaliev, A. Z., Farzaliev, Yu. Z., Rafieva, T. K., Abdullaeva, S. A. (2017). Ocenka vzaimosvyazi tekhniko-ekonomicheskih pokazateley ob'ektov EES. Elektronnoe modelirovanie, 39 (6), 93–106.
  38. Antosiak, P. P. (2008). Dekompozytsiyni protsedury u zadachi znakhodzhennia strohoho rezultuiuchoho ranzhuvannia obiektiv u vyhliadi mediany Kemeni-Snella. Naukovyi visnyk Uzhhorodskoho universytetu, 17, 29–36.
  39. Sprent, P., Smeeton, N. C. (2007). Applied nonparametric statistical methods. CRC Press Taylor & Francis Group, 544.
  40. Kraska-Miller, M. (2013). Nonparametric statistics for social and behavioral sciences. CRC Press, 260. doi: https://doi.org/10.1201/b16188
  41. Kobzar', A. I. (2006). Prikladnaya matematicheskaya statistika. Dlya inzhenerov i nauchnyh rabotnikov. Moscow: FIZMATLIT, 816.
  42. Schach, S. (1979). An Alternative to the Friedman Test with Certain Optimality Properties. The Annals of Statistics, 7 (3), 537–550. doi: https://doi.org/10.1214/aos/1176344675
  43. Quade, D. (1979). Using Weighted Rankings in the Analysis of Complete Blocks with Additive Block Effects. Journal of the American Statistical Association, 74 (367), 680. doi: https://doi.org/10.2307/2286991

##submission.downloads##

Опубліковано

2018-08-16

Як цитувати

Boltenkov, V., Kuvaieva, V., Galchonkov, O., & Ishchenko, A. (2018). Дослідження можливостей швидкого обчислення медіаних консенсусних ранжувань. Eastern-European Journal of Enterprise Technologies, 4(4 (94), 27–35. https://doi.org/10.15587/1729-4061.2018.140686

Номер

Том 4 № 4 (94) (2018): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2018 Viktor Boltenkov, Varvara Kuvaieva, Oleg Galchonkov, Alesya Ishchenko

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.