의사결정나무(decision tree)

관련글

선형회귀분석 밑바닥부터 이해하기

1. 들어가며

선형회귀모델 분석을 통해 수치형 변수를 예측하거나 수치형 변수의 결과에 영향을 미치는 X(반응변수)가 무엇인지 파악할 수 있다. 그러나 정확한 수치를 예측한다는 것은 현실적으로 어렵기 때문에 회귀분석은 Y값(결과변수)의 변화에 영향을 미치는 여러 개의 변수를 발견하고 그 영향력을 비교하는 목적으로 주로 사용된다.

 

반면 범주형 변수 예측은 어떤 변수가 어떤 범주에 속할지 예측하는 것으로서, 예를 들면 은행에 어떤 고객이 대출을 요청했을 때, 대출금을 제대로 갚을지 말지 예측하거나, 또는 이메일을 받았을 때, 스팸메일일지 아닐지 판단하는 등의 결과를 예측하는 방법을 의미한다. 범주형 변수 예측은 현재 머신러닝 분야에서 가장 많이 활용되는 기법이기 때문에 다양한 알고리즘이 개발되었는데 여기에서는 가장 대표적인 방법에 대해 살펴보자. 

 

2. 의사결정나무 알고리즘의 원리

나무(tree)라는 표현을 쓰는 이유는 의사결정과정이 나무 줄기에서 가지가 뻗어나가는 모양과 유사하기 때문이다. 의사결정나무의 기본 원리는 비교적 간단하다. 예를 들어 신용카드 회사에서 새로운 고객에게 카드를 발급할지 말지 결정해야 한다고 하자. 과거부터 현재까지 쌓인 데이터를 통해 카드 대금 연체여부에 영향을 미치는 변수들 중 가장 영향이 큰 것부터 차례로 나열하고 각 변수에서 어떠한 조건을 분기점으로 카드 대금 연체에 이르게 되는지 나무가 가지를 뻗어가는 형태로 도식화하면 된다.

 

[그림 1] 의사결정나무 알고리즘 기본 원리

 

<그림 1>에서 연봉이 2천만원 미만이고, 주택을 소유하고 있지 않으며, 신용 카드를 3장 이상 보유한 사람들은 과거에 카드 대금을 연체했다는 결과를 얻었다. 따라서 신규고객이 카드 발급을 요청했을 때 새로운 고객의 조건이 과거에 카드 대금을 연체한 사람들의 조건과 같다면 카드 대금을 연체할 가능성이 크기 때문에 카드 발급을 거절하게 될 것이다. 물론 새로운 고객이 그러한 조건이라고 해서 미래에 카드 대금을 100% 연체한다는 보장은 없지만 확률적으로 높다고 판단하는 것이 합리적이다.

 

의사결정나무 구조에서 처음 시작하는 시작하는 변수를 뿌리 노드라고 하고 중간 단계의 변수를 노드라고 하며 마지막 결과를 터미널 노드 또는 잎 노드라고 한다.

 

3. 뿌리 노드 결정 원리

그렇다면 의사결정나무에서 어떤 변수를 뿌리 노드로 결정해야 하는가? 즉 어떤 변수에서부터 시작해야 하는가? 의사결정나무에서 어떤 변수가 뿌리 노드로 결정된다는 말은 그 변수를 이용하면 전체 데이터 중에서 카드 대금 결제자와 카드 대금 연체자를 가장 분명하게 구분할 수 있다는 의미가 된다.

 

[그림 2] 변수별 범주 분류

 

<그림 2>에서 보는 것처럼 연봉>2,000 이라는 변수로 전체 데이터 중 카드 대금 연체와 결제 여부를 구분하면 Yes인 그룹과 No인 그룹에서 카드 대금 결제와 연체의 비율이 어느 한쪽으로 쏠린다. 반면 대학졸업유무로 전체 데이터를 나누면 카드 대금 결제와 연체의 비율이 어느 한쪽으로 쏠리지 않고 비슷비슷하게 나온다. 이렇게 모든 변수 중 전체 데이터를 카드 대금 결제자와 연체자로 가장 분명하게 구분하는 변수가 뿌리 노드가 되며, 다음 분기점에서 남아 있는 데이터를 가장 확실하게 구분 짓는 변수가 다음 노드가 되는 것이다.

 

