数学！近似均值，而不存储整个数据集

问题描述：

我想用来存储轨道（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时，这是一个简单的查找，而不是计算。

显然，这并不计算平均值。我已经尝试了一些小数据集，并且接近平均值。我相信随着数据集的增加，它可能会收敛？但我担心它可能会发生分歧！

你们认为什么？谢谢！

答

假设您具有无限的数字精度，则该计算会正确更新均值。实际上，你可能使用整数类型，所以它不是确切的。

如何存储累计投票数和投票数？（即，total=total+vote,numVotes=numVotes+1）。这样，你可以通过一个除以另一个来得到确切的均值。

这种方法只会在您得到如此多的选票时溢出您所使用的数据类型的范围。因此，使用大数据类型（32位应该足够了，除非您预计会有〜40亿票）！

现在很明显，您提到它了！感谢Oli :-) – 0atman 2011-01-10 10:55:36

答

您的解决方案是完全合法的。并且从完整源集合计算出的值的差别仅为浮点精度的几倍。

答

商店TrackId,RatingSum,NumberOfVotes在您的表中。

每当有人票，

NumberOfVotes = NumberOfVotes + 1
RatingsSum = RatingsSum + [由用户提供的评价]

然后选择时

SELECT TrackId, RatingsSum/NumberOfVotes FROM ...

答

你的sol的小改进ution。你有表：

TrackID 
SumOfVotes 
NumberOfVotes

当有人票，

NumberOfVotes = NumberOfVotes + 1 
SumOfVotes = SumOfVotes + ThisVote

，并看到平均只有这样，你做了分工：

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

我想补充的是，原来的（明显和昂贵的）解决方案相比，在计算平均值时提供的解决方案相对昂贵。投票被添加，删除或更改时更便宜。我想这原始表

TrackID 
Vote 
VoterID

仍然需要在所提供的解决方案，可用于跟踪每个选民的选票（等级）。因此，对于此表中的每项更改（插入，删除或投票更新），都必须更新两个表。

换句话说，最初的解决方案可能是最好的方法。

答

您当然可以计算跑步平均数和标准差，而不必掌握所有的关键点。你只需要累积总和，平方和和点数。

这不是一个近似值;平均值和标准差是确切的。

这是一个演示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; } 
}

数学！近似均值，而不存储整个数据集

相关推荐