결정 트리

결정 트리는 예 아니오로 답하는 질문을 차례로 던져 답을 가려냅니다. 머신러닝에서는 데이터를 보고 어떤 질문을 어떤 순서로 던질지 스스로 배우는 모델을 가리킵니다. 알고리즘 분석에서는 비교 한 번마다 길이 둘로 갈리는 그림을 가리킵니다. 이 그림으로 정렬이 얼마나 빨라질 수 있는지를 따집니다.

상세

스무고개를 떠올려 봅시다. 잘하는 사람은 「살아 있는 것인가」처럼 후보를 크게 가르는 질문부터 던집니다. 답을 들을 때마다 후보가 줄어듭니다. 스무 번 안에 하나로 좁히면 이깁니다.

결정 트리는 이런 질문들을 갈림길 모양으로 펼쳐 둡니다. 답을 구할 때는 맨 위 질문부터 따라 내려갑니다. 질문 하나가 갈림길 하나입니다. 맨 끝에 닿으면 거기 적힌 답을 냅니다.

머신러닝에서 결정 트리는 이 질문들을 데이터에서 배웁니다. 넣는 것은 과거 기록을 모은 표입니다. 이 표를 훈련 데이터라고 부릅니다. 표의 한 줄은 예를 들어 회원 한 명입니다.

표의 칸은 두 종류입니다. 회원을 묘사하는 값을 특성이라고 부릅니다. 마지막 접속 뒤 지난 날수나 문의 건수가 특성입니다.

맞혀야 할 답은 레이블이라고 부릅니다. 이 회원이 떠났는지 남았는지가 레이블입니다. 훈련 데이터에는 줄마다 레이블이 붙어 있습니다.

결정 트리는 두 단계로 씁니다. 먼저 훈련 데이터를 받아 트리를 만듭니다. 이 단계를 훈련이라고 합니다.

그다음 레이블이 없는 새 줄 하나를 받아 트리를 따라 내려가 답을 냅니다. 이 단계가 예측입니다.

답이 「떠남」·「남음」처럼 정해진 무리 가운데 하나면 분류입니다. 답이 집값처럼 숫자면 회귀입니다. 결정 트리는 둘 다 풉니다.

이 절은 회원 열 명의 훈련 데이터 하나를 끝까지 들고 갑니다. 이 표로 트리의 생김새, 질문을 고르는 방법, 멈추는 때, 끝까지 키우면 생기는 일을 차례로 봅니다. 회귀는 뒤의 소절에서 따로 봅니다.

회원 열 명의 훈련 데이터

어떤 서비스가 지난달 회원 열 명의 기록을 모았습니다. 특성은 둘입니다. 레이블은 이번 달에 떠났는지입니다.

떠난 회원은 넷입니다. 남은 회원은 여섯입니다. 목표는 두 특성만 보고 떠날 회원을 골라내는 질문을 찾는 것입니다.

트리를 이루는 노드

완성된 트리부터 봅니다. 이 트리를 어떻게 만들었는지는 다음 소절들이 풉니다.

flowchart TD
    Q1{"마지막 접속 뒤 30일 넘었나"}
    Q1 -->|예| Q2{"문의가 1건 이상인가"}
    Q1 -->|아니오| L3["남음 · 6명 중 5명이 남음"]
    Q2 -->|예| L1["떠남 · 3명 중 3명이 떠남"]
    Q2 -->|아니오| L2["남음 · 1명 중 1명이 남음"]

마름모 하나가 질문 하나입니다. 네모는 답입니다. 답은 훈련 때 그 네모까지 내려온 회원들의 다수 레이블입니다. 네모 안의 「6명 중 5명」은 거기까지 내려온 회원 수와 그중 답과 같은 레이블을 가진 수입니다.

이렇게 위에서 아래로만 갈라지고 되돌아오는 길이 없는 구조를 트리라고 부릅니다. 갈림길과 끝 하나하나를 노드라고 합니다.

맨 위 노드를 루트 노드라고 합니다. 더 갈라지지 않는 맨 끝 노드는 리프 노드입니다. 줄여서 루트와 리프라고도 부릅니다.

