의사 결정 나무(Decision Tree)

Decision Tree 란?

의사결정 규칙을 나무구조로 나타내어 분류 및 예측을 수행하는 분석방법이다. 이 방법은 분류 또는 예측이 나무구조에 의한 추론에 의해서 표현되기 때문에 다른 방법들에 비해 쉽게 이해가 가능하다. 

그림을 통해 노드들을 간단하게 설명하면 다음과 같다. 한 번에 하나씩의 설명변수를 사용하여 정확한 예측이 가능한 규칙들의 집합을 생성한다.

• Root Node : 트리 구조 중 가장 맨 위에 있는 노드 ( '남자인가?' )
• Leaf Node, Terminal Node : 자식 노드가 없는 가장 맨끝에 있는 노드 (사망, 생존)
• Internal Node : 루트 노드와 터미널 노드를 제외한 노드 ( '(나이 > 9.5)인가?', '(sibsp > 2.5)인가?' )

그렇다면 어떤 순서로 노드를 배치해야 하고, 어떤 질문으로 데이터를 나눠야 할지 기준이 필요할 것이다.

 

Decision Tree의 분할 기준(Split Criterion)

1. 분류 나무 (Classification Tree)

분류나무는 구분 뒤 각 영역의 순도가 증가하고, 불순도 혹은 불확실성이 감소하도록 하는 방향으로 학습을 진행한다. 

 

1-0. 정보 획득(Information Gain)

순도가 증가하고 불확실성이 감소하는 걸 두고 정보이론에서는 정보 획득이라고 한다.  정보의 가치를 반환하는 데 발생하는 사건의 확률이 작을수록 정보의 가치는 커지게 되며, 확률이 높을수록 가치는 작아지게 된다.

그래프와 같이 확률이 1에 가까워 질수록 가치는 0에 수렴한다. 사건의 발생확률이 낮다면 그만큼 가치는 급상승 한다.

예를 들면, 사람은 죽는다와 같이 확률이 1에 가까운 사건은 정보의 가치가 상당히 낮을 것이다. 이와 반대로 사람은 죽지 않는다와 같은 사건의 확률은 0에 가깝기 때문에 정보의 가치가 높을 것이다.

 

1-1. 지니 지수(Gini Index)

영역내에서 특정 클래스에 속하는 관측치들의 비율을 제외한 값이다.

Pk는 한 영역에 속한 데이터 중 k범주에 속하는 데이터의 비율. m은 범주의 갯수가 되겠다.

두 개 이상 영역에서의 식은 다음과 같다.

Ri는 분할 전 데이터 중에서 분할 후 i 영역에 속하는 데이터의 비율이다. (범주 상관없이)

분기 후 정보 획득량 (Information Gain) 은 0.47 - 0.34 = 0.13 이다.

 

1-2. 엔트로피 지수(Entropy Index)

엔트로피는 열역학에서 나온 개념으로써 무질서에 대한 측도 역할을 한다. 지니 지수와 비슷하지만 log를 취함으로써 정규화 과정을 거치게 된다.

여기서도 마찬가지로 Pk는 한 영역에 속한 데이터 중 k범주에 속하는 데이터의 비율. m은 범주의 갯수가 되겠다.

두 개 이상 영역에서는 다음과 같다.

분기 후 정보 획득량 (Information Gain) 은 0.95 - 0.75 = 0.20 이다.

 

2. 회귀 나무(Regression Tree)

2-1. 분산

분산의 감소량을 최대화하는 방향으로 노드가 나눠진다.

 

Decision Tree의 학습 방법

1. 재귀적 분귀 (Recursive Partitioning)

재귀적 분기는 특정 영역인 하나의 노드 내에서 하나의 변수 값을 기준으로 분기하여 새로 생성된 자식 노드들의 동질성이 최대화되도록 분기점을 선택하는 것이다. 동질성이 최대화된다는 말은 즉, 불순도는 최소화 된다는 의미이다. 

보통 불순도를 측정하는 기준으로 아래의 기준을 사용한다.

1. 범주형 변수 : 지니 계수 (Gini Index)
2. 수치형 변수 : 분산 (Variance)

예시로 iris 데이터 중에서 Species 범주 중 'setosa'와 'versicolor' 범주 중 12개씩만을 사용했다. 

우선 한 변수를 기준으로 정렬을 해야 하는데, 여기서는 Sepal.Width를 기준으로 정렬하겠다. 그 후에 가능한 모든 분기점에 대해서 엔트로피와 지니 지수를 구해 분기 전과 비교하여 정보 획득을 조사한다.

