На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Декабря 2024

Об одном алгоритме классификации объектов на основе модифицированного метода анализа иерархий

A method for classification of objects based on a modified analytic hierarchy
Статья опубликована в выпуске журнала № 1 за 2013 год. [ на стр. 94-97 ]
Аннотация:В работе рассматривается проблема многокритериального принятия решений в условиях неполной информации. Предложен метод классификации и ранжирования объектов при помощи модифицированного метода анализа иерархий, в основе которого лежит метод сравнения объектов альтернатив на базе теории возможностей и правила Демпстера, с помощью которого производится выбор альтернатив в условиях неполноты, неточности и неопределенности экспертной информации. Предложенный в работе подход позволяет избежать построения полной матрицы парных сравнений альтернатив, требуемой для применения классического метода анализа иерархий и большинства его мо-дификаций, путем ввода фрейма различия в качестве базы сравнения альтернатив. Кроме того, предложен метод ранжирования альтернатив на основе теории возможностей. Предложенные методы проиллюстрированы на модельной задаче оценивания моделей альянсов между банками и страховыми компаниями.
Abstract:We are going to investigate the problem of the multi-criteria decision-making under conditions of undetermined information. A method of classifying and ranking objects using a modified method of analytic hierarchy process, which is based on the method of comparing objects of alternatives based on the theory of possibility and Dempster's rule, which allows to select alternatives under incomplete, inaccurate and uncertain expert's information was proposed. The proposed approach avoids the construction of a complete matrix of pairwise comparisons of alternatives required for the application of the classical method of analytic hierarchy process and most of its modifications, by adding the frame of differences as a basis for comparison of alternatives. In addition we proposed a method of ranking alternatives, based on the theory of possibilities. The proposed methods are illustrated on the example of estimation models alliances between banks and insurance companies.
Авторы: Гордеев Р.Н. (rgordeev@naumen.ru) - Тверской государственный университет, Тверь, Россия, кандидат физико-математических наук, Бурилин А.В. (aburilin@naumen.ru) - Тверской государственный университет (ст. преподаватель), Тверь, Россия
Ключевые слова: правило демпстера., теория возможностей, принятие решений, метод анализа иерархий
Keywords: dempster rule, possibility theory, decision making, the method of hierarchies analysis
Количество просмотров: 12056
Версия для печати
Выпуск в формате PDF (5.29Мб)
Скачать обложку в формате PDF (1.21Мб)

Размер шрифта:       Шрифт:

Проблемы классификации и ранжирования объектов встречаются при решении широкого круга задач. Одним из основных направлений, где данные задачи возникают наиболее часто, является теория принятия решений. При этом в последнее время при решении указанных задач часто используются эвристические алгоритмы, а именно метод анализа иерархий (МАИ), предложенный Саати [1, 2]. Однако этот метод предполагает наличие достаточно полной информации о сравниваемых при принятии решений объектах, поэтому сейчас активно развиваются его модификации, нивелирующие данный недостаток.

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

Большинство исследователей [3–5] решают задачу многокритериального принятия решений с неполной информацией, используя следующую двухшаговую процедуру. На первом шаге формируется задача многокритериального принятия решений с полной информацией путем дополнения отсутствующих значений матрицы решений, используя механизм обучения [3, 4] или эвристические правила [5]. На втором шаге применяются стандартные методы многокритериального принятия решений для выполнения задачи с полной информацией.

В отличие от этой двухшаговой процедуры метод, предложенный авторами, позволяет решать задачу многокритериального принятия решений, непосредственно основываясь на неполных экспертных оценках альтернатив по критериям. Результат – доверительные интервалы для групп альтернатив решений. Поскольку во многих практических задачах поддержки принятия решений требуется упорядочить (ранжировать) альтернативы, необходимы специальные методы ранжирования интервалов. В данной работе приведена формализация метода и предложены методы ранжирования альтернатив решений.

Основные понятия и определения

Приведем определения основных понятий, используемых в работе [6].

