16.1. Метрическое многомерное шкалирование

16.1.1. Статистическая модель метрического МШ.

В случае метрического МШ предполагается, что элементы единственной матрицы удаленностей А есть расстояния, измеренные с некоторой ошибкой, между объектами исследуемой совокупности, которые рассматриваются как точки в некотором -мерном пространстве

где — расстояние между точками — ошибка измерения.

Обычно, хотя это и не обязательно, пространство предполагается евклидовым, тогда

Дальше в данном параграфе будем иметь дело только с евклидовой метрикой.

16.1.2. Классическая модель и решение задачи метрического МШ.

Описанные далее модель и способ определения координат точек подробно рассмотрены в работах [318, б], [52]. В данной модели предполагается, что ошибки измерения , так что — это в точности евклидовы расстояния.

Метод определения координат точек (с точностью до ортогонального вращения) и заодно размерности пространства, в которое они отображаются, основан, однако, не на непосредственном использовании матрицы А, а на преобразовании ее в матрицу В скалярных произведений центрированных векторов

Переход от матрицы исходной информации Д к матрице В производится следующим образом. Оказывается

Процедура перехода от А к В называется двойным центрированием А. Матрица В размера обладает следующими свойствами:

1) В неотрицательно определена;

2) ранг матрицы В равен размерности искомого пространства отображения;

3) ненулевые собственные числа матрицы В, упорядоченные в порядке убывания, совпадают с соответствующими собственными числами матрицы , где X — центрированная матрица данных (неизвестная нам), т. е. матрица, элементы столбца которой и являются координатами вектора Матрица есть матрица ковариаций для

4) пусть есть собственный вектор матрицы S, соответствующий собственному числу К, тогда вектор значений главной компоненты будет

В то же время пусть собственный вектор матрицы В, соответствующий тому же самому собственному значению , т. е.

тогда .

Из свойства 4) следует, что, решая проблему собственных чисел и собственных векторов для матрицы В и ограничиваясь ненулевыми собственными числами получим координатное представление точек в пространстве главных компонент, основываясь на формуле (16.4); величину размерности такого пространства, равную числу положительных собственных чисел матрицы

Элементы матрицы В могут быть представлены в виде

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

16.1.3. Погрешность аппроксимации. Оптимальность линейного метрического МШ.

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

Как следует из экстремальных свойств главных компонент (см. гл. 13),

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

Заметим, что решение , где определены равенством (16.4), доставляет глобальный минимум критерию (16.6), хотя координатные векторы являются линейными функциями от X. Этот результат носит название теоремы Эккарта — Юнга.

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

16.1.4. Возможности расширения применимости линейного метрического МШ.

Проблема аддитивной константы. Применение алгоритма линейного метрического шкалирования, строго говоря, будет корректным при выполнении следующих условий: все — евклидовы расстояния, и эти расстояния измерены без ошибки. Об устойчивости алгоритма к ошибкам свидетельствует значительное количество удачных его применений [90, 61, 89].

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

Очевидно, существует такое значение что для величин будет выполняться неравенство треугольника, т.е. они будут расстояниями. В частности, это будет, если

Значение а есть минимальное значение константы а, при котором выполняется неравенство треугольника [201] для всех троек объектов из преобразованной матрицы

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

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

16.1.5. Нелинейные методы метрического МШ.

Эти методы основываются на получении матрицы путем прямой минимизации критерием вида

или

Семейство критериев вида (16 8) с различным выбором весов рассматривается в [300, 9, 152,81] (см также § 13.6). Критерий вида (16 8) предложен в [9, 329]. Вычислительные аспекты, связанные с минимизацией (16.8), описаны в § 13.6, некоторые другие подходы, например использование метода сопряженных градиентов, описаны в [152].

Веса в критерии (16.8) обычно выбирают в одной из следующих форм. (см также § 13.6). Вид критериев типа (16 8) аналогичен виду клас сического критерия неметрического шкалирования типа «стресс» (stress) Нормирующие константы подбираются так, чтобы, во первых, критерий стал однородным по во-вторых, отражал некоторую относительную величину качества аппроксимации. Например, в критерии Сэммона (см § 13.5) вес Наличие нормирующей константы не влияет, однако на получение минимизирующего решения, поскольку величины считаются неизменными в процессе минимизации (в отличие от процедур неметрического МШ)

В качестве расстояний не обязательно брать евклидовы, можно использовать например, метрику Минковского [152]

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

При метрическом МШ, основанном на критериях типа (16.8), (16 8), уже можно обрабатывать матрицы А с пропущенными элементами Для этою суммирование в (16.8) и (16.8) достаточно проводить только тех пар объектов, для которых удаленности измерены Экспериментально показано, что качество восстановления конфигурации будет почти таким же, как для полной матрицы, даже при достаточно большом числе пропусков (порядка 1/3 расстояний для каждого объекта) [90].