Аксиоматическое введение расстояний

В прикладной статистике используют большое количество метрик и показателей различия (см. примеры в предыдущем пункте). Как обоснованно выбрать то или иное расстояние для использования в конкретной задаче? В 1959 г. американский статистик Джон Кемени предложил использовать аксиоматический подход, согласно которому следует сформулировать естественные для конкретной задачи аксиомы и вывести из них вид метрики. Этот подход получил большую популярность в нашей стране после выхода в 1972 г. перевода на русский язык книги Дж. Кемени и Дж. Снелла [19], в которой дана система аксиом для расстояния Кемени между упорядочениями. (Упорядочения, как и иные бинарные отношения, естественно представить в виде квадратных матриц из 0 и 1; тогда расстояние Кемени – это расстояние из примера 7 предыдущего пункта.) Последовала большая серия работ, в которых из тех или иных систем аксиом выводился вил метрики или показателя различия для различных видов данных, прежде всего для объектов нечисловой природы. Многие полученные результаты описаны в обзоре [20], содержащем 161 ссылку, в том числе 69 на русском языке. Рассмотрим некоторые из них.

Аксиоматическое введение расстояния между толерантностями. Толерантность - это бинарное отношение, являющееся рефлексивным и симметричным. Его обычно используют для описания отношения сходства между реальными объектами, отношений знакомства или дружбы между людьми. От отношения эквивалентности отличается тем, что свойство транзитивности не предполагается обязательно выполненным. Действительно, Иванов может быть знаком с Петровым, Петров – с Сидоровым, но при этом ничего необычного нет в том, что Иванов и Сидоров не знакомы между собой.

Пусть множество Х, на котором определено отношение толерантности, состоит из конечного числа элементов: X = { x ₁, x ₂,…, x_k }. Тогда толерантность описывается квадратной матрицей A = || a (i,j)||, i,j = 1, 2,…, k, такой, что a (i,j) = 1, если x_i и x_j связаны отношением толерантности, и a (i,j) = 0 в противном случае. Матрица A симметрична: a (i,j) = a (j,i), на главной диагонали стоят единицы: a (i,i) = 1. Любая матрица, удовлетворяющая приведенным в предыдущей фразе условиям, является матрицей, соответствующей некоторому отношению толерантности. Матрице А можно сопоставить неориентированный граф с вершинами в точках Х: вершины x_i и x_j соединены ребром тогда и только тогда, когда a (i,j) = 1. Толерантности используются, в частности, при проведении экспертных исследований (см. пункт 3.4.7 ниже).

Будем говорить, что толерантность А ₃ лежит между толерантностями А ₁ и А ₂, если при всех i, j число a ₃(i, j) лежит между числами a ₁(i, j) и a ₂(i, j), т.е. выполнены либо неравенства a ₁(i, j) < a ₃(i, j) < a ₂(i, j), либо неравенства a ₁(i, j) > a ₃(i, j) > a ₂(i, j).

Теорема 1 [2]. Пусть

(I) d (A ₁, A ₂) – метрика в пространстве толерантностей, определенных на конечном множестве X = { x ₁, x ₂,…, x_k };

(II) d (A ₁, A ₃) + d (A ₃, A ₂) = d (A ₁, A ₂) тогда и только тогда, когда A ₃ лежит между A ₁ и A ₂;

(III) если отношения толерантности A ₁ и A ₂ отличаются только на одной паре элементов, т.е. a ₁(i,j) = a ₂(i,j) при (i,j) ≠ (i ₀, j ₀), i<j, i ₀ < j₀, и a ₁(i ₀, j ₀) ≠ a ₂(i ₀, j ₀), то d (A ₁, A ₂) = 1.

Тогда

Таким образом, расстояние d (A ₁, A ₂) только постоянным множителем ½ отличается от расстояния Кемени, введенного в пространстве всех бинарных отношений как расстояние Хемминга между описывающими отношения матрицами из 0 и 1 (см. пример 7 предыдущего пункта). Теорема 1 дает аксиоматическое введение расстояния в пространстве толерантностей. Оказалось, что оно является сужением расстояния Кемени на это пространство. Сам Дж. Кемени дал аналогичную систему аксиом для сужения на пространство упорядочений. Доказательство теоремы 1 вытекает из рассмотрений, связанных с аксиоматическим введением расстояний между множествами, и приводится ниже.

