大容量データベースのデータマイニング手法 （積分型波形データの類似検索）

Presentation on theme: "大容量データベースのデータマイニング手法 （積分型波形データの類似検索）"— Presentation transcript:

1 大容量データベースのデータマイニング手法 （積分型波形データの類似検索）
寶珍　輝尚 大阪府立大学 総合科学部 数理・情報科学科 （平成１７年４月から理学系研究科 情報数理科学専攻）

2 背景 核融合科学の実験 効率の良いデータ管理が必要 類似データの発見 → 規則の発見（？） 膨大な量のデータが発生 膨大な数のデータが発生
類似データの発見　→　規則の発見（？） まず背景としまして、 核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている

3 目的 類似波形の的確かつ迅速な検索 対象データ Bolometer計測データ （放射熱量の計測） 積分型の波形 まず背景としまして、
　　（放射熱量の計測） 　　積分型の波形 まず背景としまして、 核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている

4 フーリエ変換を用いた検索方法 Davood Rafiei, Alberto Mendelzon(1999) 1. フーリエ変換
1.　フーリエ変換 2.　最初の係数k個を使用（2個目以降は複素数） 3.　2k-1次元の点として多次元インデックス（R木）で管理 4.　距離計算：ユークリッド距離 今までに考えられている 時系列データの類似検索の方法として、 フーリエ変換を用いた検索があります。 この方法は、 まずデータにフーリエ変換を行い、 最初の係数ｋ個を使用します。 ２個目以降の係数が複素数になるため、 2k-1次元の点として多次元インデックスであるR木によって 管理します。 また、距離計算にはユークリッドの距離を用います。

5 多次元インデックスR木 10次元を超えると検索効率低下 data a d c e b R1 R2 g f h R3 Overlap
R1R2R3 a b d f g h c e data Oid 次に多次元インデックスであるR木について説明します。 まずR木は、外接矩形を作成しながら 木を構築していきます。 丸で囲まれたa～hがデータで、このように存在しているとします。 まずa,b,c・・・・hに外接する矩形を作り、 それらが、木の構造でいうと下位ノードのこれらになります。 その次に近い矩形同士で外接矩形を作成します。 a,b,dが近い矩形なので、 それらを囲む外接矩形R1を作成します。 木の構造で言うと a,b,dの上位ノードにR１があると言ったようにです。 またｃ,eの上位ノードにR2があり、 f,g,hの上位ノードにR3があるといったようになります。 そして、検索は問い合わせで指定された領域と 重なる領域を再帰的に検索していきます。 またR1とR２の重なりは、オーバラップといい、 検索効率の低下を起こします。 また実験的な研究により、10次元を超えると 検索効率が低下する場合があると わかっています。 次元の呪い ある問い合わせから最も近い点と最も遠い点との 距離の差があまりなくなっていまい、 検索範囲の設定が困難。 ある範囲では1000個ちかく取れる場合でも、 すこし範囲を下げたら全く取れなくなってしまったりする。 10次元を超えると検索効率低下

6 問題点１ 最初のk個（2k-1次元）の係数がほぼ同じでも 波形が異なるデータが存在 例）インデックス5次元、データ数1000
検索キー：No094 距離が最も近いデータ：No029 フーリエ変換を用いた検索方法での問題点として、 最初の2k-1個の係数がほぼ同じでも、 波形が異なるデータが存在してしまうことがあります。 例えば、インデックスを5次元、データ数を1000個として、 左の図のNo.094というキーで検索した場合、 右のNo029というデータが得られます。 波形を見比べてみると、あまり似ていないように思えます。 （そこで、最初の2k-1次元の係数以外にも、 特徴となる係数があるのではないかと考えました。）

7 検索精度の改良 2段階の処理 ・1段階目：R木を使用（2k-1次元） 足切りに利用 ・2段階目：波形の類似度を判定 値の大きいm個の係数
　　　　　　　足切りに利用 ・2段階目：波形の類似度を判定 　　　　　　 値の大きいm個の係数 　を使用（最初の2k-1以外） そこで、2段階の処理を行うことを考えました。 まず1段階目では、2k-1次元のR木を使用し、 足切りを行います。 次に2段階目で、波形の類似度を判定します。 2段階目では、1段階目で使う2k-1個以外の係数のうち 値の大きい係数をm個使用して、距離を比較します。 同じ位置に大きい値があるなら、 その値同士で引くのですが。 同じ場所に大きい値がなければ、 キーの値から、０を引きます。

