Decision Tree (결정 트리)

 Decision Tree(결정 트리)는 분류와 회귀 작업 그리고 다중출력 작업도 가능한 머신러닝 알고리즘입니다. 그리고 최근에 자주 사용되는 강력한 머신러닝 알고리즘 중 하나인 랜덤 포레스트의 기본 구성 요소이기도 합니다. 이번 글에서는 결정 트리의 훈련, 시각화, 예측 방법에 대해 먼저 살펴보겠습니다.

참고자료 : 핸즈온 머신러닝 2판

---

결정 트리를 이해하기 위해 모델 하나를 만들어서 어떻게 예측을 하는지 확인해보겠습니다.

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)

 위 코드를 실행하시면 iris 데이터를 가져와서 Decision Tree 훈련을 진행합니다.

from sklearn.tree import export_graphviz

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

 훈련이 완료되었다면, export_graphviz 패키지를 활용하여 완성된 tree 모델을 이미지로 확인하실 수 있습니다. 위 코드를 실행하시면 폴더에 iris_tree.dot 이라는 파일이 생성될텐데요. Terminal에서 해당 위치로 간 뒤, dot -Tpng iris_tree.dot -o iris_tree.png 명령어를 실행하시면 dot 파일을 png로 변경하여 확인하실 수 있습니다.

 

 

 변경된 이미지파일을 열어보시면 어떻게 예측이 이루어지는지 보실수 있는데요. 맨 먼저 루트 노드(깊이가 0인 맨 꼭대기의 노드)에서 시작하여 꽃잎의 길이를 기준으로 왼쪽, 오른쪽 자식 노드로 이동하게 됩니다. 그렇게 이어지다가 리프 노트(자식 노드를 가지지 않는 노드)를 만나면 추가적인 검사 없이 예측 결과가 나오게 됩니다.

Decision Tree(결정 트리)의 여러 장점 중 하나는 데이터 전처리가 거의 필요하지 않다는 것입니다. 노드의 분기를 만들 때 특정 값을 기준보다 크냐, 작냐로 판단하기 때문에 스케일을 맞추는 작업을 하나마나 결과는 똑같습니다.

 이미지를 보면 노드에 sample, gini, value, class 라는 단어가 적혀있습니다 sample은 얼마나 많은 훈련 샘플이 적용되었는지 표기한 것입니다. value는 노드에서 각 클래스별로 얼마나 많은 훈련 샘플이 있는지 알려줍니다. class는 마지막 노드에서 어떠한 클래스로 판단할 것이지 Y값이 적혀 있습니다.

 

 gini 속성은 노드의 불순도를 측정합니다. 예를들어 한 노드에 모든 샘플이 같은 클래스에 속해 있다면 이 노드를 순수(gini=0)하다고 합니다. 만약 특정 노드에 54개의 샘플이 들어왔는데, [0,49,5] 이렇게 분리를 한다면 해당 노드의 gini 점수는 1-(0/54)^2-(49/54)^2-(5/54)^2 이 됩니다.

사이킷런은 이진 트리만 만드는 CART 알고리즘을 사용합니다. 따라서 리프 노트 외의 모든 노드는 자식 노드를 두 개씩만 가집니다. ID3 같은 알고리즘은 활용하면 둘 이상의 자식 노드를 가진 결정 트리를 만들 수 있습니다.

 Decision Tree는 한 샘플이 특정 클래스 k에 속할 확률을 추정할 수도 있습니다. 마지막 노드에 각 샘플의 개수가 나와있기 때문인데요. 앞서 한 노드의 value가 [0,49,5]로 적혀있었는데, 이는 한 샘플이 이 노드로 올 경우 첫 번째 클래스에 속할 확률이 0/54, 두 번째 클래스에 속할 확률은 49/54, 세 번째 클래스에 속할 확률은 5/54 로 해석할 수 있습니다.

 

Cart 훈련 알고리즘

 사이킷러너은 Decision Tree를 훈련시키기 위해 CART 알고리즘을 사용합니다. 먼저 훈련 세트를 하나의 특성 k의 임계값 tk를 사용해 두개의 서브셋으로 나눕니다. 그럼 여기서 어떻게 k와 tk를 고를까요? 바로 가장 순수한 서브셋, 가장 깔끔하게 샘플을 양분할 수 있는 (k, tk)의 조합을 찾는 것입니다. 이 CART 알고리즘이 최소화해야 할 Cost Function은 아래와 같습니다. 

 식을 보시면 알 수 있듯이 하나의 노드에서 두개의 노드로 양분되게 되고, 양분된 노드 각각의 Gini(불순도) 값을 계산합니다. 그리고 샘플 수의 비율을 가중합하여 최종적으로 CART 비용함수를 계산하게됩니다. 이처럼 하나의 세트를 둘로 나누었다면 같은 방식으로 서브셋을 또 나누고, 나누고를 반복합니다. 이 과정은 미리 설정해둔 파라미터인 Max Depth에 도달하거나 불순도를 줄이는 분할을 찾을 수 없을 때까지 진행됩니다.

 

