応答時間を考慮したストリームデータクリーニング手法の検討

DEIM Forum 2016 P4-3

応答時間を考慮したストリームデータクリーニング手法の検討

若森

拓馬

†

内山

寛之

†

岩村

相哲

†

† 日本電信電話株式会社 NTT ソフトウェアイノベーションセンタ 〒 180–8585 東京都武蔵野市緑町 3–9–11

E-mail:

†{wakamori.takuma,uchiyama.hiroyuki,iwamura.sotetsu}@lab.ntt.co.jp

あらまし IoT デバイスの普及に伴い，センサデータなどのストリームデータに含まれる外れ値・欠損値等のエラー

を取り除き，データ品質を向上するストリームデータクリーニング技術の重要性が高まっている．ストリームデータ

クリーニング手法は，あるウィンドウ内の未来のデータをもとに現在のデータを補正するため，データを取得してか

ら修正処理を完了するまでに一定の時間を要する．我々は，工場での環境センシングによる異常検知やセンサ値を用

いた即時の分析処理など，性能要件の厳しいオンライン処理に対しても，データクリーニングを行うことの価値は大

きいと考えている．しかしながら，既存手法はデータ修正の精度向上を目的としているため，応答時間の条件のもと

でクリーニング処理を制御することについてはあまり議論されていない．本研究では，オンライン処理に対してデー

タクリーニングを行うことを目的として，応答時間を考慮したストリームデータクリーニング手法について検討する．

本稿では，データの修正がどの程度の確度で行われたかを評価する指標と，オンライン処理におけるデータクリーニ

ングの有効性について，実験結果をもとに考察する．

キーワード データクリーニング，ストリームデータ処理，前処理

1.

は じ め に

IoTデバイスの普及に伴い，センサネットワークによる環境 センシングや，コンピュータクラスタのモニタリング，GPSを 用いた人流分析など，時々刻々と変化するストリームデータか ら即座に洞察を得るデータ分析技術への関心が高まっている． 現実のデータは，データを読み取る物理センサの信頼性の低さ や，手作業による入力ミスなどの理由から，外れ値や欠損値な どの誤り（エラー）を含んでいる．エラーは分析結果の精度に 悪影響を及ぼすことから，データからエラーを取り除くデータ クリーニングは，実データ分析において欠かすことのできない 重要な処理である． これまで，データ品質の評価方式の提案や，クリーニングア ルゴリズムの効率や効果の改善など，データクリーニングに関 する様々な研究がなされてきた．その中でも，ストリームデー タに対するオンラインのクリーニング手法（以降，ストリー ムデータクリーニング手法とよぶ）は，スループットの要求さ れるタスクに適用可能であることから，近年注目を集めてい る[3], [6]． ストリームデータクリーニング手法は，データストリームを ある有限長のウィンドウ幅で切り出し，修正処理を逐次実行す る．一般に，ある時点の値を修正するために，ウィンドウ内の 未来の時点の値を用いる[6]．そのため，データを取得してから 修正処理を完了するまでに一定の時間を要する． 一方，現実のオンライン処理においては，性能要件が厳しい ため，データクリーニング等の時間のかかる処理は行わないこ とが一般的である．我々は，性能要件の厳しいオンライン処理 に対しても，データクリーニングを行うことの価値は大きいと 考えている． 例えば，工場での環境センシングのタスクでは，センサが異 常値を検知した場合，即座にアラートを上げることが望まし い一方で，誤検知（false positive）をなるべく減らしたいとい う課題がある．また無線センサネットワークにおいて，複数の 発信機の発する電波の電波強度から受信機の位置を推定する Multilaterationのタスクでは，計測値をそのまま利用するので はなく，性能要件のもとで，可能な限りのデータ修正を行った 後の修正データを利用することで，位置推定の精度を向上でき る可能性がある． しかしながら，既存のストリームデータクリーニング手法は データ修正の精度（以降，修正精度とよぶ）の向上を主眼とし ているため，応答時間や他の条件のもとで修正処理を制御する ことについてはあまり議論されていない． 本研究の目的は，性能要件の厳しいオンライン処理に対して データクリーニングを行うことである．具体的に，以下の要件 を満たすストリームデータクリーニングを実現する手法を検討 する． （1） 応答時間の制御が可能である．決められた応答時間 （数ミリ秒∼数秒程度）内にデータ修正処理を完了する必要があ る．応答時間内に修正処理を完了することができない場合，修 正精度が不十分な状態でも，処理結果を出力できる必要がある． （2） データ修正の確度を評価する指標をもつ．正解データ が与えられていない場合，データ修正が正しく行われたかどう かを評価することは困難である．異常検知などのミッションク リティカルなオンライン処理では，誤ったデータ修正で本来検 出すべき異常を見逃してしまうリスクがあるため，少なくとも データ修正がどの程度の確度で行われたのかについて評価でき る必要がある． 本稿では，正解データを推測する手法に関する実験結果をも とに，データ修正の確度の評価指標の妥当性について考察する． また，実データを用いたオンライン処理に対するデータクリー

