(전공복습) 인공지능 5. 결정트리

차례

• 차례
• 들어가기 전에
• 결정트리(Decision Tree)
  • 결정트리와 오컴의 면도날(Ockham’s Razor)
  • 결정트리 만들기
  • 최적의 결정트리
• 엔트로피(Entropy)
  • 조건부 엔트로피(Conditional Entropy)
  • 정보이득(Information Gain)
    • 정보이득이 0인 경우
  • 수치형 피처의 분류
• 과적합(Overfitting)
  • 결정트리의 과적합
• 정리

들어가기 전에

이 글은 컴퓨터학과 이중전공생으로서 배운 것들을 다시 한번 정리하고자 남기는 글입니다. 불완전한 기억 등의 이유로 오류가 있을 수 있으며, 참조 내지 이정표로만 사용해주세요.
본 게시글은 고려대학교의 인공지능 강의를 기반으로 작성자의 추가적인 설명이 덧붙여진 글입니다. 또한 해당 강의는 UC 버클리 CS188을 기반으로 함을 밝힙니다.

결정트리(Decision Tree)

결정트리(Decision Tree)란, 말 그대로 의사결정을 하기 위한 트리를 의미한다. 주로 분류(Classification)에 쓰이며(회귀에도 사용은 가능하다), 지난 나이브 베이지언 분류기에서 언급했듯, 분류란 각 데이터를 몇 개의 클래스 중 하나로 할당하는 것을 의미한다.
결정트리는 인간이 해석할 수 있다는(Human Interpretable) 특징이 있는데, 일반적인 인공지능 모형은 내부 동작을 정확히 이해하기 힘든 상자(Black Box) 취급을 받는 반면, 결정트리의 선택은 왜 그런 선택을 하였는가가 상대적으로 명확하다는 장점을 지닌다.
(그래프 이론에서 트리는 무엇인지 알 것이라 가정한다. 혹여 트리에 대해 잘 모른다면 구글에 검색해보거나 추후 게시될 이산수학, 자료구조 게시글 등을 참고하라.)

트리의 중간 노드(Internal Node, 내부 노드)는 특정 피처에 대한 테스트의 형태로 존재한다. 이를테면 자동차의 연비가 좋은지 나쁜지 판단하는 결정트리를 만든다고 생각해보자. 중간 노드에는 이를테면 제조국이 어디인가, 또는 마력이 n 이상인가와 같은 질문들이 주어지는 것이다.
트리의 간선(Edge, 엣지)에는 중간 노드에 있는 테스트의 결과들이 위치한다. 예를 들어 제조국을 묻는 노드에 대해 미국, 한국, 또는 마력이 일정 이상인지 묻는 노드에 대해 예, 아니오 등이 엣지에 위치하게 되는 것이다.
이렇게 간선을 따라 내려가면, 리프 노드(Leaf Node, 말단 노드)에는 해당 노드에 대한 클래스가 위치하게 된다. 이러한 구조는 마치 어린 시절 많이 하던 화살표 심리 테스트와 유사하다.

결정트리와 오컴의 면도날(Ockham’s Razor)

결정트리는 데이터의 피처와 관련된 함수를 트리 형태로 나타낸 것이다. 그말인즉슨 결정트리 역시 얼마든지 복잡해질 수 있다는 것을 의미한다. 하지만 최고의 결정트리는 단순히 데이터를 100% 반영하는 복잡한 트리가 아니다. 동등한 결과를 가지는 결정트리 중에서도 단순한 것과 복잡한 것이 존재하고, 후술하겠지만 때로는 데이터를 완벽히 학습한 복잡한 결정트리보다 적당히 단순화된 결정트리가 좋을 수 있다.
오컴의 면도날이란 여러 가설에 대하여 간단한 것이 좋은 것이라고 여기는 원칙을 뜻한다. 물론 그렇다고 제일 간단한 게 좋다고 할 수는 없고, 정확히는 모델을 불필요하게 복잡하게 만들지 말라는 원칙을 의미한다고 할 수 있다.

결정트리 만들기

우선 우리는 가장 간단한 결정트리를 생각할 수 있다. 바로 루트 노드만 존재하는 트리이다. 상기한 자동차 연비 분류기를 생각해보자. 항상 연비를 나쁨이라고만 평가하는 분류기는 가장 간단한 분류기의 예시이다. 당연한 이야기지만, 이러한 분류기는 사실 별 쓸모가 없다.

