Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 492, № 1, стр. 101-103

Значительная часть методов интеллектуального анализа данных основана на применении эвристических (не обосновываемых теоретически) метрик, вводимых на множествах анализируемых объектов или ситуаций [1, 2]. Эвристичность метрик как инструментов анализа позволяет ставить и решать вопросы оптимизации их “потребительских качеств”, для чего можно применять соответствующие функционалы качества, в том числе и предлагаемые в данном сообщении. Существенно, что обычно числовые величины расстояний оказываются малоинтересными: реально используются только некоторые соотношения расстояний между различными парами объектов. Введенные на пространстве объектов различные метрики, порождающие совпадающие соотношения расстояний, оказываются эквивалентными с точки зрения их использования при решении модельных и прикладных задач. Метрики на конечных множествах считаются точками соответствующего полуметрического конуса, и рассматриваются классы ядерных эквивалентностей для отображений полуметрического конуса в множества некоторых вводимых ниже отношений порядка [3–5]. Отметим, что эти классы оказываются подконусами, определяемыми соответствующими системами равенств и однородных линейных неравенств.

Пусть S = {${{S}_{1}}$, …, ${{S}_{q}}$} и задана полуметрика d: S² → R₊ (допускается, что d(${{S}_{i}}$, ${{S}_{j}}$) = 0 при различных ${{S}_{i}}$ и ${{S}_{j}})$. Будем также считать, что d – точка полуметрического конуса Con^q в R^p при p = $C_{q}^{2}$. Множество упорядоченных пар индексов {(i, j)| 1 ≤ i < j ≤ q)} будем обозначать символом Q и называть пары (i, j) ребрами. Метрика d естественным образом индуцирует линейный порядок ≤₂ на Q: ((i, j) ≤₂ (k, l)) ≡ (d(${{S}_{i}}$, ${{S}_{j}}$) ≤ d(${{S}_{k}}$,${\text{\;}}{{S}_{l}}$)). Отметим, что, скажем, в алгоритмах вычисления оценок и методах типа “ближайших соседей” фактически используется только порядок ≤₂. Очевидно, что этот порядок инвариантен по отношению к любым монотонно возрастающим преобразованиям значений расстояний, так что его использование “автоматически” снимает проблемы “единиц измерения” величин расстояния.

Пусть, наоборот, на Q задан некоторый произвольный линейный порядок ≤₀. Ему легко сопоставить метрику d₀ на S такую, что соответствующий порядок ≤₂ будет совпадать с порядком ≤₀. Действительно, для построения такой метрики d₀ достаточно положить d₀ (${{S}_{i}}$, ${{S}_{j}}$) = 1 + ${{\varepsilon }_{{ij}}}$, где 0 < ε_ij < 1 и ε_ij расположены на интервале (0, 1) в нужном порядке. Указанная метрика, содержательно близкая к “абсолютно неинформативной” метрике пространства изолированных точек, может рассматриваться как в некотором смысле контрпример.

Итак, во многих случаях используется только факт принадлежности метрики к классу эквивалентности по отношению “∼”, где ${{d}_{1}}$ ∼ ${{d}_{2}}$ означает, что для всех i, j, k и l из {1, …, q} выполнено (${{d}_{1}}$(${{S}_{i}}$, ${{S}_{j}}$) ≤ ${{d}_{1}}$(${{S}_{k}}$, ${{S}_{l}}$)) ≡ (${{d}_{2}}$(${{S}_{i}}$, ${{S}_{j}}$) ≤ ${{d}_{2}}$(${{S}_{k}}$, ${{S}_{l}}$)), или, что то же, используется только факт принадлежности метрики к классу ядерной эквивалентности для отображения π₂ полуметрического конуса Con^q в подмножество булеана Q² – множество линейных порядков на Q: ${{\pi }_{2}}$(d) = {((i, j), (k, l))| d(${{S}_{i}}$, ${{S}_{j}}$) ≤ d(${{S}_{k}}$, ${{S}_{l}}$)}. Отметим, что при этом в каждом классе эквивалентности указанного вида имеются сколь угодно близкие к центральной оси Con^q метрики.

