[Machine Learning] 결정 트리

핸즈온 머신러닝 (2판)

---

Part 1. 머신러닝

CHAPTER6. 결정 트리

6.1 결정 트리 학습과 시각화 6.2 예측하기 6.3 클래스 확률 추정 6.4 CART 훈련 알고리즘 6.5 계산 복잡도 6.6 지니 불순도 또는 엔트로피? 6.7 규제 매개변수 6.8 회귀 6.9 불안정성 6.10 연습문제

---

결정트리[decision tree]

분류와 회귀, 다중 출력이 가능한 머신러닝 알고리즘

 

랜덤 포레스트의 기본 구성 요소이다.

---

결정 트리 학습과 시각화

iris 데이터셋에 DecisionTreeClassifier 훈련

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, random_state=42)
tree_clf.fit(X, y)

 

export_graphviz() 함수를 사용해서 그래프 정의를 iris_tree.dot 파일로 출력하여 훈련된 결정 트리를 시각화 할 수 있다.

from graphviz import Source
from sklearn.tree import export_graphviz

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

Source.from_file(os.path.join(IMAGES_PATH, "iris_tree.dot"))

 

.dot 파일을 Graphviz 패키지에 있는 dot 명령줄 도구로 PDF나 PNG 같은 포멧으로 변경한다.

아래 명령은 .dot  파일을 .png 이미지로 변경하는 코드이다.

$ dot -Tpng iris_tree.dot -o iris_tree.png

 

사이킷런에서 dot 파일을 만들지 않고, plot_tree() 함수를 이용해서 그릴 수도 있다.

from sklearn.tree import plot_tree
plot_tree(tree_clf)

만든 첫 번째 결정 트리

import matplotlib.pyplot as plt

explt_vars = ["sepal_length", "sepal_width", "petal_length", "petal_width"]
fct_val = {0: 'setosa', 1: 'versicolor', 2: "virginica"}

plt.figure(figsize = (10,8))
plot_tree(tree_clf, feature_names = explt_vars, class_names = fct_val, filled = True);

붓꽃 결정 트리

---

예측하기

루트 노드[root node] : 깊이가 0인 맨 꼭대기의 노드

리프 노드[leaf node] : 자식 노드를 가지지 않는 노드

 

새로 발견한 붓꽃 품종을 분류하려고 한다면

루트 노드에서 시작해서 꽃잎의 길이가 2.45보다 짧은지 검사한다.

True인 경우, 왼쪽의 자식 노드[child node] 로 이동 (깊이가 1, 왼쪽 노드) -> 이 경우, 리트노드이므로 추가적인 검사를 하지 않는다. 이 노드에 있는 예측 클래스를 보고 결정 트리가 새로 발견한 꽃의 품종은 Iris-Setosa(class=setosa)라고 예측한다.

 

False인 경우, 오른쪽의 자식 노드로 이동한다. 이 경우, 리프노드가 아니므로 추가로 꽃의 너비가 1.75보다 작인지 검사한다.

True라면, Iris-Versicolor / False라면, Iris-Virginica

 

Decision Tree의 장점

데이터 전처리가 거의 필요하지 않다는 것이다.

특성의 스케일의 맞추거나 평균을 원점에 맞추는 작업이 필요하지 않다.

 

value = [0, 1, 45] 의 의미

value 속성은 노드에서 각 클래스에 얼마나 많은 훈련 샘플이 있는지 알려준다.

Iris-Setosa는 0개, Iris-Versicolor는 1개, Iris-Virginica는 45개가 있다는 것을 의미한다.

 

노드의 gini 속성의 의미

불순도[impurity]를 측정한다.

 

$i$번째의 노드의 $gini$  점수 $G_i$를 계산하는 방법

지니 불순도

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

이 식에서 $p_{}i,k$는 $i$번째 노드에 있는 훈련 샘플중 클래스 $k$에 속한 샘플의 비율이다.

 

