들어가며

아래와 같은 설문조사가 있다. 응답자들은 0 ~ 10점 선지 중 하나를 선택한다.

이러한 응답 데이터를 활용해서 특정 값을 예측하려 한다. 어떤 모델을 쓰면 좋을까? 이 문제 상황에서 가장 먼저 떠올린 것은 결정트리 모델이었다. 최소 0부터 최대 10으로 스케일이 한정된 정수 데이터가 주어졌으며, 결정트리 모델은 조건 (예를 들면, $x > 4$ ?)에 따라 샘플을 나누며 가지를 뻗어나가기 때문이다. 문제를 해결하는 데 결정트리가 적절한 모델이라는 직관적인 느낌을 받았다.

그러나 내가 설명할 수 있는 최선은 여기까지였다. “내가 모델의 개념과 원리를 근본적으로 이해하고 있나?” 반성하게 되었고, 이 글을 쓰게 된 계기가 되었다.

제한된 범위의 정수로 이루어진 응답 데이터를 처리하는 데 있어서 결정트리 모델이 적절한가?

즉, 이 질문에 답변하기 위해 해당 모델을 공부한 글이다.

개념

결정트리 Decision Tree, 의사결정 나무라고도 부른다.

데이터를 기준에 따라 반복 분할함으로써 계층적인 구조로 하위 집합을 형성하는 방법론

역사로 이해하기

결정트리 모델의 시초는 1960년대 사회과학에서 찾아볼 수 있다. 이후 1980년대 데이터 과학 분야의 발전과 함께 결정트리 방법론이 소개되고 다양한 모델이 개발, 활용되기 시작했다.

우선 1963년에 발간된 사회과학서 Problems in the Analysis of Survey Data, and a Proposal에 초기 개념이 소개되었다. 고차원의 다중공선성을 띠는 설문조사 데이터를 다루기 위한 방법론으로, 오차제곱합(SSE)를 최소화하도록 하위 그룹으로 분할한다.

사회과학 분야에서 다룰 법한 간단한 예제를 상상해봤다. 응답자의 나이, 성별, 연봉 수준을 수집했으며 이에 따른 직업 만족도를 비교하려 한다. 그런데 나이가 많을수록 연봉 수준이 높아지기도 하고, 분포 상 응답자가 여자일수록 나이대가 낮아진다. 이러한 변수 간 상호작용을 고려하면서 종속변수(직업 만족도)의 차이를 설명하기 위해 응답자를 그룹으로 나눠볼 수 있다. 30대 미만/이상으로 나눠도 좋고, 성별에 따라 나눠도 좋다. 중요한 건 나눠진 그룹끼리 직업 만족도를 비교했을 때 차이가 커지도록 하는 것이다.

그룹끼리 차이가 커지도록 그룹을 나누는 이유는, 그룹 안의 동질성이 높다는 것과 같은 의미이기 때문이다. 한 그룹의 평균을 예측값으로 삼는다고 치자. 그룹의 동질성이 높을수록 그룹 내 샘플들은 평균에 가까이 몰려 있을 테니 실제값과 예측값 간의 오차가 전반적으로 줄어든다.

이렇듯 직업 만족도가 가장 크게 차이나는 두 그룹으로 나눠 첫번째 분할을 마쳤다. 그 다음에 오차가 더 큰 그룹을 선택한 다음 그 안에서 또 분할한다. 마찬가지로 그룹 간 차이가 크게 발생하는, 다시 말해 오차를 최소화하는 분할 기준을 결정한다. 분할을 반복한다.

Problems in the Analysis of Survey Data, and a Proposal(1963), 17페이지. 오늘날 결정트리 모델을 시각화한 모습과 같다.

사회과학 분야에서 분할의 결과는 이렇게 활용할 수 있다. ‘30세 미만 남성 노동직 그룹과 여성 고졸 그룹의 직업 만족도가 75점 수준으로 비슷하다’ - 한편 머신러닝 분야라면? 입력 데이터에 대해 예측값을 출력하는 모델을 생성하는 데 활용할 수 있겠다! 30세 미만 남성 노동직이 입력으로 들어오면 75점 가량으로 예측하는 것이다.

