2896


逐次的に平均値を求めるアルゴリズムは[指数平滑平均](http://qiita.com/awakia/items/f58e90b3b2562d787aa5)として知られていますが、同様に逐次的に中央値を求めるアルゴリズムはありませんか？


CC BY-SA 3.0
2015-01-01T08:28:36.073
2893
2015-01-01T13:52:20.870
2015-01-01T08:39:15.913
question
アルゴリズム
逐次的に中央値を求める方法はありませんか


メモリにすべてのデータを置かなくて良いという意味では、方法はないというのが答えだと思います。

中央値はその性質上各データが重要な意味を持ちます。

例えば、1,2,3というデータがあって中央値2となっているのと、1,2,10というデータがあって中央値2となっているのの区別が付きません。例えば次に4という値が来た時に、2より大きい方の3や10と言ったデータは必要になってしまう事が想像出来るかと思います。

ここで、いくつか本当に必要の無いデータはないのかと考えても、後に、現在出てきたデータより小さいデータや大きいデータが出続けた場合、現在持っているデータの全てが中央値になる可能性があるのでデータを捨てることができません。

メモリにデータを載せて良いという話なら、平衡二分木でデータを管理すればO(logN)で中央値を求めることは出来るはずです。


CC BY-SA 3.0
2015-01-01T09:25:26.220
2895
2015-01-01T09:25:26.220
5962
2893
answer


整数に限定されますが、stats.stackoverflow に  
[同様の質問があり](https://stats.stackexchange.com/questions/10539/compute-
approximate-quantiles-for-a-stream-of-integers-using-moments)、  
[論文:Effective Computation of Biased Quantiles over Data
Streams](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.853&rep=rep1&type=pdf)  
へのリンクが有りました。

あと実装としては  
[stream-lib の quantile](https://github.com/addthis/stream-
lib/tree/master/src/main/java/com/clearspring/analytics/stream/quantile)  
などがその用途で近似できたはずです。

記憶では他にも幾つか似たようなライブラリがあったと記憶していますが、具体的なことは現時点では思い出せません。 `percentile` や
`quantile` などのキーワードを中心に検索すると、多少なりとも見つかると考えられます。


CC BY-SA 3.0
2015-01-01T09:29:16.193
2896
2015-01-01T09:29:16.193
2017-04-13T12:44:19.937
-1
208
2893
answer


正確な中央値を逐次的に割り出したければ、全ての要素が復元可能な情報をどこかに蓄積しておかなければなりません。通常の方法で中央値をピックするには:

> 「全ての要素を順に並べたリストを作りつつ、中央の値を取得する」

とするのがよいです。効率の良いものは、クイックソートを途中までやって諦める方法でしょう。リニアになりますが、ピックの時間が、O(n)~O(1)で行えます。("median
of medians" とかで検索してみてください)

質問にあるような状況で、逐次的に処理したく、かつ、全てのデータを蓄積してよいなら:

> 「順に並べたリストに新しい要素を追加し、中央の値を取得する」

ことになるでしょう。今度は挿入のコストを考える必要があります。効率の良いものは、二分木に値を追加し、中央値を探索する方法です。中央値取得のみを目的にしたデータ構造ではないのですが、[Order
statistic
tree](http://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatisticsTree.html)
が使えます。二分探索木のノードにランク／深さデータを付加したもので、最適な状態（平衡木であれば）、追加及び探索コストが、それぞれ
O(log(n))に近くなり良い感じです。Python だと、
[blist](http://stutzbachenterprises.com/blist/) に実装があります。

情報を蓄積せずに中央値を割り出したいとなれば:

> 「入力データから逐次割り出していた統計値から、中央値を点推定する」

こととなりますが、中央値は分布によって大きく傾く値なので、データの種類によってやり方が異なってきそうです。確認はしていないのですが、[KoRoN
さんの提示された方法](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.853&rep=rep1&type=pdf)は入力データの偏り情報も保持しておくことで、不正確さを小さくできる方法の一つでしょう。データの大きさが未知であるストリーミングに良い方法だと思います。


CC BY-SA 3.0
2015-01-01T13:52:20.870
2911
2015-01-01T13:52:20.870
4978
2893
answer