## Tuesday, November 15, 2011

### k-NN Prediction

"Andywocky" commented not too long ago on my Prediction by Similarity posting asking whether I'd looked at k-nearest neighbors (k-NN) algorithms.  At the time I made the original posting I hadn't, but shortly thereafter I had a "D'oh" moment and realized that what I was doing was re-creating k-NN.  So I re-created some of the work I'd done using RapidMiner's k-NN operator.

The basic idea behind k-NN is that we predict the outcome of a new game by finding some number of similar past games, and then use those (say by averaging) to create a prediction for the new game.  The "k" in "k-NN" refers to the "some number" of similar past games -- k might be 5 or 50, indicating that we were using the five most similar, or 50 most similar past games.  "Nearest Neighbor" is just another way of saying similar.  If we think of the games living in a multi-dimensional space -- say a dimension for each statistical value for the game (e.g., rebounds per minute, free throw percentage, etc.) -- then the most similar games are the ones that are the nearest neighbors in this multidimensional space.

There are some subtleties in how this works.  For example, team free throw percentage might vary from (say) 50% to 100%, while rebounds per minute might vary from 0.00 to 0.056.  If we don't normalize those dimensions, one or the other is likely to be far more important in determining the nearest neighbor than the other. But a reasonable starting approach is to characterize each game with as many statistical properties as we have, normalize those to similar scales, and then predict MOV by averaging the MOVs of k nearest-neighbors.

Here's the result of doing that with k=10.  For comparison, I include the performance of the best linear regression predictor based upon the same statistical properties.

Predictor    % Correct    MOV Error
Best Statistical Predictor72.3%11.04
k-NN, k=1059.7%11.65

This isn't tremendous performance, but we have a few tweaks we can perform.  First, we can try varying k to see if some different number of neighbors provides better performance.  Some searching around produces the best performance in this case when k=41:

Predictor    % Correct    MOV Error
Best Statistical Predictor72.3%11.04
k-NN, k=1059.7%11.65
k-NN, k=4171.2%11.44

Interestingly, this shows a lot of improvement in games correct with only modest improvement in MOV error.

Another tweak we can look at is weighting our results.  Instead of doing a flat average of the 41 nearest neighbors, we can weight each neighbor's contribution to the answer by how close it is to the new game.  We can also try eliminating some of our dimensions to see if accuracy improves.  This provides some further improvement:

Predictor    % Correct    MOV Error
Best Statistical Predictor72.3%11.04
k-NN, k=1059.7%11.65
k-NN, k=4171.2%11.44
k-NN, k=44, weighted subset72.4%11.17

With this tweak k-NN is competitive with the best linear regression.  (Although they both trail the best predictors.)

I'm inclined to draw a couple of conclusions from these experiments.  First, 40+ neighbors is a large number, suggesting that while games between statistically similar may be broadly comparable, there's not a strong relationship.  Conversely, the improvement gained by using weighting suggests that closer is still better.  It would seem that good performance with this approach requires a moderate amount of generalization to help "wash out" the random component in game outcomes.

### Football Predictions (11/15/11)

I hope to have some time in the next day or so for some postings, so here are the predictions for this week in NCAA football.  I've been tracking this performance for a contest, and for the past three weeks I'm 56% against the line (and 71% winners).  That might be anomalously good performance, but I've been positive against the line every week, so take that for what it is worth.

As always, heed the Net Prophet Disclaimer.

 Home Team Away Team MOV Air Force Nevada-Las Vegas 16.1 Arizona State Arizona 18 Arkansas Mississippi State 13.1 Baylor Oklahoma -14.2 Bowling Green State Ohio -6.7 Brigham Young New Mexico State 15.7 Buffalo Akron 12.3 Central Michigan Toledo -14.9 Connecticut Louisville 0.4 Duke Georgia Tech -6.9 East Carolina Central Florida -8 Florida State Virginia 16.8 Georgia Kentucky 24.5 Hawaii Fresno State 9 Houston Southern Methodist 18.3 Idaho Utah State -8.3 Illinois Wisconsin -9.9 Iowa State Oklahoma State -17 Kent Eastern Michigan 6 Louisiana-Monroe Florida International -3.3 Memphis Marshall -15.4 Miami (Ohio) Western Michigan -2.4 Michigan Nebraska 10.2 Michigan State Indiana 20.9 Middle Tennessee State Arkansas State -11.5 Mississippi Louisiana State -26.3 Missouri Texas Tech 15.2 Nevada Louisiana Tech 1.8 North Carolina State Clemson -9.1 North Texas Western Kentucky 2 Northern Illinois Ball State 11.5 Northwestern Minnesota 14.3 Notre Dame Boston College 22.3 Ohio State Penn State 1 Oregon Southern California 14.9 Oregon State Washington -0.4 Purdue Iowa -1.6 Rice Tulane 15 Rutgers Cincinnati 0.8 San Diego State Boise State -13.6 San Jose State Navy -1.8 South Florida Miami (Florida) 3.9 Stanford California 20.3 Temple Army 15.8 Tennessee Vanderbilt 2.6 Texas Kansas State 3 Texas A&M Kansas 23.8 Texas Christian Colorado State 24.4 Texas-El Paso Tulsa -10.4 Troy Florida Atlantic 11.2 Uab Southern Mississippi -26.2 Ucla Colorado 12.2 Virginia Tech North Carolina 6 Wake Forest Maryland 11.1 Washington State Utah -2.4 Wyoming New Mexico 20.4

## Tuesday, November 8, 2011

As mentioned in my previous posting, I recently looked at the effect of dropping a football team's best game (highest Margin of Victory) and their worst game (lowest MOV).  The intuitive notion is that everybody has bad days, where everything goes wrong, and good days, where everything goes right, and maybe those days don't tell us anything useful about the real strength of a team.  If that's so, then dropping those games might give us ratings that are more accurate.

To test this hypothesis I implemented this "drop the worst score" grading system for a couple of the rating systems I use for football and measured performance in the usual way.  Here are the results for one of the rating systems:

Predictor    % Correct    MOV Error
BGD Baseline73.7%16.52
BGD w/o blowouts or lowouts 72.6%16.77
BGD w/o lowouts72.9%16.69
BGD w/o blowouts73.6%16.62

Here I'm using the whimsical "lowout" to indicate the worst loss for a team.

As this shows, eliminating the blowouts/lowouts hurts predictive performance.  For what it's worth, the losses seem to be more important than the wins.  (I saw the same effect in basketball when I looked at this last year.)

## Friday, November 4, 2011

### The Impact of MOV Cutoffs in Football Ratings

I was prompted to start my football predictions by a discussion on an email list of the value of MOV cutoffs in rating systems.  Roger Dendy believed that capping the MOV in blowout victories improved his rating system.  My testing of MOV cutoffs in basketball has shown just the opposite -- that no matter how big the blowout, there's always information in the margin of victory.  Capping MOV at any level (in both blowouts and nailbiters) always reduces the prediction value of a rating.

Of course, just because that's true in basketball doesn't mean it's true in football.  I was pretty sure it was true, but I believe in "trust but verify."  So I put together the football predictor and tested a couple of different rating systems both with and without MOV caps.

I have many rating systems that use MOV, so I picked one and measured it's performance with a 100-fold X-validation  across my archive of college football scores from 2005 to date.  It had a RMS of 16.78 and predicted 71% of the games correctly.

Then I experimented with adding a cutoff to the MOV.  I set the cutoff to 32 points, so that all the games where the MOV exceeded 32, it would be treated as 32.  I just picked 32 arbitrarily as a good figure for a blowout win.  The performance degraded to RMS=17.19 and 69%.  I then bumped up the cutoff to 48 points, and the performance was RMS=17.01 and 70%.

The other rating system showed a similar pattern of performance.

What this shows -- at least for the two rating systems I tested and these performance metrics -- is that even huge margins of victory have value in assessing future performance.  People argue intuitively that there's "no difference between winning by 48 and winning by 52" but that appears not to be true.

Recently I got to wondering if it might not make more sense to drop a blowout victory entirely.  This would be like "drop your lowest score" grading in high school.  The intuitive notion here is that sometimes teams just have a bad day -- a few unlucky bounces and worse goes to worse.  Or lucky bounces and better goes to better, from the other side of the coin.  More on that notion next time.

## Wednesday, November 2, 2011

### Football Predictions

Shown below are predictions for this week's upcoming football games.  I did a little tweaking and developed a new algorithm for this week's predictions so you'll see two predictions below.

The first is the new algorithm, the second is an ensemble of three algorithms. The new algorithm is similar to the "Homemade Sagarin Ratings" described here (although I do not use Excel Solver to calculate my ratings).  The Sagarin ratings do very well at the Prediction Tracker, so I wanted to implement something similar and see how it did in comparison to my other predictors.  Much to my surprise, it equals or surpasses my best football predictors.  In past tests on the basketball data, this type of predictor did not perform well, but in the course of implementing it for football I found several problems, so I intend to retest this on the basketball data and look at some possible improvements if warranted.

If anyone knows a better description of the Sagarin PREDICTOR algorithm, please let me know.

As always when viewing my predictions, heed the Disclaimer.

