Geometric placement based on ideal distances
ストレス・マジョライゼーションは、 多次元尺度法 （MDS）において用いられる 最適化戦略 であり 、次元データ項目の集合に対して、 いわゆる ストレス 関数を最小化する次元空間 における点 の 配置が求められる 。通常 は または で あり、つまり 行列は 次元ユークリッド空間 または 次元 ユークリッド空間 内の点をリストし 、結果を視覚化（ MDSプロット ）できるようにする。関数 は、 r 次元空間における理想的な（ 次元）距離と実際の距離 の二乗差を測定する コスト関数または 損失関数 である。これは以下のように定義される。 n {\displaystyle n} m {\displaystyle m} X {\displaystyle X} n {\displaystyle n} r {\displaystyle r} ( ≪ m ) {\displaystyle (\ll m)} σ ( X ) {\displaystyle \sigma (X)} r {\displaystyle r} 2 {\displaystyle 2} 3 {\displaystyle 3} ( n × r ) {\displaystyle (n\times r)} X {\displaystyle X} 2 − {\displaystyle 2-} 3 − {\displaystyle 3-} σ {\displaystyle \sigma } m {\displaystyle m}
σ ( X ) = ∑ i < j ≤ n w i j ( d i j ( X ) − δ i j ) 2 {\displaystyle \sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}} ここで 、は2点間の測定の重み 、 はと 間の ユークリッド距離 、は 次元データ空間 における点間の理想的な距離（間隔） です。は 、点間の類似性の信頼度を指定するために使用できます（例えば、特定の点間の情報がない場合、0を指定できます）。 w i j ≥ 0 {\displaystyle w_{ij}\geq 0} ( i , j ) {\displaystyle (i,j)} d i j ( X ) {\displaystyle d_{ij}(X)} i {\displaystyle i} j {\displaystyle j} δ i j {\displaystyle \delta _{ij}} m {\displaystyle m} w i j {\displaystyle w_{ij}}
を最小化する 構成で は、互いに近い点が元の - 次元データ空間内でも互いに近い点に対応するプロットが得られます 。 X {\displaystyle X} σ ( X ) {\displaystyle \sigma (X)} m {\displaystyle m}
を最小化する方法はたくさんあります 。例えば、Kruskal [1] は反復 最急降下法を推奨しました。しかし、 Jan de Leeuw [2] は、応力を最小化するためのはるかに優れた（収束の保証と収束速度の点で）手法を導入しました。De Leeuw の 反復的マジョライゼーション 法は、各ステップにおいて、 支持点 と呼ばれる 点で の表面に接し、かつ上から 境界をなす単純な 凸関数 を最小化します。 凸解析 では、このような関数は マジョライゼーション 関数と呼ばれます。この反復的マジョライゼーション処理は、SMACOFアルゴリズム（「複雑な関数をMAjorizingすることでスケーリングする」）とも呼ばれます。 σ ( X ) {\displaystyle \sigma (X)} σ {\displaystyle \sigma } σ {\displaystyle \sigma } Z {\displaystyle Z}
SMACOFアルゴリズム ストレス関数は 次のように拡張できます。 σ {\displaystyle \sigma }
σ ( X ) = ∑ i < j ≤ n w i j ( d i j ( X ) − δ i j ) 2 = ∑ i < j w i j δ i j 2 + ∑ i < j w i j d i j 2 ( X ) − 2 ∑ i < j w i j δ i j d i j ( X ) {\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)} 最初の項は定数であり 、2番目の項は の2次項である （つまり、 ヘッセ行列の場合、2番目の項は tr と等しい ）ため、比較的簡単に解けることに注意してください。3番目の項は次のように定義されます。 C {\displaystyle C} X {\displaystyle X} V {\displaystyle V} X ′ V X {\displaystyle X'VX}
∑ i < j w i j δ i j d i j ( X ) = tr X ′ B ( X ) X ≥ tr X ′ B ( Z ) Z {\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}}
この不等式の証明は コーシー・シュワルツの 不等式によって行われます。Borg [3] (pp. 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}
参考文献 ^ Kruskal, JB (1964)、「非計量仮説への適合度の最適化による多次元尺度構成法」 Psychometrika 、 29 (1): 1–27 、 doi :10.1007/BF02289565 。 ^ ab de Leeuw, J. (1977)、「凸解析の多次元尺度構成法への応用」、Barra, JR; Brodeau, F.; Romie, G.; et al. (eds.)、 統計学の最近の発展 、pp. 133– 145 。 ^ Borg, I.; Groenen, P. (1997), Modern Multidimensional Scaling: theory and applications , New York: Springer-Verlag 。 ^ Michailidis, G.; de Leeuw, J. (2001)、「グラフ描画によるデータの視覚化」、 Computation Stat. 、 16 (3): 435– 450、 CiteSeerX 10.1.1.28.9372 、 doi :10.1007/s001800100077 。 ^ Gansner, E.; Koren, Y.; North, S. (2004)、「ストレス・マジョライゼーションによるグラフ描画」、 第12回国際グラフ描画シンポジウム(GD'04)の議事録 、コンピュータサイエンス講義ノート、第3383巻、Springer-Verlag、pp. 239– 250 。 ^ Cohen, J. (1997)、「近接性を伝えるグラフ描画：増分配置法」、 ACM Transactions on Computer-Human Interaction 、 4 (3): 197– 229、 doi :10.1145/264645.264657 。 
