I'm experimenting with random forests with scikit-learn and I'm getting great results of my training set, but relatively poor results on my test set...

Here is the problem (inspired from poker) which I'm trying to solve:
Given player A's hole cards, player B's hole cards and a flop (3 cards), which player has the best hand?
Mathematically, this is 14 inputs (7 cards -- one rank and one suit for each) and one output (0 or 1). 

Here are some of my results so far:

Training set size: 600k, test set size: 120k, number of trees: 25
Success rate in training set: 99.975%
Success rate in testing set: 90.05%

Training set size: 400k, test set size: 80k, number of trees: 100
Success rate in training set: 100%
Success rate in testing set: 89.7%

Training set size: 600k, test set size: 120k, number of trees: 5
Success rate in training set: 98.685%
Success rate in testing set: 85.69%


Here is the relevant code used:

from sklearn.ensemble import RandomForestClassifier
Forest = RandomForestClassifier(n_estimators = 25) #n_estimator varies
Forest = Forest.fit(inputs[:trainingSetSize],outputs[:trainingSetSize])
trainingOutputs = Forest.predict(inputs[:trainingSetSize])
testOutputs = Forest.predict(inputs[trainingSetSize:])


It appears that regardless of the number of trees used, performance on training set is  much  better than on test set, despite a relatively large training set and a reasonably small number of features...

This is a common rookie error when using RF models (I'll put my hand up as a previous perpetrator). The forest that you build using the training set will in many cases fit the training data almost perfectly (as you are finding) when considered in totality. However, as the algorithm builds the forest it remembers the out-of-bag (OOB) prediction error, which is its best guess of the generalization error.

If you send the training data back into the predict method (as you are doing) you get this almost perfect prediction (which is wildly optimistic) instead of the correct OOB error. Don't do this. Instead, the trained Forest object should have remembered within it the OOB error. I am unfamiliar with the scikit-learn implementation but looking at the documentation here it looks like you need to specify oob_score=True when calling the fit method, and then the generalization error will be stored as oob_score_ in the returned object. In the R package "randomForest", calling the predict method with no arguments on the returned object will return the OOB prediction on the training set. That lets you define the error using some other measure. Sending the training set back into the predict method will give you a different result, as that will use all the trees. I don't know if the scikit-learn implementation will do this or not.

It is a mistake to send the training data back into the predict method in order to test the accuracy. It's a very common mistake though, so don't worry.
