17.11. ОБЩЕЕ СРАВНЕНИЕ МЕТОДОВ ШКАЛИРОВАНИЯ

Эта тема была начата в разделе 17.10, мы обсудили ортогональный прокрустов анализ. Критерий записывался в виде где Н — ортогональная матрица, — обозначение для . В данном разделе обсуждаются другие критерии того же общего вида, однако Н заменена на матрицу, содержащую различного рода ограничения. Если мы откажемся от ортогональных матриц, то свойства расстояний после преобразования не сохранятся, и тогда интерес будут представлять сами координатные матрицы. Чтобы подчеркнуть это, возьмем обозначение может интерпретироваться как матрица остатков. Если допустим сдвиг конфигурации X, то X и должны быть преобразованы так, чтобы их центры тяжести совпадали. Удобнее, чтобы это было начало координат, как в ортогональном прокрустовом анализе.

Первый такой критерий был исследован Дж. Хели и Р. Кателлом [см. Hurley and Cattel (1962)]. Они требовали, чтобы С минимизировала

Именно эти авторы ввели термин прокрустов анализ. Решение отыскивается в виде результат в действительности очень близок к результату классической множественной регрессии.

Интерес к критериям такого типа возник в факторном анализе, и имеется обширная литература, освещающая возможности преобразования факторных нагрузок (которые могут быть записаны как множество координат) в более простую структуру. Р. Кателл и Кхана [см. Cattel and Khanna (1977)] недавно опубликовали обзор, а Тен Берж [см. ten Berge (1977)] представил всесторонний отчет, где произвел таксономию таких процедур, классифицируя их в 36 типов (к счастью, маловероятно, что многие из них могут иметь приложения).

Критерий не налагает ограничений на С, за исключением, конечно, того, что ее размерность должна соответствовать размерностям т. е. С должна быть размерности .

М. Браун [см. Browne (1967)] обсуждает задачу косоугольного прокрустова анализа, которая состоит в отыскании С, минимизирующей где на С наложено ограничение: она должна удовлетворять соотношению

Рис. 17.11.1. Точка Р имеет координаты по ортогональным осям и координаты по косоугольным осям с направляющими косинусами с, и (относительно ортогональных осей). Величины и, и измеряются как расстояния точки Р от косоугольных осей. Два множества координат связаны соотношением где (в данном случае) С — матрица размерности ее столбцы — направляющие косинусы с, и , следовательно,

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

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

Заметим сначала, что мы можем минимизировать относительно столбца матрицы С, независимо от других столбцов. Это означает, что мы подгоняем столбец матрицы к при условии при этом другие столбцы матрицы С могут во внимание не приниматься. Введем обозначение у для и с для Тогда мы должны минимизировать что то же самое, что максимизировать при условии Дифференцирование по с и использование множителя Лагранжа приводят к соотношению

так, что условие приводит к полиному относительно X:

Для упрощения полинома выразим через разложение по собственным векторам — ортогональная, диагональная). При подстановке в предыдущее уравнение получаем

Обозначим известный вектор через тогда полином преобразуется в

Это полином степени , а следовательно, он имеет корня. Для любого корня остаточная сумма квадратов равна

Следовательно, если — остаточные суммы квадратов, соответствующие двум корням, то

Обозначив получим а из неравенства Коши

Таким образом, из следует Это означает, что для минимума необходим наименьший корень полинома. М. Браун [см. Browne (1967)] показал, что наименьший корень удовлетворяет условию где наименьшее собственное значение матрицы и для решения полиномиального уравнения рекомендовал итеративный метод Ньютона—Рафсона. Э. Крамер [см. Cramer (1974)] предлагает альтернативный подход и обсуждает проблему неединственности минимального корня. Берж и Невелс [см. ten Berge and Nevels (1977)] разработали процедуру получения решения в такой ситуации. Если возможно оценить нижнюю границу для то можно применить метод деления пополам для его определения. Этот метод вполне удовлетворителен, если использовать следующую нижнюю границу. Пусть Тогда

Следовательно, дает необходимую нижнюю границу.

Специальный случай косоугольной прокрустовой задачи, рассмотренный Брауном, состоит в минимизации с ортонормированной матрицей С. Тогда и оси, которые ранее допускались косоугольными, теперь должны быть ортогональными. Если конфигурации и -мерны, ортогональная матрица, то мы приходим к ортогональной прокрустовой задаче, которая обсуждалась и решалась в разделе 17.10. Проблема остается нерешенной только для случая, когда матрица имеет размерность а матрица X — размерность Тогда С имеет размерность и предполагается Даже при ортонормированную оценку критерия лучше заменить поворотом в пространстве X более высокой размерности, что совсем тривиально сделать, добавив нулевых столбцов в матрицу и использовав методы из раздела 17.10. Б. Грин и Дж. Говер [см. Green and Gower (1981)] обсуждают ситуацию, когда необходим именно критерий Геометрически критерий означает, что сначала X проецируется ортогонально в пространство меньшей размерности а затем эта проекция поворачивается так, чтобы лучше соответствовать матрице Альтернативный подход — сначала повернуть матрицу в пространстве более высокой размерности, а затем осуществить проецирование в пространстве более низкой размерности. При задача идентична косоугольной прокрустовой задаче, поэтому не удивительно, что она сводится к решению похожего уравнения

