Machine learning #3 Decision tree

(1, 50) -> (1, 1) tabular data를 바탕으로 간단한 categorical 예측 모델을 MLP로 만들어 보았는데

 

category가 2개뿐임에도 불구하고, 독립변수가 50개로 너무 많아서 그런지

학습을 반복해도 accuracy가 0.4949에서 좋아지지 않는 것이 확인되어서 다른 model을 찾아보다가

인터넷에서 tubular data의 경우 random forest 모델이 효과가 좋다는 것을 반복하고 한번 돌려보았더니

일단 명시적인 accuracy는 70~80%로 좋아지는 것을 확인하였다. 

 

따라서 https://nogrowth.tistory.com/34

Deep learning 기초#1 - MLP

의 초반에서 다룬 지도학습의 다른 도구들을 한번 알아보기로 하였고, 첫째로 random forest에 대해 공부해보자.

참고로 저번 글에서 다룬 지도학습의 대표적인 algorithm들은 다음과 같다. 

Decision Tree, Random forest, KNN, SVM 

 

Random forest

위키피디아의 정의는 다음과 같다. 

 

Random forests or random decision forests is an ensemble learning method for classification, regression and other tasks that operates by constructing a multitude of decision trees at training time. For classification tasks, the output of the random forest is the class selected by most trees. For regression tasks, the mean or average prediction of the individual trees is returned. Random decision forests correct for decision trees' habit of overfitting to their training set.  Random forests generally outperform decision trees, but their accuracy is lower than gradient boosted trees. However, data characteristics can affect their performance.

 

정리하면 Ensemble learning의 한 method로서분류, 회귀 문제에 적용 가능하고multitude of decision tree 들을 구성하는 방법

 

Decision tree는 위에서 살펴보았듯 지도 학습의 알고리즘의 하나이므로, 이 알고리즘을 여러 개 사용하고, 그래서 forest라는 이름이 붙었다고 받아들이면 될 것 같다. 

 

분류에서 : 가장 많은 tree로 결정된 class를 반환한다. 회귀에서 : 각각 tree들의 결과의 평균을 반환한다. 

 

또한 Random forest는 decision tree의 특성인 overfitting을 교정하기 때문에 보통 더 성능이 좋으나

accuracy는 Gradient boosted tree보다는 낮다.

 

즉 Random forest를 이해하려면 Decision tree에 대한 이해가 선행되어야 하므로 이를 먼저 알아보자.

 

 

Decision Tree learning

Decision Tree에 대해 엄청 잘 설명해두신 blog가 있어서 이를 정리해본다.

Reference : https://sanghyu.tistory.com/8

Decision tree(의사결정나무) 원리

 

Tree란 결국 다음과 같다. 

의미를 부여해보면

Node : input data를 분류할 수 있는 특성, attribute or feature

Branch : Node에 해당되는 feature의 value

Leaf node : output

 

스무고개처럼 이런 의사결정 과정을 갖는 것을 Decision tree라고 하며

결국 좋은 Tree model을 구성하는 것은

Node, 즉 Input data를 분류하는 특성을 어떻게 배치하느냐가 중요하다. 

즉 위와 같은 상황에서 Outlook, Temperature과 같은 input feature들을

어떤 node에 어떤 순서로 배치하는지를 구성하는 것이 Tree model의 핵심이다.

 

Entropy 

1st row의 경우 다음 원도 채워진 원이라고 예상할 수 있다.

2nd row의 경우 예측이 더 어렵다.

 

이를 다시 표현하면

binary classification 시 Entropy의 식은 다음과 같다. 

(해당 상태의 확률 * 확률의 log2값)의 합의 음수

 

왜 그런가? Pk는 0~1 사이이며

Pk : 해당 상태일 확률

log2Pk : 해당 상태일 확률이 2(binary)의 몇 제곱인지 => 

  예를 들어 n개의 상태가 가능한 universe에서 Pk가 1/n이면 -1 / pk가 1이면 0을 갖는데

  얼마나 균일한 확률 분포를 갖는지에 대한 값이다. 

 

정보의 일관성/순도가 높을수록 entropy는 낮아지고, 일관성이 없을수록 entropy는 증가하며

이는 0~1 사이의 값을 갖는다.

채워진 원 vs 빈 원을 찾는

binary classification 문제에서

전체 영역에 대한 binary entropy는

허나 R1, R2 두 영역으로 나눈 후 각각 구한 Entropy는

로 entropy가 낮아졌다!

즉 영역을 나눔으로써 예측에서의 의외성을 줄였다고 할 수 있다. 

이런 식으로 Tree의 entropy가 낮아지는 방향으로 모델의 구성을 진행하게 된다. 

 

이를 Tree model에 적용하면

영역을 나눈다는 행위 자체가 어떤 node를 사용하느냐 이기 때문에

각 node를 거칠 때 entropy가 얼마나 낮아지는지를 보면 node를 어떻게 배치하는 것이 효율적인지를 알 수 있게 된다.

 

Informaion gain

Tree를 평가할 때 information gain(=정보 획득량)이라는 변수를 사용하며, 이는 entropy와 연관이 있다.