8 次元数（2k-1）の選定 計測データ1000個の係数の平均 k：2から4（2k-1：3,5,7）で 大まかな波形の類似度が判断可能 k １
　計測データ1000個の係数の平均 k １ ２ ３ ４ ５ ６ ７ 実部 2059 8 -7 -12 -9 -6 -4 虚部 -14 1 まず、2k－1次元をいくつにするかと いうことを考えました。 この表は計測データ1000個の係数を平均したもので、 次数の低い係数です。 この表を見ると、 実部と虚部がともに大きいので、 ｋが２～４つまり、2k－1が３から７で 大まかな波形の類似度を判断できるのではないかと考えました。 k：2から4（2k-1：3,5,7）で 大まかな波形の類似度が判断可能

9 mの選定 値の大きい係数の個数m：実験的に選定 ・データ数:1000 ・k：2~4（2k-1：3，5，7） ・m：2，4，6，8
・検索キー：2個（波形が大きく異なる） ・類似データ：4個（あらかじめ選定） ・順位の平均で評価 （同距離のもの：同順位） データ 距離 順位 A ２ １ B ３ C D ４ 次にｍをいくつにするかということを考えました。 ｋが２～４つまり、2k－1が３、５、７に対して、 mを２，４，６，８と変えていき、 もっとも精度の良いｋとｍの組み合わせを選ぶことにしました。 方法としては、データ数を1000個の中から、 波形が大きく異なるデータを2個検索キーとして選びます。 そしてあらかじめ、そのキーに似たデータを4個選んでおきます。 あらかじめ選んでおいたデータが 何番目に現れるかという順位の平均で、評価します。 ただし、同じ距離のものは順位を同じにしています。 例えば、右下の例で説明すると、 ある検索キーに対して、 あらかじめ選んでおいたデータA,B,C,Dが この距離ので上から順に得られたとすると、 その順序はこのようになります。 これと同じことを別のキーに対しても行い、 二つの平均を取ったものが、次のグラフです。 1つのキーに対して、距離が遠くなるものを選んだ

10 mの選定 5次元インデックス（k=3）、m=4の時 最も精度が良い 横軸がｍの個数で、縦軸が平均順位となっています。
またこれが３次元、これが５次元、これが７次元の 波形に結果になります。 これは、似ている4個のデータの順位の平均なので、 グラフで下のほうに行くほど、似たデータが上位にあるということです。 このグラフを見ると、5次元(kが３）でｍ＝４のときに 最も精度が良いので、この方法に決定しました。 k=3、m=4のときの平均順位が2.5 k=3、m=2のときの平均順位が2.6 7次元で検索効率が低下している。 これはあまり重要でない係数を取ってしまっていると 考えられます。 ので、9次元でｍを変化させても、 7次元と同様に重要でない係数をとってしまうと思い、 やっていません。 5次元インデックス（k=3）、m=4の時 最も精度が良い

11 検索例 検索キー：No325 ①No329 ②No332 ③No321 検索例として、
右上の波形が最も距離が近かったデータです。 下2つの波形がその次に近かったデータです。 似ているデータを得られていることがわかると思います。

12 問題点２ 周波数領域への変換法： キー波形の波長が支配的 多少異なる波長の波形も検索したい まず背景としまして、
核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている

13 近似 仮定 t=0 以前で 0 t=t1 以降で 0 G(ω)≒F(ω)exp(－ jαω t1)
g(t)=f(t/(1+α))　ただし、α<<1 t=0 以前で 0 t=t1 以降で 0 G(ω)≒F(ω)exp(－ jαω t1) G(ω) ：g(t) のフーリエ変換 F(ω) ：f(t) のフーリエ変換 まず背景としまして、 核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている

14 検索法 角度法 貪欲法 対角法 少しずつ角度を変化 最初は検索範囲を大きくし絞り込む 対角のみ 原検索範囲 小領域 まず背景としまして、
核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている

15 評価 対象：1000個のボロメータ計測データ 角度αの増加量を変化させて測定 まず背景としまして、
核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている

16 まとめ 今後の課題 波形の高速類似検索（ＦＦＴ利用） 波長の多少異なる波形も検索（近似） 他の積分型波形への適用 揺動型波形に対する検討
1段階目：R木による検索（5次元インデックス） 2段階目：係数4個を使用（1段階目で使用の係数以外） 波長の多少異なる波形も検索（近似） 今後の課題 まず背景としまして、 核融合科学の実験では膨大な量のデータが発生し、 効率のよいデータ管理が必要とされています。 また、今回の研究で用いたデータは、 Bolometer計測と言って、放射熱量を計測したもので、 右のような波形のデータです。 横軸が時間で、縦軸が放射熱量を表しています。 またこういった研究において、類似したデータを得ることは、 新たな規則発見などにつながる場合があり、 大変意味があります。 そこで、類似データの的確かつ迅速な 検索方法の検討を目的とします。 512コの点でフーリエ変換 1000個ずつ飛ばす 波形全体をとっている 他の積分型波形への適用 揺動型波形に対する検討