全体のデータを格納することなく、平均値を近似するには、設定

Question

明白な（しかし高価な）解決策：

私はこのような表にトラック（1-10）の評価を保存したいと思い

：

TrackID 
Vote 

そして、平均値を計算するための簡単な

SELECT AVERAGE(Vote) FROM `table` where `TrackID` = some_val 

。

しかし、私はスケーラビリティについて懸念しています。特に毎回再計算する必要があるためです。

案が、おそらく愚かな、解決策は：

TrackID 
Rating 
NumberOfVotes 

誰かが投票するたびに、Ratingは

new_rating = ((old_rating * NumberOfVotes) + vote)/(NumberOfVotes + 1) 

で更新し、TrackIDの新しいRating値として保存されます。今度はRatingが欲しいときは、計算ではなく簡単なルックアップです。

明らかに、これは平均を計算しません。私はいくつかの小さなデータセットを試しました、そしてそれは平均に近似します。私はそれがデータセットが増えるにつれて収束するだろうと信じていますか？しかし、私はそれが発散するかもしれないと心配です！

あなたはどう思いますか？ありがとう！

Answer 1

数値精度が無限であると仮定すると、その計算では平均が正しく更新されます。実際には、おそらく整数型を使用しているので、正確ではありません。

累積投票数と投票数の保存はどうですか？ （すなわち、total=total+vote,numVotes=numVotes+1）。そうすれば、正確な平均値を1つずつ除算することができます。

このアプローチは、使用しているデータ型の範囲をオーバーフローさせるほど多くの票が得られた場合にのみ壊れます。したがって、大きなデータ型を使用してください（40億票を期待していない限り、32ビットで十分であるはずです）！

Answer 2

あなたのソリューションは完全に正当です。完全なソースセットから計算された値から浮動小数点精度のおよそ数倍だけdifferesします。

Answer 3

TrackId、RatingSum、NumberOfVotesをテーブルに保存します。

たびに誰かの投票、

• NumberOfVotes = NumberOfVotes + 1
• RatingsSum = RatingsSum + [ユーザーが入力格付け]

その後

SELECT TrackId, RatingsSum/NumberOfVotes FROM ... 

Answer 4

を選択

ゾルの小さな改善ution。あなたは、テーブルを持っている：

TrackID 
SumOfVotes 
NumberOfVotes 

誰かの投票、

NumberOfVotes = NumberOfVotes + 1 
SumOfVotes = SumOfVotes + ThisVote 

、あなたがだけにして除算を行う平均参照するには：

SELECT TrackID, (SumOfVotes/NumberOfVotes) AS Rating FROM `table` 

を元の（明白なことを私は追加します高価な）ソリューションは、平均を計算する際には、証明されたソリューションに比べて高価です。 投票が追加、削除、変更された場合は安いです。 私は、元のテーブル

TrackID 
Vote 
VoterID 

は、まだすべての有権者の投票（レーティング）を追跡するために提供するソリューションで使用される必要があるだろうと思います。つまり、このテーブルの変更ごとに2つのテーブルを更新する必要があります（挿入、削除、または投票の更新）。

つまり、元の解決策が最良の方法です。

Answer 5

すべてのポイントを手に入れることなく、実行中の平均と標準偏差を確かに計算できます。合計、二乗和、およびポイント数を累積するだけです。

これは近似値ではありません。平均と標準偏差は正確です。

ここに示すJavaクラスがあります。必要に応じてSQLソリューションに対応することができます。

package statistics; 

public class StatsUtils 
{ 
    private double sum; 
    private double sumOfSquares; 
    private long numPoints; 

    public StatsUtils() 
    { 
     this.init(); 
    } 

    private void init() 
    { 
     this.sum = 0.0; 
     this.sumOfSquares = 0.0; 
     this.numPoints = 0L; 
    } 

    public void addValue(double value) 
    { 
     // Check for overflow in either number of points or sum of squares; reset if overflow is detected 
     if ((this.numPoints == Long.MAX_VALUE) || (this.sumOfSquares > (Double.MAX_VALUE-value*value))) 
     { 
      this.init(); 
     } 

     this.sum += value; 
     this.sumOfSquares += value*value; 
     ++this.numPoints; 
    } 

    public double getMean() 
    { 
     double mean = 0.0; 

     if (this.numPoints > 0) 
     { 
      mean = this.sum/this.numPoints; 
     } 

     return mean; 
    } 

    public double getStandardDeviation() 
    { 
     double standardDeviation = 0.0; 

     if (this.numPoints > 1) 
     { 
      standardDeviation = Math.sqrt((this.sumOfSquares - this.sum*this.sum/this.numPoints)/(this.numPoints-1L)); 
     } 

     return standardDeviation; 
    } 

    public long getNumPoints() { return this.numPoints; } 
}