6.13. Представление данных в пространстве меньшей размерности и многомерное масштабирование

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

Начнем с более простого случая, когда имеет смысл говорить о расстояниях междуп выборками x₁, x₂, . . ., x_n. Пусть у_i — отобра­жение x_i в пространство меньшей размерности, _ij - расстояние между х_i и х_j, a d_ij — расстояние между y_i и y_j. Тогда мы ищем конфигурацию точек отображения y_i,…, y_n, такую, для которой п(п—1)/2 расстояний d_ij между точками отображений по возможно­сти близки соответствующим начальным расстояниям _ij . Так как обычно нельзя найти конфигурацию, для которой d_ij =_ij для всех i и j, нам необходим некоторый критерий для принятия решения, лучше ли одна конфигурация другой. Следующие функции сумм квадратов ошибок подходят в качестве кандидатов:

Так как функции критериев содержат только расстояния между точками, они инвариантны к жесткому передвижению всей конфигу­рации. Более того, они все нормированы, так что их минимальные значения инвариантны относительно раздвижения точек выборок. Функция J_ee выявляет наибольшие ошибки независимо от того, большие или малые расстояния _ij. Функция J_ff выявляет наиболь­шие частные ошибки независимо от того, большие или малые ошибки |d_ij-_i|. Функция J_ef— полезный компромисс, выявляющий наи­большее произведение ошибки и частной ошибки.

Если функция критерия выбрана, оптимальной считается такая конфигурация y₁, . . .,у_n, которая минимизирует эту функцию кри­терия. Оптимальную конфигурацию можно искать с помощью стандартной процедуры градиентного спуска, начиная от некоторой начальной конфигурации и изменяя у_i в направлении наибольшего уменьшения функции критерия. Так как

градиентd_ij по отношению к y_i — это просто единичный вектор в направлении y_i - у_j,. Таким образом, градиенты функции критерия легко вычислить ¹²:

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

Следующий пример иллюстрирует результаты, которые можно получить этими методами¹³. Данные состоят из 30 точек, располо­женных на единичных интервалах вдоль трехмерной спирали:

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

В неметрических многомерных задачах масштабирования вели­чины _ij представляют собой различия, чьи числовые значения не так важны, как их упорядочение. Идеальной была бы такая конфи­гурация, в которой упорядочение расстояний d_ij было бы одинако­вым с упорядочением различий _ij. Упорядочим т=п(п—1)/2 различий так, что _i1j1  …_imjm и пусть d`_ij — любые т чисел, удовлетворяющие ограничениям монотонности:

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

где всегда предполагается, что_ij удовлетворяет ограничениям монотонности. Таким образом, _mon — мера того, в какой степени

Рис. 6.21.Двумерное представление точек данных в трехмерном пространстве (Саммон, 1969). а —спираль,б —точки отображения.

конфигурация точекy_i, ... , у_n соответствует первоначальным дан­ным. К сожалению, _mon нельзя использовать для определения оптимальной конфигурации, так как это может свести конфигурацию к одной точке. Однако этот дефект легко устраняется следующей нормировкой:

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