Мера симметрической разности как расстояние между множествами. Как известно, бинарное отношение можно рассматривать как подмножество декартова квадрата Х ² того множества Х, на котором оно определено. Поэтому теорему 1 можно рассматривать как аксиоматическое введение расстояния между множествами специального вида. Укажем систему аксиом для расстояния между множествами общего вида, описанного в примере 9 предыдущего пункта.

Определение 1. Множество В находится между множествами А и С, если

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

Расстояние между двумя точками в евклидовом пространстве не изменится, если обе точки сдвинуть на один и тот же вектор. Аналогичное свойство расстояния между множествами сформулируем в виде аксиомы 1. Оно соответствует аксиоме 3 Кемени и Снелла [19, с.22] для расстояний между упорядочениями.

Аксиома 1. Если то

Определение 2. Непустая система множеств называется кольцом, если для любых двух входящих в нее множеств в эту систему входят их объединение, пересечение и разность. Множество Х называется единицей системы множеств, если оно входит в эту систему, а все остальные множества системы являются подмножествами Х. Кольцо множеств, содержащее единицу, называется алгеброй множеств [21, с.38].

Теорема 2. Пусть W - алгебра множеств, d: W ² → R ¹. Тогда аксиома 1 эквивалентна следующему условию: d (A,B) = d (A\B, B\A) для любых A, B є W.

Доказательство. Поскольку

то равенство d (A,B) = d (A\B, B\A) следует из аксиомы 1. Обратное утверждение вытекает из того, что в условиях аксиомы 1

Теорема 2 доказана.

С целью внести в алгебру множеств W отношение «находиться между», аналогичное используемому при аксиоматическом введении расстояний в пространствах бинарных отношений (см. условие (II) в теореме 1), примем следующую аксиому.

Аксиома 2. Если В лежит между А и С, то d (A, B)+ d (B, C)= d (A, C).

Определение 3. Неотрицательная функция μ, определенная на алгебре множеств W, называется мерой, если для любых двух непересекающихся множеств А и В из W справедливо соотношение

Понятие меры – это обобщение понятий длины линии, площади фигуры, объема тела.

Теорема 3. Пусть W – алгебра множеств, аксиомы 1 и 2 выполнены для функции d: W ² → [0;+∞]. Функция d симметрична: d (A, B) = d (B, A) для любых А и В из W. Тогда существует, и притом единственная, мера μ на W такая, что

(1)

при всех А и В из W, где А Δ В – симметрическая разность множеств А и В, т.е.

Доказательство. Положим

(2)

Покажем, что определенная формулой (2) функция множества μ является мерой. Неотрицательность μ следует из неотрицательности d. Остается доказать аддитивность, т.е. что из следует, что

(3)

Поскольку А всегда лежит между и , то по аксиоме 2

(4)

Если А ∩ В = , то по аксиоме 1 , откуда с учетом (4) и следует (3).

Докажем соотношение (1). Поскольку А \ B и B \ A имеют пустое пересечение, то согласно определению 1 пустое множество лежит между А \ B и B \ A. Поэтому по аксиоме 2

Из симметричности и соотношения (2) следует, что

откуда d (A \ B, B \ A)= μ(A \ B) + μ(B \ A). Из соотношения (3) следует, что μ(A \ B) + μ(B \ A) = μ(A Δ B). С другой стороны, по аксиоме 1

Из трех последних равенств вытекает справедливость равенства (1).

Остается доказать единственность меры μ в соотношении (1). Поскольку А Δ В = В при А = , то из (1) следует (2), т.е. однозначность определения меры μ = μ(d) по расстоянию d. Теорема 3 доказана.

Теорема 4 (обратная). Пусть μ – мера определенная на алгебре множеств W. Тогда функция d (A, B) = μ(A Δ B) является псевдометрикой, для нее выполнены аксиомы 1 и 2.

Доказательство. То, что функция d (A, B) из (1) задает псевдометрику, хорошо известно (см., например, [22, с.79]). Доказательство аксиомы 2 содержится в [23, c.181-183]. Аксиома 1 следует из того, что условия обеспечивают справедливость соотношений

Замечание. Полагая в аксиоме 2 А = В = С, получаем, что d (A, А) + d (A, А) = d (A, А), т.е. d (A, А) = 0. Согласно теоремам 3 и 4, из условий теоремы 3 следует неравенство треугольника. Таким образом, в теореме 3 действительно приведена система аксиом, определяющая семейство псевдометрик в пространстве множеств.