루트에서 리프까지 거치는 질문 수를 그 리프의 깊이라고 합니다. 트리의 깊이는 가장 깊은 리프의 깊이입니다. 위 트리의 깊이는 2 입니다.

새 회원 한 명을 넣어 봅시다. 마지막 접속 뒤 40일이 지났고 문의가 세 건입니다. 루트의 「30일 넘었나」에서 예로 내려갑니다. 「문의가 1건 이상인가」에서도 예로 내려가 「떠남」에 닿습니다.

이 트리는 중첩된 if 문과 같습니다. 파이썬으로 옮기면 아래와 같습니다. days 는 마지막 접속 뒤 지난 날수입니다. tickets 는 문의 건수입니다.

def predict(days, tickets):
    if days > 30:
        if tickets >= 1:
            return "떠남"
        return "남음"
    return "남음"

predict(40, 3)  # "떠남"
predict(40, 0)  # "남음"
predict(5, 3)   # "남음"

손으로 짠 if 문과 다른 점은 누가 짰느냐뿐입니다. 30이라는 기준값과 질문의 순서를 사람이 아니라 훈련이 정했습니다.

섞인 정도를 재는 불순도

훈련에서 하는 일은 대부분 질문 고르기입니다. 쓸모 있는 질문은 떠난 회원과 남은 회원을 서로 다른 쪽으로 보냅니다. 그러려면 한 무리가 얼마나 섞였는지를 숫자로 재야 합니다.

이 섞인 정도를 불순도라고 부릅니다. 한 레이블만 모인 무리는 불순도가 0 입니다. 두 레이블이 반반 섞이면 불순도가 가장 높습니다.

불순도를 재는 가장 흔한 잣대는 지니 불순도입니다. 레이블마다 무리 안의 비율을 구해 제곱합니다. 그 제곱들을 더한 값을 1 에서 뺍니다.

지니 불순도 = 1 − (레이블마다 비율을 제곱해 더한 값)

아래 표는 이 식을 무리 셋에 적용한 결과입니다. 첫 줄이 회원 열 명 전체입니다.

레이블이 둘이면 0.5 가 가장 높은 값입니다. 트리를 키우는 목표는 아래로 내려갈수록 이 값을 0 에 가깝게 만드는 것입니다.

지니 불순도 대신 엔트로피를 잣대로 쓰기도 합니다. 엔트로피는 무리의 레이블을 알아맞히는 데 평균 몇 번의 예 아니오 질문이 드는지를 잽니다. 이 값도 한 레이블만 모이면 0 입니다. 반반이면 가장 높습니다.

엔트로피를 잣대로 쓰면 질문 하나가 줄인 엔트로피를 정보 이득이라고 부릅니다. 어느 잣대를 쓰든 고르는 질문은 대개 같습니다.

가장 많이 줄이는 질문 고르기

루트에서 던질 질문 후보 둘을 견줘 봅니다. 질문마다 열 명을 두 무리로 나누고 무리마다 지니 불순도를 잽니다. 예 쪽과 아니오 쪽 칸에는 사람 수, 그중 떠난 수, 지니 불순도를 차례로 적었습니다.

오른쪽 끝 칸은 두 무리의 불순도를 사람 수로 가중 평균한 값입니다. 여섯 명짜리 무리가 네 명짜리 무리보다 결과에 더 크게 들어가야 공평하기 때문입니다. 「30일 넘었나」는 0.4 × 0.375 + 0.6 × 0.278 로 약 0.32 입니다.

나누기 전 불순도는 0.48 이었습니다. 「30일 넘었나」는 약 0.16 을 줄입니다. 「문의가 1건 이상인가」는 약 0.14 를 줄입니다. 더 많이 줄이는 「30일 넘었나」가 루트 질문이 됩니다.

기준값 30 도 같은 방식으로 고릅니다. 숫자 특성은 값을 정렬한 뒤 이웃한 두 값 사이마다 기준값 후보를 하나씩 둡니다. 후보마다 나눠 보고 불순도를 가장 많이 줄이는 후보를 씁니다.

