Мажорування стресу
Мажорування стресу — це стратегія оптимізації, використовувана в багатовимірному шкалюванні, де для набору з n елементів розмірності m шукається конфігурація X n точок у r(<<m)-вимірному просторі, яка мінімізує так звану функцію мажорування . Зазвичай r дорівнює 2 або 3, тобто (n x r) матриця X перераховує точки в 2- або 3-вимірному евклідовому просторі, так що результат можна відобразити візуально. Функція є ціною або функцією втрат, яка вимірює квадрат різниці між ідеальною (-вимірною) відстанню і актуальною відстанню в r-вимірному просторі. Вона визначається як:
- ,
де — вага для мір між парами точок , — евклідова відстань між і , а — ідеальна відстань між точками в -вимірному просторі. Зауважимо, що можна використати для задання ступеня довіри в схожості точок (наприклад, можна вказати 0, якщо для конкретної пари немає ніякої інформації).
Конфігурація , яка мінімізує , дає графік, на якому близькі точки відповідають близьким точкам у початковому -вимірному просторі.
Існує багато шляхів мінімізації . Наприклад, Крускал[1] рекомендує ітеративний підхід найшвидшого спуску. Однак істотно кращий (у термінах гарантованості і швидкості збіжності) метод мінімізації стресу запропонував Ян де Лейв[2]. Метод ітеративного мажорування де Лейва на кожному кроці мінімізує просту опуклу функцію, яка обмежує зверху і дотикається до поверхні в точці , яку називають опорною точкою. В опуклому аналізі таку функцію називають мажорувальною функцією. Цей ітеративний процес мажорування також відомий як алгоритм SMACOF (англ. Scaling by MAjorizing a COmplicated Function).
Функцію стресу можна розкласти так:
Зауважимо, що перший член є константою , а другий залежить квадратично від X (тобто для матриці Гесе V другий член еквівалентний tr), а тому відносно просто обчислюється. Третій член обмежений величиною
- ,
де має елементи
- для
для
.
Ця нерівність доводиться через нерівність Коші — Буняковського (див. статтю Борга[3]).
Таким чином, ми маємо просту квадратичну функцію , яка мажорує стрес:
Тоді ітеративна процедура мажорування робить таке:
- на кроці k ми приймаємо
- зупиняємося, якщо , в іншому випадку повертаємося на початок.
Показано, що цей алгоритм зменшує стрес монотонно (див. статтю де Лейва[2]).
Мажорування стресу і алгоритми, подібні SMACOF, застосовуються також у галузі візуалізації графів[4][5]. Тобто, завдякимінімізації функції стресу, можна знайти більш-менш естетичне розташування вершин для мережі або графа. В цьому випадку зазвичай береться як відстань (у сенсі теорії графів) між вузлами (вершинами) i і j, а ваги беруться рівними . Тут вибирається як компроміс між збереженням великих і малих ідеальних відстаней. Хороші результати отримано для [6].
- ↑ 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: .
- 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: .
- 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: .