Элеметы технологии групповой классификации многопризнаковых объектов для поддержки принятия решений

УДК 519.7

С.Г. Чёрный

ЭЛЕМЕТЫ ТЕХНОЛОГИИ ГРУППОВОЙ КЛАССИФИКАЦИИ МНОГОПРИЗНАКОВЫХ ОБЪЕКТОВ ДЛЯ ПОДДЕРЖКИ

ПРИНЯТИЯ РЕШЕНИЙ

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

Данная технология определяет работу не только над комплексом схожести объектов, но и работу нахождения ассоциаций, что является одним из быстроразвивающихся разделов интеллектуальной обработки данных. Методы анализа ассоциаций [1] обычно рассматривают транзакционную исходную модель экспериментальных данных в виде таблицы транзакций и связанных таблиц объектов и в дальнейшем осуществить преобразование к виду плоской таблицы с большим количеством пропусков, поскольку один и тот же объект принимает участие только в ограниченном наборе транзакций. Столбцы данной таблицы идентифицируются именами объектов или идентификаторами их атрибутов/свойств, а строки соответствуют «примерам», в которых объект с заданным свойством возникает или нет. Элементы такой таблицы могут быть представлены в различных шкалах, например, в категориальной шкале (в шкале наименований), числовой или линейно упорядоченной шкалах. Если некоторый объект, которому соответствует определенный столбец в таблице базы данных, присутствует в примере (транзакции), то этот факт кодируется некоторым образом в соответствующей ячейке таблицы, его отсутствие кодируется иным образом. В классических задачах анализа ассоциаций число столбцов может исчисляться тысячами и более, но число примеров, как правило, намного больше: оно может исчисляться десятками миллионов.

Известнодостаточномного подходов к индивидуальнойклассификации объектов, характеризующихся многими количественными и/или качественными признаками [1-4]. В то же время практически отсутствуют методы групповой классификации многопризнаковых объектов. Примером такой задачи может служить конкурсный отбор проектов, оцененных несколькими экспертами по многим критериям.

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

Процедура классификации объектов в рамках формальной логики может быть описана, как элемент совокупности решающих правил, вида:

ЕСЛИ <условия>, ТО <решение>.

При прямой классификации терм <условия> включает названия объектов или перечень значений признаков, описывающих объекты класса, а при непрямой классификации один или несколько термов <условия> трансформируются как отношения между различными признаками и (или) их значениями. Терм <решение> в обоих случаях означает, что объект принадлежит к определенному классу. При рассмотрении задачи групповой классификации объектов согласно представленному множеству объектов (альтернатив) О1,..., Оп, и которые можно описать набором т дискретных признаков Р1,..., Рт имеющими количественные (качественные) шкалы оценок. Каждая группа признаков Ру ={р1у,...,РуУ}, еу = 1,...,ку, у = 1,...,т

характеризует качество объектов. Принадлежность объекта О,, I = 1,...,п к некоторому классу

К, (= 1,..., / выражается атрибутом Я для шкалы Я = {г } характеризующихся {ре,..., рт | ки } .

Многопризнаковые объекты О, , i=1,..,n обычно принято представлять как кортеж р, =

в пространстве Р = Р1 х... х Рт , где Ру = {реуу } - непрерывная или дискретная шкала у признака, еу = 1,..., hy , у = 1,...,т . Трудности расчета заключаются при соответствии нескольких т-мерных векторов одному и тому же объекту О, . В таком случае О, представляется в пространстве Р группы, состоящей из к векторов

/ (!) (к(1) / е1( 1) ет(] )\ . , ,

{р\ ',.••,Й \ вида р -Iрп ,...,рт I,} = 1,.,к , при рассмотрении как единое целое. Оценки экспертов, полученные в результате различных измерений могут носить как одинаковый, так и противоречивый характер, что влечет за собой несовместимость т-мерных векторов

р( 1) = ( рй( 1) ,.••, рт1)) ,который описывает объект О, . Композиция таких, достаточно сложных структур, приводит к проблематичности анализу.

Выбор альтернативы Ан из множества «новых» альтернатив Л = {Лн } , h = (1, Н), с учетом опыта ЛПР относительно качества ранее выбранных решений из множества Р = {р } , , = (1, к), осуществим при условии, что этому решению присваивается базис ранг Я,, равный номеру позиции этого решения (прецедента) Р , в ряду Р базис-предпочтений; а каждому прецеденту Р е Р ставится в соответствие

вектор Sj = {%,si2,...,}, приусловии, что каждойновойальтернативе Лк еЛ -вектор Sh = {%,яЬ2,...,} оценок по частным критериям, представляющих собой частные ранги (номера позиций в рядах предпочтений по соответствующим частным критериям, Я/ -номер позиции альтернативы А в ряду предпочтений альтернатив Л, е Л по / -му частному критерию).

Поставим в соответствие каждому прецеденту и каждой альтернативе функцию важности Р ^п, sj2, • • •, sjg; w1, , • • •, wg). Величины м>1, w2,..., wg будем называть весами частных критериев оценки альтернатив и определив эти величины так, чтобы значения функции значимости —, —2,..., —к на векторах оценок прецедентов Р1, Р2,..., Рк были упорядочены правилу V, = 1, к [О, = Я, ], где О, - ранг значения .