이어 1984년 Classification and Regression Trees에서 결정트리 방법론을 기반으로 한 알고리즘 CART가 발표됐다. Classification And Regression Tree의 줄임말이다. 이어 CART의 업그레이드 버전인 ID3(Iterative Dichotomiser 3), C4.5, C5.0 등이 발표되면서 결정트리 모델이 더욱 발전해나갔다. 오늘날 많이 사용하는 Random Forest, XGBoost도 결정트리 방법론을 기반으로 개발된 알고리즘들이다.

분할의 기준

CART, ID3, C4.5, C5.0 알고리즘은 모두 결정트리 방법론을 기반으로 한다. 하지만 분할 기준을 무엇으로 설정하는지에 따라 다른 알고리즘으로 발전한 결과다. 앞서 언급한 예제에서는 간단하게 그룹별 직업 만족도의 평균값 차이를 기준으로 분할했지만, 실제 알고리즘에서는 더 효율적이거나 정교한 지표를 분할의 기준으로 삼는다.

분할 기준의 본질은 불순도(impurity)를 낮추는 것이다. 앞서 그룹 내 동질성을 높이는 것이 중요하다고 언급했다. 이는 불순도를 낮춘다는 말과 의미가 동일하다.

다른 데이터가 많이 섞여 있을수록 동질성이 떨어지며 이는 곧 불순도가 높은 상태다

분할의 결과로 얼마나 동질성이 높아지거나 낮아졌는지, 불순도를 수치화하는 방식은 크게 두 가지. 지니 계수와 엔트로피(정보 이득)다. 소개한 알고리즘 중 CART는 지니 계수를 사용하며, ID3, C4.5, C5.0은 엔트로피 및 정보 이득을 사용한다.

지니 계수(Gini coefficient)

지니 계수가 높을수록 불순도가 높다고 판단한다.

$J$

각 클래스

$p_{j}$

샘플이 클래스 $j$에 속할 확률

$p_{j}(1-p_{j})$

같은 클래스의 샘플을 뽑을 확률과 이어 다른 클래스의 샘플을 뽑을 확률을 곱하여 한 노드 안이 얼마나 섞여 있는지 나타내준다

지니 계수는 경제학에서 소득이 얼마나 불평등하게 분포되었는지 나타내는 데 쓴다. 결정트리 모델의 맥락에서는 분할된 노드에 얼마나 다른 클래스 샘플이 섞여 있는지 표현해준다.
$p_{j}^{2}$은 그 클래스의 샘플이 두 번 연속 추출될 확률이기 때문에 값이 높을수록 동질성이 높다는 의미다. 지니 계수는 이를 전체에서 뺌으로써 불순도를 계산한 결과다.

위에서 첨부한 이미지를 통해 분할 결과를 지니 계수로 평가해보겠다.

각 클래스에 대해 $p(1-p)$를 구한 후 합친다.

좌측 노드

• 노랑 클래스 : 4개 중 2개이므로, $p_{\text{노랑}} = 0.5$. 즉, $0.5 * (1 - 0.5)$.
• 초록 클래스 : 4개 중 1개이므로, $p_{\text{초록}} = 0.25$. 즉, $0.25 * (1 - 0.25)$.
• 검정 클래스 : 4개 중 1개이므로, $p_{\text{초록}} = 0.25$. 즉, $0.25 * (1 - 0.25)$.

$\text{Gini}_{\text{좌측}} = 0.25 + 0.1875 + 0.1875 = 0.625$

우측 노드

• 노랑 클래스 : 3개 중 1개이므로, $p_{\text{노랑}} \approx 0.333$. 즉, $0.333 * (1 - 0.3335)$.
• 초록 클래스 : 3개 중 2개이므로, $p_{\text{초록}} \approx 0.667$. 즉, $0.667 * (1 - 0.667)$.

$\text{Gini}_{\text{좌측}} = 0.222 + 0.111 = 0.445$

그 다음 분할된 개수를 기준으로 가중평균을 구한다. 좌측 노드는 네 개, 우측 노드는 세 개 샘플을 가져갔다.

해당 분할 결과에 대해서도 동일하게 구한다.

좌측 노드에서 다른 클래스가 추출될 확률($1-p$)는 $0$이므로 계산 결과도 $0$이 된다.

