Вычисление медианы Кемени - Задача исследования итогового ранжирования мнений группы экспертов с помощью медианы кемени

Если ответы экспертов - кластеризованные ранжировки, то вычисление медианы Кемени является задачей целочисленного программирования. Для ее нахождения используют различные алгоритмы дискретной математики, в частности, основанные на методе ветвей и границ, на разных подходах кластерного анализа. В настоящее время неизвестно ни одного точного алгоритма поиска множества всех медиан Кемени для заданного множества перестановок (ранжировок без связей), кроме полного перебора.

Однако существуют алгоритмы, разработанные российскими учеными Б. Г. Литваком [17], В. Н. Жихаревым [18].

Рассмотрим подход В. Н. Жихарева. Для практического использования вместо полного перебора и селекции множества всех медиан в множестве всех кластеризованных ранжировок (как он пишет - перестановок) В. Н. Жихарев предлагает эвристические алгоритмы [18], в которых исследует меньшие по количеству элементов множества - производные от совокупности экспертных ответов - и выделяет в них т. н. псевдомедианы в предположении, что псевдомедианы могут быть медианами. Псевдомедианы ищутся так же как медианы Кемени, только на выделенном множестве перестановок.

Псевдомедианой совокупности E экспертных перестановок в множестве V называется перестановка, pm(E, V), для которой сумма расстояний D(x, E) до элементов совокупности E принимает минимальное значение среди всех перестановок x множества V.

Жихарев использует также следующие понятия в пространстве G кластеризованных ранжировок (перестановок), которое рассматривается как граф (ребрами соединены перестановки, отличающиеся одной инверсией):

Сферой S(X, R) радиуса R с центром в точке (перестановке) X называется множество всех таких вершин (перестановок) y графа G, для которых выполняется условие D(X, y) = R.

Шаром B(X, R) радиуса R с центром в точке (перестановке) X называется множество всех таких вершин (перестановок) y графа G , для которых расстояние D(X, y) не превосходит R.

R - окрестностью B(V, R) множества перестановок V радиуса R называется объединение шаров радиуса R с центрами в точках Y множества V. В частности, B(V, 0) = V.

Границей (R - фронтом) S(V, R) R - окрестности B(V, R) множества перестановок V называется теоретико-множественная разность

B(V, R) - B(V, R - 1),

Причем S(V, 0) = V.

Центром C(V) множества V (центром минимальной окрестности) называется первое непустое по последовательности R = 0, 1, 2, ... пересечение всех шаров B(X, R) радиуса R с центрами во всех точках X множества V, а соответствующее минимальное значение R называется радиусом минимальной окрестности U(C(V), R), включающей в себя все элементы множества V.

Взвешенным (или смещенным) центром Cw(E) совокупности E называется первое непустое по последовательности R = 0, 1, 2, ... пересечение всех шаров B(X, [R/K(X)]) с центрами во всех точках X множества N(E) совокупности E, где K(X) - кратность элемента X в совокупности E, [R/K(X)] - целая часть рационального числа R/K(X).

Окрестность U(Cw(E), R) включает в себя все элементы множества N(E) совокупности E.

Используемые производные множества перестановок Жихарев строит путем нахождения центров множества ответов экспертов, далее алгоритмически специальным образом задаются сферы, шары, окрестности на данном множестве, тем самым ограничивая полный перебор на множестве всех перестановок экспертных ранжировок.

Дадим краткое описание алгоритмов В. Н. Жихарева.

Алгоритм 1.

    1. Построить центр C(N(E)) множества N(E) совокупности E. 2. Найти множество всех псевдомедиан PM(E, C(N(E))).

Алгоритм 2.

    1. Построить центр C(N(E)) множества N(E) совокупности E. 2. Построить окрестность U(C(N(E)), R), центра C(N(E)) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, U(C(N(E)), R)).

Алгоритм 3.

    1. Построить центр C(N(E)) множества N(E) совокупности E. 2. Построить шаровую окрестность B(E, R), произвольной точки E центра C(N(E)) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, B(E, R)).

Алгоритм 4.

    1. Построить смещенный центр Cw(E) совокупности E. 2. Найти множество всех псевдомедиан PM(E, Cw(E)).

Алгоритм 5.

    1. Построить смещенный центр Cw(E) совокупности E. 2. Построить окрестность U(Cw(E), R) центра Cw(E) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, U(Cw(E), R)).

