Дослідження можливостей швидкого обчислення медіаних консенсусних ранжувань
DOI:
https://doi.org/10.15587/1729-4061.2018.140686Ключові слова:
колективне експертне оцінювання, медіанні консенсусні ранжирування, задача про призначенняАнотація
Досліджено можливість швидкого обчислення колективних експертних оцінок медіанного типу. Незважаючи на широке застосування для розрахунку колективних експертних оцінок медіан Кемені-Снелла і Кука-Сейфорда, недостатньо досліджені можливості скорочення часу обчислення медіанного консенсусного ранжирування шляхом застосуванням задачі про призначення і відомих алгоритмів її рішення. На відміну від більшості відомих методів пропонований в статті метод не є наближеним і зберігає вихідну медіанну аксіоматику Кемені.
Досліджено можливість розрахунку медіан Кемені-Снелла і Кука-Сейфорда із застосуванням задачі про призначення методами комп'ютерного експерименту. Оцінено час рахунку медіанних ранжирувань чотирма різними алгоритмами рішення задачі про призначення. Встановлено, що запропонованим методом при помірній кількості альтернатив (n<50) медіанні ранжирування розраховуються в режимі часу, близькому до реального. Показано також, що на відміну від інших методів час обчислення медіанних ранжирувань за допомогою задачі про призначення не залежить від ступеня узгодженості індивідуальних експертних ранжирувань.
Отримані результати корисні для практичного застосування дослідженої процедури в мережевих експертних системах. У таких системах час обчислення консенсусного ранжирування має бути близьким до реального. Крім того, в мережевих системах експертизи за рахунок випадкового комплектування колективу експертів можливий низький рівень узгодженості індивідуальних ранжирування. Для дослідженої процедури це не впливає на тривалість розрахунку. Це дозволяє рекомендувати розроблену обчислювальну процедуру швидкого пошуку медіанних консенсусних ранжирувань за Кемені-Снеллом і Куком-Сейфордом для практичного застосування в системах колективної мережевої експертизи
Посилання
- 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
- 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.
- 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
- 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.
- 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
- 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.
- 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
- 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
- Burkard, R. (2009). Assignment Problems. Society for Industrial and Applied Mathematics. Philadelphia, 382.
- 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
- Moulin, H. (1983). The strategy of social choice. Vol. 18. Advanced Textbooks in Economics. Elsevier, 226.
- Heckelman, J., Miller, N. (2015). Handbook of social choice and voting. Edward Elgar Publishing, 424. doi: https://doi.org/10.4337/9781783470730
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- Samohvalov, Yu. Ya., Naumenko, E. M. (2007). Ekspertnoe ocenivanie. Metodicheskiy aspekt. Kyiv: DUIKT, 262.
- 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.
- Mack, C. (1969). The Bradford method for the assignment problem. New Journal of Statistics and Operational Research, 1, 17–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.
- Eddous, M., Stensfild, R.; Eliseeva, I. I. (Ed.) (1997). Metody prinyatiya resheniy. Moscow: Audit, YuNITI, 590.
- Ramshaw, L., Tarjan, R. E. (2012). On Minimum-Cost Assignments in Unbalanced Bipartite Graphs. HP Laboratories, HPL-2012-40R1, 91.
- 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
- 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.
- 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
- 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
- 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
- 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.
- 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.
- Sprent, P., Smeeton, N. C. (2007). Applied nonparametric statistical methods. CRC Press Taylor & Francis Group, 544.
- Kraska-Miller, M. (2013). Nonparametric statistics for social and behavioral sciences. CRC Press, 260. doi: https://doi.org/10.1201/b16188
- Kobzar', A. I. (2006). Prikladnaya matematicheskaya statistika. Dlya inzhenerov i nauchnyh rabotnikov. Moscow: FIZMATLIT, 816.
- 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
- 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##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2018 Viktor Boltenkov, Varvara Kuvaieva, Oleg Galchonkov, Alesya Ishchenko
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.