3
$\begingroup$

I have massively rewritten my original question to further explain the problem. It involves a regression problem on a dataset of about 2.5 million records. My development has been done entirely in R.

The Problem

Description

The problem involves predicting costs of highway construction contracts. Contracts are let in large groups statewide each year (called "lettings"), maybe once every other or third month. Each contract is described by a series of payitems, which specify the materials, labor, and equipment required to do the work. Each payitem is categorized by a unique code of seven digits. The codes give a clue to payitem similarity. For example, drainage-related items are under codes beginning with 542, and asphalt-related items begin with 406. "Similar" payitems are typically similar in terms of the materials and equipment used. The labor required to construct, however, may vary greatly, depending.

My goal is to predict a payitem unit price based on a history of bids going back 13 years. Note that a bid occurs each time a contractor bids on a payitem in a contract. Thus, if five contractors bid on a contract with 1,000 payitems, I can mine 5,000 individual bids from the data. To date, I've mined nearly 2.5 million individual bids.

Target predictions should be consistently within 15% of the actual value. Given that cost estimates are often inflated 10% - 15%, I felt this was a reasonable measure of success.

Predictors

To this point, the features I've selected for the problem are:

  • Location (a regional descriptor)
  • Month of letting
  • Payitem quantity
  • Payitem number
  • Total contract value
  • National Construction Cost Index (FHWA NHCCI)
  • Union laborer prevailing wage for the month of the letting
  • Relevant material and equipment cost indices

Obviously, material, labor, and equipment costs will drive the bid price, but there are other considerations I can't really model (noted below).

Based on my success thus far, I believe I've captured enough features to accurately model the data. So, without identifying which contractor made which bid, there's not much more I can do in terms of useful predictors.

Preliminary Results

To this point, I've achieved around 90% success predicting the price of guardrail payitems (a data set of about 10,000 observations) and somewhat less with asphalt payitems (about 25,000 observations). Other payitems, (like erosion control), are much harder to predict due partly to the nature of the work and materials, and the relative paucity of available data (~1,000 observations). Thus far, I have had about 50% success.

What complicates accurate prediction varies greatly. While I've managed to represent the costs of the payitems with a variety of relevant indices, there are myriad of other factors that can influence a particular bid, including distance the contractor and/or supplier is from the jobsite, potential "bidding wars" where contractors bid low on certain items to gain a competitive edge in bidding, or intentionally high bids because the contractor is not particularly well-suited for the work or suspects the designers did not adequately account for the scope of work.

The Solutions

Experience

Overall, one should expect strong linearity in the data, as quantity and price scale inversely. However, there are price ranges where that assumption breaks down which may or may not be strongly related to the other features at my disposal (bids in urban vs. rural areas, seasonal price fluctuations, etc.)

My current solution has employed the following techniques:

  1. Scale and normalize all data (even category / binary values).

  2. Log transform features that show a strong non-uniform (but otherwise non-Gaussian) distribution

  3. Remove the upper and lower 1% of outliers (validated by inspection of the data)

  4. Employ a chained ensemble of models

To elaborate on the 4th point, I initially tried a neural network and achieved 60%-70% success, but only after extensive optimization efforts. After experimenting with other algorithms, I found I could get consistently higher (70% - 80%) with any one of a support vector machine, random forest, and gradient boosting machine. Simple / geometric averages of these three models gave me another 3-7%, depending on how similar the model accuracies were.

Finally, if I took these machines and trained them again with the same hyperparameters, but appended the previous run's predictions to the original data features (creating a "chained" ensemble), I might see another 5% - 10% success increase. Chaining an individual model in this fashion only resulted in over-training with loss on the validation set accuracy.

Next Steps

