§4. Линейное шкалирование

Предположим, что исходной информацией об $n$ объектах служат экспертные данные о различиях между ними, выраженных числами $d_{ij}$ (или о сходствах $a_{ij}$). Сходства можно преобразовать в различия, например, по формулам $d_{ij} = 1/(1 + a_{ij})$ или $d_{ij} = 1 - a_{ij}$ при $0 \le a_{ij} \le 1$.

Хотелось бы представить объекты в виде точек некоторого координатного пространства $\mathbb R^m$ невысокой размерности (обычно $m = 2$ или $3$). При этом различия $d_{ij}$ между объектами должны быть как можно точнее переданы евклидовыми расстояниями $\delta_{ij}$ между точками в $\mathbb R^m$.

Каждый объект характеризуется координатами соответствующей точки по осям (шкалам) построенного пространства. Сами шкалы интерпретируются как новые признаки — те латентные или скрытые факторы, которыми неосознанно руководствуются эксперты, оценивая степень различия объектов. Процесс представления объектов наборами координат в некоторых осях называют шкалированием.

Смысл по-пацански: у тебя нет карты, есть только таблица «от кого до кого сколько идти». Шкалирование по этой таблице рисует карту. Причём оси на карте никто не подписал — что значат «север» и «восток» в этом мире, придётся догадываться самому.

Линейное шкалирование Торгерсона

Метод (его предложил У. Торгерсон в 1952 г., опираясь на работы Г. Юнга и А. Хаусхолдера 1938 и 1941 гг.; его также называют методом главных проекций) полезно связать с выделением главных компонент. Для этого удобно начать с нетипичного для приложений случая, когда объекты уже представлены точками $\boldsymbol x_i = (x_{i1}, \dots, x_{im})$ в $\mathbb R^m$, $i = 1, \dots, n$, а различия $d_{ij}$ являются евклидовыми расстояниями между ними:

Введём матрицу $\boldsymbol X = \|x_{il}\|_{n\times m}$. Допустим, что её элементы $x_{il}$ центрированы по столбцам (см. Д1 в §1). Зададим величины $g_{ij}$, $i, j = 1, \dots, n$, формулами

где $\delta_{\cdot j}^2 = \frac1n\sum_{i=1}^n\delta_{ij}^2$, $\delta_{i\cdot}^2 = \frac1n\sum_{j=1}^n\delta_{ij}^2$, $\delta_{\cdot\cdot}^2 = \frac1{n^2}\sum_{i=1}^n\sum_{j=1}^n\delta_{ij}^2$.

Процедура (7) перехода от матрицы $\boldsymbol\Delta = \|\delta_{ij}\|_{n\times n}$ к матрице $\boldsymbol G = \|g_{ij}\|_{n\times n}$ называется двойным центрированием: нетрудно убедиться, что средние значения каждой строки и каждого столбца матрицы $\boldsymbol G$ равны 0.

Метод Торгерсона опирается на следующие две теоремы.

Теорема 1. Имеет место равенство $\boldsymbol G = \boldsymbol X\boldsymbol X^T$, то есть $\boldsymbol G$ совпадает с матрицей скалярных произведений, встречавшейся ранее в §1.

Доказательство. Надо проверить, что

Раскрывая скобки в правой части равенства (6), получим

Далее, для любого фиксированного $j$ в силу теоремы Гюйгенса (см. решение задачи 3 главы 16) имеем представление $\frac1n\sum_{i=1}^n(x_{il} - x_{jl})^2 = \frac1n\sum_{i=1}^n(x_{il} - 0)^2 + (x_{jl} - 0)^2$ (центр масс столбца — ноль по Д1). Суммируя по $l = 1, \dots, m$, приходим к равенству

Точно так же, как формула (10), выводится соотношение

