[ML] 직관적인 모델 의사결정나무와 강한 학습기 앙상블

이번 글은 순천향대학교 정영섭 교수님의 강의와 우지영 교수님의 강의, 도서 핸즈온 머신러닝 2판을 참고했음을 먼저 밝힙니다.

 

순서

1. 의사결정나무

1.1. ID3 알고리즘

1.2. CART 알고리즘

 

2. 앙상블

2.1. Voting

2.2. Bagging

2.3. Boosting

2.4. Stacking

 

1. 의사결정나무

의사결정나무(DecisionTree)는 결정 트리라고도 불리는 머신러닝 알고리즘입니다. 결정할 수 있는 기준을 학습하는 알고리즘으로 패턴을 예측 가능한 규칙들의 조합으로 나타내고 이 모양이 tree와 같은 알고리즘입니다.

의사결정나무의 구성은 조건문(internal node), 조건 결과에 따른 분기(Edge), 결과(Extenal node 또는 Terminal node), 깊이가 0인 맨 꼭대기의 루트 노드(root node), 루트 노드에서 왼쪽을 자식 노드(child node), 맨 아래 노드들처럼 자식 노드를 가지지 않는 리프 노드(leaf node) 입니다. 사각형인가?와 같이 조건문이 주어지면 조건 결과에 따라 분기됩니다. 분기된 후 한 노드의 모든 샘플이 같은 클래스에 속해 있다면 이 노드를 순수하다고 하고 이를 gini 점수가 0이라고 합니다. gini 불순도는 불순도를 측정하는 지표이고 불순도를 측정하는 방법에는 entropy도 있습니다. entropy는 분자의 무질서함을 측정하는 것으로 분자가 안정되고 질서 정연하면 entropy가 0에 가까워지는 이론을 적용한 것입니다. 어떤 세트가 한 클래스의 샘플만 담고 있다면 entropy가 0입니다. gini와 entropy 수식 값의 범위는 0~1로 0일수록 깨끗한 노드입니다. 위 시각화에서 루트 노드의 왼쪽 자식 노드를 보면 gini 값이 0이고 이 노드는 모든 샘플이 같은 클래스에 속하기 때문에 더 이상 분리할 수 없습니다.

 

만약 모든 리프 노드들이 더이상 분리될 수 없다면 학습은 끝납니다. 이처럼 불순도가 낮아지는 방향으로 나눠야하고 이 방법으로는 ID3, CART, C4.5 등 여러가지 알고리즘이 있습니다.

 

 

1.1. ID3 알고리즘

이 중 ID3 알고리즘에 대해 다루겠습니다. ID3알고리즘은 루트노드에서는 모든 데이터를 고려한다고 가정하고 자식노드로 내려가면서 데이터들을 분류합니다. (둘 이상의 자식노드를 가질 수 있음.) 이때 자식노드는 부모노드에서 고려한 feature는 더 이상 고려하지 않는다는 특성을 갖고 있습니다. 노드에서 고려할 데이터가 이미 하나의 class 에만 속하였거나, 더 이상 고려할 feature가 없으면 leaf node로 여기고 더 이상 자식노드를 생성하지 않습니다. 고려할 feature가 더 이상 없어져 leaf node가 된 경우 가장 많은 수의 class를 결과값으로 채택합니다. 각 노드에서 고려할 feature를 선택할 때는 데이터들을 가장 잘 나눠주는 feature를 선택합니다. 이때 leaf node에서 완벽하게 나눠진다는 보장은 없습니다. 만약 label이 섞여있으면 또 나누고, 더 이상 나눌 label이 없으면 leaft node가 되는 것입니다. 이 경우 이상적인 경우라면 label이 다소 섞여있어도 몇 개 이하라면 나누지 않습니다. 선택된 feature에 대한 조건 별로 자식 노드를 계속 생성합니다.

 

이때 가장 잘 나눠주는 feature를 찾기 위해 entropy개념을 이용합니다. 부모노드의 entropy에서 자식노드의 entropy값을 뺀 information gain이라는 값을 사용합니다. information gain은 0~1사이의 값을 가집니다. 즉, 가지를 칠 때 information gain이 가장 큰 feaature를 선택하는 것입니다. 

 

weighted average 구하는 것에 주의하세요! 잊고 계산을 하지 않을 때가 있답니다. 

 

ID3알고리즘의 단점은 독립변수가 모두 범주형일때만 가능하다는 것입니다. 그렇다면 실수형일 때 ID3알고리즘을 어떻게 사용할 수 있을까요? 구간을 정해서 하나의 카테고리인 것처럼 만듭니다. 이를 bin 생성이라고 합니다. bin 생성 시 계산량을 줄어들겠지만 잃는 값이 있을 수 밖에 없기 때문에 (정보손실량이 증가하여) 정확도가 낮아집니다. 데이터의 성격을 보고 bin을 생성해도 되는지 그렇지 않은지 결정해야합니다. 예를 들어 1과 31의 값은 분명 다른데 bin을 생성하여 같은 것으로 볼 수도 있습니다. 데이터의 성격에 따라 문제가 되지 않을 지 고려합니다. 

 

