결정 트리decision tree
SVM처럼 결정 트리는 분류, 회귀, 다중 출력 작업도 가능한 알고리즘이다
또한 매우 복잡한 데이터셋도 학습할 수 있을만큼 강력하다. 이후에 나올 랜덤포레스트의 기본 구성요소이기도 하다.
6.1 결정 트리 학습과 시각화
https://colab.research.google.com/drive/18XiNghIvfnkumDdUY42GkGv22C5NsHwj#scrollTo=DQ1BFgfVd4Km
Google Colaboratory Notebook
Run, share, and edit Python notebooks
colab.research.google.com
6.2 예측하기
결정 트리의 예측을 만들어내는 과정.
ex 붓꽃의 품종을 분류, 위의 notebook 그래프 이미지 참조
루트노드root node 에서 꽃잎의 길이가 <= 2.45 인지 검사.
True -> 리프노드 setoas
False ->
오른쪽노드에서 꽃잎 너비가 <= 1.75인지 검사
True -> 리프노드 versicolor
False -> 리프노드 virginica
결정트리는 데이터 전처리가 거의 필요하지 않다. 특정 스케일을 맞추거나 평균을 원점에 맞추는 작업이 필요하지않다.
gini 속성 == 불순도impurity : 한 노드의 모든샘플이 같은 클래스에 속한다면 불순도는 0 이다.
p_i,k = i 번째 노드에있는 훈련 샘플중 클래스 k 에 속한 비율
결정트리는 이진트리만 만드는 CART 알고리즘 혹은 ID3 같은 둘 이상의 자식 노드를 가지는 알고리즘 등 다양하다.
모델해석 : 화이트박스 블랙박스
이 결정트리와 같이 직관적이고 이해하기 쉬운 결정 방식을 가진 모델을 화이트박스 모델 이라고 한다.
반대로 랜덤 포레스트나, 신경망은 블랙박스 모델이다. 즉 성능이 뛰어나고 예측을 만드는 연산과정을 쉽게 확인 할 수 있지만 왜 그런 예측을 만드는지는 쉽게 설명하기 어렵다.
6.3 클래스 확률 추정
한 샘플이 특정 클래스 k 에 속할 확률은 트리를 탐색해서 샘플이 속하는 리프노드를 찾는다.
그 리프노드의 클래스 k 의 비율이 샘플이 k 에 속할 확률이다.
6.4 CART 알고리즘
사이킷런은 결정 트리를 훈련하기위해 CARTclassification and regression tree 알고리즘을 사용한다
1. 훈련 세트를 하나의 특성 k 의 임계값 t_k 를 사용해 두개의 서브셋으로 나눈다.
2. k와 t_k 는 가장 순수한 서브셋으로 나눌 수 있는 (k, t_k) 짝을 찾는다.
G : 서브셋의 불순도
m : 샘플 수
3. 같은 방식으로 서브셋을 재귀적으로 나눈다.
4. max_depth으로 정의된 최대 깊이가 되면 중지하거나, 불순도를 줄이는 분할을 찾을 수 없을때 멈춘다.
이 CART 알고리즘은 Greedy 알고리즘으로 최적의 솔루션을 보장하지않는다. 최적의 트리를 찾기위해서는 샘플수의 거듭제곱에 해당하는 시간이 필요하다. 즉, 매우 작은 훈련세트에도 적용하기 어렵다. 따라서 납득할 만한 좋은 솔루션을 위한 알고리즘이다.
6.5 계산 복잡도
일반적으로 결정트리는 거의 균형을 이루기 때문에 트리를 탐색하는데 O(log2(m))개의 노드를 거쳐야 한다.
만일 각 노드에서 모든 특성을 비교한다면, 전체 훈련 복잡도는 O(n * mlog2(m))으로 증가한다.
사이킷런에서는 presort 파라미터를 통해 미리 데이터를 정렬하여 속도를 높일 수 있다.
6.6 지니 불순도 또는 엔트로피
기본적으로 gini 불순도가 사용되지만, criterion을 entropy로 지정하여 엔트로피 불순도를 사용할 수 있다.
ex) 64개중 56개, 8개로 나뉘는 노드가 있다면. 엔트로피는
지니 vs 엔트로피
보통 큰 차이는 없지만, 지니는 계산이 조금 더 빠르지만, 가장 빈도가 높은 클래스를 한쪽 가지로 고립시키는 반면,
엔트로피는 조금 더 균형있게 트리를 만든다.
결정 트리와 불순도에 대한 궁금증
이 글은 세바스찬 라쉬카의 머신러닝 FAQ 글(Why are implementations of decision tree algorithms usually binary and what are the advantages of the different impurity metrics?)을 번역한 것입니다. 결정 트리 알고리즘은 왜 이진
tensorflow.blog
6.7 규제 매개변수
결정 트리는 훈련 데이터에 대한 제약사항이 거의 없다. (반면 선형 모델의 경우 데이터가 선형이여야 하는 제한이있다.)
따라서 제한을 두지않으면 결정 트리가 데이터에 아주 가깝게 맞추기 때문에 과대적합되기 쉽다.
결정 트리는 훈련되기 전에 파라미터수가 안 정해진 비파라미터 모델nomparametric model 이고, 모델 구조가 데이터에 맞춰져 고정되지 않고 자유롭다.
(반면 선형 모델은 파라미터 모델로서 미리 정의 된 모델 파라미터 수를 가져 자유도가 제한되고 과대적합될 위험이 적다. 하지만 과소적합될 위험은 크다.)
트리의 자유도를 제한하기 위해 규제를 사용한다.
max_depth : 모델의 깊이를 제한한다.
min_samples_split : 분할되기 위해 노드가 가져야하는 최소 샘플수
min_weight_fraction_left : 가중치가 부여된 전체 샘플수에서의 비율(min_samples_split과 비슷하다.)
max_leaf_nodes : 리프 노드의 최대 수
max_features : 각 노드에서 분할에 사용할 특성의 최대 수
6.8 회귀
회귀는 분류와는 다르게 리프노드에 클래스를 사용하지않고 특정 값을 사용한다.
특정 값은 그 노드의 평균 타깃값이다. 새로운 샘플이 이 노드로 도달하면 이 값이 예측값이 된다.
회귀의 CART 알고리즘은 위에서 본 불순도를 최소화 하는 방향대신 MSE를 최소화하는 것을 제외하고는 동일하다.
분류에서와 마찬가지로 회귀에서도 결정트리가 과대적합되기 쉽다. 따라서 적당한 규제방법을 모색한다.
6.9 불안정성
결정트리는 많은 장점을 가지고 있지만, 몇가지 제한 사항이 있다.
결정트리는 계단 모양의 결정 경계를 만들기 때문에, 데이터셋의 회전에 민감하다. 예를들어,
단 하나의 수직 축으로 분할되는 데이터셋이 45도 회전하면 불필요하게 많은 조건이 추가될 수 있다.
이를 훈련데이터를 좋은 방향으로 회전하는 PCA기법을 사용 가능하다.
또한 결정트리는 훈련 데이터의 작은 변화에도 매우 민감하다.
훈련시 각 노드에서 평가할 특성을 무작위로 선택한다. 따라서 같은 훈련데이터 셋에서도 다른 모델을 얻을 수 있다.
다음의 랜덤포레스트는 많은 트리에서 만든 예측을 평균해서 이러한 불안정성을 없앤다.