Thousands of features and only 70 samples I am working on a regression problem where I have around 5-10 thousand features and have only 65 samples. I am training my algorithm on 55 samples and testing on 10 samples. I am using both Pearson correlation and feature importance using the random forest to remove irrelevant features. In testing data, the random forest algorithm is predicting the average of the training samples.
I have a few questions:
(1) Which ML algorithm should I use when I have very few samples for training (55 samples in my case)?
(2) The Best way of feature selection when we have much more features than samples?
 A: Others have described your impossible challenge very well.  To state in other ways:

*

*Your sample size is too small by a factor of 100 for split-sample validation to have any hope of working, i.e., of being precise and stable

*Statistical testing to discard features has no hope of discarding the right features

*Penalization (regularization; shrinkage) has no hope here because the sample size is too small for you to be able to choose the shrinkage factor

*Your only hope is to use unsupervised learning (data reduction; does not use the outcome variable in any way) methods such as principal components, variable clustering, sparse principal components to reduce the dimensionality of the feature space down to 1 or 2 numbers per observation, then using those 1 or 2 numbers to predict the outcome.  In other words the only hope of meeting your goal is for you to be lucky enough that the ways the features are redundant with each other can be collapsed into some kind of signal summary that relates to Y.

A: I think the answer to this question is highly data and problem dependent. Some people have reasonably suggested fitting a simple model with regularization, like ridge regression or Lasso, using all features. I also think this is a good idea, and you should try it. But see here: Is ridge regression useless in high dimensions ($n \ll p$)? How can OLS fail to overfit?
In this question, the original poster had a real world data set with approximately as many data as you and the same order of magnitude of features. They found that regularization didn't help, and another user pointed out that for some data sets with many more features than data, regularization is moving in the wrong direction from the min-norm solution.
So the point is, even very general suggestions like "use regularization" might end up being wrong in your specific case, depending on the data.
If I were you, I would start by checking if there is some domain dependent reason to include some variables. If not, check for variables that seem different than the others, different ranges, missing values, etc. Try to figure out what about the reason is for those differences and see if that gives any insight into the data.
Univariate screening like you've tried with Pearson correlation is probably only going to be useful if you find some variables with very high correlation. Use your training set, and just check if you have a situation where most of your variables have correlation between -0.5 and 0.5 (consistent with random noise in your case) but a few of your variables have correlation like 0.65 (unlikely even if you have 100 000 random features). Don't take the top 5% or 10% of features, or auto-exclude features below some correlation. Just check if there is some obviously important feature that you should already know about for domain reasons, but either you forgot something important or someone forgot to tell you something.
Failing something obvious like that, I think you're back to data/problem dependent answers. It matters how you ended up in a situation where 10000 features were created from 65 data. If all or most of your features are pairwise correlated with similar scales, maybe they are all somehow noisy measurements of the same thing. In that case, averaging all the predictors and using the result as a single feature regression might do very well.
A: *

*The chances of any predictive model doing well here are very very slim. You need to either get more data, or use domain knowledge to narrow down the number of predictors you consider.

*That said, Lasso regression is the usual choice in situations like this.

