Меры близости на бинарных отношениях

Способы получения мер близости. Общепринятым путем для получения формул или алгоритмов вычисления расстояний между отношениями является аксиоматический.

В этом случае выполняется следующая последовательность шагов.

1. Формулирование системы аксиом, которые удовлетворяют определенные требования и допущения.

2. Доказательство теоремы существования одной и только одной меры близости в отношениях, которые основываются на созданной системе аксиом.

3. Получение формулы (или алгоритма) для расчета меры близости.

В реальных условия выбор и обоснование возможностей использования той или иной меры близости ложится на аналитическую группу, которая и учитывает первичные требования.

Существование мер близости позволяет совершить постановку и решить следующие практические важные задачи.

1. Построить результирующее отношение на основе отношений полученных от экспертов.

2. Найти отношение с определенным набором свойств, которое является самым близким к экспертному.

3. Классифицировать экспертов по результатам бинарных отношений, построенных ими.

4. Сформулировать обобщенные критерии и проверить уровень противоречивости экспертов.

Меры близости при ранжировании. Для произвольной меры близости должны выполняться три основные аксиомы метрики: аксиома неотъемлемости, симметричности расстояния и аксиома треугольника.

Аксиома 1. Аксиома неотъемлемости расстояния. Расстояние d между двумя произвольными отношениями Р₁ и Р₂ является величиной неотъемлемой, то есть . Равенство достигается лишь тогда, когда отношения равны Р₁ = Р ₂

Аксиома 2. Аксиома симметричности расстояния. Расстояние является симметрической величиной, то есть .

Аксиома 3. Аксиома треугольника. Для произвольных отношений Р₁, Р₂, Р₃ справедливо неравенство (неравенство треугольника). Равенство достигается, когда отношения Р₁, Р₂, Р₃ находятся «на одной прямой». Некоторые ученые рассматривают ситуацию равенства отдельно как еще одну аксиому.

Будем считать по определениям, что ранжирование Q находится между ранжированиями Р и R, если для всех элементов матриц выполняется условие

Таким образом в ранжировании Q альтернатива х_i лучше х_j, если хотябы в одном из ранжирований Р или R альтернатива х_i лучше х_j.Альтернатива х_i и х_j могут быть равноценными в ранжировании Q, если они равноценные в Р и R, или упорядочены противоположно в Р и R. Записываются [P, Q, R], если Q находится между Р и R. Обобщим понятие прямой следующим образом: ранжирования Р₁, Р₂, …, Р_k расположены на прямой, если для произвольных Р_i, Р_j, Р_l, которые принадлежат этому множеству ранжирований справедливо [Р_i, Р_j, Р_l], где , то есть

Аксиома 4. Аксиома прямой. Если ранжирование Q находится между Р и R, то есть [P, Q, R], то

Аксиома 5. Аксиома равноправия альтернатив. F:A®A – некоторая перестановка альтернатив. Если отношения Р’ и R’ получены из Р и R путем перенумерации (перестановки) альтернатив, , то есть от перенумерации расстояние между отношениями не изменяется.

Аксиома 6. Аксиома отличий. Значение меры близости между ранжированием Р и R определяются теми сегментами этих ранжирований, в которых есть отличия в упорядочивании альтернатив, то есть расстояние между идентичными сегментами ранжирования равно 0.

Аксиома 7. Аксиома масштаба измерений. Минимальное позитивное расстояние между ранжированиями равно 1.

Лемма. Если ранжирование Р₁, Р₂, …, Р_k, расположено на прямой то справедливо соотношение

.

Лемма. Для строгого ранжирования Р аксиомы 1-7 однозначно определяют расстояния и , а именно , где n=card(A) (множество альтернатив не бесконечно, 0 – это ранжирование, в котором все альтернативы равноценны).

Теорема. Аксиомы 1-7 определяют единственную (одну и только одну) меру близости на ранжировании.

Теорема. Расстояние между двумя произвольными ранжированиями Р_j и Р_l, которые удовлетворяют аксиомам, определяется по формуле:

.

Расстояние между двумя произвольными ранжированиями Р_j и Р_l можно рассчитать так же с помощью значений элементов матриц М(Р_j) и М(Р_l), которые расположены над главной диагональю по формуле:

.

