[ML Specialization / Andrew NG] W7 Decision Tree models

1) Decision Trees

 

tree는 X가 질적변수일 때만 가능하다고 오해했었는데, 양적변수일 때도 가능하다.

 

의사결정 트리를 만들 때 무엇을 고려해야할까?

1. root node에 어떤 feature을 쓸지 -> maximize purity (entropy 개념)

2. 각각의 node에서 어떤 기준으로 split 할지 -> entropy 개념

3. 언제 tree를 중단할지-> 100% cat or 100% dog으로 나눠질 때 / maximum Depth / purity score의 improvements가 임계보다 낮을 때 / node의 예시 개수가 임계보다 낮을 때.

 

 

2) Decision tree learning

다 cat or 다 dog -> pure한 상태.

그 사이라면 얼마나 pure한지 어떻게 파악할까? -> entropy(as a measure of impurity)라는 개념이 도입된다.

한 노드에서 cat(o)이 3개, dog(x)가 3개로 oooxxx인 상황에서

p1 = cat의 비율 이라 하면, p1 = 3/6이다.

H(p1) = value of entropy of p1은 1일때(p1=1/2일때) 가장 높고, 0이나 1일때(p1=0, 1일때)가장 낮다.

p0 = 1-p1이므로, $H(p_1) = -p_1log_2p_1 - p_0log_2p_0 = -p_1log_2p_1 - (1-p_1)log_2(1-p_1)$으로 쓸 수 있다. ($0*log0 = 0$)

 

그렇다면, 엔트로피를 이용하여 split을 choosing하는 법에 대해 알아보자.

어느 feature을 각 node에 쓸지를 정할 때는 Information gain이라는 척도를 이용한다.

root node의 상황에서, p1=0.5이므로 H(p1)=1이다.

Ear Shape, Face Shape, Whiskers 변수에 대해 split 했을때의 entropy를 위의 그림에서 확인할 수 있다.

split하기 전의 entropy - split한 뒤의 entropy의 평균(비율고려) = Information gain 이다.

잘 split 됐을 수록 impurity의 값인 entropy는 줄어들고, 그만큼 information gain값은 높다.

그러므로 위의 예시에서는 root node를 Ear Shape으로 선택하게 된다.

Information gain(reduction in entropy) = $H(p_{1}^{root})-(w^{left}H(p_1^{left})+w^{right}H(p_1^{right}))$

 

과정을 요약하면 아래와 같다.

1 root node에서 all examples와 함께 시작한다

2 모든 가증한 features에 대해 information gain을 계산하고, 가장 높은 information gain을 갖는 한 변수를 선택한다.

3 선택된 feature에 대해 데이터를 split하고, 나무의 왼쪽과 오른쪽 가지들을 만든다.

4 이러한 과정을 stopping criteria를 만날 때 까지 반복한다.

    (정지기준: 100% / maximum depth / information gain의 변화가 임계 이하 / node의 example 개수가 임계 이하)

 

만약, 2개 이상의 discrete option이 있다면 어떨까? (one-hot coding)

ex) Ear shape(x1)이 pointy, oval, floppy로 3가지 가능한 값이 있을때, 원핫코딩이라는 방법을 사용한다.

질적변수가 가능한 값이 k개 있을 때, k개의 binary feature을 생성한다.

 

만약, 질적변수가 아닌 양적변수(Continuous features)가 있을 때는 어떨까?

ex) Weight(x4)가 양적변수일때, $weight \leq 8$과 같이 임계점에 대해 split 한다.

이러한 임계점(threshold)는 8, 9, 13 등의 값에 대한 information gain을 구해서 이것이 가장 클 때의 값으로 정한다.

weight feature의 값이 k개면 임계점후보는 k-1개이다.

 

만약, 의사결정트리의 목적이 분류가 아닌 회귀라면 어떨까? Regression with Decision Trees: Predicting a number

동일하게 의사결정트리를 진행하고, leaf node에 도달하면 해당 예시들의 Y값 평균을 구한다.

이때, choosing a split의 기준은 reduce the variance of weights of Y이다. 분산이 엔트로피(H(p1)) 역할을 한다.

위의 예시에서는 분산을 기준으로 구한 information gain이 가장 큰 Ear Shape을 고른다.

 

3) Tree ensembles

단일 의사결정트리의 단점은, highly sensitive(not robust)하다는 것이다. 예를 들어, 10개의 input data 중 1개를 cat에서 dog로 바꾸면 트리의 전체 형태가 달라진다. 이를 해결하기 위해서는 여러 의사결정트리를 옆으로 쌓아 많은 트리들의 더미를 학습하면 더 정확한 결과가 나온다.

 