Отметим, что в метриках типа “d(${{S}_{i}}$, ${{S}_{j}}$) = 1 + ${{\varepsilon }_{{ij}}}$” выполнены не только все необходимые по определению метрики неравенства треугольника, но и вообще все неравенства вида

и даже вида при произвольных различных i, j, k, l, m и n из {1, …, q}. Такие метрики можно назвать метриками пространств квазиизолированных точек. Как точки полуметрического конуса, они расположены “около его центральной оси”. Если принять тезис о том, что близость к метрике пространства изолированных точек свидетельствует о “малой информативности” метрики, то в качестве оценки “качества” метрики можно использовать, например, мощности множеств наборов индексов i, j, k, l, m и n, для которых не выполнены неравенства (1) или (2). Очевидно, что для метрик пространств квазиизолированных точек указанные множества пусты.

Пусть T₃ = {(k, l, m)| 1 ≤ k < m ≤ q, 1 ≤ l ≤ q, l ≠ k, l ≠ m} и U₃ = ${{T}_{3}}$ ∪ Q, а T₄ = {(k, l, m, n)| 1 ≤ k < l ≤ q, 1 ≤ m < n ≤ q} и U₄ = ${{T}_{4}}$ ∪ Q . Тройки (k, l, m) из T₃ будем называть углами. Для всех элементов α и β из U₃ или из U₄ естественным образом определяется вес W(α) = d(${{S}_{i}}$, ${{S}_{j}}$) при α = (i, j) $ \in $ Q, W(α) = = d(${{S}_{k}}$, ${{S}_{l}}$) + d(${{S}_{l}}$, ${{S}_{m}}$) при α = (k, l, m) ∈ T₃ и W(α) = = d(${{S}_{k}}$, ${{S}_{l}}$) + d(${{S}_{m}}$, ${{S}_{n}}$) при α = (k, l, m, n) $ \in $ T₄. Рассмотрим отображения ${{\pi }_{3}}$ и ${{\pi }_{4}}$ полуметрического конуса Con^q в множества линейных порядков на U₃ и U₄ соответственно:

Порядки π₃ и π₄ , вообще говоря, более точно описывают метрику d в том смысле, что по ним, естественно, однозначно восстанавливается порядок π₂, но не наоборот. Иначе говоря, содержащие метрику d классы ядерных эквивалентностей для отображений π₃ и π₄ оказываются подклассами ядерных эквивалентностей для π₂.

Кроме того, в отличие от случая π₂, теперь уже неверно, что в каждом классе эквивалентности имеются сколь угодно близкие к оси Con^q метрики.

Ясно, что классы эквивалентных метрик определяются соответствующими системами линейных неравенств и образуют подконусы конуса Con^q. Для нормированных метрик d в качестве представителей классов эквивалентности можно использовать “ближайшие” к оси Con^q или, наоборот, “наиболее отдаленные” от оси метрики, которые будут определяться обращением некоторых неравенств треугольника в равенства. Если для оценки удаленности от оси использовать метрику l₁, то такие метрики можно находить как решения задач типа

где

${{w}_{{ij}}}$ = |{(k, l)|$d\left( {{{S}_{k}},{{S}_{l}}} \right) < d\left( {{{S}_{i}},{{S}_{j}}} \right)$}| – – |{(k, l)| d(Sk, ${{S}_{l}}) > d({{S}_{i}},{{S}_{j}})$}|,

при нормировке $\Sigma d({{S}_{i}},{{S}_{j}})~$= const, ограничениях 0 < $d\left( {{{S}_{i}},{{S}_{j}}} \right)$ и ограничениях (линейных неравенствах), задаваемых порядком π₃(d) или π₄(d).

Описываемый подход позволяет ввести новые теоретико-множественные оценки “качества” конечных метрических конфигураций (в такой роли в задачах кластеризации или классификации обычно используются характеристики типа “отношение средних внутриклассовых расстояний к межклассовым”). Отметим, что указанные оценки можно использовать при решении задач коррекции и комплексирования метрик.