Обсудим независимость (друг от друга) условий теоремы 3. Отбрасывание неотрицательности функции d приводит к тому, что слово «мера» в теоремах 3 и 4 необходимо заменить на «заряд» [21, с.328]. Этот термин обозначает аддитивную функцию множеств, не обладающую свойством неотрицательности. Заряд можно представить как разность двух мер.

Функция является псевдометрикой, для нее выполнена аксиома 1, но не выполнена аксиома 2, следовательно, ее нельзя представить в виде (1).

Приведем пример системы множеств W и метрики в ней, для которых верна аксиома 2, но не верна аксиома 1, а потому эту метрику нельзя представить в виде (1). Пусть W состоит из множеств причем А ∩ В = , а расстояния таковы:

Если единица Х алгебры множеств W конечна, т.е. X = { x ₁, x ₂,…, x_k }, то расстояние (1) принимает вид

(5)

где χ _С – индикатор (индикаторная функция) множества С, т.е. χ _С (х) = 1, если х є С, и χ _С (х) = 0 в противном случае. Как следует из теоремы 3, неотрицательный коэффициент μ _i – это мера одноэлементного множества { x_i }, а также расстояние этого множества от пустого множества, т.е.

Если все коэффициенты μ _i положительны, то формула (5) определяет метрику, если хотя бы один равен 0, то – псевдометрику, поскольку в таком случае найдутся два различающиеся между собой множества А и В такие, что d (A,B) = 0.

Расстояние определяется однозначно, если априори известны коэффициенты μ _i. В частности, равноправность объектов (элементов единицы алгебры множеств Х) приводит к μ _i ≡ 1. Требование равноправности содержится в аксиомах 2 и 4 Кемени [19, с.21-22].

Применим полученные результаты к толерантностям и докажем теорему 1. Совокупность всех толерантностей, определенных на конечном множестве У, естественным образом ассоциируется с совокупностью всех подмножеств множества Х = {(y_i, y_j), 1 < i < j < k }. Именно, пара (y_i, y_j) входит в подмножество тогда и только тогда, когда y_i и y_j связаны отношением толерантности. Указанная совокупность подмножеств является алгеброй множеств с единицей Х. Определение 1 понятия «находиться между» для множеств полностью соответствует ранее данному определению понятия «находиться между» для толерантностей.

Теорема 5. Пусть выполнены условия (I) и (II) теоремы 1 и аксиома 1. Тогда существуют числа μ _ij > 0 такие, что

(6)

Для доказательства достаточно сослаться на теорему 3. Поскольку в условии (I) требуется, чтобы функция d (A, B) являлась метрикой, то необходимо μ _ij > 0.

Теорема 6. Пусть выполнены условия теоремы 1 и, кроме того, аксиома 1. Тогда верно заключение теоремы 1.

Доказательство. Рассмотрим толерантность А, для которой a (i, j) = 1 при (i, j) = (i ₀, j ₀) и a (i, j) = 0 в противном случае. Согласно условию (III) теоремы 1 , а согласно (6) имеем . Следовательно, коэффициент = 1, что и требовалось доказать.

Для окончательного доказательства теоремы 1 осталось избавиться от требования справедливости аксиомы 1.

Доказательство теоремы 1. Рассмотрим две толерантности А и В такие, что при представлении их в виде множеств . Это означает, что a (i, j) < b (i, j) при всех i, j. Поскольку Х – конечное множество, то существует конечная последовательность толерантностей A ₁, A ₂, …, A_m, …, A_t такая, что А ₁ = А, A_t = B, A₁ A ₂ … A_m … A_t, причем A_{m +1} получается из A_m заменой ровно одного значения a_m (i_m, j_m) = 0 на a_{m +1}(i_m, j_m) = 1, для (i, j) ≠ (i_m, j_m) при этом a_m (i, j) = a_{m +1}(i, j). Тогда A_m находится между A_{m -1} и A_{m +1}, следовательно, по условию (II)

По условию (III) = 1 при всех m, а потому заключение теоремы 1 верно для любых А и В таких, что .

Поскольку А ∩ В лежит между А и В, то по условию (II)

d (A, B) = d (А ∩ В, A) + d (А ∩ В, B).

