핸즈온 머신러닝 2 복습하기(챕터 6: 결정 트리)

 

CH 6. 결정 트리

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

6.1 결정 트리 학습과 시각화 

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
iris = load_iris()
X = iris.data[:, 2:] # 꽃잎 길이와 너비
y = iris.target

tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X, y)

from sklearn.tree import export_graphviz

export_graphviz(tree_clf, out_file=image_path('iris_tree.dot'),
                feature_names=iris.feature_names[2:],
                class_names=iris.target_names,
                rounded=True, filled=True)

6.2 예측하기

루트 노드(root node): 깊이가 0인 맨 꼭대기의 노드
리프 노드(leaf node): 자식 노드를 가지지 않는 노드
sample 속성: 얼마나 많은 훈련 샘플이 적용되었는지 카운팅
value 속성: 노드에서 각 클래스에 얼마나 많은 훈련 샘플이 있는지 표현
gini 속성: 불순도(impurity) 측정 

한 노드의 모든 샘플이 같은 클래스에 속해 있다면 이 노드를 순수(gini=0)하다고 한다. 반대로 우리의 직관과 달리, 샘플이 각 클래스에 고르게 분포한다면 불순도가 가장 높을 것이다. 지니 불순도 수식은 아래와 같다.

$G_i=1-\sum_{k=1}^n p_{i,k}^2$

$p_{i,k}^2$ 는 i 번째 노드에 있는 훈련 샘플 중 클래스 k에 속한 샘플의 비율이다. n은 클래스 개수로 위에선 setosa, versicolor, virginica 총 3개이다. 

지니 불순도 이외에도 criterion 매개변수를 "entropy"로 지정하여 엔트로피 불순도를 사용할 수 있다. 엔트로피는 분자의 무질서함을 측정하는 것으로 원래 열역학의 개념이다. 분자가 안정되고 질서 정연하면 엔트로피가 0에 가깝다. 즉 한 노드에서 한 클래스의 샘플만 담고 있다면 엔트로피가 0이 된다. 엔트로피 불순도 수식은 아래와 같다.

$H_i=-\sum_{k=1}^n p_{i,k}log_2(p_{i,k})$

$p_{i,k}\neq0$

지니 불순도나 엔트로피는 큰 차이가 없다. 그래도 차이를 살펴본다면, 지니 불순도가 조금 더 계산이 빨라 기본값으로 좋다. 하지만 다른 트리가 만들어지는 경우 지니 불순도가 가장 빈도 높은 클래스를 한쪽 가지(branch)로 고립시키는 경향이 있는 반면, 엔트로피는 조금 더 균형 잡힌 트리를 만든다고 한다.

참고:
결정 트리는 직관적이고 결정 방식을 이해하기 쉬워 화이트박스(white box) 모델이라고 한다. 이후 설명할 랜덤 포레스트나 신경망은 블랙박스(black box) 모델이다. 

6.3 클래스 확률 추정

결정 트리는 한 샘플이 특정 클래스 k에 속할 확률도 추정할 수 있다. 예를 들어, 길이가 5cm이고 너비가 1.5cm인 꽃잎은 위 그림에서 초록색 리프 노드에 해당하며 이때 꽃잎이 setosa, versicolor, virginica 중 어디에 속할지 확률을 출력한다. setosa는 0%(0/54), versicolor는 90.7%(49/54), virginica는 9.3%(5/54)이다. 

tree_clf.predict_proba([[5, 1.5]])
>>> array([[0., 0.90740741, 0.09259259]])
tree_clf.predict([[5, 1.5]])
>>> array([1])

6.4 CART 훈련 알고리즘

사이킷런은 결정 트리를 훈련시키기 위해 CART(classification and regression tree) 알고리즘을 사용한다. 먼저 훈련 세트를 하나의 특성 k의 임곗값 $t_k$를 사용해 두 개의 서브셋으로 나눈다. 그렇다면 어떻게 k와 $t_k$를 선택할까? 이때 (크기에 따른 가중치가 적용된) 가장 순수한 서브셋으로 나눌 수 있는 (k, $t_k$) 짝을 찾는다. 수식은 아래와 같다.

$J(k, t_k)$=${m_l \over m} G_l + {m_r \over m} G_r$

$G_{l/r}$ : 왼쪽/오른쪽 서브셋의 불순도
$m_{l/r}$ : 왼쪽/오른쪽 서브셋의 샘플 수

CART 알고리즘이 훈련 세트를 성공적으로 둘로 나누었다면 같은 방식으로 서브셋을 또 나누고 그 다음 서브셋의 서브셋을 나누고 이런 식으로 계속 반복한다. 이를 재귀적 분할(Recrusive Partitioning)이라고 하며, 탐욕적 알고리즘(greedy algorithm)의 일부이다. 탐욕적 알고리즘의 최종 결과는 "최적(best)"임을 보장하진 못하나 그래도 계산 시간을 많이 줄여주고, 성능 역시 보장된다.