ニング実験結果をもとに，データクリーニングが分析精度に与 える影響について考察する．

2.

関 連 研 究

本節では，既存のデータクリーニング手法を概観し，本研究 の位置づけを述べる． データクリーニングは，データに含まれるエラーを取り除く 手続きを表す．エラーを取り除くためには，正常値とエラーを 区別する指標が必要となる．この指標を定める方針として，モ デルベースと制約ベースの２つのアプローチがある．各アプ ローチの特徴を以下に述べる． 2. 1 モデルベースのアプローチ モデルベースのアプローチは，モデルを用いてセンサの取り うる最もらしい値を推定する．推定値から大きく外れたセンサ 値をエラーとみなす．代表的なモデルを以下に示す． 回帰モデルは，サンプリング処理の連続性と異なるサンプリ ング処理間に相関があることを前提とするモデルである．代表 的なものに多項式でモデルを記述する多項式回帰と，余弦関数 （cosθ）の多項式で表すチェビシェフ回帰がある．多項式回帰 の一つである（加重）移動平均モデルは株価予測などのオンラ イン処理に用いられる代表的なモデルの一つである． 確率モデルは，ウィンドウ内の過去の値をもとに確率分布を 推定するモデルである．データが確率分布（ガウス分布等）に 従うことを前提とし，信頼区間に含まれないものをエラーと判 断する．ガウス分布を前提として，解析的に条件付期待値を計 算するカルマンフィルタは最も一般的な確率モデルの一つであ る．ベイズの定理に基づいて確率分布を推定する手法もある． 外れ値検知モデルは，他のセンサ値から大きく外れた値（外 れ値）を検知する．検出した外れ値をエラーとみなし除去する ことでデータクリーニングを行うことができる．センサの特性 に着目した手法や，Jaccard係数やヒストグラム，距離・密度 ベースのメトリクスを用いて外れ値を特定する手法がある． 2. 2 制約ベースのアプローチ 制約ベースのアプローチでは，ユーザが宣言的に制約条件を 記述し，制約を違反した値をエラーとみなす．複雑なデータ処 理やモデル利用をユーザーから隠蔽することで，クリーニング 後のデータ活用を促進する効果が期待される．一例としては， データクリーニングをPoint, Smooth, Merge, Arbitrate, Virtualize の５つのタスクに分割して，データベースシステム上で処理を する手法[2]がある．ユーザはSQL-Likeなクエリを用いてデー タクリーニングの制約条件を記述することができる． また，データをノードとエッジからなるグラフ表現に変換し て，宣言的記法で関連する属性の集合を抽出し，この従属性を 用いて統計的手法により値を検査し，データクリーニングを行 う手法もある． また，ストリームデータに適用可能なデータクリーニング手 法として，速度制約と呼ばれる，データの勾配の最大値・最小値 に関する制約を定義する手法[6]がある．例えば歩行者の移動 軌跡を考える場合，ある２点間の距離と時刻から算出した速度 が秒速１０メートルを超える場合は，速度制約に違反している ため，データの修正の必要があると考える．このとき，最少変 更原理[1]に基づき，修正におけるデータの移動距離を出来る 限り小さくすることによって，修正精度の向上を目指している． 2. 3 本研究の位置づけ 本研究では，応答性能要件の厳しいオンライン処理において， ストリームデータのクリーニングを行うことを目的としている． そのため，オンラインに適用可能なウィンドウを用いた手法が 前提となる．多くのデータと計算時間を必要とする多項式回帰 等のモデルベースのクリーニング手法を，ストリームデータに 適用することは困難である．また，修正精度を向上することに 加え，データクリーニングがその後の分析結果の精度に与える 影響について考察する．

