Высокие статистические технологии

Здравствуйте, Александр Иванович!

У меня к Вам следующий вопрос. Передо мной стоит задача обработать мнения экспертов, представленные в виде ранжировок без связей. Исходные данные предполагают (в большинстве случаев) количество экспертов не более 30 человек, количество объектов экспертизы – не более 10. Для ее решения я предполагаю использовать следующий подход.

1. Представление ранжировки в виде бинарного отношения. Общее количество ранжировок соответствует количеству экспертов.
2. Вычисление матрицы расстояний между мнениями экспертов с помощью подсчета несовпадений элементов двух бинарных отношений.
3. Анализ матрицы расстояний с помощью иерархических агломеративных методов, например, метода Уорда. На основе анализа дендрограммы построение разбиения множества экспертов на непересекающиеся подмножества, однородные в смысле высказанных мнений.
4. Вычисление для каждого из выделенных подмножеств экспертов медианы Кемени, как итогового мнения данной подгруппы экспертов. Медина ищется как решение оптимизационной задачи в классе ранжировок.

Меня интересуют следующие моменты:

1. Как считать медиану Кемени? Полный перебор всех бинарных отношений из класса ранжировок и поиск среди них удовлетворяющего решению оптимизационной задачи весьма затруднителен с вычислительной точки зрения. В Вашей книге «Нечисловая статистика» я нашел (с. 375): «Вычисление медианы Кемени - задача целочисленного программирования. Для ее нахождения используется различные алгоритмы дискретной математики, в частности, основанные на методе ветвей и границ. Применяют также алгоритмы, основанные на идее случайного поиска, поскольку для каждого бинарного отношения нетрудно найти множество его соседей». Подозреваю, что в книге «Кемени Дж., Снелл Дж. Кибернетическое моделирование: Некоторые приложения. - М.: Советское радио, 1972. - 192 с.» должно быть подробное описание этого вопроса. Подскажите, пожалуйста.
2. Как быть в том случае, если входные данные представлены в виде кластеризованных ранжировок? Измениться ли тогда решение задачи согласно п. 1-4 выше?

Заранее спасибо.

Уважаемый Константин!

Ваш подход (шаги 1-4) - вполне естественный. Я бы делал аналогично. Целесообразно применить одновременно несколько разных алгоритмов кластер-анализа, например, ближнего соседа и дальнего соседа, и выделить общее в получяенных разбиениях.
Подход годится и для кластеризованных ранжировок, поскольку расстояние Кемени определяется для них аналогично случаю ранжировок без связей, через матрицы бинарных отношений.
А вот с вычислением медианы Кемени ситуация хуже. В учебнике Кемени и Снелла об этом ничего нет. Алгоритм разработан в книге:
Литвак Б.Г. Экспертная информация. Методы получения и анализа.
- М.: Радио и связь, 1982. -184 с.
К сожалению, он не прост. И другие тоже разрабатывали алгоритмы. После скоропостижной смерти моего сотрудника В.Н.Жихарева осталась его рукопись на эту тему.
Из-за сложности вычисления медианы Кемени она сравнительно редко применяется.
Думаю, что для практического использования можно порекомендовать искать итоговое мнение комиссии экспертов - аналог медианы Кемени не среди всех ранжировок, а только среди указанных экспертами. Тогда расчет может быть сделан и вручную, как в примерах в моих книгах.
Дополнительный аргумент - итоговое мнение - аналог медианы Кемени - при этом содержится среди названных экспертами ранжировок, что исключает эффект "центра бублика", когда ответы экспертов мы представляем себе распределенными примерно равномерно по поверхности бублика, а медиана попадает в пустоту - центр бублика.
Дополнительное использование - выделяется "наиболее представительный" эксперт - тот, чье мнение совпало с итоговым мнением комиссии экспертов.

УБРАНО в знак несогласия

Наивных (?) авторов подвело незнание терминологии и теории бинарных отношений.

1. Фактически они описывают получение среднего множества по правилу большинства.
Такое усреднение ответов экспертов, представленных в виде подмножеств конечного множества, является частным случаем эмпирического среднего в пространствах произвольной природы.
Этот простой результат я обычно рассказываю студентам 3-го (курсы "Прикладная статистика", "Эконометрика", МГТУ им.Баумана) или 4-го (курс "Математические методы качественной информации", РЭА им. Плеханова) года обучения.
Так что текст Глухова и Погодаева можно рассматривать как методическую разработку для студентов 3-4 курса, содержащую пример практического использования эмпирического среднего и соответствующую примерно 20 минутам лекционного курса.

