핸즈온 머신러닝 정리 - 6장

결정트리

SVM처럼 결정 트리는 분류와 회귀 작업 그리고 다중출력 작업도 가능한 다재다능한 머신러닝 알고리즘입니다. 또한 매우 복잡한 데이터셋도 학습할 수 있는 강력한 알고리즘입니다.

결정 트리는 최근에 자주 사용되는 가장 강력한 머신러닝 알고리즘 중 하나인 랜덤 포레스트의 기본 구성 요소이기도 합니다.

클래스 확률 추정

결정 트리는 한 샘플이 특정 클래스 k에 속할 확률을 추정할 수도 있습니다. 먼저 이 샘플에 대해 리프 노드를 찾기 위해 트리를 탐색하고 그 노드에 있는 클래스 k의 훈련 샘플의 비율을 반환합니다.

CRAT 훈련 알고리즘

이 알고리즘의 아이디어는 매우 간단합니다. 먼저 훈련 세트를 하나의 특성 k의 임계값 t_k를 사용해 두 개의 서브셋으로 나눕니다. 이 알고리즘이 최소화해야 하는 비용 함수는 아래와 같습니다.

\[J(k,t_k)=\frac {m_{left}} mG_{left}+\frac {m_{right}} mG_{right}\\ G는\,왼쪽/오른쪽\,서브셋의\,불순도\\ m은\,왼쪽/오른쪽\,서브셋의\,샘플\,수\]

훈련 세트를 성공적으로 둘로 나누었다면 같은 방식으로 서브셋을 또 나누고 그다음엔 서브셋의 서브셋을 나누고 이런 식으로 계속 반복합니다. 이 과정은 최대 깊이가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 때 멈추게 됩니다.

계산 복잡도

예측을 하려면 결정 트리를 루트 노드에서부터 리프 노드까지 탐색해야 합니다. 일반적으로 결정트리는 거의 균형을 이루고 있으므로 결정 트리를 탐색하기 위해서는 약 O(log₂(m))개의 노드를 거쳐야 합니다. 각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도는 특성 수와 무관하게 O(log₂(m))입니다. 그래서 큰 훈련 세트를 다룰 때도 예측 속도가 매우 빠릅니다.

그러나 훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교합니다. 그래서 훈련 복잡도는 O(n x mlog(m))이 됩니다.

지니 불순도 또는 엔트로피?

기본적으로 지니 불순도가 사용되지만 criterion 매개변수를 “entropy”로 지정하여 엔트로피 불순도를 사용할 수 있습니다. 지니 불순도와 엔트로피 중 어떤 것을 사용해야 할까요? 실제로는 큰 차이가 없습니다. 즉, 둘 다 비슷한 트리를 만들어냅니다. 지니 불순도가 조금 더 계산이 빠르기 때문에 기본값으로 좋습니다. 그러나 다른 트리가 만들어지는 경우 지니 불순도가 가장 빈도 높은 클래스를 한쪽 가지로 고립시키는 경향이 있는 반면 엔트로피는 조금 더 균형 잡힌 트리를 만듭니다.

규제 매개변수

결정 트리는 훈련 데이터에 대한 제약사항이 거의 없습니다. 제한을 두지 않으면 트리가 훈련 데이터에 아주 가깝게 맞추려고 해서 대부분 과대적합되기 쉽습니다. 결정 트리는 모델 파라미터가 전혀 없는 것이 아니라 훈련되기 전에 파라미터 수가 결정되지 않기 때문에 이런 모델을 비파라미터 모델이라고 부르곤 합니다.

결정 트리의 최대 깊으는 제어할 수 있습니다. max_depth를 줄이면 모델을 규제하게 되고 과대적합의 위험이 감소합니다. DecisionTreeClassifier에는 결정 트리의 형태를 제한하는 매개변수가 몇 개 있습니다. min으로 시작되는 매개변수를 증가시키거나 max로 시작하는 매개변수를 감소시키면 모델의 규제가 커집니다.

회귀