3.

実験と考察

我々は，データ修正の確度を評価する指標についての一検 討として，既存のストリームデータクリーニング手法である SCREEN [6]を用いて，正解データを推測するための検討を行っ た．本節では実験の結果を述べ，正解データの推測に関して考 察する．また，屋内位置推定タスクにおけるデータクリーニン グの実験結果をもとに，データクリーニングが位置推定の精度 に与える影響について考察する． 3. 1 実験１：ウィンドウ幅と応答時間・修正精度の関係 SCREENでは，速度制約と最小変更原理[1]に基づき，デー タ移動距離を小さくすることで修正精度を向上させている．我々 は，データの移動距離を最小化するクリーニング結果を正解 データとして用いることを考え，この仮説を検証するための実 験を実施した． 3. 1. 1 実 験 内 容

本実験では，SCREENにおけるLocal Optimumアルゴリズ ム（詳細は付録を参照）および，最小変更原理に基づき修正距 離を最小化する最適化問題を解くGlobal Optimumアルゴリズ ムにおいて，ウィンドウ幅を大きくした場合の修正精度（修正 後のデータと正解データの距離）の変化を測定した．ウィンド ウ幅が大きいほどデータの移動距離は小さくなり，正解データ に近づくと予測される． クリーニング対象には，1989年11月から2015年11月まで の過去１６年分の株価データ1（要素数：6785，最大値：893.181， 最小値：18.691）に対して人工的なエラーを挿入したものを用い た．エラーの挿入においては，全体の要素のうち5%の要素を ランダムに選択し，最大値・最小値の範囲内のランダムな値に変 更した．株価の１日あたりの変動幅は前日比±10%であること から，速度制約は最大値の約10%を根拠として，s= (−90, +90) とした．修正精度の評価には次式を用いた． a= 1 − ∆(xtr uth, xr epair)

∆(xr epair, xdir t y)+ ∆(xtr uth, xdir t y)

(1)

式1におけるxtr uth，xr epair，xdir t yは，それぞれ正解デー

タ，修正後のデータ，修正前のエラー混入データを表し，∆(x1, x2) （注 1）：http://finance.yahoo.com/q/hp?s=AIP.L+Historical+Prices

