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. は じ め に常値を検知した場合，即座にアラートを上げることが望ましい一方で，誤検知（false positive）をなるべく減らしたいとい

IoT デバイスの普及に伴い，センサネットワークによる環境う課題がある．また無線センサネットワークにおいて，複数のセンシングや，コンピュータクラスタのモニタリング，GPS を発信機の発する電波の電波強度から受信機の位置を推定する用いた人流分析など，時々刻々と変化するストリームデータかMultilateration のタスクでは，計測値をそのまま利用するのでら即座に洞察を得るデータ分析技術への関心が高まっている．

はなく，性能要件のもとで，可能な限りのデータ修正を行った

現実のデータは，データを読み取る物理センサの信頼性の低さ

後の修正データを利用することで，位置推定の精度を向上できや，手作業による入力ミスなどの理由から，外れ値や欠損値なる可能性がある．

どの誤り（エラー）を含んでいる．エラーは分析結果の精度にしかしながら，既存のストリームデータクリーニング手法は悪影響を及ぼすことから，データからエラーを取り除くデータデータ修正の精度（以降，修正精度とよぶ）の向上を主眼としクリーニングは，実データ分析において欠かすことのできないているため，応答時間や他の条件のもとで修正処理を制御する重要な処理である．

ことについてはあまり議論されていない．

これまで，データ品質の評価方式の提案や，クリーニングア

本研究の目的は，性能要件の厳しいオンライン処理に対してルゴリズムの効率や効果の改善など，データクリーニングに関データクリーニングを行うことである．具体的に，以下の要件する様々な研究がなされてきた．その中でも，ストリームデーを満たすストリームデータクリーニングを実現する手法を検討

タに対するオンラインのクリーニング手法（以降，ストリーする．

ムデータクリーニング手法とよぶ）は，スループットの要求さ（ 1 ） 応答時間の制御が可能である．決められた応答時間れるタスクに適用可能であることから，近年注目を集めてい（数ミリ秒〜数秒程度）内にデータ修正処理を完了する必要があ

る [3], [6]．

る．応答時間内に修正処理を完了することができない場合，修ストリームデータクリーニング手法は，データストリームを正精度が不十分な状態でも，処理結果を出力できる必要がある．

ある有限長のウィンドウ幅で切り出し，修正処理を逐次実行す（ 2 ） データ修正の確度を評価する指標をもつ．正解データ

る．一般に，ある時点の値を修正するために，ウィンドウ内のが与えられていない場合，データ修正が正しく行われたかどう未来の時点の値を用いる [6]．そのため，データを取得してからかを評価することは困難である．異常検知などのミッションク修正処理を完了するまでに一定の時間を要する．

リティカルなオンライン処理では，誤ったデータ修正で本来検一方，現実のオンライン処理においては，性能要件が厳しい出すべき異常を見逃してしまうリスクがあるため，少なくともため，データクリーニング等の時間のかかる処理は行わないこ

データ修正がどの程度の確度で行われたのかについて評価できとが一般的である．我々は，性能要件の厳しいオンライン処理る必要がある．

に対しても，データクリーニングを行うことの価値は大きいと考えている．
例えば，工場での環境センシングのタスクでは，センサが異本稿では，正解データを推測する手法に関する実験結果をもとに，データ修正の確度の評価指標の妥当性について考察する．
また，実データを用いたオンライン処理に対するデータクリー

ニング実験結果をもとに，データクリーニングが分析精度に与ため，データの修正の必要があると考える．このとき，最少変える影響について考察する．

更原理 [1] に基づき，修正におけるデータの移動距離を出来る

2. 関 連 研 究
本節では，既存のデータクリーニング手法を概観し，本研究の位置づけを述べる．

限り小さくすることによって，修正精度の向上を目指している．

2. 3 本研究の位置づけ
本研究では，応答性能要件の厳しいオンライン処理において，ストリームデータのクリーニングを行うことを目的としている．

データクリーニングは，データに含まれるエラーを取り除く

