Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок

Описано узагальнення методу визначення коефіцієнтів відносної вагомості критеріїв на основі ординальних оцінок альтернатив на випадок ієрархії критеріїв типу «дерево». Стаття містить постановку задачі, опис покрокової роботи алгоритму та результатів його тестування, а також ілюстративні приклади та...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
1. Verfasser:	Каденко, С.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы обработки информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/209230
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок / С.В. Каденко // Проблемы управления и информатики. — 2008. — № 4. — С. 84-91. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-209230
record_format	dspace
spelling	irk-123456789-2092302025-11-17T01:16:56Z Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок Визначення параметрів ієрархії критеріїв типу «дерево» на основі ординальних оцінок Determination of parameters of tree-like criteria hierarchy based on ordinal estimates Каденко, С.В. Методы обработки информации Описано узагальнення методу визначення коефіцієнтів відносної вагомості критеріїв на основі ординальних оцінок альтернатив на випадок ієрархії критеріїв типу «дерево». Стаття містить постановку задачі, опис покрокової роботи алгоритму та результатів його тестування, а також ілюстративні приклади та таблицю, що пояснюють роботу описаного алгоритму. The article describes a modified relative criterion weight calculation method for treelike criteria hierarchies based on ordinal estimates. The article includes problem statement, description of each algorithm step and results of its testing, as well as examples and tables illustrating the work of the specified method. 2008 Article Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок / С.В. Каденко // Проблемы управления и информатики. — 2008. — № 4. — С. 84-91. — Бібліогр.: 7 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209230 519.816 10.1615/JAutomatInfScien.v40.i8.20 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Каденко, С.В. Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок Проблемы управления и информатики
description	Описано узагальнення методу визначення коефіцієнтів відносної вагомості критеріїв на основі ординальних оцінок альтернатив на випадок ієрархії критеріїв типу «дерево». Стаття містить постановку задачі, опис покрокової роботи алгоритму та результатів його тестування, а також ілюстративні приклади та таблицю, що пояснюють роботу описаного алгоритму.
format	Article
author	Каденко, С.В.
author_facet	Каденко, С.В.
author_sort	Каденко, С.В.
title	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок
title_short	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок
title_full	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок
title_fullStr	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок
title_full_unstemmed	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок
title_sort	определение параметров иерархии критериев типа «дерево» на основе ординальных оценок
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2008
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/209230
citation_txt	Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок / С.В. Каденко // Проблемы управления и информатики. — 2008. — № 4. — С. 84-91. — Бібліогр.: 7 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT kadenkosv opredelenieparametrovierarhiikriterievtipaderevonaosnoveordinalʹnyhocenok AT kadenkosv viznačennâparametrívíêrarhííkriteríívtipuderevonaosnovíordinalʹnihocínok AT kadenkosv determinationofparametersoftreelikecriteriahierarchybasedonordinalestimates
first_indexed	2025-11-17T02:14:49Z
last_indexed	2025-11-18T02:09:04Z
_version_	1849092205273153536
fulltext	© С.В. КАДЕНКО, 2008 84 ISSN 0572-2691 УДК 519.816 С.В. Каденко ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ИЕРАРХИИ КРИТЕРИЕВ ТИПА «ДЕРЕВО» НА ОСНОВЕ ОРДИНАЛЬНЫХ ОЦЕНОК Введение В [1] описан метод определения коэффициентов относительной важности критериев на основе опыта ординального оценивания альтернатив. Речь шла о на- стройке весовых коэффициентов на основе примеров ординального оценивания (ранжирования) объектов по нескольким критериям, один из которых выступал в роли глобального критерия, а остальные — как его подкритерии. Обучение (поиск весов) могло происходить на основе одного или нескольких примеров ординаль- ного оценивания — прецедентов. Нахождение весовых коэффициентов позволяет лицу, принимающему решение (ЛПР), определять относительную важность кри- териев и приоритетные направления деятельности. Состояние проблемы Отметим, что ранее данная задача решалась для случая кардинальных оце- нок. Для настройки весов на основе кардинальных оценок можно использовать та- кие общеизвестные методы, как метод наименьших квадратов, метод группового учета аргументов, метод минимизации невязок, метод многомерной линейной экст- раполяции [2] или персептронный алгоритм Розенблатта [3]. Методы настройки весовых коэффициентов на основе ординальных оценок не разрабатывались. В последние годы получила распространение модель ординальной регрес- сии [4], которая применяется преимущественно в задачах классификации. Орди- нальные оценки в данной модели фигурируют только на выходе и обозначают принадлежность альтернатив определенному классу. Ранее автор рассмотрел один уровень иерархии критериев оценки альтерна- тив [2, 5]: глобальный критерий и группу его непосредственных подкритериев (потомков) [1]. Именно их влияние на глобальный критерий определялось с по- мощью изложенного метода. Впрочем остался открытым вопрос: можно ли опре- делить коэффициенты влияния подкритериев на глобальный критерий, если из- вестно, что иерархия имеет более сложную структуру? Ведь иерархии, с которы- ми приходится иметь дело организаторам экспертиз, часто представляют собой графы типа многоуровневого «дерева» или «сети», а иногда в них встречаются даже обратные связи. Ниже изложен подход, позволяющий определять параметры иерархии крите- риев типа «дерево». Далее приводится строгая постановка задачи, алгоритм ее решения и конкретные примеры. Постановка задачи Дано: 1. Иерархия критериев типа «дерево». В узлах иерархии находятся критерии ,1K .,,2 nKK  Корнем дерева является глобальный критерий G (или ),0K ли- стьями — критерии нижних уровней, не имеющие подкритериев (потомков) ,1jK .,,2 jpj KK  (Напомним, листом древовидного графа называется вершина, не имеющая потомков.) Ребра графа иерархии отражают влияние критериев на своих предков. Проблемы управления и информатики, 2008, № 4 85 2. Множество оцениваемых объектов (альтернатив) .,,1 mAA  3. Множество ранжирований альтернатив по критериям нижнего уровня (ли- стьям дерева) .,,1,,, ,1, mirr jpiji   4. Ранжирование альтернатив по глобальному критерию .,,1 mgg  Найти: 1. Коэффициенты относительной важности всех критериев иерархии }{ jw ),,1( nj  такие, что jK и его непосредственных потомков :,,, 21 jsjj KKK  ,1,,2,1  jjsjjjj www  ,0, jjkw sk ,,1 (подкритерии положительно вли- яют на своих предков, а суммарное влияние потомков каждого критерия на этот критерий равняется 1). 2. Ранжирование альтернатив по всем промежуточным критериям, не яв- ляющимся листьями дерева. (Предполагается, что ранжирование по глобально- му критерию задается порядком возрастания взвешенных сумм локальных ран- жирований). Пошаговый алгоритм решения: общий вид Шаг 1. Запускаем алгоритм определения коэффициентов относительной важности критериев на основе ординальных оценок, изложенный в [1]. В качестве исходных данных используем имеющиеся ранжирования альтернатив по глобаль- ному критерию и по «листьям» дерева. На выходе получим коэффициенты влия- ния критериев нижних уровней на глобальный критерий: .,1 jpj ww  Шаг 2. Находим коэффициенты влияния подкритериев самого нижнего уровня (листь- ев) на непосредственных предков. В общем виде процедура выглядит следующим обра- зом. Пусть критерий предпоследнего уровня jK имеет подкритерии ,,,, 21 jpjj KKK  которые соответственно являются листьями дерева (рис. 1). На первом шаге данного алгоритма будут найдены коэффициенты влияния подкритериев на глобальный критерий: jpjj www ,, 21 (так называемые чувст- вительности). На втором шаге, который собственно и описывается, мы находим коэффициенты влияния подкритериев jpjj KKK ,,, 21  на критерий jK : ,,1 jjw .,, ,,2 jjpjj ww  Предположим, произведение всех коэффициентов влияния крите- риев, которые в графе иерархии лежат между jK и глобальным критерием G, равняется :jw , 1 jl L l j ww    где jlw — коэффициент влияния критерия, распо- ложенного на пути от jK к G, на уровне под номером l, на своего непосредствен- ного предка, а L — общее число уровней иерархии (и соответственно промежу- точных критериев), лежащих между jK и G. В таком случае можно записать систему уравнений: .1 , , ,1 , ,11    jjpj jjjpjp jjjj ww www www   G K j w jp w j w jp, j w j1, j K j1 K jp w j1   Рис. 1 86 ISSN 0572-2691 Чтобы исключить из системы неизвестный (пока что) множитель ,jw после- довательно запишем отношения правых и левых частей всех уравнений, до пред- последнего включительно. В результате получим систему: .1 ,// ,// ,,1 ,),1()1,( ,2,121     jjpjj jjpjpjjppj jjjjjj ww wwww wwww   (1) или ,)1(21,),1(,2,1 :::::::: jppjjjjjpjpjjjjj wwwwwwww    (2) .1,,1  jjpjj ww  (3) Нулевых знаменателей в левой части системы (1) быть не может, поскольку нулевое влияние соответствует отсутствию ветви дерева. Если дерево построено, то каждый подкритерий должен характеризоваться соответствующим ненулевым влиянием на глобальный критерий. Если при настройке чувствительностей влия- ние какого-то из листов дерева на глобальный критерий оказалось нулевым, то можно просто отсечь соответствующую ветвь. Утверждение 1. Решение системы (1) существует, и оно единственно. Доказательство. Как видно из системы, искомые коэффициенты влияния со- относятся между собой так же, как и только что найденные коэффициенты влия- ния подкритериев на глобальный критерий, а их сумма равняется 1. Тогда ).(/ ),(/ 1, 11,1 jpjjpjjp jpjjjj wwww wwww      По крайней мере, одно решение существует — оно только что найдено. Если до- казать линейную независимость уравнений, то можно утверждать, что решение единственно: ведь число уравнений p совпадает с числом неизвестных. Перепишем систему (1): .1 ,0 ,0 ,,1 )1(,,),1(, 12,22,1     jjpjj pjjjppjjpj jjjjj ww wwww wwww   Векторно-матричный вид системы таков: .)1000( 1...0 ............ 1... 1...0 ),( )1(, 31 2 ,,2,1                    pj jj j jjpjjjj w ww w www Определитель системы равен ,011 )1(,2132  pjjjjpjj wwwwww  Проблемы управления и информатики, 2008, № 4 87 так как по условию задачи все веса строго положительны (мы рассматриваем де- рево, состоящее из совместимых критериев). Поскольку определитель системы ненулевой, по правилу Крамера, она имеет единственное решение. Утверждение доказано. Описанную процедуру можно применять на любом уровне иерархии. Шаг 3. Движемся вверх по графу иерархии и находим коэффициенты влия- ния критериев промежуточных уровней на глобальный критерий. При этом следу- ет постоянно руководствоваться утверждениями (2) и (3). Если критерий jK имеет подкритерии ,,,, 21 jpjj KKK  то выполняется следующее соотношение коэффициентов влияния:  )( ,,1 jjpjjj www  ,1 jpj ww   т.е. поскольку справедливо выражение (3), ,1 jpjj www   где jw — коэффициент влияния критерия jK на глобальный критерий G. Утверждение 2. Коэффициент влияния произвольного критерия иерархии, который не является листом дерева, на глобальный критерий равняется сумме ко- эффициентов влияния его потомков на глобальный критерий. Шаг 4. Когда определены все промежуточные коэффициенты влияния, мож- но найти ранжирования альтернатив по всем промежуточным критериям иерар- хии посредством модифицированных методов Борда или Кондорсе [6] или метода взвешенной суммы (см. постановку задачи). Пошаговый алгоритм решения: иллюстративный пример Для упрощения дальнейших рассуждений, повышения уровня наглядности и во избежание проблем с индексацией, поясним пошаговую работу алгоритма на конкретном примере. Предположим, иерархия критериев имеет вид, изображен- ный на рис. 2. G K1 K2 w1 w2 K3 K4 K5 K6 K7 K8 K9 w93 w83 w8 w7 w72 w52 w62 w31 w41 w6 w9 w3 w4 w5 Рис. 2 В качестве прикладного примера рассмотрим фрагмент иерархии критериев оценки высших учебных заведений, которая используется при их рейтинговании по методике, предложенной в [7]. Пусть рассматривается иерархия критериев, где в роли глобального критерия G выступает качество подготовки разработчиков в учебном заведении, а его подкритерии характеризуются следующим семантиче- ским содержанием: K1 — воспитание творческого мышления; K2 — повышение компетентности студентов в области современной научной проблематики; K3 — обеспечение качественной прикладной подготовки; K4 — ознакомление студентов с научным аппаратом решения задач; K5 — приглашение преподавателей из дру- гих учебных заведений и из-за границы; K6 — оборудование компьютерных клас- сов с современным программным, аппаратным обеспечением и быстрым досту- пом к сети; K7 — закупка и своевременное обновление научной литературы; K8 — налаживание контактов между студентами и потенциальными работодателями и 88 ISSN 0572-2691 заказчиками; K9 — проведение лабораторных и практических занятий на высоком уровне. Подчеркнем, что на самом деле такая иерархия включает большее коли- чество критериев и имеет более сложную структуру — типа «сеть». В данном контексте она приводится исключительно для наглядности. Отметим также, что дерево не обязательно должно быть двоичным, т.е. коли- чество потомков любого критерия (если он не является листом) может быть произвольным. Шаг 1. Для заданного примера получим значения коэффициентов влияния критериев с номерами 4–9 на глобальный критерий: w4, w5, w6, w7, w8, w9. Шаг 2. Находим коэффициенты влияния подкритериев нижнего уровня (листь- ев) на непосредственных предков. В рассматриваемом примере речь идет о коэффи- циентах w83, w93, w41, w52, w62, w72. Рассмотрим данную процедуру подробнее. Суммарное влияние всех непосредственных подкритериев заданного крите- рия на своего предка равняется 1 (например, w83  w93  1). Влияние любого критерия иерархии на глобальный критерий равняется про- изведению всех соответствующих промежуточных коэффициентов влияния: ,813183 wwww  .913193 wwww  Итак, коэффициенты влияния подкритериев одного критерия на своего пред- ка соотносятся друг с другом так же, как и коэффициенты их влияния на глобаль- ный критерий: .// 989383 wwww  Соответственно для каждого нижнего участка иерархии (который состоит из листьев и их непосредственного предка) можем записать систему линейных уравнений: ,19383  ww .// 989383 wwww  Неизвестными в системе являются коэффициенты влияния критериев нижне- го уровня на своего предка. Их можно легко найти путем простых линейных пре- образований: ,19383  ww (4) .// 989383 wwww  (5) Выражаем w83 через w93 из (5): ,19383  ww ./ 989383 wwww  (6) Подставляем выражение для w83 в (4): ,1)/( 939893  wwww (7) ./ 989383 wwww  (8) Находим 93w из (7): ),/( 98993 wwww  (9) ./ 989383 wwww  Находим 83w из (8): ),/( 98993 wwww  )./( 98883 wwww  Проблемы управления и информатики, 2008, № 4 89 Аналогично вычисляются и другие коэффициенты влияния листьев дерева на своих предков: ),/( 765552 wwwww  ),/( 765662 wwwww  )./( 765772 wwwww  Шаг 3. ,3131 www  (10) ,813183 wwww  (11) .913193 wwww  (12) Отсюда 8383 / www  или ./ 9393 www  Или, если сложить (11) и (12) и подставить выражение для w3 из (10), получим ,)( 9893833 wwwww  Поскольку 9839383 ,1 wwwww  . Аналогично можно найти 2w как сумму влияний потомков 2K на :G :7652 wwww  4141 www  (известно), 3131 www  (известно). Отсюда .// 343141 wwww  Запишем систему ,// 343141 wwww  ,14131  ww отсюда )./( 43441 wwww  )./( 43331 wwww  Далее находим .431 www  Шаг 4. Зная коэффициенты влияния всех критериев на своих предков, най- дем ранжирование альтернатив по критериям .31 KK  Численный пример В качестве реального численного примера рассматривался граф иерархии, кото- рая состояла из четырех (рис. 3) подкритериев и глобального критерия. Сначала за- давались реальные значения коэффициентов влия- ния и ранжирования по конечным критериям (ли- стьям), затем на их основе определялось глобаль- ное ранжирование. После этого запускался алго- ритм поиска коэффициентов относительной важности для сформированного прецедента. Данные эксперимента приведены ниже (табли- ца). Число альтернатив ,8m число подкритериев .4n Сначала генерируются ранжирования по конечным критериям, потом на ос- нове этих ранжирований и коэффициентов влияния «листьев» на глобальный кри- G K2 K1 K3 K4 0,6 0,4 0,65 0,35 Рис. 3 90 ISSN 0572-2691 терий (которые равняются произведениям соответствующих промежуточных ко- эффициентов) определяется глобальное ранжирование. При этом ранжирования по промежуточным критериям остаются неизвестными. Промежуточные ранжи- рования можно вычислить позднее, когда найдены необходимые коэффициенты влияния. Таблица W2  0,6 W1=0,4 W3  0,35 W41  0,65 Глобальный критерий K2 K1 K3 K4 G 8 — 1 3 7 6 — 6 2 4 2 — 3 1 1 7 — 7 6 8 3 — 2 4 3 4 — 4 8 5 1 — 8 5 2 5 — 5 7 6 Найденные значения коэффициентов влияния: ;65071,041 w ;34929,034 w .58584,0;41416,0 21  ww Математическое ожидание модуля относительной ошибки определения ко- эффициентов влияния %.55,1%100/ 1 realfoundreal 1    jjj n j www n M Если методом взвешенной суммы найти ранжирования по промежуточным критериям (снизу вверх), подставив в формулу найденные значения весов, а по- том попробовать для проверки последовательно найти глобальное ранжирование, то оно не обязательно будет совпадать с заданным. Впрочем, если в исходной по- становке задачи предположить, что известны промежуточные ранжирования, то следует поочередно применять алгоритм определения относительной важности подкритериев к каждому отдельному участку иерархии (к каждой группе подкри- териев), тогда результаты его работы будут более точными и согласованными. Что касается ошибки определения коэффициентов влияния, следует отме- тить, что найденные в ходе работы алгоритма значения хотя и могут существенно отличаться от эталонных, сохраняют исходное глобальное ранжирование. Боль- шое значение относительной ошибки будет свидетельствовать лишь о том, что область значений коэффициентов влияния, которые сохраняют глобальное ран- жирование, довольно «большая», а каждая точка из этой области удовлетворяет условию задачи. В нашем случае ошибка определения коэффициентов влияния очень мала. Это обусловлено большим объемом учебной выборки (ранжирование восьми альтернатив по локальным критериям и глобальному критерию позволяет построить 28 неравенств, на основе которых настраиваются веса [1]). Напомним, что метод не обязательно должен давать точный результат: если набора весов, позволяющего сохранить заданное глобальное ранжирование, не существует, то можно искать набор, для которого расстояние Кемени [1] между реально полученным и заданным глобальными ранжированиями не превышает заданного значения. Также коэффициенты влияния подкритериев нижнего уровня на глобальный критерий могут определяться не только на одном, но и на несколь- ких прецедентах [1]. Заключение Приведенный алгоритм позволяет определять параметры иерархии критериев типа «дерево», для которой заданы ранжирования альтернатив по критериям нижнего уровня (проектам) и глобальному критерию. С помощью метода можно Проблемы управления и информатики, 2008, № 4 91 найти коэффициенты влияния всех критериев иерархии на своих «предков» и ранжирования альтернатив по всем критериям. По построению графа типа «дере- во» каждый участок древовидной иерархии критериев (произвольный критерий и его «потомки»), описывается системой линейных уравнений, имеющей единст- венное решение. Если задача имеет точное решение, то метод сходится к области пространст- ва размерности n, где лежат чувствительности, позволяющие сохранить глобаль- ное ранжирование альтернатив. Если точного решения не существует, то алго- ритм ищет веса, позволяющие максимально приблизиться к заданному глобаль- ному ранжированию. Направлением дальнейших исследований может стать разработка методов определения параметров иерархии критериев типа «сеть» без обратных связей и с обратными связями. С.В. Каденко ВИЗНАЧЕННЯ ПАРАМЕТРІВ ІЄРАРХІЇ КРИТЕРІЇВ ТИПУ «ДЕРЕВО» НА ОСНОВІ ОРДИНАЛЬНИХ ОЦІНОК Описано узагальнення методу визначення коефіцієнтів відносної вагомості критеріїв на основі ординальних оцінок альтернатив на випадок ієрархії крите- ріїв типу «дерево». Стаття містить постановку задачі, опис покрокової роботи алгоритму та результатів його тестування, а також ілюстративні приклади та таблицю, що пояснюють роботу описаного алгоритму. S.V. Kadenko DETERMINATION OF PARAMETERS OF TREE-LIKE CRITERIA HIERARCHY BASED ON ORDINAL ESTIMATES The article describes a modified relative criterion weight calculation method for tree- like criteria hierarchies based on ordinal estimates. The article includes problem statement, description of each algorithm step and results of its testing, as well as ex- amples and tables illustrating the work of the specified method. 1. Каденко С.В. Удосконалення методу визначення коефіцієнтів відносної вагомості критеріїв на основі ординальних оцінок // Реєстрація зберігання і обробка даних. — 2008. — 10, № 1. — C. 137–149. 2. Тоценко В.Г. Методы и системы поддержки принятия решений. — Киев : Наук. думка, 2002. — 382 с. 3. Терехов С.А. Лекции по теории и приложениям искусственных нейронных сетей. Гл. 4. Ла- боратория искусственных нейронных сетей НТО-2, Снежинск, ВНИИТФ, 1998. — http://www.scorcher.ru/neuro/science/perceptron/mem29.htm. 4. Saaty T.L. Decision making with dependence and feedback : The analytic network process. — Pittsburgh : RWS Publ., 1996 — P. 21–22. 5. Norušis M.J. SPSS 16.0 Advanced Statistical Procedures Companion. — Prentice Hall, 2008, Chapter 4. — http://www.norusis.com/pdf/ASPC_v13.pdf. 6. Тоценко В.Г. Методы определения групповых многокритериальных ординальных оценок с учетом компетентности экспертов // Проблемы управления и информатики. — 2005. — № 5. — С. 84–89. 7. Тоценко В.Г., Каденко С.В., Сигал Т.Г. Об одном подходе к рейтингованию высших учеб- ных заведений // Там же. — 2008. — № 1. — С. 87–95. Получено 11.03.2008 После доработки 17.04.2008 http://www.scorcher.ru/neuro/science/perceptron/mem29.htm http://www.norusis.com/pdf/ASPC_v13.pdf

Определение параметров иерархии критериев типа «дерево» на основе ординальных оценок

Institution

Ähnliche Einträge