は，x1とx2の平均二乗誤差（RMS Error）を表す． 3. 1. 2 実 験 結 果 0.65 0.7 0.75 0.8 0.85 0.9 0 2 4 6 8 10 12 A c c u ra c y Window size Local Global 図 1 s= (−90, +90) における，ウィンドウ幅と修正精度の関係 0.94 0.95 0.96 0.97 0.98 0.99 1 0 2 4 6 8 10 12 A c c u ra c y Window size Local Global 図 2 s= (−5, +5) における，ウィンドウ幅と修正精度の関係 実験結果を図1に示す．結果は予測とは異なり，ウィンドウ 幅が大きければ大きいほど修正精度が低下した． そ こ で 速 度 制 約 と の 関 係 を 考 察 す る た め ，速 度 制 約 を s = (−5, +5)に変更して同様の実験を実施した．結果を図2 に示す．ウィンドウ幅が1から7の範囲では修正精度が向上す る結果となった． 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0.02 0.03 0.04 0.05 0.06 0.07 0.08 A c c u ra c y Time [s] s=(-5,+5) s=(-90,+90) 図 3 Local Optimumアルゴリズムにおける，応答時間と修正精度の 関係 次に，Local Optimumアルゴリズムにおいて，s= (−5, +5)お よびs= (−90, +90)の２つの場合について，応答時間と修正精 度の関係を測定した．結果を図3に示す． 3. 2 実験２：オンライン処理におけるデータクリーニング の有効性 我々は，応答時間を制御可能とすることで，オンライン処理 に対してデータクリーニングを行うことを目的としている．本 実験では，オンライン処理として，Bluetooth Low Energy (BLE) デバイスを用いた屋内位置推定タスクを対象に，SCREENのア ルゴリズムを用いてストリームデータクリーニングを行い，位 置推定精度への影響を測定した． 3. 2. 1 実 験 内 容 本実験では，12個のBLEデバイス（送信機）を床面へ設置 し，受信機の受信した電波強度（RSSI）から受信機の位置を推 定するMultilaterationタスクを実施した．Multilaterationのよう なオンライン処理において，測定値にデータクリーニングを 行った場合，位置推定の結果にどのような影響が生じるかにつ いて調査した． RSSIを用いた位置推定には文献[7]の手法を用いた．まず， RSSI値と距離の関係はフリスの伝達公式に基づき次式で定め られる． RSSI[dBm]= −(10 · n · log₁₀(d)+ A) (2) ここで，初期信号強度Aは，送信機と受信機の距離が1mの 地点におけるRSSIの絶対値で表される．本実験においては， 12個の送信機のRSSIの平均値から算出した．伝達係数nは信 号の減衰を表す．送信機と受信機の距離を，0.5mから5.0mの 区間で0.5m間隔で変化させてRSSIを測定し，RSSIの理論値 と測定値のRMS Errorを最少化するnを経験的に決定した．以 上の手順により決定したパラメータを以下に示す． 記号 定義 設定値 A 初期信号強度 70.65 n 伝達系数 1 s 速度制約 (-0.0003,+0.0003) w ウィンドウ幅 100 測定においては，送信機を幅6m，奥行き4mの空間に2m間 隔で格子状に配置し，受信機の受信したRSSIから各送信機と の距離を式2にて算出した．Multilaterationにおける非線形最 小二乗問題の解法にはLevenberg-Marquardt法を用いた．以上 の手順にしたがって測定値を元に算出した1294点の位置推定 値をクリーニング対象とした． 3. 2. 2 実 験 結 果 クリーニング前のデータを用いた位置推定結果と修正データ を用いた位置推定結果を図4に示す．図の(x_truth, y_truth)・(x, y)・(x’, y’)は，それぞれ正解データ・クリーニング前のデータ・ Local Optimumアルゴリズムでの修正データの(x, y)座標を表 している． 図4の修正後のから，速度制約を満たすようにデータを修正 したことで，信頼性の低いセンサを用いた場合でも，ある程度 正解データに近い推定を行うことができたことが読み取れる． 一方，y座標，Local Optimumアルゴリズムでは，ウィンドウ幅

-10 -5 0 5 10 0 10 20 30 40 50 60 70 ࠴ ඬ [m ] ܨգ࣎ؔ[භ] x_truth y_truth x y x' y' 図 4 正解データとクリーニング前後の位置推定結果の比較 表 1 位置推定タスクにおけるデータクリーニングの効果 手法 修正距離 修正精度 RMS Error 精度改善率 修正前 - - 6.31 1 Local 6723 0.59 5.39 1.17 Global 15816 0.52 10.08 0.63 また，この時の修正距離・修正精度，RMS Error，制度改善率 を表1にまとめる．表1におけるLocalはLocal Optimumアル ゴリズム，GlobalはGlobal Optimumアルゴリズムを表し，精 度改善率は，修正前のRMS Errorを１とした場合の，修正後の RMS Errorの改善率を示している． 表に示すとおり，Local Optimumアルゴリズムでデータク リーニングを行うことにより，位置推定精度が向上することが 分かった．一方，Global Optimumは，クリーニング時間が30 分を経過した時点で解の探索が終了せず，推定精度が低下する 結果となった． 3. 3 考 察 実験１および実験２を通じて，ストリームデータクリーニン グ手法がオンライン処理の精度向上に有効であることが示され た．一方，本実験を通じて以下の課題も明らかとなった． • 無限のウィンドウ幅を用いたクリーニング結果をもって 正解データの代わりとすることは妥当ではない．実験１では， 速度制約が強い場合を除き，ウィンドウ幅が大きいほど修正精 度が低下する傾向を示した．これは，ウィンドウ幅が大きいほ ど，ウィンドウ内に多くのエラー値を含むことになり，未来の値 を用いる既存手法では，エラーの影響を強く受けてしまうこと が原因と考えられる．また実験２の結果から，Global Optimum アルゴリズムは現実的な時間で解を探索できないため，正解 データを生成することは困難であるといえる． • 速度制約は，変動幅の変化するデータに対する効果が小 さい．実験１で使用した株価データは，最小値付近の日付では １日あたりの変動幅が1.8以下であるのに対して，最大値付近 では１日あたりの90近く変動する可能性がある．そのため，変 動の最大値・最小値のみを制約条件とする場合，最小値付近の 日付において修正対象のデータを見逃す可能性が高い．一方， 速度制約を強くした場合，最大値付近で本来修正する必要のな いデータを修正してしまう可能性が生じる．したがって，速度 制約は，現在値に応じて柔軟に制御可能であることが望ましい． • エラー割合が大きすぎる場合，データクリーニング以外 の手段でエラーを除去するべきである．実験２において，デー タクリーニングにより位置推定精度を向上できることを確認で きた．一方，Local OptimumおよびGlobal Optimumのいずれ

