[ML] 의사결정나무(Decision Tree) 뿌시기

* <데이터 과학자와 데이터 엔지니어의 인터뷰 문답집>을 참고하여 작성되었습니다.

의사결정나무(Decision Tree) 뿌시기

의사결정나무란?

• 의사결정나무는 데이터의 feature의 값에 따라서 분기를 나누면서 트리 구조를 만들고, 이를 이용해 분류나 회귀 문제를 푸는 모델이다.

의사결정나무의 장단점

• 장점: 인간이 실제로 하는 판단과 과정이 비슷하기 때문에 직관적이고, 설명하기 쉽다.
• 단점: 과적합의 위험이 크다.

의사결정나무가 만들어지는 방식

feature들을 통해서 분기를 나누면서 데이터를 예측하는 방식으로, 최적의 의사결정모델을 구하는 방식은 NP-hard 문제에 속한다. 따라서 의사결정나무는 분기를 나눌 feature를 정할 때, 휴리스틱 함수를 이용한다. 휴리스틱 함수는 위키백과의 정의에 따르면 "가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수"라고 정의 했다. 의사결정나무는 즉 모든 경우를 고려하여 최적의 트리를 만드는 방식이라기 보다는, 분기를 나눌때마다 휴리스틱 함수에 따라서 그때그때 최선의 feature를 선택하는 그리디 방식에 가깝다고 볼 수 있다.

의사결정나무를 만드는 데 사용되는 휴리스틱 함수는 최대정보이득, 최대정보이득비율, 지니계수가 있다.이 세 휴리스틱 함수는 각각 의사결정나무를 만드는 알고리즘인 ID3, C4.5, CART 알고리즘에서 사용된다.

• 최대 정보 이득

최대 정보 이득을 구하기 위해서는 먼저 엔트로피에 대해서 알아야한다. 여기서 말하는 엔트로피는 열역학의 엔트로피는 아니고, 정보이론에서 말하는 엔트로피이다. 정보이론은 엔트로피라는 개념을 도입해 어떤 사건을 통해서 얻을 수 있는 "정보량"을 표현하고자 했다. 정보이론은 어떤 사건이 흔하게 발생하는 사건이면 그 사건은 새로운 정보를 주지 못하기 때문에 정보량이 낮고, 드물게 발생하는 사건이면 반대로 정보량이 높다고 한다. 엔트로피는 이 정보량의 평균을 의미한다.

이 정보량의 평균, 즉 엔트로피는 조건에 따라 변화하기도 한다. 아무런 데이터 없이 미래를 예측하는 것은 어렵다. 예상 가능한 미래의 사건이 수 없이 많을 것이고, 가능한 사건이 많다보니 각각의 확률도 낮아 결국 평균 정보량이 높아진다. 엔트로피가 높다. 하지만 과거의 데이터가 있다면 미래 예측은 좀 더 쉬워지게 된다. 이러한 사전정보로 인해 미래 예측에 대한 엔트로피가 낮아진다.

정보 이득(information gain)은 어떤 feature를 따라 분류했을 때 엔트로피가 낮아지는 정도라고 생각하면 된다. 이 경우엔 엔트로피를 최대한 많이 낮출 수 있는 feature를 찾아 분기를 만든다.

• 최대 정보 이득비

정보 이득이 단순히 줄어드는 엔트로피의 값을 이용해 계산하는 것이라면, 정보 이득 비는 해당 feature에 따른 엔트로피와 그 feature가 주는 정보 이득 사이의 비율을 이용해서 계산한다. 이렇게 하는 이유는 feature의 종류의 수에 따른 불균형을 보정해주기 위한 것이다.

가능한 종류가 수없이 많은 feature의 경우, 당연하게도 정보이득이 굉장히 크다. 예를 들어 사람을 DNA 변수로 분류를 한다고 했을 때, 사람마다 전부 DNA가 다르기 때문에 각각 DNA의 확률도 낮아지게 되고 결국 정보 이득이 커질 수 밖에 없다.

하지만 이런 정보 이득은 실제 예측에서는 의미가 없다. 사람마다 전부 다른 DNA로 분류를 예측한다는 것은 과적합을 부를 뿐이다. 이런 단점을 보정해주기 위해 제안된 것이 최대 정보 이득비다. 앞서 언급한 DNA 정보같은 경우는 정보 이득이 상당히 크지만 DNA에 따른 엔트로피도 클 것이기 때문에 ''정보 이득 비''에서는 이것이 보정이 된다.

• 지니 계수

