의사 결정 나무 (Decision Tree)
06 Apr 2020 | Machine-Learning
본 포스트는 문일철 교수님의 인공지능 및 기계학습 개론 I 강의를 바탕으로 작성하였습니다. 다양한 결정 트리 알고리즘에 대한 부분은 이곳 을 참조하였습니다.
Decision Tree
규칙 기반 학습(Rule Based Learning)에서는 우리가 관측한 데이터가 완벽한 세계(Perfect)의 것임을 가정하였습니다. 하지만 우리가 살고 있는 세계는 완벽한 세계와는 너무나도 다릅니다. 일단, 모든 특성을 관측할 수 없습니다. 관측 오차도 발생하기 마련이지요. 그렇기 때문에 실제 상황에서 규칙 기반 학습을 적용하기 어렵습니다. 그렇기 때문에 다른 방법을 통해 분석을 시도해야 하는데 그 중 가장 쉬운 방법 중 하나로 의사 결정 나무(Decision Tree) 가 있습니다.
이번 게시물에서는 UCI 신용평가 데이터셋을 분석하며 의사 결정 나무에 대해서 알아보도록 합시다. 이 데이터셋에서는 총 690개의 인스턴스가 있으며 각 인스턴스는 15개의 특성을 가지고 있습니다. 아래 사진은 학습 데이터셋이 첫 번째 특성(A1) 또는 아홉 번째 특성(A9)으로 나누었을 때 각각의 결과가 어떻게 나오는지 도식화한 것이다.
이미지 출처 : 인공지능 및 기계학습 개론 학습자료
위 이미지와 같이 원래 데이터에는 Positive 레이블을 가진 인스턴스가 307개, Negative 레이블을 가진 인스턴스가 383개 포함되어 있습니다. A1특성으로 나눌 경우 왼쪽처럼 $a$ 노드에 98개의 Positive, 112개의 Negative 인스턴스가 배정되며, $b$ 노드에 206개의 Positive, 262개의 Negative 인스턴스가 배정됩니다. 그리고 어느 분류에도 속하지 않는 12개의 인스턴스가 또 다른 세 번째 노드에 배정됩니다. A9 특성으로 나눌 경우에는 오른쪽처럼 $t$ 노드에 284개의 Positive, 77개의 Negative 인스턴스가 배정되며, $f$ 노드에 23개의 Positive, 306개의 Negative 인스턴스가 배정됩니다.
Entropy & Information Gain
위와 같은 결과가 나왔다면 어떤 특성을 기준으로 나누었을 때가 더 좋은 기준이라고 할 수 있을까요? 더 좋은 분류를 평가하기 위한 수치(Metric)로 정보 엔트로피 혹은 섀넌 엔트로피(Shannon Entropy) 가 있습니다. 정보 엔트로피가 무엇인지 알기 전에 정보 이론에서 사용되는 정보량에 대해 알아봅시다. 정보량 $I$ 를 표현하는 수식은 아래와 같습니다.
\[I(X) = \log_2 \frac{1}{p(X)}\]
위 식에서 $p(X)$ 는 사건 $X$ 가 발생할 확률을 나타냅니다. 해당 수식으로부터 특정 사건이 가지고 있는 정보량은 그 사건깅 일어날 확률의 로그값에 반비례하는 것을 알 수 있습니다. 엔트로피 $H(X)$ 는 이 정보량의 평균을 나타내는 것으로 수식은 다음과 같습니다.
\[H(X) = -\sum_X P(X=x) \log_b P(X=x)\]
엔트로피는 데이터의 불확실성(Uncertainty)을 나타내므로 이 값이 높을수록 그 데이터셋이 더 불확실하다는 것을 의미합니다. 이 엔트로피 식에 조건부 확률을 적용하면 조건 엔트로피(Conditional entropy)에 대한 식이 됩니다.
\[\begin{aligned}
H(Y\vert X) &= \sum_X P(X=x) \log_b H(Y\vert X=x) \\
&= \sum_X P(X=x) \{ -\sum_Y P(Y=y\vert X=x) \log_b H(Y=y\vert X=x)\}
\end{aligned}\]
위 식을 이용하여 원래 데이터셋의 엔트로피와 이 데이터셋을 각각 A1과 A9으로 나누었을 때의 엔트로피를 계산해봅시다.
\[\begin{aligned}
H(Y) &= -\sum_{Y \in \{+,-\}} P(Y=y) \log_2 P(Y=y) = 0.991 \\
H(Y\vert A1) &= \sum_{X \in \{a,b,?\}} \sum_{Y \in \{+,-\}} P(A1= x, Y=y) \log_2 \frac {P(A1=x)}{P(A1= x, Y=y)} = 0.989 \\
H(Y\vert A9) &= \sum_{X \in \{t,f\}} \sum_{Y \in \{+,-\}} P(A9= x, Y=y) \log_2 \frac {P(A9=x)}{P(A9= x, Y=y)} = 0.566
\end{aligned}\]
이제는 정보 획득도(Information Gain, IG) 에 대해 알아봅시다. 정보 획득도는 엔트로피가 얼마나 줄어들었는 지를 나타내는 것으로 데이터셋의 불확실성이 얼마나 줄어들었는지 나타내는 수치기이도 합니다. 정보 획득도를 구하는 식은 다음과 같습니다. 아래는 이를 사용하여 각 특성으로 나누었을 때의 정보 획득도입니다.
\[\begin{aligned}
IG(Y,A_i) &= H(Y) - H(Y \vert A_i) \\
IG(Y,A_1) &= H(Y) - H(Y \vert A_1) = 0.991 - 0.989 = 0.002 \\
IG(Y,A_9) &= H(Y) - H(Y \vert A_9) = 0.991 - 0.566 = 0.425
\end{aligned}\]
A9 특성을 기준으로 나누었을 때가 A1 특성을 기준으로 나누었을 때보다 훨씬 더 높은 정보 획득도를 보이는 것을 알 수 있습니다. 이를 기준으로 노드를 나눌 때 A1보다 A9가 더 나은 특성임을 판가름하게 됩니다.
Variable Decision Tree
의사 결정 나무의 종류에도 여러가지가 있습니다.
첫 번째로 알아볼 것은 ID3(Iterative Dichotomiser 3) 입니다. 먼저 모든 인스턴스가 포함된 하나의 노드를 만듭니다. 그 다음에는 그 노드를 분류할 최적의 특성을 선택합니다. 그리고 그 특성의 클래스에 맞게 인스턴스를 분리하여 새로운 노드에 배치합니다. 한 노드에 담긴 인스턴스의 레이블이 모두 동일한 경우에 나누는 것을 종료합니다. 가장 기본적인 의사 결정 나무 알고리즘이지만, 범주형 특성만을 다룰 수 있다는 단점이 있습니다. 또한 순수한 노드가 나올 때까지 가지를 나누게 되므로 과적합(Overfitting)이 쉽게 발생하는 문제점이 있습니다.
두 번째는 ID3의 단점을 보완한 C4.5 입니다. ID3가 범주형 속성만을 다룰 수 있는데 비해 이 알고리즘은 수치형 속성까지 다룰 수 있습니다. 그리고 C4.5 알고리즘에서는 가지치기(Pruning)를 추가하여 트리가 너무 깊게 형성되는 것을 방지할 수 있습니다. 또한 결측치를 알아서 처리하고 속성마다 다른 가중치를 부여함으로서 계산을 효율적으로 진행할수 있다는 장점도 가지고 있습니다.
세 번째로 알아볼 의사 결정 나무 알고리즘은 CART(Classification And Regression Tree) 입니다. 이 알고리즘이 진행되는 방향은 ID3와 알고리즘이 진행되는 방향이 동일합니다. 차이점은 특성을 선택하는 기준에 있습니다. ID3는 특성 선택의 기준으로 엔트로피의 변화인 정보 획득도를 사용하지만 CART에서는 지니 계수(Gini Index) 라는 새로운 수치를 사용합니다. 지니 계수 $G_i$ 는 다음과 같은 수식으로 구할 수 있습니다.
\[G_i = 1 - \sum^n_{k=1} {p_{i,k}}^2\]
훈련 데이터셋을 특성 $k$ 의 임곗값인 $t_k$ 를 기준으로 두 개의 서브셋으로 나눕니다. 그리고 아래의 비용함수(Cost function)를 최소화하는 특성과 그 임곗값이 가지를 나누는 기준이 됩니다. 아래의 비용함수 식에서 $G$ 는 각 서브셋(Subset)의 불순도를, $m$은 각 서브셋의 샘플 수를 나타냅니다.
\[J(k, t_k) = \frac{m_{\text{left}}}{m}G_{\text{left}} + \frac{m_{\text{right}}}{m}G_{\text{right}}\]
CART는 다양한 XGboost 등 부스팅 알고리즘의 기본 알고리즘으로 사용되고 있습니다.
마지막으로 알아볼 알고리즘은 CHAID(Chi-squared Automatic Interaction Detection) 입니다. 이 알고리즘은 이산형 목표 변수에 대한 카이제곱( $\chi^2$ ) 검정과 연속형 목표 변수에 대한 F-검정을 이용하여 다지 분리(Multiway split)을 수행하는 알고리즘입니다. 이 두 검정에 대한 수치를 기준으로 노드를 분할합니다. 해당 수치가 임곗값보다 낮을 경우 하위 노드를 병합하는 과정을 통해 과적합을 면할 수 있다는 장점이 있습니다.
본 포스트는 문일철 교수님의 인공지능 및 기계학습 개론 I 강의를 바탕으로 작성하였습니다. 다양한 결정 트리 알고리즘에 대한 부분은 이곳 을 참조하였습니다.
Decision Tree
규칙 기반 학습(Rule Based Learning)에서는 우리가 관측한 데이터가 완벽한 세계(Perfect)의 것임을 가정하였습니다. 하지만 우리가 살고 있는 세계는 완벽한 세계와는 너무나도 다릅니다. 일단, 모든 특성을 관측할 수 없습니다. 관측 오차도 발생하기 마련이지요. 그렇기 때문에 실제 상황에서 규칙 기반 학습을 적용하기 어렵습니다. 그렇기 때문에 다른 방법을 통해 분석을 시도해야 하는데 그 중 가장 쉬운 방법 중 하나로 의사 결정 나무(Decision Tree) 가 있습니다.
이번 게시물에서는 UCI 신용평가 데이터셋을 분석하며 의사 결정 나무에 대해서 알아보도록 합시다. 이 데이터셋에서는 총 690개의 인스턴스가 있으며 각 인스턴스는 15개의 특성을 가지고 있습니다. 아래 사진은 학습 데이터셋이 첫 번째 특성(A1) 또는 아홉 번째 특성(A9)으로 나누었을 때 각각의 결과가 어떻게 나오는지 도식화한 것이다.
이미지 출처 : 인공지능 및 기계학습 개론 학습자료
위 이미지와 같이 원래 데이터에는 Positive 레이블을 가진 인스턴스가 307개, Negative 레이블을 가진 인스턴스가 383개 포함되어 있습니다. A1특성으로 나눌 경우 왼쪽처럼 $a$ 노드에 98개의 Positive, 112개의 Negative 인스턴스가 배정되며, $b$ 노드에 206개의 Positive, 262개의 Negative 인스턴스가 배정됩니다. 그리고 어느 분류에도 속하지 않는 12개의 인스턴스가 또 다른 세 번째 노드에 배정됩니다. A9 특성으로 나눌 경우에는 오른쪽처럼 $t$ 노드에 284개의 Positive, 77개의 Negative 인스턴스가 배정되며, $f$ 노드에 23개의 Positive, 306개의 Negative 인스턴스가 배정됩니다.
Entropy & Information Gain
위와 같은 결과가 나왔다면 어떤 특성을 기준으로 나누었을 때가 더 좋은 기준이라고 할 수 있을까요? 더 좋은 분류를 평가하기 위한 수치(Metric)로 정보 엔트로피 혹은 섀넌 엔트로피(Shannon Entropy) 가 있습니다. 정보 엔트로피가 무엇인지 알기 전에 정보 이론에서 사용되는 정보량에 대해 알아봅시다. 정보량 $I$ 를 표현하는 수식은 아래와 같습니다.
\[I(X) = \log_2 \frac{1}{p(X)}\]위 식에서 $p(X)$ 는 사건 $X$ 가 발생할 확률을 나타냅니다. 해당 수식으로부터 특정 사건이 가지고 있는 정보량은 그 사건깅 일어날 확률의 로그값에 반비례하는 것을 알 수 있습니다. 엔트로피 $H(X)$ 는 이 정보량의 평균을 나타내는 것으로 수식은 다음과 같습니다.
\[H(X) = -\sum_X P(X=x) \log_b P(X=x)\]엔트로피는 데이터의 불확실성(Uncertainty)을 나타내므로 이 값이 높을수록 그 데이터셋이 더 불확실하다는 것을 의미합니다. 이 엔트로피 식에 조건부 확률을 적용하면 조건 엔트로피(Conditional entropy)에 대한 식이 됩니다.
\[\begin{aligned} H(Y\vert X) &= \sum_X P(X=x) \log_b H(Y\vert X=x) \\ &= \sum_X P(X=x) \{ -\sum_Y P(Y=y\vert X=x) \log_b H(Y=y\vert X=x)\} \end{aligned}\]위 식을 이용하여 원래 데이터셋의 엔트로피와 이 데이터셋을 각각 A1과 A9으로 나누었을 때의 엔트로피를 계산해봅시다.
\[\begin{aligned} H(Y) &= -\sum_{Y \in \{+,-\}} P(Y=y) \log_2 P(Y=y) = 0.991 \\ H(Y\vert A1) &= \sum_{X \in \{a,b,?\}} \sum_{Y \in \{+,-\}} P(A1= x, Y=y) \log_2 \frac {P(A1=x)}{P(A1= x, Y=y)} = 0.989 \\ H(Y\vert A9) &= \sum_{X \in \{t,f\}} \sum_{Y \in \{+,-\}} P(A9= x, Y=y) \log_2 \frac {P(A9=x)}{P(A9= x, Y=y)} = 0.566 \end{aligned}\]이제는 정보 획득도(Information Gain, IG) 에 대해 알아봅시다. 정보 획득도는 엔트로피가 얼마나 줄어들었는 지를 나타내는 것으로 데이터셋의 불확실성이 얼마나 줄어들었는지 나타내는 수치기이도 합니다. 정보 획득도를 구하는 식은 다음과 같습니다. 아래는 이를 사용하여 각 특성으로 나누었을 때의 정보 획득도입니다.
\[\begin{aligned} IG(Y,A_i) &= H(Y) - H(Y \vert A_i) \\ IG(Y,A_1) &= H(Y) - H(Y \vert A_1) = 0.991 - 0.989 = 0.002 \\ IG(Y,A_9) &= H(Y) - H(Y \vert A_9) = 0.991 - 0.566 = 0.425 \end{aligned}\]A9 특성을 기준으로 나누었을 때가 A1 특성을 기준으로 나누었을 때보다 훨씬 더 높은 정보 획득도를 보이는 것을 알 수 있습니다. 이를 기준으로 노드를 나눌 때 A1보다 A9가 더 나은 특성임을 판가름하게 됩니다.
Variable Decision Tree
의사 결정 나무의 종류에도 여러가지가 있습니다.
첫 번째로 알아볼 것은 ID3(Iterative Dichotomiser 3) 입니다. 먼저 모든 인스턴스가 포함된 하나의 노드를 만듭니다. 그 다음에는 그 노드를 분류할 최적의 특성을 선택합니다. 그리고 그 특성의 클래스에 맞게 인스턴스를 분리하여 새로운 노드에 배치합니다. 한 노드에 담긴 인스턴스의 레이블이 모두 동일한 경우에 나누는 것을 종료합니다. 가장 기본적인 의사 결정 나무 알고리즘이지만, 범주형 특성만을 다룰 수 있다는 단점이 있습니다. 또한 순수한 노드가 나올 때까지 가지를 나누게 되므로 과적합(Overfitting)이 쉽게 발생하는 문제점이 있습니다.
두 번째는 ID3의 단점을 보완한 C4.5 입니다. ID3가 범주형 속성만을 다룰 수 있는데 비해 이 알고리즘은 수치형 속성까지 다룰 수 있습니다. 그리고 C4.5 알고리즘에서는 가지치기(Pruning)를 추가하여 트리가 너무 깊게 형성되는 것을 방지할 수 있습니다. 또한 결측치를 알아서 처리하고 속성마다 다른 가중치를 부여함으로서 계산을 효율적으로 진행할수 있다는 장점도 가지고 있습니다.
세 번째로 알아볼 의사 결정 나무 알고리즘은 CART(Classification And Regression Tree) 입니다. 이 알고리즘이 진행되는 방향은 ID3와 알고리즘이 진행되는 방향이 동일합니다. 차이점은 특성을 선택하는 기준에 있습니다. ID3는 특성 선택의 기준으로 엔트로피의 변화인 정보 획득도를 사용하지만 CART에서는 지니 계수(Gini Index) 라는 새로운 수치를 사용합니다. 지니 계수 $G_i$ 는 다음과 같은 수식으로 구할 수 있습니다.
\[G_i = 1 - \sum^n_{k=1} {p_{i,k}}^2\]훈련 데이터셋을 특성 $k$ 의 임곗값인 $t_k$ 를 기준으로 두 개의 서브셋으로 나눕니다. 그리고 아래의 비용함수(Cost function)를 최소화하는 특성과 그 임곗값이 가지를 나누는 기준이 됩니다. 아래의 비용함수 식에서 $G$ 는 각 서브셋(Subset)의 불순도를, $m$은 각 서브셋의 샘플 수를 나타냅니다.
\[J(k, t_k) = \frac{m_{\text{left}}}{m}G_{\text{left}} + \frac{m_{\text{right}}}{m}G_{\text{right}}\]CART는 다양한 XGboost 등 부스팅 알고리즘의 기본 알고리즘으로 사용되고 있습니다.
마지막으로 알아볼 알고리즘은 CHAID(Chi-squared Automatic Interaction Detection) 입니다. 이 알고리즘은 이산형 목표 변수에 대한 카이제곱( $\chi^2$ ) 검정과 연속형 목표 변수에 대한 F-검정을 이용하여 다지 분리(Multiway split)을 수행하는 알고리즘입니다. 이 두 검정에 대한 수치를 기준으로 노드를 분할합니다. 해당 수치가 임곗값보다 낮을 경우 하위 노드를 병합하는 과정을 통해 과적합을 면할 수 있다는 장점이 있습니다.
Comments