What is the difference between between mean decrease in accuracy and mean decrease in Gini impurity in Random Forest, any simple example about it? Like how these measures are related in variable importance.
A Random Forest is a ensemble of Decision Trees, and these terms are used of decision trees.
As you are building a decision tree, you choose splits based on the homogeneity of the target variable within each of the two groups. Impurity is low when groups are homogenous and high when they are not. (So the maximum impurity is when a group consists of an equal number of each of the two or more classes, and minimum impurity is when a group is 100% of one class.)
Accuracy is of course, what percentage of cases are properly classified.
Two different, though related measurements. Gini is often used in the decision tree algorithm itself, while accuracy may be used to evaluate the tree.
Variable importance is not magic. Too many people now-a-days want to run an automated procedure so they don't actually have to learn their data. Variable importance procedures can be a nice helper -- if you work hard to avoid confirmation bias -- but beware. If you're using R, check out the Boruta package, which may shed some light on the issue and which uses a more sophisticated algorithm than mean decrease in accuracy or Gini impurity.
I believe Gini is more biased towards variables which are factors with lots of levels -- more choices -- and I would tend to look more towards mean decrease in accuracy. But you should really do both, look at Boruta-like methods, and also understand your data.
All of these variable importance methods will gladly pick variables with leaks from the future as important, because they have no idea what they mean. And they will gladly reject variables that have some data corruption that you could fix but don't know about. It's not magic.