Очевидно, что значения весов частных критериев, определенные таким образом, несут информацию об опыте ЛПР относительно качества его предыдущих решений. Визуализация данного набора представлений удобна на основании предоставления шкал. Из множества существующих шкал наиболее часто применяются шкалы измерений для оценивания приоритетности критериев качества функционирования систем. Математическую модель шкалы Sc представляемую кортежем [2-5]:

Sc = < С, 1 , и >,

где X = {хр..., х.,..., хп; Rx} - множество элементов х. е X системы и отношений Rx между ними; и = {у1 ,..., у. =ф(х.),..., уп; Ry} - множество элементов у. е Y шкалы и отношений Ry между ними; Ф еФ = {ф .., фп} - гомоморфне отображение множества элементов X на множество элементов Y, которое сохраняет базовые отношения и операции, то есть устанавливает соответствие между X и и таким образом, что {ф (х1),., ф (хп)} I Ry, тогда и только тогда, когда (хр..., хп)е Rx; тип шкалы определяется по гомоморфному отображению Ф, то есть по множеству допустимых преобразований х. ^ у..

Шкалой отношения называется шкала [6], в которой численные значения числовой системы ич определяется с точностью до преобразований подобия ф

ф

и ф(/ (а2)), где ф(х) = ах, а > 0 . тогда получаем —-:—тт- = ——;—т = —:—т. В шкале интервалов

ф

отношения оценок альтернатив не сохраняются [7,8], но сохраняется отношение разностей численных оценок. Пусть, альтернативам а1, а2, а3, а4 в некоторой числовой системе ич соответствуют числа / (а1), / (а2), / (а3), / (а4), в другой числовой системе, в которую так же гомоморфно отображается имперически система, числа ф[ / (а1)] , / (а2)] , / (а3)] , / (а4)], где ф(х) = ах +/3, а> 0 -

„ й „ ф

линейное преобразование. Исходя из этого - —¡——тт—-¡——тг = ———г———т = ——г———т.

ф

Таблично представим характеристики.

Таблица 1

Измерения Шкала Допустимые преобразования

Качественная Номинальная ф( х) - взаимно однозначные

Порядка ф( х) - монотонные

Гиперпорядка ф( х) - монотонные, сохраняющие порядок первых разностей

Количественная Интервалов ф (х) = ах + Ь, а > 0

Отношений ф(х) = ах,а > 0

Разностей ф( х) = х + р

Абсолютная (ф )x = x

Частным случаем шкалы интервалов является шкала разностей, т.е. при переходе от одной числовой системы к другой, соответствующей той же эмпирической системе, меняется лишь начало отсчета. Допустимыми преобразованиями численных оценок при измерении в шкале разностей являются только преобразования сдвига ф ( x) = x + р .

Качественные измерения альтернатив являются менее строгими [8-9], соответствующие типы шкал

- менее «сильными», а допустимые преобразования числовых систем образуют более широкий класс. Порядковой шкалой называется шкала, в которой численное значение числовой системы U4 определяется с точность до монотонных преобразований ф

. С вопросом допустимости преобразовании оценок в шкалах различных типов тесно связана задача нахождения агрегированных групповых оценок. Доказано [4-6], что операция нахождения среднего арифметического корректна для вычисления агрегированных оценок в абсолютной шкале, шкалах отношений, разностей и интервалов с последующим сравнением альтернатив по этим агрегированным оценкам. Действительно, пусть m экспертов дали альтернативам Aj, A2 оценки f (Aj), f2 (A2), • • •, fm (Ai) и f (Aj), f2 (A2),•.., fm (A2) соответственно и при сравнении альтернатив по их средним арифметическим оценкам выполняется неравенство

