17.7. МЕТРИЧЕСКОЕ ШКАЛИРОВАНИЕ: ДРУГИЕ МЕТОДЫ

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

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

В дальнейшем мы сосредоточим внимание на поиске множества координат X в пространстве размерности к, которые порождают евклидовы расстояния Будем предполагать, что элементы —матрицы А аппроксимируют данные Один из возможных подходов — подобрать X, минимизирующую Это — шкалирование по методу наименьших квадратов, а сам критерий иногда называют стрессом (STRESS) [см. в разделе 17.8 соответствующее определение для неметрического шкалирования]. Если наблюдения независимы и одинаково нормально распределены, то за критерий принимается максимум правдоподобия. Дифференцирование этого критерия по элементам матрицы X приводит к нормальным уравнениям относительно элементов матрицы X:

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

Например, из условия нулевой суммы элементов X по столбцам следует, что центрированная матрица расстояний, соответствующая [см. в разделе 17.6]. Умножив нормальное уравнение на получим

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

Итак, или . Отсюда при минимальном значении критерия имеем

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

Для решения уравнения относительно X предлагается два метода. В первом используется одна из процедур многоцелевой оптимизации, разработанных специалистами по численному анализу [см., например, Murray (1972)]. Второй подход более эвристический, он опирается на работу Гуттмана [см. Guttman (1968)]. Имеем где — симметричная матрица с нулевой суммой по строкам (и столбцам), Если X задана в центрированном виде, то можно записать нормальное уравнение:

Оно может служить основой для итеративной последовательности

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

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

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

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

Другой критерий, применяемый в метрическом шкалировании, — найти конфигурацию X, минимизирующую Такой подход называют квадратичным шкалированием по методу наименьших квадратов, а критерий иногда называют стрессом (STRESS). Нормальные уравнения

напоминают нормальные уравнения для шкалирования по методу наименьших квадратов. — симметричная матрица с нулевой суммой элементов по строкам (и столбцам), Как и ранее,

В данном случае

Мы приходим к дисперсионному анализу квадратов расстояний:

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

Критерии обычно задаются в форме с весовыми коэффициентами:

и

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

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

его можно минимизировать, выбрав

что приводит к

где

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

Аналогичные рассуждения приводят к выражению для

где

поэтому минимизируется при максимизации последнее достигает максимального значения при

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

Взвешенная нецентрированная корреляция между может быть определена как

Положив , получаем

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

. В точке минимума

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

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