Пусть G есть произвольное множество с элементами gÎG; P(G) – класс подмножеств G, причем Æ, GÎP(G), E1 – числовая прямая.

Определение 1. Мерой возможности p называется функция множества p: P(G)®E1, обладающая свойствами p(Æ)=0, p(G)=1; , , "I, где I – любое индексное множество.

Определение 2. Триплет (G, P(G), p) называется возможностным пространством.

Введем понятие меры необходимости, двойственной мере возможности.

Определение 3. Мерой необходимости m называется функция множества m: P(G)®[0, 1], определяемая по следующей формуле: m(A)= =1–p(Ac), где Ac есть дополнение A.

При этом функцию m называют функцией доверия и обозначают Bel, а функцию  называют функцией правдоподобия и обозначают Pls.

Функции Bel(A) и Pls(A) интерпретируются как пессимистическая и оптимистическая оценки события A. Интервал [Bel(A), Pls(A)] называется доверительным интервалом.

Определение 4. Множество Q всех взаимоисключающих событий в G называется фреймом различия. Возможными гипотезами являются все возможные подмножества Q, их количество |2Q|.

Для агрегирования независимых доверий относительно одних и тех же гипотез используется правило Демпстера [7], согласно которому агрегированные доверия к гипотезам находятся посредством вычисления ортогональных сумм:

m1⊕m2(A)=,                      (1)

где  – нормировочная константа, интерпретируемая как мера конфликта при агрегировании доверий m1 и m2.

Используя свойство ассоциативности правила Демпстера (1), m1⊕(m2⊕m3)=(m1⊕m2)⊕m3, осуществляется агрегирование трех и более независимых доверий.

Формализация метода

Рассмотрим постановку задачи нахождения доверительных интервалов для альтернатив решений и ранжирования альтернатив по множеству критериев в соответствии с предложенным методом. Под ранжированием будем понимать упорядочение альтернатив в порядке убывания доверия к ним.

Пусть А={Ai | i=1, ..., n} – множество альтернатив решений, а С={Cj | j=1, ..., q} – множество критериев решений.

Требуется найти значения доверий к альтернативам, доверительные интервалы для альтернатив, ранжирование альтернатив.

Для этого каждую группу альтернатив решений будем сравнивать с фреймом различия (все множество альтернатив) по каждому из критериев, и эксперт определит степень «благоприятного знания» для каждой из этих групп альтернатив [8, 9]. Данный факт является принципиальным отличием от метода МАИ, в котором парные сравнения проводятся между отдельными альтернативами. Количество групп альтернатив отображает количество знаний эксперта по данному критерию. К альтернативам, находящимся в одной группе, полагается (имеет место) одинаковое доверие, то есть эксперт не обладает достаточными знаниями для их различения. Кроме того, для агрегирования весов альтернатив по множеству критериев используется правило Демпстера вместо дистрибутивного и идеального методов, применяемых в МАИ.

В итоге метод состоит из семи этапов [8, 9]:

1)    определение множества альтернатив и критериев решений;

2)    нахождение точечных весов критериев по методу собственного вектора МАИ;

3)    формирование групп альтернатив относительно критериев, при этом к альтернативам, находящимся в одной группе, имеется одинаковое доверие;

4)    парное сравнение сформированных групп альтернатив с фреймом различения (всем множеством альтернатив) по каждому из критериев;

5)    нахождение значений функций базового распределения доверия mj(∙) для групп альтернатив и фрейма по каждому из критериев j=1, ..., q методом главного собственного вектора;

6)    агрегирование полученных на предыдущем этапе функций базового распределения доверия, используя правило Демпстера;

7)    расчет значений полного доверия Bel(∙) и правдоподобия Pls(∙), построение доверительных интервалов для групп альтернатив.

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

,  (2)

где di=diQ – количественное выражение степени преобладания группы альтернатив Si над фреймом Q; r – количество групп альтернатив по рассматриваемому критерию; wc – вес критерия. Записывая нули в соответствующие позиции МПП (2), полагаем, что парные сравнения между различными группами альтернатив не производятся.