Припишем каждой точке (строке) $\boldsymbol x_i$ массу 1. По допущению Д1 их центром масс будет начало координат $\boldsymbol 0$. Согласно теореме о межточечных расстояниях (см. решение задачи 5 главы 16) запишем

где $I_{\boldsymbol 0}$ — момент инерции точек относительно $\boldsymbol 0$. Последнее соотношение эквивалентно равенству

Подставляя соотношения (9)–(12) в формулу (7), получаем равенство (8): все квадраты сокращаются, и остаётся только $-\frac12\cdot(-2)\sum_lx_{il}x_{jl}$. $\blacksquare$

Смысл по-пацански: из одних расстояний можно вытащить скалярные произведения, а значит — и углы, и длины. Двойное центрирование — это фокус «поставить начало координат в центр масс, ни разу не узнав координат».

Теорема 2. Отличные от нуля собственные значения $\mu_l$ у матрицы скалярных произведений $\boldsymbol G = \boldsymbol X\boldsymbol X^T = \|g_{ij}\|_{n\times n}$ и матрицы рассеяния $\boldsymbol W = \boldsymbol X^T\boldsymbol X = \|w_{ij}\|_{m\times m}$ одинаковы. При этом соответствующие собственные векторы $\boldsymbol y_l$ и $\boldsymbol z_l$ ($\boldsymbol G\boldsymbol y_l = \mu_l\boldsymbol y_l$, $\boldsymbol W\boldsymbol z_l = \mu_l\boldsymbol z_l$) связаны простым соотношением

$$\sqrt{\mu_l}\,\boldsymbol y_l = \boldsymbol X\boldsymbol z_l. \tag{13}$$

(Поскольку выборочная ковариационная матрица $\hat{\boldsymbol\Sigma}$ и матрица рассеяния $\boldsymbol W$ отличаются лишь постоянным множителем, $\hat{\boldsymbol\Sigma} = \frac1n\boldsymbol W$, то $\boldsymbol z_l$ совпадают с собственными векторами $\boldsymbol c_l$ матрицы $\hat{\boldsymbol\Sigma}$, а $\mu_l = n\lambda_l$.)

По кирпичикам: если $\boldsymbol X^T\boldsymbol X\boldsymbol z = \mu\boldsymbol z$, то $\boldsymbol X\boldsymbol X^T(\boldsymbol X\boldsymbol z) = \boldsymbol X(\boldsymbol X^T\boldsymbol X\boldsymbol z) = \mu(\boldsymbol X\boldsymbol z)$ — то есть $\boldsymbol X\boldsymbol z$ собственный для $\boldsymbol G$ с тем же $\mu$. А $|\boldsymbol X\boldsymbol z|^2 = \boldsymbol z^T\boldsymbol X^T\boldsymbol X\boldsymbol z = \mu$, отсюда множитель $\sqrt\mu$.

Заметим, что справа в равенстве (13) стоит вектор координат проекций точек на $l$-ю главную компоненту $\boldsymbol z_l$. Таким образом, не зная самих координат $x_{il}$, можно на основе различий $d_{ij} = \delta_{ij}$ восстановить конфигурацию точек в пространстве $\mathbb R^m$ с помощью следующей процедуры шкалирования:

1. двойным центрированием матрицы различий $\boldsymbol\Delta$ вычислить матрицу $\boldsymbol G$;
2. степенным методом найти для матрицы $\boldsymbol G$ первые $m$ отличных от нуля (положительных) собственных значений $\mu_l$ и соответствующих им собственных векторов $\boldsymbol y_l$;
3. из (13) определить координаты точек в новом базисе пространства $\mathbb R^m$, состоящем из главных осей $\boldsymbol z_1, \dots, \boldsymbol z_m$: $l$-я координата $i$-й точки равна $\sqrt{\mu_l}\,y_{l,i}$.