예를 들어, 위 예시에서 나눌 수 있는 모든 분기점을 row 번호로 나열한다면 (1 | 2 : 24), (1 : 2 | 3 : 24), ... (1 : 23 | 24) 이렇게 될 것이다. (1 | 2 : 24)의 예시에서 엔트로피와 지니 지수를 구해보자.

• 분기 전

분기 전 지니 지수

분기 전 엔트로피 지수

분기 전의 경우 영역은 한 개이며, 해당 영역 내에서 총 24개의 데이터 중 각 범주별로 12개씩 존재한다.

• 분기 후

분기 후 지니지수

분기 후 엔트로피 지수

분기 후의 경우 A, B라는 2개의 영역으로 나눠진다고 가정할때, A 영역 내에는 Sepal.Length = 5.0 / Sepal.Width = 2.0 / Species = Versicolor인 첫 번째 데이터만 있을 것이고 그 이외 23개의 데이터는 B 영역내에 있다.

정보획득 수치를 각각 계산한다면 지니지수 = 0.5 - 0.48 = 0.02 / 엔트로피 지수 = 1 - 0.96 = 0.04 이다.

따라서 분기별로 지니지수와 엔트로피 지수를 구하고 분기 전과 후의 값을 빼면 정보 획득 수치가 나올 것이다. 정보 획득량이 가장 최대가 되는 분기를 선택하면 된다.

만약 분기를 하는데 기준이 되는 변수가 위와 같이 수치형이 아닌 범주형이라면 범주를 나누면 된다. 예를 들면 다음과 같다. 만약 A, B, C 총 3개의 범주가 있다면,

위의 경우 마다 각각 지니 지수와 엔트로피 지수를 구하여 정보 획득을 계산하면 된다.

 

2. 가지치기 (Pruning)

가지치기란 나무의 가지를 치는 것과 같아서 이름이 붙여졌으며, 가지를 잘라서 버리는 것이 아닌, 합치는 것이라고 이해해야 한다. Decision Tree 분기 수가 증가할때, 초기에는 오류율이 감소하지만 어느 시점부터는 증가하기 시작한다. 

먼저 full tree란 Terminal node의 순도가 100%인 상태인 트리를 말한다.

보통 full tree의 경우 분기가 너무 많아 과적합 (Overfitting)이 발생하기 쉽다. 따라서 먼저 full tree를 생성한 뒤 적절한 수준에서 하위 노드와 상위 노드를 결합해주어야 한다.

 

1-1. Cost Complexity Pruning

비용 복잡도(Cost Complexity)를 사용하여 최적의 Decision Tree 구조를 선택한다. 

• CC(T) : Decision Tree의 비용 복잡도 (낮을수록 우수한 Decision Tree이다.)
• Err(T) : 검증데이터에 대한 오분류율
• L(T) : Terminal Node의 수 (구조의 복잡도)
• α : Err(T)와 L(T)를 결합하는 가중치 (Weight). 사용자에 의해서 지정된다. 보통 (0.01 ~ 0.1)을 사용한다.

 

1-2. Reduced Error Pruning

 

노드 가지치기 전의 Error와 노드의 아래부분을 모두 자르거나 결합한 뒤의 Error를 비교하여 오류가 더이상 감소하기 전까지 반복하는 방법이다.

 

1-3. Rule Post Pruning

Rule이란 Root Node부터 Leaf Node 까지의 경로를 의미하며, 트리를 모두 Rule 형태로 변환 한 뒤 각 Rule의 Acuuracy를 구하고 낮은 순으로 제거하는 방법이다.

 

 

오른쪽의 경우 Full-tree 이며, 왼쪽의 경우 적절한 Pruning을 한 뒤의 Tree이다.

 

Decision Tree의 장점 & 단점

1. 장점

1. 쉽게 이해를 할 수 있는 규칙의 형태로 구성되어 있다.
2. 데이터의 전처리 (정규화, 결측치, 이상치 등) 를 하지 않아도 된다.
3. 수치형과 범주형 변수를 한꺼번에 다룰 수 있다.

2. 단점

1. 한 번에 하나의 변수만을 고려하므로 변수간 상호작용을 파악하기가 어렵다.
2. 결정경계 (Decition Boundary) 가 데이터 축에 수직이어서 비선형(Non-Linear) 데이터 분류에는 적합하지 않다.
3. Full Tree일 경우 오버피팅이 발생하기 쉽다.

 

Reference

• https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%ED%8A%B8%EB%A6%AC_%ED%95%99%EC%8A%B5%EB%B2%95
• https://gomguard.tistory.com/86
• https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
• https://en.wikipedia.org/wiki/Decision_tree_pruning