앙상블에는

배깅(Bagging; Bootstrap Aggregating): 랜덤 포레스트

부스팅(Boosting): AdaBoost, Gradient Boosting(GBM), XGBoost, LightGBM(LGBM), CatBoost

스태킹(Stacking)이 있다.

 

배깅에서 복원추출(sampling with replacement)를 통해 원래 데이터셋에서 서로 다른 부트스트랩 샘플을 만들어낸다. 이 새로운 training set을 통해 여러개의 트리모델에 조금씩 다른 데이터를 학습시키어 앙상블 효과를 강화시킨다.

 

 

배깅 알고리즘 중에서 가장 대표적인 알고리즘인 랜덤포레스트(Random Forest)에 대해 알아보자.

이후, B개의 트리들의 결과를 합쳐서 final prediction을 정한다.

B가 커질수록 성능이 안좋아지지는 않지만, 계산량이 늘어나므로 return이 점점 줄어든다. 100주변인 64~128을 추천한다.

랜덤 포레스트(Random Forest)는 배깅(Bagging) 알고리즘에서 '추가적인 무작위성(randomness)'를 더한 버전이다.

즉, 기존의 배깅은 복원 추출로 만든 부트스트랩 샘플을 같은 알고리즘 여러개가 학습한다. 그러나, 복원 추출을 이용하면 데이터가 변해도 일부분만 변하므로, 첫번째 노드의 feature은 거의 변하지 않는다. tree를 더 다양화하여 정확도를 높이기 위해서, 첫 node도 다르게 하기 위해 randomness를 더한다.

각 노드에서 feature을 정할 때, n개의 feature 후보가 있다고 하면 그중의 일부인 k(k<n)개 feature의 subset을 뽑고, 그 subset에서만 feature을 고를 수 있도록 한다. 보통 $k=sqrt{n}$이다.

이렇게하면 tree ensemble은 more robust하고, 더 잘 작동하는 Random Forest Algorithm이 된다.

 

 

이번에는, 부스팅 알고리즘 중에서 가장 대표적인 알고리즘인 XGBoost(XGB)에 대해 알아보자.

피아노를 배울 때 틀렸던 부분만 연습하는것 처럼, 이전 모델의 결과를 보고 not yet doing well인 subset of data에 집중하여 input 데이터를 뽑아낸다. b=B일때, b=1, 2, ... B-1의 tree 결과를 참조하여 still not doing well data를 뽑을 확률을 높여서 new tree에 학습하는 방법을 통해 더 빨리 정확도가 높아지도록 하는 것이 부스팅 알고리즘의 원리이다.

 

XGBoost(eXtreme Gradient Boosting)은 부스팅에서 가장 많이 사용하는 알고리즘이다.

빠르고 효율적인 구현이 가능하며, splitting criteria와 정지규칙 디폴트가 잘 설정되어있고, 오버피팅을 막기 위해 정규화 기법을 사용한다. 캐글 대회 등 머신러닝 competition에서 매우 경쟁력있는 알고리즘이다.

 

 

신경망과 비교해서, 언제 decision tree나 tree ensemble을 사용할까?

의사결정트리는 tabular/structured(정형) 데이터에서 잘 작동하지만, 이미지, 텍스트, 오디오 등에서는 잘 작동하지 않는다. 또한, 학습이 빠르다는 장점과 작은 트리는 human interpretable하다는 특성이 있다.

 

신경망은 정형/ 비정형 상관없이 모든 종류의 데이터에서 잘 작동하지만, 의사결정트리보다 느리다. 또한, transfer learning(전이학습)과도 잘 작동한다는 장점과, 여러 모델이 함께 작동할때 트리는 하나씩 학습하는 반면 NN은 여러 신경망을 한번에 묶어서 학습할 수 있다는 특성이 있다.

 

<>
Tree에 대한 설명과, 앙상블에대한 설명.

그리고 앙상블에서 배깅+랜덤포레스트/ 부스팅+XGBoost에 대한 설명까지 내용구성이 알찼다. 배깅의 원리에서는 부트스트랩의 기본 로직인 sample with replacement 정도만 설명했고, 부스팅의 원리에 대해서는 수학적인 내용이 하나도 포함되지 않고, 그냥 이전 모델에서 부정확했던 subset of data가 다음 모델의 input으로 추출될 확률을 높인다는 다소 추상적인 로직만 설명해준 점이 인상적이다. 부스팅의 수학적 원리에 대해 찾아보고 여러 부스팅 알고리즘의 차이점에 대해서도 알아봐야겠다.

<>