[ fi (Aj )+ f2 (Aj ) + • + fm (Aj )] / m >[ fi (A2 ) + f2 (A2 )+ • + fm (A2 )] / m .

При переходе к другой шкале интервалов, применяя допустимое для этого типа шкал линейное преобразование ф (x) = ax + 8, получаем

a[fj (Aj) + fj (Aj) + • + fm (Aj)]/m + 8>a[fj (A2) + f2 (A2) + • .. + fm (A2)]/ m + 8 предпочтения средних арифметических оценок альтернатив сохраняется при линейных преобразованиях, допустимых для шкал интервалов и более «сильных» шкал отношений и абсолютной. Справедливо это для среднего геометрического в абсолютной шкале и шкале отношений, а для порядковой шкалы в качестве среднего используют медиану.

Вариант модели отбора эксперта для группы можно представить, как кортеж ресурса модели для дальнейшего формирования критерия отбора:

Uf =

где Ult - возраст эксперта; Ustg - стаж работы в «проблемной области»; Upub - количество публикаций по проблеме; Uvst - количество выступлений связанных с проблематикой решения задачи; Udl

- занимаемая должность; Uus - ученая степень; Uzv - научное звание; Upt - количество патентов,

свидетельств (связанных с решаемой проблемой); Usam - самооценка компетентности; Uusp - количество успешных реализованных проектов; Uimn - характеристика эксперта другими экспертами;

или как функциональная зависимость от них

Uf = {kiUlt + k2Ustg + к3 Upub + k4Uvst + k5U

dl + k6Uus + k7Uzv + k8Upt + k9Usam + k10U usp + kUUimn) ,

где k, k2,..., kjj - весовые коэффициенты.

Uft = (Щ); Uft = XkuU'u ; ^g = (u^) ; Ustg = Xk^ ; ii

Upub = (Ulpu^j ; Upub = Xk3jUpub ; Uvst = (Uvst) ; Uvst = Xk4JUvst ;

ii

Udi = (u^) ; Udi = Xks.iUdi ; иш = (u^) ; Uus = XkU ;

ii

Uzv = (u^) ; Uzv = Xk^ ; Upt = (u;) ; Upt = XkU ;

ii

U = luj У U = V k Uj • U = luq V U = V k nq •

sam \ sam sam / , 9, j sam usp \ usp usp / , 10, q usp

j q

U = /ux \ - U = V k Ux

imn \ imn imn / ,"11,x imn r

x

где k1i,..., k8i, k9, j, k10, q, k11, x - весовые коэффициенты.

Определение группы экспертов и шкалы представления для оценки многопризнаковых объектов можно применить и методику оценки альтернативного выбора для анализа расхождений (как один из множества вариантов оценки). Непосредственная численная оценка альтернатив является распространенным приемом в практике получения экспертной информации, эксперту предъявляется набор альтернатив a1,..., an . В том случае, когда цель экспертизы заключается в оценке их сравнительной предпочтительности то эксперт ставит в соответствие каждой альтернативе ai, i е {1,...,n} число f (ai), характеризующее ее предпочтительность. Когда известна численная оценка каждой альтернативы, можно получить сравнительную оценку предпочтительности для каждой пары альтернатив; можно определить, на сколько условных единиц или во сколько раз одна альтернатива превосходит другую. Если цель экспертизы заключается в разбиении альтернатив на классы, тогда для каждой пары альтернатив эксперт указывает численную оценку степени сходства.

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

1 f (ai )> f (aj )J, а численная оценка aj выше численной оценки al, | f (aj )> f (al )J, тогда численная оценка альтернативы ai выше численной оценки al | f (ai )> f (al)] . Часто используется оценивание альтернатив в баллах, причем каждой альтернативе в выбранной системе баллов приписывается балл, соответствующее ее оценке, чем выше предпочтение, тем выше балл.

Среди методов непосредственной оценке альтернатив применяется и метод средней точки, он применяется при достаточно большом наборе альтернатив. Пусть экспертом указаны наиболее и наименее предпочтительные альтернативы aj и a2 .После этого эксперту предлагается указать альтернативу a3, по предпочтительности расположенную точно между aj и a2, так что f (a3) = |f (aj) + f (a2)]/2. Далее эксперту предлагается указать альтернативы, расположенные по предпочтительности точно между aj и a3 , между a3 и a2 и т.д. Процесс заканчивается тогда, когда оценок альтернатив оказывается достаточно для получения кривой.

