Мажорирование стресса
Геометрическое размещение на основе идеальных расстояний

Мажорирование стресса — это стратегия оптимизации, используемая в многомерном шкалировании (MDS), где для набора -мерных элементов данных ищется конфигурация точек в -мерном пространстве, которая минимизирует так называемую функцию стресса . Обычно это или , т. е. матрица перечисляет точки в или -мерном евклидовом пространстве, так что результат может быть визуализирован (т. е. график MDS ). Функция представляет собой функцию стоимости или потерь , которая измеряет квадраты разностей между идеальными ( -мерными) расстояниями и фактическими расстояниями в r -мерном пространстве. Она определяется как: н {\displaystyle n} м {\displaystyle м} Х {\displaystyle X} н {\displaystyle n} г {\displaystyle r} ( ≪ м ) {\displaystyle (\ll м)} σ ( Х ) {\displaystyle \сигма (X)} г {\displaystyle r} 2 {\displaystyle 2} 3 {\displaystyle 3} ( н × г ) {\displaystyle (n\times r)} Х {\displaystyle X} 2 − {\displaystyle 2-} 3 − {\displaystyle 3-} σ {\displaystyle \сигма} м {\displaystyle м}

σ ( Х ) = ∑ я < дж ≤ н ж я дж ( г я дж ( Х ) − δ я дж ) 2 {\displaystyle \sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}}

где — вес для измерения между парой точек , — евклидово расстояние между и и — идеальное расстояние между точками (их разделение) в -мерном пространстве данных. Обратите внимание, что можно использовать для указания степени уверенности в сходстве между точками (например, можно указать 0, если для конкретной пары нет информации). ж я дж ≥ 0 {\displaystyle w_{ij}\geq 0} ( я , дж ) {\displaystyle (я,j)} г я дж ( Х ) {\displaystyle d_{ij}(X)} я {\displaystyle я} дж {\displaystyle j} δ я дж {\displaystyle \delta _{ij}} м {\displaystyle м} ж я дж {\displaystyle w_{ij}}

Конфигурация , которая минимизирует, дает график, на котором точки, расположенные близко друг к другу, соответствуют точкам, которые также расположены близко друг к другу в исходном -мерном пространстве данных. Х {\displaystyle X} σ ( Х ) {\displaystyle \сигма (X)} м {\displaystyle м}

Существует много способов минимизации. Например, Крускаль [1] рекомендовал итеративный подход наискорейшего спуска . Однако значительно лучший (с точки зрения гарантий и скорости сходимости) метод минимизации напряжения был предложен Яном де Леу . [2] Итеративный метод мажорирования Де Леу на каждом шаге минимизирует простую выпуклую функцию, которая одновременно ограничивает сверху и касается поверхности в точке , называемой опорной точкой . В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажорирования также называется алгоритмом SMACOF («Scaling by MAjorizing a COmplicated Function»). σ ( Х ) {\displaystyle \сигма (X)} σ {\displaystyle \сигма} σ {\displaystyle \сигма} З {\displaystyle Z}

Алгоритм SMACOF

Функцию напряжения можно разложить следующим образом: σ {\displaystyle \сигма}

σ ( Х ) = ∑ я < дж ≤ н ж я дж ( г я дж ( Х ) − δ я дж ) 2 = ∑ я < дж ж я дж δ я дж 2 + ∑ я < дж ж я дж г я дж 2 ( Х ) − 2 ∑ я < дж ж я дж δ я дж г я дж ( Х ) {\displaystyle \sigma (X)=\sum _{i<j\leq 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)}

Обратите внимание, что первый член является константой , а второй член является квадратичным по (т.е. для матрицы Гессе второй член эквивалентен tr ) и поэтому относительно легко решается. Третий член ограничен: С {\displaystyle С} Х {\displaystyle X} В {\displaystyle V} Х ′ В Х {\displaystyle X'VX}

∑ я < дж ж я дж δ я дж г я дж ( Х ) = тр Х ′ Б ( Х ) Х ≥ тр Х ′ Б ( З ) З {\displaystyle \sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)=\,\operatorname {tr} \,X'B(X)X\geq \,\operatorname {tr} \,X'B(Z)Z}

где есть: B ( Z ) {\displaystyle B(Z)}

b i j = − w i j δ i j d i j ( Z ) {\displaystyle b_{ij}=-{\frac {w_{ij}\delta _{ij}}{d_{ij}(Z)}}} для d i j ( Z ) ≠ 0 , i ≠ j {\displaystyle d_{ij}(Z)\neq 0,i\neq j}

и для b i j = 0 {\displaystyle b_{ij}=0} d i j ( Z ) = 0 , i ≠ j {\displaystyle d_{ij}(Z)=0,i\neq j}

и . b i i = − ∑ j = 1 , j ≠ i n b i j {\displaystyle b_{ii}=-\sum _{j=1,j\neq i}^{n}b_{ij}}

Доказательство этого неравенства основано на неравенстве Коши-Шварца , см. Борг [3] (стр. 152–153).

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

σ ( X ) = C + tr X ′ V X − 2 tr X ′ B ( X ) X {\displaystyle \sigma (X)=C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(X)X}
≤ C + tr X ′ V X − 2 tr X ′ B ( Z ) Z = τ ( X , Z ) {\displaystyle \leq C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(Z)Z=\tau (X,Z)}


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

  • на шаге, который мы установили k t h {\displaystyle k^{th}} Z ← X k − 1 {\displaystyle Z\leftarrow X^{k-1}}
  • X k ← min X τ ( X , Z ) {\displaystyle X^{k}\leftarrow \min _{X}\tau (X,Z)}
  • остановитесь, в противном случае повторите. σ ( X k − 1 ) − σ ( X k ) < ϵ {\displaystyle \sigma (X^{k-1})-\sigma (X^{k})<\epsilon }

Было показано, что этот алгоритм монотонно снижает стресс (см. de Leeuw [2] ).

Использование при построении графиков

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

Ссылки

  1. ^ Kruskal, JB (1964), «Многомерное шкалирование путем оптимизации качества соответствия неметрической гипотезе», Psychometrika , 29 (1): 1– 27, doi :10.1007/BF02289565.
  2. ^ ab de Leeuw, J. (1977), «Применение выпуклого анализа к многомерному шкалированию», в Barra, JR; Brodeau, F.; Romie, G.; et al. (ред.), Последние разработки в статистике , стр.  133–145.
  3. ^ Борг, И.; Гроенен, П. (1997), Современное многомерное шкалирование: теория и приложения , Нью-Йорк: Springer-Verlag.
  4. ^ Michailidis, G.; de Leeuw, J. (2001), «Визуализация данных с помощью графического рисунка», Computation Stat. , 16 (3): 435–450 , CiteSeerX 10.1.1.28.9372 , doi :10.1007/s001800100077 .
  5. ^ Ганснер, Э.; Корен, Ю.; Норт, С. (2004), «Построение графиков методом мажорирования напряжений», Труды 12-го Международного симпозиума по построению графиков (GD'04) , Конспект лекций по информатике, том 3383, Springer-Verlag, стр.  239–250.
  6. ^ Коэн, Дж. (1997), «Рисование графиков для передачи близости: метод инкрементального расположения», ACM Transactions on Computer-Human Interaction , 4 (3): 197–229 , doi :10.1145/264645.264657.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Stress_majorization&oldid=1093860243"