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

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

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

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

多次元インデックス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次元を超えると検索効率低下

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

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

次元数（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）で 大まかな波形の類似度が判断可能

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つのキーに対して、距離が遠くなるものを選んだ

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の時 最も精度が良い

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

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

近似 仮定 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個ずつ飛ばす 波形全体をとっている

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

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

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