분할 전 지니 계수가 $0.612$ 라는 점을 고려하면, 두 분할 방식 모두 지니 계수가 줄어들어 불순도가 낮아진 상태이다. 둘 중에서는 이렇게! 의 지니 계수 $0.214$ 가 이렇게? 의 $0.548$ 보다 더 낮으므로 더 적합한 분할이라고 판단할 수 있다.

엔트로피(Entropy)

엔트로피는 정보량의 기대값을 의미한다.

$J$

각 클래스

$p_{j}$

샘플이 클래스 $j$에 속할 확률

$-\log{(p_{j})}$

클래스 $j$에 대한 정보량

정보 이론에서는 의외인 사건이 발생할 때 정보량(Information Content)이 더 많다고 본다. 여기서 ‘의외인 사건’은 곧 사건의 확률이 낮다는 것을 의미한다. (11월은 강우 확률이 낮으니까 11월에 눈이 오는 것은 의외인 사건이며 정보량이 많은 것이기도 하다. 1월에 눈이 오는 사건에 비해서 말이다.)

이처럼 확률이 낮을수록 정보량이 많고 높을수록 정보량이 낮아지는 것은 확률에 로그를 취하고 음수화한 값으로 표현할 수 있다. 그리고 이 정보량에 확률을 곱함으로써 구한 기댓값을 엔트로피라고 부른다.

확률이 낮다 => 정보량이 많다 => 엔트로피가 높다 <=> 사건을 예측하기 어렵다

노드에 다양한 클래스가 혼재되어 있을수록 어떤 클래스가 추출될지 예측하기 어렵다. 따라서 불순도를 측정하는 방식으로 엔트로피를 쓸 수 있다.

정보획득량 (Information Gain)

결정트리 알고리즘 ID3 에서는 ‘정보획득량’을 불순도 지표로 사용하는데, 이는 분할 전후의 엔트로피 차이를 계산한 값이다.

$IG(S, A)$

$A$ 속성을 기준으로 $S$를 분할했을 때의 정보 획득량

$H(S)$

$S$의 엔트로피

$T$

$S$를 분할함으로써 생성된 노드들

$p(t)$

$S$ 대비 노드 $t$의 비율(크기)

$H(t)$

노드 $t$의 엔트로피

$H(S|A)$

$A$ 속성을 기준으로 $S$를 분할하여 생성된 노드들의 $H(t)$를 가중 평균한 값

‘이렇게!’ 분할 방식을 정보 획득량에 따라 평가해보자. 나이 30살을 기준으로 샘플을 분할했다고 가정했다.

먼저 분할 전 엔트로피 $H(S)$를 구한다. 엔트로피 식 $-\sum_{j=1}^{J} p_{j} \log{(p_{j})}$ 을 적용하면 된다.

• 노랑 클래스 : 7개 중 3개이므로, $- \frac{3}{7} \log \frac{3}{7}$
• 초록 클래스 : 7개 중 3개이므로, $- \frac{3}{7} \log \frac{3}{7}$
• 검정 클래스 : 7개 중 1개이므로, $- \frac{1}{7} \log \frac{1}{7}$

$H(S) \approx 0.523 + 0.523 + 0.402 = 1.448$

다음으로 분할 후 엔트로피 $H(S|A)$를 구한다. 이는 각 노드의 엔트로피를 가중 평균하여 계산한다.

True 노드

• 초록 클래스 : 3개 중 3개이므로, $- \frac{3}{3} \log \frac{3}{3} = 0$

$H(\text{True}) = 0$

False 노드

• 노랑 클래스 : 4개 중 3개이므로, $- \frac{3}{4} \log \frac{3}{4} = 0$
• 검정 클래스 : 4개 중 1개이므로, $- \frac{1}{4} \log \frac{1}{4} = 0$

$H(\text{True}) \approx 0.311 + 0.5 = 0.811$

그 다음 분할된 비율을 기준으로 가중평균을 구한다. 좌측 노드는 네 개, 우측 노드는 세 개 샘플을 가져갔다.

$H(S|A) = \frac{3}{7} \cdot H(\text{True}) + \frac{4}{7} \cdot H(\text{False}) \approx 0.463$

최종적으로 분할 전에 비해 정보량을 비교한다.

