[머신러닝]비선형분류모형(상)

의사결정나무(decision tree)

의사결정나무는 비선형분류모델로 많이 사용되는 분류기 중 하나이며 데이터에 대한 분류 이유를 설명할 수 있다는 특징을 가지고 있다. 대부분의 머신러닝 모델들이 결과에 대한 해명을 하지 못한다는 사실에서 굉장한 장점이라는 것을 느낄 수 있다. 루트에서부터 리프까지 각 지점에 있는 기준에 의해 데이터가 순차적으로 분류된다. 또한 동일한 데이터 셋에 대해 여러 개의 다른 구조의 트리 모델을 학습시킬 수 있다.

---

의사결정나무 모델을 학습하는 알고리즘 중 Hunt’s algorithm은 다음과 같다. 특정 노드 A에 속해 있는 데이터들이 모두 동일한 클래스 B에 속해 있다면 노드 A는 클래스 B의 리프 노드라고 한다. 노드에 아무 데이터도 없다면 노드 A는 기본 클래스(default class)의 리프 노드라고 한다. 만약 노드에 속해 있는 데이터들이 두 가지 이상의 클래스로 분류될 수 있다면 하나의 노드에 동일한 클래스의 데이터들이 속할 수 있도록 노드를 더 작게 분할한다. 이러한 방식으로 각 노드가 특정한 클래스를 대표할 수 있도록 트리를 점진적으로 성장시켜 나가는 것이 Hunt 알고리즘이다.

---

노드를 분할하는 방식은 현재 상태에서 가장 괜찮은 분리 조건(greedy)을 하나의 입력 변수에 대해 탐색하여 시행하는 것이다. 모든 조건을 탐색하면서 트리를 구성하기에는 시간이 오래 걸리기 때문이다. 어떤 변수를 기준으로 어떤 방식으로 언제 분리할지 결정해야 한다. 분리 방식은 기준 변수의 속성에 따라 달라질 수 있다.

명목형 변수인 경우 가질 수 있는 값의 개수에 따라 일일이 분할을 하거나 어떠한 최적의 기준에 따라 두 집합으로 분할을 시도할 수 있다.

순서형 변수인 경우 가질 수 있는 값의 개수에 따라 일일이 분할을 하거나 어떠한 최적의 기준에 따라 두 집합으로 분할을 시도할 수 있다. 두 집합으로 분할을 시도할 때 하나의 집합에는 반드시 이웃하는 클래스끼리만 존재할 수 있다. 클래스의 순서를 유지해야 하기 때문이다.

연속형 변수의 경우 특정한 값을 기준으로 노드의 분할을 시도할 수 있다. 이때 하나의 값을 기준으로 잡으면 두 개의 노드로 분할되며 여러 값을 기준으로 잡으면 여러 개의 노드로 분할시킬 수 있다.

---

어떤 기준 변수를 어떠한 방식으로 분할하는 것이 좋을지 판단하기 위해서는 평가 척도가 요구된다. 의사결정트리 모델에서 각 노드의 데이터들이 균일한(homogeneous)한 클래스를 가질수록 모델의 성능이 좋아진다. 따라서 노드 내 데이터들의 클래스가 얼마나 균일한지 측정하기 위해 불순도(impurity)라는 평가 척도가 도입된다. 불순도를 측정하기 위해 여러 가지 공식이 차용될 수 있는데 대표적으로 Gini index, Entropy, Misclassification error 등이 있다. 불순도가 낮을수록 노드의 클래스가 균일하다는 것을 의미한다.

어떠한 방식의 분할이 가장 적절하다는 것을 정당화하기 위해 분할하기 전의 노드의 불순도와 분할한 후 노드의 불순도의 차이인 Gain을 비교한다. Gain이 더 클수록 분할을 통해 더 많은 클래스들을 균일하게 만들어 불순도를 낮추었다는 사실을 알 수 있다.

---

