シグネチャを用いた類似検索
シグネチャを用いた類似検索
- シグネチャ
- 個々のデータオブジェクトから生成される固定ビット列であり,オブジェクトの特徴量を表現するものである.(http://www.ieice.org/iss/de/DEWS/proc/2004/paper/1-C/1-C-01.pdf)
- シグネチャって概念はなんかの特徴を現したものみたいな?
- 特徴空間みたいなもんだろう
スペクトルシグネチャ
問題:R木は15次元以上の空間では性能が下がる
解決法:個々のシークエンスから低い次元のシグネチャを取り出し,シグネチャスペースにインデックスする
- 類似性を判定する方法
- 時系列を時間軸上で考える方法
- 時系列を周波数領域に変換して考える方法
- efficient similarity search in sequence database
- 時系列を周波数領域に変換して考える方法を使ってる
- 離散フーリエ変換(Discrete Fourier Transform; DFT)を使ってるらしい.
- DFT とは系列の時間領域から周波数領域への変換
- 空間アクセス法
- R木
- B木に似た木構造のデータ構造であり、多次元情報(例えば、二次元座標データなど)のインデックス付け、すなわち空間インデックスに使われる。
- それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。
- http://ja.wikipedia.org/wiki/R%E6%9C%A8
- F-index
- k次元空間の展集合の空間索引(R木とかR*木を利用)
- ST-index
- 時系列Siを長さwの部分系列に(重複を許して)分割
- 長さwの各部分系列をw点DFT変換
- w点DFTの係数k個を特徴関数値として利用
- 時系列Siは特徴空間上でtrail(小径)として表現される
- trailの各点をすべて記憶(R*木などを利用)
- MBR
- (Minimum Bounding Rectangle = 最小外接矩形)または Envelope。
- これは境界ジオメトリであり、最小と最大(X,Y)の座標で形成される。
- 要するにR木で使ってる長方形