Алгоритм 6.

    1. Построить смещенный центр Cw(E) совокупности E экспертных ответов. 2. Построить шаровую окрестность B(Ew, R) произвольной точки Ew смещенного центра Cw(E) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, B(Ew, R)).

Алгоритм 7.

    1. Старт: N = N1 = N(E), R = 3, N(E)- совокупность экспертных ответов. 2. Операция "захвата":

Построить окрестность B(N, R), где R - радиус окрестности, построенной в каждой из точек N.

3. Операция селекции:

Найти множество всех псевдомедиан N1 = PM(E, B(N, R)).

4. Условие остановки. Сравнить N и N1. Если N = N1, то остановка, иначе переход к п.2.

В работе В. Н. Жихарева использовалось несколько моделей ответов экспертов. В наиболее общей модели 1: совокупность экспертных ответов формируется методом случайной неупорядоченной выборки с повторениями, при этом любая перестановка множества X с одинаковой вероятностью может быть выбрана в качестве экспертного ответа. В модели 2: локализованная совокупность экспертных ответов, т. е. все экспертные ответы лежат внутри шара с фиксированным радиусом и равновероятны. |В модели 3: центрированная и локализованная совокупность экспертных ответов, т. е. существует одна "истинная" и наиболее вероятная перестановка - центр шара. Вероятности выбора других перестановок совокупности зависят от расстояния до центра шара.

В результате численных экспериментов В. Н. Жихарев проводит сравнение множества псевдомедиан, найденных с помощью предложенных эвристических алгоритмов, с множеством медиан Кемени, найденным им путем полного перебора (табл. 2). Жирным шрифтом в таблице указано описание серии экспериментов методом Монте-Карло, которое состоит из набора характеристических параметров, а именно:

Номер модели совокупности экспертных ответов,

Количество объектов,

Количество экспертов,

Количество испытаний (тестов).

(Например: 1-5-5-1000).

В первых двух колонках табл. 2 указан порядковый номер и "условный" символ алгоритма, разработанного В. Н. Жихаревым. Используя поочередно каждый из предложенных алгоритмов, автор сравнивает количество найденных псевдомедиан с числом медиан Кемени, вычисленным методом полного перебора на множестве всех перестановок X. В третьей, четвертой и пятой колонках указаны проценты испытаний (тестов) для каждого типа алгоритмов, в которых удалось найти все медианы Кемени, некоторые или ни одной. В последней колонке указаны средние отношения времени работы каждого тестируемого эвристического алгоритма ко времени работы алгоритма полного перебора.

В. Н. Жихарев выделяет один из предложенных им эвристических алгоритмов (номер 7 в таблице) в качестве наиболее эффективного по количеству найденных медиан в условиях наиболее общей модели ответов экспертов (модель 1). Однако, как показывают данные последней колонки табл.2, алгоритм полного перебора в большинстве экспериментов работает более быстро.

Таблица 2. Сводная таблица результатов испытаний поиска медиан Кемени по алгоритмам В. Н.Жихарева

Номер алгоритма

Символ алгоритма

Найдены все медианы

(% тестов)

Найдены не все медианы

(% тестов)

Не найдено ни одной медианы

(% тестов)

Относительное быстродействие

1-5-5-1000

1

C

23.7

13.7

62.6

3.9

2

U(C)

99.5

0.2

0.3

0.00087

3

U(Ce)

98.

1.2

0.8

0.001

4

Cw

24.7

14.

61.3

3.78

5

U(Cw)

99.5

0.2

0.3

1.23

6

U(Cwe)

98.

1.2

0.8

1.46

7

Move

100.

0

0

1.11

1-5-10-1000

1

C

7.4

38.1

54.5

1.7

2

U(C)

99.3

0.7

0

0.001

3

U(Ce)

94.2

5.7

0.1

0.0012

4

Cw

7.7

38.3

54

1.6

5

U(Cw)

99.3

0.7

0

0.69

6

U(Cwe)

94.8

5.1

0.1

0.76

7

Move

100.

0

0

0.81

1-7-5-61

1

C

14.7541

8.19672

77.0492

4.02

2

U(C)

100

0

0

0.0205

3

U(Ce)

98.3607

1.63934

0

0.0257

4

Cw

14.7541

8.19672

77.0492

4.04

5

U(Cw)

100

0

0

1.43

6

U(Cwe)

98.3607

1.63934

0

1.8

7

Move

95.082

4.91803

0

11.1

1-6-5-500

5

U(Cw)

100

0

0.3

1.3

