Метод согласования кластеризованных ранжировок
Проблема состоит в выделении общего нестрогого порядка из набора кластеризованных ранжировок (на статистическом языке - ранжировок со связями). Этот набор может отражать мнения нескольких экспертов или быть получен при обработке мнений экспертов различными методами. В различных прикладных областях (экология, инженерный бизнес, менеджмент, экономика, социология, прогнозирование, научные и технические исследования) возникает необходимость анализа нескольких кластеризованных ранжировок объектов. В качестве объектов могут выступать образцы продукции, технологии, математические модели, проекты, кандидаты на должность и др. Кластеризованные ранжировки могут быть получены как с помощью экспертов, так и объективным путем, например, при сопоставлении математических моделей с экспериментальными данными с помощью того или иного критерия качества. Описанный ниже метод был разработан в связи с проблемами химической безопасности биосферы и экологического страхования.
Рассмотрим метод построения кластеризованной ранжировки, согласованной со всеми рассматриваемыми кластеризованными ранжировками. При этом противоречия между отдельными исходными ранжировками оказываются заключенными внутри кластеров согласованной ранжировки. В результате упорядоченность кластеров отражает общее мнение экспертов, точнее, то общее, что содержится в исходных ранжировках. В кластеры заключены объекты, порождающие противоречия некоторых из исходных ранжировок. Для их упорядочения необходимо провести новые исследования.
Поясним формирование кластеризованной ранжировки на примере. Пусть имеется конечное число объектов, которые мы для простоты изложения будем изображать натуральными числами 1,2,3,...,k и называть “носителем”, объекты разбиты на группы-кластеры, причём в кластере может быть и один элемент. Входящие в один кластер объекты будем заключать в фигурные скобки. Например, объекты 1,2,3,...,10 могут быть разбиты на 7 кластеров: {1}, {2,3}, {4}, {5,6,7}, {8}, {9}, {10}. В этом разбиении один кластер {5,6,7} содержит три элемента, другой кластер {2,3} - два, остальные пять - по одному элементу. Кластеры не имеют общих элементов, а объединение их (как множеств) есть все рассматриваемое множество объектов. Между кластерами установлен строгий линейный порядок, т.е. задано, какой из них первый, какой второй, и т.д. Изображается упорядоченность с помощью знака <. При этом кластеры, состоящие из одного элемента, будем для простоты изображать без фигурных скобок. Тогда кластеризованную ранжировку на основе введенных выше кластеров можно изобразить так: А = [ 1 < {2,3} < 4 < {5,6,7} < 8 < 9 < 10 ]. Конкретные кластеризованные ранжировки будем заключать в квадратные скобки.
Введенная описанным образом кластеризованная ранжировка является бинарным отношением на множестве {1,2,3,...,10}. Задано отношение эквивалентности с 7-ю классами эквивалентности, а именно, {2,3}, {5,6,7}, а остальные состоят из оставшихся 5 отдельных элементов. Затем введен строгий линейный порядок между классами эквивалентности. Введенный математический объект известен в литературе как "ранжировка со связями" (М. Холлендер, Д.Вулф), "упорядочение" (Дж. Кемени, Дж. Снелл), "квазисерия" (Б.Г.Миркин), "совершенный квазипорядок" (Ю.А. Шрейдер). Термин "кластеризованная ранжировка" явным образом называет основные элементы изучаемого математического объекта - кластеры, рассматриваемые на этапе согласования ранжировок как классы эквивалентности, и ранжировку - строгий совершенный порядок между ними.
Рассмотрим смысл понятия противоречивость. Оно определяется для четверки - две кластеризованные ранжировки на одном и том же носителе и два различных объекта - элементы того же носителя. При этом два элемента из одного кластера будем связывать символом равенства, как эквивалентные.
Пусть А и В - две кластеризованные ранжировки. Пару объектов (a,b) называют “противоречивой”относительно А и В, если эти два элемента по-разному упорядочены в А и В, т.е. a < b в А и a > b в В (первый вариант противоречивости) либо a >b в А и a < b в В (второй вариант противоречивости). Отметим, что в соответствии с этим определением, пара объектов (a,b), эквивалентная хотя бы в одной кластеризованной ранжировке, не может быть противоречивой: a = b не образует "противоречия" ни с a < b, ни с a > b.
В качестве примера рассмотрим две кластеризованные ранжировки В = [{1,2} < { 3,4, 5} < 6 < 7 < 9 < {8, 10}], C = [3 < {1, 4} < 2 < 6 < {5, 7, 8} < {9, 10}]. Совокупность противоречивых пар объектов для двух кластеризованных ранжировок А и В называют “ядром противоречий”и обозначают S(A,B). Для рассмотренных выше в качестве примеров трех кластеризованных ранжировок А, В и С, определенных на одном и том же носителе {1, 2, 3,..., 10}, имеем S(A,B) = [ (8, 9)], S(A,C) = [ (1, 3), (2,4) ] , S(B,C) = [ (1, 3), (2, 3), (2, 4), (5, 6), (8,9) ] . Как при ручном, так и при программном нахождении ядра можно в поисках противоречивых пар просматривать пары (1,2), (1,3), (1.,4), ...., (1, k), затем (2,3), (2,4), ..., (2, k), потом (3,4), ..., (3, k), и т.д., вплоть до (k-1, k).
“Ядро противоречий” можно изобразить графом с вершинами в точках носителя. При этом противоречивые пары задают ребра этого графа. Граф для S(A,B) имеет только одно ребро (одна связная компонента более чем из одной точки), для S(A,C) - 2 ребра (две связные компоненты более чем из одной точки), для S(B,C) - 5 ребер (три связные компоненты более чем из одной точки {1, 2 , 3, 4}, {5, 6} и {8, 9}).
Каждую кластеризованную ранжировку, как и любое бинарное отношение, можно задать матрицей || x(a, b) || из 0 и 1 порядка k* k. При этом x(a, b) = 1 тогда и только тогда, когда a < b либо a = b. В первом случае x(b, a) = 0, а во втором x(b, a) = 1. При этом хотя бы одно из чисел x(a, b) и x(b, a) равно 1. Из определения противоречивости пары (a, b) вытекает, что для нахождения всех таких пар достаточно поэлементно перемножить две матрицы ||x(a,b)|| и ||y(a, b)||, соответствующие двум кластеризованным ранжировкам, и отобрать те и только те пары, для которых x(a,b)y(a,b)=x(b,a)y(b,a)=0.
Предлагаемый алгоритм согласования некоторого числа кластеризованных ранжировок состоит из трех этапов:
1) выделение противоречивых пар объектов во всех парах кластеризованных ранжировок;
2) формирование кластеров итоговой кластеризованной ранжировки (т.е. классов эквивалентности - связных компонент графов, соответствующих объединению попарных ядер противоречий);
3) упорядочение этих кластеров (классов эквивалентности). Для установления порядка между кластерами произвольно выбирается один объект из первого кластера и второй - из второго, порядок между кластерами устанавливается такой же, какой имеет быть между выбранными объектами в любой из рассматриваемых кластеризованных ранжировок.
Два объекта из разных кластеров согласующей кластеризованной ранжировки могут оказаться эквивалентными в одной из исходных кластеризованных ранжировок (т.е. находиться в одном кластере). В таком случае надо рассмотреть упорядоченность этих объектов в какой-либо другой из исходных кластеризованных ранжировок. Если же во всех исходных кластеризованных ранжировках два рассматриваемых объекта находились в одном кластере, то естественно считать (и это является уточнением к этапу 3 алгоритма), что они находятся в одном кластере и в согласующей кластеризованной ранжировке.
Результат согласования кластеризованных ранжировок А, В, С,... обозначим f(А, В, С,...). Тогда f(А, В) = [1<2<3<4<5<6<7<{8, 9}<10], f(А, С) = [{1,3}<{2, 4}<5<6<7<8<9<10], f(В, С) = [{1,2,3,4}<{5,6}<7<{8,9}<10], f(А, В, С) = f(В, С) = [{1,2,3,4} <{5,6}<7<{8, 9}<10]. В случае f(А, В) дополнительного изучения с целью упорядочения требуют только объекты 8 и 9. В случае f (В, С) объекты 1,2,3,4 объединились в один кластер, т.е. кластеризованные ранжировки оказались настолько противоречивыми, что процедура согласования не позволила провести достаточно полную декомпозицию задачи нахождения итогового мнения экспертов.
Рассмотрим некоторые свойства алгоритмов согласования. Пусть D = f(А, В, C). Если a<b в согласующей кластеризованной ранжировке D, то a<b или a=b в каждой из исходных ранжировок А, В, C. Построение согласующих кластеризованных ранжировок может осуществляться поэтапно. В частности, f(A, B, C) = f(f(A, B), f(A, C), f(B, C)) . Ядро противоречий для набора кластеризованных ранжировок является объединением таких ядер для всех пар рассматриваемых ранжировок. Построение согласующих кластеризованных ранжировок нацелено на выделение общего упорядочения в исходных кластеризованных ранжировках. Однако при этом некоторые общие свойства исходных кластеризованных ранжировок могут теряться. Так, при согласовании ранжировок В и С, рассмотренных выше, противоречия в упорядочении элементов 1 и 2 не было - в ранжировке В эти объекты входили в один кластер, т.е. 1 = 2, в то время как 1<2 в кластеризованной ранжировке С. Значит, при их отдельном рассмотрении можно принять упорядочение 1 < 2. Однако в f(В,C) они попали в один кластер, т.е. возможность их упорядочения исчезла. Это связано с поведением объекта 3, который "перескочил" в С на первое место и "увлек с собой в противоречие" пару (1, 2), образовав противоречивые пары и с 1, и с 2. Другими словами, связная компонента графа, соответствующего ядру противоречий, сама по себе не всегда является полным графом. Недостающие ребра при этом соответствуют парам типа (1, 2), которые сами по себе не являются противоречивыми, но "увлекаются в противоречие" другими парами.