이 글에선 한 번에 하나씩의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘인 의사결정 나무(Decision Tree)에 대해 다뤄보도록 하겠습니다.
1. 의사결정 나무(Decision Tree)란?
의사결정 나무는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 나무와 같다고 해서 의사결정 나무라 불린다. 아래 예시를 보자.
위 예시는 운동경기가 열렸다면 PLAY = 1, 그렇지 않으면 Play = 0으로 하는 이진분류 문제이다. 모든 사례를 조사해 그림으로 도식화하면 위와 같은 그림이 될 것이다. 그림을 해석해보자면 날씨가 맑고(sunny), 습도(humidity)가 70 이하인 날엔 경기가 열렸다. 해당 조건에 맞는 데이터들이 '경기가 열렸다(Play 2건)'고 말하고 있기 때문이다. 반대로 비가 오고(rain) 바람이 부는(windy) 날엔 경기가 열리지 않았다. 의사결정 나무를 일반화한 그림은 아래와 같다.
의사결정 나무는 트리 자료구조와 동일한 모양이다. 초기 지점은 root node이고 분기가 거듭될 수록 그에 해당하는 데이터의 개수는 줄어든다. 각 terminal node에 속하는 데이터의 개수를 합하면 rood node의 데이터 수와 일치한다. 바꿔 말하면 terminal node 간 교집합이 없다는 뜻이다. 한편 terminal node의 개수가 분리된 집합의 개수가 된다. 예컨대 위 그림처럼 terminal node가 3개라면 전체 데이터가 3개의 부분집합으로 나눠진 셈이다.
의사결정 나무는 분류(classification)와 회귀(regression) 모두 가능하다. 즉 범주나 연속형 수치 모두 예측할 수 있다. 의사결정 나무의 범주 예측, 즉 분류 과정은 이렇다. 새로운 데이터가 특정 terminal node에 속한다는 정보를 확인한 뒤 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류하게 된다. 운동경기 예시를 기준으로 설명하면 날씨는 맑은데 습도가 70이 넘는 날은 경기가 열리지 않을 거라고 예측한다.
회귀의 경우 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 된다 이 때 예측값의 종류는 terminal node 개수와 일치한다. 만약 treminal node 수가 3개뿐이라면 새로운 데이터가 100개, 1000개가 주어진다고 해도 의사결정 나무는 오직 3종류의 답만을 출력한다.
그렇다면 데이터를 분할한다는건 정확히 어떤 의미를 지니는 걸까? 설명변수(X)가 3개짜리인 다변량 데이터의 의사결정 나무를 적용한다고 가정하고 아래 그림을 보자.
아무런 분기가 일어나지 않은 상태의 root node는 A이다. 변수가 3개짜리이니 왼쪽 그래프처럼 3차원 공간에 있는 직육면체를 A라고 상정해도 좋을 것 같다. A가 어떤 기준에 의해 B와 C로 분할됐다고 생각해 보자. 그렇다면 두 번째 그림처럼 A가 두 개의 부분집합으로 나뉘었다고 상상해 볼 수 있다. 마지막으로 B가 D와 C로 분할됐다면, 3번째 줄의 그림처럼 될 것이다. 이 예시에서 terminal node는 C, D, E 세 개인데, 이를 데이터 공간과 연관 지어 생각해보면 전체 데이터 A가 세 개의 부분 집합으로 분할된 것 또한 알 수 있다. D 특성을 가지는 새로운 데이터가 주어졌을 때 의사결정 나무는 D 집합을 대표할 수 있는 값(분류=최빈값, 회귀=평균)을 반환하는 방식으로 예측한다.
2. 불순도/불확실성?
의사결정 나무는 한번 분기 때마다 변수 영역을 두 개로 구분하는 모델이다. 그렇다면 대체 어떤 기준으로 영역을 나누는 것일까? 이 글에서는 타겟 변수(Y)가 범주형 변수인 분류 나무를 기준으로 설명하겠다. 결론부터 말하면 분류 나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행한다. 순도가 증가/불확실성이 감소하는 걸 두고 정보이론에서는 정보획득(information gain)이라고 한다. 이번 글에서는 어떤 데이터가 균일한 정도를 나타내는 지표, 즉 순도를 계산하는 2가지 방식에 대해 살펴보도록한다. 아래 그림을 보자.
먼저 살펴볼 지표는 엔트로피(entropy)이다. m개의 레코드가 속하는 A영역에 대한 에트로피는 아래와 같은 식으로 정의 된다. (Pk = A영역에 속하는 레코드 가운데 k 범주에 속하는 레코드의 비율)
이 식을 바탕으로 오렌지색 박스로 둘러쌓인 A영역의 엔트로피를 구해보자. 전체 16개(m = 16) 중에 빨간색(범주 : 1)은 10개 파란색(범주 : 2)은 6개가 있다. 그럼 A영역의 엔트로피는 다음과 같다.
여기서 A 영역에 빨간색 점선을 그어 두개 부분집합(R1, R2)으로 분할한다고 가정해보자. 두 개 이상 영역에 대한 엔트로피 공식은 아래와 같다. 이 공식에 의해 분할 수 A 영역의 엔트로피를 아래와 같이 각각 구할 수 있다. (Ri = 분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드의 비율)
분기 전과 분기 전 엔트로피는 0.95였는데 분기한 뒤에 0.75가 된 것을 알 수 있다. 0.2만큼 엔트로피가 감소한 것이다. 이는 불확실성 감소, 순도 증가, 정보획득으로 해석할 수 있다. 따라서 의사결정 나무 모델은 분할한 것이 분할 전보다 낫다는 판단 하에 데이터를 두 개의 부분집합으로 나누게 된다. 다시 정리하자면 의사결정 나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가/불확실성(엔트로피)이 최대한 감소하도록 하는 방향으로 학습을 진행한다.
순도와 관련해 부연설명을 하자면 A 영역에 속한 모든 레코드가 동일한 범주에 속할 경우(=불확실성 최소=순도 최대) 엔트로피는 0이다. 밑이 2인-log그래프를 떠올려보면 log의 진수가 1에 가까울 수록 그 결괏값이 0에 가까워지기 때문이다. 이는 순도가 100퍼센트인 상태로 볼 수 있다. 반대로 범주가 둘 뿐이고 해당 개체의 수가 동일하게 반반씩 섞여 있을 경우(=불확실성 최대=순도 최소) 엔트로피는 1의 값을 가진다. 엔트로피 외에 불순도 지표로 많이 쓰이는 지니계수(Gini Index) 공식은 아래와 같다.
3. 모델 학습
의사결정 나무의 학습 과정은 입력 변수 영역을 두 개로 구분하는 재귀적 분기(recursive partitioning)와 너무 자세하게 구분된 영역을 통합하는 가지치기(pruning)두 가지 과정으로 나뉜다. 우성 재귀적 분기 먼저 살펴보자.
3.1 재귀적 분기
아래와 같이 24개 가정을 대상으로 소득(Income), 주택 크기(Lot size), 잔디 깎기 기계 구입 여부(Ownership)를 조사한 데이터가 있다. 이를 토대로 소득과 주택 크기를 설명변수(X), 기계 구입 여부를 종속변수(Y)로 하는 분류 나무 모델을 학습시켜 보자.
우선 이를 한 변수 기준(예컨대 주택 크기)으로 정렬한다. 이후 가능한 모든 분기점에 대해 엔트로피/지니 계수를 구해 분기 전과 비교해 정보획득을 조사한다. 예컨대 아래 표 기준으로 보면 분기 지점을 첫 레코드와 나머지 23개 레코드로 두고, 1번 레코드와 2~24번 레코드 간의 엔트로피를 구한 뒤 이를 분기 전 엔트로피와 비교해 정보획득을 조사한다. 그 결과는 아래와 같다.
이후 분기 지점을 두 번째 레코드로 두고 처음 두 개 레코드와 나머지 22개 레코드 간의 엔트로피를 계산한뒤 정보획득을 알아본다. 이렇게 순차적으로 계산한 뒤, 이번엔 다른 변수인 소득을 기준으로 정렬하고 다시 같은 작업을 반복한다. 모든 경우의 수 가운데 정보 획득이 가장 큰 변수와 그 지점을 택해 첫 번째 분기를 하게 된다. 이후 또 같은 작업을 반복해 두 번째, 세 번째... 이렇게 분기를 계속해 나가는 과정이 바로 의사결정 나무의 학습이다.
정리하자면 n개의 데이터 d개의 변수가 있다고 할때
- 첫 번째 변수에 대해 정렬한다.
- 분기 지점을 첫 번째부터 n - 1까지 변경하며 엔트로피와 정보 획득률을 전부 계산한다.
- 이 과정을 d개의 변수에 대해 수행하고 가장 큰 정보 획득률을 갖는 변수 di의 ni번째를 분기 지점으로 데이터를 분류한다.
- 이 과정을 분류 기준 변수가 없을 때까지 반복한다.
그렇다면 1회 분기를 위해 계산해야 하는 경우의 수는 총 몇 번일까? 개체가 n개, 변수가 d 개라고 할 때 경우의 수는 d(n - 1) 개가 된다. 분기를 하지 않는 경우를 제외하고 모든 개체와 변수를 고려해 보는 것이다.
3.2 가지 치기
의사결정 나무 모델 학습의 또 다른 축은 가지치기(Pruning)이다. 모든 terminal node의 순도가 100%인 상태를 Full tree라고 하는데, Full tree를 생성한 뒤 적절한 수준에서 terminal node를 결합하여 분기가 너무 많아 생기는 오버 피팅을 방지해 주어야 한다.
이러한 문제를 해결하기 위해서는 검증 데이터에 대한 오분류율이 증가하는 시점에서 적절히 가지치기를 수행해줘야 한다. 가지치기 개념도는 아래와 같다. 가지치기는 데이터를 버리는 개념이 아닌 분기를 합치는(merge) 개념이다.
아래 예시에서 왼쪽 그림은 모든 terminal node의 불순도는 0이다. 하지만 terminal node가 너무 많으면 새로운 데이터에 대한 예측 성능인 일반화(generalization) 능력이 떨어질 염려가 있다. terminal node를 적절하게 합쳐주면 오른쪽 그림과 같은 결과가 나오는 걸 확인할 수 있다.
가지치기의 비용 함수(Cost function) CC(T)는 다음과 같다. 의사결정 나무는 이 비용 함수를 최소로 하는 분기를 찾아내도록 학습된다.
.
- CC(T) = 의사결정 나무의 비용 복잡도(=오류가 적으면서 terminal node 수가 적은 단순한 모델일수록 작은 값)
- Err(T) = 검증 데이터에 대한 오분류율
- L(T) = terminal node의 수 (구조의 복잡도)
- Alpha = Err(T)와 L(T)를 결합하는 가중치(사용자에 의해 부여됨, 보통 0.01 ~ 0.1)
4. 장점과 단점
장점
- 데이터의 전처리 (정규화, 결측치, 이상치 등) 를 하지 않아도 된다.
- 수치형과 범주형 변수를 한꺼번에 다룰 수 있다.
단점
- 만약 샘플의 사이즈가 크면 효율성 및 가독성이 떨어진다.
- 과적합으로 알고리즘 성능이 떨어질 수 있다.
- 이를 극복하기 위해서 트리의 크기를 사전에 제한하는 튜닝이 필요하다.
- 한 번에 하나의 변수만을 고려하므로 변수간 상호작용을 파악하기가 어렵다.
- 결정트리는 Hill Climbing 방식 및 Greedy 방식을 사용하고 있다.
- 일반적인 Greedy 방식의 알고리즘이 그렇듯이 이 방식은 최적의 해를 보장하지는 못한다.
- 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다.
- 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.
- 이같은 문제를 극복하기 위해 등장한 모델이 바로 랜덤포레스트이다.
- 같은 데이터에 대해 의사결정나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법이다.
마치며
이 글에서는 의사결정 나무에 대해 정리해 보았다. 의사결정 나무는 계산 복잡성 대비 높은 예측 성능을 낸다.
다만 결정 경계(decision boundary)가 데이터 축에 수직이어서 특정 데이터에만 잘 작동할 가능성이 높다.
이 같은 문제를 극복하기 위해 등장한 모델인 랜덤 포레스트이다. 같은 데이터에 대해 의사결정 나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법이다.
랜덤 포레스트에 대해서도 공부하고 정리할 계획이다.
참고 문헌
https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
https://wooono.tistory.com/104
'머신러닝, 딥러닝 > Decision Tree' 카테고리의 다른 글
| [ML] 의사결정 나무(Decision Tree) CART 알고리즘 (0) | 2022.02.24 |
|---|---|
| [ML] 의사결정 나무(Decision Tree) C4.5 알고리즘 (0) | 2022.02.24 |
| [ML] ID3 알고리즘, 엔트로피(Entropy) (0) | 2022.02.24 |
댓글