Значения функции базового распределения доверия mj(∙) для групп альтернатив и фрейма вычисляются как элементы собственного вектора МПП (2), отвечающего наибольшему собственному числу этой матрицы. Используя уравнения det(Dr+1–lIr+1)=0, Dr+1w=lmaxw, нетрудно доказать следующие утверждения.

Утверждение 1. Наибольшее собственное число МПП (2) равно .

Утверждение 2. Элементы нормированного главного собственного вектора MПП (2), соответствующие ее наибольшему собственному числу lmax, равны

                        (3)

Величины wi, i=1, 2, …, r+1, вычисленные по формулам (3), являются значениями функции базового распределения доверия по критерию m(Si)=wi, i=1, 2, …, r, m(Q)=wi+1.

Определение 5. Мерой неполноты экспертной информации по критерию назовем величину m(Q) базового доверия к фрейму по рассматриваемому критерию.

Определение 6. Мерой неполноты экспертной информации по множеству критериев С={Cj | j=1, ..., q} назовем величину (m1⊕m2⊕…⊕mq)(Q) базового агрегированного доверия к фрейму.

В результате применения метода каждой группе альтернатив Si (альтернативе в частном случае) ставится в соответствие доверительный интервал [Beli, Plsi] (рис. 1).

Поскольку значение полного доверия Beli показывает «точное» доверие к группе Si в отличие от значения правдоподобия Plsi, которое, в свою очередь, показывает величину максимального доверия, которое может быть по возможности назначено Si, в данной работе предлагаются следующие два метода ранжирования групп альтернатив:

–      ранжирование в соответствии с убыванием точечных значений Beli полных агрегированных доверий к группам альтернатив;

–      ранжирование, полученное при сравнении доверительных интервалов [Beli, Plsi].

Метод ранжирования групп альтернатив по их доверительным интервалам

Пусть [Beli, Plsi] и [Belj, Plsj] – доверительные интервалы групп альтернатив Si и Sj соответственно. Введем понятие степени нестрогого преобладания интервала для Si над интервалом Sj: p(Si≥Sj)∈[0, 1]. Вычисление значений p(Si≥Sj) будем осуществлять на основе следующих аксиом:

p(Si≥Sj)= =

Матрица степеней нестрогого преобладания Р={(pij=p(Si≥Sj)) | i, j=1, …, n}, где n – количество групп альтернатив, которые необходимо ранжировать, имеет следующие свойства: pij∈[0, 1], pij+pji=1, pii=1/2.

В соответствии с введенными pij метод ранжирования состоит в следующем:

–      вычисление суммы степеней преобладания Si над всеми остальными группами альтернатив: pi=Spij,  j=1, …, n;

–      ранжирование групп альтернатив в соответствии с убыванием значений pi.

Пример

Рассмотрим модельную задачу оценивания моделей альянсов между банками и страховыми компаниями в соответствии с двумя группами критериев: финансовые (С1) и риски (С2) [10]. К финансовым, например, были отнесены такие критерии, как необходимый кредитный капитал, инвестиционные возможности, управление продажами, управление связями с клиентами, соотношение доходы–затраты, логика прибыли, источники конфликтов, экономия вследствие роста масштабов производства и портфеля услуг. Выполним ранжирование десяти альтернативных моделей альянсов M1, М2, МЗ, М4, М5, М6, М7, М8, М9, М10, используя оценки эксперта по указанным двум группам критериев (далее – критериям) (см. табл.).

Результаты оценивания экспертом групп альтернатив

По критерию С1

C1

Q

S11={М5, M7}

1

S12={М1, M8}

5

S13={МЗ, М4, М9}

2

S14={М2}

3

По критерию С2

C2

Q

S21={М6, М8}

4

S22={М1, М9, М10}

2

S23={М2, M5, M7}

3

Данные экспертные оценки доверия к каждой группе выполнены в 7-точечной шкале 1–7, где крайние значения шкалы означают соответственно «очень слабое доверие» и «абсолютное доверие».