Метод Чёрчмена-Акофа для последовательной корректировке оценок, указанных экспертами. Основные предположения на которых основан метод, следующие: каждой альтернативе ai, i е {1,...,n} ставится в соответствие действительное неотрицательное число f (ai); если альтернатива ai предпочтительнее альтернативы aj, то f (ai )> f (aj), но если альтернативы ai и aj равноценны, то f (ai ) = f (aj); если f (ai) и f (aj) - оценки альтернатив ai и aj, то f (ai) + f (aj) соответствует совместному осуществлению альтернатив ai и aj. Наиболее сильным является последнее предположение об аддитивности оценок альтернатив.

Согласно методу Чёрчмена-Акофа альтернативы aj,...,an ранжируются по предпочтительности. Пусть для удобства изложения альтернатива aj наиболее предпочтительная, за ней следует a2 и т.д.

Эксперт должен указать предварительные численные оценки / (аг) для каждой из альтернатив. Иногда наиболее предпочтительной альтернативе приписывается оценка 1, остальные оценки располагаются между 0 и 1 в соответствии с их предпочтительностью. Далее эксперт производит сравнение а1 и суммы

п

альтернатив а2,...,ап . Если а1 предпочтительнее, тогда эксперт корректирует оценки /(а1 )>^/(аг),

г =2

п

иначе в противном случае должно сохранятся неравенство /(а1 /(аг). Если альтернатива а1

г =2

оказалась менее предпочтительной, то для уточнения оценок она сравнивается по предпочтению с суммой альтернатив а2,...,ап-1 и т.д. После того как а1 оказывается предпочтительнее суммы альтернатив а2,...,ак (к > 2), данная альтернатива исключается из рассмотрения, а вместо оценки рассмотрения альтернативы а1 рассматривается и корректируется оценка а2 . Процесс длится до тех пор, пока скорректированы оценки всех альтернатив. При достаточно большом п применение метода Чёрчмена-Акофа становится слишком трудоемким и тогда целесообразно разбиение альтернатив на группы, одну из альтернатив, например максимальную, включив во все группы, что позволяет получить численные оценки всех альтернатив с помощью оценивания альтернатив внутри каждой из групп.

Метод Терстоуна [5,7,8,9] для численных оценок предпочтительности альтернатив используются парные сравнения. Через ву обозначим частоту выбора альтернативы аг в качестве более предпочтительной при сравнении с альтернативой ау . Случайная величина предполагается распределенной по нормальному закону с математическим ожиданием Мг и дисперсией ог2. Разность случайных величин / (аг) и / (а у) так же распределена по нормальному закону с математическим ожиданием Му = Мг - М у и дисперсией

Ст;2 = о2 + о2 - 2гуООу, где Гу - коэффициент корреляции между /(аг) и /(а у). Задачей определения величины Мг, I е {1,...,п} , которые в этом случае и выбираются в качестве численных оценок альтернатив по значениям частот ву. Частота ву характеризуется вероятностью того, что / (аг )> / (а у):

Iе/ \2

,„ = р (/ (, )> / (., ))=- М ^ *

V 0

При помощи таблицы квантилей нормального распределения определяем отношения М у / о^ и

Му г—2-2-

получаем п (п -1) /2 уравнений: Мг -Му =-.Лстг +Оу - 2гуООу , называемых уравнениями

сравнительного суждения. Число неизвестных в системе больше числа переменных. Делая дополнительные предположения, а именно пологая Гу = 0, о = о у и выбрав в качестве единицы шкалы ^/2стг получаем переопределенную систему уравнений Мг - М у = Му / о у.

Метод фон Неймана-Моргенштерна заключается в способе получения численных оценок альтернатив с помощью так называемых вероятностных смесей предложен Фон Нейманом и Моргенштерном [8,9,10]. В основе метода лежит предположение, согласно которому эксперт для любой альтернативы а у, менее предпочтительней чем аг, но более предпочтительнее чем а{, может указать число р (0 < р < 1), такое, что а у эквивалентна смешенной альтернативе \^раг, (1 -р) а1 ] . Смешанная альтернатива состоит в том, что альтернатива аг выбирается с вероятностью р , а альтернатива а1 - с вероятностью 1 - р ; очевидно что если р достаточно близко к 1, то альтернатива а у менее предпочтительна, чем смешанная альтернатива \_раг, (1 -р) аг ]; если р достаточно близко к 0, то альтернатива а у более предпочтительна, чем смешанная альтернатива \_раг,(1 -р)а1 ] . Этот подход развивался в работах [8-10]. В них рассматривалась, помимо упомянутого выше предположения, система предположений о свойствах смешанных и несмешанных альтернатив. К числу таких предположений относятся: предположение о связанности и транзитивности отношения предпочтительности альтернатив; предположения о том, что смешанная альтернатива \раг, (1 -р) а1 ] предпочтительнее чем \_р'аг, (1 -р') а1 ], если р > р' и др. Если указанная система предпочтений выполнена, то для каждой из набора основных альтернатив а1,.,аг определяются числа и1,...,иг, характеризующие численную оценку смешанных альтернатив. Численная оценка смешанной альтернативы [р1а1,р2а2,...,ргаг] равна и1р1 + и2р2 + . + игрг. Смешанная альтернатива [р1а1, р2а2,., ргаг ] предпочтительней, чем смешанная альтернатива [р1а1, р2 а2,., р'гаг ], если и1р1 + и2р2 + . + игрг > и1р1' + и2р'2 +... + игр'г ,тогда устанавливается существование функции полезности и1р1 + и2р2 + . + игрг, значение которой характеризует степень предпочтительности любой смешанной