Для неметризованных отношений понятие расстояния между отношениями Р_k и Р_l определяется степенью расхождения между соответствующими матрицами отношений и . Следует однако понимать, что так как матрицы неметризованных отношений не имеют, метричной интерпретации, элементами этих матриц могут быть не обязательно 1 и 0, но и произвольные элементы, которые отличаются между собой.

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

Разделим метризованные отношения на два класса соответственно к представлению их в виде матрицы Р^М: М(Р^М)^Р – класс метризованных отношений порядка и линейного порядка и М(Р^М)^Т – класс метризованных отношений толерантности и эквивалентности.

Матрицы метризованных отношений согласованны.

Матрица аддитивного метризованного отношения будет согласованной, если для всех элементов выполняется условие: (считаем, что 0=-0 и ). Соответственно матрица метризованных отношений будет согласованной, если для всех элементов .

Если матрицы метризованных отношений согласованны, то в классе М(Р^М)^Р для определения расстояния достаточно рассматривать элементы матрицы такие, для которых , а для толерантностей и эквивалентностей- такие , для которых , и в обоих случаях i£j. Поэтому далее расстояние между метризованными отношениями будет определяться на этих подмножествах элементов матрицы Р^М.

Метризованные отношения Q находится между метризованными отношениями P и R, если выполняются следующие условия:

Если метризованные матрицы согласованны, используется аксиома 5а, если несогласованны то 5б.

Аксиома 5а. Если Р и Q отличаются лишь одной упорядоченной парой альтернатив (x_i,x_j), то расстояние между Р и Q определяется следующим образом:

где w – некоторое число, которое удовлетворяет условию ,то есть можно выбрать .

Аксиома 5б. Если Р и Q отличаются лишь одной упорядоченной парой альтернатив (x_i,x_j), то расстояние между Р и Q определяется следующим образом:

Теорема. Мера близости между согласованными аддитивными метризованными отношениями толерантности, эквивалентности, частично упорядоченными множествами, ранжированиями определяется по формуле:

где

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

Теорема. Мера близости для несогласованных аддитивных метризованных отношений определяется по формуле:

.

Информация о преимуществах может быть представлена также в виде вектора преимуществ , где n – количество альтернатив, значения является числом альтернатив, которые преобладают .

Если информация о преимуществе эксперта представляется в виде векторов преимущества , то для получения формулы для расстояния между ними используются аксиомы 1-4, и аксиома минимального расстояния 5с.

Аксиома 5с. Если вектор преимущества и отличаются лишь одной i-ой компонентой, то расстояние между ними составляет . В этом случае мера близости между произвольными векторами преимуществ и рассчитывается по следующей формуле:

.

Структурные меры близости. Использование аналогии между мерами близости на отношениях и метриками на графах позволяет получить структурные меры близости. Для этого рассмотрим множество носитель отношений А={x₁,x₂,…,x_n} и множества P={P₁, P₂,…, P_n} всех возможных отношений определенного заданного типа с носителем А. Каждому отношению поставим в соответствие i-тую вершину конечного графа G. Если два отношения P_i,P_jÎP являются соседними, то они соединяются между собой дугой. Каждой дуге графа ставиться в соответствие число, что характеризует расстояние между соседними отношениями согласно определенного закона, который отображает специфические особенности меры. Считаем, что отношение является неметризованными, потому что в другом случае множество вершин графа G является безграничным.

Понятия «находятся между» в этом случае формулируются следующим образом: считаем, что Q находится отношениями Р и R, если вершины графа G, что соответствует отношение Q, находится на кратчайшем пути, который связывает вершины, которые соответствуют Р и R. При условии действия аксиомы 1-4 и аксиомы 5д структурная мера близости является однозначной.

Аксиома 5д. Если Р и Q – соседние отношения, то -число, которое является мерой близости между ними.

Чтобы найти расстояние между произвольными отношениями, необходимо найти кратчайший путь в графе G между соответствующими вершинами.

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

Аксиома 5е. Если ранжирования Р и Q отличаются лишь инверсией альтернатив, которые расположены на i-ом та (i+1) местах, то , и , потому что ранжируем альтернативы с целью нахождения наилучшей.

При условии действия аксиом 1-4, 5еструктурная мера близости на взвешенных ( ) ранжированиях определяется как

