머신러닝 알고리즘 정리 (Decision Tree, Random Forest)

1. Decision Tree (결정 트리)

Rull based prediction model로 Tree구조로 각 노드에서 binary 혹은 multi-way의 조건을 체크하면서 모든 응답이 거의 같은 값을 가리킬 때 까지 leaf node로 classification 혹은 regression을 하는 머신러닝 기법이다. 쉽게 설명하면 스무고개를 통해 원래 데이터가 어디에 속하는 지 알아나가는 과정이라고도 볼 수 있다. 

각 노드에 질문을 통해 분류되는 클래스들은 homogenous(같은 클래스의 비중이 높을수록)할수록 좋다. 예를 들면 어떤 질문을 통해 5:5로 나누어지는 것 보다는 9:1로 나눌 수 있는 것이 좋다는 것이다. 다시 말해 각 영역의 순도(homogeneity)가 높을 수록, 불순성(Node impurity)가 낮을 수록 정보 획득(information gain)이 크다고 본다. 이 때, 이와 같은 순도나 불순성을 측정하는 방법은 아래와 같다.

Classification의 경우 -  1. Gini index  / 2. Entropy / 3. Misclassification error
Regression의 경우 - 1. MSE / 2. varinace of X  (class probability가 존재하지 않으므로..)

결정트리의 예

장점
nominal variable을 numerical하게 변환할 필요 없이 그 자체로 이용할 수 있다.
(numerical한 value들은 discretization (A > v or A < v)를 활용하여 binary 혹은 multi decision으로 변환한다.)
계산 복잡성 대비 높은 예측 성능을 낸다.

단점
특정 데이터에만 잘 작동할 가능성이 크다.
sample이 너무 작으면 쉽게 overfit될 수 있다.
overfitting이 쉽게 일어날 수 있다. (이를 위해, pre-pruning 혹은 post-pruning을 진행한다.)
- pre-pruning: 트리가 완전히 커지기 전에 알고리즘을 멈춘다.
- post-pruning: 트리를 완전히 키운 다음에 가지치기를 한다. (generalization error를 계산하여 split 안 한 경우가 낳으면 prune_가지치기한다.), (generalization error를 계산할 때에는 원래 test set으로 구하는 거지만, training 과정 중에 post-pruning을 하는 것이므로, training set을 이용해 추측한다.(optimistic or pessimistic error))

Assumption(가정): No assumption (다른 머신러닝 알고리즘처럼 Linearity나 분포에 대한 가정이 필요없다.)
Parameter: No parameter

2. Random Forest (랜덤 포레스트)

Decision Tree의 특정 데이터에만 잘 작동할 가능성이 크다는 단점을 극복하기 위해 만들어진 알고리즘으로, 같은 데이터에 대하여 Decision Tree를 여러 개 만들어, 그 결과를 종합해 내는 방식이다. 이와 같은 기법을 앙상블 이라고 하는데, 이를 통해 정확도와 안정성을 높일 수 있다. 

 랜덤 포레스트의 원리.

이 때, 많은 decision tree를 생성해내기 위해서 bootstraping을 하는데 이 때 bagging을 통해 random하게 샘플을 뽑고 boosting을 통해 여러개의 모델에 fitting 시킨다. 이 때, 랜덤포레스트는 tree를 더 많이 fitting 시킨다고 더 많이 fitting되지 않는다.

Random Forest의 variable importance는 MDI(mean decrease impurity) 혹은 MDA(mean decrease accuracy)를 통해 알 수 있다.