이 결정트리를 점점 성장시켜 보도록 하자. 우선 하나의 피처(범주형 변수라고 가정하자)에 대해, 루트 노드의 데이터를 각 범주별로 나눈다. 예를 들어, 우리는 자동차 연비를 파악하기 위해 실린더(기통)의 개수를 셀 수 있다. 편의를 위해 4기통은 5대, 5기통과 6기통은 각각 2대라고 하자.

이제 각 범주별로 클래스의 분포를 확인한다. 우리 예제의 경우 연비가 좋은 차와 나쁜 차의 개수를 세어 주면 된다. 이를테면 4기통은 좋은 차가 3대, 나쁜 차가 2대, 5기통은 좋은 차가 1대, 나쁜 차가 1대, 6기통은 나쁜 차만 2대라고 하자. 이 경우, 4기통은 연비가 좋은 차가 더 많으므로 좋음 클래스를 가지게 된다. 5기통은 두 클래스의 개수가 동일하므로, 이 경우는 일단 나쁨을 취하는 것으로 하자. 6기통은 각각 연비가 나쁜 차가 더 많으므로 나쁨 클래스를 가지게 된다.

두 대의 차가 모두 나쁨인 6기통과 달리, 4기통과 5기통은 실제로 모든 차의 클래스가 같지 않으므로 더 분류가 가능하다. 예를 들어 제조국별로 4기통과 5기통 차를 더 분류할 수도 있다. 4기통 자동차 5대 중 연비가 좋은 차인 3대는 한국산, 연비가 나쁜 차인 2대는 중국산이라고 하자. 그렇다면 그 자동차들을 추가로 분류할 수 있게 된다. 그러면 4기통이면서 한국산인 차들은 모두 좋음, 4기통이면서 중국산인 차들은 모두 나쁨 클래스로 분류된다. 이처럼 해당 노드의 데이터를 완벽하게 분류해낸 경우, 당연히 다른 피처를 가지고 추가적으로 트리를 성장시킬 필요가 없다. 하지만, 완벽하게 분류가 되지 않는 경우도 있을 것이다. 이를테면 5기통 자동차는 연비가 좋은 차가 1대, 나쁜 차가 1대였는데, 제조국별로 분류해본 결과 두 차 모두 중국산일 수 있다. 이처럼 남은 데이터가 모두 같은 피처를 가진 경우 당연히 추가적인 분류가 아무런 의미를 갖지 못한다.
이처럼, 각 특성에 대해 재귀적으로 분류를 해나가면 최종적으로는 더이상 분류가 불가능한 노드를 제외한 모든 리프노드가 완벽히 분류된 트리가 만들어진다.

최적의 결정트리

위에서 말했듯이, 동일한 결과를 내는 결정트리 중 어떤 것은 단순하고, 다른 것은 그렇지 않다. 하지만, 동등한 결정트리 중 가장 간단한 결정트리를 만드는 문제는 NP-완전(NP-Complete) 문제에 속한다. 쉽게 말해서, 간단하면서도 강력한 결정트리를 만드는 것은 적어도 오늘날의 기술로는 매우 어렵다.
(P-NP 문제에 관해 더 알고 싶다면 검색해보거나 추후 올라올 알고리즘에 관한 게시글을 참조하라.)
따라서 우리는 휴리스틱(Heuristic, 어림법)을 통해 최적에 근사하는 적당히 좋은 결정트리를 만들도록 할 것이다. 그렇게 하기 위한 방법은 아래와 같다.

1. 위와 마찬가지로 가장 간단한(단일 노드) 트리에서 시작한다.
2. 가장 나은 피처를 기준으로 노드를 분할한다.
3. 모든 리프노드가 완벽하게 분류되거나 더이상 분류가 불가능해질 때까지 반복한다.

엔트로피(Entropy)

