- 追加された行はこの色です。
- 削除された行はこの色です。
- FastMap へ行く。
* 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]]