大容量データベースのデータマイニング手法
(積分型波形データの類似検索)
寶珍 輝尚
大阪府立大学 総合科学部 数理・情報科学科
(平成17年4月から理学系研究科 情報数理科学専攻)
背景
• 核融合科学の実験
– 膨大な量のデータが発生
– 膨大な数のデータが発生
• 効率の良いデータ管理が必要
• 類似データの発見 → 規則の発見(?)
目的
類似波形の的確かつ迅速な検索
• 対象データ
Bolometer計測データ
(放射熱量の計測)
積分型の波形
フーリエ変換を用いた検索方法
Davood Rafiei, Alberto Mendelzon(1999)
1. フーリエ変換
2. 最初の係数k個を使用(2個目以降は複素数)
3. 2k-1次元の点として多次元インデックス(R木)
で管理
4. 距離計算:ユークリッド距離
多次元インデックスR木
g
b d f
R1
a
Overlap
R3
h
e R2
c
R1R2R3
a b d
c
e
f g
Oid
data
10次元を超えると検索効率低下
h
問題点1
最初のk個(2k-1次元)の係数がほぼ同じでも
波形が異なるデータが存在
例)インデックス5次元、データ数1000
検索キー:No094
距離が最も近いデータ:No029
検索精度の改良
2段階の処理
・1段階目:R木を使用(2k-1次元)
足切りに利用
・2段階目:波形の類似度を判定
値の大きいm個の係数
を使用(最初の2k-1以外)
次元数(2k-1)の選定
計測データ1000個の係数の平均
k
1
実部 2059
虚部
0
2
3
4
5
6
7
8
-7
-12
-9
-6
-4
-14
-14
-4
0
1
1
k:2から4(2k-1:3,5,7)で
大まかな波形の類似度が判断可能
mの選定
値の大きい係数の個数m:実験的に選定
・k:2~4(2k-1:3,5,7)
・m:2,4,6,8
・データ数:1000
・検索キー:2個(波形が大きく異なる)
・類似データ:4個(あらかじめ選定) データ
A
・順位の平均で評価
B
(同距離のもの:同順位)
C
D
距 順
離 位
2
1
3
2
3
2
4
4
mの選定
7
6
平均順位
5
4
3
2
3次元
5次元
7次元
1
0
m=2
m=4
m=6
m=8
5次元インデックス(k=3)、m=4の時
最も精度が良い
検索例
検索キー:No325
②No332
①No329
③No321
問題点2
• 周波数領域への変換法:
キー波形の波長が支配的
• 多少異なる波長の波形も検索したい
近似
• 仮定
– g(t)=f(t/(1+α)) ただし、α<<1
– t=0 以前で 0
– t=t1 以降で 0
• G(ω)≒F(ω)exp(- jαω t1)
– G(ω) :g(t) のフーリエ変換
– F(ω) :f(t) のフーリエ変換
検索法
• 角度法
– 少しずつ角度を変化
• 貪欲法
– 最初は検索範囲を大きくし絞り込む
• 対角法
– 対角のみ
原検索範囲
小領域
評価
時間 [sec]
• 対象:1000個のボロメータ計測データ
• 角度αの増加量を変化させて測定
35
30
25
20
15
10
5
0
angle
heavy-eat
diag3
diag5
0
0.02
0.04
0.06
0.08
角度増分 [deg]
0.1
0.12
まとめ
• 波形の高速類似検索(FFT利用)
– 1段階目:R木による検索(5次元インデックス)
– 2段階目:係数4個を使用(1段階目で使用の係数以外)
• 波長の多少異なる波形も検索(近似)
今後の課題
• 他の積分型波形への適用
• 揺動型波形に対する検討
ダウンロード

宝珍輝尚