13.6. Нелинейное отображение многомерных данных в пространство низкой размерности

В некоторых случаях более точного отображения геометрической структуры исходной матрицы данных X в пространстве малой размерности можно добиться, используя нелинейное отображение [300, 9, 152]. Для получения таких отображений задаются тем или иным критерием (мерой) искажения и решают задачу на определение минимума . Рассмотренные в данном параграфе меры искажения основаны на сравнении попарных расстояний между точками в исходном пространстве и пространстве отображения. В зависимости от выбранного критерия может получаться та или иная конфигурация точек и существенно меняется время вычисления.

13.6.1. Нелинейное отображение по критерию типа стресса.

Мера искажения, рассматриваемая ниже, была предложена Сэммоном [300] и является аналогом критерия «стресса», используемого в многомерном шкалировании (см. гл. 16).

(13.16)

где — расстояние, например, евклидово, между объектами, т. е. строками матрицы; — евклидово расстояние между образами соответствующих объектов в -мерном пространстве.

Пусть — -мерные векторы координат образов объектов при нелинейном отображении Расстояние будем считать евклидовым, т. е. .

Так как евклидово расстояние не меняется при повороте осей координат, то координаты образов объектов, которые будем искать с помощью минимизации, можно считать некоррелированными (ортогональными) и центрированными . Это не меняет величины критерия, а результаты работы метода становятся более наглядными.

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

Использование двухпараметрического критерия, предложенного в [152]

дает большие возможности, поскольку естественно ожидать, что можно удачно отобразить конфигурацию в пространство меньшей размерности, если искажения носят такой характер, что большие расстояния несколько увеличиваются, а малые несколько уменьшаются. Это, например, может оказаться полезным для дальнейшего использования преобразованной матрицы данных в задачах классификации, поскольку малые расстояния характерны для объектов, принадлежащих одному классу, а большие — разным. Поэтому можно ожидать, что степень разнесенности классов не слишком уменьшиться в результате такого преобразования, а, возможно, и возрастет. Для получения такого эффекта надо положить

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

Поиск образов объектов, минимизирующий значение функционала (13.16) при нелинейном отображении, осуществляется, например, с помощью итерационной градиентной процедуры:

(13.17)

где t — номер шага итерации; координата образу объекта в -мерном пространстве; — первая производная по вычисляется по формуле

Выражение для градиента приведено в [11].

Пусть — значение критерия на шаге итерационной процедуры.

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

В качестве начального приближения для итерационной процедуры могут использоваться, например, проекции объектов на главные компоненты. Размерность пространства образов q, допустимое количество итераций и точность для градиентной процедуры считаются заданными. В работе [152] предлагается применять для минимизации (13.11) метод сопряженных градиентов, который может быть эффективнее, чем градиентная процедура (13.12).

13.6.2. Быстрое нелинейное отображение с помощью опорных точек.

Рассмотренный в п. 13.5.1 алгоритм нелинейного отображения требует при реализации выполнения большого количества арифметических операций, на каждом шаге итерации количество умножений пропорционально Формирование матрицы расстояний между точками в исходном пространстве перед началом работы алгоритма также требует порядка у умножений. Число умножений на каждом шаге итерации в предлагаемом ниже алгоритме быстрого нелинейного отображения (БНО) пропорционально величине , т. е. растет лишь линейно, в зависимости от числа используемых объектов. Результирующая матрица точек образов на выходе этого алгоритма может быть использована либо непосредственно для дальнейшего анализа, либо как начальная конфигурация для алгоритма нелинейного отображения из п. 13.5.1.

Идея алгоритма БНО. Алгоритм БНО [66] основан на том, что в -мерном пространстве координаты точки Z можно однозначно определить набором евклидовых расстояний между Z и соответствующим образом выбранными опорными точками

Действительно, разности лишь линейно зависят от координат вектора Z. Поэтому для определения Z можно использовать систему из q линейных уравнений , где строка матрицы А есть компонента вектора В равна т. е. выражается через известные величины [160].

Конечно, опорные точки должны быть выбраны так, чтобы матрица А была невырождена.

Если опорные точки зафиксированы, то в качестве функционала качества отображения может быть использована следующая величина:

(13.18)

где — расстояние между объектом и опорной точкой X, в исходном пространстве, — аналогичные расстояния, но в пространстве образов.

Итерационная процедура уточнения координат точки в пространстве образов имеет вид:

где

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

опорная точка в исходном пространстве.

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

Другой способ состоит в разбиении матрицы X на сгущений с помощью алгоритма Мак-Кина и в качестве опорных выбираются точки, ближайшие к центрам классов. При наличии априорных соображений точки могут задаваться исследователем.

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

Пусть объекты из матрицы данных, выбранные в качестве опорных. Образы опорных точек получаются с помощью следующей процедуры.

Шаг 1. Вычисляется матрица попарных скалярных произведений размера

Шаг 2. Вычисляются собственные числа и векторы матрицы V.

Рис. 13.5 Быстрое нелинейное отображение сельскохозяйственных регионов СССР в двумерное пространство

Пусть есть собственный вектор с компонентой, а , — соответствующее собственное число. Тогда координаты опорных точек будут компонентами вектора