そのため，オンラインに適用可能なウィンドウを用いた手法が手続きを表す．エラーを取り除くためには，正常値とエラーを前提となる．多くのデータと計算時間を必要とする多項式回帰区別する指標が必要となる．この指標を定める方針として，モ等のモデルベースのクリーニング手法を，ストリームデータにデルベースと制約ベースの２つのアプローチがある．各アプ適用することは困難である．また，修正精度を向上することにローチの特徴を以下に述べる．

加え，データクリーニングがその後の分析結果の精度に与える

2. 1 モデルベースのアプローチ
モデルベースのアプローチは，モデルを用いてセンサの取りうる最もらしい値を推定する．推定値から大きく外れたセンサ値をエラーとみなす．代表的なモデルを以下に示す．

影響について考察する．

3. 実験と考察
我々は，データ修正の確度を評価する指標についての一検回帰モデルは，サンプリング処理の連続性と異なるサンプリ討として，既存のストリームデータクリーニング手法であるング処理間に相関があることを前提とするモデルである．代表

SCREEN [6] を用いて，正解データを推測するための検討を行っ的なものに多項式でモデルを記述する多項式回帰と，余弦関数た．本節では実験の結果を述べ，正解データの推測に関して考（cos θ ）の多項式で表すチェビシェフ回帰がある．多項式回帰察する．また，屋内位置推定タスクにおけるデータクリーニンの一つである（加重）移動平均モデルは株価予測などのオンラグの実験結果をもとに，データクリーニングが位置推定の精度イン処理に用いられる代表的なモデルの一つである．に与える影響について考察する．

確率モデルは，ウィンドウ内の過去の値をもとに確率分布を3. 1 実験１：ウィンドウ幅と応答時間・修正精度の関係推定するモデルである．データが確率分布（ガウス分布等）にSCREEN では，速度制約と最小変更原理 [1] に基づき，デー従うことを前提とし，信頼区間に含まれないものをエラーと判

タ移動距離を小さくすることで修正精度を向上させている．我々断する．ガウス分布を前提として，解析的に条件付期待値を計は，データの移動距離を最小化するクリーニング結果を正解算するカルマンフィルタは最も一般的な確率モデルの一つであデータとして用いることを考え，この仮説を検証するための実る．ベイズの定理に基づいて確率分布を推定する手法もある．

験を実施した．

外れ値検知モデルは，他のセンサ値から大きく外れた値（外3. 1. 1 実 験 内 容れ値）を検知する．検出した外れ値をエラーとみなし除去する

本実験では，SCREEN における Local Optimum アルゴリズ

ことでデータクリーニングを行うことができる．センサの特性ム（詳細は付録を参照）および，最小変更原理に基づき修正距に着目した手法や，Jaccard 係数やヒストグラム，距離・密度離を最小化する最適化問題を解く Global Optimum アルゴリズ

ベースのメトリクスを用いて外れ値を特定する手法がある．

ムにおいて，ウィンドウ幅を大きくした場合の修正精度（修正2. 2 制約ベースのアプローチ

後のデータと正解データの距離）の変化を測定した．ウィンド

制約ベースのアプローチでは，ユーザが宣言的に制約条件をウ幅が大きいほどデータの移動距離は小さくなり，正解データ記述し，制約を違反した値をエラーとみなす．複雑なデータ処に近づくと予測される．

理やモデル利用をユーザーから隠蔽することで，クリーニングクリーニング対象には，1989 年 11 月から 2015 年 11 月まで後のデータ活用を促進する効果が期待される．一例としては，の過去１６年分の株価データ 1 （要素数：6785，最大値：893.181，

データクリーニングを Point, Smooth, Merge, Arbitrate, Virtualize最小値：18.691）に対して人工的なエラーを挿入したものを用いの５つのタスクに分割して，データベースシステム上で処理をた．エラーの挿入においては，全体の要素のうち 5% の要素をする手法 [2] がある．ユーザは SQL-Like なクエリを用いてデーランダムに選択し，最大値・最小値の範囲内のランダムな値に変タクリーニングの制約条件を記述することができる．

更した．株価の１日あたりの変動幅は前日比 ±10% であること

また，データをノードとエッジからなるグラフ表現に変換して，宣言的記法で関連する属性の集合を抽出し，この従属性をから，速度制約は最大値の約 10% を根拠として，s = (−90, +90)とした．修正精度の評価には次式を用いた．