2. Термин "медиана Кемени" используется для описания усреднения ответов экспертов, представленных в виде бинарных отношений из определенного класса (упорядочений, или отношений эквивалентности, и т.п.), когда среднее ищется среди бинарных отношений того же класса как решение оптимизационной задачи.
Алгоритм, описанный в тексте Глухова-Погодаева (а на самом деле известный в нашей стране с того момента, как в СССР прочитали работы Кемени - с начала 70-х), не дает возможности получить медиану Кемени. Это связано с тем, что вектор, рассчитанный по правилу большинства в п.2 алгоритма, может не соответствовать ни одному из элементов рассматриваемого класса бинарных отношений. Например, может нарушаться свойство транзитивности. Конечно, это вектор соответствует некоторому бинарному отношению А. Но нет никаких гарантий, что это бинарное отношение А входит в класс упорядочений, хотя все ответы экспертов - упорядочения.
Найти решение задачи оптимизации в заданном классе бинарных отношений существенно труднее, чем применить тривиальную процедуру правила большинства.
Именно поэтому сложны алгоритмы Б.Г. Литвака, В.Н.Жихарева и др. по нахождению медианы.

3. Как обычно у наивных авторов, БОЛЬШОЕ ЗАБЛУЖДЕНИЕ ДОПОЛНЯЕТСЯ МАЛЫМИ. На с.43 сказано: "решение оптимизационной задачи есть один из ответов экспертов". Зачем же тогда рассказывать про правило большинства? Достаточно перебрать суммы расстояний в количестве, равном числу экспертов, и выбрать наименьшую.
Из сказанного ранее ясно, что такой способ усреднения - выбрать мнение одного эксперта - не дает медиану Кемени. Другое дело, что он представляет собой достаточно разумный способ нахождения итогового мнения комиссии экспертов.

4. В опусе Глухова-Погодаева буквальным образом повторяются мои формулировки, как из учебника, так и из текстов в настоящей теме
http://forum.orlovs.pp.ru/posting.php?mode=reply&t=349
Например, о "центре бублика".
При этом ссылок на меня нет.
На общение с Глуховым я потратил достаточно много времени. И вот благодарность!

Добрый день!

Согласен с мнением Александра Ивановича, что описанный алгоритм не позволяет вычислить медиану Кемени в классе ранжировок. Для вычисления медианы я использовал алгоритм, разработанный Б. Г. Литваком и описанный в книге: Литвак Б.Г. Экспертная информация. Методы получения и анализа. - М.: Радио и связь, 1982. -184 с. (см. дискуссию выше). Я вычислял медиану Кемени только для строгих ранжировок. Действительно, алгоритм достаточно сложен. Если искать решение задачи в классе кластеризованных ранжировок, то сложность алгоритма повышается. Кстати, результаты практического применения разработанной программы, показали, что «эффект бублика» возникает достаточно редко. Мне, например, так и не удалось на реальных данных получить что-либо подобное. Еще хотелось бы отметить, что далеко не всегда в практических приложениях имеет смысл искать именно точное решение задачи. Поиск медианы Кемени среди исходных данных, т.е. исходной ранжировки, которая наименее удалена от всех остальных исходных, дает очень неплохие результаты. Весьма часто, особенно при небольшом 5-6 числе альтернатив, имеет место совпадение с точной ранжировкой. Если же совпадения не наблюдается, то ранжировка, полученная прямым поиском, очень близка в смысле расстояния Кемени к точной ранжировке. А если учесть затраты времени на написание и отладку ПО, то я считаю возможным рекомендовать именно такой подход.
Конечно, предварительно, приходилось прибегать к классификации мнений несколькими иерархическими агломеративными методами с целью выделения однородных групп экспертов в отношении высказанных мнений. Использовал даже процедуры 2-мерного шкалирования, потому что там очень хорошо видно выбросы и группы экспертов.

Да, и большое спасибо Александру Ивановичу за содержательную информацию по поиску медианы Кемени. Очень помогло.

УБРАНО в знак несогласия

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

Современное представление об экспертных оценках отражено в главе 12 учебника "Эконометрика" http://orlovs.pp.ru/econ.php#ek1, а также в статье "Экспертные оценки" http://orlovs.pp.ru/stat.php#s3p8.

Вчера читал очередную лекцию третьекурсникам по прикладной статистике.
Неожиданно сыграл опус Погодаева-Глухова.
Рассказал я, как обычно каждый год, о нахождении среднего множества, и сказал:
"То, что вы услышали, только что проректор и аспирант из провинциального технического университета опубликовали как результат своих научных изысканий. Так что вы находитесь на переднем крае научно-технического прогресса. А то, о чем сейчас говорил Алексанлр Лебедев (студент-третьекурсник), - это уже заявка на прорыв в непознанное. Так что дерзайте, исследуйте, пишите статьи".
Так что в педагогических целях текст Погодаева-Глухова оказался полезен.

удалено

А перед Б.Г. Литваком не хотите извиниться?
Он так много занимался алгоритмом нахождения медианы Кемени, придумал сложный метод. А вы - раз и готово, вот вам "медиана Кемени" Даже две. Фактически вы объявили, что Литвак - дурак.

УБРАНО в знак несогласия

1. Первое верно, второе - нет:

В книге Орлова нет алгоритма вычисления медианы Кемени.
2.
n! растет весьма быстро с ростом n. Никакой компьютер не сможет перебрать 100! вариантов (если компьютер сделан из атомов, скорость передачи информации не превышает скорости света, верно соотношение неопределенностей Гейзенберга и компьютер по размерам не превосходит Солнечную систему).
3. Неверно:

По определению медиана ищется среди всех элементов соответствующего пространства бинарных отношений. Нельзя подменять понятия.
4. Не имеют смысла слова:

