データマイニングにおけるランダム化アルゴリズムとデータストリーム管理システム（DSMS）とは

ランダム化アルゴリズムとは

ランダム化アルゴリズムは、ランダムサンプリングやスケッチングといった手法の形で、大規模かつ高次元のデータストリームを扱うために活用されています。ランダム性を取り入れることで、既存の決定論的アルゴリズムと比べて、よりシンプルかつ効率的なアルゴリズムを実現できる点が大きな特徴です。

ラスベガス型とモンテカルロ型

ランダム化アルゴリズムには大きく分けて2つのタイプがあります。常に正しい答えを返すものの実行時間が変動するアルゴリズムはラスベガス型と呼ばれます。一方、モンテカルロ型は実行時間に上限が定められている代わりに、必ずしも正しい結果を保証できないという特性を持ちます。実際の応用では、モンテカルロ型のアルゴリズムが広く採用されています。

概念的には、ランダム化アルゴリズムとは「決定論的アルゴリズムの集合上に確率分布を定義したもの」と捉えることができます。

チェビシェフの不等式

ランダム化アルゴリズムは結果として確率変数を返すため、その確率変数の裾確率（期待値から大きく外れる確率）に上界を設けることが可能です。つまり、確率変数が期待値から乖離する確率は小さいと言えます。この分析における主要な道具となるのがチェビシェフの不等式です。

平均 μ、標準偏差 σ（分散 σ²）を持つ確率変数 X に対して、チェビシェフの不等式は次のように表されます。

$$\mathrm{P(|X-\mu|>k)<\frac{\sigma^2}{k^2}}$$

ここで k は任意の正の実数です。この不等式により、確率変数の分散をもとに誤差の発生確率を評価できます。さらに、複数の独立な確率変数を組み合わせることで結果の信頼度を高められる場合があり、その際にはチェルノフ境界が有効です。

チェルノフ境界

X₁, X₂, …, Xₙ を互いに独立なポアソン試行とします。ポアソン試行とは、成功確率が試行ごとに異なり得る試行のことです。X を X₁ から Xₙ までの総和とするとき、チェルノフ境界の弱い形式は次のように与えられます。

$$\mathrm{P[X<(1+\delta)\mu]<e^{-\mu\delta^2}}$$

ここで δ ∈ (0, 1] です。この式が示すように、平均から離れるほど確率は指数関数的に減少します。その結果、極端に不正確な推定値が得られる可能性は非常に低くなります。

データストリーム管理システム（DSMS）とは

データストリーム管理システムでは、複数のデータストリームを扱います。これらのストリームはオンラインで到着し、連続的・時系列的であり、理論上は無限に続き得るという特性を持ちます。ストリームの各要素は処理された後、破棄されるかアーカイブされるため、明示的にメモリへ保存しない限り、後から再取得することはできません。

クエリ処理の構造

ストリームデータのクエリ処理アーキテクチャは、次の3つの要素で構成されます。

• エンドユーザー：DSMSに対してクエリを発行する
• クエリプロセッサ：クエリを受け取り、スクラッチスペースに保持されたデータを用いて処理し、結果をユーザーへ返す
• スクラッチスペース：メインメモリやディスクを含む作業領域

一回限りのクエリと連続クエリ

DSMSにおけるクエリには2種類あります。一回限りのクエリは、ある時点のデータセットのスナップショットに対して一度だけ計算が実行され、その結果がユーザーに返されます。一方、連続クエリは、データストリームが到着し続ける限り、継続的に計算が繰り返されるクエリです。リアルタイム性が求められるストリーム処理では、連続クエリが中心的な役割を果たします。