10.1.3. Итеративный алгоритм.

Конфигурация векторов в -мерном пространстве может иметь истинную размерность,

меньшую чем Это означает, что указанная конфигурация паходится на -мерной гиперповерхности в -мерном пространстве Эту гиперповерхность можно рассматривать как результат нелинейного искажения некоторой линейной гиперповерхности. Это искажение можно устранить с помощью итеративного процесса «растягивания». На рис. 10.4 показано множество из пяти векторов, расположенных на кривой (сплошная линия) в двумерном пространстве. Эти точки развертываются в прямую лиьшю (пунктирная линия). После этого истинную размерность можно определить методом Карунена — Лоева.

Рис. 10.4. Растягивание данных.

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

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

Если эти расстояния удовлетворяют условию

то говорят, что ранг равен 1, ранг равен 2 и т.

В результате преобразования от расстояния между объектами

Величины вообще говоря, отличны от но нам хотелось

бы сохранить их ранги, т. е. сделать так, чтобы ранг остался равным рангу

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

Пример 10.3. Для четырех объектов, показанных на рис. 10.5, а, можно найти преобразование, переводящее их в одномерное пространство и сохраняющее ранговый порядок (рис. 10.5» б) 4

Рис. 10.5. Истинная размерность и ранговый порядок. о)

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

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

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

Размер локальной области, в пределах которой ранги должны сохраняться, выбирается из практических (инженерных) соображений. Например, если выбрать две локальные области, как по казано пунктирными линиями на рис. 10.5, в, то для первой области сохраняются соотношения для второй — (рис. 10.5, г). Поэтому можно сделать вывод, что истинная размерность данных на рис. 10.5, в равна 1. Являются ли данные на рис. 10.5, в одно- или двумерными — это весьма субъективный вопрос, на который нельзя дать однозначного ответа.

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

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

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

показанные на рис. 10.4, сближать друг с другом, кривая будет выпрямляться.

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

Таблица 10.3 (см. скан) Математическое ожидание и дисперсия расстояния между объектами

Существует много способов увеличения дисперсии без нарушения рангового порядка. Расмотрим один из них [Беннет, 1969].

Рис. 10.6. Плотность вероятности расстояния [Беннет, 1969].

1. Дисперсию увеличивают путем смещения каждого объекта Х согласно следующему правилу:

Общее смещепие состоит из ненулевых компонент. Если то существует компонента, отодвигающая объект

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

2. Если смещение объекта нарушает ранговый порядок следует изменить таким образом, чтобы уменьшить это нарушение. Это можно сделать следующим образом:

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

Преобразования такого типа первоначально были предложены для решения некоторых задач психологии, например, следующей задачи [Шепард, 1962 а, б]. Совокупность из объектов характеризуется набором из чисел — попарных степеней сходства . При этом физический смысл имеет лишь относительная величина, или ранг каждого Задача состоит в том, чтобы получить осмысленное геометрическое представление этих объектов.

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