6.5 계산 복잡도

예측을 하려면 결정 트리는 루트 노드에서부터 리프 노드까지 탐색해야 한다. 일반적으로 결정 트리를 탐색하기 위해선 약 $O(log_2(m))$개의 노드를 거쳐야 한다. 각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도는 특성 수와 상관없이 $O(log_2(m))$이다.

반면, 훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교하기 때문에 훈련 복잡도는 $O(n x mlog_2(m))$이다. 

6.6 규제 매개변수

결정 트리는 훈련 데이터에 대한 제약 사항이 거의 없다. 훈련되기 전에 파라미터 수가 결정되지 않기 때문에 이를 비파라미터 모델(nonparametric model)이라고 부른다. 반대로 선형 모델은 데이터가 선형일 것이라 가정한다. 따라서 결정 트리의 경우, 제한을 두지 않으면 훈련 데이터에 아주 가깝게 맞추려고 해서 대부분 과대적합되기 쉽다. DecisionTreeClassifier에는 결정 트리 형태를 제한하는 여러 매개변수가 있다. 

max_depth: 결정 트리 깊이
min_samples_split: 노드가 가져야 하는 최소 샘플 수
min_samples_leaf: 리프 노드가 가져야할 최소 샘플 수
min_weight_fraction_leaf: min_samples_leaf와 같지만 가중치가 부여된 전체 샘플 수에서의 비율
max_leaf_nodes: 리프 노드 최대 수
max_features: 각 노드에서 분할에 사용할 특성의 최대 수

min_으로 시작하는 매개변수를 증가시키거나 max_로 시작하는 매개변수를 감소시키면 모델 규제가 커져 과대적합을 방지할 수 있다. 

이외에 제한 없이 결정 트리를 훈련시키고 불필요한 노드를 가지치기(pruning)하는 알고리즘도 있다. 순도를 높이는 것이 통계적으로 큰 효과가 없다면 리프 노드 바로 위의 노드는 불필요할 수 있다. 대표적으로 카이스퀘어 검정(chi-squared test)과 같은 통계적 검정을 사용하여 우연히 향상된 것인지 추정한다. 이 확률을 p-값(p-value)이라 부르며 어떤 임곗값보다 높으면 그 노드는 불필요한 것으로 간주되고 그 자식 노드는 삭제된다.

참고:
카이스퀘어 검정은 범주(category)별로 관측된 빈도와 기대빈도의 차이를 봄으로써 데이터가 클래스별로 균등하게 분산되어 있는지 파악한다. 이때 귀무가설(H0)은 '클래스 간 데이터가 균등하게 분산되어 있다', 대립가설(H1)은 '균등하게 분산되어 있지 않다' 이다. p-값은 귀무가설이 기각될 확률을 나타내는 것으로, 작으면 작을수록 통계적으로 유의하다고 본다. 임곗값보다 크면 귀무가설이 기각되지 않으며, 불순도 변화는 우연히 향상된 것으로 보기 때문에 삭제된다. 

6.7 회귀

결정 트리는 회귀 문제에도 사용되며 사이킷런의 DecisionTreeRegressor를 사용하면 된다.  

from sklearn.tree import DecisionTreeRegressor

tree_reg = DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X, y)

분류 트리와의 주요한 차이는 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측하는 것이다. CART 알고리즘은 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신 평균제곱오차(MSE)를 최소화하도록 분할한다. 

$J(k, t_k)$=${m_l \over m} MSE_l + {m_r \over m} MSE_r$

$MSE_{node}=\sum_{i}(\hat{y}_{node}-y^{(i)})^2$
$\hat{y}_{node}={1 \over m_{node}}\sum_{i}y^{(i)}$

6.8 불안정성

결정 트리는 계단 모양의 결정 경계를 만든다. 이를 Axis Orthogonal Split이라 부르는데 쉽게 말해 모든 분할은 축에 수직이라는 의미이다. 따라서 훈련 세트의 회전에 민감하다. 원래는 간단한 선형으로도 구분할 수 있지만, 데이터셋을 $45^\circ$ 회전하면 불필요하게 구불구불해질 수 있다. 이 문제를 해결하는 한 가지 방법은 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA 기법을 사용하는 것이다. 

또 하나의 문제는 훈련 데이터에 있는 작은 변화에도 매우 민감하다는 것이다. 이는 랜덤 포레스트를 통해 많은 트리에서 만든 예측을 평균하여 극복할 수 있다.