Серия «Естественные и Технические науки» # Январь  2016

В статье рассматриваются три алгоритма нахождения итогового ранга. Описывается численный эксперимент, в результате которого выявлена зависимость между точностью определения результирующего ранга и числом экспертов, числом рангов и коэффициента конкордации. Показано преимущества использования метода Шульце перед алгоритмами нахождения медианы Кемени. Ключевые слова: Медиана Кемени, метод Шульце, ранжирование, статистика.

ВВЕДЕНИЕ

Проблема ранжирования объектов на основании мнения экспертов, как предмет теории принятия решения, исследована достаточно полно. В отечественной квалитологии наибольшую известность имеет так называемая медиана Кемени. Как показал анализ публикаций, основным методом получения результирующих рангов в отечественных научных разработках является подход, описанный Б. Г. Литваком, включающий в себя эвристический и комбинаторный алгоритмы [1, c. 82-88] и метод, основанный на сведении задачи к задаче линейного программирования (задаче о назначениях) при отыскании медианы Кемени на векторах предпочтений [1, c. 88-89]. Из зарубежных исследований следует отметить работу [2], в которой рассматриваются существующие алгоритмы нахождения медианы Кемени и предлагается три подхода, воплотившиеся в пакете расширения для R ConsRank [3]:

• Предложенные авторами статьи[2] FAST и QUICK алгоритмы;
• метод ветвей и границ, описанный в работе [4].

На основании подходов, описанных в статье [5], ранее был реализован алгоритм, основанный на модифицированном расстоянии между рангами, равном числу перестановок в алгоритме пузырьковой сортировки, и сводящий задачу нахождения медианы Кемени к задаче линейного программирования (ЛП). Также был реализован метод Шульце на основе алгоритма Флойда — Уоршелла, показавший высокую эффективность [6].  Для решения задачи упорядочивания объектов по методике, описанной в [6], необходимо выбрать наиболее эффективный и робастный из перечисленных выше алгоритмов. Следовательно, постановку эксперимента можно описать нижеследующим образом.

Пусть имеется случайная матрица рангов ||a_ij||_n×m, где n – число экспертов, а m – число ранжируемых объектов. Предположим, что все строки матрицы заполнены одинаковыми случайными рангами, без повторов от 1 до m, где 1 – наиболее предпочтительный объект. Произведем случайную перестановку рангов двух объектов во все строки, начиная со второй, имитируя таким образом помехи при оценке. Первую строку матрицы оставим без изменения, чтобы снизить вероятность возникновения парадокса Кондорсе. Дизайн эксперимента можно описать следующим образом:

• число ранжируемых объектов m от трех до восьми включительно;
• число экспертов n равно: 4, 8, 16, 32, 64, 128, 256, 512;
• число тестов для каждой пары n и m – 100.
• сравниваемые алгоритмы: QuickCons из пакета R, модифицированные к входным данным разработанные программы, по алгоритмам описанным в статье [6]. Для ускорения вычисления алгоритм нахождения конценсуса по методу Шульце был переписан на C++.

Итого необходимо провести 4800 тестов. Цель эксперимента: установить способность алгоритмов восстанавливать первоначальную последовательность после внесения случайных помех.

Следует отметить, что в исследовании [7] уже был проведен ряд серий численных экспериментов по изучению свойств выборочных медиан Кемени. «В каждой серии методом статистических испытаний определенное число раз моделировался случайный и независимый выбор экспертных ранжировок, а затем находились все медианы Кемени для смоделированного набора мнений экспертов. При этом в сериях 1-5 распределение ответа эксперта предполагалось равномерным на множестве всех ранжировок, а в серии 6 это распределение являлось монотонным относительно расстояния Кемени с некоторым центром» [7] Однако проведенный численный эксперимент, описанный в настоящей статье, отличается простой повторяемостью результатов благодаря открытым исходным кодам программы эксперимента, большим исследуемым диапазоном для монотонного расстояния Кемени, а также применением для эксперимента не только алгоритмов отыскания медианы Кемени, но и метода Шульце. Для воспроизводимости результатов протокол испытания, а также результаты эксперимента доступны по URL: https://github.com/Tushavin/RANKING.

Проведенный эксперимент показал, что скорость нахождения консенсуса методом Шульце в среднем на три порядка выше, чем у остальных алгоритмов (см. рис. 1). На рисунке 2 представлена диаграмма Венна, показывающая пересечения множества найденных решений. Как видно из схемы, существуют расхождения, и наиболее заметно они проявляются при нахождении медианы Кемени методом линейного программирования. Как показал анализ данных эксперимента (доступно в виде файла Excel по приведенной выше ссылке), программа на основе ЛП не находит правильное решение  в случае, если число экспертов равно четырем, а число оцениваемых параметров - трём. Точность ранжирования для программ составила (в скобках указан 95% доверительный интервал):

• Шульце (C++) [6]:  0.804 (0.793, 0.815);
• из пакета ConsRank [3]: 0.808 (0.796, 0.819);
• Метод линейного программирования (R) [5,6]: 0.761 (0.748; 0.773).

Читать полный текст статьи …

СПИСОК ЛИТЕРАТУРЫ:
1. Литвак Б. Г. Экспертная информация: Методы получения и анализа. – М. : Радио и связь, 1982 – 184 с.
2. Amodioa S., D’Ambrosio A., Sicilianob R. Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach // European Journal of Operational Research. 2016, Vol. 249, Issue 2, P. 667–676. DOI: 10.1016/j.ejor.2015.08.048
3. D'Ambrosio A., Amodio S. ConsRank: Compute the Median Ranking(s) According to the Kemeny's Axiomatic Approach [R package version 1.0.2]. 2015. URL: http://CRAN.R-project.org/package=ConsRank
4. Emond, E., & Mason, D. A new rank correlation coefficient with application to the consensus ranking problem // Journal of Multi-Criteria Decision Analysis. 2002, no. 11(1), 17–28
5. Conitzer V., Davenport A., Kalagnanam J. Improved Bounds for Computing Kemeny Rankings // AAAI'06: Proceedings of the 21st National Conference on Artificial Intelligence, 2006 Vol. 1. P. 620-626
6. Тушавин В. А. Ранжирование показателей качества с использованием методов Кемени-Янга и Шульце // Экономика и менеджмент систем управления. 2015. № 4.4 (18). С. 497–503
7. Орлов А.И., Жихарев В.Н. Законы больших чисел и состоятельность статистических оценок в пространствах произвольной природы // Статистические методы оценивания и проверки гипотез. Межвузовский сборник научных трудов. - Пермь: Изд-во Пермского государственного университета, 1998. С.65-84.
8. Walker S. H., Duncan D. B. Estimation of the probability of an event as a function of several independent variables// Biometrika. 1967. Vol. 54, No. 1/2 (Jun., 1967), pp. 167-179. doi:10.2307/2333860
9. Breiman L, Friedman J, Stone C. J., Olshen R.A. Classification and Regression Trees (Wadsworth Statistics/Probability). Chapman and Hall/CRC. 368 p.
10. Therneau T., Atkinson B, Ripley B. rpart: Recursive Partitioning and Regression Trees [R package version 4.1-10]. 2015. URL: http://CRAN.R-project.org/package=rpart.