Неметрическое шкалирование. Схема алгоритма Каскала

Рассмотрим один из известных алгоритмов неметрического многомерного шкалирования, предложенный Дж. Краскалом. Пусть – оценки координат, где i – номер точки; k – номер координаты; – оценка расстояний по -метрике; – ранговые образы расстояний, иначе отклонения. Эти величины должны соответствовать, насколько это возможно, оценкам расстояний, но с сохранением условия монотонности: . (12.1)

Для оценки степени расхождения вводят меру соответствия (S -стресс):

либо , где – среднее арифметическое оцененных расстояний.

Наряду с S -стрессом используется SS -стресс, где в числителе оценки расстояний и отклонения заменены их квадратами. SS -стресс обеспечивает более быструю сходимость, если матрица различий симметрична.

Алгоритм Краскала состоит из пяти основных этапов:

1) формирование стартовой конфигурации, то есть получение начальных оценок координат (размерность пространства предполагается известной);

2) стандартизация расстояний и оценок координат;

3) неметрический этап, в ходе которого вычисляются отклонения;

4) метрический этап: перерасчет оценок координат;

5) подсчет меры соответствия.

Если мера улучшилась, то возвращаются к этапу 2; в противном случае работа алгоритма завершается.

Рассмотрим перечисленные этапы подробнее. Стартовая конфигурация строится по методу Торгерсона (ортогональное проектирование). Затем по координатам найденных точек вычисляется матрица расстояний с элементами .

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

Стандартизация оценок расстояний и координат состоит в делении их на сумму квадратов . Очевидно, подобное преобразование делает сумму квадратов расстояний равной единице, что снижает вероятность получения вырожденного решения и упрощает вычисления, особенно при использовании S ₁-стресса, выражение для которого приобретает вид . (12.2)