| 사이킷런은 이진 트리만 만드는 CART 알고리즘을 사용한다. 따라서 리프 노드 외의 모든 노드는 자식 노드를 두 개씩 갖는다(즉, 질문의 답은 예 or 아니오). 하지만 ID3 같은 알고리즘은 둘 이상의 자식 노드를 가진 결정 트리를 만들 수 있다. |

 

max_depth를 2로 설정했기 때문에 결정 트리는 더 분할되지 않는다.

만약 3으로 설정하면 깊이 2의 두 노드가 각각 결정 경계를 추가로 만든다(점선).

결정 트리의 결정 경계

 

화이트박스[white box] 모델 : 직관적이고 결정 방식을 이해하기 쉬운 모델 ex.결정 트리

블랙박스[black box] 모델 : 성능이 뛰어나고 예측을 만드는 연산 과정을 쉽게 확인할 수 있지만 왜 그런 예측을 만드는지는 쉽게 설명하기 어려운 모델 ex.랜덤 포레스트, 신경망

---

클래스 확률 추정

결정 트리는 한 샘플이 특정 클래스 k에 속할 확률을 추정할 수도 있다.

# 길이가 5cm, 너비가 1.5cm인 꽃잎
tree_clf.predict_proba([[5, 1.5]])
#array([[0.        , 0.90740741, 0.09259259]])
tree_clf.predict([[5, 1.5]])
#array([1])

Iris-Setosa일 확률은 0%, Iris-Versicolor는 90.7%, Iris-Virginica는 9.3%

---

CART 훈련 알고리즘

CART; classification and regression tree

사이킷런에서 결정 트리를 훈련시키기 위해 사용하는 알고리즘

 

분류에 대한 CART 비용 함수

$ J(k,t_k) = \frac{m_{left}}{m} G_{left} + \frac{m_{right}}{m} G_{right}        $

$\text{여기에서} \begin{cases} G_\text{left/right} \text{는 왼쪽/오른쪽 서브셋의 불순도} \\ m_\text{left/right} \text{는 왼쪽/오른쪽 서브셋의 샘플 수}                     \end{cases}$

 

CART 알고리즘이 훈련 세트를 성공적으로 둘로 나누었다면 같은 방식으로 서브셋을 또 나누고 그 다음엔 서브셋의 서브셋을 나누는 식으로 반복된다.

이 과정은 max_depth 매개변수인 최대 깊이가 되면 중지하거나 불순도를 줄이는 분할을 찾을 수 없을 때 멈추게 된다.

그 외에도 min_samples_split, min_samples_leaf, min_weight_fraction_leaf, max_leaf_nodes도 중지 조건을 걸 수 있다.

---

계산 복잡도

예측을 하려면 결정 트리를 루트 노드에서부터 리프 노드까지 탐색해야 한다. 일반적으로 결정 트리는 거의 균형을 이루고 있으므로 결정 트리를 탐색하기 위해서는 약 $O(log_2(m))$개의 노드를 거쳐야 한다.

각 노드는 하나의 특성값만 확인하기 때문에 예측에 필요한 전체 복잡도는 특성 수와 무관하게 $O(log_2(m))$이다. 그래서 훈련 세트를 다룰 때도 예측 속도가 매우 빠르다.

 

훈련 알고리즘은 각 노드에서 모든 훈련 샘플의 모든 특성을 비교한다. max_features가 지정되었다면 그보다는 적은 특성을 비교한다. 각 노드에서 모든 샘플의 모든 특성을 비교하면 훈련 복잡도는 $O(n$ x $m log_2(m))$이 된다.

 

훈련 세트가 수천개 이하의 샘플 정도로 작을 경우 사이킷런은 presort=True로 지정하면 미리 데이터를 정렬하여 훈련 속도를 높일 수 있다. But 훈련 세트가 클 경우에는 속도가 많이 느려진다.

---

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

기본적으로는 지니 불순도가 사용된다.

criterion 매개변수를 "entropy"로 지정하여 엔트로피 불순도를 사용할 수 있다.

 

