![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
\(n\)個の点の間の類似度が与えられたとき，類似度の高い点を近くに，低い点を遠くに配置する方法．
点\(i,j,\;i,j=1\ldots,n,\,i\ne j\)の間の類似度を\(e_{ij}\)とする．ただし，類似度は対称 \(e_{ij}=e_{ji}\) とする．もし対称でない類似度\({e'}_{ij}\) は \(e_{ij}=e_{ji}=({e'}_{ij}+{e'}_{ji})/2\) などとして対称化すればよい．
点iをk次元ベクトル \(\mathbf{x}_i=(x_{i1},\ldots,x_{ik})\) に配置する． このとき，\(\sum_{i=1}^n\sum_{j=1}^k {x_{ij}}^2\) が一定との制約のもと次式を最大化するように \(\mathbf{x}_1,\ldots,\mathbf{x}_n\) を定める． \[\sum_{i=1}^n\sum_{j\gt i}(-e_{ij})||\mathbf{x}_i-\mathbf{x}_j||^2\] ただし，\(||\cdot||\) はEuclidノルム．
解を求めるにはまず，対角要素が \(h_{ii}=-\sum_{j=1}^n e_{ij}\) で，他は \(h_{ij}=e_{ij}\) であるような行列 \(H\) を生成． この行列の上位k個の固有値と，それに対する固有ベクトルを求める． すると\(\mathbf{x}_i\) は，k個の固有ベクトルのi番目の要素を取り出したものになる．
-- しましま