の手法においても，修正精度は6割に満たなかった．また，図 4から，修正後のデータと正解データの間には依然として距離 があることが読み取れる．この結果から，修正前のデータの大 部分が修正対象とみなされる場合，速度制約の「制約を満たす データは移動しないようにする」という性質を活用して修正精 度を向上することは困難であるとわかる．実タスクにデータク リーニングを適用するためには，データに含まれるエラーの割 合が少なくとも半分以下になるような信頼性の高いセンサを利 用する必要があると考えられる．

4.

お わ り に

本研究では，性能要件の厳しい現実のオンライン処理に対し てデータクリーニングを行うことを目的として，応答時間を考 慮したストリームデータクリーニング手法について考察した． 正解データを予測する手法の一検討として，既存手法のウィン ドウ幅とデータ修正の精度の関係を調査する実験を実施した． 実験により，オンライン処理に対してデータクリーニングを行 うことの有効性を示した．一方，データ修正の確度の評価にお いては，ウィンドウ幅を大きくとったものを正解データの代わ りとすることは困難であることが分かった． 今後の課題として，応答時間を制御する手法を考案するとと もに，確率モデルに基づく品質評価手法[4], [5]をデータ修正の 確度の評価に用いる予定である． 文 献

[1] P. Bohannon, W. Fan, M. Flaster, and R. Rastogi. A cost-based model and effective heuristic for repairing constraints by value modification. In SIGMOD, pp. 143–154, 2005.

[2] S. R. Jeffery, G. Alonso, M. J. Franklin, W. Hong, and J. Widom. Declarative support for sensor data cleaning. In PERVASIVE, pp. 83–100, 2006.

[3] E. J. Keogh, S. Chu, D. Hart, and M. J. Pazzani. An online algorithm for segmenting time series. In ICDM, pp. 289–296, 2001.

[4] A. Klein. Incorporating quality aspects in sensor data streams. In

CIKM, pp. 77–84, 2007.

[5] A. Klein and W. Lehner. Representing data quality in sensor data streaming environments. Data and Information Quality, pp. 10:1– 10:28, 2009.

[6] S. Song, A. Zhang, J. Wang, and P. S. Yu. Screen: Stream data cleaning under speed constraints. In SIGMOD, pp. 827–841, 2015. [7] X. Wang, O. Bischoff, R. Laur, and S. Paul. Localization in wireless

ad-hoc sensor networks using multilateration with rssi for logistic applications. Procedia Chemistry, pp. 461–464, 2009.

付

録

1. SCREENのデータクリーニング手法 本節では実験に用いたSCREENのデータクリーニング手法 の詳細を説明する．なお，データ修正アルゴリズムは，Local Optimumのみについて言及する． まず，ストリームデータクリーニングの問題を定式化する． ストリームデータの系列をx= x[1], x[2], ...,とする．x[i]はi番 目の値を表す．x[i]の発生時刻をt[i]とする．簡単のため，x[i] をxi，t[i]をti と表記する．ある時刻間隔（ウィンドウ）wに

