서론
의사 결정 트리(Decision Tree)는 데이터를 특성에 따라 분할하여 관측치를 여러 개의 집단으로 나누는 지도 학습 알고리즘이다. 트리 구조에서 각 내부 노드는 특정 특성으로 나누는 분기점을 나타내며, 각 리프 노드는 해당 리프에 속하는 관측치가 특정한 클래스에 속할 확률을 나타낸다. 의사 결정 트리는 데이터를 분할하는 데 있어서 직관적이고 해석하기 쉽다는 장점이 있다. 또한 범주형 및 수치형 데이터를 모두 처리할 수 있는 다목적 알고리즘이기 때문에 널리 사용되는 머신 러닝 알고리즘 중 하나이다.
의사 결정 트리(Decision Tree)
SVM과 마찬가지로 의사결정 트리는 분류 및 회귀 작업은 물론 다중 출력 작업까지 수행할 수 있는 다목적 기계 학습 알고리즘이다. 의사결정 트리는 현재 사용할 수 있는 가장 강력한 기계 학습 알고리즘 중 하나인 Random Forests의 기본 구성 요소이기도 한다.
의사 결정 트리 학습과 시각화(Training and Visualizing a Decision Tree)
의사결정나무를 이해하기 위해 의사결정나무를 만들고 이것이 어떻게 예측하는지 살펴보자. 아래 예시는 iris 데이터세트와 graphviz를 사용하여 훈련된 의사결정 트리 시각화하였다.
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_name[2:],
class_names = iris.target_names,
rounded = True,
filled = True
)예측(Making Predictions)
위 예시는 결정 트리로 iris 꽃의 특성에 따라 연속적인 질문을 통해 꽃을 분류한다. 각 노드는 특정 특성에 대한 질문을 나타내며, 이를 통해 데이터를 좀 더 세분화하여 최종적으로 클래스를 예측한다. 또한, 노드의 samples, value, 그리고 gini 속성을 통해 특정 노드가 얼마나 많은 훈련 데이터를 다루는지, 각 클래스의 분포는 어떻게 되는지, 그리고 불순도는 어느 정도인지를 확인할 수 있다. 이를 통해 결정 트리는 직관적이고 해석하기 쉬운 모델로 평가받고 있다.
윗 내용은 결정 트리의 예측과정에 대한 설명이다. 결정 트리는 각 노드에서 특정 기준에 따라 데이터를 분할하여 예측을 수행한다. 데이터가 각 노드에 어떻게 적용되는지, 각 노드의 불순도와 샘플 수는 모델의 학습 및 예측 과정에서 중요한 정보를 제공한다. 불순도(impurity)는 해당 노드의 데이터가 얼마나 혼합되어 있는지를 나타내며, 불순도가 낮을수록 노드는 보다 순수한 상태라고 볼 수 있다.
Gini Score / Entropy
Gini Score
Gini score는 결정 트리 알고리즘에서 사용되는 지표 중 하나로, 해당 노드의 불순도를 측정한다. 이것은 해당 노드에서 샘플이 임의로 선택될 때 잘못 분류될 확률을 의미한다. Gini 점수가 낮을수록 노드는 더 순수하며, 모든 샘플이 같은 클래스에 속하는 경우 Gini 점수는 0이 된다. 결정 트리는 이러한 Gini 점수를 최소화하도록 분할을 선택하여 각 노드에서 가능한 한 더 순수한 서브그룹을 만들려고 한다. 따라서 Gini 점수는 결정 트리의 분할 기준을 결정하는 데 중요한 역할을 한다.
Entropy
엔트로피(Entropy)는 분자의 무질서도를 측정하는 개념으로, 엔트로피는 분자가 정지하고 잘 정렬될 때 0에 가까워진다. 이후 엔트로피는 샤넌의 정보 이론(Shannon’s information theory)을 통해 메시지의 평균 정보 내용을 측정하는 데 사용되었다. 엔트로피는 모든 메시지가 동일할 때 0이 된다. 머신 러닝에서 엔트로피는 종종 불순도 측정으로 사용되며, 집합의 엔트로피는 한 클래스의 인스턴스만 포함할 때 0이다.
Gini score와 엔트로피 중 어느 것을 사용해야 할까? 사실 대부분의 경우 유사한 의사 결정 트리를 이끌어내기에 큰 차이나지 않는다.
의사 결정 트리 결정 경계(Decision Tree’s Decision Boundaries)
두꺼운 수직선은 루트 노드(깊이 0)의 결정 경계를 나타낸다. 꽃잎 길이 = 2.45cm이다. 왼쪽 영역은 순수(Iris setosa만)이므로 더 이상 분할할 수 없다. 그러나 오른쪽 영역은 불순하므로 깊이 1 오른쪽 노드는 꽃잎 너비 = 1.75cm(점선으로 표시)에서 분할한다. max_깊이가 2로 설정되었으므로 의사결정나무는 바로 거기서 멈춘다. max_length를 3으로 설정하면 두 개의 깊이 2 노드가 각각 다른 결정 경계(점선으로 표시)를 추가한다.
Model Interpretation: White Box Versus Black Box
의사 결정 트리는 직관적이며 해당 결정을 해석하기 쉽다. 이러한 모델을 흔히 화이트박스 모델(white box models)이라고 한다. 반대로 다음에 볼 Random Forest 또는 신경망은 일반적으로 블랙박스 모델(black box models)로 간주된다. 블랙박스 모델들은 좋은 선능을 지닌 예측을 하며, 이러한 예측을 하기 위해 수행한 계산을 쉽게 확인할 수 있다. 그럼에도 불구하고 예측이 이루어진 이유를 간단한 용어로 설명하는 것은 일반적으로 어렵다.
Estimating Class Probabilities
의사결정 트리는 인스턴스가 특정 클래스 k에 속할 확률도 추정할 수 있다. 먼저 이 인스턴스의 리프 노드를 찾기 위해 트리를 순회한 다음 이 노드에서 클래스 k의 훈련 인스턴스 비율을 반환한다. 예를 들어, 꽃잎 길이가 5cm, 너비가 1.5cm인 꽃을 발견했다고 가정해 보자. 해당 리프 노드는 깊이 2의 왼쪽 노드이므로 의사결정 트리는 Iris setosa의 경우 0%(0/54), Iris versicolor의 경우 90.7%(49/54), Iris virginica의 경우 9.3%(5/54)의 확률을 출력해야 한다.
The CART Training Algorithm
CART(Classification and Regression Tree, 분류 및 회귀 트리) 알고리즘은 Scikit-Learn에서 결정 트리를 훈련하는 데 사용된다. 이 알고리즘은 이진트리만 생성하며(즉, 비단말 노드는 항상 두 개의 자식을 갖습니다.), 다른 알고리즘(ID3)은 두 개 이상의 자식을 갖는 노드로 구성된 결정 트리를 생성할 수 있다. 이 알고리즘은 먼저 하나의 특성 k와 임계값 tk(예: "꽃잎 길이 ≤ 2.45cm")을 사용하여 훈련 세트를 두 개의 하위 세트로 분할한다. 알고리즘은 순수성을 최대화하는(크기별 가중치) (k, tk) 쌍을 찾는다.
CART 알고리즘은 성공적으로 훈련 세트를 두 개로 분할한 후 동일한 논리를 사용하여 하위 세트, 그 다음 하위 하위 세트 등을 재귀적으로 분할한다. 최대 깊이(최대_깊이 하이퍼파라미터로 정의)에 도달하거나 불순도를 줄일 수 있는 분할을 찾을 수 없는 경우 재귀를 중단한다. CART 알고리즘은 탐욕(greedy) 알고리즘으로, 최상위 수준에서 최적 분할을 탐욕적으로 탐색한 다음 각 하위 수준에서 이 과정을 반복한다. 이는 분할이 여러 수준 아래에서 최소 불순도를 낮추는지 여부를 확인하지 않는다. 최적 트리를 찾는 것은 NPComplete 문제로 알려져 있으며, O(exp(m)) 시간이 소요되어 작은 훈련 세트에서도 문제를 해결하기 어렵게 만든다.
시간 복잡도
예측을 하려면 루트에서 리프까지 의사결정 트리를 순회해야 한다. 의사결정 트리는 일반적으로 대략 균형을 이루고 있으므로 의사결정 트리를 탐색하려면 대략 O(log2(m)) 노드를 거쳐야 한다. 여기서 log2(m)는 m의 이진 로그이며 log(m) / log(2)와 같다. 각 노드는 하나의 특성값만 확인하면 되므로 전체 예측 복잡도는 특성 개수에 관계없이 O(log2(m))이다. 따라서 대규모 훈련 세트를 처리할 때에도 예측이 매우 빠르다. 훈련 알고리즘은 각 노드의 모든 샘플에 대해 모든 특징(또는 max_features가 설정된 경우 더 적은 특징)을 비교한다. 각 노드에서 모든 샘플의 모든 특징을 비교하면 O(n × m log2(m))의 학습 복잡도가 발생한다.
하이퍼파라미터 정규화(Regularization Hyperparameters)
결정 트리는 훈련 데이터에 대해 매우 적은 가정을 한다. 선형 모델과는 달리 데이터가 선형이라고 가정하지 않는다. 제약을 받지 않으면 트리 구조는 훈련 데이터에 적응하여 매우 밀접하게 적합하며, 실제로는 과적합될 가능성이 높다. 이러한 모델은 비매개변수 모델(nonparametric model)이라고 한다. 이는 매개변수가 없는 것이 아니라 훈련 전에 매개변수의 수가 결정되지 않기 때문에 모델 구조가 데이터에 근접하게 유지된다. 반면에 선형 모델과 같은 매개변수적 모델은 미리 결정된 수의 매개변수를 갖기 때문에 자유도가 제한되어 과적합의 위험을 줄이지만 과소적합의 위험을 증가시킨다. 훈련 중 결정 트리의 자유도를 제한하여 훈련 데이터의 과적합을 피하려면 최대 깊이를 제한할 수 있다. DecisionTreeClassifier 클래스에는 Decision Tree의 모양을 유사하게 제한하는 몇 가지 다른 매개변수가 있다. min_ * 하이퍼파라미터를 증가시키거나 max_ * 하이퍼파라미터를 감소시키면 모델을 정규화할 수 있다. 위 예시는 moons 데이터셋에서 훈련된 두 개의 결정 트리이다. 왼쪽은 기본 하이퍼파라미터로 훈련되었으며(과적합), 오른쪽은 min_samples_leaf=4로 훈련되었다(일반화가 더 잘 됨).
- min_samples_split: 노드를 분할하기 전에 노드가 가져야 하는 최소 샘플 수
- min_samples_leaf: 리프 노드가 가져야 하는 최소 샘플 수
- min_weight_fraction_leaf: min_samples_leaf와 동일하지만 총 가중치 인스턴스 수의 일부로 표시됨
- max_leaf_nodes: 리프 노드의 최대 개수
- max_features: 각 노드에서 분할을 위해 평가되는 최대 기능 수
회귀(Regression)
결정 트리는 회귀 작업도 수행할 수 있다. 예시로 최대 깊이가 2인 잡음이 많은 이차 데이터셋을 학습시켰다. 이 트리는 이전에 만든 분류 트리와 매우 유사하다. 주요 차이점은 각 노드에서 클래스를 예측하는 대신 값을 예측한다는 것이다. 예를 들어 x1=0.6이면 값은 0.111로 예측된다. 이 예측은 이 잎 노드에 연결된 110개의 훈련 인스턴스의 평균 타깃 값을 나타내며, 이로 인해 이 110개 인스턴스에 대한 평균 제곱 오차가 0.015이다.
각 영역에 대한 예측 값이 해당 영역의 인스턴스의 평균 타깃 값임에 유의하자. 알고리즘은 각 영역을 분할하여 대부분의 훈련 인스턴스가 해당 예측 값에 가능한 한 가깝도록한다. CART 알고리즘은 이전과 거의 같은 방식으로 작동하지만 불순도를 최소화하는 방식으로 훈련 세트를 분할하는 대신 이제 평균 제곱 오차를 최소화하도록 훈련 세트를 분할하려고 한다. 정규화에 대해서도 언급할 만한다.
불안성(Instability)
Sensitivity to Axis Orientation
결정 트리는 직교하는 결정 경계(모든 분할이 축에 수직)를 선호하므로 훈련 세트의 회전에 민감하다. 왼쪽의 경우, 결정 트리는 쉽게 분할할 수 있지만 오른쪽의 경우 데이터셋이 45° 회전된 후 결정 경계가 불필요하게 복잡해 보인다. 이 문제를 제한하는 한 가지 방법은 데이터를 스케일링한 다음 주성분 분석(principal component analysis, PCA) 변환을 적용하는 것이다. PCA는 간단히 말하면 특성 간 상관관계를 줄이도록 데이터를 회전시키는데, 이는 종종 트리에 유리한 방향으로 작용한다.
from sklearn.decomposition import PCA
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
pca_pipeline = make_pipeline(StandardScaler(), PCA())
X_iris_rotated = pca_pipeline.fit_transform(X_iris)
tree_clf_pca = DecisionTreeClassifier(max_depth = 2, random_state = 42)
tree_clf_pca.fit(X_iris_rotated, y_iris)High Variance
결정 트리의 주요 문제점은 훈련 데이터의 작은 변화에 매우 민감하다는 것이다. 예를 들어, 붓꽃 훈련 세트에서 가장 넓은 버시컬러 붓꽃(꽃잎 길이 4.8cm, 너비 1.8cm)를 제거하고 새 결정 트리를 훈련시키면 위 그림과 같이 나타날 수 있다. 사실, Scikit-Learn에서 사용하는 훈련 알고리즘은 확률적으로 각 노드에서 평가할 특성 집합을 무작위로 선택하기 때문에, 정확히 같은 데이터에 대해 동일한 결정 트리를 다시 훈련시켜도 매우 다른 모델이 생성될 수 있다. 다행히도 많은 트리를 거쳐 예측을 평균화함으로써 분산을 크게 줄일 수 있다. 이러한 트리 앙상블을 랜덤 포레스트라고 하며, 현재 가장 강력한 모델 유형 중 하나이다.
'컴퓨터공학 > AI' 카테고리의 다른 글
| 기계 학습 8. 차원 축소(Dimensionality Reduction) (0) | 2023.10.28 |
|---|---|
| 기계 학습 7. Ensemble Learning and Random Forests (1) | 2023.10.20 |
| 기계 학습 5. Support Vector Machine(SVM) (1) | 2023.10.19 |
| 기계 학습 4. 회귀(Regression) 분석 (1) | 2023.10.19 |
| 기계 학습 3. 분류(Classification) (0) | 2023.09.20 |
댓글