머신러닝 개념 정리) 결정 트리, 엔트로피 지수, 지니 지수, CART 알고리즘

결정 트리란?

트리 구조를 기반으로 데이터 안에 숨어있는 패턴을 속성들의 조합으로 표현하는 분류 모델이다.

각 분기점에서 하나의 질문을 던지고, 대답에 따라 데이터들을 분류한다. 분류된 데이터에 다시 또 다른 질문을 하여 데이터를 세분화한다. 반복하여 최종 값을 얻을 수 있다.

 

결정 트리는 노드, 가지, 깊이로 구성된다.

• 노드는 데이터를 분류하기 위한 질문 지점이자 하나의 결정 단위로 작용하며 박스같은 도형형태로 표시된다. 각 노드는 주어진 조건(질문)에 따라 데이터를 두 그룹으로 나누는 과정을 반복하여 데이터를 세분화한다.
• 가지는 한 노드에서 다음 노드로 이어지는 경로를 의미하며, 선으로 표시된다. 데이터가 어떻게 분리되는지 시각적으로 보여준다.
• 깊이는 루트 노드부터 리프 노드까지 거치는 분할 단계의 수를 의미한다. 루트 노드의 깊이는 0, 다음 노드로 이동할 때마다 깊이가 1씩 늘어난다. 모델의 복잡도를 판단하는 지표로 활용되며, 이후 가지치기를 통해 적절한 수준으로 조절한다.

출처: 어깨동무 머신러닝 및 딥러닝

1. 트리의 최상단에 위치한 루트 노드에서 첫 번째 질문인 월소득 213만 원을 적용한다
2. 조건의 결과인 월소득 213만원 이상이면 참 또는 그렇지 않으면 거짓에 따라 해당하는 가지를 따라 이동한다
3. 다음 노드인 하위 노드에 도착하면 새로운 질문을 적용하며 월소득 213만원 이상 그룹의 경우 연령을 기준으로 분류한다
4. 마지막 노드인 잎 노드에 도달하면 최종 결과인 해당 데이터의 최종 분류나 예측 결과를 나타낸다

노드의 종류

• 루트 노드: 최상단 노드, 전체 데이터를 포함, 첫 번째 질문을 통한 분리하는 역할
• 결정 노드: 루트 노드 이후에 새로운 분기(질문)가 발생하는 노드
• 리프 노드: 가장 하단에 위치한 노드, 더 이상 분할이 이루어지지 않음

루트, 결정, 리프(잎) 노드

데이터 분할 시, 노드의 불순도가 낮게 나누는 것이 중요하다.
예를 들어, 데이터를 분할한 뒤에도 한 영역에 Yes, No 두 클래스가 여전히 존재한다면 불순도가 높다고 할 수 있다.

데이터 분할 예시

각 분기에서 노드 안의 데이터가 가능한 한 한쪽 클래스에 치우치도록 하는 것이 중요하다.
이러한 불순도를 측정하기 위해 지니 지수나, 엔트로피 지수 같은 지표가 활용된다.

엔트로피 지수란?

엔트로피 지수는 데이터의 무질서도인 혼란스러운 정도를 수치로 나타내는 지표이다.
0에 가까울수록 데이터가 하나의 클래스에 집중되어 있어 순도가 높고,
값이 클수록 여러 클래스가 고르게 섞여 있어 무질서한 상태를 의미한다.

엔트로피 지수 수식

수식으로는 각 클래스에 속하는 비율에 로그값을 곱해 전체를 더한 뒤에 마이너스 부호를 붙인다.

데이터를 나눠가며 순도를 높이는 과정

위 사진은 오렌지색 점선을 기준으로 두 데이터를 나눴지만
여전히 두 클래스가 섞여있는 모습이다.

점선이 없다고 생각하고 엔트로피 지수를 구한 값과,
점선으로 반으로 나눈 후에 엔트로피 지수 값을 비교하면

반으로 나눴을 때 더 낮게 나오는 걸 확인할 수 있다.
반복하여 엔트로피 지수가 가장 낮을 때로 모델을 수정하여 모델의 정확도를 높일 수 있다.

지니 지수란?

엔트로피 지수와 마찬가지로 노드 내 데이터의 혼합 정도를 나타내는 지표이다.
0과 1 사이의 값을 가지며, 0에 가까울수록 순도가 높고 1에 가까울수록 불순도가 높다.
하지만  엔트로피처럼 로그 계산을 수행하지 않아 계산 과정이 단순하다.

지니 지수 수식

