1. 序章


このチュートリアルでは、データストリームの中央値を計算するための2つのアルゴリズムを紹介します。


2. ストリームの中央値








確率変数の中央値は、の範囲を半分に分割する値です。半分は、より小さく、もう半分はそれより大きくなります。


      


から抽出されたサンプルの中央値を決定するために、サンプルの順序統計を取得するためにそれを並べ替え、サンプルの中央値として中央値を選択します。


      




ただし、この式は、サンプルがソート可能であることを前提としています。 つまり、メモリに保存して、複数回パスすることができます。


2.1. データストリーム


サンプルがビッグデータストリームの場合はそうではありません。 このような場合、要素が利用可能になり次第、ストリームから要素を1つずつ読み取ります。 さらに、それらをメモリに保持すると、ストリームが終了する前にメモリが不足していました。 そのため、ストリーム全体を効果的に保存または並べ替えることはできません。また、要素を読み取った後、保存しない限り、要素に再度アクセスすることはできません。 残念ながら、ストリーム全体を保持するのに十分なメモリがありません。 これらの理由により、通常の方法で中央値を決定することはできません。


代わりに、データストリームに特化したストリーミングアルゴリズムを使用します。 設計上、これらは、アルゴリズムの実行中の任意の時点でストリームの一部のみを格納できる低メモリ環境で実行されます。 これらの制約を尊重するために、 ストリーミングアルゴリズムは、メモリの複雑さを低くするために精度を犠牲にします。  S o、オフラインアルゴリズムが返す推定値を返しません。 目標は、可能な限り高い精度を維持しながら、時間とスペースの複雑さを軽減することです。


3. 対称データ


データが対称的に分布している場合、それらの中央値はそれらの平均に等しくなります。 したがって、ストリーミング平均を計算することで中央値を見つけることができます。






このアルゴリズムはメモリが複雑で、時間内に実行されます。 ただし、データが通常または均一などの対称分布に従うことを保証できない場合は、ストリーミング平均を使用して中央値を推定するべきではありません。 代わりに、などの分位数推定ストリーミングアルゴリズムを使用できます。


4. アルゴリズム


（）の分位数は、の分布よりも大きい値です。


      


中央値は分位数であるため、アルゴリズムなど、ストリーミング分位数の推定には任意の方法を使用できます。 中央値の場合（）で提示します。


4.1. 5つのマーカー


中央値を見つけるには、ストリームの読み取り中に5つのマーカーを維持します。


    

  • 、最小
    • 

  • 、-分位
    • 

  • 、-分位
    • 

  • 、-分位
    • 

  • 、最大値（-分位数）
    • 



とは、中央値と極値の間にあるため、中間マーカーと呼ばれます。 アイデアは、ストリームを読み取るときにマーカーを更新することです。 最後に、の現在の値を返します。


4.2. 更新ステップ


それぞれがに関連付けられており、これまでに観測された要素の数は現在（）を超えません。 理想的には、任意のポイントでほぼ等しくなります。ここで、はストリームから読み取った要素の数であり、マーカーが表す分位数を決定します（）。 より正確に：


      


新しい要素を読み取るとき、、は、以上のすべてのマーカーので増加します。 newが理想値と少なくとも1だけ異ならない場合、更新は行われません。 それ以外の場合は、区分的放物線（PPまたは）式（アルゴリズムの名前の由来）を使用して更新します。 調整する場合は、次のセクションで説明するように変更します。


4.3. 区分的放物線調整


隣接する3つのマーカーを通過する曲線は、放物線であると想定しています。


      


つまり、2次関数は、任意の3つのマーカー間の基礎となるCDFの十分な近似であると想定しています。


理想的なsは実際のスケールですが、実際のsは整数です。 更新されたものとの違いがである場合、何もしません。 それ以外の場合は、次のように更新します。


 (1)    


ここで、つまり、差が。の場合、および差が。の場合。


調整する場合は、次のようにも調整します。


      


4.4. 技術的注意


調整式はにのみ適用されます。 最小値に対応する最初のマーカーは、それが新しい最小値である場合に置き換えられます。 最大マーカーについても同じことが言えます。 、、、およびの場合のように、それらの値を調整しません。


すべてのsが異なっている必要があります。 したがって、調整によって2つが等しくなる場合、それは適用されません。 また、sは減少しない（）である必要があります。 放物線調整が順序に違反している場合は、代わりに線形代替を使用します：


 (2)    


最後になりましたが、最初の5つの要素を使用してマーカーを初期化するため、マーカーを更新または調整しません。 したがって、アルゴリズムの主要部分は。で始まります。


4.5. 擬似コード


ここでは、次の擬似コードを示します。




4.6. 考えられる改善とトレードオフ


それはかなりうまく機能することがわかりました。 その理由は、 2次曲線は、データが実際にたどる実際のCDFの十分に正確な区分的近似であるためです。 高次の曲線はさらに良い推定値を提供する可能性がありますが、改善された精度は、数学的な複雑さと計算負荷の増加に値しない可能性があります。


5つのマーカーが3つ（最小、ターゲット、最大）よりもうまく機能するように、 7つのマーカーにより、おそらくより正確な推定が可能になります。 ただし、より多くのマーカーを使用すると、アルゴリズムの速度が低下します。


4.7. 複雑


のスペースの複雑さは、一定数のマーカーを使用するためです。 時間の複雑さは、ストリームを1回読み取るためです。


5. 例


次のストリームでデモンストレーションしましょう。


      


5.1. 初期化


最初の5つの数値を読み取って並べ替え、sとs（）を初期化します。


      


以来、理想的な値は次のとおりです。


      


5.2. 6番目の要素を読む


今、私たちは読みます。 以来、理想的な値は次のように変化します。


      


実際の値も同様です。


      


絶対差はないので、更新しません。


5.3. 7番目の要素を読む


今、私たちは読みます。 以前と同様に、理想的な値は次のように変化します。


      


そして実際のものもそうです：


      


となので、更新する必要があります。 （および）の放物線式を使用すると、次のようになります。


      


以来、放物線調整を受け入れます。 も更新します。 同じロジックがに適用されます。


6. 結論


この記事では、ビッグデータストリームの中央値を見つけるための2つのアルゴリズムを紹介しました。最初に、データが対称である場合、対称分布の中央値と平均が同じであるため、ストリーミング平均アルゴリズムを実行します。 。 それ以外の場合は、ストリーミング分位数を推定するために設計された多くの方法の1つであるを使用できます。この方法の中央値は、特殊なケースです。