При этом А ∩ В А и А ∩ В В. Применяя результат предыдущего абзаца, получаем, заключение теоремы 1 верно всегда.

Замечание 1. Таким образом, условие (III) не только дает нормировку, но и заменяет аксиому 1.

Замечание 2. Условие (I) теоремы 1 не использовалось в доказательстве, но было приведено в первоначальной публикации [24], чтобы подчеркнуть цель рассуждения. По той же причине оно сохранено в формулировке теоремы 1, хотя в доказательстве удалось без него обойтись. Понадобилась только симметричность функции d.

Аксиоматическое введение метрики в пространстве неотрицательных суммируемых функций. Рассмотрим пространство L (E, μ) неотрицательных суммируемых функций на множестве E с мерой μ. Далее в настоящем пункте будем рассматривать только функции из L (E, μ). Интегрирование всюду проводится по пространству Е и по мере μ. Будем писать g = h или g < h, если указанные соотношения справедливы почти всюду по μ на Е (т.е. могут нарушаться лишь на множестве нулевой меры).

Аксиоматически введем расстояние в пространстве L (E, μ) (изложение следует работе [25]). Обозначим M (g, h) = max (g, h) и m (g, h) = min (g, h). Пусть D: L (E, μ) × L (E, μ) → R ¹ – тот основной объект изучения, аксиомы для которого будут сейчас сформулированы.

Аксиома 1. Если gh = 0, g + h ≠ 0, то D (g, h) = 1.

Аксиома 2. Если h < g, то D (g, h) = C ∫ (g – h) d μ, где множитель С не зависит от h, т.е. C = C (g).

Лемма. Из аксиом 1,2 следует, что для h < g ≠ 0

Для доказательства заметим, что по аксиоме 1 D (g, 0) =1, а по аксиоме 2 D (g, 0) = С ∫ g d μ, откуда С = (∫ g d μ)^-1. Подставляя это соотношение в аксиому 2, получаем заключение леммы.

Требование согласованности расстояния в пространстве L (E, μ) с отношением «находиться между» приводит, как и ранее для расстояния d (A, B), к следующей аксиоме.

Аксиома 3. Для любых g и h справедливо равенство D (g, h) = D (M (g, h), g) + D (M (g, h), h).

Замечание. В ряде реальных ситуаций естественно считать, что наибольшее расстояние между элементами пространства множеств (которое без ограничения общности можно положить равным 1), т.е. наибольшее несходство, соответствует множествам, не имеющим общих элементов. Расстояние, введенное в теореме 3 (формула (1)), этому условию не удовлетворяет. Поэтому в пространстве множеств была аксиоматически введена [20] так называемая D -метрика (от dissimilarity (англ.) – несходство), для которого это условие выполнено. Она имеет вид:

(7)

Приведенные выше аксиомы являются обобщениями соответствующих аксиом для D -метрики в пространстве множеств.

Теорема 7. Из аксиом 1-3 следует, что

(8)

Доказательство. Поскольку

(M (g, h) - g) + (M (g, h) – h) = | g – h |,

то заключение теоремы 7 при g + h ≠ 0 вытекает из леммы и аксиомы 3. Из аксиомы 2 при g = 0 следует, что D (0, 0) = 0. Легко видеть, что функция D, заданная формулой (8), удовлетворяет аксиомам 1-3 и, кроме того, D (g, h) < 1 при любых g и h.

Замечание. Если g и h – индикаторные функции множеств, то формула (8) переходит в формулу (7). Если g и h – функции принадлежности нечетких множеств, то формула (8) задает метрику в пространстве нечетких множеств, а именно, D -метрику в этом пространстве [20].

Теорема 8. Функция D (g,h), определенная формулой (8), является метрикой в L (E, μ) (при отождествлении функций, отличающихся лишь на множестве нулевой меры), причем D (g, f) + D (f, h) = D (g, h) тогда и только тогда, когда f = g, f = h или f = M(g, h).

Доказательство. Обратимся к определению метрики. Для рассматриваемой функции непосредственно очевидна справедливость условий неотрицательности и симметричности. Очевидна и эквивалентность условия D (g, h) = 0 равенству g = h. Остается доказать неравенство треугольника и установить, когда оно обращается в равенство.

Без ограничения общности можно считать, что рассматриваемые расстояния задаются верхней строкой формулы (8) и, кроме того,

