Содержание к диссертации
Введение
1 Проблематика обработки данных в порядковых шкалах для систем поддержки принятия решений 10
1.1 Общее состояние 12
1.2 Основные понятия 13
1.2.1 Оснооные понятия о структурировании множества объектов 14
1.2.2 Отношения и представления отношений 15
1.2.3 Меры близости на отношениях 17
1.2.4 Коллективные решения, результирующее ранжирование 19
1.2.5 Аксиомы Эрроу 21
1.3 Научная проблема 22
1.4 Постановка задач исследований 26
2 Методы и алгоритмы поиска результирующих ранжирований 28
2.1 Исходные данные 28
2.1.1 Суммарные матрицы отношений 29
2.1.2 Матрица весов 30
2.2 Методы, использующие меру близости на отношениях 31
2.2.1 Медиана Кемени 31
2.2.2 Тривиальные методы нахождения Медианы Кемени 32
2.2.3 Эвристический алгоритм 33
2.2.4 Полный перебор строгих ранжирований 34
2.2.5 К-медиана 34
2.2.6 Мультипликативная свертка 35
2.3 Метод минимального несогласия 35
2.3.1 Метод минимального несогласия для векторов предпочтений 35
2.3.2 Меры близости на отношениях порядка 37
2.3.3 Метод минимального несогласия 38
2.3.4 Вычисление элемента матрицы потерь 40
2.3.5 Случай нестрогих ранжирований 41
2.4 Свертки рангов 42
2.4.1 Линейная свертка рангов 43
2.4.2 Оценка достоверности ответа... 44
2.4.3 Мультипликативная свертка рангов 45
2.5 Методы, использующие матрицу весов 46
2.5.1 Модифицированный метод большинства 46
2.5.2 Правило большинства 48
2.5.2.1 Алгоритм 1 48
2.5.2.2 Алгоритм 2 49
2.5.2.3 Алгоритм 3 49
2.5.3 Метод Копленда 50
2.5.4 Правило Блэка 50
2.5.5 Квантильный метод 51
2.6 Преобразование рангов 52
2.7 Спортивный турнир 54
2.8 Собственные вектора 54
2.9 Метод ELECTRE 55
2.10 Получение ранжирования из матрицы отношений 57
2.11 Выводы 58
3 Методы и алгоритмы поиска результирующих ранжирований для данных с пропусками 59
3.1 Общее состояние 59
3.2 Модель Цермело-Бредли-Тири 61
3.3 Модель Леонардо 62
3.4 Модель Девидсона 63
3.5 Обобщение метода строчных сумм 63
3.6 Линейная модель 65
3.7 Коррекция итоговых весов объектов.,.. 67
3.8 Пополнение матриц 68
3.9 Пропорциональный метод 69
3.10 Метод зависимостей 70
3.11 Выводы 73
4 Методы и алгоритмы предварительной обработки данных и анализа решений 74
4.1 Предварительная обработка данных 74
4.1.1 Согласованность данных 74
4.1.2 Разреженность матриц отношений 75
4.1.3 Определение значимости ответов 76
4.1.4 Статистический анализ рангов 76
4.1.5 Выделение из множества ранжирований групп с высокой согласованностью 76
4.2 Анализ решений 77
4.2.1 Построение частотных гистограмм расстояний до образца 78
4.2.2 Чувствительность решения 78
4.3 Множество Парето 79
4.3.1 Множество Парето для ранжирований 79
4.3.2 Алгоритм формирования матрицы множества Парето 80
4.4 Диалога-машинная процедура поиска итогового ранжирования 82
4.4.1 Выделение наилучших и наихудших объектов 83
4.4.2 Выбор методов получения результирующего ранжирования 84
4.5 Оценки данных анкетирования 86
4.5.1 Классы эквивалентностей 86
4.5.2 Алгоритм вычисления максимально возможного расстояния до фиксированной группировки 86
4.6 Задача о назначениях в порядковых шкалах 88
4.7 Выводы 91
5 Программная реализация и примеры практического применения 92
5.1 Программная система "Обработка информации в порядковых шкалах" 92
5.1.1 Общее описание 92
5.1.2 Особенности применения 93
5.1.3 Настройка системы на предметную область задачи 95
5.1.4 Ввод и редактирование исходных данных 95
5.1.5 Расчет оптимальных ранжирований и их характеристик 97
5.1.6 Тестирование 99
5.1.7 Задача о назначениях 100
5.2 Практическое применение 102
5.2.1 Анализ эффективности коэффициентов согласованности и методов поиска результирующего ранжировання 102
5.2.2 Рейтинг крупнейших банков России 106
5.2.3 Задача о назначениях 109
5.2.4 Тестирование студентов 110
5.3 Выводы 112
Заключение 113
Список литературы 115
Приложение А. Алгоритм полного перебора строгих ранжирований с процедурой оптимизации 121
Приложение Б. Венгерский алгоритм 125
Приложение В. Акты об использовании результатов диссертационного исследования 128
- Общее состояние
- Методы, использующие меру близости на отношениях
- Обобщение метода строчных сумм
- Предварительная обработка данных
Введение к работе
Актуальность. Управление организациями в условиях функционирования систем менеджмента качества (СМК) возможно только па базе систем поддержки принятия решений (СППР) как инструмента использования информационных технологий. В сложных организационно-технических системах информация представлена как в количественных, так и в порядковых шкалах. Порядковая шкала позволяет устанавливать соотношения равенства, неравенства и последовательности между уровнями при отсутствии точки отсчета и расстояния между ними. Такие шкалы— естественный инструмент получения экспертных данных. Ранжирование объектов па основе экспертной информации играет важную роль для принятия решений в вопросах экономики, управления, политики, здравоохранения, спорта, образования и в других областях [1-6]. Так же упорядочивание объектов но предпочтению используется в ряде методов многокритериальной оптимизации [7-11]. В СППР может быть много компонентов накопления и обработки разнородной информации (формирование баз данных, оптимизация, статистическая обработка количественной информации и др.). В результате с помощью СППР формируется набор допустимых решений. Предложенные решения необходимо представить в виде упорядоченной последовательности (ранжирования) для выбора окончательных вариантов. Поэтому важнейшими компонентами СППР являются подсистемы обработки информации в порядковых шкалах. Такая обработка данных необходима как па нижних уровнях СППР (обработка первичной информации), так и на верхних — для принятия окончательных решений. Таким образом, математическое и алгоритмическое обеспечение СППР обязательно включает методы и алгоритмы обработки информации в порядковых шкалах. Сравнение в порядковых шкалах выполняется с помощью бинарных (или п-арных) отношений, обладающих некоторыми специальными свойствами (отношения порядка). В данной работе рассматриваются ранжирования (отношения линейного и частичного порядка) и классы эквивалентаостей.
Для обработки качественной информации используются функции предпочтений пользователя, математическое программирование в порядковых шкалах, специальные методы для особых типов данных. В настоящее время методы и алгоритмы обработки информации в порядковых шкалах недостаточно проработаны для включения их в математическое обеспечение СППР, что затрудняет создание соответствующих программных компонент. Проблемам обработки информации в порядковых шкалах и методам получения результирующего ранжирования посвящены работы зарубежных ученых (Р. Л. Кини, X. Райфа, Р. Р. Девидсона, Д. Блэка), а также работы В. В. Подиновского, Б. Г. Литвака, Д. Б. Юдина и др. [12-41]. Общие вопросы обработки экспертной информации и поддерж-
ки принятия решений освещены в работах [42-53], [54-65] и [66-72]. Одна из основных задач обработки данных в порядковых шкалах — получение результирующего ранжирования (задача группового выбора), для решения которой известно более десятка методов [1, 2, 9, 18, 20, 72]. При высокой согласованности данных все методы, как правило, приводят к одинаковым результатам. На практике, когда согласованность данных невысока, применение известных методов дает противоречивые результаты, что затрудняет использование их в СППР. Необходима более глубокая теоретическая переработка существующей совокупности методов, рассмотрение их с единых позиций, представление в виде комплекса методов с возможностью их сравнения по выработанным критериям.
Это обусловливает актуальность задачи совершенствования математического и алгоритмического обеспечения СППР для обработки данных в порядковых шкалах, позволяющего выполнять ранжирование как исходных данных, так и порождаемых внутри СППР при работе других подсистем (например, в ходе имитационного моделирования с последующей экспертной оценкой).
Объектом исследований в диссертации является система поддержки принятия ре-
i шений для задач, в которых часть данных представлена в порядковых шкалах.
Предметом исследований являются методы, модели и алгоритмы обработки данных в порядковых шкалах.
Научная задача заключается в том, чтобы для ряда практических задач принятия решений выявить характерные для них особенности исходных данных в порядковых шкалах (в виде ранжирований или матриц отношений) и разработать комплекс адекватных им методов и алгоритмов для получения результирующих ранжирований.
Цель работы — разработка и унификация математического и алгоритмического обеспечения подсистемы получения результирующего ранжирования в системах поддержки принятия решений для задач обработки информации в порядковых шкалах.
Для достижения поставленной цели в диссертации поставлены и решены следующие задачи:
классификация исходных данных для выбора алгоритмов их предварительной обработки и методов получения результирующих ранжирований;
выявление свойств существующих методов получения результирующего ранжирования применительно к типу исходных данных и свойств полученных решений;
разработка новых и модификация существующих методов и алгоритмов получения результирующих ранжирований с целью расширения класса решаемых задач;
разработка диалоговых процедур для управления процессом обработки данных в порядковых шкалах;
5) разработка и исследование комплекса алгоритмов и реализующего его программного обеспечения для подсистемы получения результирующего ранжирования в системах поддержки принятия решений.
Методы исследований: При выполнении работы использовались элементы теории многокритериальной оптимизации (решающие правила, множество Парето), дискретного программирования, комбинаторики (элементы теории графов, бинарные отношения), теории вероятностей. Эффективность методов и алгоритмов исследована с помощью численных экспериментов.
Основная идея диссертации заключается в том, чтобы распространить подходы, применяемые для анализа информации в количественных шкалах, на порядковые шкалы с учетом их специфики с разработкой новых или соответствующей модификацией существующих методов и алгоритмов.
Основные результаты:
На основе анализа существующих методов получения результирующего ранжирования выполнена унификация их математического описания, обоснованы рекомендации по их применению и выполнена их модификация в части реализующих их алгоритмов, а также вновь разработаны и алгоритмизированы методы для специальных типов данных (модифицированный метод большинства, метод минимального несогласия, модификация метода ELECTRE, к-медиана и мультипликативная свертка критериев качества, метод преобразования рангов, а также для неполный парных сравнений — линейная модель, пропорциональный метод, методы зависимостей и пополнения матриц). Предложены и обоснованы оценки чувствительности и достоверности решений.
Разработан оригинальный алгоритм предварительной обработки данных, учитывающий их пропуски и согласованность, модифицирован алгоритм очистки слабо согласованных данных и алгоритм определения компетентности эксперта на основе статистики его ответов.
Разработан алгоритм управления получением результирующего ранжирования со стороны ЛПР фиксированием ранга объекта или отношения между парами объектов с представлением множества Парето в виде одной матрицы и визуализацией решений (через расстояния между решениями и частотные гистограммы).
Предложена и реализована процедура оценивания в порядковых шкалах результатов тестирования в форме ранжирований объектов или разделения объектов на классы эк-вивалентностей.
Выполнена постановка задачи оптимального распределения ресурсов (задачи о назначениях) с исходными данными в виде ранжирований. Предложен и реализован подход
сведения этой задачи к классической постановке в количественных шкалах с помощью
меры близости па отношениях,
Разработан комплекс алгоритмов для обработки данных в порядковых шкалах (в том числе построение матрицы множества Парето, вычисление максимального расстояния между классами эквивалептностеи, вычисление матрицы потерь для метода минимального несогласия) с исключением вечного цикла в Венгерском алгоритме и настройкой алгоритма перестановок на тип решаемой задачи.
Создана диалоговая программная система, реализующая разработанный комплекс алгоритмов первичной обработки данных и получения результирующих ранжирований, протестированная на автоматически сгенерированных начальных данных с заданными (для тестирования) характеристиками.
Научная новизна полученных результатов.
Разработаны новые, а также модифицированы существующие методы и алгоритмы поиска результирующего ранжирования, на основе исследования их свойств сформулированы рекомендации для их выбора в соответствии с типом исходных данных.
Разработан оригинальный алгоритм предварительной обработки данных, учитывающий их пропуски и согласованность, модифицирован алгоритм очистки слабо согласованных данных и алгоритм определения компетентности эксперта на основе статистики его ответов.
С помощью меры близости на отношениях задача оптимального распределения
ресурсов (задача о назначениях) с исходными данными в виде ранжирований сведена к
классической постановке в количественных шкалах.
4. Разработан комплекс алгоритмов для обработки данных в порядковых шкалах,
обеспечивающих построение матрицы множества Парето, вычисление максимального
расстояния между классами эквивалептностеи, вычисление матрицы потерь для метода
минимального несогласия, исключён вечный цикл в Венгерском алгоритме, обеспечена
возможность настройки алгоритма перестановок на тип решаемой задачи.
Значение для теории заключается в систематизации основных методов и алгоритмов решения задач в порядковых шкалах с их сравнением, уточнением области применения, разработкой новых методов и алгоритмов.
Значение для практики заключается в расширении области применения и повышении эффективности вычисления результирующих ранжирований за счёт возможности использования их при слабо*-согласованных данных и в случае неполных парных сравнений. Реализованная диалого-машинная процедура обеспечивает проведение вычислительных
экспериментов для анализа эффективности различных методов и выработки рекомендаций к их применению.
Результаты диссертации использованы в системе менеджмента качества подготовки специалистов Красноярского государственного технического университета (КГТУ) и в региональной системе управления качеством медицинской помощи на территории Красноярского края, что подтверждено соответствующими актами.
Личный вклад автора состоит в постановке задачи исследования, разработке комплекса методов и алгоритмов обработки информации в порядковых шкалах и его программной реализации.
Результаты диссертации были апробированы на Всероссийской научно-методической конференции в 2004 году [73] (Даничев, А. А. Обработка экспертной информации в порядковых шкалах / М. А. Воловик, А. А. Даничев // Материалы Всероссийской научно-методической конференции 24—26 марта 2004. — Совершенствование системы управления качеством подготовки специалистов. — Красноярск: ИПЦ КГТУ), а так же на семинарах кафедр САУП и САПР КГТУ.
Публикации по материалам диссертации включают 5 работ, из них: 4— статьи в сборниках научных работ [74-77]; 1 — программа для электронных вычислительных машин, зарегистрированная в "Национальном информационном фонде неопубликованньк документов" [78].
Общая характеристика диссертации. Диссертация состоит из 5 разделов, содержит основной текст на 130 с, 29 иллюстраций, 23 таблицы, список использованных источников из 103 наименований.
Общее состояние
Процесс получения экспертных данных в порядковых шкалах довольно прост: объекты либо непосредственно ранжируются экспертом, либо производятся парные сравнения объектов друг с другом. Способы и приемы получения экспертных оценок [87-89]. довольно хорошо изучены. В зависимости от поставленной задачи отыскивается либо наилучший объект, либо результирующее ранжирование (упорядочивание) объектов. Исходные данные представляют собой результаты парных сравнений [2, 14]. Это могут быть упорядочивания экспертами объектов в порядке предпочтительности, результаты спортивных состязаний и т.д. Можно выделить три случая.
1) Исходные данные представлены ранжированиями объектов в порядке их предпочтения или соответствующими ранжированиям матрицами отношений.
2) Матрицы парных сравнений (соответствующие мнениям экспертов или результатам спортивного турнира) не транзитивны. В этом случае они не соответствуют ранжированиям. Например, студент считает дисциплину А более важной, чем дисциплина Б, "Б предпочтительней дисциплины С, но С почтительней дисциплины А.
3) Исходные данные имеют пропуски. Например, не все команды сыграли друг с другом, или эксперт не может сравнить некоторые объекты.
Для получения результирующего ранжирования разработаны различные методы [1, 2, 3, 9, 84]: метод Борда, правило большинства, вычисление медианы Кемени и прочие. В случае 2) многие методы нельзя применять. Из нетранзитивной, матрицы, с помощью, например, метода строчных сумм можно получить ранжирование. Но при этом часть исходной информации будет п/этеряна, искажена. Известно несколько методов для исходных данных с пропусками [1, 13, 20]. Они разработаны для случая недостоверных данных (например, по результатам спортивного турнира предсказать победителя).
В случае высокой согласованности исходных данных все методы, как правило, приводят к одинаковым результатам. Однако на практике согласованность редко бывает высока, и применение этих методов дает противоречивые результаты. Поэтому вопрос использования того или иного метода требует соответствующего обоснования. Это обоснование также может быть получено от экспертов в соответствующей предметной области на основании верификации полученных результатов с использованием множества различ- пых методов. Поэтому целесообразно использовать различные методы с их последующим сравнением и интерпретацией в рассматриваемой предметной области.
Существуют разнообразные программные системы с исходными данными в количественных шкалах, например, система "Expert choice", основанная па методе анализа иерархий (МАИ) Саати [90, 91]. Основная трудность использования этого метода и подобных ей систем — необходимость количественной оценки для предпочтений между объектами [27, 32,92].
Существуют системы (например [93]), в которых используются функции предпочтений пользователя (ФП). Пусть объект имеет некоторый набор харшстеристик. Необходимо упорядочить однотипные объекты. Экспертиза заключается в формировании ФП: указывается, как соотносятся между собой два объекта при всех возможных значениях их характеристик. Далее различные множества объектов автоматически, упорядочиваются. Недостаток такого подхода, заключается в том, что для пользователя формирование ФП — трудоемкая задача, и в случае, когда количество характеристик велико проще непосредственно сравнить объекты между собой.
Существует несколько компьютерных систем, реализующих методы из семейства ELEKTRE [18]. В отличие от МАИ, в методах ELECTRE не определяется количественно показатель качества каждого объекта, а устанавливается лишь условие превосходства од ного объекта над другим. Недостатком методов ELECTRE является то, что они являются вспомогательными средствами, а не способом выработки лучшего решения. Отсутствие методической литературы и малое количество специалистов в данной области приводит к негативной ситуации с практическим применением методов поиска результирующего ранжирования— на практике подобные задачи решаются редко, и за частую неграмотно. Программные системы, позволяющие находить результирующее ранжирование без участия специалистов, разбирающихся в тонкостях математического аппарата, в настоящее время не известны.
Системы "ПРОТОТИП" П.В Горского и "Экспертные оценки" компании ОАО "Вол гоинформесть", реализующие метод строчных сумм — первые шаги в этой области. Ниже рассмотрены основные термины и понятия, необходимые для дальнейшего изложения.
Основные понятии о структурировании множества объектов
Рассмотрим задачу упорядочивания объектов. Т.е. согласно некоторому критерию или решающему правилу на основе нескольких критериев, "лучшим" (1-м в рейтинге, наилучшим по предпочтению) признается объект я4, следующим по предпочтению следует объект ah и т.д.
В теории многокритериального анализа метод упорядочивания объектов принято называть решающим правилом. Решающих правил разработано большое количество. Выбор конкретного правила для решения практической задачи определяется из особенностей соответствующей предметной области.
Большинство решающих правил работает с количественными оценками объектов по критериям. Однако эти оценки могут иметь нечеткий характер (например, получены с большой погрешностью) и решающие правила, использующие, например, суммы или произведения оценок, могут привести к ошибочным результатам. Существуют специальные методы для интервальных оценок, оценок в виде балов и прочие [9].
Методы, использующие меру близости на отношениях
Медиана Кемени представляет собой аддитивную свертку без весовых коэффициентов: ДД) = Х (Д) гшп. =і Медиана совпадает с упорядочиванием по методу П. Слайтера. Так же медиане равно, если существует, упорядочивание Кондорсе (принцип выбора Кондорсе рассмотрен в разделе 1.2.4).
Вычисление медианы через суммарные матрицы из раздела 2.1.1 позволяет учитывать различные, заложенные в них, параметры и значительно сократить время вычислений. Пусть матрица отношений \Щтят соответствует искомому упорядочиванию Д, пред ставленному вектором индексов объектов (pi,pi,—,pm). Таким образом, матрица отношений с] г соответствует строгому ранжированию и tpi,Pl =1 для всех i j. Исходные данные представлены матрицами отношений f MXW, соответствующими ранжированиям ft. Расстояние от произвольного ранжирования до всех ранжирований, указанных экспертами, определяется по формуле.
Задача вычисления медианы Кемени может быть сформулирована как задача отыскания такого упорядочения объектов, а следовательно, строк и столбцов матрицы JV , чтобы сумма ее элементов, расположенных над диагональю, была максимальна (что соответствует упорядочиванию согласно принципу Кондорсе). Действительно, если P = (pi,p2,...,pm)- вектор индексов упорядочивания объектов по принципу Кондорсе, то для i j Np,-pi NP,P, и сумма NPiPI максимальна. Использование Щ = Ыд+0.5Щ можно назвать обобщением принципа Кондорсе для случая нестрогих ранжирований. Если искомое ранжирование нестрогое, его можно представить в виде упорядочивания множеств R={u\,U2,...,Un,-). Множества и содержат индексы равноценных объектов. Задача оптимизации в этом случае tn -l т mu пи tn "UJ-l Wit Алгоритмы поиска медианы приведены только для строгого результирующего ранжирования, так как эвристические алгоритмы для связанных рангов неизвестны, а перебор всех возможных нестрогих ранжирований неприемлемо ресурсоемок.
Тривиальные методы нахождения Медианы Кемени
Пусть количество повторов у всех ранжировании одинаково, т — число элементов ранжирования, п — количество различных ранжирований в начальных данных. Тогда: если н = т[, то медианы— вес ранжирования; если п = т\-1 и отсутствует ранжирование Р = (рі,рг,...,рт),то медианой будет ранжирование P = (p/n,p„-i,...,pi) О, —индекс объекта, расположенного на / -м месте).
Эвристический алгоритм
В [2] приводиться эвристический алгоритм вычисления альтернативы Кондорсе. Приведенный ниже алгоритм отличается тем, что вместо матрицы потерь используется матрица N (2ЛЗ). Вычисляется строгое ранжирование. Алгоритм применяется только для транзитивной матрицы W. Матрицу N называют транзитивной, если N1 N ji как только Й №и N kj N)k. 1) Проверка матрицы N на транзитивность. 1.1) Выполнить для г, j — 1 ..т ІФ j: Если Щ Np, то-. 1.1.1) Для k l.jnt k i, к j: если Nlk N ki и Nlj Njk, то данное множество ранжирований не обладает свойством Кондорсе, конец; 2) Вычисление вспомогательного упорядочения Р!. т т 2.1) Подсчитаем s\ =У]М у» —, =5 - Найдем Si\ = maxs). Объект дл ставим на первое место в искомом ранжировании. Вычеркивая в N строку и столбец с номером h получаем новую матрицу N 1, множество индексов строк и столбцов которой соответ-ственно Р =Jl ={I,,..,m}\/]. п 2.2) В матрице N k ] подсчитаем sf = N y , і є /а_1 . Найдем Sn = max 5 . Объект ац ставим на /t-e место в искомом ранжировании. Вычеркивая в N k l строку и столбец с номером ik получаем матрицу JV , множество индексов строк и столбцов которой соответственно / =Jk ={l,...,m}\{/! . ..,/ }. 2.3) Алгоритм завершается после т-й итерации /m =Jm - 0. Получено упорядоче ние Р[ =(ш і,...,ши). 3) Последовательно проверяем справедливость соотношений N i&k+i N nn-Uk, к = т-\, m-2,. ..1. Как только для некоторого к оно нарушено, объекты ац и а,ы вран жировании меняем местами, а соотношение Л% +і iWif проверяем, начиная с объекта непосредственно предшествующему объекту, подвергшемуся перестановке. После конечного числа шагов будет получено итоговое упорядочивание Pff, для которого условие оптимальности по Кондорсе выполнено. 2.2.4 Полный перебор строгих ранжирований Строгое ранжирование можно представить перестановкой множества индексов объ-i ектов. В [94] приводятся 3 алгоритма генерирования всех ml перестановок множества из /«элементов. Для вычисления медианы Кемени автором выбран алгоритм, в котором каждая последующая перестановка образуется в результате выполнении однократной трапе-позиции соседних элементов, что позволяет избежать вычисления суммы (2.12) для каждой перестановки. Для новой перестановки вместо.
Рассмотрен известный метод получения результирующего ранжирования, сводящийся к решению задачи о назначениях. Показано, что применение меры близости на векторах предпочтений для данного метода не корректно. Предложено использовать для построения матрицы потерь меру близости на матрицах отношений. В результате разработан новый метод получения результирующего ранжирования— метод минимального несогласия. Рекомендации к применению данного метода такие же, как у медианы Кемени, но для данного метода возможно получать решения при большом числе случаев нетранзитивности данных, а так же для большого числа ранжируемых объектов.
Обобщение метода строчных сумм
Исходные данные представлены матрицами отношений Тк = k L m к = \..п с элементами: математическое ожидание неопределенного элемента г , Выполняются следующие ограничения; В случае, когда матриць! отношений не имеют пропусков, обобщенные строчные суммы совпадают с обычными строчными суммами. Если имеют место пропуски, то xt задаются математическим ожиданием Ет.
В [20] П. Ю. Чеботарев предлагает обобщение метода строчных сумм, основанное на предположении, что математическое ожидание пропорционально разности оценок сравниваемых объектов:
Таким образом, получаем систему линейных уравнений:
При є = 0 обобщенные строчные суммы совпадают с неполными строчными суммами, которые, очевидно, дают неправильное итоговое упорядочивание. Какие-либо оценивания є, произведенные автором, не показали улучшение результата. Рекомендуется устанавливать для Е наибольшее значение.
Па рисунке 3.2 изображены функции у(х() = ЕТЩ), xj= const (m = 6, /1 = 300). Точками изображены графики для метода Чеботарева, сплошными линиями — для линейной модели (раздел 3.6). Жирные линии соответствуют случаю Xj = -300, тонкие —- случаю Xj = 300. Заметим, что для линейной модели Er(tjj) P(at etj)-Р(щ «,).
Вместо матриц / используем, для оптимизации, суммарные матрицы Л ]тхл, (2.6) и I L. (2 Так данная система не всегда имеет решение, ищется решение, дающее наименьшую ошибку.
В численных экспериментах данный метод приводит к более корректным результатам и менее ресурсоемок, чем описанные выше методы. Однако наличие многих пропусков делает ответ слабо обоснованным и непредсказуемым (несколько раз упорядочивание, согласно суммам .г,-, было противоположно истинному). Поэтому рекомендуется проверять полученное упорядочивание с помощью методов из разделов 3.2 или 3.6.
Линейная модель
Предлагается следующая модель. Каждому объекту щ соответствует его "сила" х;. Вероятности того, что объект at предпочтительнее объекта aj и что объекты равноценны, не зависят от результатов других сравнений и равны
Коррекция итоговых весов объектов
Приведенные ниже преобразования весов, позволяют применять к вектору весов, полученному по любой из моделей, оценки достоверности ответов из раздела 2.4.2.
Зафиксируем в модели (3.1) вес х,- и посмотрим, как завит вероятность Р(а, 0/) от і веса ХІ. Вес изменяется х,- от 1 до 1801. Зафиксируем xj =601. На рисунке 3.4 изображены: пунктиром — вероятность того, что объект а, более предпочтителен, чем объект aj (у = Xt/(x, + Xj) ) и точками — вероятность того, что объект a j более предпочтителен, чем объект сц (y = x,/(xi +х,) Рисунок 3.4 — Вероятность предпочтительности объекта
К подобным кривым так же приводят модели Леонардо и Девидсона. Это следствие сильного предположения, о том, что вероятности предпочтений объектов задаются отношением их весов. Представляется, что подобные кривые должны быть симметричны относительно прямой у = xj, приближаться к нулю и единице в крайних значениях х,. Подобные требования выполняются для линейной модели. В линейной модели и методе Чеботарева вероятности предпочтений объектов пропорциональны разности весов, и полученные веса соответствуют строчным суммам матриц (пополненных этими методами). Для оценки достоверности ответов из раздела 2.4.2 необходимо преобразовать вектор весов. Строчные суммы лежат в интервале [0,1], поэтому
Для моделей Цермело-Бредли-Тири, Леонардо, Девидсона необходимо, предварительно, выполнить следующее преобразование: max X min X
Если при оценке достоверности ответов параметры хі были изменены, то, для применения метода пополнения матриц, необходимо произвести обратные преобразования параметров.
Пополнение матриц
В статистических моделях обьекты следует ранжировать в порядке убывания величия JC,- Однако, если, согласно полученным параметрам x рассчитать суммарные матрицы отношений, то они, как правило, будут сильно отличаться от исходных матриц. Действительно, получая упорядочивание согласно параметрам Xi, мы учитываем исходную информацию через "призму" статистической модели. Известно, что в случае матриц без пропусков данное упорядочивание совпадает с упорядочиванием по методу строчных сумм. Предлагается, согласно полученным величинам jc,- заполнить пропуски в исходных матрицах отношений, после чего применить к ним метод строчных сумм. Таким образом, исходная информация будет учтена максимально полно.
Предварительная обработка данных
Согласованность мнения экспертов принято оценивать по величине коэффициента конкордации Кендалла: сумма квадратов отклонений всех оценок рангов каждого объекта экспертизы от среднего значения. Коэффициент конкордации изменяется в диапазоне 0 Кс 1, причем О — полная несогласованность, 1 -— полное единодушие. Данный коэффициент возможно рассчитать только для данных, представленных ранжированиями.
Введем коэффициент конкордации, для данных представленных матрицами отношений:
Коэффициент изменяется в диапазоне 0 Ks 1. При высокой согласованности (Ks 0.6 или ЛГс 0.4) все методы, как правило, дают одинаковые решения. При низкой согласованности (Ks 0.2 или Кс 0Л) рекомендуется разбить исходные данные на группы с высокой согласованностью (раздел 4.1.5).
Для оценки числа случаев нетранзитивности в матрице N будем использовать коэффициент Чем сильнее отличается коэффициент Kst от пуля, тем более противоречивы исходные данные. При Kst, близком к единице, следует провести повторную экспертизу иначе, скорее всего, придется признать все объекты равноценными: метод строчных сумм работает некорректно (признает многие объекты равноценными), а вычисление медианы Кемени навряд ли можно обосновать.
Рассчитаем результирующее ранжирование несколькими методами и вычислим среднеарифметическое расстояний между полученными решениями:
Величина Кг примерно равна ошибке, с которой можно вычислить результирующее ранжирование. Компьютерное моделирование показало высокую корреляцию между значениями Кг и расстояниями от решений методов до известного правильного ранжирования.
4.1.2 Разреженность матриц отношений
Введем коэффициенты для оценки разреженности матриц парных сравнений Kz и Kio. При низких значениях коэффициентов необходимо применять метод зависимостей, или исключить из рассмотрения объекты с малым числом сравнений. Оценка пропусков, обусловленных тем, что объекты сравнивались не всеми экспертами: ,Определение значимости ответов Определим значимость ответа эксперта (вес ранжирования) на основе статистики его ответов. Статистический анализ рангов ,Статистический анализа рангов позволяет выполнить расчет математического ожидания, дисперсии, проверку гипотез о виде распределения или попарной независимости [97]. ,Выделение из множества ранжирований групп с высокой согласованно стью В 1977г. в [19] подробно рассматривался вопрос о выделении из множества ранжирований групп похожих друг на друга ранжирований и нестандартных ранжирований. При этом нестандартные ранжирования оказываются весьма далекими от истины, и исключение их из анализа улучшает результаты. Было показано, что наилучшие результаты можно получить, если рассмотреть не все стандартные ранжирования, а только "ядро" — наибольшую, наиболее плотную группу ранжирований. Так же была указана возможность выделить несколько ядерных групп, соответствующих разным правильным решениям. В качестве способа измерения близости двух ранжирований использовался показатель объекта в ранжировании R2. Критерием близости служило значение показателя Т (Г Т , Т = 6). Судя по отсутствию дальнейших публикаций, исследований по данному направлению больше не проводились.
Ниже предлагается алгоритм выделения нескольких ядерных групп, соответствующих разным решениям. Заметим, что для расчета Т следует использовать формулу (2.11) с показателем V = 2. Исходные данные— матрицы отношений Ti,T2,...,Tn. Рекомендуемые значение параметров: 7" = 2, Т" - max {st}, Tm = 0.75. На шаге 3 получаем ядро Go для единственного решения. В цикле 6-7 получаем ядра Gk, соответствующие различным решениям. На шаге 8 получаем множества G стандартных ранжирований, соответствующие различным решениям ("стандартные" — все те ранжирования, что входят в окрестность хотя бы одного ранжирования из ядра).
При создании подсистемы СППР для каждого из результирующих ранжирований, полученных одним или различными методами, разработаны следующие инструменты анализа: построение частотной гистограммы расстояний; вычисление расстояния до других решений (смотрите раздел 4.5); оценка чувствительность решения. 4.2.1 Построение частотных гистограмм расстояний до образца
Для некоторого ранжирования гистограмма строится следующим способом. Вычисляются расстояния от этого ранжирования до каждого ранжирования из исходных данных. Расстояние d между ранжированиями т объектов является целым числом в интервале от О до т(т — 1). Для каждого возможного значения d подсчитывается количество ранжирований Nd , расстояние до которых равно d . Например, на гистограмме А (рисунок 4.1, а) из пятидесяти ранжирований семи объектов, двадцать объектов находятся на расстоянии 2 от рассматриваемого ранжирования.
Допустим, необходимо сравнить два решения, отображаемых гистограммами А и Б. Решение А в целом близко к исходным данным, но сильно отличается от одного из исходных ранжирований. Если наличие одного значительного различая (Nd(38) = 1) приемлемо, то предпочтение следует отдать варианту А. В противном случае выбор следует остановить на варианте Б. Решение Б существенно отличается от исходных ранжирований (Nd = 10,14,1 б), но является приемлемым для всех экспертов.
