Random forest is overfitting I am trying to use Random Forest Regression in scikits-learn. The problem is I am getting a really high test error:
train MSE, 4.64, test MSE: 252.25.
This is how my data looks: (blue:real data, green:predicted):

I am using 90% for training and 10% for test. This is the code I am using after trying several parameter combinations:
rf = rf = RandomForestRegressor(n_estimators=10, max_features=2, max_depth=1000, min_samples_leaf=1, min_samples_split=2, n_jobs=-1) 
test_mse = mean_squared_error(y_test, rf.predict(X_test))
train_mse = mean_squared_error(y_train, rf.predict(X_train))

print("train MSE, %.4f, test MSE: %.4f" % (train_mse, test_mse))
plot(rf.predict(X))
plot(y)

What are possible strategies to improve my fitting? Is there something else I can do to extract the underlying model? It seems incredible to me that after so many repetitions of the same pattern the model behaves so badly with new data. Do I have any hope at all trying to fit this data? 
 A: The biggest problem is that regression trees (and algorithms based on them like random forests) predict piecewise constant functions, giving a constant value for inputs falling under each leaf. This means that when extrapolating outside their training domain, they just predict the same value as they would for the nearest point at which they had training data. @mbq is correct that there are specialized tools for learning time series that would probably be better than general machine learning techniques. However, random forests are particularly bad for this example, and there other general ML techniques would probably perform much better than what you are seeing. SVMs with nonlinear kernels are one option that comes to mind. Since your function has periodic structure, this also suggests working the frequency domain, using Fourier components or wavelets.
A: This is a textbook example for data over-fitting, the model does very well on trained data but collapses on any new test data. 
This is one of the strategies to address this:
Make a ten fold cross validation of the training data to optimize the parameters. 
Step 1. Create a MSE minimizing function using the NM optimization. An example could be seen here: http://glowingpython.blogspot.de/2011/05/curve-fitting-using-fmin.html
Step 2. Within this minimization function, the objective is to reduce the MSE. In order to do this, create a ten-fold split of the data where a new model is learned on 9 folds and tested on the 10th fold. This process is repeated ten times, to obtain the MSE on each fold. The aggregated MSE is returned as the result of the objective. 
Step 3. The fmin in python will do the iterations for you. Check which hyper parameters are necessary to be fine tuned (n_estimators, max_features etc.) and pass them to the fmin. 
The result will be the best hyper-parameters which will reduce the possibility of over-fitting. 
A: Some suggestions:


*

*Tune your parameters using a rolling window approach (your model must be optimized to predict the next values in the time series, not to predict values among the ones supplied)

*Try other models (even simpler ones, with the right feature selection and feature engineering strategies, might prove better suited to your problem)

*Try to learn optimal transformations of the target variable (tune this too, there's a negative linear/exponential tendency, you may be able to estimate it)

*Spectral analysis perhaps

*The maxima/minima are equally spaced it seems. Learn where they are given your features (no operator input, make an algorithm discover it to remove bias) and add this as a feature. Also engineer a feature nearest maximum. Dunno, it might work, or perhaps not, you can only know if you test it :)

A: I think you are using wrong tool; if your whole X is equivalent to the index, you are basically having some sampled function $f:\mathbb{R}\rightarrow\mathbb{R}$ and trying to extrapolate it. Machine learning is all about interpolating history, so it is not surprising that it scores spectacular fail in this case.
What you need is a time series analysis (i.e. extracting trend, analysing spectrum and autoregressing or HMMing the rest) or physics (i.e. thinking if there is an ODE that may produce such output and trying to fit its parameters via conserved quantities).
A: This is an interesting problem. Your data suggests some regularity (periodic $x^2$ like functions) but has sharp peaks at transitions. All this suggests a slightly complex model. I would model these data by a succession of $x_2$ functions parametrized by a coefficient and a displacement parameter.
A: After reading above post , I want to give another different answer.
For tree based models, such as random forest, they can't extrapolate the value beyond the training set. So, I don't think it is an over fitting problem, but an wrong modeling strategy.
So, what can we do for time series prediction with tree model?
The possible way is to combine it with linear regression: first, detrend the time series (or modeling trend with linear regression), then modeling the residual with trees (residuals are bounded, so tree models can handle it).
Besides, there is a tree model combined with linear regression can extrapolate, called cubist, it does linear regression on the leaf.
A: If you simply want to predict within the bounds of the graph, then simply randomizing the observations before splitting the data set should solve the problem. It then becomes an interpolation problem from the extrapolation one as shown.
