Мажорування стресу

Мажорування стресу — це стратегія оптимізації, використовувана в багатовимірному шкалюванні, де для набору з n елементів розмірності m шукається конфігурація X n точок у r(<<m)-вимірному просторі, яка мінімізує так звану функцію мажорування ${\displaystyle \sigma (X)}$. Зазвичай r дорівнює 2 або 3, тобто (n x r) матриця X перераховує точки в 2- або 3-вимірному евклідовому просторі, так що результат можна відобразити візуально. Функція ${\displaystyle \sigma }$ є ціною або функцією втрат, яка вимірює квадрат різниці між ідеальною (${\displaystyle m}$-вимірною) відстанню і актуальною відстанню в r-вимірному просторі. Вона визначається як:

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

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

Конфігурація ${\displaystyle X}$, яка мінімізує ${\displaystyle \sigma (X)}$, дає графік, на якому близькі точки відповідають близьким точкам у початковому ${\displaystyle m}$-вимірному просторі.

Існує багато шляхів мінімізації ${\displaystyle \sigma (X)}$. Наприклад, Крускал рекомендує ітеративний підхід найшвидшого спуску. Однак істотно кращий (у термінах гарантованості і швидкості збіжності) метод мінімізації стресу запропонував Ян де Лейв. Метод ітеративного мажорування де Лейва на кожному кроці мінімізує просту опуклу функцію, яка обмежує ${\displaystyle \sigma }$ зверху і дотикається до поверхні ${\displaystyle \sigma }$ в точці ${\displaystyle Z}$, яку називають опорною точкою. В опуклому аналізі таку функцію називають мажорувальною функцією. Цей ітеративний процес мажорування також відомий як алгоритм SMACOF (англ. Scaling by MAjorizing a COmplicated Function).

Алгоритм SMACOF

Функцію стресу ${\displaystyle \sigma }$ можна розкласти так:

${\displaystyle \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)}$

Зауважимо, що перший член є константою ${\displaystyle C}$, а другий залежить квадратично від X (тобто для матриці Гесе V другий член еквівалентний tr${\displaystyle X'VX}$), а тому відносно просто обчислюється. Третій член обмежений величиною

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

де ${\displaystyle B(Z)}$ має елементи

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

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

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

Ця нерівність доводиться через нерівність Коші — Буняковського (див. статтю Борга).

Таким чином, ми маємо просту квадратичну функцію ${\displaystyle \tau (X,Z)}$, яка мажорує стрес:

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

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

Тоді ітеративна процедура мажорування робить таке:

• на кроці k ми приймаємо ${\displaystyle Z\leftarrow X^{k-1}}$
• ${\displaystyle X^{k}\leftarrow \min _{X}\tau (X,Z)}$
• зупиняємося, якщо ${\displaystyle \sigma (X^{k-1})-\sigma (X^{k})<\epsilon }$, в іншому випадку повертаємося на початок.

Показано, що цей алгоритм зменшує стрес монотонно (див. статтю де Лейва).

Використання у візуалізації графів

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

Примітки

1. Kruskal, 1964, с. 1–27.
2. de Leeuw, 1977, с. 133–145.
3. Borg, Groenen, 1997, с. 152–153.
4. Michailidis, de Leeuw, 2001, с. 435–450.
5. Gansner, Koren, North, 2004, с. 239–250.
6. 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.