Feature Selection in unbalanced data I was always taught 3 things:


*

*Training algorithms (rf, trees, etc) don't perform well with unbalanced data.

*I should balance data only after performing feature selection (mainly to keep variables independent)

*Feature selection algorithms usually are based on training algorithms.
Taking these three points into consideration, how do I perform feature selection on an unbalanced data set?
EDIT: 
After talking to many people, we all came to the conclusion that the best thing will be to separate the training and validation data and balance each separately. In this scenario, the feature selection will be done with synthetic data points, but they will belong only to the training set and won't "leak" to the validation/test set, thus I get the most objective feature selection possible in such a case.
Can anyone confirm this theory?
 A: In my experience feature selection tends to make performance worse rather than better if you are using a modern machine learning method that has some feature, such as regularisation, to avoid over-fitting.  Miller's monograph on feature selection has similar advice hidden away in the appendices (sadly someone has borrowed my copy, so I can't find it).  Basically feature selection is adding one binary degree of freedom to the learning problem for each input feature.  This means the feature selection criteria can be reduced in two ways (i) getting rid of genuinely uninformative features (ii) selecting a set of features that happens to exploit some random sampling peculiarity of the data (i.e. overfitting).  For an example of over-fitting in feature selection, see my answer to a related question about cross-validation and feature selection.  The paper by Ambroise and MacLachlan is also well worth reading by anybody thinking of using feature selection with modern machine learning methods.
Secondly, the class imbalance problem is not really due to the imbalance itself, but because there are too few patterns belonging to the minority class to adequately describe it's distribution.  Most classifiers work fine with imbalanced data provided you have a lot of data.  Attempts to balance the dataset can make things worse rather than better by over-correcting for the bias due to class imbalance.
So if you have a performance problem due to class imbalance, it means you don't have enough data to adequately estimate the model parameters, in which case the last thing you should do is to perform feature selection as the added degrees of freedom this adds to the problem will only make the estimation problem worse.  Regularisation is likely to be a much better solution as it adds essentially one continuous degree of freedom, and will be much less susceptible to over-fitting.
A: It seems that you are mixing two problems: 1) performing feature selection with an ensemble learning algorithm (e.g. random forest, RF); 2) balancing your dataset so the learning process of your algorithm is maximum.
For the first one, perhaps you could take a look to this paper, in which the authors propose a modification of RF (called Guided Regularized RF) to perform feature selection as well. There is an R implementation of this algorithm here that maybe is useful. 
Then, the second problem is largely detached from the first one. In my experience, I have never seen a machine learning algorithm handling decently data imbalance by default (I am all ears if any reader has experienced the contrary), like a Poisson, Weibull or a Negative Binomial model would do. They are simply not fit for this task, at least in its basic form. But this does not have to be a problem: you can balance the classes yourself. 
You should ensure an even number of samples belonging to each class during the training phase, and you should repeat this training phase using cross-validation techniques with random selection of samples to make sure that you are capturing most of the variance of the imbalanced class(es). In this way, the subsequent process of feature selection with RF should not be biased towards the imbalanced classes.
A: The question discusses more than one important topic.
For the first one: There are many techniques to handle imbalance classes before learning a model or after the learning process. Techniques for balancing classes such as SMOTE and cost-sensitive learning and after learning a model, including the choice of performance measures that are less sensitive such as the AUC score. 
The second question, I'd suggest applying cross-validation then balancing the classes followed by the chosen feature selection technique. 
Regarding the third point, there are three categories of feature selection techniques (filters, wrappers and embedded techniques) and not all of them measure features' importance based on training a predictive model. 