где — симметричная матрица множителей Лагранжа размерности Ранее рассматривалась как скаляр, а уравнение допускало для С явное решение через X и, следовательно, определенно приводило к практическому решению. В данной ситуации это стало невозможно. Однако уравнение все же остается линейным относительно элементов матрицы принципе может иметь решение. Условие ортонормированности приводит к полиномиальным уравнениям относительно элементов матрицы .

Решение системы полиномиальных уравнений — сложная вычислительная проблема. Она осложняется еще и тем, что не известно, какое множество корней соответствует минимальной сумме квадратов критерия Так что такой подход не применим на практике. Б. Грин и Дж. Говер [см. Green and Gower (1981)] предложили итеративный алгоритм, который должен хорошо работать на практике, хотя авторам не удалось показать, что он должен сходиться к глобальному минимуму. Алгоритм состоит в следующем:

1) добавить нулевых или произвольных столбцов к матрице

2) использовать ортогональную прокрустову процедуру для построения X, соответствующей новой

3) заменить последние столбцов матрицы на соответствующие столбцы повернутой матрицы X и повторить шаг 2.

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

Интересная связь между ортогональной и косоугольной прокрустовой задачами следует из записи разложения по собственным векторам в виде Тогда основное уравнение может быть записано так:

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

На рис. 17.11.1 показано, как координаты точки относительно косоугольных осей могут быть выражены через кратчайшие расстояния этой точки до осей. Это один из способов работы с косоугольными осями, но он не является обычным. Обычный способ представлен на рис. 17.11.2: координатные значения вычисляются не ортогональным, а параллельным проецированием точки на косоугольные оси. Если косоугольные оси ортогональны, то оба подхода эквивалентны обычной декартовой системе координат. При проекционном подходе координаты относительно косоугольных осей и связаны с координатами относительно ортогональных осей соотношением

а при параллельном подходе — соотношением

Рис. 17.11.2. Точка Р имеет координаты по ортогональным осям и координаты по косоугольным осям с направляющими косинусами Два множества координат связаны соотношением

Следовательно, соотношение

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

следовательно,

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

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

Такой вариант брауновской задачи; кажется, еще не изучался. Если С ортонормирована, то критерий сводится Если С — квадратная и невырожденная, то критерий сводится к и задача очень напоминает ту, которую обсуждает Дж. Грювиус [см. Gruvaeus (1979)], за исключением того, что он накладывает ограничение вместо Соответствующая задача для «параллельной» координатной системы сводится к минимизации

Такую проблему обсуждают М. Браун и У. Кристоф [см. Browne and Kristof (1969)]. Критерии подобного типа обычно рассматриваются в контексте факторного вращения, и они имеют очень слабое отношение к сравнению методов многомерного шкалирования. Для минимизации критерия и, вероятно, критерия нужны итеративные процедуры.

Матрицы весов и могут быть заменены на другие типы весовых коэффициентов, которые часто соотносятся с моделями, постулирующими неодинаковые остаточные дисперсии. Р. Лисиц, II. Шонеман и Дж. Линго [см. Lissitz, Schonemann and Lingoes (1967)] рассматривают взвешенный ортогональный прокрустов критерий который должен минимизироваться при условии ортогональности матрицы Н для заданной матрицы Заметим, что в произведении множители не являются коммутативными, как это было при отсутствии весовых коэффициентов. Вторая задача тривиальна, поскольку известна, и, следовательно, и X могут быть заменены на и поэтому мы можем использовать предыдущую процедуру. Первая задача более сложная и приводит к уравнениям, очень похожим на те, которые выведены Б. Грином и Дж. Говером [см. Green and Gower (1981)]. Р. Лисиц и его соавторы отмечают, что трудности исчезают, если заменить требование ортогональности Н требованием ортогональности Но это едва ли решает первоначальную проблему.

Проблема, которая предположительно может встретиться в контексте многомерного шкалирования, связана с тем, что и X могут относиться к одним и тем же (или похожим) объектам, но представленным в разных порядках. Следует попытаться найти матрицу перестановок Р, которая переставляет сроки матрицы X так, чтобы их порядок соответствовал порядку строк в матрице Тогда следует минимизировать

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

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

На практике, кроме матрицы перестановок, вводят еще и ортогональное вращение. Тогда можно минимизировать

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

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

где и X симметричны, а Т ортогональна. П. Шонеман [см. Schdnemann (1968)] показал, что если имеет разложение по собственным векторам в виде а X в виде то оценка для Т имеет вид Тогда приближается Оси двух конфигураций совмещаются, но разбросы по осям не изменяются. Введение масштабного множителя могло бы привести к изменению масштаба по осям для матрицы X, тогда она была бы сопоставима с матрицей Общая двухсторонняя прокрустова задача, которую рассматривает П. Шонеман [см. Schonemann (1968)], более сложна. Необходимо минимизировать

где и X квадратные, а Т и ортогональные. Разложения по сингулярным значениям

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

Связь между проблемой перестановок и двухсторонней прокрустовой задачей становится понятной после анализа выражений для Единственная разница в том, что Т — ортогональная матрица общего вида, матрица перестановок, т. е. специальный случай ортогональной матрицы. Это приводит к приближенной неитеративной процедуре минимизации

а) найти Т по методу Шонемана [см. Schonemann];

б) взять в качестве Р ближайшую к матрицу перестановок.

Шаг б) эквивалентен минимизации ее можно осуществить, положив и используя решение, полученное с помощью линейного программирования.

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