6.13. ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПРОСТРАНСТВЕ МЕНЬШЕЙ РАЗМЕРНОСТИ И МНОГОМЕРНОЕ МАСШТАБИРОВАНИЕ

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

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

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

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

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

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

легко вычислить:

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

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

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

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

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

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

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

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

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

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