계산 복잡도

 예측을 하려면 결정 트리를 루트 노드에서부터 리프 노드까지 탐색해야 합니다. 일반적으로 결정 트리는 1개 -> 2개 -> 4개 -> 8개 -> ... 이렇게 양분되면 2배씩 늘어나기 때문에 결정 트리를 탐색하기 위해서는 약 O(log2(m)) 개의 노드를 거쳐야 합니다. 각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도는 특성 수와 무관하게 O(log2(m)) 입니다. 그래서 큰 훈련 세트를 다뤄도 예측 속도가 빠릅니다.

 

 훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교합니다. 각 노드에서 모든 샘플의 모든 특성을 비교하면 훈련 복잡도는 O(n x m(lob2(m)) 이 됩니다. 따라서 훈련 세트가 클 경우에는 속도가 많이 느려집니다.

m : 훈련 데이터 수

n : 특성 수

Gini or Entropy

 DecisionTreeClassifier의 criterion 매개변수의 기본값은 Gini 불순도가 사용되지만 "entropy"로 지정하여 엔트로피 불순도를 사용할 수도 있습니다. 엔트로피는 분자의 무질서함을 측정하는 것으로 원래 열역할의 개념입니다. 분자가 안정되면 엔트로피가 0에 가깝습니다. 위에서 Gini 불순도를 계산한 예시를 활용하여 entropy 값을 구해보면,

-(49/54)log2(49/54)-(5/54)log2(5/54) = 0.445 로 구할 수 있습니다.

 

 Gini 와 Entropy 중 어떤 것을 사용하던지 큰 차이는 없습니다. 둘 다 비슷한 트리를 만들어냅니다. Gini가 계산이 조금 더 빠르기 때문에 기본값으로 좋습니다. 다만 데이터가 한쪽으로 치우쳐진 Imbalanced 한 상황의 경우, Gini 불순도를 사용할 때는 한쪽 가지로 고립시키는 경향이 있는 반면 엔트로피는 조금 더 균형 잡힌 트리를 만들어 냅니다.

 

규제 매개변수

 Decision Tree는 비선형 모델이라 훈련 데이터에 대한 제약 사항이 거의 없습니다. 모델에 제한을 두지 않는 경우 트리가 훈련 데이터에 과대적합되기 쉬운데요. Decision Tree는 훈련되기 전에 모델 파라미터 수가 결정되지 않기 때문에 비파라미터 모델 이라고 부릅니다. 그래서 모델 구조가 데이터에 따라 자유롭게 바뀝니다. 반대로 선형 모델은 파라미터 모델 이라고 하며, 미리 정의된 모델 파라미터 수를 가지므로 자유도가 제한되고 과대적합될 위험이 줄어듭니다.

 

 이처럼 Decision Tree는 비파라미터 모델의 특성상 과대적합의 위험이 있기 때문에 학습할 때 자유도를 제한할 필요가 있습니다. 이를 "규제" 라고 하는데요. Decision Tree에서는 최대 깊이(max depth) 를 제어할 수 있습니다. 최대 깊이를 줄이면 모델을 규제하게 되고 과대적합의 위험이 감소합니다.

 

 또 다른 매개변수로는 min_samples_split(분할되기 위해 노드가 가져야 하는 최소 샘플 수), min_sample_leaf(리프 노드가 가지고 있어야 할 최소 샘플 수), min_weight_fraction_lead(min_sample_leaf와 같지만 가중치가 부여된 전체 샘플 수에서의 비율), max_leaf_nodes(리프 노드의 최대 수), max_features(각 노드에서 분할에 사용할 특성의 최대 수) 가 있습니다. min으로 시작하는 매개변수를 증가시키거나 max로 시작하는 매개변수를 감소시키면 모델에 규제가 커집니다.

 

제한 없이 Decision Tree를 학습시키고 불필요한 노드를 가지치기 하는 알고리즘도 있는데요. 순도를 높이는 것이 통계적으로 큰 효과가 없다면 리프 노드 바로 위의 노드를 불필요할 수 있습니다. 즉 특정 노드를 2개로 분리하였지만 통계적으로 의미가 없을 때 위 노드를 불필요한 것으로 간주하고 자식노드를 삭제하는 것입니다. 이때 통계적으로 차이가 있는지를 확인할 때는 Chi-squared test 와 같은 통계적 검정 방법을 사용합니다.

 

회귀

 위에서는 iris 데이터셋을 활용하여 분류문제에서 Decision Tree를 사용하였습니다. DecisionTreeRegressor를 사용하면 회귀 문제에서도 결정 나무를 사용할 수 있습니다.

from sklearn.tree import DecisionTreeRegressor

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

 주요한 차이는 각 노드에서 클래스를 예측하는 대신 어떤 값을 예측한다는 점입니다. 각 리프노드에는 특성 예측 value 값들이 들어있고, 훈련 데이터가 들어갔을 때 노드를 타고 어떤 value가 나오는지에 따라 예측값이 정해집니다. 그리고 이 예측값과 실제값의 차이가 Error가 됩니다.

 

 회귀 문제에서의 CART 알고리즘은 훈련 세트를 불순도를 최소화하는 방향으로 분할하는 대신 평균제곱오차(MSE)를 최소화하도록 분할하는 것을 제외하고는 앞서 설명한 것과 거의 비슷하게 작동합니다. 아래 식은 알고리즘이 최소화하기 위한 비용 함수를 보여줍니다.

 식을 보면 알 수 있듯이 상대적으로 많은 비중이 든 샘플쪽에 Error가 가중합되게 되어있습니다. 즉 많은 샘플이 들어있는 쪽의 Error를 낮추어야 전체 Cost Function이 낮아지게됩니다.

 

불안정성

 Decision tree는 해석하기 쉽고, 사용하기 편하다는 장점이 있습니다. 다만 계단 모양의 결정 경계를(모든 분할이 축에 수직) 만들기 때문에 훈련 세트의 회전에 민감합니다. 만약 X축에 수직인 선 하나로 분류 문제를 해결할 수 있는 데이터가 있는데 이를 45도 회전한다면? 분류를 하기위해 필요한 선이 늘어날텐데요. 이런 문제를 해결하는 방법으로는 훈련 데이터를 좋은 방향으로 회전시키는 PCA 기법이 있습니다.

 

 

문제

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

  -> log2(10^6) 라고 답은 적혀있는데, 잘못 적혀있는것 같다..