Метрическое шкалирование: подход Торгерсона

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

, . (5.26)

Так как – симметричная матрица, то существует матрица Х, удовлетворяющая условию:

. (5.27)

С другой стороны, согласно курсу линейной алгебры, матрицу можно представить в виде:

, (5.28)

где – матрица из собственных векторов матрицы ,

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

Выражение (5.28) можно представить в виде:

, (5.29)

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

Сравнивая выражения (5.27) и (5.29), получаем . Так как на главной диагонали матрицы различий стоят нули, то след этой матрицы равен нулю, и, следовательно, по крайней мере, одно её собственное число отрицательно, что приводит к появлению комплексного числа на главной диагонали матрицы [21]. Таким образом, разложение матрицы вида (5.27) не позволяет получить координаты объектов в пространстве действительных чисел.

Возникает необходимость преобразовать матрицу таким образом, чтобы все ее собственные числа были больше или равны нулю, т.е. сделать ее положительно полуопределенной. Такое преобразование впервые было предложено Торгерсоном. Метод Торгерсона основывается на теореме Янга и Хаусхолдера, которая определяет пути решения задачи нахождения расстояния между точками в действительном евклидовом пространстве.

Рассмотрим расстояния , , между точками i, j, k (рисунок 5.6).

Рисунок 5.6 – Треугольник со сторонами , ,

Предлагается найти симметричную матрицу , элементы которой определяются как скалярное произведение двух векторов: . Из теоремы косинусов () следует, что . Таким образом, элементы матрицы рассчитываются по формуле: . В качестве точки i можно взять любую из n точек и тогда будут получены n матриц .

Теорема Янга и Хаусхолдера утверждает следующее [16]:

1. если какая-либо матрица положительно полуопределена, то расстояния между объектами можно рассматривать как действительные расстояния в евклидовом пространстве. Все собственные числа при этом больше или равны нулю;

2. число положительных собственных чисел определяет ранг матрицы и равно числу осей координатного пространства;

3. любую положительно полуопределенную матрицу ранга k () можно факторизовать в виде . Строки матрицы Х – это координаты n объектов в k -мерном евклидовом пространстве с центром в точке i. Каждой i -ой точке будет соответствовать своя конфигурация.

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

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

, (5.30)

где ; ; , .

Матрица с двойным центрированием – это матрица, у которой среднее значение элементов каждой строки и каждого столбца равно нулю.