Мажорирование стресса

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

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

,

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

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

Существует много путей минимизации $\sigma (X)$ . Например, Крускал[1] рекомендует итеративный подход кратчайшего спуска. Однако существенно лучший (в терминах гарантированности и скорости сходимости) метод минимизации стресса был предложен Яном де Лейвом[2][3]. Метод итеративной мажоризации де Лейва на каждом шаге минимизирует простую выпуклую функцию, которая ограничивает $\sigma$ сверху и касается поверхности $\sigma$ в точке $Z$ , которая называется опорной точкой. В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажоризации также упоминается как алгоритм SMACOF (англ. Scaling by MAjorizing a COmplicated Function).

Алгоритм SMACOF

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

\sigma (X)=\sum _{i<j\leqslant 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\geqslant \,\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}$ .

Данное неравенство доказывается через неравенство Коши — Буняковского, см. статью Борга[4].

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

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

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

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

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

Было показано, что этот алгоритм уменьшает стресс монотонно (см. статью де Лейва[3]).

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

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

Примечания

Kruskal, 1964, с. 1–27.
Имя нидерландское и родился он в Вубурге (Нидерланды), см. с таким же именем статью «Портрет Яна де Лейва».
de Leeuw, 1977, с. 133–145.
Borg, Groenen, 1997, с. 152–153.
Michailidis, de Leeuw, 2001, с. 435–450.
Gansner, Koren, North, 2004, с. 239–250.
Cohen, 1997, с. 197–229.

Литература

Kruskal J. B. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis // Psychometrika. — 1964. — Т. 29, вып. 1. — С. 1–27. — doi:10.1007/BF02289565.
de Leeuw J. Applications of convex analysis to multidimensional scaling // Recent developments in statistics / Barra J. R., Brodeau F., Romie G., van Cutsem B.. — 1977. — С. 133–145.
Borg I., Groenen P.,. Modern Multidimensional Scaling: theory and applications. — New York: Springer-Verlag, 1997.
Michailidis G., de Leeuw J. Data visualization through graph drawing // Computation Stat.. — 2001. — Т. 16, вып. 3. — С. 435–450. — doi:10.1007/s001800100077.
Gansner E., Koren Y., North S. Graph Drawing by Stress Majorization // Proceedings of 12th Int. Symp. Graph Drawing (GD'04). — Springer-Verlag, 2004. — Т. 3383. — С. 239–250. — (Lecture Notes in Computer Science).
Cohen J. Drawing graphs to convey proximity: an incremental arrangement method // ACM Transactions on Computer-Human Interaction. — 1997. — Т. 4, вып. 3. — С. 197–229. — doi:10.1145/264645.264657.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_ac4f295f7550fddb-1] Kruskal, 1964, с. 1–27.

[2] Имя нидерландское и родился он в Вубурге (Нидерланды), см. с таким же именем статью «Портрет Яна де Лейва».

[_c4a045f1b7b53784-3] Leeuw, 1977, с. 133–145.

[_5f28148d1a2c2b71-4] Borg, Groenen, 1997, с. 152–153.

[_c1c9e03f2f35d98f-5] Michailidis, de Leeuw, 2001, с. 435–450.

[_2f179ac1458a1331-6] Gansner, Koren, North, 2004, с. 239–250.

[_a2c1099cd1cb845f-7] Cohen, 1997, с. 197–229.