Метризация информационных пространств при четкой постановке задачи. Локальные метрики
Многие фундаментальные закономерности и свойства множеств и других математических объектов обусловливаются взаимным расположением составляющих их элементов. Такие свойства отражают «геометрические» особенности связей между элементами или пространственную структуру множеств. Одной из важнейших функциональных характеристик структурных отношений между элементами множества является понятие близости элементов, тесно связанное с понятиями расстояния между элементами, сходимости последовательности и непрерывности функции. Любое множество, в котором тем или иным образом введено понятие близости элементов, принято называть пространством, а его элементы – точками пространства.
Неотрицательная действительная функция dX, определенная на прямом произведении X×X множества X, называется метрикой на множестве Х, если для любых элементов множества Х она удовлетворяет следующим условиям (аксиомам):
- симметрии: dX(x, y) = dX(y, x);
- тождества: dX(x, y) = 0 ⇔ x = y;
- треугольника: dX(x, y) ≤ dX(x, z) + dX(z, y).
Числовое значение функции dX(x, y) называется расстоянием между элементами x и y множества X. Множество Х метризуемо, если на нем может быть введена некоторая метрика. Метризуемое множество Х с заданной на нем метрикой dX называется метрическим пространством и обозначается (X, dX). Требования, налагаемые на метрику, называются аксиоматикой метрического пространства. Задавая различные метрики на одном и том же множестве элементов X, получаем разные метрические пространства. Разные метрические пространства также получаются, если ввести одну и ту же метрику на различных множествах элементов. Свойства метрических пространств: открытость и замкнутость, замыкание, связность, плотность, сепарабельность, полнота и пополнение, компактность. Метрические пространства являются частным случаем топологических пространств.
Понятие топологического пространства можно рассматривать как аксиоматизацию понятия близости точки к множеству: точка близка к множеству, если она принадлежит его замыканию. Топология это как бы до- или внеметрическая форма (метод) отображения реальности, в которой остается только некоторая упорядоченность и смежность (в т.ч., связность). Кроме того, от понятия пространства сохраняется в большинстве случаев понятие размерности, но эти различия становятся трансформируемыми, могут определенным образом преобразовываться одно в другое, что в метрике принципиально невозможно, там размерность аксиоматизирована. Теория метрических пространств является аксиоматизацией понятия близости точек: в метрическом пространстве каждой паре точек соответствует вещественное число – расстояние между ними, основные свойства которого описываются системой аксиом. Необходимое и достаточное условие для метризуемости топологического пространства: топологическое пространство должно быть регулярным и иметь базу, распадающуюся на счётное множество локально конечных систем множеств.
Метризация (от греч. metrike – мера, размер) – процедура выделения расстояния между точками рассматриваемой шкалы; с помощью метризации осуществляется переход от нечисловой информации, полученной по номинальным ранговым шкалам, к числовой, т.е. построенной на отношениях меры, порядка и смежности. Мера – аналог бытового понятия длины, длительности, весовых отношений и т.д. Порядок – аналог некоторого относительного расположения (положительное-отрицательное, больше-меньше, слева-справа и т.д.). Смежность – это наличие «зон слияния», общих границ чего-либо. Именно через меру, порядок и смежность достаточно целостно отображается мир. Изначально любой тип таких отображений, в т.ч. и явно не метрических, осуществляется через интеллектуальные процедуры метризации – присвоения неупорядоченным множествам явлений этих самых значений меры, порядка, смежности.
Метризация осуществляется посредством процессов, соответствующих понятиям функций, функционалов и операторов. Эти процессы в самом мышлении являются операционными, т.е. обеспечивают мышление как его операционная система, среда. Именно после такой обработки из множественных (сенсорных, интуитивных, чувственных и пр.) неметрических и даже несвязных потоков сообщений «реальность и место объекта в ней» становится обобщенной структурированной моделью
Конструирование собственного пространства признаков и нахождение индивидуальной меры называется локальным преобразованием пространства признаков.
Задача определения контекстно-зависимой локальной метрики заключается в нахождении линейного преобразования новой векторной переменной. Для ее решения пригоден хорошо разработанный аппарат методов многомерного линейного анализа данных. Ограничение на применение этих методов накладывается требованием неотрицательности компонент весового вектора, так как различие объектов и по какому либо признаку должно обязательно приводить к увеличению расстояния либо в случае вообще не сказываться на изменении расстояния.
Критерий качества локальной метрики определяется контекстом, а его конкретная форма задается исследователем. Например, с учетом информации о принадлежности объектов к тем или иным классам эквивалентности это может быть стандартный для линейного дискриминантного анализа критерий, построенный на отношении разброса между классами к внутриклассовому разбросу. Или, имея в виду сложную неоднородную структуру классов, целесообразнее строить критерий качества на оценке первых k-ближайших объектов, то есть фактически на локальной оценке отношения правдоподобия в точке. Также не лишен смысла критерий, основанный на сравнении расстояний от объекта до его q-ближайших соседей из собственного класса с расстояниями до его r-ближайших соседей из других классов и т.п.
При построении локальной метрики могут использоваться самые различные методы, ориентированные на максимизацию заданного критерия. Нередко достаточно ограничиться только отбором центрированных признаков. Это бывает целесообразно, главным образом, при работе с бинарными признаками. Для решения данной задачи особенно эффективны алгоритмы отбора переменных типа «плюс l минус r» и эволюционные методы (например, метод случайного поиска с адаптацией).
Индивидуально сконструированные локальные метрики обеспечивают каждому объекту, как представителю своего класса, максимально возможную «сферу действия», которой нельзя достигнуть при построении общего пространства признаков и использовании одинаковой метрики для всех объектов.
Описание каждого эмпирического факта оказывается полностью избавленным от неинформативных элементов, что позволяет в дальнейшем иметь дело с чистыми «незашумленными» структурами данных. В этом описании остается только то, что действительно важно для отражения сходства и различия эмпирического факта с другими фактами в контексте решаемой задачи.
В свете представлений о контекстно-зависимых локальных метриках, очевидно, что один и тот же объект может поворачиваться разными гранями своего многомерного описания сообразно заданному контексту. К любому объекту, запечатленному в памяти как целостная многомерная структура, «привязан» набор различных локальных метрик, каждая из которых оптимизирует иерархию его сходства (различия) с другими объектами соответственно целям определенной задачи отражения отношений между объектами реального или идеального мира.
В результате построения локальных метрик отношения между объектами выражаются матрицей удаленностей. Так как локальные метрики у разных объектов могут не совпадать, то для элементов матрицы могут не выполняться требования симметричности и неравенства треугольника. Поэтому данная матрица, хотя и отражает отношения различия между объектами, не может истолковываться как матрица расстояний. Для устранения нарушений метрических отношений между элементами матрицы вводится специальный класс метрик.
Образно говоря, если окинуть взором множество объектов с точки, занимаемой объектом, в пространстве, специально сконструированном для этого объекта, то для такого взора объекты выстроятся в специфический ряд по степени удаленности от данной точки. С другой точки и в другом пространстве ряд удаленностей тех же самых объектов будет иметь свой специфический вид.
Выбор конкретного преобразования зависит от того, на каком аспекте структуры данных исследователь решает сделать акцент. Например, может использоваться преобразование в ранговую величину. Другой вариант – преобразование в классификационный показатель. В этом случае все объекты, проранжированные по удаленности, заменяются идентификатором своего класса, образно говоря, «окрашиваются» в цвета своего класса. Выбор меры зависит, с одной стороны, от вида преобразования и, с другой стороны, от того, какие особенности рядов и объектов имеется намерение оттенить при определении их сходства (различия).
Прямой способ основан на вычислении расстояния (например, евклидова). В данном случае не требуется дальнейшего подбора констант и для соблюдения метрических требований, так как они выполняются автоматически. Однако бывает более целесообразно использовать в качестве меры тот или иной коэффициент связи, например, коэффициент корреляции Пирсона, Кендалла и др. Если преобразование дает классификационную переменную, то мерой подобия может служить какой-либо коэффициент сопряженности для номинальных переменных.
После перехода от матрицы к матрице расстояний исследование совокупности объектов с привязанными к ним собственными локальными метриками может производиться всеми доступными методами и алгоритмами, использующими геометрическую метафору данных.
Сюда относятся алгоритмы автоматического группирования (кластерный анализ, иерархическое группирование, определение «точек сгущения») и методы визуализации данных, для которых исходной информацией служит матрица расстояний (многомерное шкалирование, адаптивная развертка).