17.9. МНОГОМЕРНАЯ РАЗВЕРТКА

Многомерная развертка впервые была предложена психологами. Однако ее приложения в настоящее время широко распространены и в других областях. Пусть мы имеем таблицу с двумя входами. Ее строки соответствую! различным людям, а столбцы — деятельности или опыту этих людей. Для иллюстрации предположим, что столбцы соответствуют газетам, которые они читают. Для заполнения таблицы с двумя входами каждого человека просят проракжировать газеты по предпочтительности. Результатом многомерной развертки является совместная ординация, включающая как людей, так и газеты. Газеты с высоким рангом для данного человека представляются точкой, которая находится вблизи точки, представляющей этого человека. постановке этот метод похож на биплоты [см. раздел 17.4] и на анализ соответствий [см. раздел 17.5], но в отличие от них многомерная развертка позволяет определить расстояния между двумя множествами точек, которые потом получают непосредственную интерпретаций. В своем первоначальном виде совместная ординация была одномерной. Можно вообразить линию, сложенную (подвешенную) в точке, соответствующей индивиду, который интересует исследователя. Все точки, представляющие газеты, должны быть по одну сторону от точки подвеса и в порядке, соответствующем предпочтениям индивида. По крайней мере так было бы, если бы была возможна точная ординация. Точки, представляющие индивидов, называют идеальными точками. Одномерная совместная ординация очень редко точно отражает предпочтения всех индивидов. Ординации в пространстве более высокой размерности дают более точное представление.

Один из путей реализации многомерной развертки — применение стандартных методов неметрического шкалирования. В разделе 17.8 мы обращали внимание на то, что алгоритмы неметрического шкалирования могут работать с пропущенными данными. Таблица

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

Хотя развертка зародилась для данных о предпочтениях, к настоящему времени она обобщена и на количественные данные. В этом случае элементы строк и столбцов матрицы А измерены в одной системе и нет необходимости в разбиении критерия по строкам; здесь неметрическое многомерное шкалирование «работает» лучше. При количественных данных подобного типа целесообразно испробовать возможности метрического подхода. Исследуем случай, когда А — часть матрицы расстояний между точками в пространстве размерности . Будем оперировать квадратами расстояний. Матрица той же размерности, что и А, но ее элементы могут быть функциями от элементов матрицы А. Тогда проблема развертки состоит в нахождении координат порождающих матрицу На данный момент допустим, что возможно точное отображение. Тогда по теореме Пифагора

где — единичная матрица. Пусть Тогда

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

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

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

Поскольку можно упростить уравнение относительно у:

что после обратной постановки дает

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

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

где определяется из предыдущего уравнения. Наконец, вычисляются координаты

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

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

Одна из таких итеративных схем следует из анализа нормальных уравнений для шкалирования квадратов расстояний по методу наименьших квадратов [см. раздел 17.7] применительно к развертке. Введем остаточную матрицу

Тогда в качестве критерия минимизации используют что приводит к нормальным уравнениям:

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

R инвариантна относительно вращений и переносов конфигураций X и Легко увидеть, что решение нормальных уравнений недоопределено в этом отношении. В случае точного приближения обе части уравнений также обращаются в нуль. Умножив оба уравнения слева на (соответствующей длины), получим

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

После подстановки результатов решения нормальных уравнений получаем

откуда

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

Нормальные уравнения порождают естественный альтернативный алгоритм наименьших квадратов для итеративного решения задачи развертки. Если известно, то первое уравнение дает оценку для X при шкалировании квадратов расстояний по методу наименьших квадратов. Эта оценка уменьшает (или по крайней мере не увеличивает) остаточную сумму квадратов. Аналогично если известна X, то из второго нормального уравнения можко получить оценку для Процедура повторяется до сходимости к удовлетворительному решению. К сожалению, даже когда известна, не всегда просто решается первое (второе) уравнение относительно

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

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

где Заметим, что ни одно из уравнений

относительно к элементов строки матрицы X не включает элементов других строк. М. Гринакр [см. Greenacre (1978)] предлагает для решения этих уравнений ввести новую переменную

тогда

Подстановка в формулу для дает

где Это выражение — полином от степени Следовательно, он имеет хотя бы один действительный корень. Проблема в том, как найти наилучшее решение этого полинома. В задачах такого типа обычно наименьший корень должен соответствовать минимальной остаточной сумме квадратов [см., например, косоугольный прокрустов анализ в разделе 17.10]. М. Гринакр отмечает, что он не встречал примеров, когда не было бы оптимальным корнем, но нет доказательств того, что он всегда оптимален. Поэтому необходимо исследовать все действительные решения полинома, хотя, конечно, допустимо редуцирование этого процесса. Например, и тогда нет действительного корня, превосходящего по величине Эти простые правила, ограничивающие действительные корни полинома, допускают применение аппроксимационных методов, таких, как метод Ньютона для решения полиномиальных уравнений или метод деления пополам. Более тонкие правила приводят к более экономным процедурам.

Для каждого возможного необходимо вычислить остаточную сумму квадратов. Мы имеем

но из первого нормального уравнения откуда

Выделим члены, содержащие X:

Подставив значение x в точке минимума, получим

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

Это дает простой способ оценки с целью получения минимального значения .

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

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

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

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

Записав и переставив члены, получим

Записав получим

Кососимметричная матрица в правой части имеет ранг 2. Мы не проводили детальный анализ того, что же порождает такое условие, однако представляют интерес некоторые специальные решения. Одно очевидное решение получаем при тогда Существует ли решение для ортогональной матрицы Н? Из этого условия следует, что поэтому если X имеет ранг, равный количеству столбцов, то Симметричными ортогональными матрицами являются диагональные матрицы с элементами которые соответствуют различным отражениям относительно координатных осей (или относительно начала координат). Тогда преобразование Хаусхолдера дает где — единичный вектор. Такое решение представляет отражение относительно гиперплоскости с нормалью и [см. III, раздел 4.10]. Существуют более сложные решения. Например, если где — симметричная матрица, то правая часть уравнения обращается в нуль, а левая дает т. е. константу. Тогда и конфигурация X лежит на конусе общего вида, задаваемого квадратичной формой Конфигурация лежит на конусе, задаваемой квадратичной формой Эти два конуса опираются на одни и те же главные оси. Когда симметрична, кажется, что расстояния между точками-строками и расстояния между точками-столбцами должны совпадать. Однако последний пример показывает, что это вовсе не обязательно.

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

Интерпретация двумерной симметричной развертки пока не до конца осмыслена, но некоторые эмпирические правила можно сформулировать:

а) если развертка дает пары совпадающих точек, то вероятно, что исходные расстояния соответствуют конфигурации, близкой к двумерной;

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

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

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