좋은 트리는 leaf node에서 통일된 label의 데이터만 남아 분류와 의사결정의 정확도가 높은 트리, 트리의 높이가 짧아 빠른 수행 속도를 가지는 트리라고 간주합니다. 

 

1.2. CART 알고리즘

Python의 sklearn 패키지의 의사결정나무는 CART 알고리즘을 사용합니다. 훈련 세트를 하나의 특성 k의 임계값 $t_k$를 사용해 rkwkd tnstngks 두 개의 서브셋으로 나눕니다. (ID3알고리즘과 달리 자식 노드를 2개씩 가짐.) 같은 방식으로 서브셋을 나누기 위한 특성 k와 임계값 $t_k$를 찾는 과정을 반복합니다. 이때 max_depth가 되거나, 불순도를 더이상 줄이는 분할을 찾을 수 없다면 알고리즘이 중단됩니다. 크기에 따른 가중치가 적용된 가장 순수한 서브셋으로 나눌 수 있는 (k, $t_k$) 짝을 찾을 때 알고리즘이 최소화하는 비용함수는 아래와 같습니다.

 

각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도는 특성의 수와 무관하게 약 O(log2(m))개의 복잡도를 갖습니다. 이때 m은 훈련 데이터의 수 입니다. 또한 훈련 아로리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교하므로 약 O(nxm(log2(m))입니다. 훈련 데이터가 적을 경우 sklearn의 DecisionTreeClassifier 를 사용할 때 presort=True로 파라미터를 설정하면 미리 데이터를 정렬하여 속도를 개선할 수 있습니다. 

 

CART알고리즘은 불순도를 선택할 수 있습니다. gini 불순도와 entropy는 실제로는 큰 차이가 없고 둘 다 비슷한 트리를 만들어냅니다. gini 불순도가 조금 더 계산이 빨라 기본값으로 사용하기 좋지만 가장 빈도 높은 클래스를 한쪽 가지로 고립시키는 경향이 있는 반면 entropy는 조금 더 균형 잡힌 트리를 만들 수 있습니다.

 

의사결정나무는 특성 중요도를 확인할 수 있습니다. 노드에 사용된 특성별로 (현재 노드의 샘플 비율x불순도)-(왼쪽 자식 노드의 샘플 비율x불순도)-(오른쪽 자식 노드의 샘플 비율x불순도)로 계산하여 더하고, 중요도 합이 1이 되도록 전체 합으로 나누어 정규화합니다. 

 

이처럼 예측을 만드는 연산 과정을 쉽게 확인할 수 있기 때문에 직관적이고 결정 방식을 이해하기 쉽습니다. 이러한 모델을 화이트박스 모델라고 합니다. 랜덤포레스트나 신경망은 성능이 뛰어나고 예측을 만드는 연산 과정을 쉽게 확인할 수 있지만 왜 그런 예측을 만드는지는 쉽게 설명하기 어렵습니다. 이를 블랙박스 모델이라고 합니다. 다음은 랜덤포레스트와 같은 앙상블 모델에 대해 다루겠습니다.

 

2. 앙상블

앙상블 모델은 여러 개의 모델을 합친 모델입니다. 무작위로 선택된 수천 명의 사람에게 복잡한 질문으로 하고 대답을 모은다고 가정합니다. 이렇게 모은 답이 전문가의 답보다 낫습니다. 이를 대중의 지혜라고 합니다. 이 이론에서 나온 것으로 여러 개의 모델을 사용하면 하나의 모델보다 더 좋은 예측을 얻을 수 있을 것이다라는 알고리즘입니다. 앙상블은 Voting(투표 기반), Bagging, Boosting, Stacking 등이 있고 의사결정나무의 앙상블을 랜덤포레스트라고 합니다.

 

2.1. Voting

Voting은 여러 개의 분류기의 예측을 모아서 가장 많이 선택된 클래스롤 예측하는 것으로 다수결 투표로 정해지는 직접 투표 (hard voting)분류기와 분류기의 예측을 평균 내어 확률이 가장 높은 클래스를 예측하는 간접 투표(soft voting) 분류기가 있습니다. 

 

2.2. Bagging

Bagging은 Voting과 동일한 방식이지만 같은 분류기들을 이용한다는 것이 차이점입니다. 

 

Voting와 Bagging

같은 분류기를 이용하는 방법에도 훈련 세트에서 중복을 허용하여 샘플링하는냐 그렇지 않느냐에 따라 배깅과 페이스팅으로 나뉩니다. 그렇기 때문에 Bagging만이 같은 훈련 샘플을 여러 번 샘플링할 수 있습니다. 보통 분류일 때는 직접 투표처럼 통계적 최빈값을 사용하고 회귀일 때는 평균을 계산합니다. 개별 예측기들은 훈련 세트로 훈련시킨 것보다 훨씬 크게 편향되어 있지만 배깅의 수집 함수(통계적 최빈값 또는 평균)를 사용하면 편향과 분산이 모두 감소합니다. 일반적으로 앙상블의 결과는 편향은 비슷하지만 분산이 줄어듭니다. 배깅은 다른 CPU 코어나 서버에서 병렬로 학습할 수 있는 확장성 덕분에 인기가 높습니다. 

 

배깅은 훈련 샘플 뿐만 아니라 특성도 샘플링할 수 있습니다. 무작위로 선택한 입력 특성의 일부분과 훈련 샘플 보다 샘플링하는 것을 랜덤 패치 방식, 훈련 샘플은 모두 사용하고 특성만 샘플링하는 방식을 랜덤 서브스페이스 방식이리고 합니다. 이런 특성 샘플링은 더 다양한 예측기를 만들 수 있고 편향을 늘리는 대신 분산을 줄여줍니다. 

 

샘플링할 때 어떤 샘플은 한 예측기를 위해 여러 번 선택되지만 어떤 샘플은 전혀 선택되지 않을 수도 있습니다. 평균적으로 각 예측기에 훈련 샘플의 63%정도만 샘플링되는데 이때 선택되지 않은 37%의 샘플들을 oob(out of bag)샘플이라고 합니다. 각 예측기마다 남겨진 37%는 모두 다르고 이 샘플들을 검증하는데 사용할 수 있습니다. 

 

2.3. 랜덤포레스트

배깅의 대표적인 알고리즘이 랜덤포레스트입니다. 랜덤포레스트는 트리를 만들 때 각 노드에서 무작위로 특성의 서브셋을 만들어 분할에 사용합니다. 즉, 트리의 노드를 분할할 때 무작위로 선택한 특성 후보 중에서 최적의 특성을 찾는 식으로 무작위성을 더 주입합니다. 트리를 다양하게 만들고 편향이 높아지지만 분산을 줄여 더 좋은 모델을 만듭니다. 

 

랜덤포레스트의 트리를 더욱 무작위하게 만들기 위해 최적의 임계값을 찾는 대신 후보 특성을 사용해 무작위로 분할한 다음 최상의 분할을 선택하는 랜덤포레스트를 익스트림 랜덤 트리 앙상블이라고 합니다. 이 모델 역시 편향이 늘어나고 분산이 줄어듭니다. 특성마다 가장 최적의 임곗값을 찾는 것은 시간이 가장 많이 소요되는 작업이기 때문에 랜덤포레스트보다 훨씬 더 빠르다는 장점이 있습니다. 둘의 성능은 둘 다 시도해보고 교차검증으로 비교하는 것이 유일합니다. 

 

랜덤포레스트는 의사결정나무처럼 특성 상대적 중요도를 측정할 수 있습니다. 어떤 특성을 사용한 노드가 평균적으로 불순도를 얼마나 감소시키는지 확인하여 특성의 중요도를 측정합니다. 각 결정 트리의 특성 중요도를 모두 계산하여 더한 후 트리 수로 나눈 값입니다. 

 

2.4. 부스팅

부스팅은 훈련한 이전 모델을 보완해나가면서 일련의 예측기를 학습하는 방법입니다. 대표적인 방법은 AdaBoost, GradientBoosting 방법이 있습니다. 

 

AdaBoost는 이전 모델이 틀린 부분을 adaptive 하게 바꾸어가며 잘못 분류되는 데이터의 가중치를 높이는 것입니다. 

이렇게 하면 새로운 예측기는 학습하기 어려운 샘플에 점점 더 맞춰집니다. 모든 예측기가 훈련을 마치면 배깅과 같은 방식으로 예측을 만듭니다. 가중치가 적용된 훈련 세트의 전반적인 정확도에 따라 예측기마다 다른 가중치가 적용됩니다. 연속된 학습 기법이므로 병렬화 할 수 없어 낮은 확장성을 갖고 있습니다. 

 

AdaBoost

 

Gradient Boosting은 이전 예측기가 만든 잔여 오차에 새로운 예측기를 학습하는 방법입니다. 경사하강법을 이용하여 손실함수를 정량화합니다. 손실함수를 파라미터로 미분해서 기울기를 구하고 이 손실 값이 작아지는 방향으로 파라미터를 움직이게 하는 학습 방법입니다. 

Gradient Boosting

2.5. Stacking

스태킹은 훈련 데이터와 검증데이터로 나눈 후 훈련 데이터를 학습하고 검증 데이터를 target으로 사용하는 것입니다. 훈련 데이터의 예측값들을 새로운 훈련 세트로 만드는 방법입니다.