用いて統計的手法により値を検査し，データクリーニングを行う手法もある．
また，ストリームデータに適用可能なデータクリーニング手法として，速度制約と呼ばれる，データの勾配の最大値・最小値に関する制約を定義する手法 [6] がある．例えば歩行者の移動軌跡を考える場合，ある２点間の距離と時刻から算出した速度が秒速１０メートルを超える場合は，速度制約に違反している

a =1−∆(x truth, x r epair )∆(x repair , x dirty ) + ∆(x truth, x dirty )(1)

式 1 における x truth ，x repair ，x dirty は，それぞれ正解デー
タ，修正後のデータ，修正前のエラー混入データを表し，∆(x 1, x 2 )（注 1）：http://finance.yahoo.com/q/hp?s=AIP.L+Historical+Prices3. 2 実験２：オンライン処理におけるデータクリーニング

は， x 1 と x 2 の平均二乗誤差（RMS Error）を表す．の有効性

3. 1. 2 実 験 結 果

我々は，応答時間を制御可能とすることで，オンライン処理0.9に対してデータクリーニングを行うことを目的としている．本

Accuracy

0.85

実験では，オンライン処理として，Bluetooth Low Energy (BLE)
Local
Global

0.8

デバイスを用いた屋内位置推定タスクを対象に，SCREEN のアルゴリズムを用いてストリームデータクリーニングを行い，位0.75

置推定精度への影響を測定した．

0.7

3. 2. 1 実 験 内 容
0.650

図1246
Window size

81012

本実験では，12 個の BLE デバイス（送信機）を床面へ設置し，受信機の受信した電波強度（RSSI）から受信機の位置を推s = (−90, +90) における，ウィンドウ幅と修正精度の関係定する Multilateration タスクを実施した．Multilateration のようなオンライン処理において，測定値にデータクリーニングを行った場合，位置推定の結果にどのような影響が生じるかについて調査した．

1RSSI を用いた位置推定には文献 [7] の手法を用いた．まず，Accuracy

0.99
0.98

RSSI 値と距離の関係はフリスの伝達公式に基づき次式で定め

Local
Global0.97られる．

0.96

RSSI[dBm] = −(10 · n · log10 (d) + A)

0.95
0.940246Window size

81012ここで，初期信号強度 A は，送信機と受信機の距離が 1m の地点における RSSI の絶対値で表される．本実験においては，s = (−5, +5) における，ウィンドウ幅と修正精度の関係

図2(2)12 個の送信機の RSSI の平均値から算出した．伝達係数 n は信号の減衰を表す．送信機と受信機の距離を，0.5m から 5.0m の実験結果を図 1 に示す．結果は予測とは異なり，ウィンドウ区間で 0.5m 間隔で変化させて RSSI を測定し，RSSI の理論値と測定値の RMS Error を最少化する n を経験的に決定した．以幅が大きければ大きいほど修正精度が低下した．
そ こ で 速 度 制 約 と の 関 係 を 考 察 す る た め ，速 度 制 約 を上の手順により決定したパラメータを以下に示す．

s = (−5, +5) に変更して同様の実験を実施した．結果を図 2

定義設定値に示す．ウィンドウ幅が 1 から 7 の範囲では修正精度が向上す

記号

A 初期信号強度70.65る結果となった．

n

伝達系数

1s

速度制約(-0.0003,+0.0003)

w

ウィンドウ幅100

10.95

Accuracy0.9

s=(-5,+5)s=(-90,+90)

0.85

測定においては，送信機を幅 6m，奥行き 4m の空間に 2m 間0.8隔で格子状に配置し，受信機の受信した RSSI から各送信機と0.75の距離を式 2 にて算出した．Multilateration における非線形最0.7

小二乗問題の解法には Levenberg-Marquardt 法を用いた．以上

0.650.020.030.040.05
Time [s]0.06

0.070.08

図 3 Local Optimum アルゴリズムにおける，応答時間と修正精度の関係の手順にしたがって測定値を元に算出した 1294 点の位置推定値をクリーニング対象とした．

