Формальная постановка задачи шкалирования

Дана симметричная матрица различий между объектами .

Требуется построить пространство возможно меньшей размерности r и найти в нем координаты точек-объектов

так, чтобы матрица расстояний

между ними, вычисленная по введенной на Х метрике, была, в смысле некоторого критерия, близка к исходной матрице G попарных различий.

При решении поставленной задачи возможны два подхода: метрический, при котором матрица различий G изначально является искомой матрицей расстояний D, и неметрический (монотонный, ранговый), ориентированный на сохранение того же порядка попарных расстояний, что и в исходной матрице различий: → .

Неметрический этап

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

Этап состоит из нескольких шагов.

1. Упорядочить по возрастанию данные о различиях по исходной матрице G. Получившийся порядок пар объектов задает и порядок оценок расстояний или отклонений.

2. Серия проходов: в начале первого прохода на конкретной итерации отклонениями являются текущие оценки расстояний из предыдущей итерации или стартовой конфигурации. В начале каждого последующего прохода на той же итерации отклонения берутся из предыдущего прохода. Проход начинается с разбиения оценок отклонений на блоки равных значений. Пусть m=(1,...,M) будет индексом, обозначающим блоки от самого верхнего (m=1) до самого низкого (m=M). Начиная с m=1, элементы m-го блока сравниваются с элементами (m+1)-го блока. Если элементы m-го блока меньше элементов (m+1)-го блока, необходимо перейти к сравнению двух следующих блоков. Как только элементы m-го блока окажутся больше элементов (m+1)-го блока, то все элементы m-го и (m+1)-го блоков приравниваются среднему арифметическому обоих блоков. Эти два блока объединяют в один, который становится новым
m-ым блоком. Затем опять сравнивают m-й и (m+1)-й блоки; проход заканчивается после сравнения всех соседних блоков. Результат прохода – новый набор оценок отклонений. После завершения проходов отклонения будут удовлетворять условию монотонности (12.1). Пример работы алгоритма дается в табл.27.

Таблица 27

Продолжение табл.27

В столбце 3 нет подряд идущих одинаковых чисел, так что каждая строка образует блок. Просматривая этот столбец сверху вниз, обнаруживаем, что в строках 3 и 4 имеет место инверсия (нарушение монотонности –– 0,16>0,14). Блоки 3 и 4 объединяются в один со значением (0,16+0,14)/2=0,15. Просматривая теперь столбец 5, убеждаемся в необходимости слияния блоков 6 и 7. Как видно из 7-го столбца нарушений условия монотонности не осталось, что позволяет считать элементы столбца 7 искомыми отклонениями .

Метрический этап

На этом этапе решают задачу математического программирования, в результате чего получают новые оценки координат, по которым рассчитывают новые оценки расстояний. Исходными данными являются отклонения, рассчитанные на неметрическом этапе, оценки координат и расстояний предыдущей итерации. В качестве целевой функции выступает S₁ (12.2).

Минимизация S₁ проводится одним из градиентных методов.