Многомерное шкалирование. Метрический и неметрический подходы.

Кроме таблиц «объект-признак» источником данных могут служить таблицы «объект-объект», содержащие данные о связях объектов. Математический образ подобных таблиц – квадратная матрица, элемент которой на пересечении i-й строки и j-го столбца содержит сведения о попарном сходстве либо различии анализируемых объектов. Задача состоит в том, чтобы представить эти объекты в виде точек некоторого координатного пространства невысокой размерности. При этом связи объектов должны быть переданы расстояниями между точками. Такая простая геометрическая модель приводит к содержательно интерпретируемому решению: каждая ось порождаемого пространства является одномерной шкалой и соответствует некому латентному признаку. Тем самым объекты наделяются признаками, интерпретация которых связывается с расположением объектов в искомом пространстве.

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

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

Требуется построить пространство возможно меньшей размерности 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 искомыми отклонениями .

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

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

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