지니계수는 CART에서 사용되는 휴리스틱 함수인데 CART는 다른 알고리즘과 약간 다른 것이 분기를 나눌때 항상 이진 트리의 형태로 나눈다. 예를 들어 성적이라는 변수에 상, 중, 하라는 값이 있을 때 다른 의사결정나무 알고리즘은 상, 중, 하로 분기를 나눌 수 있지만 CART는 성적이 상인 집합 또는 상이 아닌 집합 둘로만 나눌 수 있다. CART는 이런 식으로 모든 feature에 대해 두 집합으로 나눠보면서 지니계수를 계산하고 지니계수가 가장 낮은 feature를 선택한다.

지니계수를 사용하는 CART 알고리즘의 경우, 범주형 변수 뿐만 아니라 수치형 변수도 사용할 수 있다는 특징이 있다. 모든 분기에서 이진 분할을 사용하기 때문이다. (수치형 변수를 절반으로 나누면 된다) 또한 분류 뿐만 아니라 회귀 태스크에서도 지니계수 대신 MSE로 분기하는 방식으로 사용 가능하다.

왜 의사결정트리는 앙상블 모델에서 많이 쓰일까?

앙상블은 여러 모델을 융합하는 전략과 방법을 통칭해서 부르는 말이다. 앙상블의 주된 목적은 여러 모델의 결과를 사용해서 결과 값의 분산이나 바이어스를 줄이는 것이다. 그런데 이를 위해서는 여러 모델들이 다양한 값을 출력해야 한다. 모든 모델이 비슷한 값만 출력한다면 앙상블을 하나마나 의미가 없다.

이런점에서 의사결정트리가 앙상블에 최적인 모델이라고 볼 수 있다. 앙상블을 하는 과정에서 보통 학습 데이터에서 일정 비율의 샘플을 랜덤하게 추출해 여러개의 모델을 학습시키는 방법을 사용하는데 선형 회귀 등 다른 모델들은 학습 데이터가 조금 바뀌더라도 결과값이 크게 바뀌지 않는 반면 의사결정트리는 학습 데이터에 따라 트리 구조가 많이 바뀔 수 있다. 따라서 앙상블에서는 의사결정트리 모델을 많이 사용하게 된 것이다.

앙상블의 종류

앙상블에는 부스팅과 배깅이 있다. 부스팅은 여러개의 모델을 학습시킬 때, 전의 모델이 잘못 분류한 샘플에 대해 가중치를 줘서 다음 모델을 학습시킬 때 적용한다. 쉽게 말해서 부스팅에선 모델이 점점 발전하는 방식으로 학습이 된다고 할 수 있다. 이 방법은 마치 인간이 학습을 하는 과정과 비슷하다. 인간은 어떤 것을 처음 배울땐 서툴지만, 한번 두번 배우고나서 점점 과거에 실수했던 기억을 이용해 더 잘 배우게 된다.

반면 배깅의 경우는 모델들을 서로 독립적으로 유지시킨다. 대표적으로 랜덤 포레스트가 있다. 훈련 데이터셋에서 랜덤으로 샘플을 추출하고 각각 다른 데이터 셋 샘플을 만들어서 여러개의 모델을 훈련시킨다. 이렇게 훈련된 모델들은 서로 다른 데이터에서 학습되었으므로 상호 독립적이다. 이렇게 학습된 모델들은 투표(voting)를 이용해 최종 결과값을 결정하게 된다.

비유적으로 설명하면 부스팅은 직렬적, 배깅은 병렬적이다. 부스팅은 한 사람이 어떤 것을 여러 번 배우면서 익혀나가는 과정과 같다면 배깅은 여러 사람이 머리를 맞대고 의견을 모아 생각하는 것과 똑같다.

앙상블은 왜 사용하는가?

어떤 예측 모델의 불확실성을 설명할 때, 분산과 바이어스의 관점으로 설명할 수 있다. 분산은 훈련 데이터 셋이 가지고 있는 노이즈를 학습함에 의한 에러라면, 바이어스는 모델 자체의 성능에 따른 에러다.

부스팅 모델의 경우는 가중치를 이용해 모델을 점점 발전시키므로, 모델이 표현할 수 있는 범위를 늘려 모델의 "바이어스"에 따른 에러를 줄일 수 있다.

반면 배깅 모델의 경우는 훈련 데이터 셋에서 여러 샘플을 뽑아 여러 개의 모델을 학습시키므로 데이터 셋이 가지고 있는 노이즈가 희석 되어, 모델의 "분산"에 따른 에러를 줄일 수 있다.

앙상블의 결과를 병합하는 방법

기초 분류기의 결과를 병합하는 방법에는 투표(voting)와 스태킹(stacking)이 있다. 투표는 가장 많은 표를 얻은 결과를 출력하는 것이고, 스태킹은 모든 기초 분류기의 결과를 가중치에 따라 더한 값을 출력하는 것이다.