엔트로피 : 분자의 무질서함을 측정하는 것으로 원래 열역학의 개념이다.

분자가 안정되고 질서 정연하면 엔트로피가 0에 가깝다.

메시지의 평균 정보 양을 측정하는 섀넌의 정보 이론도 여기에 포함된다. 여기서는 모든 메시지가 동일할 때 엔트로피가 0이 된다.

 

머신러닝에서는 불순도의 측정 방법으로 자주 사용된다.

어떤 세트가 한 클래스의 샘플만 담고 있다면 엔트로피가 0이다.

 

$i$번쨰 노드의 엔트로피 정의

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

 

지니 불순도와 엔트로피 중 어떤 것을 사용?

실제로는 큰 차이는 없다. 즉, 둘 다 비숫한 트리를 만들어낸다.

지니 불순도가 조금 더 빠르게 계산이 가능헤서 기본값으로 좋다.

But 다른 트리가 만들어지는 경우, 지니 불순도가 가장 빈도 높은 클래스를 한쪽 가지[branch]로 고립시키는 경향이 있는 반면 엔트로피는 조금 더 균형 잡힌 트리를 만든다.

---

규제 매개변수

결정 트리는 훈련 데이터에 대한 제약 사항이 거의 없지만 제한을 두지 않으면 대부분 과대적합되기 쉽다.

 

비파라미터 모델[nonparametric model] : 훈련되기 전에 파라미터 수가 결정되지 않는 모델. 모델 구조가 데이터에 맞춰져서 고정되지 않고 자유롭다. ex.결정트리

파라미터 모델[parametric model] : 미리 정의된 모델 파라미터 수를 가지므로 자유도가 제한되고 과대적합 될 위험이 줄어든다. But 과소적합될 위험은 커진다. ex.선형모델

 

DecisionTreeClassifier 파라미터

파라미터	설명
max_depth	최대 깊이 / 기본값=None
min_samples_split	분할되기 위해 노드가 가져야 하는 최고 샘플 수
min_samples_leaf	리프 노드가 가지고 있어야 할 최소 샘플 수
min_weight_fraction_leaf	min_samples_leaf와 같지만가중치가 부여된 전체 샘플 수에서의 비율
max_leaf_nodes	히프 노드의 최대수
max_features	각 노드에서 분할에 사용할 특성의 최대 수

min_ 으로 시작하는 매개변수를 증가시키거나

max_ 로 시작하는 매개변수를 감소시키면 모델에 규제가 커진다.

 

min_samples_leaf=4로 지정하여 훈련시켰을 때와 비교

min_samples_leaf 매개변수를 사용한 규제

---

회귀

사이킷런의 DecisionTreeRegressor을 이용

 

잡음이 섞인 2차 함수 형태의 데이터셋에서 max_depth=2 설정으로 회귀 트리 만들기

# 2차식으로 만든 데이터셋 + 잡음
np.random.seed(42)
m = 200
X = np.random.rand(m, 1)
y = 4 * (X - 0.5) ** 2
y = y + np.random.randn(m, 1) / 10

from sklearn.tree import DecisionTreeRegressor

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

import matplotlib.pyplot as plt

plt.figure(figsize = (12,8))
plot_tree(tree_reg, filled = True);

회귀 결정 트리

각 영역의 예측값은 항상 그 영역에 있는 타깃값의 평균이 된다. 알고리즘은 예측값과 가능한 많은 샘플이 가까이 있도록 영역을 분할한다.

두 개의 결정 트리 회귀 모델의 예측

결정 트리 회귀 모델의 규제

---

불안정성

결정 트리의 몇가지 제한 사항

• 계단 모양의 결정 경계를 만든다. 모든 분할이 축에 수직이다. 그래서 훈련 세트의 회전에 민강하다.
  => 해결방법 : 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA기법 사용

훈련 세트의 회전에 민감한 결정 트리

• 주된 문제 : 훈련 데이터에 있는 작은 변화에도 매우 민감하다.

훈련 세트의 세부사항에 민감한 결정 트리

---