,

где k³1 – число альтернатив, которые одновременно в Р хуже (менее весомы), чем x_i, а в Q лучше, чем x_j. Это соотношение определяет в соответствующем графе G длину кратчайшего пути между вершинами, которые отвечают ранжированиям Р и Q.

Структурные меры близости на эквивалентностях могут определятся разнообразными способами. Рассмотрим меру, которая имеет следующие свойства: расстояние между произвольными отношениями эквивалентности определяется кратчайшим путем между вершинами графа G, что соответствует эквивалентностям Р и R, который обязательно проходит через вершину, которая соответствует эквивалентности .

Если Р и R – эквивалентности, то будет эквивалентно такому разбитию на классы, когда к одному классу будут принадлежать элементы, которые одновременно входят и в Р и в R. Таким образом состоит из не пустых пересечений классов эквивалентности Р и R.

Измельчением разбития Р будет такое разбитие R (обозначается Р®R), если для любого класса эквивалентности найдется класс , такой чтобы .Очевидно, что . Пусть . - тот из классов эквивалентности , мощность которого наибольшая (то есть в состав которого входит максимальное количество элементов).

Понятие «между» определяется следующим образом – отношение эквивалентности Q находится между отношениями Р и R - [P, Q, R], если Q=P R, или Р®R(R®P), и каждый класс эквивалентности из Q или имеет в себе один из классов , или входит в один из классов .

Отношения эквивалентности Р и R будут называться соседними, если Р®R и Р отличаются от R лишь тем, что один из его классов эквивалентности заменен двумя, то есть , при этом . Таким образом конкретизируем аксиому 5ф.

Аксиома 5ф. Если Р и R –соседние отношения эквивалентности, то d(P,R)=1.

Используя аксиомы 1,2 ,4, 5ф получаем, что значение структурной меры близости между эквивалентностями Р и R определяется по формуле:

где S₁,S₂ – число классов в Р и R соответственно, и - число подклассов соответственно в Р_i и R_i.

Меры близости Эвклида. При введении аналога прямой в множествах отношений разных типов расстояния между отношениями одного типа P₁,P₂,…,P_m, которые расположены на прямой, удовлетворяют условию:

.

Если вместо аналога прямой использовать аналог ортогональных линейных сегментов, получается важный класс мер близости - эвклидовы меры.

Линейным сегментом L называется такая последовательность отношений P₁,P₂,…,P_m, которые располагаются на одной прямой, для которой выполняется следующее условие: если R расположено между Р_i и P_i+1 – [Р_i,R, P_i+1], то R= Р_i или R= P_i+1.

Каждое из отношений линейного сегмента L получается добавлением или отбрасыванием одной пары альтернатив (x_i,x_j). Линейные сегменты L₁ и L₂ ортогональны, если при добавлении или отбрасывании пары альтернатив (x_i,x_j) в одном из них в другом она не может быть добавлена или отброшена соответственно. - изометрическая перестановка отношение, то есть:

L – линейный сегмент .

Аксиома 5г. (симметричность расстояния относительно пустого отношения). , где - пустое отношение, Р – отношение частичного порядка, в состав которого входят (x_i,x_j) лишь в том случае когда (x_i,x_j)ÎР.

Аксиома 6г. (независимость расстояния от изометрической перестановки). Если - изометрическая перестановка линейного сегмента P₁,P₂,…,P_m, то .

Аксиома 7г. Если линейные сегменты P₁,P₂,…,P_m и P_m,…,P_m+s ортогональны, то

.

В случае действия этих аксиом расстояние между частичными порядками Р и R однозначно рассчитываются по формуле:

Аналогично определяется мера близости на метризованных ранжированиях.

Аксиома 8г. Если метризованные ранжирования P,Q,R такие, что сегменты [P,R] и [R,Q] ортогональные, то .

Аксиома 9г. Если матрицы метризованных ранжирований Р и Q различаются только одной парой элементов , то

На метризованных ранжированниях понятия ортогональности сегментов определяется следующим образом. Сегменты [P,R] и [R,Q] будут ортогональными, если для каждой пары i,j или или .

При условии действия аксиом 1-3, 8г,9г меры близости между метризованными ранжированиями однозначно рассчитываются по формуле:

.

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