의사결정나무(Decision Tree) [Supervised Learning]

AI, 데이터 분석의 밑바탕인 머신러닝(기계학습)에는 크게 세 가지 갈래가 있다.

 

- 지도학습 (타겟, 정답을 함께 학습시켜 타겟을 예측한다.)

- 비지도학습 (타겟, 정답없이 학습시켜 데이터의 특성을 파악한다.)

- 강화학습 (주어진 상태에 대한 보상을 통해 최적의 행동을 학습시킨다.)

 

의사결정나무 - 지도학습

의사결정나무는 분류, 회귀 문제에 모두 적용이 가능한 지도학습 알고리즘이다.

(분류 문제: 분류 나무, 회귀 문제: 회귀 나무)

이는 비교적 간단하고 쉬운 알고리즘으로 오늘날까지 현업에서 가장 많이 이용되는 알고리즘 중 하나이다.

이름에서도 알 수 있듯이, 이 모형은 의사결정 과정을 단계별로 도식화한 나무 형태를 가진다.

이 모형에서 각 단계를 "노드"라고 하는데, 이 알고리즘은 상위노드에서 하위노드로 뻗어나갈 때, 불순도를 줄이는 방향으로 분기해 나간다.

 

의사결정나무 예시, 출처)구글

 

장점

 

- 이 모형은 최종 분류나 수치 예측에 도달하기까지의 과정을 확인할 수 있기 때문에, 설명력이 매우 우수하며 해석이 용이하다.

- 복잡한 전처리 과정을 요구하지 않으며, 연속형 변수와 범주형 변수를 모두 처리할 수 있다.

- 각 노드, 분류기준을 통해 의미 있는 변수를 알아볼 수 있다.

 

단점

 

- 분류지점에서 오류가 발생할 위험이 높다.

ex) 분류기준에서 기준값이 1000일 때, 999와 1001은 다르게 분류된다.

- 과적합 문제에 매우 민감하다.

- 데이터 셋이나 적용 상황에 따라 계산량이 매우 많아진다.

 

 

용어

 

 

- 깊이(depth): 나무의 성장치, 최대 길이

- 노드(node): 각 마디, 분류기준이 되는 변수 (= 마디)

- 자식마디(child node): 상위 노드에서 분리되어 나간 하위 마디들

- 부모마디(parent node): 분류기준이 되는 상위 마디

- 루트(root): 뿌리 노드로, 부모마디가 없는 제 1 분류기준

- 잎(leaf): 가장 말단 마디로, 자식마디가 없는 노드

 

분석 과정

 

1. 변수 선택

 

목표변수(= 타겟변수 = 종속변수)와 관련된 설명변수( = 독립변수)를 선택한다. 

보통 각 도메인과 목표에 따라 전략적으로 선정한다. 

 

2. 모델링

 

의사결정나무 모델을 만든다.

이는 나무를 성장시킨다고 표현하기도 하는데, 분석가는 적절한 정지규칙과 분류기준, 평가기준을 지정해야 한다.

 

특히, 정지규칙을 설정하는 것은 모델링에 있어서 매우 중요한 하이퍼 파라미터(분석가가 조정하는)이다.

정지규칙은 최대 깊이(depth)를 지정하거나 잎 노드의 최소 데이터 수를 지정하는 등 나무의 성장정도를 미리 지정하는 것인데, 이 정지규칙을 적절히 설정하지 않으면 모델이 지나치게 과적합 혹은 과소적합될 위험이 있다.

 

하이퍼 파라미터 설정 예시

 

분리기준은 모델이 분류 나무인지 회귀 나무인지에 따라 다른 척도가 쓰인다.

 

분류 나무일 때,

 

- 카이제곱 통계량:  ((실제도수 - 기대도수)^2 / 기대도수)의 합 (CHAID 알고리즘)

- 지니 지수: 불순도 함수로, 특정 집합에서 한 항목을 뽑아 무작위로 클래스를 추정 시에 틀릴 확률

(CART 알고리즘)

- 엔트로피 지수: 불순도 함수로, 무질서 정도에 대한 측도 (C4.5 / C5.0)

 

분리 기준, 즉, 노드를 선택할 때, 서로 다른 데이터가 섞여 있는 정도인 "불순도"를 통해 자식 노드가 부모 노드에 비해 불순도가 감소되도록 한다. 이 때, 부모 노드와 자식 노드의 불순도 차이를 "정보 획득(Information Gain)"이라고 부른다.

따라서 나무는 정보 획득을 최대화하는 방향으로 분기한다고 볼 수 있다.

 

회귀나무일 때, 

 

- mse: 평균제곱오차

- F-통계량의 P-value (CHAID 알고리즘)

- 분산감소량 (CART 알고리즘)

 

 

F통계량의 P값이나 분산의 감소량은 그것이 커지는 쪽으로 분기가 일어난다.

이는 P값이나 분산 감소량은 값이 커질수록 자식 노드 간의 이질성이 커지며 노드 내부의 순수도는 올라가기 때문이다.

 

 3. 가지치기

 

테스트 데이터를 활용하여 성능을 확인한 후,

부적절한 추론규칙을 가지고 있거나 불필요한 혹은 오류를 크게 할 위험이 있는 마디를 직접 제거한다.

이는 분기가 너무 많을 경우(나무가 지나치게 성장한 경우) 학습 데이터에 과적합될 위험을 차단하기 위해서이다.

 

이에 사전에 성장을 제한하거나 특정 노드를 제외하는 등의 "사전 가지치기"나

사후 평가를 통해 오류를 줄이고 혹은 정확도가 낮은 순서대로 노드를 제거하는 "사후 가지치기"가 필요하다.