Теорема Торгерсона

Если элементы матрицы различий удовлетворяют условию (5.26), то элементы матрицы будут иметь вид [26]:

, , (5.31)

где , – центрированные значения l -го признака для i -го и j -го объектов в координатном пространстве.

Если в качестве матрицы Х рассматривать матрицу центрированных значений признаков, то или .

Доказательство теоремы Торгерсона приведено в приложении К.

Матрицу удобнее рассчитать в матричном виде. Для этого необходимо построить матрицу М с элементами , . Тогда формула (5.30) принимает вид:

, (5.32)

где – эффект строк;

– эффект столбцов;

– общий эффект.

Матрица в матричном виде рассчитывается следующим образом:

, (5.33)

где .

Так как матрица положительно полуопределена, то можно найти такую ортогональную матрицу Y и диагональную матрицу с неотрицательными элементами, что .

Факторизацию матрицы можно провести аналогично факторизации матрицы или R в методе главных компонент: , где – собственный вектор матрицы , соответствующий собственному числу . Собственные числа () равны суммам квадратов соответствующих координат объектов и могут использоваться, как и в методе главных компонент, для выбора размерности координатного пространства k.

Количество шкал k выбирают исходя из требуемого уровня информативности. Также могут быть использованы и другие критерии: для визуализации данных количество шкал берут равным двум или трем; в других случаях оставляют только те шкалы, которые поддаются интерпретации, или шкалы, для которых оценка собственного значения не меньше единицы или некоторого порогового значения [43]. При выборе размерности признакового пространства можно пользоваться критерием «каменистой осыпи» («сломанной трости»). Согласно этому критерию выбирается число координат, после которого исследуемая зависимость собственных чисел от числа координатных осей становится пологой и близкой к горизонтальной оси [16].

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

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

Алгоритм Торгерсона основан на предположении, что внедиагональные элементы матрицы различий являются в точности расстояниями и, в большинстве случаев, данный алгоритм позволяет получить положительно полуопределенную матрицу . Однако на практике встречаются ситуации, когда матрица не является положительно полуопределенной, что объясняется большими ошибками измерения элементов исходной матрицы расстояний , которые не удовлетворяют неравенству треугольника. Возникает вопрос, можно ли подобрать аддитивную константу c, чтобы стали расстояниями? Если удастся подобрать такую константу, то шкалирование приведет к действительным координатам. Взяв аддитивную константу достаточно большой, можно добиться того, чтобы матрица стала неотрицательно определенной, а это гарантирует размещение точек в евклидовом пространстве. До настоящего времени не известно точного решения проблемы аддитивной константы, хотя имеется много численных алгоритмов нахождения этой константы. Например, оценку величины с можно вычислить по формуле: . Для получения оценки по этой формуле нужно из наибольшего элемента матрицы вычесть сумму двух наименьших элементов, что обеспечивает неравенство треугольника для всех элементов матрицы . После оценки константы с вычисляют новые расстояния , , , [16, 33, 26].