некоторого нелинейного однозначного отображения в
-мерное пространство. Как меру качества отображения рассмотрим какой-либо из функционалов, отражающих сохранение локальной геометрической структуры матрицы данных X, существующей в исходном пространстве. Различные типы таких функционалов приведены в [8, 78, ИЗ], Мы ограничимся рассмотрением функционала вида
где
— расстояние между точками в исходном пространстве;
— расстояние между точками в пространстве образов.
В качестве расстояний могут использоваться взвешенное евклидово расстояние
(обычное евклидово расстояние получается как частный случай, когда
расстояние Махаланобиса, инвариантное к линейным преобразованиям в исходном пространстве,
и расстояние Колмогорова
В
-мерном пространстве образов также возможно использование любой из перечисленных метрик.
Дальше будет рассматриваться случай евклидовой метрики в исходном пространстве и в пространстве образов. Переход от взвешенного евклидова расстояния и от расстояния Махаланобиса в исходном пространстве к евклидову может быть легко осуществлен предварительным линейным преобразованием данных.
Итак, пусть в пространстве образов расстояние между точками-образами задается формулой
Подставляя это выражение в (10.26), получаем представление функционала
как функции
координат
и задача поиска минимума функционала
сводится к минимизации функции
переменных.
Прежде чем перейти к описанию вычислительной процедуры минимизации, рассмотрим свойства критерия (10.26) в зависимости от значений параметра а. Если значение
то искажение расстояния (т. е. разность
) оказывает на величину критерия тем большее влияние, чем больше величина расстояния между точками в исходном пространстве. Поэтому при использовании критерия с параметром
следует ожидать, что чем больше расстояние между точками в исходном пространстве, тем меньше будет искажено взаимное положение этих двух точек в пространстве образов. По аналогичным соображениям, если значение параметра
в меньшей степени будут искажаться взаимные положения точек, находящихся на малом расстоянии в исходном пространстве.
Более гибким является подход, основанный на использовании параметра а, значение которого меняется в зависимости от величины разности
Именно:
(10,27)
Рассмотрим случай, когда
. Пусть
а величина
велика. Тогда вес искажения
будет мал
. С другой стороны, пусть
и величина
опять велика, тогда вес искажения
будет большим
Следовательно, при минимизации
будет наблюдаться тенденция искажения больших расстояний в сторону увеличения, а малых — в сторону уменьшения. Естественно ожидать, что при таком характере искажений отображение исходной конфигурации будет более удачным. Во всяком случае при выделении всякого рода «сгустков», «кластеров» точек этот тип искажений может быть даже полезен, поскольку расстояние между точками, относящимися к одному кластеру, имеют тенденцию быть малыми, а между точками из разных кластеров — большими, и, следовательно, искажения рассмотренного типа увеличивают «контрастность» картины при визуализации.
Как уже указывалось, определение конфигурации, для которой достигается минимальное значение функционала качества
, сводится к задаче поиска минимума функции
переменных. Ввиду большого числа переменных наиболее применимы для решения этой задачи итерационные схемы, являющиеся разновидностями градиентного метода,
Рассмотрим схему, реализованную в программе сокращения размерности в пакете ППСА [67]. Именно поиск точки минимума функции
в
-мерном пространстве проводится с помощью итерационной процедуры:
где t — номер шага итерации,
координата образа i-го объекта в
-мерном пространстве:
Таким образом, это процедура градиентного типа. Ее особенность состоит в выборе шага, который равен
Обоснование такой величины шага аналогично обоснованию величины шага для критерия вида (10.26) при
которое приведено в работе [37] (тогда величина шага, очевидно, равна
). Можно доказать сходимость итерационного процесса (10.28) к некоторой точке локального минимума функционала
при любом задании начальных условий. Так как точек локального минимума у функционала
может быть очень много, чтобы попасть в точку глобального минимума, нужно много просчетов, требующих достаточно больших затрат машинного времени. Поэтому весьма существенным является вопрос о выборе начального приближения. В пакете ППСА [67] в качестве начального приближения используется проекция точек из X на q первых главных компонент. Если
, то главные компоненты минимизируют критерий
в классе линейных ортогональных отображений. Хотя такой выбор начальных условий и не гарантирует достижения глобального минимума, однако во многих случаях он приводит к существенному
улучшению отображения структуры по сравнению с методом главных компонент. В заключение отметим одно важное свойство нелинейного отображения — центр тяжести конфигурации, полученной в результате отображения, совпадает с центром тяжести конфигурации, взятой в качестве начального приближения.