Пример 13.3. На рис. 13.5 предоставлены отображения, полученные с помощью алгоритма БНО. В качестве матрицы данных использовалась матрица данных из [149] . См. также пример 19.2. Номера опорных точек 43, 50, 100. На рисунке они обведены кружками. Как видим, точки разделились на три хорошо выделенных кластера, объективность существования которых подтверждается их соотнесением с классификацией, предложенной в [149].

13.6.3. Быстрый алгоритм нелинейного проецирования многомерных данных.

Как меру искажения геометрической конфигурации будем рассматривать здесь

(13.19)

где

Для дальнейшего удобно будет использовать величину

(13.19)

Очевидно, что

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

Дальше, в силу того, что расстояния не меняются при преобразованиях переноса, не ограничивая общности, будем считать, что выполнены следующие условия: (исходные данные и их образы центрированы).

Из аналогичных соображений (инвариантности расстояний при ортогональных преобразованиях) можно считать, если , т. е. что переменные-образы попарно ортогональны.

Пусть дальше есть дисперсия (точнее, ее оценка) для дисперсия для . Введем еще коэффициент сопряженности между двумя -компонентными векторами у и t

Таким образом, это скалярное произведение у и t, деленное на .

Если у и t центрированы, то есть просто коэффициент ковариации между переменными у и

Найдем теперь первую производную от , где координата образа объекта Имеем

В точке глобального минимума Это приводит к следующему уравнению:

Далее имеем

Меняя порядок суммирования по Г и получим с учетом условий ортогональности и центрированности компонент

где векторы

Аналогично получаем, что

Кроме того,

Окончательно вектор производных по компонентам

— вектор размерности с единичными компонентами; — матрица коэффициентов сопряженности размера

— матрица размера с элементами — матрица размера с элементами

Поскольку и центрированы, элемент , есть не что иное, как ковариация между переменной и переменной Используем для поиска точки минимума разновидность алгоритма с переменной метрикой, для чего потребуется еще матрица вторых производных по Непосредственным дифференцированием убеждаемся, что матрица вторых производных имеет вид

Предлагаемый алгоритм основан на применении итерационного соотношения процесса Ньютона отдельно для каждого вектора

(13.20)

Вопросы вычислительной реализации и сходимости итерационной процедуры. Дальнейшие упрощения могут быть получены за счет использования формулы Бартлетта для обращения матрицы

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

(13.21)

В частности, в точках минимума функционала (13.19) условие (13.21) выполняется, поскольку матрица там неотрицательно определена и, следовательно, неотрицательно определены ее диагональные блоки (хотя допустимо, что (13.21) обращается в равенство).

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

В выражение, задающее каждый из частных градиентов входят матрицы одинаковые для всех .

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

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

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

13.6.4. Сравнение нелинейного проецирования (картирования) с линейным.

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

Пример 13.4. Предположим, что в двумерном пространстве переменных точки некоторой генеральной совокупности равномерно заполняют внутренность области, образованной двумя полуокружностями, расположенной так, чтобы Присоединим к каждой из точек этой фигуры несколько переменных равномерно распределенных на отрезке и независимых между собой и . Так что в результате получим -мерные объекты. В трехмерном пространстве область, заполняемая такими трехмерными точками, имеет вид полутороида с прямоугольным сечением (рис. 13.6).

Внешний R и внутренний радиусы тороида выберем так, что . Тогда проекция на две первые главные компоненты будет просто проекцией на плоскость (легко проверить, что матрица ковариаций будет диагональной). Эта проекция представляет собой исходную подковообразную структуру на плоскости.

Рис. 13.6. Тороидальная структура данных в -мерном пространстве

Точки лежащие симметрично плоскости соответственно на верхней и нижней плоскостях тороида для трехмерного случая, отображаются при этом в одну точку Р. Однако существенная особенность исходной конфигурации — ее подковообразность — с помощью проекции на главные компоненты передается.

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

На рис. 13.7 представлены результаты отображения моделированных данных соответственно на плоскость двух первых главных компонент и с помощью нелинейного отображения по критерию Сэммона (13.16). Использована выборка из трехмерных точек равномерно распределенных внутри тороида, представленного на рис. 13.6, с параметрами Подковообразная структура на рис. 13.7, б существенно более «размыта», чем на рис. 13.7, а.

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

Рис. 13.7. Отображение: а) на плоскость двух первых главных компонент ; б) нелинейное (по критерию Сэммона)

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

Третья и последующие координаты вносят ошибку в расстояния, и в нелинейном проецировании имеем дело не с , а с расстояниями , где . При достаточно большом уровне ошибки (шума) нелинейное отображение приводит к неверной передаче особенностей исходной информации. Главные же компоненты в данной ситуации обладают лучшими фильтрационными свойствами

В то же время, если координата будет нести информацию о некоторой структуре данных (например, точки разделяются по ) на две хорошо обособленные группы), нелинейное отображение передает эту особенность — будем иметь две параллельные «подковы» на плоскости, а картина отображения на плоскость главных компонент не изменится.

Приведенный пример подтверждает необходимость правильного выбора переменных и метрики при использовании нелинейного проецирования и метода главных компонент, а также целесообразность использования совокупности этих методов для анализа структур данных (см. также гл. 18, 19).