Замечание 6. Сама матрица $\boldsymbol X$ не восстанавливается по матрице $\boldsymbol G$ однозначно. Действительно, пусть координаты точек $\boldsymbol x_i$ преобразуются в новые координаты по формуле $\tilde{\boldsymbol x}_i = \boldsymbol C\boldsymbol x_i$, где $\boldsymbol C$ — любая ортогональная матрица (см. П10). Так как векторы $\boldsymbol x_i$ — это столбцы матрицы $\boldsymbol X^T$, то $\tilde{\boldsymbol X}^T = \boldsymbol C\boldsymbol X^T$, или $\tilde{\boldsymbol X} = \boldsymbol X\boldsymbol C^T$. Тогда

$$\tilde{\boldsymbol G} = \tilde{\boldsymbol X}\tilde{\boldsymbol X}^T = (\boldsymbol X\boldsymbol C^T)(\boldsymbol C\boldsymbol X^T) = \boldsymbol X(\boldsymbol C^T\boldsymbol C)\boldsymbol X^T = \boldsymbol X\boldsymbol X^T = \boldsymbol G,$$

то есть матрица $\boldsymbol G$ сохраняется при ортогональном преобразовании координат. По этой причине исследователи иногда производят дополнительный (субъективный) поворот системы координат, чтобы содержательно интерпретировать признаки, соответствующие повёрнутым осям.

С другой стороны, матрица рассеяния $\boldsymbol W = \boldsymbol X^T\boldsymbol X$ меняется: $\tilde{\boldsymbol W} = \tilde{\boldsymbol X}^T\tilde{\boldsymbol X} = \boldsymbol C\boldsymbol W\boldsymbol C^T$. Новая матрица $\tilde{\boldsymbol W}$ подобна $\boldsymbol W$ (см. П10). Следовательно, их собственные значения $\mu_l$ совпадают. Новые собственные векторы $\tilde{\boldsymbol z}_l$ связаны с $\boldsymbol z_l$ тем же преобразованием, что и координаты точек: $\tilde{\boldsymbol z}_l = \boldsymbol C\boldsymbol z_l$. При этом правая часть соотношения (13) сохраняется: $\tilde{\boldsymbol X}\tilde{\boldsymbol z}_l = (\boldsymbol X\boldsymbol C^T)(\boldsymbol C\boldsymbol z_l) = \boldsymbol X\boldsymbol z_l$.

Проверим на реальной географии: по одним расстояниям между городами восстановим карту.

Получается карта, повёрнутая и, возможно, зеркально отражённая (замечание 6): метод знает расстояния, но не знает, где север. Два собственных значения почти исчерпывают след — Земля в этих масштабах «почти плоская».

Подход Торгерсона и аддитивная константа

Подход Торгерсона состоит в применении описанной выше процедуры шкалирования к произвольной симметричной матрице различий $\boldsymbol D = \|d_{ij}\|_{n\times n}$. Размерность $m$ координатного пространства задаётся исследователем. Обозначим через $\boldsymbol G^*$ результат двойного центрирования матрицы $\boldsymbol D$. (При умножении всех $d_{ij}$ на $c > 0$ элементы и собственные значения $\boldsymbol G^*$ умножаются на $c^2$, собственные векторы остаются прежними, а задаваемые формулой (13) координаты объектов в построенных шкалах умножаются на $c$. Из-за этого шкалирование Торгерсона называют линейным.)

Замечание 7. В случае, когда различия $d_{ij}$ не являются евклидовыми расстояниями, матрица $\boldsymbol G^*$ может не быть неотрицательно определённой. Приём, который обычно используется для преодоления этого, заключается в переходе к модели с так называемой аддитивной константой: $d_{ij}' = d_{ij} + a$, где $a > 0$. Наименьшее значение $a$, обеспечивающее выполнение неравенства треугольника для всевозможных троек $d_{ij}'$, очевидно, определяется по формуле

$$\hat a = \max_{1\le i,j,k\le n}\max\{d_{ik} - d_{ij} - d_{jk}, 0\}. \tag{14}$$

