SVM과 마찬가지로 Decision trees는 classification과 regression 그리고 multioutput을 모두 수행할 수 있는 versatile Machine Learning algorithms이다. powerful한 algorithm으로 복잡한 데이터 세트에 적합하다.
Decision trees 또한 Random Forests의 기본 구성 요소이며, 오늘날 가장 강력한 Machine Learning algorithms 중 하나이다. 6장에서는 Decision Trees를 사용하여 Train, visualize 및 predictions 하는 방법에 대해 논의한다.
Training and Visualizing a Decision Tree
위의 visualization된 algorithm을 가지고 간단히 설명하고자 한다. class는 setosa, versicolor, virginica 3개로 이루어져 있다. 목표은 각각의 class에 제대로 분류하는 것이다. depth는 3으로 이루어져 있다. 분류를 하기 위해서 feature은 petal length와 petal width 2가지를 사용하였다. petal length가 2.45cm보다 작은 것들은 left node(leaf node)인 setosa로 분류하였고 나머지는 right node로 분류하였다. 그리고 그리고 최종적으로 setosa에는 [50, 0, 0], versicolor에는 [0 49, 5], virginica에는 [0, 1, 45]로 분류가 되었다.
여기서 중요한 개념은 Gini impurity(지니 불순도)이다. Gini impurity란 임의의 새로운 변수 가 데이터 세트로부터 클래스 라벨의 분포에 따라 무작위로 분류된 경우, 임의 변수의 새로운 인스턴스의 잘못된 분류 가능성에 대한 측정치이다. 즉, 잘 분류가 되었는지 판단할 수 있는 척도이다.
첫 번째 feature에서 분류된 것을 보면 Gini impurity가 0이다. 50개의 setosa(actual)를 모두 setosa(predict)로 분류하였으며, setosa가 아닌 100개의 sample을 모두 아니라고 분류하였다. 수식으로는 전개한다면 '1 - {(50/50)^2 + (0/50)^2 + (0/50)^2} = 0'이 된다.
그렇다면 왜 더 이상 feature를 통해 더 분류하지 않은 것일까? 이미 Gini impurity가 0이므로 더 이상 분류가 필요 없다. 또 그렇다면 feature를 통해 분류를 할때 Gini impurity는 0이 되어야 하는 것일까? 아니다. impurity가 낮다고 판단되면 더 이상 진행할 필요가 없다. 만약 계속해서 분류가 진행된다면 overfitting이 발생하게 된다. 그래서 모델링을 할 때, feature, max depth, min leaf 등을 통해 제한을 두게 된다.
*위 그림은 max_depth가 2로 제한이 된 경우이지만 해당 경우가 아닐 때에 대한 설명
위의 그림은 Decision trees에서 decision boundaries를 보여준다. 두꺼운 세로선(depth=0)은 root node의 decision boundary이다. 그러나 오른쪽 영역은 불완전하므로 depth=1인 pental width = 1.75cm(점선으로 표시)로 분할한다.
그러나 오른쪽 영역은 불완전하므로 depth-1 오른쪽 노드는 꽃잎 너비 = 1.75cm (점선으로 표시)로 분할한다. max_depth가 2로 설정되었으므로 Decision tree가 바로 중지된다. max_depth를 3으로 설정하면 두 개의 depth-2 노드는 각각 다른 decision boundary(점으로 표시)를 추가한다.
Estimating Class Probabilities
Decision tree는 또한 instance가 특정 클래스 k에 속할 확률을 추정할 수 있다. 먼저 트리를 통과하여 이 instance의 leaf 노드를 찾은 다음이 노드에서 k-class의 Training instances 비율을 return한다. 예를 들어, 꽃잎의 길이가 5cm이고 너비가 1.5cm인 꽃을 발견했다고 가정해보자. 해당 leaf 노드는 depth-2 left node이므로 Decision tree는 다음과 같은 확률을 출력해야 한다. Iris setosa (0/54)의 경우 0%, Iris versicolor (49/54)의 경우 90.7 %, Iris virginica의 경우 9.3 % (5/54). 즉, Iris versicolor - class를 반환해야 한다.
The CART Training Algorithm (Classification and Regression Tree)
Decision trees에서 classification과 Regression이 모두 가능한 algorithm이다. binary tree(2진)로 이루어져 있다. 여러가지 feature 중 어떤 feature를 우선순위로 선택하는지, 그리고 feature에서 분류하게 되는 threshold 값이 중요하다. (k번째 feature, threshold tk) Random하게 feature를 선택하고 threshold 값을 설정한다. (CART algorithm은 greedy algorithm 중 하나이다.)그 후에 gini impurity를 계산한다. 그리고 여기서 선택은 gini impurity가 최소화되는 점을 찾아야한다. 그래서 cost function을 이용하게 된다.
* Greedy Algorithm
- 최적의 해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택할 때 그것이 그 상황에서 가장 좋다고 생각하는 것을 선택해 나아가는 방식으로 진행한다. 하지만 반드시 최적의 해를 보장하지는 않는다.
binary tree구조 이므로 2개로 분리했을 때 left node에 대한 Gini impurity, right node에 대한 Gini impurity가 구해진다. 우리는 하나만 고려해야하는 것이 아니라 두 경우에 대한 Gini impurity를 모두 고려해야 하므로 weighted sum에 대한 값으로 표현해야 한다. 그래서 cost function은 위와 같은 형태로 표현된다.
Gini Impurity or Entropy ?
기본적으로 Gini impurity 측정이 사용되지만 대신 기준 hyperparameter를 "Entropy"로 설정하여 Entropy impurity 측정을 선택할 수 있습니다. 분류가 잘 되었나 안되었나를 측정하는 기준이 2개(Gini impurity, Entropy)가 되는 것이다.
Regularization Hyperparameters
training data가 overfitting되지 않으려면 training 중 decision tree의 freedom을 제한해야 한다. 앞에서 decision tree에서 gini impurity가 0이 될 때까지 진행하면 매우 복잡한 algorithm이 만들어지고 overfitting이 발생한다고 언급했다. 그것을 막기 위해 제한된 model이 필요하다. 이것을 regularization(정규화)라고 한다. regularization hyperparameters는 사용된 algorithm에 따라 다르지만 일반적으로 decision tree의 maximum depth를 제한할 수 있다. (max depth를 줄이면 모델이 정규화 되어 overfitting을 줄일 수 있다.)
Decision Tree Classifier 클래스에는 Decision Tree 모양을 유사하게 제한하는 몇 가지 다른 매개 변수들이 있다. min_samples_split(노드가 분할하기 전에 노드에 있어야하는 최소 샘플 수), min_samples_leaf (leaf node에 있어야하는 최소 샘플 수), min_weight_fraction_leaf (min_samples_leaf와 동일하지만 총 가중 인스턴스 수의 일부로 표시됨), max_leaf_nodes (최대 리프 노드 수) 및 max_features (각 노드에서 분할에 대해 평가되는 최대 피처 수)들의 min_ * hyperparameters를 늘리거나 max_ * hyperparameters를 줄이면 모델이 정규화된다.
다음 그림은 Data set에 대해 train된 2개의 Decision tree를 보여준다. 왼쪽에는 의사결정 트리가 기본 hyperparameter(제한 없음)로 훈련되고 오른쪽에는 min_sample_leaf = 4로 훈련된다. 왼쪽의 모델이 과적합이고, 오른쪽의 모델이 일반화가 될 가능성이 매우 크다.
Regression
Decision tree는 regression도 가능하다.
regression 또한 이전에 설명했던 classification과 매우 유사하다. 주요 차이점은 각 노드에서 class를 예측하는 대신 값을 예측한다는 것이다. 예를 들어 x1 = 0.6 인 새로운 인스턴스를 예측한다고 가정해보자. 루트에서 시작하여 나무를 가로 지르면 결국 value = 0.111을 예측하는 leaf node에 도달한다. 이 예측은이 leaf node와 연관된 110 개의 train 인스턴스의 평균 목표 값이며, 이 110 개의 인스턴스에 대해 평균 제곱 오차(mse)가 0.015와 같다.
각 영역을 분할하여 대부분의 training instance를 가능한 한 예측된 값에 가깝게 만든다. CART Algorithm은 불순물을 최소화하는 방식으로 training set를 분할하는 대신 MSE를 최소화하는 방식으로 training set를 분할하려고한다는 점을 제외하면 대부분 이전과 동일한 방식으로 작동한다. 다음 식은 algorithm이 최소화하려고하는 cost function를 보여준다.
classfication과 마찬가지로 Decision tree는 regression을 처리 할 때 overfitting하기 쉽다. 정규화없이 (예 : 기본 hyperparameter 사용) 다음 아래의 그림 중 왼쪽과 같은 결과(no restrictions)가 나온다. 이러한 예측은 분명히 training set에 매우 적합하지 않다. min_samples_leaf = 10 만 설정하면 오른쪽의 그래프가 훨씬 더 합리적인 모델이 된다.
Instability
Decision tree는 직교 결정 경계 (모든 분할이 축에 수직임)를 좋아하므로 훈련 세트 회전에 민감하다. (train data set의 분포에 따라 민감하다.) 예를 들어, 위의 왼쪽 그래프는 선형으로 분리 가능한 간단한 데이터 집합을 보여준다. 왼쪽에는 의사 결정 트리가 쉽게 분할 할 수있는 반면, 오른쪽에는 데이터 집합이 45 ° 회전 된 후 의사 decision boundary가 불필요하게 복잡해 보인다. 두 Decision tree 모두 학습 세트에 완벽하게 맞지만 오른쪽의 모델이 일반화되지 않을 가능성이 크다. 이 문제를 제한하는 한 가지 방법은 Principal Component Analysis (8장 참조)를 사용하는 것인데, 이로 인해 종종 훈련 데이터의 방향이 향상된다.
일반적으로 decision tree의 주요 문제는 training data의 작은 변형에 매우 민감하다는 것이다. 예를 들어, 훈련 세트 (가로장 4.8cm, 폭 1.8cm)에서 가장 넓은 petal을 제거하고 새로운 decision tree를 train 시키면 <sensitivity to training set details 2> 표시된 모델을 얻을 수 있다.
댓글