4. 엔트로피 계수(entropy coefficient)

앞에서 설명했듯이 각 단계에서 가장 명확하게 전체 데이터를 카드 대금 결제자와 연체자로 구분하는 변수를 결정하기 위해서 일반적으로 엔트로피 계수라는 값을 사용한다. 엔트로피가 높으면 집단의 성격이 균일하지 못하다고 표현한다. <그림 2>에서 어떤 그룹이 카드 대금 결제자가 4명이고 카드 대금 연체자가 6이면 거의 비슷하게 섞여 있으므로 균일하지 못하다. 반면 카드 대금 결제자가 1명이고 카드 대금 연체자가 9명인 그룹은 90%가 카드 대금 연체자로 구성되었으므로 집단의 성질이 상대적으로 균일하다고 볼 수 있다.

 

요약하자면, 엔트로피 계수는 한 집단의 불확실성 또는 불순도를 의미하며 다음과 같은 수식으로 표현된다.

 

가령 한 집단에 두 개의 그룹이 있고 이들이 대등한 비율(50 : 50)로 섞여 있으면 엔트로피 값이 최대가 되고 어느 하나의 그룹으로만 구성되었을 때 최소값을 갖는 성질이 있다. 따라서 모든 변수들의 엔트로피 값을 구한 후, 가장 엔트로피 값이 작은 변수를 뿌리 노드로 설정한다.

실제 엔트로피 값을 계산해보자. 전체 데이터에 카드 대금 결제자(70%)와 카드 대금 연체자(30%)가 7:3으로 분포되어 있을 때 이 상태에서의 엔트로피는 다음과 같다.

 

 

 

5. 지니계수(Gini Coefficient)

 

엔트로피계수의 대안으로 지니계수가 사용될 수도 있다. 엔트로피계수와 개념은 비슷하고 단지 계수를 구하는 공식에 약간 차이가 있을 뿐이다. 공식은 다음과 같다. 

엔트로피계수를 계산했던 사례를 지니 계수로 계산해 보자. 카드 대금 결제자(70%)와 카드 대금 연체자(30%)가 7:3으로 분포되어 있을 때 이 상태에서의 지니계수는 다음과 같다.

 

 

6. 정보이득(information gain)

의사결정트리에서 뿌리 노드가 정해졌다면 다음 단계로 가지를 뻗어나가기 위해서 정보이득(Information Gain) 개념이 필요하다. 정보이득은 어떤 변수로 분할을 했을 때, 계산되는 불확실성 차이이다. 예를 들어 하나의 변수 F를 기준으로 뿌리 마디에서 다음 마디로 분할이 이루어졌다면 분할 전(𝑆1)과 분할 후(𝑆2)의 엔트로피 값에 차이가 발생하는데 이 차이 값을 정보이득이라고 한다.

 

 

만약 어떠한 변수를 기준으로 다음 단계로 분할 한 후(𝑆2)의 엔트로피가 크다면 여전히 불순도가 높다는 의미고, 그 말은 두 그룹의 분리가 확실하게 되지 않았다는 의미이다. 따라서 (𝑆2)의 엔트로피가 크면 자연히 정보이득(Information Gain)의 값은 작을 것이다. 

 

반대로 분할 한 후(𝑆2)의 엔트로피가 작다면 불순도가 낮고 두 그룹의 분리가 어느 정도 확실하게 되었다는 의미이며, 따라서 (𝑆2)의 엔트로피가 작으면 정보이득(Information Gain)의 값은 커질 것이다.

 

결론적으로 어떠한 변수를 기준으로 다음 단계로 가지 분할 했을 때, 정보이득 값이 크면 그 변수를 분할 기준 변수로 쓴 것이 적절했다는 의미이다. 따라서 다음 단계로 가지 분할할 변수는 정보이득 값을 가장 크게 하는 변수를 찾으면 될 것이다. 정보이득을 구하는 예는 <그림 3>과 같다. 

[그림 3] 정보이득 계산 예

 

 

 

정말 쉬운 연관규칙 알고리즘

R_의사결정나무 분석(rpart)

혼동행렬(confusion matrix)