* FastMap [#gcb6102e]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

次元削減手法の一つ.
削減後の次元数を \(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\)回繰り返せば次元削減ができる.
これには,この部分空間中での距離が必要になるが,これも簡単な幾何的関係から計算できる点がポイント.

> -- しましま

** 関連項目 [#s6306378]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[次元削減]]
#br
-[[検索:FastMap]]

** リンク集 [#o7b4f2c9]

//関連するWWW資源があればリンクしてください.

** 関連文献 [#he73c496]

//この%項目%に関連する書籍や論文を紹介してください.

-基本文献~
C.Faloutsos and K.-I.Lin, "FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets", SIGMOD (1995)~
[[GoogleScholarAll:FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets]]

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS