Меню Главная Случайная статья Настройки Мажорирование стресса Материал из https://ru.wikipedia.org Мажорирование стресса — это стратегия оптимизации, используемая в многомерном шкалировании, где для набора из 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)}$. Например, Крускал[1] рекомендует итеративный подход кратчайшего спуска. Однако существенно лучший (в терминах гарантированности и скорости сходимости) метод минимизации стресса был предложен Яном де Лейвом[2][3]. Метод итеративной мажоризации де Лейва на каждом шаге минимизирует простую выпуклую функцию, которая ограничивает ${\displaystyle \sigma }$ сверху и касается поверхности ${\displaystyle \sigma }$ в точке ${\displaystyle Z}$, которая называется опорной точкой. В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажоризации также упоминается как алгоритм SMACOF (англ. Scaling by MAjorizing a COmplicated Function). Содержание 1 Алгоритм SMACOF 2 Использование в визуализации графов 3 Примечания 4 Литература Алгоритм 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}}$. Данное неравенство доказывается через неравенство Коши — Буняковского, см. статью Борга[4]. Таким образом, мы имеем простую квадратичную функцию ${\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 }$, в противном случае возвращаемся в начало. Было показано, что этот алгоритм уменьшает стресс монотонно (см. статью де Лейва[3]). Использование в визуализации графов Мажорирование стресса и алгоритмы, подобные SMACOF, имеют также приложение в области визуализации графов[5][6]. То есть можно найти более или менее эстетичное расположение вершин для сети или графа путём минимизации функции стресса. В этом случае ${\displaystyle \delta _{ij}}$ обычно берётся как расстояние в смысле теории графов между узлами (вершинами) i и j, а веса ${\displaystyle w_{ij}}$ берутся равными ${\displaystyle \delta _{ij}^{-\alpha }}$. Здесь ${\displaystyle \alpha }$ выбирается как компромисс между сохранением длинных и коротких идеальных расстояний. Хорошие результаты были показаны для ${\displaystyle \alpha =2}$[7]. Примечания Kruskal, 1964, с. 1–27. Имя нидерландское и родился он в Вубурге (Нидерланды), см. с таким же именем статью «Портрет Яна де Лейва». 1 2 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. Michailidis G., de Leeuw J. Data visualization through graph drawing // Computation Stat.. — 2001. — Т. 16, вып. 3. — С. 435–450. — doi:10.1007/s001800100077. 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.