Но из выполнения неравенства треугольника ещё не следует неотрицательная определённость матрицы $\boldsymbol G^*$, вычисленной на основе $d_{ij}'$ (см. пример 3 ниже). Покажем, что, увеличивая $a$, можно добиться того, чтобы $d_{ij}'$ оказались евклидовыми расстояниями для некоторой конфигурации точек в $\mathbb R^m$, если размерность $m$ также достаточно велика. Действительно, для любой размерности $k$ можно указать $k + 1$ точку в $\mathbb R^k$, которые находятся друг от друга на одном и том же расстоянии $h$ (они называются вершинами правильного симплекса). Таковыми будут, скажем, $\boldsymbol u_0 = (0, \dots, 0)$ и $\boldsymbol u_i = (u_{i1}, \dots, u_{ik})$ ($i = 1, \dots, k$), где

$$u_{ij} = \begin{cases}h(\sqrt{k+1} + k - 1)/(k\sqrt2), & \text{если } i = j,\\ h(\sqrt{k+1} - 1)/(k\sqrt2), & \text{если } i \ne j\end{cases} \tag{15}$$

(для $k = 2$ — правильный треугольник). При очень большом значении $a$ объекты будут располагаться вблизи вершин правильного симплекса с рёбрами длины $a$ в пространстве $\mathbb R^{n-1}$, где $n$ — число объектов.

С другой стороны, при увеличении $a$ всё более нивелируются относительные отличия между $d_{ij}'$ по сравнению с отличиями между исходными $d_{ij}$. Кроме того, увеличивается число значимых по величине положительных $\mu_l$, то есть растёт размерность $m$ пространства, в котором располагается конфигурация точек, достаточно точно воспроизводящая $d_{ij}'$. Поэтому разумнее не добиваться неотрицательной определённости матрицы $\boldsymbol G^*$, а ограничиться тем, чтобы несколько её наибольших собственных значений $\mu_l$ были положительными, а все остальные собственные значения — малыми по модулю.

Смысл по-пацански: экспертные «расстояния» часто не лезут ни в какую геометрию: А близко к Б, Б близко к В, а А от В — как до луны. Аддитивная константа «надувает» все расстояния, чтобы картинка сложилась. Но перестараешься — и все объекты станут одинаково далёкими друг от друга, как вершины симплекса, и карта превратится в «каждый сам по себе».

Пример 3. Признаки собак и волков

Проиллюстрируем вышесказанное на примере анализа корреляционной матрицы рис. 3 (признаки собак и волков из §1). Положим $d_{ij} = 100\times(1 - \hat\rho_{ij})$: чем сильнее признаки связаны, тем они «ближе». Вычисленные степенным методом собственные значения матрицы $\boldsymbol G^*$ и приходящиеся на них проценты от полной дисперсии (следа матрицы):

Поскольку $\mu_4 = -187$, матрица $\boldsymbol G^*$ не является неотрицательно определённой.

На плоскости ($m = 2$) в целом точность хорошая — за исключением расстояния 1–2 и расстояний между точкой 6 и точками 4, 5: первое слишком большое (18 вместо 4), вторые — слишком малые (5 вместо 24 и 13 вместо 21). Для объяснения этого факта заметим, что для $d_{23} = 80$, $d_{21} = d_{12} = 4$ и $d_{13} = 65$ не выполняется неравенство треугольника: $80 > 4 + 65$. Чтобы его обеспечить, пришлось увеличить расстояние между точками 1 и 2 до 18.

В свою очередь, точки 4, 5 и 6 должны находиться на расстоянии примерно 65 от точки 3, при этом каждая из них должна быть (почти) равноудалена от точек 1 и 2. Это означает, что точки 4, 5 и 6 обязаны располагаться рядом, а именно — вблизи точки пересечения окружности с центром в 3 и радиусом 65 и серединного перпендикуляра к отрезку с концами в точках 1 и 2. Получаем противоречие с тем, что $d_{46} = 24$ и $d_{56} = 21$.

