[단단한 머신러닝] Ch 4 - 의사결정 트리

 

 

의사결정 트리(decision tree)는 머신러닝 학습법 중 하나로, 우리가 흔히 알고 있는 수형도라고 생각하면 좋다. 

책에서는 계속 예시로 이용하던 '수박'으로 내용을 진행했다. '잘 익은 수박'은 양성 클래스, 아니면 음성 클래스로 분류했다. 

의사결정 트리는 하나의 루트 노드(root node)와 여러 개의 리프 노드(leaf node / terminal noe)로 구성된다. 수형도처럼 하나의 속성 테스트 결과에 따라 하위 노드로 분류되는 과정이다. 기본 과정을 간단하게 나타내면

 

1. 해당 노드에 포함된 샘플(훈련 세트에서 나온 것)이 모두 같은 클래스에 속하면, 분할 더 이상 진행하지 않음.
2. 해당 속성 집합이 0(공집합), 즉 모든 샘플들의 속성이 전부 같으면, 분할 더 이상 진행하지 않음. = 리프 노드로 판단 / 사후 분포 사용.
3. 해당 노드에 해당하는 샘플의 집합이 0(공집합)이면, 분할 더 이상 진행하지 않음. = 리프노드로 판단. 상위 부모 노드의 하위 노드의 샘플들 중에 다수가 속한 클래스로 정의. / 사전 분포 사용. 

---

분할 선택 / 노드 정하기

중요한 부분은 어떤 속성을 노드로 설정할 것인가에 대한 문제이다. 각 노드의 샘플들은 최대한 같은 클래스에 속하기를 원하며, 즉, 순도가 높게끔 원한다.

 

순도를 결정하는 지표로 대표적으로 정보 엔트로피(Information Entropy)가 있다. 샘플 집합 D의 k번째 클래스 샘플이 차지하는 비율 \(p_k\)라 하면, 정보 엔트로피는 다음과 같다. \[ Ent(D) = - \sum_{k=0}^{\left| Y \right|} p_k log_{2} p_k \]

여기서 Y는 나눠지는 비율 갯수를 의미한다. \(Ent(D)\)의 값이 작을수록 D의 순도는 높다.

샘플 수가 많은 노드의 영향이 크게 하기 위해 가중치를 해당 노드(훈련 세트 집합 D에서 속성 \(a\)에서 속성 \(a^{v}\) 값을 가진 샘플을 모두 가진 집합 세트 \(D^{v}\)에 부여한다. 이를 이용해 정보 이득(Information gain)의 식을 다음과 같이 얻을 수 있다. \[ Gain(D, a) = Ent(D) - \sum_{v=0}^{|V|} \frac {\left| D^{v} \right|} {\left| D \right|} Ent(D^{v}) \]

루트 노드의 정보 엔트로피를 구한 후 속성 집합의 각 속성들의 정보 이득을 계산해서, 리프 노드들을 결정한다. 예시로, 루트 노드의 정보 엔트로피는 잘 익은 수박인가(양성), 아닌가(음성)으로 판단하고, 속성 집합들의 예시로 색깔, 줄무늬, 꼬리 형상 등의 정보 이득을 계산하여 가장 높은 정보 이득으로 처음 분할을 진행한다. 

 

정보 이득율로 각 속성의 비율을 알 수 있다.

\[ IV(a) = - sum_{v=1}^{V} \frac{\left| D^{v} \right|}{\left| D \right|} log_{2} \frac{\left| D^{v} \right|}{\left| D \right|} \]

\[ Gain_ratio(D, a) = \frac {Gain(D, a)} {IV(a)} \]

 

의사결정 트리 C4.5(ver이름) 알고리즘은 휴리스틱 방법을 활용해서 분할 속성 후보 중 정보 이득이 평균 수준보다 높은 속성에서 이득율이 가장 높은 것을 선택한다.

 

CART 의사결정 트리는 지니계수(Gini index)를 사용해 데이터 세트의 순도를 파악하기도 한다.

---

가지치기

일전에 언급한 사전 분포, 사후 분포가 각각 사전 가지치기와 사후 가지치기와 관련 있다. 우선 첫 번째로 정보 이득 규칙으로 의사결정 트리 초안을 완성한다. 이후 일반화 성능을 높이기 위해 사전 가지치기와 사후 가지치기를 진행한다.

 

사전 가지치기는 간단히 얘기하면, 루트 노드의 각 리프 노드로 분할 했을 때 다음 리프노드로 분할 전과 후의 검정 정확도를 파악한다. 분할 전이 분할 후보다 정확도가 높으면 분할을 더 이상 진행하지 않고, 특별이 1층의 분할만 진행된 의사결정 트리를 의사결정 그루터기라고 한다.

 

사후 가지치기는 반대로 가장 마지막 리프 노드에서의 검정도와 그 상위 리프 노드만 남긴 분할을 진행하지 않은 것을 비교하여 검정도가 더 높을 때를 선택하는 방법이다. 

---

연속 속성일 때의 의사결정 트리

연속 속성일 경우, 속성 n개가 있을 때 각 속성을 오름차순으로 줄 지어 놓고,  i번째 속성과 i+1 번째 속성의 중앙값을 후보 분할점으로 선택한다. (i는 1 이상 n-1 이하의 값)

---

결측값 처리

각 데이터의 모든 속성이 다 있지 않은 경우가 많다. 이 경우

1. 결실된 속성들이 있는 상황에서 어떤 속성을 기준으로 분할을 진행할 것인가?
2. 정했을 때 어떤 샘플들 경우 그 속성이 결측되어 있으면 이를 어떻게 분할할 것인가?

이는 무결측값 샘플이 차지하는 비율(\(\rho\)), 무결측값 샘플에서 k번째 클라스가 차지하는 비율((\p_k\)), 무결측값 샘플 중 속성 \(a ~ a^{v}\) 값을 취할 수 있는 샘플이 차지하는 비율(\(\tilde{r}_v\)이 세 가중치를 각각 계산한다.

\[Gain(D, a) = \rho \times Gain(\tilde{D}_v) = \rho \times (Ent(\tilde{D}) - \sum_{v=1}^{V} \tilde{r}_v Ent(\tilde{D}^{v}) \]

---

다변량 의사결정 트리와 단변량 의사결정 트리 차이점

이 의사결정 트리를 하나의 좌표에 나타내면, 속성이 하나의 차원을 담당한다면, d개의 속성은 d차원 공간이다. 의사결정 트리의 분류 경계는 x축에 평행하다. 다변량 의사결정 트리는 양성 클래스, 음성 클래스를 대각선 분할을 통해 더 복잡한 의사결정 트리를 만들 수 있다. 단변량 의사결정 트리는 앞서 우리가 본 의사결정 트리와 같아 최적의 분할 속성을 찾는 것이지만, 다변량 의사결정 트리는 기하학적으로 이를 좌표로 나타낸 것으로 보면 된다.