Feature importance (in Decision Tree, RF)

의사결정나무, 혹은 여러개의 의사결정 나무를 가진 Random Forest에서 

어떻게 트리를 만들어내고, 

어떻게 Feature importance가 계산되어 나오는지 확인하려 한다.

 

Decision Tree

의사결정 나무는 어떻게 dataset들을 분리시키고, 타겟을 예측할지 학습한다.

여기서, 의사결정나무가 어떻게 가지를 치는지(splitting) 여러 과정들이 있다. (ID3, CART)

1. ID3

- information gain을 최대화시키는 카테고리컬 feature를 찾는 것으로, numeric features는 다룰수 없고 오직 분류문제에만 해당한다.

2. CART (Classification and Regression Trees)

- categorical, numeric features 모두 사용하며 정보의 불순도를 이용해 분류문제를 풀고,

- mse를 이용한 공분산 감소도로 회귀문제글 푼다

 

Node impurity / impurity Criterion

Information Gain

- 이전 상태의 엔트로피양과 액션이 취해진 이후 엔트로피양의 차이가 곧 information gain이라고 한다.

- Feature importance는 결국 information gain의 양이 가장 많은 Feature를 나타낸 것으로 보면 된다.

Gain(T,X) = Entropy(T) — Entropy(T,X)

• T = target variable
• X = Feature to be split on
• Entropy(T,X) = The entropy calculated after the data is split on feature X

Feature Importance

- 해당 노드의 불순도에서 연결된 자식노드에 weight를 매긴 불순도를 뺀 값을 의미

Feature importance is calculated as the decrease in node impurity weighted by the probability of reaching that node. The node probability can be calculated by the number of samples that reach the node, divided by the total number of samples. The higher the value the more important the feature.

• ni sub(j)= the importance of node j
• w sub(j) = weighted number of samples reaching node j
• C sub(j)= the impurity value of node j
• left(j) = child node from left split on node j
• right(j) = child node from right split on node j

- 위 식을 이용해 각각의 노드에서의 불순도를 구한 이후, 전체 노드의 불순도 양에서 해당 노드의 불순도가 어느정도 되는지를 통해 최종적으로 feature importance를 계산한다.

 

The importance for each feature on a decision tree is then calculated as:

• fi sub(i)= the importance of feature i
• ni sub(j)= the importance of node j

These can then be normalized to a value between 0 and 1 by dividing by the sum of all feature importance values:

The final feature importance, at the Random Forest level, is it’s average over all the trees. The sum of the feature’s importance value on each trees is calculated and divided by the total number of trees:

• RFfi sub(i)= the importance of feature i calculated from all trees in the Random Forest model
• normfi sub(ij)= the normalized feature importance for i in tree j
• T = total number of trees

 

참고

https://towardsdatascience.com/the-mathematics-of-decision-trees-random-forest-and-feature-importance-in-scikit-learn-and-spark-f2861df67e3

The Mathematics of Decision Trees, Random Forest and Feature Importance in Scikit-learn and Spark