По формуле (14) подсчитана наименьшая аддитивная константа $\hat a = 11$, обеспечивающая выполнение неравенства треугольника для всех троек $d_{ij}' = d_{ij} + \hat a$ (это как раз $80 - 4 - 65$). Ей соответствует спектр $4958;\ 2094;\ 663;\ 190;\ -93{,}3;\ 0$. Здесь уже положительны $\mu_1$–$\mu_4$, а доля следа, приходящаяся на отрицательное собственное значение, уменьшилась с 3,5 % до 1,2 %.

Точки только слегка отдалились от начала координат, конфигурация качественно не изменилась. Однако на первые две оси теперь приходится всего 90,3 %, а не 97,3 % следа матрицы $\boldsymbol G^*$, как раньше: дисперсия «размазывается» по спектру. Это проявляется в плохом воспроизведении $d_{ij}'$ для признаков 4, 5 и 6. Преодолеть этот недостаток можно за счёт увеличения размерности $m$ до 3: третья координата как раз отвечает за разделение признака 6 и признаков 4 и 5. Соответствие пространственных расстояний и $d_{ij}'$ (за исключением пары 4–5) довольно хорошее.

Чтобы добиться неотрицательной определённости матрицы $\boldsymbol G^*$, понадобится увеличить аддитивную константу $a$ до 17. Спектр выглядит так: $5631;\ 2568;\ 904;\ 335;\ 7{,}3;\ 0$. При $m = 4$ все расстояния между точками (при округлении до ближайшего целого числа) совпадают с $d_{ij}' = d_{ij} + 17$.

Все эти числа виджет воспроизводит точно — нажимай кнопки «a = 0», «â = 11», «a = 17» и переключай $m$.

Смысл по-пацански: на карте признаков череп (1, 2, 3) и зубы (4, 5, 6) разъезжаются по разным углам, а ширина челюсти (3) вообще живёт отдельно. Это та же история, что рассказали главные компоненты в §1, только нарисованная по одной таблице корреляций.

Пример 4. Межотраслевые связи

Данные были взяты из книги известного американского экономиста А. Картера. Они представляют собой подсчитанные на основе межотраслевого баланса американской экономики коэффициенты прямых затрат $r_{ij}$, равные отношению затрат $i$-й отрасли на закупку продукции у $j$-й отрасли к общей величине затрат $i$-й отрасли. Симметризация $r_{ij}$ даёт в качестве мер близости $a_{ij} = r_{ij} + r_{ji}$. Переход от $a_{ij}$ к различиям $d_{ij}$ осуществлялся по формуле $d_{ij} = (\max a_{ij} - a_{ij})/(\max a_{ij} - \min a_{ij})$.

На полученной методом многомерного шкалирования карте (рис. 16 у Лагутина, сильные связи обозначены стрелками) видна структура экономики.

• Обеспечение первичными ресурсами ресурсоёмких отраслей. Аграрный, лесной и рыбный сектор (1) поставляет в пищевую (2), табачную (3) и текстильную (4) отрасли. Пищевая отрасль снабжает обувное производство (5), а продукция текстильной промышленности нужна при переработке металлолома (6).
• Металлургическая ветвь. Поставки чугуна и стали (7) идут в металлообрабатывающую промышленность (8), автомобильную промышленность (9), железнодорожный транспорт и суда (10) и переработку металлолома (6). Металлообработка отдаёт значительную часть продукции строительству (11), а оно вносит вклад в сектор недвижимости и помещений (12).
• Ещё две ветви: добыча руд цветных металлов (13) связана с обработкой цветных металлов (14), а нефтедобыча (15) — с нефтепереработкой (16).

Сами коэффициенты Картера в книге не приведены, поэтому здесь мы ограничиваемся описанием.

Проверь себя