Gini index의 경우 원래는 경제적 불평등을 계수화하기 위해 사용된 지수이지만 여기서는 불순도를 측정하는 데 사용되기도 한다. 값이 낮을수록 데이터들은 하나의 클래스를 가지는 경향을 보인다. 분할 후 노드의 총 불순도를 계산할 때는 각 노드의 개별 불순도에 노드 내 데이터의 개수만큼의 가중치를 곱하여 더하는 식으로 계산한다. Count matrix를 사용하여 모든 분리 가능한 경우의 지니 계수를 측정하여 비교하는 식으로 최적의 분리 방식을 찾기 때문에 많은 시간이 걸린다. 분할된 노드 중 지니 계수가 가장 낮은 것을 선택한다.

엔트로피 평가의 경우, 지니 계수와 비슷하게 분할 후 엔트로피를 감소시켜 Gain을 커지도록 분리하는 경향이 있다. 다만, 많이 분리하여 작고 순수한 집합을 만드는 경향도 보이기도 한다.

오분류 에러의 경우도 위의 방식들과 비슷하다.

---

의사 결정 트리에 대한 학습은 한 노드 안의 데이터가 같은 클래스를 가지게 되면 종료된다. 또는 비슷한 입력 값을 가지면 종료된다. 그 이상 트리를 성장시키는 것은 학습 데이터에 대한 지나친 과적합을 유발하여 일반화 오차를 증가시키기 때문이다.

---

의사결정트리에 대해 요약하면 다음과 같다. 학습이 쉽고, 모델의 분류 속도 또한 빠르다. 또한 어떠한 분류에 대해 의사결정트리의 기준변수를 바탕으로 분류 이유를 설명할 수 있다. 이러한 의사결정트리 모델은 많은 데이터셋에 대해서 좋은 예측을 내어놓는다고 한다.

---

의사 결정 트리 모델은 한 번에 하나의 변수에 대해 데이터를 분류하기 때문에 축에 평행한 결정 경계를 그려낸다. 한 번에 여러 개의 변수를 고려하여 분리 조건을 만들어낸다면 어떠한 형태로든 결정 경계를 그려낼 수 있지만 최적의 조건인지 판별하는 데 오랜 시간이 걸리게 된다.

---

의사 결정 트리는 트리가 커질수록 학습 데이터에 대해서는 오차가 줄어들지만 일반화 오차가 커지는 과적합이 발생할 가능성도 커진다. 이러한 일반화 오차를 측정하기 위해 여러 가지 방법이 있다.

Optimistic approach는 학습 데이터에 대한 오차와 일반화 오차가 같다고 평가하는 것이다.

Pessimistic approach는 학습 데이터에 대한 오차를 이용하되 추가적인 오차를 보정한 후 좀더 비관적으로 일반화 오차를 평가하는 것이다.

Reduced error pruning(REP)는 검증 데이터 셋을 이용해 일반화 오차를 측정하는 것이다.

만약 두 가지의 의사결정 트리 모델이 동일한 일반화 오차를 가진다면 더욱 단순한 모델이 더욱 높은 평가를 받게 된다. 즉, 모델의 복잡도도 같이 평가해야만 한다.

---

의사 결정 트리의 과적합을 방지하기 위해 Pre-Pruning, Post-Pruning을 시도할 수 있다.

Pre-Pruning의 경우 위에서 설명했듯 클래스 내 데이터가 같은 클래스에 속하거나 같은 입력 변수를 가질 때 트리의 성장이 종료된다. 이외에도 추가적인 조건을 걸어 트리의 학습을 중단시킬 수 있다.

Post-Pruning의 경우 의사 결정 트리를 최대한 성장시킨 후 서브트리를 리프노드로 대체했을 때 일반화 오차가 얼마나 줄어드는지 확인하여 가지치기를 해나가는 방식이다. 이때 리프 노드는 데이터 수가 가장 많은 클래스를 노드의 클래스로 가지게 된다.