이 표에서 지난 날수를 정렬하면 15 다음이 38 입니다. 15 와 38 사이 어디에 선을 그어도 나뉘는 결과가 같습니다. 이 글은 읽기 쉽게 30 을 썼습니다.

두 질문의 차이는 0.02 쯤입니다. 기록 한두 줄만 달라져도 루트 질문이 뒤바뀔 수 있는 차이입니다. 이 성질은 뒤의 「결정 트리가 잘 맞는 데이터와 약한 데이터」 소절에서 다시 나옵니다.

노드마다 되풀이하는 탐욕적 방식

루트 질문이 정해지면 열 명이 두 무리로 갈립니다. 각 무리 안에서 같은 일을 되풀이합니다. 그 무리의 불순도를 가장 많이 줄이는 질문을 다시 찾습니다.

예 쪽 네 명, 곧 30일 넘은 회원은 「문의가 1건 이상인가」로 나누면 두 쪽 모두 불순도가 0 이 됩니다. 떠난 셋은 모두 문의를 한 적이 있습니다. 남은 한 명은 문의가 없었습니다.

이렇게 매번 눈앞의 불순도만 가장 많이 줄이는 방식을 탐욕 알고리즘이라고 부릅니다. 결정 트리는 노드 하나를 정할 때 그 아래에서 무슨 일이 생길지는 따지지 않습니다.

가능한 트리를 모두 만들어 견주는 방법도 생각할 수 있습니다. 그러나 특성과 줄이 조금만 늘어도 트리 가짓수가 걷잡을 수 없이 늘어납니다. 현실적인 시간 안에 끝나지 않으므로 결정 트리는 탐욕 방식으로 키웁니다. 대가는 전체로 보면 더 작고 더 잘 맞히는 트리를 놓칠 수 있다는 것입니다.

멈추는 조건

되풀이를 그냥 두면 모든 리프에 한 레이블만 남을 때까지 갈라집니다. 그래서 훈련 전에 멈출 조건을 정해 둡니다. 흔히 쓰는 조건은 넷입니다.

이 값들은 데이터가 아니라 사람이 훈련 전에 정합니다. 이런 설정값을 하이퍼파라미터라고 부릅니다.

지금까지 본 키우기를 한 그림으로 모으면 아래와 같습니다. 무리 하나를 받을 때마다 이 흐름을 처음부터 탑니다.

flowchart TD
    A["무리 하나를 받는다"] --> B{"멈춤 조건에 닿았나"}
    B -->|예| C["리프가 된다 · 다수 레이블이 답"]
    B -->|아니오| D["불순도를 가장 많이 줄이는 질문을 고른다"]
    D --> E["두 무리로 나눈다"]
    E -->|무리마다 처음부터| A

갈라진 두 무리는 각각 맨 위로 돌아갑니다. 모든 무리가 리프가 되면 트리가 완성됩니다.

앞의 트리는 아니오 쪽 여섯 명, 곧 30일 안 넘은 회원을 더 가르지 않았습니다. 최소 감소량을 0.1 로 정해 두었다고 해 봅시다. 여섯 명을 가르는 질문 가운데 불순도를 가장 많이 줄이는 것도 약 0.06 밖에 못 줄입니다. 그래서 아니오 쪽은 리프로 남습니다.

그 질문으로 갈라도 예측은 안 바뀝니다. 나뉜 두 무리 모두 남은 회원이 더 많아서 답이 둘 다 「남음」이기 때문입니다.

끝까지 키우면 생기는 과적합

멈춤 조건 없이 끝까지 가르면 아니오 쪽의 7번 회원도 따로 떼어 낼 수 있습니다. 7번은 접속한 지 5일밖에 안 됐습니다. 그런데도 떠났습니다.

아니오 쪽 여섯 명의 지난 날수는 1 · 3 · 5 · 7 · 12 · 15 입니다. 7번 한 명만 떼려면 「4일 넘었나」와 「6일 이하인가」 두 질문이 더 필요합니다. 그러면 트리는 「접속한 지 4일 넘고 6일 이하면 떠난다」는 규칙을 갖게 됩니다.

그렇게 키운 트리의 아니오 쪽은 아래와 같습니다. 예 쪽은 앞 그림과 같아서 한 칸으로 접었습니다.