В соответствии с методом по формулам (3) для каждого критерия вычисляются значения базового распределения доверия. Например, для критерия С1 весом w1c=0,6 эти значения равны: m1(S11)= =0,072, m2(S12)=0,360, m1(S13)=0,144, m1(S14)=0,216, m1(Θ)=0,208. Следующий этап – агрегирование maggr=m1⊕m2 доверий по критериям по правилу Демпстера (1). Затем вычисляются значения полных доверий и правдоподобий.

Доверительные интервалы групп альтернатив в данном примере равны: {M1}:[0,083, 0,359], {M2}: [0,163, 0,319], {M8}:[0,165, 0,489], {М9}:[0,033, 0,224], {M1, M8}:[0,393, 0,572], {М5, М7}:[0,053, 0,209], {М6, М8}:[0,260, 0,489], {M1, М9, М10}: [0,163, 0,452], {М2, М5, М7}:[0,288, 0,372], {МЗ, М4, М9}:[0,093, 0,224]. Вычислим матрицу P= ={(pij=p(Si>Sj)) | i, j=1, ..., n}, n=10 степеней нестрогого преобладания для этих групп альтернатив, и найдем ранжирование, которое будет следующим: {М8}>{M2}>{M1}>{М9}, {M1, М8}> >{М6, М8}>{М5, М7}, {M2, М5, М7}>{M1, М9, М10}>{МЗ, М4, М9}.

Отметим, что значение базового агрегированного доверия, равное maggr(Θ)=0,085, в соответствии с определением 3 является мерой неполноты экспертной информации по множеству критериев. Таким образом, уровень неопределенности данной задачи принятия решений составляет 8,5 %.

Таким образом, в работе предложен модифицированный метод анализа иерархий, использующий для сравнения альтернатив решающее правило, основанное на теории возможностей и правиле Демпстера. Это позволяет осуществлять поддержку принятия решений в условиях неполноты, неточности и неопределенности экспертной информации. Предложенные методы проиллюстрированы на модельной задаче оценивания моделей альянсов между банками и страховыми компаниями. Направлением дальнейших исследований может быть оценивание чувствительности метода к изменениям во множестве альтернатив решений.

Литература

1.     Saaty T.L., Theory of the Analytic Hierarchy Process, 2003, Part 2.1, no. 1, pp. 48–72.

2.     Saaty Т.L., European Journ. of Operational Research, 2003, no. 145 (1), pp. 85–91.

3.     Fortes I., Mora-L'opez L., Morales R., Triguero F., Math. and Comp. Modelling, 2006, no. 44, pp. 790–806.

4.     Hong T.P., Tseng L.H., Wang S.L., Expert Systems with Applications, 2002, no. 22, pp. 285–293.

5.     Quinten A., Raaijmakers W., Educational and Psychological Measurement, 1999, no. 59 (5), pp. 725–748.

6.     Yazenin A.V., Wagenknecht M., BUTC-UW, 1996, Vol. 6, 143 p.

7.     Dempster A.P., Journ. of the Royal Statistical Society, Series B, 1968, no. 30, pp. 205–247.

8.     Beynon M.J., Curry B., Morgan P.H., Omega, 2000, no. 28 (1), pp. 37–50.

9.     Beynon M.J., European Journ. of Operational Research, 2002, no. 140, pp. 148–164.

10.  Korhonen P., Voutilainen R., European Journ. of Opera­tional Research, 2006, no. 175 (2006), pp. 1285–1299.

11.  Beynon M.J., Computers & Operations Research, 2005, no. 32, pp. 1881–1896.

12.  Beynon M.J., European Journ. of Operational Research, 2005, no. 163, pp. 403–417.

13.  Beynon M.J., Group Decision and Negotiation, 2006, no. 15, pp. 21–42.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=3390&lang=&like=1
Версия для печати
Выпуск в формате PDF (5.29Мб)
Скачать обложку в формате PDF (1.21Мб)
Статья опубликована в выпуске журнала № 1 за 2013 год. [ на стр. 94-97 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: