Regression on Predicting Time

Question

If I have a dataset like this:

ID  beg_lng beg_lat end_lng end_lat start_timestamp Time (sec)
0   -74.009087  40.713818   -74.004326  40.719986   1420950819  10
1   -73.971176  40.762428   -74.004181  40.742653   1420950819  1120
2   -73.994957  40.745079   -73.999939  40.73465    1421377541  321

Think of it a grocery shopping details of a delivery person. It has the starting lat/long where it starts and ending lat/long of destination. It also has the corresponding time it took in seconds (Time). start_timestamp is epoch in seconds of starting time.

Now if I want to build a regression model to predict the grocery delivery trip time, I tried first a basic crude method of linear regression with elastic net and put in all the above features (after standardizing them). I used the lat/long as given and didn't do much transformation.

However I get a very bad fit.

The mean train scores are [ 0.08447384  0.08447416  0.08447448  0.0844748   0.08447511  0.08448194
  0.08448468  0.08448715  0.08448937  0.08449133  0.08453318  0.08451306
  0.08446719  0.08439527  0.08429637  0.08253336  0.07888605  0.07359639
  0.06619284  0.0578421   0.00454754 -0.00018343 -0.00018343 -0.00018343
 -0.00018343]

The mean validation scores are [ 0.08389243  0.08389275  0.08389305  0.08389336  0.08389367  0.08390072
  0.08390336  0.08390575  0.08390787  0.08390974  0.08395386  0.08393282
  0.08388601  0.08381316  0.08371341  0.08197247  0.07835721  0.07306636
  0.06565797  0.05737215  0.00448677 -0.00021397 -0.00021397 -0.00021397
 -0.00021397]

The score on held out data is: 0.08395386395024673
 Hyper-Parameters for Best Score : {'l1_ratio': 0.15, 'alpha': 0.01}

The R2 Score of sgd_regressor on test data is: 0.0864573982691922

The mse of sgd_regressor on test data is: 469651.012051
The mean absolute error of sgd_regressor on test data is: 422.247732739

Here is the Grid search code

  def grid_search(self):

        """This function does Cross Validation using Grid Search

        """

        from sklearn.model_selection import GridSearchCV
        self.g_cv = GridSearchCV(estimator=self.estimator,param_grid=self.param_grid,cv=5)
        self.g_cv.fit(self.train_X,self.train_Y)

And code to check the error:

def test_performance(self,name):
    """This method checks the performance of each algorithm on test data."""

    from sklearn.metrics import mean_squared_error, mean_absolute_error

    # 
    print("The R2 Score of "+ name + " on test data is: {}\n".format(self.g_cv.best_estimator_.score(self.test_X,self.test_Y)))

    print ("The mse of "+ name + " on test data is:",\
           mean_squared_error(test_Y, self.g_cv.best_estimator_.predict(self.test_X)))

    print ("The mean absolute error of "+ name + " on test data is:",\
           mean_absolute_error(test_Y, self.g_cv.best_estimator_.predict(self.test_X)))

Why am I getting such a bad R2 and errors? Any idea where I can be going wrong?

Answer 1

This is probably a case where a linear (or other) regression won't be very helpful. People will only ever go shopping at stores.

If midway between store A (where your user usually spends two minutes to buy a cup of coffee) and store B (where your user usually spends two hours to buy clothes), there is only a stretch of highway, it makes little sense to predict that he will shop there for about one hour.

Instead, it's probably better to use $k$-nearest neighbors, or a variant that only searches within a given maximum geographical radius. Which is pretty much a proxy for "identify the last $k$ visits to this store, then predict the average time spent there". Note that if you include the starting time stamp, you automatically make sure that only the last visits count (you may need to play around with the weights on the geographical vs. the time dimension here).

If there are less than $k$ previous visits, best to use the average of those visits we do have, not include a neighboring coffee shop or supermarket, which may not be comparable (that's where the "maximum geographical radius" comes in).

Answer 2

This response is really a comment but it quickly became too long for that format.

The discussion with @stephenkolassa makes the OPs query sound more like a bad variant of the classic TSP (Traveling Salesman Problem) which, with more than a few nodes, quickly becomes an Np-hard problem in terms of computational complexity. Nearest neighbor algorithms are commonly used in TSP solutions. So, +1 to Stephen for this suggestion.

I do have some points of difference. First of all, my view is that treating lat/long as continuous features is a mistake. To me, it would make more sense to discretize them in two possible ways (at least): first, treat lat/long in terms of 'distance traveled' or, second, by assigning them to a zip code. Both approaches would require digging up one of the widely available lat/long distance calculators (e.g., here ... http://www.nhc.noaa.gov/gccalc.shtml). This NOAA function can also be treated as a formula and coded up in your software for the large number of computations required.

Assignment of lat/long to a zip code is a little trickier insofar as it requires using the same distance or comparison function to find the zip code closest to each lat/long (starting and ending). In this case, the two lat/longs would be evaluated separately against the zip code lat/longs at their 'centroid.' Publicly available, accessible and free databases are out there that have zip code centroid lat/longs extracted from US census data (e.g., here ... https://stackoverflow.com/questions/19819418/up-to-date-zip-code-database). In addition, many of them have geodemographic enhancements such as median hhold income, population size, ethnicity, etc., which can also be leveraged for descriptive purposes. The caveat to this second approach is that zip code is a massively categorical feature, even if only using the approximately 36,000 residential zip codes. Treating a cross-product matrix of this size in a classic, closed form, ANOVA-type model would be prohibitive. Few machines on the planet would have sufficient RAM to decompose such a matrix. A hierachical bayesian workaround to this challenge is proposed in this paper by Steenburgh and Ainslie Massively Categorical Variables: Revealing the Information in Zip Codes (here ... http://bear.warrington.ufl.edu/centers/MKS/abstracts/vol22/no1/aab6f24ee7_abstract.pdf). A frequentist approach would be to leverage one of the many variants of divide and conquer algorithms out there which would reduce the problem to a more manageable size.

The first, discretizing solution is probably the way to go.