flowchart TD
    Q1{"마지막 접속 뒤 30일 넘었나"}
    Q1 -->|예| Y["앞 그림과 같음"]
    Q1 -->|아니오| Q2{"4일 넘었나"}
    Q2 -->|아니오| L1["남음 · 1일 · 3일 두 명"]
    Q2 -->|예| Q3{"6일 이하인가"}
    Q3 -->|예| L2["떠남 · 5일 7번 한 명"]
    Q3 -->|아니오| L3["남음 · 7일 · 12일 · 15일 세 명"]

「떠남」 리프에는 7번 한 명만 남습니다. 리프 하나가 회원 한 명을 외운 셈입니다.

이 규칙은 회원 한 명에게서 나왔습니다. 7번이 떠난 까닭은 기록에 없는 우연일 가능성이 큽니다. 새 회원이 접속한 지 5일째라고 해서 떠날 까닭은 없습니다.

이처럼 훈련 데이터에 지나치게 맞춰져 새 데이터 앞에서 틀리는 현상을 과적합이라고 부릅니다. 끝까지 키운 결정 트리는 훈련 데이터를 거의 언제나 다 맞힙니다. 리프마다 한 줄만 남을 때까지 가를 수 있기 때문입니다.

기록에 끼어든 우연한 흔들림을 잡음이라고 합니다. 끝까지 키운 트리는 잡음까지 규칙으로 삼습니다.

과적합을 막는 방법은 둘입니다. 하나는 앞 소절의 멈춤 조건으로 미리 멈추는 것입니다. 다른 하나는 끝까지 키운 뒤 도움이 안 되는 가지를 잘라 내는 가지치기입니다.

가지를 자를지는 훈련에 쓰지 않고 따로 떼어 둔 데이터로 판단합니다. 가지를 잘라도 그 데이터에서 맞히는 비율이 떨어지지 않으면 자릅니다. 이렇게 떼어 둔 데이터를 검증 세트라고 합니다.

숫자를 맞히는 회귀 트리

답이 숫자일 때도 같은 틀을 씁니다. 리프는 레이블 대신 거기 모인 줄들의 평균값을 답으로 냅니다. 이런 결정 트리를 회귀 트리라고 부릅니다.

질문을 고르는 잣대만 바뀝니다. 레이블이 섞인 정도 대신 값이 평균에서 얼마나 흩어졌는지를 잽니다. 흩어진 정도는 분산으로 재는 것이 흔합니다. 질문은 이 흩어짐을 가장 많이 줄이는 것을 고릅니다.

회귀 트리의 예측은 계단 모양입니다. 같은 리프에 떨어진 입력은 모두 같은 값을 받습니다. 방 크기로 집값을 맞히는 트리의 리프가 넷이면 내놓는 집값도 네 가지뿐입니다.

예측과 훈련에 드는 시간

예측은 루트에서 리프까지 질문에 한 번씩 답하면 끝납니다. 그래서 예측 시간은 트리의 깊이에 비례합니다. 빅오 표기법으로 O(깊이)라고 적습니다. 빅오 표기법은 입력이 늘 때 비용이 어떤 모양으로 따라 느는지를 적는 약속입니다.

질문마다 양쪽이 고르게 갈리면 줄 n 개로 끝까지 키운 트리의 깊이는 log n 쯤입니다. log n 은 n 을 1 이 될 때까지 반으로 나눈 횟수입니다. 한쪽으로만 치우쳐 갈리면 깊이가 n 가까이 길어집니다.

줄 여덟 개로 두 경우를 그리면 아래와 같습니다. 칸 안의 숫자는 그 노드가 받은 줄 수입니다.

flowchart TD
    subgraph G1["고르게 갈릴 때"]
        A0["8"] --> A1["4"] & A2["4"]
        A1 --> A3["2"] & A4["2"]
        A2 --> A5["2"] & A6["2"]
        A3 & A4 & A5 & A6 --> A7["한 줄씩 리프 여덟 · 깊이 3"]
    end
    subgraph G2["치우쳐 갈릴 때"]
        B0["8"] --> B1["1"] & B2["7"]
        B2 --> B3["1"] & B4["6"]
        B4 --> B5["1"] & B6["5"]
        B6 --> B7["… 깊이 7까지"]
    end
    G1 ~~~ G2

