大容量データベースのデータマイニング手法 （積分型波形データの類似検索） 寶珍 輝尚 大阪府立大学 総合科学部 数理・情報科学科 （平成１７年４月から理学系研究科 情報数理科学専攻） 背景 • 核融合科学の実験 – 膨大な量のデータが発生 – 膨大な数のデータが発生 • 効率の良いデータ管理が必要 • 類似データの発見 → 規則の発見（？） 目的 類似波形の的確かつ迅速な検索 • 対象データ 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 問題点１ 最初のk個（2k-1次元）の係数がほぼ同じでも 波形が異なるデータが存在 例）インデックス5次元、データ数1000 検索キー：No094 距離が最も近いデータ：No029 検索精度の改良 2段階の処理 ・1段階目：R木を使用（2k-1次元） 足切りに利用 ・2段階目：波形の類似度を判定 値の大きいm個の係数 を使用（最初の2k-1以外） 次元数（2k-1）の選定 計測データ1000個の係数の平均 k １ 実部 2059 虚部 0 ２ ３ ４ ５ ６ ７ 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 距 順 離 位 ２ １ ３ ２ ３ ２ ４ ４ 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 問題点２ • 周波数領域への変換法： キー波形の波長が支配的 • 多少異なる波長の波形も検索したい 近似 • 仮定 – 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 まとめ • 波形の高速類似検索（ＦＦＴ利用） – 1段階目：R木による検索（5次元インデックス） – 2段階目：係数4個を使用（1段階目で使用の係数以外） • 波長の多少異なる波形も検索（近似） 今後の課題 • 他の積分型波形への適用 • 揺動型波形に対する検討
© Copyright 2024 ExpyDoc