각 범주에 속하는 데이터의 비율을 제곱하여 모두 더한 뒤에 그 합을 1에서 뺀 값이다.
계산이 비교적 단순하여 엔트로피 보다 실무에서 더 많이 사용된다.

가지치기란?

가지치기는 이미 완성된 풀 트리(Full Tree)에서 불필요한 가지나 노드를 제거하는 과정이다.
결정 트리는 학습 데이터를 기준으로 계속 분할을 반복해 각 노드의 불순도를 줄여나가는데
끝까지 수행하면 모든 리프노드는 하나의 클래스 데이터만 가지는 순도 100%인 풀 트리가 된다.

풀 트리는 학습데이터에는 완벽하지만 새로운 데이터에는 일반화 성능이 떨어질 수 있다.
풀 트리는 학습 데이터의 세세한 패턴까지 학습하기 때문에, 과적합이 발생할 수 있다.

과적합된 트리는 새로운 데이터가 들어왔을 때 성능이 떨어지는 단점이 있다.

이를 해결하기 위한 것이 바로 가지치기이다.
가지치기는 모델이 불필요하게 세세한 패턴까지 학습하지 않도록 트리를 단순화하는 과정이다.
이때 단순히 데이터를 버리는 과정이 아닌 적절히 결합하여 보다 단순하고 해석 가능한 구조로 만드는 과정이다.

풀 트리를 가지치기하는 과정

가지치기에는 트리가 완전히 성장하기 전에 특정 조건을 만족하면 더 이상의 분할을 허용하지 않고 해당 노드를 리프 노드로 설정하는 사전 가지치기와 트리가 풀 트리로 성장한 후에 불필요한 가지를 제거하는 방식인 사후 가지치기로 나뉜다.

사전 가지치기는 너무 일찍 분할을 멈췄을 때 발생하는 과소적합의 위험이 있고,
사후 가지치기는 일단 풀 트리로 성장해야 하기에 계산량이 많고, 시간이 오래 걸린다는 단점이 있다.

 

CART(Classification And Regression Trees) 알고리즘이란?

CART 알고리즘은 엔트로피 지수를 사용한 ID3와 C4.5 알고리즘의 한계를 보완한 것으로
오늘날의 표준적인 트리 알고리즘이다. 이름에서 알 수 있듯 분류 문제와 회귀 문제에 모두 사용가능하다.
분류 문제의 경우 분할 기준으로 지니 지수를 사용하고 이진 분할만 사용해 구조가 단순하고 계산이 빠르다.
회귀 문제의 경우에는 분할 기준으로 평균제곱오차를 사용하고 각 분할이 예측값의 변동성을 얼마나 줄이는지를 평가하여 오차가 가장 작아지는 방향으로 데이터를 나눈다.

 

ID3(Iterative Dichotomiser 3) 알고리즘

- 정보 이득을 기준으로 데이터를 분할하며, 불순도를 줄이는 방향으로 트리를 성장시킨다. 이때 엔트로피 지수를 사용한다.

여기서 정보이득이란 특정 속성이 데이터를 얼마나 잘 구분하는지를 평가하는 지표이다.
ID3는 특정 속성으로 데이터를 나누었을 때
엔트로피 지수가 얼마나 감소했는지를 계산하여 분류 기준으로 사용한다.

 

- ID3의 한계
연속형 데이터 처리(나이, 월소득, 키, 몸무게 등)와 가지치기 기능의 부재
값의 종류가 많은 속성을 선호하여 과적합 위험
=> ID3는 정보 이득이 높은 속성을 선택하기에

• 속성 A: 성별 → {남, 여} (값 2개)
• 속성 B: 학생 ID → {001, 002, 003, … 1000} (값 1000개)

위 두 속성 A, B 중 성별보다 학생 ID의 경우에서 분할 시 엔트로피 지수가 더 많이 감소한다.

이때 실제로는 학생 ID를 분류했을 때 큰 의미가 없지만, 성별에 비해 더 많이 분류하게 되기에
정보이득이 높게 나와 과적합이 발생할 수 있다는 의미이다. 

 

 

C4.5 알고리즘

- ID3의 한계를 보완하여 연속형 데이터 처리, 가지치기를 추가하고 속성 값이 많은 변수에 편향되는 문제를 해결하기 위해 정보 이득 비율을 도입한 알고리즘이다. 정보 이득 비율은 정보 이득을 해당 속성의 고유 엔트로피 지수값으로 나눠 다양한 범주를 가진 속성에 대해 과적합을 방지한다. 또한 결측값을 가진 데이터도 처리할 수 있으며 사후 가지치기 기능을 포함해 일반화 성능을 높였다.