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.

NCAA Football Predictions (11/15/11)
Home TeamAway Team  MOV
Air ForceNevada-Las Vegas16.1
Arizona StateArizona18
ArkansasMississippi State13.1
BaylorOklahoma-14.2
Bowling Green StateOhio-6.7
Brigham YoungNew Mexico State15.7
BuffaloAkron12.3
Central MichiganToledo-14.9
ConnecticutLouisville0.4
DukeGeorgia Tech-6.9
East CarolinaCentral Florida-8
Florida StateVirginia16.8
GeorgiaKentucky24.5
HawaiiFresno State9
HoustonSouthern Methodist18.3
IdahoUtah State-8.3
IllinoisWisconsin-9.9
Iowa StateOklahoma State-17
KentEastern Michigan6
Louisiana-MonroeFlorida International-3.3
MemphisMarshall-15.4
Miami (Ohio)Western Michigan-2.4
MichiganNebraska10.2
Michigan StateIndiana20.9
Middle Tennessee StateArkansas State-11.5
MississippiLouisiana State-26.3
MissouriTexas Tech15.2
NevadaLouisiana Tech1.8
North Carolina StateClemson-9.1
North TexasWestern Kentucky2
Northern IllinoisBall State11.5
NorthwesternMinnesota14.3
Notre DameBoston College22.3
Ohio StatePenn State1
OregonSouthern California14.9
Oregon StateWashington-0.4
PurdueIowa-1.6
RiceTulane15
RutgersCincinnati0.8
San Diego StateBoise State-13.6
San Jose StateNavy-1.8
South FloridaMiami (Florida)3.9
StanfordCalifornia20.3
TempleArmy15.8
TennesseeVanderbilt2.6
TexasKansas State3
Texas A&MKansas23.8
Texas ChristianColorado State24.4
Texas-El PasoTulsa-10.4
TroyFlorida Atlantic11.2
UabSouthern Mississippi-26.2
UclaColorado12.2
Virginia TechNorth Carolina6
Wake ForestMaryland11.1
Washington StateUtah-2.4
WyomingNew Mexico20.4

Tuesday, November 8, 2011

One Bad (Good) Game

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              |                |               |               |
+-------------------+---------
-------+---------------+---------------+
|nebraska           |northwestern    |12.2           |13.1           |
+-------------------+---------
-------+---------------+---------------+
|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           |
+-------------------+---------
-------+---------------+---------------+
|colorado           |southern        |-13.6          |-16.1          |
|                   |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          |
+-------------------+---------
-------+---------------+---------------+

NCAA Basketball Schedule Data

I have provide on this page links to a file containing the currently published schedule of games for the upcoming basketball season.  I scraped this today from Yahoo Sports so it may be missing some games that have not yet been scheduled, tournament games, etc.  The format is self-explanatory and designed for easy ingest by Lisp, but should be easily translated to CSV or other format.  All fields are enclosed with quotes for easy parsing.

At the same page I've also provided a listing of conferences and team names.  The team names correspond to the names used in the schedule and on Yahoo Sports.  This is the same conference file I used last year -- I don't believe there have been any conference changes, but if so let me know and I'll update the file.