3. 2. 2 実 験 結 果
クリーニング前のデータを用いた位置推定結果と修正データを用いた位置推定結果を図 4 に示す．図の (x_truth, y_truth)・(x,次に，Local Optimum アルゴリズムにおいて，s = (−5, +5) おy)・(x’, y’) は，それぞれ正解データ・クリーニング前のデータ・よび s = (−90, +90) の２つの場合について，応答時間と修正精Local Optimum アルゴリズムでの修正データの (x, y) 座標を表度の関係を測定した．結果を図 3 に示す．

している．
図 4 の修正後のから，速度制約を満たすようにデータを修正したことで，信頼性の低いセンサを用いた場合でも，ある程度正解データに近い推定を行うことができたことが読み取れる．
一方，y 座標，Local Optimum アルゴリズムでは，ウィンドウ幅

x_truthy_truthxyx'の手法においても，修正精度は 6 割に満たなかった．また，図y'࠴ඬ [m]

104 から，修正後のデータと正解データの間には依然として距離50があることが読み取れる．この結果から，修正前のデータの大-5部分が修正対象とみなされる場合，速度制約の「制約を満たす-100102030405060

データは移動しないようにする」という性質を活用して修正精70‫ܨ‬գ࣎ؔ [භ]

度を向上することは困難であるとわかる．実タスクにデータク

図 4 正解データとクリーニング前後の位置推定結果の比較リーニングを適用するためには，データに含まれるエラーの割合が少なくとも半分以下になるような信頼性の高いセンサを利表1

位置推定タスクにおけるデータクリーニングの効果

手法

修正距離 修正精度用する必要があると考えられる．

RMS Error 精度改善率

修正前--6.31

1

Local6723

0.59

5.39

1.17

Global

15816

0.52

10.08

0.63

4. お わ り に本研究では，性能要件の厳しい現実のオンライン処理に対してデータクリーニングを行うことを目的として，応答時間を考慮したストリームデータクリーニング手法について考察した．

また，この時の修正距離・修正精度，RMS Error，制度改善率を表 1 にまとめる．表 1 における Local は Local Optimum アルゴリズム，Global は Global Optimum アルゴリズムを表し，精度改善率は，修正前の RMS Error を１とした場合の，修正後のRMS Error の改善率を示している．
表に示すとおり，Local Optimum アルゴリズムでデータクリーニングを行うことにより，位置推定精度が向上することが分かった．一方，Global Optimum は，クリーニング時間が 30分を経過した時点で解の探索が終了せず，推定精度が低下する

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

結果となった．

3. 3 考察

実験１および実験２を通じて，ストリームデータクリーニン
グ手法がオンライン処理の精度向上に有効であることが示された．一方，本実験を通じて以下の課題も明らかとなった．

•

無限のウィンドウ幅を用いたクリーニング結果をもって正解データの代わりとすることは妥当ではない．実験１では，速度制約が強い場合を除き，ウィンドウ幅が大きいほど修正精度が低下する傾向を示した．これは，ウィンドウ幅が大きいほど，ウィンドウ内に多くのエラー値を含むことになり，未来の値を用いる既存手法では，エラーの影響を強く受けてしまうことが原因と考えられる．また実験２の結果から，Global Optimum
アルゴリズムは現実的な時間で解を探索できないため，正解データを生成することは困難であるといえる．

•速度制約は，変動幅の変化するデータに対する効果が小さい．実験１で使用した株価データは，最小値付近の日付では１日あたりの変動幅が 1.8 以下であるのに対して，最大値付近では１日あたりの 90 近く変動する可能性がある．そのため，変文

献[1] P. Bohannon, W. Fan, M. Flaster, and R. Rastogi. A cost-based modeland eﬀective heuristic for repairing constraints by value modification.
In SIGMOD, pp. 143–154, 2005.
[2] S. R. Jeﬀery, 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. Bischoﬀ, R. Laur, and S. Paul. Localization in wirelessad-hoc sensor networks using multilateration with rssi for logisticapplications. 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]タクリーニングにより位置推定精度を向上できることを確認でを x i ，t[i] を t i と表記する．ある時刻間隔（ウィンドウ）w にきた．一方，Local Optimum および Global Optimum のいずれ

おける x に対する速度制約を s = (s min, s max ) とする．s min は•最低速度， s max は最高速度を表す．

