참고 문헌: 1. 서강대 AI MBA 데이터마이닝 강의교재 (2023) 2. Müller, A. C., & Guido, S. (2016). *Introduction to Machine Learning with Python*. 1st Edition. O’Reilly Media, Inc., Sebastopol, CA. ISBN: 978-1449369415.
의사결정나무는 분류/회귀에서 널리 사용되는 모델이다. 특히, 계층적으로 만약/그렇지 않으면의 질문을 학습하며 의사결정을 이끈다. 다음은 의사결정나무를 잘 보여주는 그림이다. 어릴 적 주로 했던 스무고개 퀴즈를 생각하면 쉽게 이해할 수 있을 것이다.
의사결정나무 모델 구축 의사결정나무 학습은 올바른 답에 가장 빨리 도달할 수 있는 일련의 if/else 질문들을 학습하는 과정이다. 이 질문들은 머신러닝에서 "테스트(test)"라고 불리며, 모델의 일반화 성능을 평가하는 테스트 데이터(test set)가 아닌, 의사결정나무에서 노드를 분할하는 데 사용되는 조건을 의미하며, 테스트 세트(test set)는 모델의 성능을 평가하는 데 사용되는 별도의 데이터다.
의사결정나무를 구축할 때, 알고리즘은 목표 변수를 가장 잘 분리할 수 있는 최적의 조건(테스트)을 찾는다. 예를 들면, 은행에서 고객의 대출 승인 여부를 결정하는 과정에서 의사결정나무를 사용할 수 있다. 이 경우, 고객의 정보(나이, 소득, 신용 점수 등)를 바탕으로 대출을 승인할지 여부를 결정하는 일련의 if/else 질문들로 나무를 구축할 수 있다.
예시: 대출 승인 여부 결정 -------------------------------- 1. 루트 노드 (첫 번째 질문)
질문: 고객의 신용 점수가 700 이상인가?
이 질문은 대출 승인 여부에 가장 큰 영향을 미칠 수 있는 조건으로 선택된다.
신용 점수가 700 이상이면 대출을 승인할 가능성이 높고, 그렇지 않으면 대출을 거절할 가능성이 크다.
2. 첫 번째 분할
왼쪽 노드 (신용 점수가 700 이상인 경우)
질문: 고객의 연 소득이 $50,000 이상인가?
이 두 번째 질문은 왼쪽 노드에서 대출 승인 여부를 더욱 세분화한다.
소득이 $50,000 이상이면 대출을 승인할 가능성이 높아지고, 그렇지 않으면 대출을 거절할 가능성이 있다.
오른쪽 노드 (신용 점수가 700 미만인 경우)
이 경우, 대부분 대출이 거절될 수 있다. 하지만 추가적인 질문을 통해 특정 조건을 만족하는 경우 대출을 승인할 수도 있다.
3. 두 번째 분할
왼쪽 노드 (소득이 $50,000 이상인 경우)
결론: 대출 승인.
오른쪽 노드 (소득이 $50,000 미만인 경우)
질문: 고객의 나이가 30세 이상인가?
이 질문을 통해 추가적인 세분화가 이루어진다. 나이가 30세 이상이면 대출을 승인할 가능성이 높아진다.
루트 노드로부터 두 번째 분할까지 이어지면서,
고객의 신용 점수, 소득, 나이 등의 정보를 바탕으로 고객이 대출을 받을 수 있는지 여부가 결정된다.
나무의 각 노드는 고객의 특정 특성(신용 점수, 소득 등)을 기준으로 대출 승인 여부를 분류한다.
의사결정나무 분기 방법 의사결정나무는 부모가지로부터 순수도를 증가시키는 방향으로 분기를 하며, 분기하는 방법은 다음과 같다.
범주형 변수
수치형 변수
CHAID
Chi square statistic
ANOVA F statistic
CART
Gini index
Variance reduction
C4.5
Entropy index
N/A
CART (Classification and Regression Trees) 알고리즘 설명 ART는 의사결정나무 알고리즘 중 하나로, 분류(Classification)와 회귀(Regression) 문제 모두에 사용할 수 있는 알고리즘이다. CART는 Gini 불순도를 기반으로 데이터를 분할하며, 이 알고리즘은 데이터셋을 이진 분할(Binary Splitting)하여 최적의 의사결정나무를 생성한다.
CART의 주요 특징
이진 분할:
CART는 각 분할 단계에서 데이터를 두 개의 하위 집합으로만 나누는 이진 분할 방식을 사용한다. 이 과정은 반복적으로 수행되어 최종적인 의사결정나무가 생성된다.
Gini 불순도와 엔트로피 기반의 분할:
CART는 주로 Gini 불순도를 사용하여 분할을 결정한다. Gini 불순도는 데이터가 특정 클래스에 속할 확률을 측정하는 지표로, 불순도가 낮을수록 데이터가 잘 분류된 상태를 의미한다.
Gini 불순도 Gini impurity(p)는 다음과 같이 계산된다: $\text{Gini impurity}(p) = 1 - \sum_{i=1}^{n} p_i^2$ 여기서pi는 클래스i의 확률이다.
가지치기(Pruning):
CART는 가지치기 기법을 사용하여 나무의 복잡성을 조절하고, 과적합을 방지한다. 가지치기는 필요 없는 분기를 제거하여 나무를 단순화하는 과정이다.
회귀 트리:
CART는 회귀 문제에서도 사용할 수 있으며, 이 경우 트리의 각 노드는 특정 값의 평균을 예측하는 데 사용된다.
불균형 데이터 처리:
CART는 클래스가 불균형한 데이터셋에서도 효과적으로 사용할 수 있다.
C4.5 알고리즘 설명
C4.5는 머신 러닝과 데이터 마이닝에서 사용되는 의사결정나무 알고리즘 중 하나로, 엔트로피를 기반으로 분기를 수행한다. 이 알고리즘은 J. Ross Quinlan이 개발했으며, ID3 알고리즘의 개선된 버전이다. C4.5는 주로 분류 문제를 해결하는 데 사용되며, 여러 가지 중요한 특징을 가지고 있다.
C4.5의 주요 특징
1. 엔트로피와 정보 이득(Information Gain) 기반의 분할: - C4.5는 각 특성에 대해 엔트로피를 계산하고, 이를 바탕으로 정보 이득(Information Gain)을 구해 데이터셋을 분할한다. 정보 이득은 특성이 데이터를 얼마나 잘 분류할 수 있는지를 측정하며, 정보 이득이 가장 큰 특성을 선택해 분할을 수행한다.
2. 연속형 속성 처리: - C4.5는 연속형 데이터(숫자형 데이터)도 처리할 수 있다. 연속형 속성에 대해서는 가능한 모든 분할점을 고려해 최적의 분할점을 찾는다.
3. 결측치 처리: - C4.5는 결측치를 효과적으로 처리해, 결측된 데이터를 활용하여 모델을 구축할 수 있다.
4. 가지치기(Pruning): - C4.5는 의사결정나무가 너무 복잡해지지 않도록 가지치기(pruning)를 수행하여 불필요한 노드를 제거한다. 이를 통해 과적합을 방지한다.
5. 다양한 클래스 처리: - C4.5는 다중 클래스 분류 문제에서도 효과적으로 사용할 수 있다.
C4.5의 작동 방식
1. 엔트로피 계산: - 각 특성에 대해 엔트로피를 계산한다. 엔트로피는 데이터의 불확실성을 측정하며, 엔트로피가 낮을수록 데이터가 잘 분류된 상태를 의미한다.
- 엔트로피 \( H(S) \)는 다음과 같이 계산된다: \[ H(S) = -\sum_{i=1}^{n} p_i \log_2 p_i \] 여기서 \( p_i \)는 클래스 \( i \)의 확률이다.
2. 정보 이득 계산: - 각 특성에 대해 정보 이득을 계산한다. 정보 이득은 특성을 사용해 데이터를 분할한 후의 엔트로피 감소량을 의미한다.
- 정보 이득은 다음과 같이 계산된다: \[ \text{Information Gain} = H(S) - \sum_{i=1}^{n} \frac{|S_i|}{|S|} H(S_i) \] 여기서 \( H(S) \)는 전체 데이터의 엔트로피, \( S_i \)는 분할된 데이터의 부분집합, \( |S_i| \)는 부분집합의 크기이다.
3. 최적의 분할: - 정보 이득이 가장 큰 특성을 선택해 데이터를 분할한다. - 이 과정을 반복하여 각 노드에서 최적의 분할을 수행해 의사결정나무를 구축한다.
4. 가지치기: - 의사결정나무가 너무 복잡해지는 것을 방지하기 위해 가지치기를 수행해 불필요한 분기를 제거한다.
C4.5의 예
예를 들어, 주어진 데이터셋에서 특정한 속성들(예: 날씨, 온도, 습도 등)을 기반으로 사람들의 활동(예: 운동 여부)을 예측하는 문제를 해결한다고 가정하자. C4.5는 각 특성에 대해 정보 이득을 계산하고, 정보 이득이 가장 큰 특성을 선택해 데이터를 분할한다. 이 과정을 반복해 최종적으로 의사결정나무를 생성하며, 이 나무는 새로운 데이터에 대해 그 사람의 활동을 예측하는 데 사용된다.
C4.5는 엔트로피와 정보 이득을 기반으로 데이터셋을 효과적으로 분류하는 강력한 알고리즘으로, 많은 분류 문제에서 사용된다.
CHAID는 명목형 데이터를 처리하는 데 주로 사용되는 의사결정나무 알고리즘이다. CHAID는 카이제곱(Chi-square) 통계량을 기반으로 데이터를 분할하며, 이 통계량을 통해 각 분할이 얼마나 통계적으로 유의미한지를 평가한다. CHAID는 여러 가지 중요한 특징을 가지고 있다.
카이제곱 통계량 기반의 분할:
CHAID는 각 특성에 대해 카이제곱 통계량을 계산하고, 이를 기반으로 데이터를 분할한다. 카이제곱 통계량이 높을수록 해당 특성과 타겟 변수 간의 관계가 강하다고 판단하며, 이를 바탕으로 최적의 분할을 수행한다.
카이제곱 통계량χ2는 다음과 같이 계산된다: $\chi^2 = \sum_{i=1}^{n} \frac{(O_i - E_i)^2}{E_i}$ 여기서 Oi는 관측된 빈도, Ei는 기대 빈도를 의미한다.
다중 분할:
CHAID는 한 번의 단계에서 여러 그룹으로 분할할 수 있으며, 이는 데이터의 복잡성을 효과적으로 반영하는 데 도움이 된다.
연속형 데이터의 이산화:
CHAID는 연속형 데이터를 이산화하여 처리할 수 있으며, 각 분할에 대해 카이제곱 검정을 수행하여 최적의 이산화 기준을 선택한다.
가지치기(Pruning):
CHAID는 과적합을 방지하기 위해 가지치기를 수행하여 불필요한 분기를 제거한다.
다중 클래스 처리:
CHAID는 다중 클래스 분류 문제에서도 효과적으로 사용할 수 있다.
CHAID의 예 예를 들어, 특정 제품의 구매 여부를 예측하는 문제에서 CHAID는 고객의 연령, 성별, 소득 수준과 같은 특성을 분석하여 구매 여부를 분류할 수 있다. CHAID는 카이제곱 통계량을 기반으로 최적의 특성을 선택하고, 이를 바탕으로 데이터를 여러 그룹으로 나눠 최종적인 의사결정나무를 생성한다.
CHAID, C4.5, CART 알고리즘 정리
- CHAID: 주로 범주형 데이터를 처리하는 데 사용되며, 카이제곱(Chi-square) 통계량을 기반으로 분할을 수행한다. 연속형 데이터를 사용할 경우 이산화하여 처리한다.
- C4.5: 범주형 데이터와 연속형 데이터 모두를 처리할 수 있는 알고리즘이다. 연속형 데이터의 경우 가능한 모든 분할점을 고려해 최적의 분할을 선택한다. 엔트로피(Entropy)와 정보 이득(Information Gain)을 기반으로 데이터를 분할한다.
- CART: 범주형 데이터와 연속형 데이터 모두를 처리할 수 있으며, 주로 Gini 불순도를 기준으로 데이터를 이진 분할한다. 분류와 회귀 문제 모두에 사용할 수 있는 알고리즘이다.
범주형 알고리즘 예제
1. CHAID 알고리즘 예제
CHAID는 주로 카이제곱 통계량을 기반으로 분할을 수행한다. 예를 들어, 고객의 성별(남성, 여성)과 제품 구매 여부(구매, 미구매)를 분석한다고 가정해보자.
X축: 성별 (남성, 여성) Y축: 구매 여부 (구매, 미구매) 카이제곱 통계량을 사용하여 성별과 구매 여부 간의 관계를 분석하고, 두 변수 간의 유의미한 차이가 있는지 검정한다. CHAID는 유의미한 차이가 있을 경우, 성별을 기준으로 데이터를 분할한다.
C4.5는 정보 이득을 기반으로 데이터를 분할한다. 예를 들어, 날씨(맑음, 흐림, 비)와 운동 여부(운동함, 운동하지 않음)를 분석한다고 가정해보자.
위 그림은 C4.5 알고리즘 예시로, 날씨 조건(맑음, 흐림, 비)에 따른 운동 여부(운동함, 운동하지 않음)를 나타낸 바 그래프입니다. 초록색 막대는 운동한 사람들의 수를, 빨간색 막대는 운동하지 않은 사람들의 수를 나타냅니다. C4.5는 각 날씨 조건에 대해 정보 이득을 계산한다. 예를 들어, 맑은 날의 엔트로피를 계산하여 분할 전후의 정보 이득을 구한다.
CART 알고리즘은 Gini 불순도를 최소화하는 방향으로 데이터를 분할합니다. 위 계산 결과에 따르면, Gini 불순도가 가장 낮은 20대에서 분할하는 것이 바람직합니다. 이로 인해 Gini 불순도를 줄이는 방향으로 나이대를 기준으로 데이터를 분할할 수 있습니다.
의사결정나무의 구성 요소
Root Node (루트 노드):
전체 인구 또는 샘플을 나타내며, 이후 두 개 이상의 동질적인 집합으로 분할된다.
Splitting (분할):
노드를 여러 하위 노드로 분리하는 과정이다.
Decision Node (의사결정 노드):
하위 노드로 나뉘어진 노드는 의사결정 노드가 된다.
Leaf or Terminal Nodes (말단 또는 종단 노드):
더 이상 분할되지 않는 노드들로, 최종적인 예측 결과를 나타낸다.
Pruning (가지치기):
의사결정 노드에서 하위 노드를 제거하는 과정으로, 역분할이라고도 할 수 있다.
Branch or Sub-Tree (가지 또는 서브 트리):
전체 트리의 분할된 부분이다.
Parent and Child Node (부모 노드와 자식 노드):
하위 노드로 나뉘는 노드를 부모 노드라고 하며, 하위 노드들은 자식 노드다.
의사결정나무 장단점 장점:
해석이 용이함:
의사결정나무는 직관적이고 시각적이어서, 비전문가도 쉽게 이해할 수 있다.
비선형 데이터 처리 가능:
데이터의 비선형적 관계를 잘 처리할 수 있다.
특성 선택:
데이터에서 가장 중요한 특성들을 자동으로 선택하여 사용된다.
명확한 규칙:
생성된 트리는 명확한 규칙 집합으로 해석할 수 있다.
단점:
과적합 가능성:
트리가 너무 깊어지면 과적합의 위험이 있습니다. 이는 가지치기를 통해 완화할 수 있다.
변동성:
데이터의 작은 변화에도 트리의 구조가 크게 바뀔 수 있다.
복잡한 모델:
매우 큰 트리는 해석이 어려울 수 있으며, 계산 복잡도가 증가한다.
<추가>
의사결정나무가 이상치에 민감하지 않다는 점과 데이터의 작은 변화에 트리 구조가 크게 바뀔 수 있다는 점은 서로 다른 맥락에서 이해해야 한다.
- 이상치에 민감하지 않음 의사결정나무는 분할할 때 평균이나 표준편차와 같은 통계적 척도를 사용하지 않고, 데이터의 특정 임계값을 기준으로 분할한다. 즉, 데이터의 순위나 특정 값에 따라 분할을 진행하기 때문에, 일반적인 통계 모델들에 비해 이상치(outlier)에 덜 민감하다. 이는 의사결정나무가 이상치에 의해 큰 영향을 받지 않는다는 것을 의미한다.
- 데이터의 작은 변화에 민감함 반면에, 데이터의 작은 변화에도 트리 구조가 크게 바뀔 수 있다는 것은 다음과 같은 이유에서 발생한다:
1. 임계값 변화: - 의사결정나무는 데이터를 분할할 때 특정 임계값을 기준으로 분할한다. 데이터에 약간의 변화가 생겨 이 임계값이 바뀌게 되면, 트리의 분할 구조가 달라질 수 있다.
2. 초기 분할의 중요성: - 의사결정나무는 각 분할 단계에서 가장 큰 정보 이득을 제공하는 특성과 임계값을 선택한다. 초기 분할이 전체 트리의 구조에 큰 영향을 미치기 때문에, 초기 데이터에 약간의 변화가 발생하면 전체 트리의 구조가 크게 변할 수 있다.
3. 다중 분할 후보: - 여러 개의 분할 후보가 비슷한 정보 이득을 제공할 경우, 데이터의 작은 변화가 트리에서 어느 분할이 선택될지를 결정하게 된다. 이로 인해 트리의 최종 구조가 달라질 수 있다.
따라서, 의사결정나무는 이상치에 민감하지 않지만, 데이터의 작은 변화에 의해 트리의 구조가 크게 변할 수 있는 점은 알고리즘의 특성상 발생할 수 있는 단점으로 볼 수 있다. 이는 특히 데이터 샘플링이 자주 일어나거나, 데이터셋이 작을 때 더 두드러질 수 있는 문제다. 이런 변동성을 줄이기 위해서는 여러 번의 트리 생성과 결과의 앙상블(예: 랜덤 포레스트) 기법이 사용되기도 한다.
