FastMap

次元削減手法の一つ. 削減後の次元数を \(K\),データ数を \(N\) としたとき,主成分分析多次元尺度構成法は \(O(N^2K)\) の計算量が必要.これを,削減による歪みは大きくなるが,計算量は \(O(NK)\) で抑えられる

オリジナルのデータを \(\mathbf{x}_i^{(0)}\) とする. 第\(k-1\)次元目までの座標値が計算済みのとき,第\(k\)次元目の座標値を求める.

二つの十分に離れた二つのデータ点 \(\mathbf{x}_a^{(k-1)}\) と \(\mathbf{x}_b^{(k-1)}\) を選ぶ. それ以外の点 \(\mathbf{x}_i^{(k-1)}\) は,\(\mathbf{x}_a^{(k-1)}\) と \(\mathbf{x}_b^{(k-1)}\) を結ぶ直線に垂直に射影し,その垂線の足と \(\mathbf{x}_a^{(k-1)}\) の間の距離を,\(k\)次元目での座標値 \(\mathbf{x}_i^{(k)}\) とする.

\(\mathbf{x}_a^{(k-1)}\) と \(\mathbf{x}_b^{(k-1)}\) に垂直な,\(N-k\)次元の部分空間中で,再度この手続きを\(K\)回繰り返せば次元削減ができる. これには,この部分空間中での距離が必要になるが,これも簡単な幾何的関係から計算できる点がポイント.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-08-10 (水) 23:09:04