문제는, 가장 나은 피처를 어떻게 선별하냐는 점이다. 노드를 분리할 때 가장 좋은 피처가 무엇일지에 대한 평가수단이 필요한데, 이때 활용되는 개념이 바로 엔트로피이다.
연비가 좋음과 나쁨으로 분류되는 8대의 자동차가 있다고 하자. 기통별로 분류했더니 4기통은 좋음만 4개고, 5기통은 나쁨만 4개인 반면, 제조국별로 분류했더니 한국산은 좋음이 2개, 나쁨이 2개고, 중국산도 좋음이 2개, 나쁨이 2개일 수 있다. 이 경우 어느 쪽이 더 나은 피처가 되겠는가?
아마, 많은 이들은 제조국보다는 기통이 더 분류를 위해 적합하다고 할 것이다. 기통을 기준으로 분류하면 클래스의 분포가 좋음과 나쁨 중 한쪽으로 치우치는데 반해, 제조국을 기준으로 분류하면 균일분포(Uniform Distribution)를 가지기 때문이다. 가장 좋은 경우는 기통의 경우처럼 하나의 클래스만 남는 경우다. 반면, 가장 나쁜 경우는 제조국의 경우처럼 균일분포가 등장하는 경우다.

많은 경우 분포는 그 중간에 위치할텐데, 이때 그 분포가 위 두 가지 경우 중 어디에 가까운지를 측정하는 방법이 바로 엔트로피이다. 확률변수 \(Y\)에 대한 엔트로피는 아래와 같이 계산한다.

• \[H(Y) = -\sum\limits_{i=1}^k P(Y = y_i) \log_2 P(Y = y_i)\]

즉, 엔트로피 \(H(Y)\)는 확률변수가 가질 수 있는 모든 값에 대해 \(p\log_2p\)를 더해주고 양수로 만든 것이다(여기서 \(p\)는 각 경우의 확률). 확률 \(p \le 1\)이므로 \(p\log_2p\)는 항상 음수이기 때문에 \(-1\)을 곱해야 양수가 된다. 또한, 예외처리를 위해 \(0\log_2 0 = 0\)으로 정의하자.
이 값 \(H(X) = 1\)이라면 균일분포이고, \(H(X) = 0\)이라면 완벽히 결정적인(Deterministic) 분포를 의미한다. 즉, 엔트로피는 불확실성(무질서)의 정도라고 할 수 있다. 엔트로피가 높아질수록 \(X\)가 실제로 갖는 값을 추측하기 어려워지고, 반대로 낮아질수록 \(X\)가 가질 확률이 높은 값을 특정하기 쉬워진다.

조건부 엔트로피(Conditional Entropy)

조건부 엔트로피는 조건부 확률의 엔트로피를 계산하기 위한 방법이다. 정확히는 확률변수 \(X\)가 정해졌을 때, 확률변수 \(Y\)가 가지는 엔트로피의 기댓값이다(단순히 엔트로피가 아니라 기댓값인 이유는 \(X\)가 가질 수 있는 값이 여러가지이고, 이를 가중평균내기 때문이다). \(X\)의 값이 결정되었을 때 \(Y\)의 엔트로피 기댓값은 아래와 같이 나타낼 수 있다.

• \[H(Y\vert X) = -\sum\limits_{j=1}^v P(X = x_j) \sum\limits_{i=1}^k P(Y=y_i\vert X = x_j) \log_2 P(Y=y_i \vert X= x_j)\]

식이 더 길어졌지만, 본질적으로는 기존 엔트로피와 거의 동일하다. 가능한 모든 \(X\)의 값에 대해, \(P(Y \vert X)\)의 엔트로피를 구하고 이를 \(X\)의 확률에 따라 가중평균 낸 값이다. 조건부 엔트로피는 하나의 피처를 기준으로 데이터를 분리했을 때 클래스의 분포가 어떻게 바뀌는지 알 수 있으므로 결정트리를 만드는 데에 매우 중요하다.

정보이득(Information Gain)

정보이득이란, 원래 엔트로피에서 조건부 엔트로피를 뺀 값이다. 다시 말해 원래 상황 대비 분류 이후에 엔트로피가 얼마나 줄었는지를 의미한다. 확률변수 \(X\)가 정해졌을 때 얻는 정보이득에 대한 수식은 당연히 아래와 같다.

• \[IG(X) = H(Y) - H(Y \vert X)\]

따라서, 결정트리를 만들기 위해 가장 먼저 취할 피처는 \(\arg \max _i IG(x_i)\)로, 즉 정보이득을 최대로 만드는 피처이다.

정보이득이 0인 경우

정보이득이 \(0\)인 경우, 해당 피처로 노드를 나누는 것이 의미를 가질까? 얼핏 생각하면 \(IG(X) = 0\)이라면 이는 해당 피처를 이용해도 그대로 불확실한 분류를 하게 되므로 무의미할 것 같다. 그러나 실제로 이런 분류는 의미를 가진다.
두 개의 피처 \(a \in \{0, 1\}\)와 \(b$ \in \{0, 1\}$에 대해\)a \oplus b\(를 클래스로 갖는 데이터를 생각해보자(\)\oplus$$는 XOR을 의미한다). 이 경우 각 데이터는 아래와 같을 것이다.