Ранжировки - частный случай бинаных отношений.
5. Именно подмена понятий позволила Глухову и Погодаеву написать ту чушь, которую они опубликовали.
Вместо классической медианы Кемени, той, что у Литвака, они рассмотрели другое понятие.
А для этого другого понятия они напечатали как свое открытие то, что давно и хорошо известно.
Встает классический вопрос:
Что это - глупость или преступление?

УБРАНО в знак несогласия

В книге Орлова нет алгоритма вычисления медианы Кемени. Есть пример расчета эмпирического среднего.

УБРАНО в знак несогласия

В литературе термин "Медиана Кемени" стал использоваться неаккуратно. И польза от опуса Глухова-Погодаева в том, что выявилась необходимость разобрать различные варианты употребления этого термина в связи с решаемыми задачами анализа экспертных оценок. Иначе неясно, почему вычисление медианы Кемени трудно для Литвака, но легко для Глухова. О разном говорят эти авторы.
Напишу статью о медиане Кемени.

УБРАНО в знак несогласия

Конечно.
Книга Литвака вышла в 1982, алгоритм разработан в конце 70-х.
Любой современный персональный компьютер на порядки мощнее (по любым характеристикам) тогдашних ЭВМ.
Но и сейчас алгоритм Литвака интересен, чтобы проникнуть далее тех пределов, в которых достаточно перебора.
Правда, возникает вопрос - а что нужно для реальных экспертиз? Моя дипломница заставляла экспертов из НИИ космического приборостроения упорядочивать 15 факторов (при разработке системы ГЛОНАСС)... Кто больше?

УБРАНО в знак несогласия

Методов кластер-анализа бесконечно много.
Можно использовать разные расстояния и меры близости.
В пространстве ранжировок хорошо известны две системы аксиом.
Из одной вытекает расстояние Кемени, из другой - D-метрика.
См. соответствующие разделы в учебниках "Эконометрика" и "Прикладная статистика".

Игорь! Я имел ввиду классификацию ранжировок по следующей схеме. 1. Вычисляем расстояние Кемени между ранжировками, получаем матрицу расстояний n*n, где n - количество ранжировок, т.е. экспертов. Т.е. сначала переводим в бнарное отношение, затем считаем расстояние Кемени. 2. Классифицируем (автоматическая классификация) ранжировки, в качестве вхоных данных выступает матрица расстояний. Метод классификации - любой из иерархических агломеративных. Способ вычисления расстояние между группами ранжировок и обуславливает тот или иной метод классификации. Например, в методе "ближний сосед" расстояние между двумя группами объектов вычисляется как расстояние между двумя ближайшими объектами из этих групп. Далее снова подвергаем классификации все объекты, но уже другим методом и т.д. В результате, в соответсвии с концепцией стат. устойчивости, определяем наиболее устойчивое решение.
Действительно, алгоритмов классификации бесконечно много. Я же решил использовать иерархические агломеративные методы по двум причинам: 1. Объектов в моей задаче не много, не более нескольких десятков 2. Исходя из соображений программной реализации мне было проще использовать именно ИА методы. Что касается метода Уорда. Согласен с замечанием. Его применение обосновано в том случае, если мы использем количественные перменные, т.е. поскольку нам приходится вычислять среднее группы. Но некоторые статистические пакеты проводят классификацию по методу Уорда, когда входная информация представлена только (!) матрицей расстояний. Это я имел ввиду, говоря о методе Уорда применительно к калссификации ранжировок. Я, к сожалению, не понял как это делается в программе и соответсвующей теоретической информации не нашел. Но результат есть, он совпадает с результами по другим методам. Если кто знает, как проводить классификацию по методу Уорда, когда есть только матрица расстояний между объектами и ничего больше, буду признателен.

Хорошо читаете данный на сайте учебник "Прикладная статистика".

Здравствуйте!
Буду очень признательна за ответ.
У меня возникла задача схожая с задачей автора этой темы. В книге Литвака предложено несколько алгоритмов ее решения (эвристический, комбинаторный..) какой лучше использовать для программной реализации отыскания результирующей ранжировки.
Мне как не специалисту в этой области сложно быстро разобраться.

Советую обратиться непосредственно к Борису Григорьевичу Литваку http://www.bglitvak.ru/

Спасибо за ссылку.

Добрый день!
Подскажите, пожалуйста! Я не могу разобраться в комбинаторном алгоритме, описанном в книге Б. Г. Литвака "Экспертная информация. Методы получения и анализа."
А именно непонятна итерация 1 в разобранном примере на стр 87: у них H^(1) = B^(1) = 13, для r^(1). А по-моему, r^(1) должна быть пустая, и эти значения для неё не вычисляются. Даже если взять r^(1) такую же, как на предыдущей итерации, то почему нижняя граница H^(1) увеличилась?
Возможно, где-то ещё есть другое его изложение этого алгоритма? Или более подробно разобранные примеры?
Спасибо.

Медиану Кемени вычислял Дмитрий Андреевич Сумкин <dmitry.sumkin@phystech.edu>

Спасибо за информацию.