고르게 갈리면 세 번 만에 한 줄씩 남습니다. 8 을 반으로 세 번 나누면 1 이 되기 때문입니다. 치우치면 한 번에 한 줄씩만 떨어져 나가 일곱 번이 걸립니다.

훈련은 예측보다 무겁습니다. 노드마다 모든 특성에 대해 기준값 후보를 전부 시험하기 때문입니다. 숫자 특성은 값을 정렬해 두면 후보를 앞에서부터 한 번 훑으며 불순도를 셀 수 있습니다.

같은 깊이에 있는 노드들은 훈련 데이터를 나눠 가집니다. 그 노드들이 받은 줄을 모두 더하면 n 개입니다. 줄 n 개를 정렬하는 데는 n log n 쯤이 듭니다.

그래서 같은 깊이의 노드를 모두 만드는 데 특성 수 × n log n 쯤이 듭니다. 트리 전체로는 여기에 깊이를 곱합니다.

결정 트리가 잘 맞는 데이터와 약한 데이터

먼저 경계라는 말부터 풉니다. 특성이 둘이면 줄 하나를 평면 위의 점 하나로 찍을 수 있습니다. 가로축에 지난 날수, 세로축에 문의 건수를 두는 식입니다. 평면에서 답이 바뀌는 선을 결정 경계라고 부릅니다.

결정 트리의 질문은 특성 하나만 기준값과 견줍니다. 그래서 경계가 가로선과 세로선으로만 그어집니다. 경계가 비스듬하면 계단을 여러 개 쌓아 흉내 냅니다.

위 세 줄이 결정 트리를 고르는 까닭입니다. 왜 그렇게 예측했는지를 사람에게 설명해야 하는 일에 맞습니다. 대출 심사나 이탈 예측의 근거를 보여 줘야 할 때가 그렇습니다.

아래 세 줄은 트리 하나만 쓸 때의 약점입니다. 정확도가 더 중요하면 다음 소절의 앙상블을 쓰거나 다른 모델을 씁니다.

여러 트리를 묶는 앙상블

트리 하나가 데이터에 흔들리는 약점을 거꾸로 이용하는 방법이 있습니다. 조금씩 다른 트리를 여럿 만들어 답을 모읍니다. 트리마다 흔들린 방향이 달라서 모으면 흔들림이 서로 상쇄됩니다.

이렇게 모델 여럿을 묶어 하나처럼 쓰는 방법을 앙상블이라고 부릅니다. 결정 트리는 앙상블의 재료로 가장 흔히 쓰입니다.

랜덤 포레스트는 트리마다 훈련 데이터에서 무작위로 뽑은 줄을 줍니다. 답은 트리들의 다수결로 냅니다.

flowchart TD
    D["훈련 데이터"] --> T1["트리 1 · 무작위로 뽑은 줄"]
    D --> T2["트리 2 · 무작위로 뽑은 줄"]
    D --> T3["트리 3 · 무작위로 뽑은 줄"]
    T1 & T2 & T3 --> V["다수결"]

그레이디언트 부스팅은 트리를 하나씩 차례로 더합니다. 새 트리는 앞 트리들이 틀린 만큼을 메우도록 훈련됩니다. 답은 모든 트리의 답을 더해서 냅니다.

flowchart TD
    T1["트리 1"] -->|틀린 만큼| T2["트리 2"]
    T2 -->|틀린 만큼| T3["트리 3"]
    T1 & T2 & T3 --> S["세 트리의 답을 더한다"]

랜덤 포레스트의 트리들은 서로를 모른 채 따로 자랍니다. 부스팅의 트리는 앞 트리가 틀린 것을 보고 자랍니다.

알고리즘 분석에서 쓰는 결정 트리

같은 이름이 알고리즘 분석에도 나옵니다. 이쪽은 데이터로 배우는 모델이 아닙니다. 알고리즘 하나가 입력에 따라 할 수 있는 모든 행동을 트리로 펼친 그림입니다.