이 데이터는 처음에 \(IG(a) = IG(b) = 0\)이다. 처음 클래스의 분포는 균일분포이고, 어떤 피처로 나누든 \(1\)과 \(0\)의 개수가 같으므로 계속 균일분포이기 때문이다. 그러나 분류를 한번 더 진행하면 아래와 같은 트리를 만들 수 있다.

따라서, 정보이득이 0이라도 종료조건(노드의 모든 데이터가 같은 클래스거나 같은 피처를 가짐)에 해당하지 않으면 계속 분류를 이어나가는 것이 좋다.

수치형 피처의 분류

예시와 같은 범주형(Categorical) 피처에 대해서는 위 방법이 매우 간단하다. 여기서 범주형 피처란 성별이나 제조국처럼 몇 개의 범주가 있고, 데이터는 상호배타적(Mutually Exclusive)으로 범주 중 하나에 소속되는 경우를 의미한다. 이 경우 결정트리에서 노드의 자식노드는 범주의 개수만큼 나올 것이다.
하지만, 수치형 피처는 가능한 값이 매우 많거나, 경우에 따라서는 무한하다. 이를테면 나이나 소득 등은 이론적으로 가능한 값이 무한하므로 범주형 피처처럼 취급하기에는 어려움이 많다. 이런 경우에는 문턱값(Threshold, 쓰레숄드)을 정해서 문턱값을 기준으로 수치의 크기를 비교할 수 있다. 이를테면 나이를 10세 미만, 10세 이상 20세 미만, 20세 이상 30세 미만, …하는 식으로 쪼개는 것이다.

하지만 이 경우, 문턱값을 어떻게 정하는 것이 좋을지에 대해 고민할 필요가 있다. 나이를 쪼개는 기준을 어떻게 정할 것인가? 단순히 10세 단위로 자르는 것은 사람이 보기엔 편할 수 있어도 좋은 예측을 하는 데에는 도움이 안 될 수도 있다. 따라서 우리는 어떻게 수치형 피처의 문턱값을 정할지 고민해볼 것이다.

우선, 문턱값의 가능한 경우는 무한하다. 나이를 두 구간으로 분리한다고 했을 때, 문턱값의 기준으로 모든 나이가 가능하기 때문이다. 하지만, 실제로는 유한한 개수의 문턱값만이 의미가 있다. 데이터가 오직 2개고, 각각의 나이가 10세와 20세라고 하자. 그러면 의미가 있는 문턱값은 10과 20 사이의 숫자뿐일 것이다. 그리고 우리가 가진 데이터의 관점에서는 이 문턱값이 11세든 19세든 동등하다. 10과 20 사이에만 있다면 어떤 숫자든 데이터를 똑같이 나누기 때문이다.
이러한 관점에서, 문턱값을 두 데이터 사이의 중간값(이 경우 15)으로 정하는 것은 퍽 합리적이다. 즉, \(N\)개의 데이터에서 실제로 유의미한 문턱값의 개수는 \(N-1\)개이다(피처의 값이 모두 다르다고 가정했을 때).

가능한 문턱값의 개수를 더 줄일 순 없을까? 우리가 하고 싶은 일은 분류이고, 따라서 서로 같은 클래스의 데이터 사이에 문턱값을 두는 것은 무의미하다. 예를 들어, 이번엔 3개의 데이터가 있다고 하자. 그들의 나이는 각각 10, 20, 30세이며, 10세와 20세는 클래스 1에, 30세는 클래스 2에 속한다고 하자. 가능한 문턱값으로는 15(10과 20 사이)와 25(20과 30 사이)를 생각할 수 있다. 하지만 15는 의미가 없는 문턱값인데, 10과 20이 같은 클래스이기 때문에 그러한 분할이 의미를 갖지 않기 때문이다.

그렇다면 이러한 사항들을 모두 고려했을 때, 문턱값을 정하기 위한 공식은 없을까? \(H(Y \vert X:t)\)를 \(X\)의 문턱값이 \(t\)일 때, \(Y\)의 엔트로피라 하면 아래와 같이 나타낼 수 있다.