Gain을 구하는 방법(ID3 방식)은 다음과 같다. 식을 음미해보면

Gain은 S와 A의 함수인데 이때 S는 주어진 데이터 전체를, A는 우리가 다루는 feature를 뜻한다.

 

전체 Entropy에서 뭘 빼는데, 뭘 빼냐?

feature A의 결과들에 대해서

개별 결과의 빈도와 entropy를 곱한 것을 뺀다.  

 

다시 말하면

상위 Entropy와

node를 지나고 난 후의 Entropy에, 해당 value에 속한 데이터의 개수를 가중치로 하여 곱해준 후, 모두 합한 것의

차이를 구하는 것이다. 

==> node를 지나고 나서 Entropy가 얼마나 감소하였는가? = Information gain

 

이는 node에도 적용할 수 있고 Tree에도 적용할 수 있으며

Gain이 높을수록 초기에 비해 Entropy가 많이 감소한 것이므로 나은 모델이라고 판단할 수 있다. 

 

Greedy algorithm

위의 information gain을 구하는 방식으로 Tree를 학습해나가는 것을 Greedy algorithm이라고 한다. 

예시는 다음과 같다.

이때 Wind라는 feature를 첫 node로 사용했을 때의 Gain을 구해보면

이런 방식으로 첫 node로 wind 대신 다른 feature를 사용한 경우와 비교할 수 있다.

gain이 가장 큰 feature(여기서는 Outlook)를 root node로 사용하고

Outlook node 이후 분류되는 value들에서 또다시 같은 방식으로 반복한다.

이를 가지치기(Pruning)라고 한다.

 

Overfitting

그렇다면 feature가 4개, output data가 10개 (10열)인 tabular data에서

계속적인 Tree 최적화를 통해

node가 엄청나게 많아서 100% 예측률을 보이게 된다면 이는 어떨까? 좋은 모델일까?

당연히 train data에서는 좋겠지만, 일반화가 잘 안 되는 문제가 발생하며 이를 overfitting이라 하며 Decicion Tree의 구조적인 문제이다. 

이렇게 test data에 대해 Entropy(S)가 0인 tree를 full tree라고 한다. 

1) Induction bias

따라서 이러한 현상을 방지하기 위해 induction bias를 사용하여 model에 제약을 걸어 Tree를 단순화시킬 필요가 있다.

Tree model의 경우 이러한 induction bias는

• depth의 maximum을 제한하는 방법
• leaves 개수의 maximum을 제한하는 방법

등이 있겠다. 

 

2) Pruning - 가지치기

다른 방법으로는 pruning이 있는데 방법은 다음과 같다. 

 

1. test data를 추가로 넣어본다. (validation set)

validation set를 넣어서 검증한 것과

하나의 split(분기)를 제거한 후 검증했을 때 성능이 증가한다면 해당 split을 pruning 한다. 

 

2. 통계적으로 유의한 지 확인해본다. 

위에서 얘기한 full tree가 문제가 되는 이유는, test data에 대해서는 100% 적합하지만 통계적 유의성이 없기 때문이다.

일반적으로 Chi-square test를 이용한다.

** 카이제곱 검정 자체가 관찰된 빈도와 기대 빈도가 의미 있게 다른지 확인하는 검정이다. 

 

위와 같은 그림에서 (빨간 점 class A, 초록 점 class B)

특정 node로 split이 이뤄졌을 때 

Lt. child로 가는 비율은

이로 계산한 class A와 class B가 Lt. child에 있을 기댓값은

이때 실제 NAL = 1, NBL = 4 이므로

기댓값과 실제값을 비교하여 "통계적으로 유의하게 다르다면" 문제가 된다. 

정리하면

위의 경우에 대입해보면

이 chi square 값이 작으면

=> information gain이 커서 분기했던 건데, 기댓값과 실제값의 차이가 작으므로 통계적으로 유의미하지 않다.

=> 의미 없는 분기이다.

=> split을 제거하자 = pruning 하자

 

값이 작은지 큰지 판단하는 threshold는 t라고 쓰며 

t가 작을수록 (그만큼 작은 chi square도 남게 되니까) tree는 복잡해지고 과최적화 위험이 높아진다. 

t가 클수록 tree는 단순해지고 과최적화 위험이 낮아진다. 

 

다른 방법으로

우리가 구한 chi square는 알려진 대로 chi square distribution을 따르기 때문에 이를 이용해 p-value를 구해서

우리의 p value보다 p threshold가 크면 pruning 하는 방법도 있다. 

이때의 p threshold를 MasPchance라고 표기한다.  

 

3) 비용 함수

full tree를 줄여나가는 다른 방법으로 비용 함수를 이용하는 것이 있다. 

CC(T) : Tree의 비용

Err(T) : 오류 비율

L(T) : 구조의 복잡도 = terminal node의 수

alpha : 가중치, 보통 0.1~0.01

 

이러한 비용 함수가 최소화되는 L(T)를 구해서 이용하는 방법이다. 

 

 

---

여기까지 Random forest를 알아보려다가

Decision tree의 기본적인 의미와 구성에 대하여 알아보았다. 

다음 글에서 마저 Random forest에 대해 알아보자!