[머신러닝] 의사결정트리(Decision Tree) 알고리즘

의사결정 트리란?

 

분류(Classification)와 회귀(Regression) 모두 가능한 지도 학습 모델 중하 나입니다. 데이터에 있는 규칙을 학습을 통해 자동으로 찾아내 트리 기반의 분류 규칙을 만드는 것입니다. 일반적으로 가장 쉽게 표현하는 방법은 if/else 기반으로 나타내는 것인데, 스무고개를 생각하면 쉽게 다가올 것입니다.

결정 트리에서 질문이나 정답은 노드(Node)라고 불립니다. 한번 분기 때마다 변수 영역을 두 개로 구분합니다. 이진트리의 개념으로 보면 될 것 같습니다.

 

• 뿌리 마디(Root Node): 나무 구조가 시작되는 마디 전체 데이터로 이루어져 있음
• 중간 마디(Internal Node): 나무 구조의 중간에 있는 마디들
• 끝 마디(Terminal Node): 나무 구조의 끝에 위치하는 마디
• 결정 트리의 기본 아이디어는, Leaf Node가 가장 섞이지 않은 상태로 완전히 분류되는 것, 즉 복잡성(entorpy)이 낮도록 만드는 것

 

CART(Classification And Regression Trees)

 

CART는 가장 널리 사용되는 의사결정 나무 알고리즘으로, 분류와 회귀 나무에서 모두 사용이 가능합니다. 불순도를 측정할 때 목표 변수(y)가 범주형인 경우 엔트로피, 지니 지수를 사용하고, 연속형인 경우 MSE를 이용해 분산량을 감소시켜 이진 분리를 합니다.

 

 

불순도(Impurity)

 

트리를 분기하는 기준은 불순 도라는 개념을 사용합니다.

• 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지를 뜻합니다.
• 다양한 개체가 섞여 있을수록 불순도가 높아집니다.

현재의 불순도에 비해 자식 노드의 불순도가 감소하도록 설정해야하고, 현재 노드와 자식노드의 불순도 차이를 정보 이득이라고 합니다.

 

정보 이득 (Information gain)

• 분기 이전의 불순도와 분기 이후의 불순도 차이를 정보 이득이라고 합니다.
• 불순도가 1인 상태에서 0.4인 상태로 바뀌었다면 정보 이득은 0.6입니다.

1. Root 노드의 불순도 계산
2. 나머지 속성에 대해 분할 후 자식 노드의 불순도 계산
3. 각 속성에 대한 정보 이득 계산 후 정보 이득(Root노드와 자식 노드의 불순도 차이)이 최대가 되는 분기 조건을 찾아 분기
4. 모든 leaf 노드의 불순도가 0이 될 때까지 2, 3을 반복 수행

 

엔트로피(Entropy)

 

정보 이득의 최대화 -> 불순도의 감소 -> 엔트로피의 감소

 

 

 

지니(Gini)

정보 이득의 최대화 -> 불순도의 감소 -> 엔트로피의 감소

 

 

 

연속형

분할 전 결정 값

분할 후 결정값

연속형 변수의 경곗값을 찾는 방법

1. 변수 값에 따라 데이터를 정렬한다.
2. 정답이 바뀌는 경계 지점을 찾는다.
3. 경계의 평균값을 기준으로 잡는다.
4. 구간별 경계값을 기준으로 불순도를 계산한다.
5. 가장 불순도를 낮추는 구간을 경계로 나눈다.

데이터

1) 변수 값에 따라 데이터를 정렬한다.

2) 정답이 바뀌는 경계 지점을 찾는다.

3) 경계의 평균값을 기준으로 잡는다.

4) 구간별 경곗값을 기준으로 불순도를 계산한다.

여기서는 지니계수

 

 

5) 가장 불순도를 낮추는 구간을 경계로 나눈다.

 

가장 정보 이득이 높은 구간을 경계로 나눈다.

범주형

• 데이터의 특성의 유무로 분할을 한다.
• 정보 이득을 최대화하는 분할을 선택한다.

 

 

Feature Importance(변수 중요도)와 가지치기

 

의사결정 나무에서 어떤 변수가 가장 중요한지를 나타내는 정도

불순도를 가장 크게 감소시키는 변수의 중요도가 가장 크다(불순도 감소는 정보 이득의 최대화와 동일한 뜻)

 

지니 지수를 이용한 Feature Importance

 

• 부모 노드의 지니 지수에서 자식 노드의 지니 지수를 뺍니다.
• 가중치는 전체 데이터 대비 노드에 있는 데이터 수의 비율

 

 

 

가지치기

Full Tree는 모든 끝 마디에서의 순도가 100%인 상태입니다. 분기가 너무 많아져서 Overfitting이 일어나기 쉽습니다.

분기가 너무 많아지는 것을 막기 위해서는 적절한 수준에서 끝 노드를 결합해주는 가지치기가 필요합니다.

 

사전 가지치기

트리의 최대 Depth나 노드의 최소 개수를 미리 지정해 더 이상 분할이 일어나지 않게 하는 방법

 

사후 가지치기

트리를 만든 후 데이터가 적은 노드를 삭제 또는 병합하는 방법

 

 

 

장단점

 

장점

• 모델의 예측 결과를 해석하고 이해하기가 쉽다.
• 데이터를 가공할 필요가 거의 없다.

단점

• 연속형 변수를 범주형 값으로 취급하기 때문에 분리의 경계점 부근에서 예측 오류가 클 수 있다.
• 노이즈 데이터에 영향을 크게 받는다.(Overfitting 발생 쉬움)