close

Вход

Забыли?

вход по аккаунту

?

bd000101347

код для вставкиСкачать
Ш^
На правах рукописи
Даничев
Алексей Александрович
Методы и алгоритмы обработки данных
в порадковых шкалах
для систем поддержки принятия решений
05.13.01 — системный анализ, управление и обработка информации
(по отраслям: информатика, вычислительная техника и управление)
Автореферат диссертации на соискание ученой степени
кандидата технических наук
Красноярск 2005
Работа выполнена
в Государственном образовательном учреждении
высшего профессионального образования
"Красноярский государственный технический университет"
Научный руководитель:
доктор технических наук, доцент
Бронов Сергей Александрович
Официальные оппоненты:
доктор технических наук, профессор
Медведев Александр Васильевич
доктор физико-математических наук, профессор
Носков Михаил Валерьянович
Ведущая организация:
Институт вычислительного моделирования
Сибирского отделения Российской Академии
наук (г. Красноярск)
Защита состоится
16 декабря 2005 года в
14:00 на заседании
диссертационного совета Д 212.098.04 при Красноярском государственном
техническом университете по адресу: ул. академика Киренского, 26, Красноярск,
660074, ауд.Д 501.
Факс:
E-mail:
Телефон:
(3912) 43-06-92 ( К Г Т У , для каф. С А П Р )
sovet@front.ru
(3912) 91-22-95 (каф. С А П Р )
С диссертацией можно ознакомиться
государственного технического университета.
в
библиотеке
Красноярского
Автореферат разослан 15 ноября 2005 г.
Ученый секретарь
диссертационного совета
д.т.н.
С.А.Бронов
_^fioej
M>jsr
iwmib
О б щ а я характеристика работы
Актуальность. Управление организациями в условиях функционирования
систем менеджмента качества ( С М К ) возможно только на базе систем поддержки
принятия решений (СППР) как инструмента использования информационных
технологий. В сложных организационно-технических системах информация
представлена как в количественных, так и в порядковых шкалах. Порядковая
шкала позволяет устанавливать соотношения
равенства, неравенства и
последовательности между уровнями при отсутствии точки отсчета и расстояния
между ними. Такие шкалы — естественный инструмент получения экспертных
данных. В С П П Р может быть много компонентов накопления и обработки
разнородной
информации
(формирование
баз
данных,
оптимизация,
статистическая обработка количественной информации и др.). В результате с
помощью С П П Р формируется набор допустимых решений. Предложенные
решения необходимо представить в виде упорядоченной последовательности
(ранжирования) для выбора окончательных вариантов. Поэтому важнейшими
компонентами С П П Р являются подсистемы обработки информации в порядкввых
шкалах. Такая обработка данных необходима как на нижних уровнях СППР
(обработка первичной информации), так и на верхних— для принятия
окончательных решений. Таким образом, математическое и алгоритмическое
обеспечение С П П Р обязательно включает методы и алгоритмы обработки
информации в порядковых шкалах. Сравнение в порядковых шкалах выполняется
с помощью бинарных (или «-арных) отношений, обладающих некоторыми
специальными
свойствами
(отношения
порядка).
В
данной
работе
рассматриваются ранжирования (отношения линейного и частичного порядка) и
классы эквивалентностей.
Для
обработки
качественной
информации
используются
функции
предпочтений пользователя, математическое программирование в порядковых
шкалах, специальные методы для особых типов данных. В настоящее время
методы и алгоритмы обработки информации в порядковых шкалах недостаточно
проработаны для включения их в математическое обеспечение СППР, что
затрудняет создание соответствующих программных компонент. Проблемам
обработки
информации
в порядковых
шкалах
и
методам
получения
результирующего ранжирования посвящены работы зарубежных ученых (Р. Л .
Кини, X . Райфа, Р. Р. Девидсона, Д. Блэка), а также работы В. В. Подиновского,
Б. Г. Литвака, Д. Б. Юдина и др. Одна из основных задач обработки данных в
порядковых шкалах — получение результирующего ранжирования (задача
группового выбора), для решения которой известно более десятка методов. При
высокой согласованности данных все методы, как правило, приводят к
одинаковым результатам. На практике, когда согласованность данных невысока,
применение известных методов дает противоречивые результаты, что затрудняет
использование их в СППР. Необходима более глубокая теоретическая переработка
существующей совокупности методов, рассмотрение их с единых позиций,
представление в виде комплекса методов с возможностью их сравнения по
РОС. НАЦИОНАЛЬНАЯ {
выработанным критериям.
БИБЛИОТЕКА
{
.v'rat!
Это обусловливает актуальность задачи совершенствования математического
и алгоритмического обеспечения СППР для обработки данных в порядковых
шкалах, позволяющего выполнять ранжирование как исходных данных, так и
порождаемых внутри С П П Р при работе других подсистем (например, в ходе
имитационного моделирования с последующей экспертной оценкой).
Объектом исследований в диссертации является система поддержки
принятия решений для задач, в которых часть данных представлена в порядковых
шкалах.
Предметом исследований являются методы, модели и алгоритмы обработки
данных в порядковых шкалах.
Научная задача заключается в том, чтобы для ряда практических задач
принятия решений выявить характерные для них особенности исходных данных в
порядковых шкалах (в виде ранжирований или матриц отношений) и разработать
комплекс адекватных им методов и алгоритмов для получения результирующих
ранжирований.
Цель
работы —
разработка
и- унификация
математического
и
алгоритмического
обеспечения
подсистемы
получения
результирующего
ранжирования в системах поддержки принятия решений для задач обработки
информации в порядковых шкалах.
Для достижения поставленной цели в диссертации поставлены и решены
следующие задачи:
1) классификация
исходных
данных
для
выбора
алгоритмов
их
предварительной
обработки
и
методов
получения
результирующих
ранжирований;
2) выявление свойств существующих методов получения результирующего
ранжирования применительно к типу исходных данных и свойств полученных
решений;
3) разработка новых и модификация существующих методов и алгоритмов
получения результирующих ранжирований с целью расширения класса решаемых
задач;
4) разработка диалоговых процедур для управления процессом обработки
данных в порядковых шкалах;
5) разработка и исследование комплекса алгоритмов и реализующего его
программного обеспечения для подсистемы получения результирующего
ранжирования в системах поддержки принятия решений.
Методы исследований: При выполнении работы использовались элементы
теории многокритериальной оптимизации (решающие правила, множество
Парето), дискретного программирования, комбинаторики (элементы теории
графов, бинарные отношения), теории вероятностей. Эффективность методов и
алгоритмов исследована с помощью численных экспериментов.
Основная идея диссертации заключается в том, чтобы распространить
подходы, применяемые для анализа информации в количественных шкалах, на
порядковые шкалы с учетом их специфики с разработкой новых или
соответствующей модификацией существующих методов и алгоритмов.
Основные результаты:
1. На основе анализа существующих методов получения результирующего
ранжирования выполнена унификация их математического описания, обоснованы
рекомендации по их применению и выполнена их модификация в части
реализующих их алгоритмов, а также вновь разработаны и алгоритмизированы
методы для специальных типов данных (модифицированный метод большинства,
метод минимального несогласия, модификация метода E L E C T R E , к-медиана и
мультипликативная свертка критериев качества, метод преобразования рангов, а
также для неполный парных сравнений—линейная модель, пропорциональный
метод, методы зависимостей и пополнения матриц). Предложены и обоснованы
оценки чувствительности и достоверности решений.
2. Разработан оригинальный алгоритм предварительной обработки данных,
учитывающий их пропуски и согласованность, модифицирован алгоритм очистки
слабо согласованных данных и алгоритм определения компетентности эксперта на
основе статистики его ответов.
3 .-Разработан
алгоритм
управления
получением
результирующего
ранжирования со стороны Л П Р фиксированием ранга объекта или отношения
между парами объектов с представлением множества Парето в виде одной
матрицы и визуализацией решений (через расстояния между решениями и
частотные гистофаммы).
4. Предложена и реализована процедура оценивания в порядковых шкалах
результатов тестирования в форме ранжирований объектов или разделения
объектов на классы эквивалентностей.
5. Выполнена постановка задачи оптимального распределения ресурсов
(задачи о назначениях) с исходными данными в виде ранжирований. Предложен и
реализован подход сведения этой задачи к классической постановке в
количественных шкалах с помощью меры близости на отношениях.
6. Разработан комплекс алгоритмов для обработки данных в порядковых
шкалах (в том числе построение матрицы множества Парето, вычисление
максимального расстояния между классами эквивалентностей, вычисление
матрицы потерь для метода минимального несогласия) с исключением вечного
цикла в Венгерском алгоритме и настройкой алгоритма перестановок на тип
решаемой задачи.
7. Создана диалоговая программная система, реализующая разработанный
комплекс алгоритмов первичной обработки данных и получения результирующих
ранжирований, протестированная на автоматически сгенерированных начальных
данных с заданными (для тестирования) характеристиками.
Н а у ч н а я новизна полученных результатов.
1. Разработаны новые, а также модифицированы существующие методы и
алгоритмы поиска результирующего ранжирования, на основе исследования их
свойств сформулированы рекомендации для их выбора в соответствии с типом
исходных данных.
2. Разработан оригинальный алгоритм предварительной обработки данных,
учитывающий их пропуски и согласованность, модифицирован алгоритм очистки
слабо согласованных данных и алгоритм определения компетентности эксперта на
основе статистики его ответов.
3. С помощью меры близости на отношениях задача оптимального
распределения ресурсов (задача о назначениях) с исходными данными в виде
ранжирований сведена к классической постановке в количественных шкалах.
4. Разработан комплекс алгоритмов для обработки данных в порядковых
шкалах, обеспечивающих построение матрицы множества Парето, вычисление
максимального расстояния между классами эквивалентностей, вычисление
матрицы потерь для метода минимального несогласия, исключён вечный цикл в
Венгерском
алгоритме,
обеспечена
возможность
настройки
алгоритма
перестановок на тип решаемой задачи.
Значение для теории заключается в систематизации основных методов и
алгоритмов решения задач в порядковых шкалах с их сравнением, уточнением
области применения, разработкой новых методов и алгоритмов.
Значение для практики заключается в расширении области применения и
повышении^эффективности вычисления результирующих ранжирований за счёт
возможности использования их при слабо-согласованных данных и в случае
неполных парных сравнений. Реализованная диалого-машинная процедура
обеспечивает
проведение
вычислительных
экспериментов
для
анализа
эффективности различных методов и выработки рекомендаций к их применению.
Результаты диссертации использованы в системе менеджмента качества
подготовки
специалистов
Красноярского
государственного
технического
университета ( К Г Т У ) и в региональной системе управления качеством
медицинской помощи на территории Красноярского края, что подтверждено
соответствующими актами.
Л и ч н ы й вклад автора состоит в постановке задачи исследования,
разработке комплекса методов и алгоритмов обработки информации в порядковых
шкалах и его программной реализации.
Результаты диссертации были апробированы на Всероссийской научнометодической конференции в 2004 году (Даничев, А. А. Обработка экспертной
информации в порядковых шкалах / М. А. Воловик, А. А. Даничев // Материалы
Всероссийской научно-методической конференции 24—26 марта 2 0 0 4 . —
Совершенствование системы управления качеством подготовки специалистов. —
Красноярск. И П Ц К Г Т У ) , а так же на семинарах кафедр С А У П и С А П Р К Г Т У .
Публикации по материалам диссертации включают 5 работ, из них: 4 —
статьи в сборниках научных работ; 1 —
программа для электронных
вычислительных машин, зарегистрированная в "Национальном информационном
фонде неопубликованных документов".
О б щ а я характеристика диссертации. Диссертация состоит из 5 разделов,
содержит основной текст на 130 с., 29 иллюстраций, 23 таблицы, список
использованных источников из 103 наименований.
Основное содержание работы
Во введении обоснована актуальность темы, определены цель и задачи
работы, отражены основные результаты, научная новизна, значение работы для
теории и практики, приведены сведенья об апробации.
В
первом разделе приводятся основные понятия и определения,
необходимые для представления и обработки данных в порядковых шкалах,
сделан обзор современного положения в области разработки математического и
программного обеспечения для обработки данных в порядковых шкалах.
Подробно рассмотрена научная проблема и выполнена постановка задачи.
В о втором разделе выполнен анализ существующих методов нахождения
результирующих ранжирований. С целью повышения их практической
значимости предложены модификации методов, введено унифицированное
математическое описание, указанно для каких типов данных их целесообразно
применять.
Методы
алгоритмизированы,
подготовлены
к
программной
реализации. Разработано 6 новых методов поиска результирующих ранжирований,
позволяющих получать корректный результат для новых типов данных.
Формат исходных данных унифицирован в виде суммарных матриц
отношений
и матрицы весов. Это
позволило
избежать
многократно
повторяющихся расчетов, упростить алгоритмы и расширить функциональные
возможности известных методов. Например, элемент N,, суммарной матрицы
отношений равен числу случаев, когда объект а, предпочтительнее объекта Uj.
Так как экспертам могут быть назначены (согласно их компетентности, важности)
веса Wk е [0,1], то
N,j=±Wk.
(1)
Предложена матрица весов, элемент которой v,j равен (для строгих
ранжирований) числу экспертов, поставивших в ранжировании г-й объект на 7-е
место:
V.J = Z vv* .
(2)
г,* -7
Для нестрогих ранжирований (когда объекты могут иметь равные ранги) в
диссертации предложен следующий алгоритм получения весов v,j:
1)
v,j =0,ддя
i,j = \..т;
к = \;
2)
Мк = max /-,^; шаги 2.1 и 2.2 можно пропустить;
1-1 т
2.1) Если Мк =\,то A,t =1, В,к =т
для i = ]..т;
шаг 5;
2.2) Если Мк =т , то Лк = Вл = i, для i = \..m; шаг 5;
3)
/;= 7 ^ + 1, для У = 5 3 ? : ;
4)
Д* = ОкруглитьВверхи^
Мк
1 , Д* = ОкруглитьВиизи^
] , г = 1 ..от;
Wlc
5)
Для ; = 1..7я и / = Д* .В, увеличить v„ на
;
6)
7)
Увеличить А: на 1; Если к<п ,го шаг 2;
Конец.
Для
вычисления
расстояний
между
ранжированиями
используют
разнообразные метрики. В разделе показано, что их применение не всегда
корректно. Известна формула, определяющая единственную меру близости
(согласно набору определенных аксиом) на эквивалентностях и на отношениях
частичного порядка:
d(,R,R,) = \^\t,j-ti\.
(3)
'■/=1
С введением меры близости на отношениях предлагается введение новых
критериев качества:
dk{R) = d{R,Rk) ■ Для вычисления
результирующего
ранжирования можно воспользоваться сверткой критериев. Подробно рассмотрена
аддитивная свертка без весовых коэффициентов, известная как медиана Кемени: ~
f(,R) = Y,d,{R)^mm.
(4)
t=i
Вычисление медианы через суммарные матрицы позволило учитывать различные
заложенные в них параметры и значительно сократить время вычислений. Если
искомое ранжирование нестрогое, его можно представить в виде упорядочения
множеств R = (u\,U2,...,Um). Множества Ut ={рк\,.-.,Рк т}
содержат индексы
равноценных объектов. Задача оптимизации в этом случае:
т'
1
т'
mici mi
t i = l i ; = t i . l 1=]
j'\
m' "1*1-1 mil
+z s z iKu.p.u - Ku.p.,) ^ ™n •
Также предложены две свертки.
К-медиана:
{т-\)
к
' ^ mm .
(5)
(6)
Мультипликативная свертка:
^(«)=Jn ,-fizii^)U.,x.
V.-iV
т{т-\)
(7,
J
С применением к ранжированиям свертки рангов выполняется переход от
порядковой шкалы к бальным оценкам (что, конечно, приводит к искажению
данных). При высокой согласованности данных свертки рангов приводят, как
правило, к тем же упорядочениям, что и аналогичные свертки на основе метрики
на матрицах отношений. При этом они значительно менее ресурсоемки.
Предложены линейная и мультипликативная свертки рангов. Частным случаем
линейной свертки является метод строчных сумм или способ Борда. Для
суммарной матрицы и для матрицы весов линейная свертка вычисляется по
формулам:
21 ^-j
s, = -^
zl^uim-j)
и 5, = ^
(m-l)n
.
(8)
(m-1)w
Мультипликативная свертка представляет собой взвешенное произведение
нормированных оценок по квалиметрическому методу Руссмана:
s,=T\\(\-s)
i=T\
'- + £]
Mt-\
, где У wl = 1 , M i =maxr,*.
I
ft?
(9)
'='"
Разработана оценка достоверности решений, основанная на сравнениях
строчных сумм с их некоторыми табличными значениями. Объект а, превосходит
объект Oj, если разница между s, и s, больше порога различия d = kdo,
do = 1/(т - 1 ) .
На
основе
вычислительных
экспериментов
определено
рекомендуемое значение к = 0.2 . При этом оценки достоверности с, е [-1,1]:
^
'-],s,
О, -т. J
'
'\
с.=и
B[mj;Oj]
'-^-^ие{Ог,МЛ
,
(10)
Mj-Oj)
где j = r,, i = \..m. т,,М,,0,—
минимальные, максимальные и оптимальные
значения s,. Коэффициент с, = О означает, что i -я сумма существенно
отличается от ближайших сумм. Из |с,| = 1 следует, что ранг г-го объекта
определен приблизительно (с, > О — возможно объект имеет меньший ранг,
с, < О — больший).
Далее рассмотрены методы, использующие матрицу весов. Подробно
изложены такие известные методы — метод Копленда, правило большинства,
квантильный метод. Показано, что квантильный метод связан с задачей (4).
Разработанный "модифицированный метод большинства" состоит в
следующем. Введем переменную
'•'=[
1,если объект а, находится на_/-м месте (ранг г, = j);
(О-впротивном случае.
Если
матрица
Цх'Цшх,,,
соответствует
результирующему
ранжированию,
представленному вектором рангов {г\,А,...,г!„), то сумму
Jv,4
(12)
можно рассматривать как количество голосов, отданных экспертами за то, что г-е
объекты находятся на г,' местах. Возникает следующая оптимизационная задача:
^v,jX,j - ^ m a x
(13)
'.у
при ограничениях
^ х „ =1, i = \..m ; '^х,, =l,j = l..m; х,, е[0,1],
j=\
(14)
.=1
известная как задача о назначениях. Далее поставлена задача оптимизации для
вычисления нестрогого результирующего ранжирования:
1К11 = 1 К " 1 | . V
=тах{/яш:<*»} ,
(15)
где
||jci'>| и max'", A = l..w
находятся из
^v,jxj*'-^•тах
>,)
при ограничениях
т
1=\
(16)
т
1=1
4*'=0, i = \Jn,j = YvL:ik; ^ £ 4 * ' = ' « 1 4*'=[0,1].
(17)
j=\ 1=1
Данный метод целесообразно применять в тех случаях, когда важно не взаимное
упорядочение объектов, а то, какой ранг получит объект. Метод слабо
чувствителен к присутствию в начальных данных сильно различающихся
ранжирований, его можно применять при большом числе случаев
нетранзити вн ости.
Разработан новый метод получения результирующего ранжирования,
основанный на построении матрицы потерь для матриц отношений и сводящийся
к решению задачи о назначениях— метод минимального несогласия.
Рекомендации к применению данного метода такие же, как и у медианы Кемени,
но возможно получать решения для ббльшего числа ранжируемых объектов.
Исходные данные: Л,, ... Л„ — векторы рангов, указанные экспертами, 71, ...
Т„ — соответствующие им матрицы отношений. Пусть некоторый вектор R = (rj,
... г^) отличается от вектора рангов Л* только i-й компонентой и г, = j (объект а,
находится на j-м месте). Составим матрицу отношений
Т = \\t\\„^„,
соответствующую вектору R . Тогда
<=rf(r,71)=Xh-AVl
(18)
характеризует "несогласие" А:-го эксперта с назначением объекта а, на_/-е место.
Элемент матрицы потерь
щ=^w,u^.
(19)
t=i
Оптимизационная задача:
^u,jX,j
I.J
-^ mm
(20)
10
при ограничениях (14) Далее разработан алгоритм, снижающий вычислительные
затраты при формировании матрицы потерь. При расчете «,5 можно ограничиться
вычислением только 2 ( т - 1 ) элементов матрицы Т:
1)
<=0,i' = l;
2)
Если i' = г, то щаг 6;
3)
4)
5)
Если п <г,',то t„ = 1, шаг 5;
Если г, >г,', то („■ = -1 ; иначе /„■ = О ;
Увеличить к* на |/' - ? „ | ;
6)
Если г'= _/,то шаг 10;
7)
Если г, < г,', то /j, = 1, шаг 9;
8)
Если rj > п , то tj, = - 1 ; иначе tj,' = О;
9)
Увеличить и^ на |/*, - ? ; , | ;
10) Если i' <т , то увеличит г' на 1, шаг 2;
11 У- Конец.
Для случая нестрогих ранжирований в диссертации предложен
алгоритм получения щ:
1)
щ =0 , для i,j = \..т ; к = \;
2)
Мк = т ш с г л ;
следующий
1=\ т
2.1) Если Mk = 1, то Д* = 1, B,k =т
для i = \..т ; шаг 5;
2.2) Если Mk = m , то A,k = Вц = i, для / = 1../и; шаг 5;
3)
^ j = y .т-\
+ 1,для y = O..Mt ;
М*
4)
5)
4* = ОкруглитъВверхЦ^,^), Д* =ОкруглитъВниз(1^),
Для / = 1../И и 71 = 1"Л^4 :
i = \..m;
5.1) Рассчитать элемент матрицы потерь «Jf*;
5.2) Для _; = ^),-8* : увеличить щ на «,'*';
6)
Увеличить А: на 1; если А: < и , то шаг 2;
7)
Конец.
Задача оптимизации для вычисления нестрогого результирующего ранжирования
аналогична (15).
Предложенный метод преобразования рангов (рисунок 1) обобщает класс
методов, работающих непосредственно с рангами объектов. Различные процедуры
голосования задаются эквивалентными рангами R = (_ri,r2,...fm) и весами для
рангов G, е [0,1]. С помощью этих параметров выполняется преобразование
матриц отношений: 7i -> Л * — ^ R t -^Тк^^ТЦ, после чего применяется метод
строчных сумм, либо любой другой метод.
В разделе приводятся такие известные методы, как турнирные показатели и
оценка объектов правым собственным вектором, рассмотрено получение
11
ранжирования из матрицы отношений Согласно принципам методов E L E C T R E в
диссертации разработан алгоритм поиска результирующего ранжирования.
Ранги
Обобщает класс методов:
R = (1,2, 3, 4, 5)
Л-
Метод строчных
Эквивалентные
Метод Борда
R = (1, 1,2,3,3)
ранги
Метод Коп ленда
Правило большинства
Веса рангов
G = (1,0.8, 0.1)
Только голоса против
Матрицы
Защита от манипулирования
отношений
сумм
G = (1 1, 1,1,1)
G = (1 0,0,0, 1)
G = (1 О, О, О, 0)
G = (О,0,0,0,1)
G = (О,1,1, 1,0)
Рисунок 1 — Метод преобразования рангов
Третий раздел посвящен неполным парным сравнениям. Разработаны новые
методы нахождения результирующего ранжирования для данных, представленных
неполными^ матрицами парных сравнений. Подробно рассмотрены известные
методы (модели Цермело-Бредли-Тири, Леонардо, Девидсона и метод
Чеботарева). Приведены формулы для вычислений и предложены способы выбора
неизвестных коэффициентов.
В статистических моделях вероятность Р того, что один объект лучше, хуже
или равноценен другому, задается соотношениями весов объектов xi. Ввиду того,
что эти модели слабо соответствуют реальной ситуации, предложены линейная
статистическая модель и коррекция итоговых весов объектов, что позволяет
оценивать достоверность решения. Для моделей Цермело-Бредли-Тири,
Леонардо, Девидсона коррекция весов выполняется следующим преобразованием:
max X -min X
X, <
=
=
, ,,
.
^ч
1п(1 +х,- minX)
.
,,
+ minX
.
\п{тах_Х - min_X +1)
На рисунке 2 изображены при фиксированном Xj-60\ следующие функции:
Р(а, > Oj) — точками, Р{а, <aj) — пунктиром, Р{а, =aj) — сплошная (для
линейной модели); тонкими л и н и я м и — аналогичные кривые для модели
Девидсона.
Рисунок 2 — Вероятности того, что один объект лучше, хуже или равноценен
другому при фиксированном весе второго объекта (л:^ = 601)
12
в статистических моделях объекты следует ранжировать в порядке убывания
X, . Предлагается заполнить пропуски в исходных матрицах отношений и матрице
весов согласно полученным величинам х,, затем применять методы из второго
раздела. Таким образом, исходные данные будут учтены максимально полно.
Например, пополнение суммарной матрицы отношений HiVijH,,,,,, может быть
выполнено следующим образом:
N,j =N,j+{n-N;j)P{a,
>а,),1^
j,i,j = YJn,
(21)
где М; — ч и с л о сравнений объектов. Вероятности Р{а, > а,) соответствуют той
статистической модели, по которой получены параметры х,. Для пополнения
матрицы весов из ранжирования R', соответствующего параметрам х,, получаем
матрицу весов | К | | „ , „ :
{хихг,...,х„)^
ir<M,...rL)^
IK t , „ .
(22)
Затем вычисляются
V,=^v,
(23)
j^\
и
задаются
начальные значения
v,j = v,j.
Новые
элементы матрицы
весов
вычисляются по формуле:
v,r. = v , „ + V , % ( / J > , - F ; ) , i = \..m.
(24)
Пропорциональным методом заполняются пропуски, обусловленные тем, что
объекты сравнивались не всеми экспертами. В соответствие с параметром доверия
данным хб[0,1] увеличиваются значения элементов суммарных матрвд. Этот
параметр равен О, если результаты парных сравнений случайны (результаты
сравнений объектов попарно независимы) и равен единице при транзитивных
экспертных оценках. Например:
N,=N,{^-\\Y
+ N,.
(25)
Если в суммарной матрице отношений много пропусков, то известные
методы, как правило, приводят к ошибочным итоговым ранжированиям.
Предлагаемый метод зависимостей предназначен для транзитивных данных для
заполнения пропусков, обусловленных тем, что объекты ни разу не сравнивались
между собой. Идея метода состоит в следующем. В грйфе, соответствующем
суммарной матрице отношений ЦЛ'уЦтхт (например, рисунок 3), производится
поиск всех путей между всеми парами несмежных вершин. Для каждого пути
согласно некоторой функции рассчитываются в е с а — число голосов "за" и
"против" того, что один объект предпочтительней другого. Если найден хотя бы
один путь между несмежными вершинами и сумма полученных весов отлична от
нуля, то получено новое ребро. Если некоторые ребра получить не удалось, можно
повторно воспользоваться алгоритмом, используя вновь полученные ребра. Если
число вершин и отсутствующих ребер велико, то длину пути следует ограничить
(например, путь составляет только два ребра). Предлагаются формулы расчета
весов и соответствующий алгоритм вычислений.
13
Л^
a,b
Kc=Q-9,\
= 1 , N,
■
h,ii
=0
N^
Рисунок 3 — Граф суммарной матрицы отношений (ребро ас и соответствующие
ему элементы матрицы получены методом зависимостей)
В четвертом разделе приводятся способы и алгоритмы анализа исходных
данных и получаемых решений, описание диалого-машинной процедуры поиска
итогового ранжирования, необходимые для создания подсистемы СППР.
Разработанная система ориентирована на диалог с ЛПР, в ходе которого
выбираются
способы
нахождения
результирующего
ранжирования,
рассчитываются оптимальные-ранжирования, их характеристики, формируется
итоговое ранжирование.
Для предварительной обработки данных в диссертации предложены:
■ коэффициенты
для
определения
числа
пропусков
и
степени
согласованности данных;
■ алгоритм очистки данных от сильно отличающихся ответов или выделения
фупп ранжирований, соответствующих различным решениям;
■ определение весов ранжирований на основе наборов ответов экспертов и
соответствующих им результирующих ранжирований.
Выбор методов получения результирующего ранжирования для решения
практической задачи основан на классификации исходных данных и выборе
соответствующего метода их обработки. Схема на рисунке 4 иллюстрирует
Ограничения
пользователя
Важно, как
соотносятся
объекты
i
;
#
Модифицированный
метод большинства
Медиана Кемени
Много случаев
хнетранзитивности.
Метод минимального
несогласия
Квантильный метод
Ранжирования
чмало различаются^
Выделение ядер с
высокой
согласованностью
Строчные суммы
К-медиана
Мульт. свертка
критериев ]<ачества^
Мультипликативная
I
свертка рангов
Собственные вектора
Правила большинства
Преобразование
рангов
Специальные^
процедуры
ь голосования,
Рисунок 4 — Выбор методов получения результирующего ранжирования
14
процесс выбора методов получения результирующего ранжирования для решения
практической задачи. Широкими линиями показаны требования и настройки,
вводимые ЛПР. Тонкие линии — автоматические действия системы. На выбор
методов также влияет число объектов Если объектов больше 12, то вместо
методов, отмеченных символом '*', применяются аналогичные свертки рангов.
Жирным шрифтом отмечены методы, разработанные в диссертации. На рисунке 5
представлен процесс выбора методов для случая неполных парных сравнений.
Результат парныхХ
сравнений - случайное)
событие
I
I
\
I
Методы поиска
результирующего
г I
г1 —•
ранжирования
Метод строчных суии
■
I
,
....<».ncuusc»,Di пг. >
\ пя-гм UO гпяаиыояпиги I
/
\
,,
„
Много пропусков
f
f
Рисунок 5 — Выбор методов для неполных парных сравнений
Разработанная диалоговая процедура поиска итогового ранжирования
включает следующие функции.
■ Вычисление множества пересечения матриц отношений. Выделенные
наилучшие и наихудшие объекты исключаются из рассмотрения и задача поиска
результирующего ранжирования решается для меньшего числа объектов.
■ Выбор методов поиска результирующего ранжирования, корректных для
данного типа данных.
■ Формирование множества Парето на множестве исходных данных или на
множестве результирующих ранжирований, рассчитанных различными методами.
■ Фиксирование рангов. Если Л П Р зафиксировал i -й объект на ; -м месте
(г' = J), то i -й объект исключается из исходных данных, но в итоговом
ранжировании остается на j -м месте.
■ Фиксирование отношений. Л П Р (с помощью матрицы множества Парето)
указывает отношение между i -м и J -м объектами, затем изменяются суммарные
матрицы отношений, что повышает согласованность данных.
■ Повторный расчет результирующих ранжирований и множества Парето с
учетом предпочтений Л П Р как для исходных данных, так и для множества
результирующих ранжирований.
15
в разделе приводится определение множества Парето для ранжирований.
Предложено представлять множество Парето в виде одной матрицы, что
позволяет использовать множество Парето в диалоговой процедуре поиска
результирующего
ранжирования.
Разработан
эффективный
алгоритм
формирования такой матрицы. На рисунке 6 представлен пример построения
множества Парето для четырех исходных ранжирований Знак ">" на пересечении
строки а и столбца b означает, что все эксперты считают объект а
предпочтительней объекта Ь. Знак " о " на пересечении строки Ь и столбца с
означает, что часть экспертов считают объект b предпочтительней объекта с, часть
экспертов — наоборот.
(а, е, Ь, с, d)
(а, е, Ь, d, с)
а
b
с
d
е
(а, с, е, Ь, d)
(а, d, с, е, Ь)
а) Исходные ранжирования
а
b
с
d
*
<
<
<
<
>
*
>
о
*
о
о
>
о
о
|
|
е
>
<
о
о
о
*
о
о
>
*
б) Матрица множества Парето
(а, е, Ь, с, d)
(а, с, е, Ь, d)
(а, е, Ъ, d, с)
{а, d, е, Ь, с)
(а, е, с, Ь, d)
(а, с, е, d, b)
(а, е, d, Ъ, с)
{а, d, е, с, h)
(а, е, с, d, b)
(а, с, d, е, Ь)
(а, е, d, с, Ь)
{а, d, с, е, Ь)
в) Возможные оптимальные ранжирования
(выделено результирующее ранжирование)
Рисунок 6 — Множество Парето для ранжирований
Анализ решений основан на:
■ оценке достоверности решения;
■ сравнении получаемых решений с помощью частотной гистограммы
расстояний; вычислении расстояний до других решений.
■ оценке
чувствительности
решения
к
незначительным
случайным
изменениям в исходных ранжированиях.
Также поддерживается оценка результатов тестирования и поиск оптималь­
ного распределения ресурсов.
Предложен и реализован подход оценки результатов тестирования. Ответы
могут быть ранжированиями объектов или группировками объектов на классы
эквивалентностей. Разработан эвристический алгоритм вычисления максимально
возможного расстояния до фиксированной группировки.
Выполнена постановка задачи о назначениях, в которой каждая должность и
каждый претендент на эти должности имеют собственные характеристики —
16
ранжирования. Предложен и реализован подход сведения этой задачи к
классической задачи о назначениях с помощью меры близости на отношениях.
Задача наглядно представляется двудольным неориентированным графом
Г = ( Л ' " u X ^ j K ) (рисунок 7), где Х° и А'* —независимые множества вершин и
для каждого ребра у,, ={x,,Xj)fiY
имеет место х, е Х",
д:^ е А"*. Каждой
вершине х, € X" сопоставлено ранжирование а, е А и каждой вершине х, е А'*
сопоставлено ранжирование Ь, е В . Ребро y,j = (л:,,л,) присутствует в графе Г в
том случае, если г-й претендент претендует на у-ю должность. Решением будет
некоторое паросочетание (например, выделенные ребра).
Претенденты
'^'профаммирование''^
"математика"
"английский"
Должности
'профаммирование''
"математика"
"английский"
математика
"профзммирование'
"английский"
"английский"
профаммирование"
"математика"
профаммирование
"математика"
"математика"
'профаммирование"
^
"английский"
математика
"английский"
''профаммирование'
Рисунок 7 — Пример задачи о назначениях
В
п я т о м разделе приводится описание программной компоненты
"Обработка информации в порядковых шкалах" СППР. Рассмотрены следующие
примеры использования созданной подсистемы.
1. Анализ эффективности коэффициентов согласованности и методов поиска
результирующего ранжирования (таблица 1). Начальные данные представляют
Таблица 1 -- Тестирование методов и коэффициентов
Ранжирова­
Максимально возможное расстояние
Объек­
Испыта­
тов— 5
ний — 500
ний—1000
между ранжированиями — 20
Методы
Коэффициенты согласованности данных
С Ч п Стат
Р
хар-ки M l / М2/ мз/М4/ К4/ К 1 / К 1 / К 1 / К 1 / К 1 / К2/ К2/ К2/ К2/ К2/ КЗ/ КЗ/ КЗ/ КЗ/ КЗ/
К4 К4 К4 К4 СР M l М2 МЗ М4 К4 M l М2 МЗ М4 К4 M l М2 МЗ М4 К4
0 12
95 0 0 Ср 3 71 2 53 2 320 86 194
0 06
0 01
С р KB 2 69 3 00 3 052 63 182
0 01
019
Корр 0 75 0 67 0.67 0 340 73-0 7-0 5 -0.4 -0 2 -0.4
04 04 04 05 04 -05-03-03-0 1-0 4
Нср 0.19 0 13 0 120.04 0.10
0 4 3 Ср 011 0.00 0 05 2 300 06
0 22
0.00
0 05
С р KB 0 44 0 00 0 32 177 0 23
0 02
000
0 01
Корр 0 95 0 00 0 66 0 110 42 - 0 0 - 0 0 - 0 0 0 0 - 0 1 0 3 0 3 0 3 0 3 0 1 -00-00-0000 00
Нср 001 0 00 000 011 0 00
17
собой 500 одинаковых ранжирований пяти объектов. Для каждого эксперимента
указываются типы случайных помех (Ср., Ч.и., П.о.), затем проводится 1000
испытаний. Для каждого испытания генерируются измененные начальные данные,
вычисляются коэффициенты согласованности, рассчитываются результирующие
ранжирования и расстояния от них до правильного решения, рассчитываются
статистические характеристики (выборочное среднее, выборочное "исправленное"
среднеквадратичное
отклонение,
выборочный
коэффициент
корреляции,
нормированное выборочное среднее).
2. Рейтинг крупнейших банков России. Данный пример иллюстрирует
применение СППР для нахождения результирующих ранжирований для данных в
количественных, порядковых шкалах, данных с пропусками и анализа
полученных результатов. Так, различие аналитических рейтингов для данных в
количественных и порядковых шкалах достигало 34% от максимального.
3. Пример решения задачи о назначениях для 1000 претендентов на 500
должностей, размерность ранжирований— 15.
4. Тестирование студентов для проверки владения понятийным аппаратом
предмета "Общая психология" (совместно со специалистами Института
информатизации социальных систем К Г Т У ) . Студентам предоставляется набор
терминов изучаемой дисциплины. Им необходимо выполнить следующие задания.
■ Упорядочить термины согласно их близости к данной дисциплине.
■ Разбить набор терминов на произвольные группы. В каждой группе должны
содержаться термины, близкие по смыслу.
■ Разбить, как и во 2-м задании, набор терминов на группы. При этом
указывается, сколько должно получиться групп и по сколько должно быть
терминов в каждой фуппе).
Известны правильные упорядочение и группировка терминов. Оценка
ответов производится путем их сравнения с образцом. Для этого вычисляется
расстояние между ответом и образцом.
В двух приложениях приводятся предложенные в диссертации модификации
двух известных алгоритмов: Венгерский эвристический алгоритм решения задачи
о назначениях (исключены случаи вечного цикла) и алгоритм генерирования всех
перестановок с минимальным числом транспозиций соседних элементов
(используется в нескольких методах для полного перебора).
Заключение
Обобщённым
результатом диссертационной работы можно
считать
комплексную проработку математического и реализующего его алгоритмического
обеспечения для анализа данных
в порядковых
шкалах.
Выполнено
унифицированное представление всех рассмотренных методов, модификация
существующих и разработка новых методов и алгоритмов, обоснование
применения того или иного метода для получения корректного решения при
низкой согласованности данных, разработаны оценки чувствительности и
достоверности решений. При этом рассматривалась обработка как первичной, так
и вторичной информации (результирующее ранжирование).
18
Полученные результаты обеспечивают более полное удовлетворение
потребностей в обработке данных в порядковых шкапах и предоставляют
возможность построения функционально законченных С П П Р .
Одной из идей диссертации является распространение, где это возможно,
подходов к анализу данных в количественных шкалах на работу с порядковыми
шкалами.
Были проанализированы и выделены основные типы исходных данных с
возможностью их автоматизированного распознавания и для них предложены
предпочтительные варианты математических методов и алгоритмов. Обеспечена
возможность коррекции слабо согласованных исходных данных в порядковых
шкалах (с пропусками, сильно отличающимися значениями), определения
компетентности эксперта на основе статистики его ответов.
Разработаны новые методы и алгоритмы: "модифицированный метод
большинства",
метод
минимального
несогласия,
"модификация
метода
E L E C T R E " , к-медиана и мультипликативная свертка критериев качества, метод
преобразования рангов, а также для неполный парных сравнений— линейная
модель, пропорциональный метод, методы зависимостей и пополнения матриц.
Модифицированы алгоритмы для квантильного метода, вычисления медианы
Кемени, правила к-большинства, Борда, Копленда.
Алгоритмизированы известные методы Цермело-Бредли-Тири, Леонардо,
Девидсона, Чеботарева, Блэка, турнирные показатели, рассмотрены особенности
применения среднегеометрического строчных элементов и соотношения левого и
правого собственных векторов с целью программной реализации в рамках
созданной подсистемы "Обработка информации в порядковых шкалах". Для ряда
из них предложены способы выбора незаданных коэффициентов.
Унификация
представления
математических
методов
позволила
единообразно строить реализующие их алгоритмы при создании программного
обеспечения, в том числе, использовать унифицированные процедуры внутри
различных алгоритмов, в частности, алгоритм перестановок с настройкой на тип
решаемой задачи.
Решен ряд частных задач, связанных с повышением эффективности
применения существующих и предложенных методов и алгоритмов: построение
матрицы множества Парето, вычисление максимального расстояния между
классами
эквивалентностей,
вычисление
матрицы
потерь
для метода
минимального несогласия, исключение вечного цикла в Венгерском алгоритме.
Создана программа в виде диалого-машинной процедуры, реализующая
разработанный комплекс алгоритмов обработки данных, позволяющая выполнять
предварительную
обработку
исходных
данных
(с
автоматизацией
их
классификации), выбирать предпочтительные алгоритмы обработки данных и
учитывать мнение Л П Р в случаях, когда различные методы дают противоречивые
результаты.
С помощью генерации начальных данных выполнено тестирование методов
первичной
обработки
данных
и
методов
получения
результирующих
ранжирований. Созданная подсистема "Обработка информации в порядковых
19
шкалах" позволяет находить результ
решении прикладных задач из раз
вспомогательные задачи обработки
инструментом для дальнейших исследо!
Разработанные методы и алгорит\
научно-исследовательских работ в реп
медицинской помощи на территорр
менеджмента качества подготовки спец1
и^ ^ 2 4 5 8
г Н Ь РуССКИИ фОНД
' ^ 0 0 ^ - 4
20355
Публикации автора ..., .^,..». „..^^^^^
1. Даничев, А. А. Задача о назначениях в порядковых шкалах для системы
поддержки принятия решений / М. А. Воловик, А. А. Даничев // Информатика и
системы управления : межвуз. сб. науч. тр. / Отв. редактор С. А. Бронов. —
Вьш. 7. — Красноярск: Г У Н И И информатики и процессов управления, 2002. —
С. 334—339.
2. Даничев, А . А . Программная система поддержки принятия решений:
обработка информации в порядковых шкалах / М. А. Воловик, А. М . Даничев,
А. А. Даничев // Бюллетень "CAD/CAM/CAE/CALS. — Красноярск: К Г Т У , научно
образовательный центр интегрированных компьютерных технологий, 2004. —
С. 32—46.
3. Даничев, А. А.
Алгоритм
формирования
множества
Парето для
ранжирований / А. А. Даничев // Информатика и системы управления : межвуз. сб.
науч. тр./ Отв. редактор С. А. Бронов.— В ы п . 1 0 . — Красноярск: Г У НИИ
информатики и процессов управления, 2004. — С. 220—224.
4. Даничев, А . А.
Метод
минимального
несогласия / А. А . Даничев //
Информатика и системы управления : межвуз. сб. науч. тр. / Отв. редактор С. А .
Бронов.— В ы п . 1 0 . — Красноярск: Г У Н И И информатики и процессов
управления, 2004. — С. 225—232.
5. Даничев, А . А . Система поддержки принятия решений "Обработка
информации в порядковых шкалах" ESS/3RD : Свидетельство об отраслевой
регистрации разработки №5652 / М. А. Воловик, А. А. Даничев // Отраслевой
фонд алгоррггмов и программ, 2005. — 17 с.
Даничев Алексей Александрович
Методы и алгоритмы обработки данных в порядковых шкалах
для систем поддержки приняггия решений.
Автореф. дисс. на соискание учёной степени кандидата тех. наук.
Подписано в печать 14.14.2005. Заказ № ^в/Х^
Формат 60x90/16. Усл. печ. л. 1. Тираж 100 экз.
Отпечатано в И П Ц К Г Т У 660074, Красноярск, ул. Киренского, 28
20
Документ
Категория
Без категории
Просмотров
0
Размер файла
907 Кб
Теги
bd000101347
1/--страниц
Пожаловаться на содержимое документа