Мажорирование стресса (Bg'kjnjkfguny vmjyvvg)

Перейти к навигации Перейти к поиску

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

,

где является весом для мер между парами точек , является евклидовым расстоянием между и , а является идеальным расстоянием между точками в -мерном пространстве. Заметим, что может быть использовано для спецификации степени доверия в похожести точек (например, можно указать 0, если нет никакой информации для конкретной пары).

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

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

Алгоритм SMACOF

[править | править код]

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

Заметим, что первый член является константой , а второй зависит квадратично от X (то есть для матрицы Гессе V второй член эквивалентен tr), а потому относительно прост в вычислениях. Третий же член ограничен величиной

,

где имеет элементы

для

для

.

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

Таким образом, мы имеем простую квадратичную функцию , которая мажорирует стресс:


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

  • на шаге k мы принимаем
  • останавливаемся, если , в противном случае возвращаемся в начало.

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

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

[править | править код]

Мажорирование стресса и алгоритмы, подобные SMACOF, имеют также приложение в области визуализации графов[5][6]. То есть можно найти более или менее эстетичное расположение вершин для сети или графа путём минимизации функции стресса. В этом случае обычно берётся как расстояние в смысле теории графов между узлами (вершинами) i и j, а веса берутся равными . Здесь выбирается как компромисс между сохранением длинных и коротких идеальных расстояний. Хорошие результаты были показаны для [7].

Примечания

[править | править код]
  1. Kruskal, 1964, с. 1–27.
  2. Имя нидерландское и родился он в Вубурге (Нидерланды), см. с таким же именем статью «Портрет Яна де Лейва».
  3. 1 2 de Leeuw, 1977, с. 133–145.
  4. Borg, Groenen, 1997, с. 152–153.
  5. Michailidis, de Leeuw, 2001, с. 435–450.
  6. Gansner, Koren, North, 2004, с. 239–250.
  7. 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.