KFold Cross Validation does not fix overfitting

The reason you're overfitting is because a non-regularized tree-based model will adjust to the data until all training samples are correctly classified. See for example this image:

As you can see, this does not generalize well. If you don't specify arguments that regularize the trees, the model will fit the test data poorly because it will basically just learn the noise in the training data. There are many ways to regularize trees in sklearn, you can find them here. For instance:

• max_features
• min_samples_leaf
• max_depth

With proper regularization, you can get a model that generalizes well to the test data. Look at a regularized model for instance:

To regularize your model, instantiate the RandomForestRegressor() module like this:

rfr = RandomForestRegressor(max_features=0.5, min_samples_leaf=4, max_depth=6)

These argument values are arbitrary, it's up to you to find the ones that fit your data best. You can use domain-specific knowledge to choose these values, or a hyperparameter tuning search like GridSearchCV or RandomizedSearchCV.

Other than that, imputing the mean and median might bring a lot of noise in your data. I would advise against it unless you had no other choice.

While @NicolasGervais answer gets to the bottom of why your specific model is overfitting, I think there is a conceptual misunderstanding with regards to cross-validation in the original question; you seem to think that:

Cross-validation is a method that improves the performance of a machine learning model.

But this is not the case.

Cross validation is a method that is used to estimate the performance of a given model on unseen data. By itself, it cannot improve the accuracy. In other words, the respective scores can tell you if your model is overfitting the training data, but simply applying cross-validation does not make your model better.

Example: Let's look at a dataset with 10 points, and fit a line through it:

import numpy as np 
import matplotlib.pyplot as plt
from sklearn.linear_model import LinearRegression

X = np.random.randint(0,10,10)
Y = np.random.randint(0,10,10)

fig = plt.figure(figsize=(1,10))

def line(x, slope, intercept):     
    return slope * x + intercept

for i in range(5):

    # note that this is not technically 5-fold cross-validation
    # because I allow the same datapoint to go into the test set
    # several times. For illustrative purposes it is fine imho.
    test_indices = np.random.choice(np.arange(10),2)
    train_indices = list(set(range(10))-set(test_indices))

    # get train and test sets
    X_train, Y_train = X[train_indices], Y[train_indices]
    X_test, Y_test = X[test_indices], Y[test_indices]
    # training set has one feature and multiple entries
    # so, reshape(-1,1)
    X_train, Y_train, X_test, Y_test = X_train.reshape(-1,1), Y_train.reshape(-1,1), X_test.reshape(-1,1), Y_test.reshape(-1,1)

    # fit and evaluate linear regression
    reg = LinearRegression().fit(X_train, Y_train)
    score_train = reg.score(X_train, Y_train)
    score_test = reg.score(X_test, Y_test)

    # extract coefficients from model:
    slope, intercept = reg.coef_[0], reg.intercept_[0]

    print(score_test)
    # show train and test sets
    plt.subplot(5,1,i+1)
    plt.scatter(X_train, Y_train, c='k')
    plt.scatter(X_test, Y_test, c='r')

    # draw regression line
    plt.plot(np.arange(10), line(np.arange(10), slope, intercept))
    plt.ylim(0,10)
    plt.xlim(0,10)

    plt.title('train: {:.2f} test: {:.2f}'.format(score_train, score_test))

You can see that the scores on training and test set are vastly different. You can also see that the estimated parameters vary a lot with the change of train and test set.

That does not make your linear model any better at all. But now you know exactly how bad it is :)