핸즈온 머신러닝 ㅡ 결정트리, DT(Decision Tree)

1. 아이디어

결정 트리는 우리가 일상 생활에서도 사용하는 방식이다. 예를 들어 음식 배달 주문을 할 때,

중식을 먹을지 양식을 먹을지, 중식을 먹는다면 짜장면을 먹을지,  짬뽕을 먹을지, 짜장면을 먹는다면 간짜장을 먹을지 삼선짜장을 먹을지와 같이 선택지를 큰 범주부터 작은 범주로 점진적으로 좁혀나가는 방식이다.

2. 훈련 방식

그림을 보자. 위에서 든 짜장면 예시와 다를 것이 없다. 맨 위에서 부터, 특정 샘플의 petal width(꽃잎 너비)가 0.8보다 작으면 왼쪽, 크면 오른쪽 아래로 내려간다. 예를 들어 샘플의 꽃잎 너비가 1.8, 길이가 5라고 하자. 맨 위 루트 노드부터 시작한다. 이 샘플의 꽃잎 너비가 0.8보다 크기 때문에 오른쪽 아래로 내려간다. 이 노드에서는 샘플의 꽃잎 너비가 1.75보다 작은지 검사한다. 크니까 오른쪽 아래로 내려간다. 이 노드에서는 꽃잎 길이가 4.85보다 작은지 검사한다. 보다시피 더 크기 때문에 오른쪽 아래로 내려간다.  자식 노드가 없는 리프 노드인 경우에는 추가적인 검사를 하지 않고 노드에 있는 예측 클래스로 예측을 한다.

3. 비용 함수(Cost function)

3.1 불순도(impurity) 측정

사이킷런에 구현되어 있는 결정 트리의 비용 함수를 이해하기 위해 불순도 개념을 먼저 이해해야한다. 결정 트리에서의 불순도란 얼마나 서로 다른 클래스의 샘플이 한 노드에 속해있는 지를 의미한다. 만약 한 노드에 속해 있는 샘플이 하나의 클래스의 샘플이라면 지니 불순도 값은 0이고 순수(pure)하다고 말한다.

3.1.1 지니 불순도(Gini impurity)

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

3.1.2 엔트로피(Entropy)

$ H_i = -\sum\limits_{k=1 \atop p_{i,k} \ne 0}^{n}{{p_{i,k}}\log_2(p_{i,k})} $

3.1.3 두 불순도의 차이

실제로는 큰 차이가 없다. 일반적으로 비슷한 트리를 만들어낸다. 다만 예외적으로 서로 비슷하지 않은 트리가 만들어지는 경우, 지니 불순도가 가장 빈도 높은 클래스를 한쪽으로 고립시키는 경향이 있는 반면 엔트로피는 더 균형잡힌 트리가 만들어진다.

훈련 시 계산 속도는 지니 불순도가 조금 더 빠르다. 

3.1.4 CART 알고리즘(Classification and Regression TRee)

사이킷런은 결정 트리를 훈련하는 알고리즘으로 CART 알고리즘을 사용한다. 아래의 비용 함수를 최소화하는 특성 k와 임계값 t_k를 찾아 훈련 세트를 두 개의 더 작은 세트로 나누고, 이를 반복하다가 깊이가 하이퍼파라미터로 정의한 max_depth와 같아 지거나, 불순도를 줄이는 분할을 찾을 수 없으면 훈련을 중지한다.

4. 분류

아래와 같이 사이킷런의 DecisionTreeClassifier를 사용한다.

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris() # 붓꽃 데이터 세트 불러오기
X = iris.data[:, 2:] # 특성들 중 일부만 선택
y = iris.target

model = DecisionTreeClassifier(max_depth=3) # 최대 깊이 3으로 설정
model.fit(X, y)

5. 회귀

분류에서는 특성과 그 임계치로 영역을 분할한 후 클래스를 예측했다면 회귀에서는 분할된 영역에 포함된 샘플들의 평균값으로 예측한다.

