의사 결정 트리 (Decision Tree)

의사 결정 트리는 일련의 분류 규칙을 통해 데이터를 분류, 회귀하는 지도 학습 모델 중 하나이며, 결과 모델이 Tree구조를 가지고 있기 때문에 의사 결정 트리 또는 결정 트리(Decision Tree)라고 합니다. 위의 그림은 의사 결정 트리의 예시로 특정 기준(질문)에 따라 데이터를 구분하는 모델입니다. 질문이나 정답을 노드(Node)라고 하며 가장 상위에 있는 질문을 Root Node라고 하고 중간에 나타나는 노드를 Intermediate Node, 최하단의 마지막 노드를 Leaf Node라고 합니다.

만들어진 모델을 쉽게 시각화할 수 있어서 이해하기 쉬우며 각 특성이 개별적으로 처리되어 데이터를 분할하는 데 데이터 스케일의 영향을 받지 않으므로 특성의 정규화나 표준화, 이상치와 결측치 제거 같은 데이터 전처리 과정이 필요없습니다. 특히 특성의 스케일이 서로 다르거나 이진 특성과 연속적인 특성이 혼합되어 있을 때도 사용할 수 있습니다. 즉 수치형과 범주형 변수를 모두 다룰 수 있습니다.

결정 트리의 주요 단점은 가지치기와 하이퍼파라미터 조절 등을 사용함에도 불구하고 과대적합되는 경향이 있어 일반화 성능이 떨어집니다.

 

의사 결정 트리 생성 과정

초기 데이터셋

위의 그림과 같이, 파란 동그라미 클래스 0과 빨간 세모 클래스 1인 두 개의 클래스로 구분해야 하는 데이터셋을 예시로 들겠습니다. 결정트리를 학습한다는 것은 정답에 가장 빨리 도달할 수 있는 질문 목록을 학습한다는 의미이며, 가능한 모든 질문에서 가장 잘 나누어진 질문을 선택합니다.

깊이 1인 결정 트리(오른쪽)가 만든 결정 경계(왼쪽)

위의 그림에서 직선이 의미하는 x[1] <= 0.0596 기준이 선택되고 직선의 아래에는 클래스 0이 2개, 클래스 1이 32이고 직선의 위에는 클래스 0이 48개, 클래스 1이 18개로 구분이 되었습니다.

깊이 2인 결정 트리(오른쪽)가 만든 결정 경계(왼쪽)

다음으로 위의 그림에서는 직선으로 나누어진 두 영역에서 또 가장 잘 나누어지도록 x[0] 값을 기준으로 왼쪽과 오른쪽 영역으로 나누고 있습니다. 이렇게 영역이 가장 잘 나누어진 직선이 의미하는 기준을 반복해서 학습하며 모델을 정확하게 만들 수 있습니다.

깊이 9인 결정 트리의 일부(오른쪽)와 이 트리가 만든 결정 경계(왼쪽)(전체 트리는 너무 커서 일부만 표시)

계속해서 위와 같은 반복된 프로세스를 통해 각 분할된 영역들이 한 개의 클래스를 가질 때까지 반복합니다. 한 개의 클래스만 이루어진 leaf node를 순수노드(Pure Node)라고 합니다. 예시 데이터셋의 최종 분할 트리는 위의 그림과 같습니다.

반복적으로 하나의 축을 따라 데이터를 둘로 나누는 과정을 통해 데이터를 분류하고 기준이 되는 특성(Feature)은 동일하기 때문에 나누어진 영역은 항상 축에 평행합니다. 결론적으로 의사 결정 트리는 계층적으로 영역을 분할해가는 알고리즘이라고 할 수 있습니다.

 

불순도 지수

결정 트리에서 분기되는 기준을 선택하기 위해 불순도를 계산하고 사용합니다. 불순도는 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지를 뜻하며 다양한 개체들이 섞여 있을수록 불순도가 높아집니다. 결정 트리 알고리즘에서 분기 기준 설정 시 현재 노드의 불순도에 비해 자식 노드의 불순도가 감소되도록 설정해야합니다. 불순도를 수치적으로 나타낼 수 있는 대표적인 불순도 지수는 지니(Gini) 지수와 엔트로피(Entropy) 지수가 있습니다.

1)지니 지수

지니 지수의 공식은 위와 같으며 지니 지수는 반드시 0 ~ 0.5 사이의 값을 가지게 됩니다. 클래스들이 골고루 섞여 있을수록 지니 지수의 값이 커집니다.

위의 그림은 범주 안에 빨간색 점 10개, 파란색 점 6개 있을 때의 계산 예제입니다.

 

2) 엔트로피 지수

엔트로피 지수의 공식은 위와 같으며 엔트로피 지수는 지니 지수와 달리 반드시 0 ~ 1 사이의 값을 가지게 됩니다. 클래스들이 골고루 섞여 있을수록 엔트로피 지수의 값이 커집니다.

정보획득(Information Gain)

분기 이전의 불순도와 분기 이후의 불순도 차이를 정보획득이라고 합니다. 불순도가 1인 상태에서 0.7인 상태로 바뀌었다면 정보획득은 0.3입니다. 의사 결정 트리 알고리즘에서 분기 기준을 선택하기 위해 정보획득을 사용하며 결정 트리 구성 단계는 아래와 같습니다.

1. Root 노드의 불순도를 계산
2. 나머지 특성에 대해 분할 후 자식 노드의 불순도를 계산
3. 각 특성에 대한 정보획득을 계산하고 비교하여 정보획득이 최대가 되는 분기 조건을 찾아 분기합니다.
4. 모든 Leaf 노드의 불순도가 0이 될때까지 단계 2, 3을 반복 수행

 

과적합 문제(Overfitting)

결정 트리 생성 시 Leaf 노드가 한 가지 범주만을 가지게 되는 최대 트리(Full Tree)일 경우 과적합 문제(overfitting)가 발생하여 일반화 성능이 떨어지게 됩니다. 따라서 새로운 데이터가 입력되면 예측률이 떨어지게 됩니다. 이를 막기위해 아래와 같은 여러 하이퍼파라미터(Hyper Parameter)를 조절하거나 가지치기를 통해 일반화 성능을 올릴 수 있습니다.

• Max_Depth : 최대 트리의 깊이를 제한
• Min Sample Split : 노드 내에서 분할이 필요한 최소의 데이터 수
• Min Samples Leaf : Leaf 노드의 최소 데이터 수
• Max Leaf Nodes : Leaf 노드의 최대 개수
• Max Features : 최적의 분할을 찾기 위해 고려할 특성의 수

가지치기(Pruning)

일반화 성능을 높히는 방법 중 하나로 최대 트리로 형성된 결정 트리의 특정 노드 및의 하부 트리를 제거하는 방법입니다. 

 

 

참고사이트

https://tensorflow.blog/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D/2-3-5-%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%AC/

2.3.5 결정 트리

https://wooono.tistory.com/104

[ML] 의사결정트리(Decision Tree) 란?