Calculate trendline and predict future results

Question

I'm writing some analytics modules for the site I'm working on and I need to estimate the total views after the current hour. I have data for every minute up to the current minute, so if the time is 12:28, I will have an array that looks something like this:

0: "21410"
1: "21886"
2: "21837"
3: "21895"
4: "21564"
5: "21714"
6: "21571"
7: "21324"
8: "21310"
9: "21390"
10: "21764"
11: "21598"
12: "21493"
13: "21352"
14: "21478"
15: "21058"
16: "20942"
17: "20825"
18: "21321"
19: "20950"
20: "21039"
21: "21117"
22: "20733"
23: "20773"
24: "20929"
25: "20900"
26: "20687"
27: "20999"

Currently I am projecting the hour's value like this:

(60/minsSoFar)*totalSoFar

This works reasonably well, but I'd rather do it a bit more mathematically. I'd like to calculate the line of best fit for the data I have so far and project that up to the 60th minute. This would take into account acceleration and deceleration.

With the method I'm currently using, I'm effectively assuming the trend is a straight line. How would I calculate the formula for a polynomial or power trend?

I'm writing this in NodeJS so JavaScript would be ideal, but I'll take pseudocode too!

Here's the array in an easier format in case you want it:

[21410, 21886, 21837, 21895, 21564, 21714, 21571, 21324, 21310, 21390, 21764, 21598, 21493, 21352, 21478, 21058, 20942, 20825, 21321, 20950, 21039, 21117, 20733, 20773, 20929, 20900, 20687, 20999]

Thanks for any help!

Didactic

You are probably going to want to start here en.wikipedia.org/wiki/Curve_fitting – Shovelnose

Answer 1

You can do a least-squares fit of a line.

function LineFitter()
{
    this.count = 0;
    this.sumX = 0;
    this.sumX2 = 0;
    this.sumXY = 0;
    this.sumY = 0;
}

LineFitter.prototype = {
    'add': function(x, y)
    {
        this.count++;
        this.sumX += x;
        this.sumX2 += x*x;
        this.sumXY += x*y;
        this.sumY += y;
    },
    'project': function(x)
    {
        var det = this.count * this.sumX2 - this.sumX * this.sumX;
        var offset = (this.sumX2 * this.sumY - this.sumX * this.sumXY) / det;
        var scale = (this.count * this.sumXY - this.sumX * this.sumY) / det;
        return offset + x * scale;
    }
};

function linearProject(data, x)
{
    var fitter = new LineFitter();
    for (var i = 0; i < data.length; i++)
    {
        fitter.add(i, data[i]);
    }
    return fitter.project(x);
}

Example:

>>> linearProject([
        21410, 21886, 21837, 21895, 21564, 21714, 21571, 21324, 21310, 21390,
        21764, 21598, 21493, 21352, 21478, 21058, 20942, 20825, 21321, 20950,
        21039, 21117, 20733, 20773, 20929, 20900, 20687, 20999
    ], 60);
19489.614121510676

---

Doing something similar for a square polynomial is a little more complicated:

function SquareFitter()
{
    this.count = 0;
    this.sumX = 0;
    this.sumX2 = 0;
    this.sumX3 = 0;
    this.sumX4 = 0;
    this.sumY = 0;
    this.sumXY = 0;
    this.sumX2Y = 0;
}

SquareFitter.prototype = {
    'add': function(x, y)
    {
        this.count++;
        this.sumX += x;
        this.sumX2 += x*x;
        this.sumX3 += x*x*x;
        this.sumX4 += x*x*x*x;
        this.sumY += y;
        this.sumXY += x*y;
        this.sumX2Y += x*x*y;
    },
    'project': function(x)
    {
        var det = this.count*this.sumX2*this.sumX4 - this.count*this.sumX3*this.sumX3 - this.sumX*this.sumX*this.sumX4 + 2*this.sumX*this.sumX2*this.sumX3 - this.sumX2*this.sumX2*this.sumX2;
        var offset = this.sumX*this.sumX2Y*this.sumX3 - this.sumX*this.sumX4*this.sumXY - this.sumX2*this.sumX2*this.sumX2Y + this.sumX2*this.sumX3*this.sumXY + this.sumX2*this.sumX4*this.sumY - this.sumX3*this.sumX3*this.sumY;
        var scale = -this.count*this.sumX2Y*this.sumX3 + this.count*this.sumX4*this.sumXY + this.sumX*this.sumX2*this.sumX2Y - this.sumX*this.sumX4*this.sumY - this.sumX2*this.sumX2*this.sumXY + this.sumX2*this.sumX3*this.sumY;
        var accel = this.sumY*this.sumX*this.sumX3 - this.sumY*this.sumX2*this.sumX2 - this.sumXY*this.count*this.sumX3 + this.sumXY*this.sumX2*this.sumX - this.sumX2Y*this.sumX*this.sumX + this.sumX2Y*this.count*this.sumX2;
        return (offset + x*scale + x*x*accel)/det;
    }
};

function squareProject(data)
{
    var fitter = new SquareFitter();
    for (var i = 0; i < data.length; i++)
    {
        fitter.add(i, data[i]);
    }
    return fitter.project(60);
}

Example2:

>>> squareProject([
        21410, 21886, 21837, 21895, 21564, 21714, 21571, 21324, 21310, 21390,
        21764, 21598, 21493, 21352, 21478, 21058, 20942, 20825, 21321, 20950,
        21039, 21117, 20733, 20773, 20929, 20900, 20687, 20999
    ], 60);
19282.85862700518

I could do this for higher degree polynomials, but the expressions would get even longer. For arbitrary degree, you would have to look at matrices.

Skolnik

I'd seriously suggest finding a curve-fitting library in some other language and translating what you need to JavaScript rather than trying to directly implement textbook formulas. The problem is that textbook formulas are often numerically unstable, which is to say that they're really sensitive to the difference between floating-point representations of numbers and actual mathematical numbers. For example, any calculation that potentially involves subtracting one large number from another large number is likely to be overcome with rounding errors if the two numbers are close to each other. – Puissant

what does "x" in linearProject mean? – Trainee

@KashyapKotak The x parameter is the x-coordinate for which to return the y-coordinate on the estimated line (or curve). In the examples, the list index is used as x-coordinates. – Skolnik