There is strong linearity in certain price ranges, and linear regression may perform quite well on some (or even most) of the data, but I have no easy way to split out the linear / non-linear segments without knowing the target price in advance. Interestingly, (and perhaps it's intuitive), if I used linear regression as the second step in a "chained" model, (thus relying on predictions from previous non-linear models), linear regression fared much better, often performing almost as well as a non-linear model.

I've experimented with splitting the data using decision trees so I can segment it by its features. They've proved helpful, but I don't yet have a good grasp of how effective it may be in reducing overall non-linearity. Of course, if I could eliminate the non-linearity using decision trees and apply linear regression to the resulting datasets, I would certainly do that.

Looking at the non-linear solution I've developed, it may be over-complicated, but I don't know that it's necessarily a bad option. To the point, I have discovered that the networks didn't need to be optimized that well to provide a similar level of success. A poorer level of optimization only resulted in a 2% - 5% loss of success. If there is a feasible solution here, it would have to involve finding the breakpoint where the overall accuracy depends more on the number of models in the ensemble than the degree of optimization applied to them.

These are the two primary solutions I see in approaching the problem as a whole. What complicates implementing either of these is the volume of data (2.5 million records) and individual payitems (43,000+). As suggested in the comments, using the payitem number as a feature may prevent similar payitems from benefiting from the patterns the model learns from other payitems. This could prove problematic especially where some payitems are poorly represented, but are otherwise very similar to other, better represented items.

Again, I apologize for the length, but I hope it explains the problem more clearly.

$\endgroup$
  • 1
    $\begingroup$ you really have to be more concrete - otherwise it is difficult to help - I suspect that you would be fine with linear regression or timeseries analysis and your current solution is way too complex. are you aware of sparse representations (ie you don't enter a vector of 43000 inputs , but only the non zero elements), so your dataset and memory useage is much smaller. you could use glmnet in R for instance (scikit-learn in python has similar algorithms that accept sparse data [en.wikipedia.org/wiki/Sparse_matrix] $\endgroup$ – seanv507 Nov 6 '15 at 23:47
  • $\begingroup$ The data is somewhat non-linear. That is, I found if I model it with non-linear algorithms first, then take their predictions (along with the original data features), I can use linear regression to improve the accuracy. I've encountered the sparse matrix idea before, but have never used it in practice. Anyway, I'd happily be more concrete... I don't want to edit the question, though, without an idea of what sort of details would be helpful. $\endgroup$ – Joel Graff Nov 7 '15 at 4:57
  • $\begingroup$ Joel, you need to explain the concrete problem you are solving (in business terms, and Eg what inputs) and any insights you have on the problem. Then the statisticians on the site can suggest a good algorithm. You create nonlinear terms in linear regression by adding non linear transformation of the input variables to your input vector and creating interaction variables Eg , last year price x season (where you create separate price input for each season). 1 of n $\endgroup$ – seanv507 Nov 7 '15 at 9:31
  • $\begingroup$ 1 of n encoding is generally bad(because you are not sharing information between products), so if possible you would have categories that you think capture similarities between products. You need to specify what language you are using (I would recommend R or python). I would expect such a model to take less than 5 minutes to train and run on 8gb machine $\endgroup$ – seanv507 Nov 7 '15 at 9:40
  • $\begingroup$ @sean507 - Complete rewrite posted. Hope it clarifies a few things. Thanks for taking the time. :) $\endgroup$ – Joel Graff Nov 7 '15 at 18:51
4
$\begingroup$

Nice, exhaustive write-up! I want to propose an additional consideration or two. Most importantly, instead of building separate models for each payitem that you integrate the massively categorical nature of the payitems into a hierarchical modeling framework. This approach has several advantages: 1) by pooling the data, it would improve estimation for the sparsely populated payitems, 2) it would "shrink" the parameter estimates and their standard errors, and 3) would more appropriately account for the variability in the data versus building each model separately. Here's a paper that focuses on leveraging zip codes in a direct marketing modeling environment that describes a Bayesian approach to this:

http://www.people.hbs.edu/tsteenburgh/articles/Steenburgh_Ainslie_and_Engebretson_(winter_2003).pdf

But you aren't limited to a Bayesian approach. When this paper was written, hierarchical Bayesian frameworks offered significant advantages over the challenges traditional, closed-form or "frequentist" models faced in, e.g., inverting a massive cross-products matrix such as is required when evaluating ~35,000 zip codes at one time. However, that was then and this is now. Today, there are workarounds to the massive size of your data that have put "frequentist" approaches at parity with Bayesian techniques. These include so-called "divide and conquer" algorithms which, in essence, can be analogized to massive random forest-like approaches in that -- instead of just creating a thousand or so mini-trees (Breiman's original forests or ensembles) -- one builds tens of thousands of mini-models and aggregates the results on the back end. Here's a recent review paper on D&C:

http://stat.rutgers.edu/home/mxie/RCPapers/split_and_conquer_rev1_final.pdf

Of course, this method would be still be a challenge today on a single CPU or laptop as these techniques only really become an advantage on a multi-core platform.

There's plenty of literature to review regarding hierarchical models... starting with Gelman and Hill's Data Analysis Using Regression and Multilevel/Hierarchical Models. Otherwise, I'm agnostic as to the specific functional form the regression should take beyond a hierarchical one. It could be that exploring different approaches to analyzing one, two or a few of the payitems would provide direction towards answering that question.

$\endgroup$
  • $\begingroup$ Wow. It'll take me a day or two to digest that, so I may not accept this as the answer right away, but that seems to be the sort of thing I need. Thanks for the response! $\endgroup$ – Joel Graff Nov 7 '15 at 19:58
  • $\begingroup$ Having dug a little deeper into the topic, it seems well-suited to my particular problem. One challenge I foresee is how to establish my hierarchies. Using the zipcode example, each bid constitutes an individual, and the corresponding zipcode could be the first three digits of the payitem number. I should mention, though, that PI numbers are roughly increasingly hierarchical. That is, 630000XX would be guardrail installation, but 630000XXX would include both installation and removal... Still, this is obviously the approach I need to consider. $\endgroup$ – Joel Graff Nov 8 '15 at 12:59
  • $\begingroup$ Defining the hierarchies can be challenging, particularly when the information is multilevel and heterarchical as opposed to strictly hierarchical. To me, it sounds like PI numbers are analogous to SIC or industry classifications where, as you take fewer and fewer digits, the partitions become successively more aggregate. This isn't a problem but, to your point, finding the right "stopping" rule is never clearly defined in advance. Again, consider developing your model(s) on one, two or a few payitems -- trying several combinations of "stopping" rules -- and then roll it out for all. $\endgroup$ – DJohnson Nov 8 '15 at 13:08
  • $\begingroup$ A simple approach is just to add hierarchies/heterarchies of dummy variables with L2 regularisation. The regularisation ensures that learning is done at the highest order category possible, with specialisation at lower levels only if there are enough such data points to significantly reduce the overall error $\endgroup$ – seanv507 Nov 27 '15 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.