Стресс-мажоризация

Мажоризация напряжений — это стратегия оптимизации, используемая в многомерном масштабировании (MDS), где для набора $n$ $m$-мерные элементы данных, конфигурация $X$ из $n$ указывает на $r$ $(\ll m)$ищется -мерное пространство, минимизирующее так называемую напряжения функцию $\sigma (X)$. Обычно $r$ является $2$ или $3$, то есть $(n\times r)$ матрица $X$ перечисляет точки в $2-$ или $3-$многомерное евклидово пространство , чтобы результат можно было визуализировать (т. е. график MDS ). Функция $\sigma$ — это функция затрат или потерь , которая измеряет квадрат разницы между идеальными ( $m$-мерные) расстояния и реальные расстояния в r -мерном пространстве. Он определяется как:

$\sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}$

где $w_{ij}\geq 0$ это вес для измерения между парой точек $(i,j)$, $d_{ij}(X)$ это евклидово расстояние между $i$ и $j$ и $\delta _{ij}$ – идеальное расстояние между точками (их разделение) в $m$-мерное пространство данных. Обратите внимание, что $w_{ij}$ может использоваться для указания степени уверенности в сходстве между точками (например, можно указать 0, если для конкретной пары нет информации).

Конфигурация $X$ что сводит к минимуму $\sigma (X)$ дает график, на котором точки, находящиеся близко друг к другу, соответствуют точкам, также близким друг к другу в оригинале $m$-мерное пространство данных.

Есть много способов, которые $\sigma (X)$ можно было бы свести к минимуму. Например, Крускал рекомендовал итеративный подход наискорейшего спуска . Однако значительно лучший (с точки зрения гарантий и скорости сходимости) метод минимизации стресса был предложен Яном де Леу . Де Леу Итеративный метод мажорирования на каждом этапе минимизирует простую выпуклую функцию, которая одновременно ограничивает $\sigma$ сверху и касается поверхности $\sigma$ в какой-то момент $Z$, называемая опорной точкой . В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажорирования также называется алгоритмом SMACOF («Масштабирование путем MAjorizing сложной функции»).

Алгоритм SMACOF

Функция стресса $\sigma$ можно расширить следующим образом:

$\sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}=\sum _{i<j}w_{ij}\delta _{ij}^{2}+\sum _{i<j}w_{ij}d_{ij}^{2}(X)-2\sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)$

Обратите внимание, что первый член является константой $C$ а второй член квадратичен по $X$ (т.е. для матрицы Гессе $V$ второй член эквивалентен tr $X'VX$) и поэтому относительно легко решается. Третий член ограничен:

$\sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)=\,\operatorname {tr} \,X'B(X)X\geq \,\operatorname {tr} \,X'B(Z)Z$

где $B(Z)$ имеет:

$b_{ij}=-{\frac {w_{ij}\delta _{ij}}{d_{ij}(Z)}}$ для $d_{ij}(Z)\neq 0,i\neq j$

и $b_{ij}=0$ для $d_{ij}(Z)=0,i\neq j$

и $b_{ii}=-\sum _{j=1,j\neq i}^{n}b_{ij}$.

Доказательством этого неравенства является неравенство Коши-Шварца , см. Борг. (стр. 152–153).

Таким образом, мы имеем простую квадратичную функцию $\tau (X,Z)$ который мажорирует стресс:

$\sigma (X)=C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(X)X$

$\leq C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(Z)Z=\tau (X,Z)$

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

• в $k^{th}$ шаг, который мы установили $Z\leftarrow X^{k-1}$
• $X^{k}\leftarrow \min _{X}\tau (X,Z)$
• остановись, если $\sigma (X^{k-1})-\sigma (X^{k})<\epsilon$ в противном случае повторите.

Было показано, что этот алгоритм монотонно уменьшает напряжение (см. de Leeuw ).

Использование в рисовании графиков

Мажорирование напряжений и алгоритмы, подобные SMACOF, также имеют применение в области рисования графов . То есть можно найти достаточно эстетически привлекательную компоновку сети или графа, минимизируя функцию напряжения в положениях узлов графа. В этом случае $\delta _{ij}$ обычно устанавливаются на теоретико-графовые расстояния между узлами $i$ и $j$ и веса $w_{ij}$ считаются $\delta _{ij}^{-\alpha }$. Здесь, $\alpha$ выбирается как компромисс между сохранением идеальных расстояний на большие или короткие расстояния. Хорошие результаты были показаны для $\alpha =2$.