R = ∫ M (g, f) d μ - ∫ M (f, h) d μ > 0

(частные случаи с использованием нижней строки формулы (8) рассматриваются элементарно, а справедливости последнего неравенства можно добиться заменой обозначений функций – элементов пространства L (E, μ)). Тогда

(9)

причем равенство имеет место тогда и только тогда, когда R = 0 или f = h. Положим

P = ∫ (| g – f | + |f – h| - | g – h |) d μ, Q = ∫ (M (g, f) – M (g, h)) d μ.

Ясно, что P > 0 и

(10)

Если Q < 0, то, очевидно, неравенство треугольника выполнено, причем неравенство является строгим. Рассмотрим случай Q > 0.

Воспользуемся следующим элементарным фактом: если y > x, y > 0, P > Q > 0, то

(11)

Из соотношений (10) и (11) вытекает, что для доказательства неравенства треугольника достаточно показать, что P – Q > 0.

Рассмотрим

k = {| g – f | + | f – h | - | g – h |} – M (g, f) + M (g, h).

Применяя равенство (M (g, h) - g) + (M (g, h) – h) = | g – h | к слагаемым, заключенным в фигурные скобки, получаем, что

k = M (f, h) + [ M (g, f) + M (f, h) – M (g, h) – 2 f ].

Применяя соотношение

M (g, h) = g + h – m (g, h) (12)

К слагаемым, заключенным в квадратные скобки, получаем, что

k = M (f, h) – m (f, h) – m (g, f) + m (g, h).

Так как M (f, h) – m (f, h) = | f – h |, то

k = | f – h | - (m (g, f) – m (g, h)) > (f – h) - (m (g, f) – m (g, h)). (13)

В соответствии с (12) правая часть (13) есть M (g, f) – M (g, h), а потому

P – Q = ∫ k d μ > Q > 0,

что завершает доказательство для случая Q > 0. При этом неравенство треугольника является строгим.

Осталось рассмотреть случай Q = 0. В силу соотношений (9) и (10) неравенство треугольника выполнено. Когда оно обращается в равенство? Тривиальные случаи: f = g или f = h. Если же f отлично от g и h, то необходимо, чтобы R = 0 и P = 0. Как легко проверить, последнее условие эквивалентно неравенствам

m (g, h) < f < M (g, h). (14)

Из правого неравенства в (14) следует, что M (g, f) < M (g, M (g, h)) = M (g, h). Так как Q = 0, то M (g, f) = M (g, h). Аналогичным образом из

соотношений

M (h, f) < M (h, M (g, h)) = M (g, h) = M (g, f)

и R = 0 следует, что M (f, h) = M (g, h).

Рассмотрим измеримое множество X = { x є E: h (x) < g (x)}. Тогда M (g, h) (x) = M (f, h) (x) = g (x) > h (x), т.е. h (x) < f (x) = M (g, h) (x) для почти всех x є X. Для почти всех y є { x є E: h (x) > g (x)} точно так же получаем f (y) = M (g, h) (y). Для почти всех z є { x є E: h (x) = g (x)} в силу (14) f (z) = M (g, h) (z), что и завершает доказательство теоремы.

Замечание. Назовем функции g и h подобными, если существует число b > 0 такое, что g = bh. Тогда при 0 < b < 1 имеем D (g, h) = 1 – b, т.е. расстояние между подобными функциями линейно зависит от коэффициента подобия. Далее, пусть a > 0, тогда D (ag, ah) = D (g, h). Таким образом, метрика (8) инвариантна по отношению к преобразованиям подобия, которые образуют группу допустимых преобразований в шкале отношений. Это дает основания именовать метрику (8) метрикой подобия [25].

Контрольные вопросы и задачи

1. Приведите примеры практического использования количественных и категоризованных данных.

2. Как соотносятся группы допустимых преобразований для различных шкал измерения?

3. Почему анализ нечисловых данных занимает одно из центральных мест в прикладной статистике?

4. В каких случаях целесообразно применение нечетких множеств?

5. Справедливо ли для нечетких множеств равенство (A+B) C = AC + BC? А равенство (AB) C = (AC)(BC)?

6. Докажите, что для блочного расстояния (пример 4 из пункта 1.1.5) справедливо неравенство треугольника.

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

8. Докажите, что если d (x, y) – расстояние в некотором пространстве, то - также расстояние в этом пространстве.