값끼리 크기를 견주기만 해서 정렬하는 방법을 비교 정렬이라고 합니다. 비교 정렬을 트리로 펼치면 노드 하나가 「a 가 b 보다 작은가」 같은 비교 한 번입니다. 리프 하나는 가능한 정렬 결과 하나입니다.

값이 n 개면 가능한 순서는 n! 가지입니다. n! 은 1 부터 n 까지 모두 곱한 수입니다. 트리는 이 결과를 빠짐없이 리프로 가져야 합니다.

값 셋 a · b · c 로 좁혀 봅니다. 가능한 순서는 3! = 6 가지입니다. 이 값 셋을 정렬하는 트리는 아래와 같습니다.

flowchart TD
    R{"a 가 b 보다 작은가"}
    R -->|예| X{"b 가 c 보다 작은가"}
    R -->|아니오| Y{"a 가 c 보다 작은가"}
    X -->|예| L1["작은 순 · a b c"]
    X -->|아니오| X2{"a 가 c 보다 작은가"}
    X2 -->|예| L2["작은 순 · a c b"]
    X2 -->|아니오| L3["작은 순 · c a b"]
    Y -->|예| L4["작은 순 · b a c"]
    Y -->|아니오| Y2{"b 가 c 보다 작은가"}
    Y2 -->|예| L5["작은 순 · b c a"]
    Y2 -->|아니오| L6["작은 순 · c b a"]

리프는 여섯 개입니다. 가능한 순서마다 하나씩입니다. 리프에는 값을 작은 순으로 적었습니다. 가장 긴 길은 비교를 세 번 합니다.

비교 한 번은 길을 둘로만 가릅니다. 그래서 깊이가 d 인 트리의 리프는 많아야 2 를 d 번 곱한 수입니다. 값 셋이면 깊이 2 로는 리프가 넷뿐이라 여섯을 못 담습니다.

리프가 n! 개가 되려면 깊이가 적어도 log₂(n!) 이어야 합니다. 이 값은 n log n 과 같은 속도로 자랍니다.

깊이는 가장 긴 길의 비교 횟수입니다. 그러므로 어떤 비교 정렬이든 n log n 에 비례하는 횟수만큼 비교해야 하는 입력이 반드시 있습니다. 이 결론을 비교 정렬 하한이라고 부릅니다.

두 뜻은 모양이 같습니다. 노드는 질문입니다. 리프는 답입니다. 깊이는 곧 질문 횟수입니다.

머신러닝은 이 트리를 데이터에서 만듭니다. 알고리즘 분석은 알고리즘에서 읽어 냅니다.

관련 항목

결정 트리가 속하는 상위 분류

머신러닝 · 지도학습 · 분류 · 회귀 · 모델 · 알고리즘

결정 트리를 이루는 구성 요소

트리 · 이진 트리 · 노드 · 루트 노드 · 리프 노드 · 특성 · 레이블 · 임계값

결정 트리를 키우는 알고리즘

CART · ID3 · C4.5 · 탐욕 알고리즘 · 재귀 분할

결정 트리가 질문을 고르는 잣대

불순도 · 지니 불순도 · 엔트로피 · 정보 이득 · 분산 · 평균 제곱 오차

결정 트리의 과적합을 다스리는 방법

과적합 · 과소적합 · 가지치기 · 하이퍼파라미터 · 검증 세트 · 교차 검증 · 편향과 분산 · 잡음

여러 결정 트리를 묶는 앙상블

앙상블 · 랜덤 포레스트 · 그레이디언트 부스팅 · 배깅 · 부스팅 · XGBoost · LightGBM

결정 트리와 겨루는 다른 모델

로지스틱 회귀 · 선형 회귀 · 최근접 이웃 · 나이브 베이즈 · 서포트 벡터 머신 · 신경망

결정 트리의 예측을 해석하는 개념

결정 경계 · 특성 중요도 · 해석 가능성 · 설명 가능한 인공지능

결정 트리로 비용의 하한을 따지는 분석

비교 정렬 · 비교 정렬 하한 · 정렬 알고리즘 · 빅오 표기법 · 시간 복잡도 · 계산 복잡도 이론