+-------------------+----------------+---------------+---------------+
|Hname              |Aname           |prediction(1)  |prediction(2)  |
+-------------------+---------
-------+---------------+---------------+
|wisconsin          |purdue          |23.4           |19.2           |
+-------------------+---------
-------+---------------+---------------+
|west virginia      |louisville      |11.6           |9.3            |
+-------------------+---------
-------+---------------+---------------+
|maryland           |virginia        |4.1            |1.5            |
+-------------------+---------
-------+---------------+---------------+
|rice               |texas-el paso   |-.3            |1.0            |
+-------------------+---------
-------+---------------+---------------+
|texas              |texas tech      |11.1           |11.1           |
+-------------------+---------
-------+---------------+---------------+
|wyoming            |texas christian |-16.7          |-15.5          |
+-------------------+---------
-------+---------------+---------------+
|tennessee          |middle          |22.3           |20.5           |
|                   |tennessee state |               |               |
+-------------------+---------
-------+---------------+---------------+
|oregon state       |stanford        |-18.7          |-20.2          |
+-------------------+---------
-------+---------------+---------------+
|east carolina      |southern        |-13.0          |-10.4          |
|                   |mississippi     |               |               |
+-------------------+---------
-------+---------------+---------------+
|southern           |tulane          |19.0           |18.1           |
|methodist          |                |               |               |
+-------------------+---------
-------+---------------+---------------+
|san jose state     |idaho           |10.7           |9.9            |
+-------------------+---------
-------+---------------+---------------+
|san diego state    |new mexico      |32.9           |29.0           |
+-------------------+---------
-------+---------------+---------------+
|rutgers            |south florida   |2.1            |1.4            |
+-------------------+---------
-------+---------------+---------------+
|washington         |oregon          |-13.7          |-12.8          |
+-------------------+---------
-------+---------------+---------------+
|oklahoma state     |kansas state    |15.3           |14.2           |
+-------------------+---------
-------+---------------+---------------+
|oklahoma           |texas a&m       |17.7           |17.9           |
+-------------------+---------
-------+---------------+---------------+
|ohio state         |indiana         |21.7           |21.2           |
+-------------------+---------
-------+---------------+---------------+
|wake forest        |notre dame      |-10.0          |-10.5          |
+-------------------+---------
-------+---------------+---------------+
|north carolina     |north carolina  |-4.9           |-6.4           |
|state              |                |               |               |
+-------------------+---------
-------+---------------+---------------+
+-------------------+---------
-------+---------------+---------------+
|navy               |troy            |7.4            |6.5            |
+-------------------+---------
-------+---------------+---------------+
|baylor             |missouri        |2.0            |4.4            |
+-------------------+---------
-------+---------------+---------------+
|michigan state     |minnesota       |22.9           |22.8           |
+-------------------+---------
-------+---------------+---------------+
|iowa               |michigan        |-11.3          |-14.1          |
+-------------------+---------
-------+---------------+---------------+
|miami (florida)    |duke            |8.7            |8.4            |
+-------------------+---------
-------+---------------+---------------+
|fresno state       |louisiana tech  |-3.2           |-4.9           |
+-------------------+---------
-------+---------------+---------------+
|louisiana-lafayette|
louisiana-monroe|11.3           |13.6           |
+-------------------+---------
-------+---------------+---------------+
|kentucky           |mississippi     |-2.1           |-.8            |
+-------------------+---------
-------+---------------+---------------+
|iowa state         |kansas          |19.3           |19.7           |
+-------------------+---------
-------+---------------+---------------+
|alabama-birmingham |houston         |-31.4          |-30.6          |
+-------------------+---------
-------+---------------+---------------+
|hawaii             |utah state      |1.2            |.7             |
+-------------------+---------
-------+---------------+---------------+
|georgia            |new mexico state|24.8           |25.2           |
+-------------------+---------
-------+---------------+---------------+
|western kentucky   |florida         |-3.3           |-3.9           |
|                   |international   |               |               |
+-------------------+---------
-------+---------------+---------------+
|florida            |vanderbilt      |8.6            |9.9            |
+-------------------+---------
-------+---------------+---------------+
|eastern michigan   |ball state      |4.2            |4.7            |
+-------------------+---------
-------+---------------+---------------+
|connecticut        |syracuse        |-1.6           |-3.3           |
+-------------------+---------
-------+---------------+---------------+
|pittsburgh         |cincinnati      |-1.3           |-2.0           |
+-------------------+---------
-------+---------------+---------------+
|california         |washington state|3.1            |3.5            |
+-------------------+---------
-------+---------------+---------------+
|nevada-las vegas   |boise state     |-30.6          |-28.2          |
+-------------------+---------
-------+---------------+---------------+
|florida atlantic   |arkansas state  |-12.7          |-15.1          |
+-------------------+---------
-------+---------------+---------------+
|arkansas           |south carolina  |.6             |1.0            |
+-------------------+---------
-------+---------------+---------------+
|ucla               |arizona state   |-7.5           |-7.2           |
+-------------------+---------
-------+---------------+---------------+
|arizona            |utah            |1.3            |-1.7           |
+-------------------+---------
-------+---------------+---------------+
|alabama            |louisiana state |3.9            |5.9            |
+-------------------+---------
-------+---------------+---------------+
|air force          |army            |11.1           |12.8           |
+-------------------+---------
-------+---------------+---------------+
|                   |california      |               |               |
+-------------------+---------
-------+---------------+---------------+
|kent               |central michigan|5.5            |8.4            |
+-------------------+---------
-------+---------------+---------------+
|central florida    |tulsa           |-2.5           |1.0            |
+-------------------+---------
-------+---------------+---------------+
|miami (ohio)       |akron           |13.8           |13.3           |
+-------------------+---------
-------+---------------+---------------+
|boston college     |florida state   |-13.5          |-13.3          |
+-------------------+---------
-------+---------------+---------------+