분할 전후의 엔트로피를 비교한 결과 정보 이득은 약 $0.985$이다. 반면 이렇게? 분할 방식의 정보 이득을 계산하면 $0.198$로 비교적 정보 이득이 적은 것을 알 수 있다.

이처럼 불순도를 낮추는 방향으로 데이터를 분할하는 것을 반복함으로써 계층적인 트리 구조를 형성하는 것이 결정트리 방법론이다. 여기서 ‘불순도’를 어떤 지표로 평가할지, 언제까지 분할을 반복할지, 어떤 노드를 주로 참고할지 등 구체적인 활용 방식에 따라 다른 알고리즘이 될 수 있다.

직관 설명하기

제한된 범위의 정수로 이루어진 응답 데이터를 처리하는 데 있어서 결정트리 모델이 적절한가?

지금까지 결정트리 방법론의 등장 맥락, 분할의 기준을 살펴보았다. 이제 처음의 질문으로 돌아가보자.

“제한된 범위”

결정트리 모델은 값이 좁은 범위로 제한된 데이터에 대해 유리할 수 있다. 결정트리가 비모수적 모델(non-parametric models)이기 때문이다.
결정트리 모델은 주어진 데이터를 거듭된 조건에 따라 쪼개 나간다. 특정 분포를 가정하지 않고 주어진 데이터에 따라 비선형적인 구조를 형성한다는 의미다. 반면 선형회귀와 같은 모수적 모델은 모든 범위의 데이터에 대해서 유효한 분포(함수)가 있다고 가정하고 이에 맞춰 파라미터를 학습(fit)한다. 실제 데이터에 비해 함수 가정이 과도할 수 있다. 우리는 0 ~ 10 의 범위에서 벗어나는 입력은 전혀 고려하지 않고 있단 말이다.

“정수”

결정트리 모델은 특정 임계값을 기준으로 데이터를 분할하는데, 정수형 데이터는 이산적(discrete) 성격을 띠므로 분할 자체가 직관적이고 간단해진다. 예를 들어 ‘5번 질문에 대한 응답이 3점 이상’이라는 분할 조건을 세우는 건 간단하고 직관적이다. 하지만 데이터가 연속형이었으면 ‘A 속성이 0.3728 이상’과 같이 정밀한 임계값을 정해야 했을 것이다. 당연히 더 많은 경우의 수를 고려해야 하기 때문에 난이도가 높아진다.

“응답 데이터”

설문 참여자들은 비슷한 질문에 대해 비슷하게 응답하는 경향이 있을 것이다. 예를 들어 ‘인생이 행복합니까?’ 라는 질문에 그렇다고 응답할수록, ‘생활이 만족스럽습니까?’ 라는 질문에도 그렇다고 응답할 것이다. 이처럼 변수 간 상관관계가 존재하는 다중공선성의 문제에 결정트리 모델이 유리하다. 애초에 결정트리는 사회과학 연구에서 일종의 교차분석과 유사한 방법론으로 제시되지 않았는가?
결정트리는 불순도가 (지니 계수든 엔트로피든) 가장 크게 감소하는 조건을 선택하여 분할을 실시하기 때문에 가장 중요한 변수가 우선적으로 선택되는 효과가 있다. 그 결과 비슷한 패턴의 변수들은 자연스럽게 제외되기 때문에 변수 간 상관관계는 결정트리 모델에 큰 해가 되지 않는다.

나가며

결정트리의 작동 맥락과 주요 지표를 살펴봄으로써 나의 직관을 설명할 수 있었다. 이 과정에서 ‘비모수형 모델’의 개념을 명확하게 이해할 수 있게 되었고, 머신러닝 분야에서 ‘엔트로피’가 가지는 의미를 다시 상기할 수 있었다. 이번 공부를 통해 나의 직관이 어느 정도 의미 있었다는 결론을 내렸으므로, 이제 실제 적용하는 일만 남았다.

분량이 너무 길어져서 가지치기나 정지규칙, 코드 등 더 깊은 내용은 다루지 못했지만 모델의 본질과 연결되는 직관을 이해했다는 점에서 만족스러운 공부였다. 이어서 결정트리 방법론을 기반으로 하는 다양한 머신러닝 모델에 대해서 하나씩 공부하는 시간을 가져보겠다.