결정 트리는 회귀 문제에도 사용할 수 있습니다. 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측합니다. CART 알고리즘은 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신 평균제곱오차를 최소화하도록 분할하는 것을 제외하고는 앞서 설명한 것과 거의 비슷하게 작동합니다.

불안정성

결정 트리는 계단 모양의 결정 경계를 만듭니다. 그래서 훈련 세트의 회전에 민감합니다. 이런 문제를 해결하는 한 가지 방법은 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA 기법을 사용하는 것입니다.

결정 트리의 주된 문제는 훈련 데이터에 있는 작은 변화에도 매우 민감하다는 것입니다. 다음 장에서 보게 될 랜덤 포레스트는 많은 트리에서 만든 예측을 평균하여 이런 불안정성을 극복할 수 있습니다.

연습문제

1. 백만 개의 샘플을 가진 훈련 세트에서 (규제 없이) 훈련시킨 결정 트리의 깊이는 대략 얼마일까요?

   m개의 리프 노드를 포함한 균형이 잘 잡힌 이진 트리의 깊이는 log₂(m)을 반올림한 것과 같습니다. 이진 결정 트리를 제한을 두지 않고 훈련시키면 훈련 샘플마다 하나의 리프 노드가 되므로 어느 정도 균형이 잘 잡힌 트리가 됩니다. 따라서 훈련 세트에 백만 개 샘플이 있다면 결정 트리의 깊이는 log₂(10⁶)=20이 될 것입니다.

2. 한 노드의 지니 불순도가 보통 그 부모 노드보다 작을까요, 아니면 클까요? 일반적으로 작거나 클까요, 아니면 항상 작거나 클까요?

   한 노드의 지니 불순도는 일반적으로 부모의 불순도보다 낮습니다. 이는 자식의 지니 불순도의 가중치 합이 최소화되는 방향으로 각 노드를 분할하는 CART 훈련 알고리즘의 비용 함수 때문입니다. 그러나 다른 자식 노드의 지니 불순도 감소량이 어떤 노드의 불순도 증가량보다 큰 경우라면 부모의 불순도보다 큰 노드가 생길 수 있습니다.

3. 결정 트리가 훈련 세트에 과대적합되었다면 max_depth를 줄이는 것이 좋을까요?

   결정 트리가 훈련 세트에 과대적합되었다면 모델에 제약을 가해 규제해야 하므로 max_depth를 낮추는 것이 좋습니다.

4. 결정 트리가 훈련 세트에 과소적합되었다면 입력 특성의 스케일을 조정하는 것이 좋을까요?

   결정 트리는 훈련 데이터의 스케일이나 원점에 맞추어져 있는지 상관하지 않습니다. 이것이 결정 트리의 장점 중 하나입니다. 그러므로 결정 트리가 훈련 세트에 과소적합되었다고 입력 특성의 스케일을 조정하는 것은 시간 낭비입니다.

5. 백만 개의 샘플을 가진 훈련 세트에 결정 트리를 훈련시키는 데 한 시간이 걸렸다면, 천만 개의 샘플을 가진 훈련 세트에 결정 트리를 훈련시키는 데는 대략 얼마나 걸릴까요?

   결정 트리 훈련의 계산 복잡도는 O(n x mlog(m))입니다. 그러므로 훈련 세트의 크기에 10을 곱하면 훈련 시간은 K = O(n x 10m x log(m))/(n x m x log(m)) = 10 x log(10m) / log(m)배 늘어납니다. 만약 m=10⁶이면 K=11.7이므로 훈련에 대략 11.7시간이 걸릴것으로 예상할 수 있습니다.

6. 십만 개의 샘플을 가진 훈련 세트가 있다면 presort=True로 지정하는 것이 훈련 속도를 높일까요?

   데이터셋의 샘플 수가 수천 개 미만일 때 훈련 세트를 사전에 정렬하여 훈련 속도를 높일 수 있습니다. 100,000개의 샘플을 포함하고 있을 때 presort=True로 지정하면 훈련 속도가 매우 느려질 것입니다.