最低速度，smaxは最高速度を表す． xk が速度制約sを満たすとき，xk |= sと表記する．すなわ ち，x_k |= sのとき，x_k 以降の任意の点xi(tk < ti <= tk+ w)に ついて，smin<= x_ti_i−x_−tkk <= smaxが成り立つ． xに対する修正x′とは，t′_i= tiにおける値xiのx′_iへの変更 を表す．データ修正における修正距離は，最少変更原理に基づ き，元のxと修正後のx′の距離によって，次式のように定義 される． ∆(x, x′)= ∑ xi∈x |xi− xi′| (A·1) 例として，６点からなる系列x= {12, 12.5, 13, 10, 15, 15.5}, t = {1, 2, 3, 5, 7, 8}を考える．図A· 1における黒色の点は系列xを 表す．系列xの速度制約をsmax= 0.5，smin= −0.5とする． V a lu e Time s_max s_min w t_i t_i+1 t₆ x₁ x_i x’_i+1 x’’_i+1 x_i+1 x₆ 図 A· 1 速度制約下における修正候補 ウィンドウ幅がw= 2のとき，点x3とx4（時刻間隔は5−3 <= 2）は，速度制約におけるsmin= −0.5を違反している．なぜな らば，x3，x4間の速度について，10−13₅₋₃ = −1.5 < −0.5が成り立 つからである．同様に，x₄とx₅間の速度は15−10₇₋₅ = 2.5 > 0.5 であり，smax= 0.5を違反している． この2つの違反（図A· 1における破線部）を矯正するため に，例えば，x4をx′₄= 14（図A· 1における白色の点）に修正 することができる．図A· 1に示すとおり，修正後の系列は，最 高速度・最低速度の速度制約をともに満たしている．このとき， 修正距離は∆(x, x′)= |10 − 14| = 4である． もしウィンドウ幅が非常に小さい（例えばw = 1）ならば， x3とx4間（x4とx5間）の違反は発見できない．なぜならば， 時刻間隔が2> 1となるからである．一方，ウィンドウ幅が十 分に大きい（例えばw= 10）ならば，系列x内のすべての点の 組を比較しなければならない．同じ修正x′を行うことができ たとしても，計算のオーバーヘッドは明らかに大きくなる．ゆ えに，修正精度と効率の釣り合いをとるためには，適切なウィ ンドウ幅を設定する必要がある． このデータ修正問題は，以下のように定義できる． min n ∑ i=1 |xi− xi′| s.t. x ′ k− xi′ t_k− ti <= smax, tk < ti <= tk+ w, 1 <= i <= n x_k′− x_i′ tk− ti >= smin, tk < ti <= tk+ w, 1 <= i <= n (A·2) データ修正とは，式(A·2)を満たすx_i′(1<= i <= n)を求めるこ とである． Algorithm 1Local(x, s) Require: x,時刻で整列済みの系列; s, 速度制約 Ensure: x′, xの修正 1: for k← 1 から n に対して do 2: Xmi n k ← ∅; X m a x k ← ∅; 3: xmi n k ← x′k−1+ smi n(tk− tk−1), または k = 1 に対して − ∞; 4: x_km a x← x′_k−1+ sm a x(tk− tk−1), または k = 1 に対して + ∞; 5: for i← k + 1 から n に対して do 6: if ti> tk+ w then 7: ループを抜ける ; 8: end if 9: Xmi n k ← X mi n k ∪ {xi+ smi n(tk− ti)}; 10: Xm a x k ← X m a x k ∪ {xi+ sm a x(tk− ti)}; 11: end for 12: x_kmi d← median(X_kmi n∪ X_km a x∪ {xk}); 13: if x_km a x< x_kmi dthen 14: x′_k← xm a x_k ; 15: else if xm a x k > x mi d k then 16: x′_k← xmi n k ; 17: else 18: x′_k← xmi d k ; 19: end if 20: end for 21: return x′ Algorithm 1に，既存手法における速度制約sのもとで系列x をx′に修正するデータ修正アルゴリズムを示す．このアルゴ リズムは，ある点x_k の修正において，x_k+1からxnの範囲で ウィンドウ幅w内に存在する点を用いる（５∼１１行目）．