17.6. МЕТРИЧЕСКОЕ ШКАЛИРОВАНИЕ: АНАЛИЗ ГЛАВНЫХ КООРДИНАТ И КЛАССИЧЕСКОЕ ШКАЛИРОВАНИЕ

Стартовая точка для всех методов многомерного шкалирования — симметричная матрица М порядка Ее элементы ту задают некоторые меры связей (например, близости, различия, расстояния) между объектами и Связи могут быть наблюдаемы непосредственно, а могут быть вычислены из других более фундаментальных данных, таких, как матрицы данных, обсуждаемые в разделе 17.1. Необходимо проанализировать матрицу М и построить ординацию в виде множества из точек в -мерном пространстве таким образом, чтобы расстояния между точками аппроксимировали ту или по крайней мере некоторую функцию от . При метрическом шкалировании, которое обсуждается в настоящем и последующих разделах, критерии для оценки качества отображения — просто функции , где — аппроксимирующие значения. При неметрическом подходе, рассматриваемом в разделе 17.8, используются более общие критерии качества отображения.

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

Предположение, что величины ту — расстояния, влечет за собой следующее:

б) существует действительное множество точек

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

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

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

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

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

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

тогда элементы матрицы М? есть

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

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

Отсюда 1 — собственный вектор, соответствующий нулевому корню. Для любого разложения имеем — вектор-строка центроида конфигурации; как было показано, отсюда следует, что все Сумма координат по столбцам равна нулю, геометрически это означает, что начало координат находится в центре тяжести конфигурации. Если и является спектральным разложением матрицы то диагональна. Поэтому координатные оси являются главными осями конфигурации точек. Отсюда следует, что собственные значения X,, расположенные в порядке убывания, дают суммы квадратов, вычисленные для последовательных осей, и могут, как и в компонентном анализе, использоваться для определения размерности, достаточной для хорошего отображения. Заметим, что преобразование гарантирует Это метод главных координат, который для любой симметричной матрицы М порядка дает набор координат точек, такой, что начало координат находится в центре тяжести конфигурации, и главные оси совпадают с координатными осями. В случае, когда расстояния евклидовы, найденные таким образом координаты — действительные. Для существования действительного решения необходимо и достаточно, чтобы матрица М была положительно полуопределена для некоторого вектора Достаточность очевидна, необходимость доказать сложнее [см. Blumenthal (1970)]. М может быть вычислена из матрицы М для любым способом выбранного вектора лишь бы он давал дополнительное нулевое собственное значение. Оба способа, обсуждаемые выше, в матричном обозначении записываются так:

и

где — вектор, компонента которого равна единице, а все остальные — нули.

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

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

где — любой вектор с единичной суммой элементов, не являющийся нулевым вектором матрицы М. Такой выбор эквивалентен определению как Говер [см. Gower (1982)] показал, что конфигурация является евклидовой тогда и только тогда, когда положительно полуопределена. Разложение даег конфигурацию с центром, удовлетворяющим соотношению Введенные мультипликативные формы показывают, что для для М. Квадрат расстояния каждой точки от выбранного начала координат задается как Эта диагональная матрица может быть записана в виде вектора-столбца где первый элемент отсутствует, если М является матрицей расстояний. Эти результаты могут быть использованы для получения с хорошими геометрическими свойствами. Например, если начало координат должно быть в центре гиперсферы, описанной вокруг конфигурции, то налагается условие

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

для некоторого . Для невырожденной матрицы М

и поскольку то определяет и задает Такое определяет

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

может не оказаться положительно полуопределенной. Тогда отвергается предположение, что существует реальная евклидова конфигурация в пространстве размерности с заданными расстояниями; это вызывает сомнение в обоснованности геометрических аргументов, базирующихся на проекциях. Отрицательность малых собственных значений не представляет серьезной проблемы. В исследованиях эффектов добавления возмущений в матрицу евклидовых расстояний Р. Сибсон [см. Sibson (1979)] показал, что может быть порождено несколько малых отрицательных собственных значений. Он предложил удобное правило для определения размерности: сумма оставшихся положительных собственных значений должна быть приблизительно равна сумме всех собственных значений. Можно считать, что малые отрицательные собственные значения уничтожают несущественно малые положительные собственные значения.

Наличие большого по абсолютной величине отрицательного собственного значения отвергает идею об евклидовом пространстве. Оправданность использования классической процедуры шкалирования может быть проверена по теореме Экарта—Юнга [см. раздел 17.3]. Мы имеем и теорема Экарта—Юнга для симметричных матриц утверждает, что наилучшее приближение ранга матрицы можно получить, положив равными нулю все меньшие по модулю собственные значения. Если при этом остаются отрицательные собственные значения, то евклидово представление нереализуемо. Даже если наибольших по модулю собственных значений положительны и евклидово представление допустимо, оптимизируемый при этом критерий наименьших квадратов не идентичен первоначальному критерию. Эти два критерия совпадают, только когда все собственные значения неотрицательны. Хотя аппроксимации, включающие отрицательные собственные значения, не могут интерпретироваться в терминах расстояний, они дают полезные упрощающие преобразования данных. Из всех метрических методов шкалирования только классическое шкалирование/метод главных координат позволяет распознать хорошую неевклидову аппроксимацию, если она существует. Другие методы, обсуждаемые в разделе 17.7, аппроксимируют только евклидовы конфигурации и не могут быть модифицированы так, чтобы реализовывать достаточно гибкие неевклидовы модели. Трудность в том, что в -мерной аппроксимации каждая из осей может быть мнимой, и их возможных представлений только одно евклидово. В анализе главных координат отрицательные собственные значения указывают, сколько нужно включить мнимых осей. В других методах приходится независимо просчитывать возможных решений, что непрактично, особенно если это должно быть сделано для каждого значения потенциальных размерностей.

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

Встает вопрос, можно ли подобрать константу к, чтобы к стали действительными евклидовыми расстояниями и, следовательно, приводили к действительной ординации, даже когда исходные к ней не приводят. До недавнего времени не было известно точного решения этой проблемы, хотя У. Торгерсон [см. Torgerson (1958)] разработал численный итеративный алгоритм. Прежде чем описывать новое решение проблемы аддитивной константы, приведем решение, предложенное Дж. Линго [см. Lingoes (1971)] для более простой задачи. Необходимо подобрать наименьшую константу к, чтобы были квадратами действительных евклидовых расстояний. Поскольку для воспроизведения расстояний ту необходима матрица с элементами в дальнейшем в данном разделе будем предполагать, что матрица М задана именно в таком виде. Тогда матрица с эквивалентными скорректированными квадратами расстояний будет следующей:

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

Для матрицы двойное центрирование:

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

Чтобы обеспечить существование действительной конфигурации, достаточно выбрать , такое, чтобы все были неотрицательны.

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

Вернемся к проблеме аддитивной константы. Ф. Кайез [см. Cailliez (1983)] показал, что к является наибольшим собственным значением матрицы

где . При таком к расстояния к порождают действительную конфигурацию в пространстве размерности не более