7

Move

99.2

0.8

0

2.8

1-6-10-500

5

U(Cw)

99

1

0

2.63

7

Move

100

0

0

3.26

2-6-10-500

5

U(Cw)

100

0

0

4.4

7

Move

100

0

0

2.52

3-6-10-500

5

U(Cw)

100

0

0

2.3

7

Move

100

0

0

2.4

В. Н. Жихарев считает, что метод полного перебора на современных компьютерах может быть достаточно эффективно применен для поиска всех медиан Кемени при относительно небольшом количестве экспертов (для числа объектов в перестановке вплоть до восьми и даже девяти). Описанные выше эвристические алгоритмы созданы для решения более сложных задач: выявления каких-либо закономерностей при изучении взаимного расположения медиан по отношению к экспертной совокупности или экспертному множеству.

К недостаткам предложенных методов вычисления медианы Кемени В. Н. Жихарев относит тот факт, что множество, построенное на первом этапе этих алгоритмов, может оказаться слишком большим - сравнимым по размерам (по числу лементов) со множеством всех перестановок, и тогда на втором этапе фактически осуществляется полный перебор перестановок. Это обстоятельство следует иметь в виду прежде всего в том случае, когда имеется сильный разброс в ответах экспертов и они приблизительно могут быть описаны моделью №1. В этом случае может оказаться целесообразным не вычислять медианы, а провести новую экспертизу с другим подбором объектов [18].

В работе Б. Г. Литвака [17] предложены два алгоритма вычисления медианы Кемени: точный и эвристический. Расстояние от произвольного ранжирования P до всех ранжирований P1, ..., Pm определяется как:

,

Где

.

Используется матрица потерь с элементами:

.

Поиск медианы Кемени эквивалентен отысканию упорядочивания строк и столбцов матрицы потерь, обладающей минимальной суммой наддиагональных элементов. Точный алгоритм Литвака строится на теореме о необходимом и достаточном условии транзитивности матрицы потерь, обладающей свойством Кондорсе. Ранжирование P обладает свойством Кондорсе, если любое подмножество альтернатив обладает альтернативой Кондорсе. Пусть матрица потерь построена для единственного ранжирования P. Если в упорядочивании P альтернатива предпочтительнее альтернативы, то. Если в матрице потерь, как только и, такая матрица называется транзитивной. Матрица потерь может быть нетранзитивна в случае непоследовательности ответов экспертов при парных сравнениях. Пусть ранжирования P1, ..., PM обладают альтернативой Кондорсе - это означает, что матрица потерь содержит строку такую, что. Благодаря свойству транзитивности (последовательности экспертов в своих выборах) после удаления некой альтернативы, альтернативой Кондорсе становится.

Точный алгоритм Литвака использует метод ветвей и границ, в нем предполагается последовательное фиксирование расположения части альтернатив (наилучших альтернатив Кондорсе и наименее предпочтительных альтернатив), определение верхней и нижней границ значений целевой функции на уменьшенном таким образом множестве ранжирований и отбрасывание заведомо бесперспективных при поиске медианы Кемени вариантов. Точный алгоритм Б. Г. Литвака, в частности, описан Д. А. Сумкиным (в коллективной монографии [19]).

Если ранжирования P1, ..., Pm не обладают свойством Кондорсе, то Литвак предлагает использовать разработанный им эвристический алгоритм поиска медианы Кемени. В этом алгоритме на первом этапе последовательно находятся минимумы из сумм:

, ,

После чего соответствующую минимальной сумме

Альтернативу ставят на первое место, вычеркивая ее из матрицы потерь. Далее аналогичные действия проводятся с уменьшенной матрицей потерь до тех пор, пока не получится ранжировка: . На втором этапе для полученной ранжировки последовательно проверяются соотношения: . Как только для некоторого K оно нарушено, альтернативы и меняются местами в новом ранжировании. Данный алгоритм описан, например, в работе польских авторов [20].

Недостатком подходов Б. Г. Литвака является то, что предложенные методы поиска могут найти лишь одну медиану из большого множества возможных, поэтому в общем случае они должны быть модифицированы.

В простейшем случае, представляет интерес подсчет итогового мнения комиссии экспертов только среди указанных экспертами ответов ("модифицированная" медиана Кемени, предложенная в [21]).

Похожие статьи




Вычисление медианы Кемени - Задача исследования итогового ранжирования мнений группы экспертов с помощью медианы кемени

Предыдущая | Следующая