또한, 회귀에서는 분류에서와 달리 CART 비용 함수에 지니 불순도가 아닌 MSE를 사용한다.

 

아래와 같이 사이킷런의 DecisionTreeRegressor를 사용한다.

from sklearn.tree import DecisionTreeRegressor

model = DecisionTreeClassifier(max_depth=3)
model.fit(X, y)

 

6. 계산 복잡도

균형 트리의 탐색의 시간 복잡도는 O(log n)이다. 예측 시, 결정 트리가 루트부터 리프 노드까지 탐색을 진행하므로 결정 트리의 시간 복잡도는 균형 트리의 시간 복잡도를 따른다. 따라서 큰 데이터 세트를 다룰 때도 속도가 빠른 편이다.

훈련 시, 훈련 알고리즘은 각 노드에서 모든 훈련 샘플(n)의 모든 특성(k)을 비교하므로 시간 복잡도는 O(k * log n)이 된다.(속도를 높이기 위해 미리 데이터를 정렬한 후라고 가정, 사이킷런에서 presort=True로 지정한다.)

7. 기타

7.1 규제

결정 트리는 훈련 데이터에 대한 제약 사항이 거의 없다. 즉 선형 모델처럼 데이터가 선형이라고 가정하지 않는다. 제약 사항없이 각각의 훈련 데이터에 가깝게 맞추려고 해서 과대적합이 일어나기 쉽다. 일반적으로 제약은 모델의 파라미터 수나 하이퍼파라미터로 사전 정의되는데 결정 트리는 파라미터 수가 훈련 전에 결정되지 않는다. 따라서 하이퍼 파라미터로 모델에 제약을 가해 과대적합을 방지한다.

7.1.1 결정 트리의 하이퍼 파라미터

max_depth: 트리의 최대 깊이

min_samples_split: 분할되기 위해 노드가 가져야 하는 최소 샘플 수

min_samples_leaf: 리프 노드가 가져야 할 최소 샘플 수(절대치)

min_weight_fraction_leaf: 리프 노드가 가져야 할 가중치가 부여된 최소 샘플 수(상대치)

max_leaf_nodes: 리프노드의 최대 수

max_features: 각 노드에서 분할에 사용할 특성의 최대 수

 

* 정리하면 min_으로 시작하는 매개변수 값을 증가시키거나 max_로 시작하는 매개변수 값을 감소시키면 모델에 제약이 더 크게 작용한다.

7.2 불안정성

결정 트리는 이해하고 해석하기 쉽다. 즉 특정 붓꽃의 클래스를 예측한 후, 그 결과가 어떻게 도출되었는 지를 파악하기 쉽다. 맨 위의 트리 그림을 다시 보자. 샘플 A의 클래스 예측 결과가 setosa라고 나왔다면 그 샘플 A의 꽃잎 너비가 0.8보다 작기 때문에 그러한 결과가 나왔다는 것을 알 수 있다. 

하지만 단점도 있다. 아래와 같이 결정 트리는 결정 경계가 계단 모양으로 형성된다는 데서 문제가 생긴다. 같은 데이터 세트를 회전시키면 선형적으로 구분되는 데이터셋이 불필요하게 계단 모양으로 구불구불해진다.

다른 문제로는 모델이 훈련 데이터의 작은 변화에도 민감하게 반응하는 것이다.

 

위 데이터에서 길이 4.8, 너비 1.8인 샘플을 제거한 후 다시 결정 트리를 훈련시키면 아래와 같이 전혀 다른 결정 경계가 형성된다. 

또 다른 문제로 사이킷런에서 사용하는 훈련 알고리즘은 max_features를 데이터셋의 특성 개수보다 작게 설정하면 전체 특성 중 일부만 랜덤으로 선택해 훈련하기 때문에 같은 데이터를 두고도 다른 모델이 만들어질 수 있다.