Математики! Аппроксимация среднего значения без сохранения всего набора данных - PullRequest
Новая
       11

Математики! Аппроксимация среднего значения без сохранения всего набора данных

0 голосов
/ 10 января 2011

Очевидное (но дорогое) решение:

Я бы хотел сохранить рейтинг трека (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)

и сохраняется как новое Rating значение TrackID. Теперь, когда требуется Rating, это простой поиск, а не расчет.

Ясно, что это не вычисляет среднее. Я пробовал несколько небольших наборов данных, и это приближает среднее значение. Я полагаю, что это может сходиться по мере увеличения набора данных? Но я боюсь, что это может расходиться!

Что вы, ребята, думаете? Спасибо!

Ответы [ 5 ]

8 голосов
/ 10 января 2011

Предполагая, что у вас была бесконечная числовая точность, этот расчет корректно обновляет среднее значение. На практике вы, вероятно, используете целочисленные типы, поэтому оно не будет точным.

Как насчет хранения кумулятивного подсчета голосов и количества голосов? (т.е. total=total+vote, numVotes=numVotes+1). Таким образом, вы можете получить точное среднее значение, разделив одно на другое.

Этот подход будет нарушен, только если вы наберете столько голосов, что переполните диапазон используемого вами типа данных. Поэтому используйте большой тип данных (32-битного должно быть достаточно, если вы не ожидаете ~ 4 миллиарда голосов)!

3 голосов
/ 10 января 2011

Храните TrackId, RatingSum, NumberOfVotes в вашей таблице.

Каждый раз, когда кто-то голосует,

  • NumberOfVotes = NumberOfVotes + 1
  • RatingsSum = RatingsSum + [рейтинг предоставлен пользователем]

Тогда при выборе 

SELECT TrackId, RatingsSum / NumberOfVotes FROM ...
2 голосов
/ 10 января 2011

Вы, конечно, можете рассчитать среднее значение и стандартное отклонение, не имея при этом всех точек.Вам просто нужно накопить сумму, сумму квадратов и количество очков.

Это не приближение;среднее значение и стандартное отклонение являются точными.

Вот класс 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; }
}
2 голосов
/ 10 января 2011

Ваше решение полностью законно.и отличается лишь приблизительно в несколько раз точностью с плавающей запятой от значения, рассчитанного на основе полного исходного набора.

1 голос
/ 10 января 2011

Небольшое улучшение вашего решения. У вас есть таблица: 

TrackID
SumOfVotes
NumberOfVotes

Когда кто-то голосует, 

NumberOfVotes = NumberOfVotes + 1
SumOfVotes = SumOfVotes + ThisVote

и для просмотра среднего вы только затем делите: 

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

Я бы добавил, что исходное (очевидное и дорогое) решение является дорогостоящим по сравнению с предоставленным решением при расчете среднего. Это дешевле, когда голос добавлен, удален или изменен. Я предполагаю, что оригинальная таблица 

TrackID
Vote
VoterID

все равно необходимо будет использовать в предоставленном решении для отслеживания голосов (рейтинга) каждого избирателя. Итак, две таблицы должны обновляться для каждого изменения в этой таблице (вставка, удаление или обновление голосования).

Другими словами, оригинальное решение может быть лучшим путем.

...