n∑minx k が速度制約 s を満たすとき， x k |= s と表記する．すなわ
ち， x k |= s のとき， x k 以降の任意の点 x i (t k < t i <= t k + w) にx −xs max , t k < t i <= t k + w, 1 <=i<=ntk − ti =x に対する修正 x ′ とは，t i′ = t i における値 x i の x i′ への変更

x k′ − x i′> s min, t k < t i <= t k + w, 1 <=i<=ntk − ti =を表す．データ修正における修正距離は，最少変更原理に基づき，元の x と修正後の x ′ の距離によって，次式のように定義される．

(A·2)

i=1x k′ − x i′
<s.t.

ik
ついて， s min <= ti −tk <= s max が成り立つ．

|x i − x i′ |データ修正とは，式 (A·2) を満たす x i′ (1 <= n) を求めるこ=i<とである．

∆(x, x ′ ) =∑xi ∈x|x i − x i′ |(A·1)

Algorithm 1 Local(x, s)
Require: x, 時刻で整列済みの系列; s, 速度制約

例として，６点からなる系列 x = {12, 12.5, 13, 10, 15, 15.5}, t =Ensure: x ′ , x の修正{1, 2, 3, 5, 7, 8} を考える．図 A· 1 における黒色の点は系列 x を

1: for k ← 1 から n に対して do表す．系列 x の速度制約を s max = 0.5， s min = −0.5 とする．

2:
3:

Valuex6

smax′x kmi n ← x k−1+ smi n (tk − tk−1 ), または k = 1 に対して − ∞;4:

′x kma x ← x k−1+ sma x (tk − tk−1 ), または k = 1 に対して + ∞;5:

for i ← k + 1 から n に対して do

6:

x’i+1

Xkmi n ← ∅; Xkma x ← ∅;if ti > tk + w then
ループを抜ける ;7:xix’’i+1

x1

smin

xi+1
ti

w

ti+1

t6

Time

8:

end if

9:

Xkmi n ← Xkmi n ∪ {xi + smi n (tk − ti ) };10:

Xkma x ← Xkma x ∪ {xi + sma x (tk − ti ) };11:

end for12:

x kmi d ← median(Xkmi n ∪ Xkma x ∪ {x k });13:

if x kma x < x kmi d then

14:
15:

図 A· 1

速度制約下における修正候補

16:
17:

ウィンドウ幅が w = 2 のとき，点 x 3 と x 4（時刻間隔は 5−3 <=2）は，速度制約における s min = −0.5 を違反している．なぜならば，x 3 ，x 4 間の速度について， 10−13
5−3 = −1.5 < −0.5 が成り立

18:
19:

x k′ ← x kma x ;else if x kma x > x kmi d thenx k′ ← x kmi n ;else
x k′ ← x kmi d ;end if

20: end for
21: return x ′つからである．同様に， x 4 と x 5 間の速度は 15−10
7−5 = 2.5 > 0.5であり， s max = 0.5 を違反している．
この 2 つの違反（図 A· 1 における破線部）を矯正するために，例えば， x 4 を x 4′ = 14（図 A· 1 における白色の点）に修正することができる．図 A· 1 に示すとおり，修正後の系列は，最高速度・最低速度の速度制約をともに満たしている．このとき，修正距離は ∆(x, x ′ ) = |10 − 14| = 4 である．
もしウィンドウ幅が非常に小さい（例えば w = 1）ならば，x 3 と x 4 間（ x 4 と x 5 間）の違反は発見できない．なぜならば，時刻間隔が 2 > 1 となるからである．一方，ウィンドウ幅が十分に大きい（例えば w = 10）ならば，系列 x 内のすべての点の組を比較しなければならない．同じ修正 x ′ を行うことができたとしても，計算のオーバーヘッドは明らかに大きくなる．ゆえに，修正精度と効率の釣り合いをとるためには，適切なウィンドウ幅を設定する必要がある．
このデータ修正問題は，以下のように定義できる．

Algorithm 1 に，既存手法における速度制約 s のもとで系列 xを x ′ に修正するデータ修正アルゴリズムを示す．このアルゴリズムは，ある点 x k の修正において， x k+1 から x n の範囲でウィンドウ幅 w 内に存在する点を用いる（５〜１１行目）．