• \[H(Y \vert X:t) = P(X < t) H(Y \vert X < t) + P(X \ge t) H(Y \vert X \ge t)\]

이는 원래 수치형인 피처 \(X\)를 문턱값 \(t\)를 기준으로 나누어 새로운 범주형 피처를 만들어서 그 조건부 엔트로피를 구한 것과 동일하다. 따라서 여러 개의 문턱값을 기준으로 삼는 경우에도 같다. \(H(Y \vert X: \{t_0, t_1, ..., t_i\})\)에 대해 아래와 같이 나타낼 수 있다.

• \[H(Y \vert X: \{t_0, t_1, ..., t_k\}) = \sum\limits_{i=0}^{k-1} P(t_i \le X < t_{i+1})H(Y \vert t_i \le X < t_{i+1})\]

이제, 엔트로피를 계산할 수 있으므로 정보이득 역시 계산이 가능해진다. 수치형 피처에서 문턱값이 \(t\)일 때의 정보이득은 \(IG(Y \vert X: t) = H(Y) - H(Y \vert X:t)\)이고, 우리는 정보이득을 최대화하는 문턱값을 찾아야 하므로 \(IG^* = \max_t IG(Y \vert X:t)\)를 수치형 피처의 정보이득으로 삼을 수 있다.

과적합(Overfitting)

사실, 위의 방식으로 만든 결정트리는 실제 데이터에 대해 낮은 정확도를 보여준다. 그 이유는 결정트리가 너무 복잡하기 때문이다. 모델은 큰 경향성만 학습해야 한다. 예를 들어 우리가 연비를 좋음과 나쁨으로 예측하기 위해 아래와 같은 피처를 수집했다고 해보자.

• 기통
• 제조국
• 출시년도
• 차 색깔
• 차 이름의 길이

기통이나 제조국, 출시년도 등은 아마도 연비에 영향을 끼칠 것이다. 그런데 차 색깔이나 이름의 길이는 연비와 관련이 없다. 하지만 수집한 데이터는 차 색깔이나 이름의 길이에 따라 연비가 좋은 차와 나쁜 차의 개수가 다를 수 있다(확률적으로 상식적인 일이다). 즉, 우리 결정트리는 차 색깔과 이름의 길이처럼 무의미한 피처를 가지고도 분류를 이어나갈 것이다. 당연히 정확도는 떨어질 수밖에 없다.

이처럼 학습 대상 데이터(표본)의 모든 측면을 학습해서, 실제 모집단의 경향성과는 무관한 것들까지 판단의 기준으로 삼는 것을 과적합(Overfitting)이라 한다. 과적합이 일어나면 학습 데이터에 대한 정확도는 매우 높지만, 테스트 데이터 내지는 실제 데이터에 대한 정확도는 오히려 떨어지게 된다.
반대로, 지나치게 데이터를 덜 학습해서 모델이 너무 단순한 경우 이를 과소적합(Underfitting)이라 한다. 이 경우 학습이 너무 덜 이루어졌으므로 학습 데이터에 대한 정확도부터 떨어지게 된다.
아래는 흔히 볼 수 있는 과적합과 과소적합을 설명하는 이미지이다(출처).

결정트리의 과적합

아무튼, 위에서 우리가 본 결정트리는 가능한 모든 수단(피처)을 동원해서 데이터를 분류하려고 하기 때문에 과적합 문제에 맞닥뜨리게 된다. 즉, 모든 가능한 경우에 대해 미주알고주알 분류를 하기 때문에 정확도가 떨어지게 되는 것이다. 이런 문제를 해결하기 위해 우리는 결정트리의 생성을 조기에 멈추거나(Early Stopping), 완성된 트리를 프루닝(Pruning, 가지치기)하여 더 단순한 트리를 만들도록 할 수 있다.
(결정트리의 과적합을 방지하기 위한 구체적인 내용은 추후 기계학습 강의 등 다른 게시글에서 다루도록 한다.)

정리

오늘은 결정트리에 대해 알아보았다. 그 과정에서 엔트로피와 과적합 역시 짧게 다루고 넘어갔다. 둘다 중요한 개념으로 다뤄지므로 잘 알고 있는 편이 좋을 듯하다.

다음 시간에는 군집화(Clustering)에 대해 알아보고, 이어서 신경망과 역전파를 알아보면 인공지능 복습은 끝나게 된다.

• 2024 18
• 2023 143