データマイニングにおけるランダム化アルゴリズムとデータストリーム管理システムとは何ですか？

ランダム化アルゴリズム −ランダムサンプリングとブループリントの形式のランダム化されたアルゴリズムは、大規模で高次元のデータストリームを処理するために使用されます。ランダム化の必要性は、既知の決定論的アルゴリズムとは対照的に、より単純でより効果的なアルゴリズムにつながります。

ランダム化されたアルゴリズムが継続的に正しい答えを返すが、実行時間が変化する場合、それはラスベガスアルゴリズムと呼ばれます。対照的に、モンテカルロアルゴリズムには実行時間に制限がありますが、実際の結果を復元することはできません。通常、モンテカルロアルゴリズムを考慮することができます。ランダム化アルゴリズムの重要性は、決定論的アルゴリズムのグループ全体の確率分布として単純です。

ランダム化されたアルゴリズムが結果として確率変数を復元することを考えると、その確率変数のテール確率に限界がある可能性があります。これは、確率変数がその期待値から変化する確率が短いことを示しています。主なツールはチェビシェフの不等式です。

Xを、平均µと標準偏差σ（分散σ ² ）を持つ確率変数とします。 ）。チェビシェフの不等式はそれを言います

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

任意の正の実数に対して、k。この不等式は、確率変数の分散を制限するために使用されます。場合によっては、複数の確率変数を使用して、この結果の信頼性を向上させることができます。これらの確率変数が完全に独立していることを考慮すると、Chernoff境界を使用できます。

X ₁ X ₂ …x_n 独立したポアソン試行である。ポアソン試行では、成功の確率は試行ごとに異なります。 XがX₁の合計である場合 X _nへ 、その後、Chernoffバウンドの弱いバージョンは私たちにそれを伝えます

$$ \ mathrm {P [X <（1+ \ delta）\ mu]

ここで、δ∈（0、1]。これは、確率が平均から移動できるため、確率が指数関数的に減少することを示しています。これにより、推定値が低くなる可能性ははるかに低くなります。

データストリーム管理システム −データストリーム管理システムには、いくつかのデータストリームがあります。それらはオンラインで表示され、連続的で時間的に連続しており、場合によっては無限です。データストリームのコンポーネントは処理されているため、破棄またはアーカイブされ、明示的にメモリに保存されない限り、単純にフェッチすることはできません。

ストリームデータクエリ処理構造には、エンドユーザー、クエリプロセッサ、スクラッチスペース（メインメモリとディスクを含めることができます）などの3つの要素が含まれます。エンドユーザーはDSMSへのクエリに関心があり、クエリプロセッサはクエリを受け取り、スクラッチスペースに保存されたデータを使用してクエリを処理し、結果をユーザーに復元します。

クエリは、1回限りのクエリでも継続的なクエリでもかまいません。 1回限りのクエリは、データセットの特定の時点の写真に対して1回計算され、回答がユーザーに復元されます。データストリームが表示され続けると、継続的なクエリが継続的に計算されます。