альтернативы, а в частности, и не смешанной. Более предпочтительней та смешанная альтернатива, для которой значение функции полезности больше. Уровень квалификации эксперта в определенной отрасли знаний в общем виде определяется:

Л = {4|£ = ÏÏ},

Л - множество значений компетентности экспертов; Як - коэффициент компетентности к -го эксперта.

Вывод. Проблемы классификации объектов, которые описываются многими количественными и/или качественными признаками, причем каждый из объектов может существовать в нескольких различающихся «состояниях», являются достаточно трудными для решения и реализации алгоритмами. Применение методик экспертного оценивания в моделях управления развитием [11] достоточно актуальная тема. Рассмотренная задача формирования экспертной группы для решения задач ранжирования и оценки многопризнаковых объектов и дальнейшего анализа, набирает популярность в последнее время. Алгоритмичность процессов формирования и решения сложных структур связаны прежде всего с содержательным основанием и формальными причинами (например, большая размерность задачи). Предлагается осуществлять анализ структур с помощью смешанных шкал и детализации задания экспертной группой по набору стандартизированных механизмов (методик) анализа.

ЛИТЕРАТУРА

1. Petrovsky A. B. Multi-Attribute Sorting of Qualitative Objects in Multiset Spaces // Multiple Criteria Decision Making in the New Millenium. Berlin: Springer-Verlag, 2001. P. 124-131.

2. Коваленко И.И. Экспертные оценки в управлении инновационными проектами: Учеб. пособие. / Коваленко И.И., Драган С.В., Рыхальский М.А. - Николаев: НУК, 2007. - 168 с.

3. Гнапенко Г.М. Експертш Технологи прийняття ршень: Монографiя. / Гнапенко Г.М., Снитюк В.£. -К.: ТОВ «Маклаут», - 2008. - 444 с.

4. Литвак Б.Г. Экспертная информация: методы получения и анализа. / Литвак Б.Г. - М.:Радио и связь, 1982. - 184 с.

5. Сидельников Ю.В. Теория и организация экспертного прогнозирования / Сидельников Ю.В. - М.: ИМЭМО РАН, 1990. - 196 с.

6. Снитюк В.£. Прогнозування. Моделг Методи. Алгоритми: Навчальний поабник. / Снитюк В.£. - К.: ТОВ «Маклаут», - 2008. - 364 с.

7. Коваленко И.И. Методы и средства поддержки принятия решений: Учебное пособие. / Коваленко И.И., Гожий А.П. - Николаев, 2005. - 104 с.

8. Китаев Н.Н. Групповые экспертные оценки. / Китаев Н.Н. - М.: Знание, 1975. - 64 с.

9. Панкова Л.А. Организация экспертизы и анализ экспертной информации./ Панкова Л.А., Петровский А.М., Шнейдерман М.В. - М.: Наука, 1984. - 120 с.

10. Тоценко В.Г. Експертш системи дiагностики i пвдтримки ршень / Тоценко В. Г. - К. : Наукова думка, 2004. - 126 с.

11. Петров Э.Г. Методы и средства принятия решений в социально-экономических и технических системах. Учебное пособие. / Петров Э.Г., Новожилова М.В., Гребенник И.В., Соколова Н.А. - Херсон: ОЛДИ-плюс, 2003. - 380 с.

ЧЁРНЫЙ Сергей Григорьевич - к.т.н. кафедра электрооборудования судов и автоматизации производства Керченского государственного морского технологического университета

Научные интересы: технологии экспертной оценки.