ストレスのメジャー化

ストレスメジャー化は、多次元尺度構成法(MDS)で使用される最適化戦略であり、次元データ項目のセットに対して、いわゆるストレス関数を最小化する次元空間内の点の構成が求められます。通常はまたはです。つまり、行列は次元ユークリッド空間または次元ユークリッド空間内の点をリストし、結果を視覚化できるようにします ( MDS プロット)。関数は、理想的な ( 次元) 距離とr次元空間の実際の距離の差の二乗を測定するコスト関数または損失関数です。次のように定義されます。 ${\displaystyle n}$ ${\displaystyle m}$${\displaystyle X}$${\displaystyle n}$${\displaystyle r}$ ${\displaystyle (\ll m)}$${\displaystyle \sigma (X)}$${\displaystyle r}$${\displaystyle 2}$${\displaystyle 3}$${\displaystyle (n\times r)}$${\displaystyle X}$${\displaystyle 2-}$${\displaystyle 3-}$${\displaystyle \sigma}$${\displaystyle m}$

${\displaystyle \sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}}$

ここで、は 2 つのポイント間の測定の重み、はと間のユークリッド距離、 は次元データ空間におけるポイント間の理想的な距離 (ポイント間の距離) です。 を使用して、ポイント間の類似性の信頼度を指定できます (たとえば、特定のペアに関する情報がない場合は 0 を指定できます)。 ${\displaystyle w_{ij}\geq 0}$${\displaystyle (i,j)}$${\displaystyle d_{ij}(X)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \delta_{ij}}$${\displaystyle m}$${\displaystyle w_{ij}}$

を最小化する構成では、互いに近い点が元の - 次元データ空間内でも互いに近い点に対応するプロットが得られます。 ${\displaystyle X}$${\displaystyle \sigma (X)}$${\displaystyle m}$

を最小化する方法はたくさんあります。たとえば、Kruskal ^[1]は反復最急降下法を推奨しました。しかし、応力を最小化するためのはるかに優れた方法 (収束の保証と収束率の点で) がJan de Leeuwによって導入されました。^[2] De Leeuw の反復メジャー化法は、各ステップで、支持点と呼ばれる点で上から境界をなし、 の表面に触れる単純な凸関数を最小化します。凸解析では、このような関数はメジャー化関数と呼ばれます。この反復メジャー化プロセスは、SMACOF アルゴリズム (「複雑な関数をメジャー化することによってスケーリングする」) とも呼ばれます。 ${\displaystyle \sigma (X)}$${\displaystyle \sigma}$${\displaystyle \sigma}$${\displaystyle Z}$

ストレス関数は次のように拡張できます。 ${\displaystyle \sigma}$

${\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 番目の項は次のように制限されます。 ${\displaystyle C}$${\displaystyle X}$ ${\displaystyle V}$${\displaystyle X'VX}$

${\displaystyle \sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)=\,\オペレーター名 {tr} \,X'B(X)X\geq \,\オペレータ名 {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}}$

この不等式の証明はコーシー・シュワルツの不等式によって行われる。Borg ^[3] (pp. 152–153)を参照。

したがって、応力を主とする 単純な二次関数が得られます。${\displaystyle \tau (X,Z)}$

${\displaystyle \sigma (X)=C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(X)X}$

${\displaystyle \leq C+\,\オペレータ名 {tr} \,X'VX-2\,\オペレータ名 {tr} \,X'B(Z)Z=\tau (X,Z)}$

反復最小化手順は次のようになります。

• 私たちが設定したステップで${\displaystyle k^{th}}$${\displaystyle Z\leftarrow X^{k-1}}$
• ${\displaystyle X^{k}\leftarrow \min _{X}\tau (X,Z)}$
• それ以外の場合は停止し、繰り返します。${\displaystyle \sigma (X^{k-1})-\sigma (X^{k})<\epsilon }$

このアルゴリズムはストレスを単調に減少させることが示されている（de Leeuw ^[2]を参照）。

ストレスメジャー化とSMACOFに似たアルゴリズムは、グラフ描画の分野にも応用されています。^{[4] [5]}つまり、グラフ内のノードの位置に対するストレス関数を最小化することで、ネットワークまたはグラフの見た目に適度に魅力的なレイアウトを見つけることができます。この場合、 は通常、ノード間のグラフ理論的距離に設定され、重みはとされます。ここで、は長距離または短距離の理想距離を維持することのトレードオフとして選択されます。 に対して良い結果が示されています。^[6]${\displaystyle \delta _{ij}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle w_{ij}}$${\displaystyle \delta _{ij}^{-\alpha }}$${\displaystyle \alpha }$${\displaystyle \alpha =2}$