핸즈온 머신러닝 2 chap 6 decision tree

결정트리(decision tree)는 분류, 회귀, 다중출력도 가능한 머신러닝 알고리즘임.

 

6.1 결정트리 학습과 시각화

 

결정트리가 어떻게 생겼는지 보자

 

6.2 예측하기

 

루트노드 (root node) 는 깊이가 0 인 맨 윗 노드에서 시작해서 샘플에 따라 오른쪽 또는 왼쪽으로 이동한다. 이동한 노드는 깊이가 늘어나고 이를 자식 노드 (child node)라 한다. 만약 끝에 도달하면 리프 노드 (leaf node) 라고하며, 이때는 class를 지정한다.

 

※ 결정 트리의 장점중 하나는 데이터 전처리가 거의 필요하지 않다는 것이다.

 

node의 sample 은 얼마나 거쳐갔는지, value 속성은 몇개의 샘플이 클래스로 분류되었는지이다. 마지막으로 gini의 불순도(impurity) 를 측정한다. 한 노드의 모든 샘플이 같은 클래스에 속해있으면 그 노드는 순수(gini = 0) 이라고 한다.

※ 사이킷런은 이진트리를 만드는 CART 알고리즘을 사용 -> 2개의 자식 노드를 가짐.

 

6.3 클래스 확률 추정

클래그 k 에 속할 확률을 추정 . leaf node 까지 내려온 후 각각의 확률의 계산.

 

6.4 CART 훈련 알고리즘

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

특성 k 의 임계값 tk 를 사용해 두개의 서브셋으로 나눈다. 그럼 k 랑 tk 는 무슨기준으로 고르냐. 가장 순수한 서브셋으로 나눌수 있는 k tk 짝을 찾는다. 이 알고리즘이 최소화 해야하는 비용함수는 아래와 같다.

G 는 서브셋의 불순도, m 은 샘플수.

이 과정을 max_depth 깊이가 되면 중지하거나 불순도를 줄이는 분할이 더이상 없을때 까지 반복한다.

 

※ CART 는 greedy 알고리즘이다. 즉 최적의 솔루션을 보장하지는 못한다. 또 NP-complete 문제라서 O(exp(m)) 의 시간복잡도를 가진다.

 

6.5 계산 복잡도

 

일반적으로 결정트리는 균형을 이루고 있으므로 약 O(log(m)) 개의 노드를 거친다. 각노드는 하나의 특성값만 확인하기 때문에 예측의 복잡도도 특성수와 무관하게 O(log(m))를 가진다. 즉 예측속도는 굉장히 빠른편이다.

훈련알고리즘은 각 노드에서 모든 훈련샘플의 모든 특성과 비교한다. 각 노드에서 모든 샘플의 모든 특성을 비교하면 훈련복잡도는 O(n*mlog(m)) 이 된다. 즉 dataset 이 큰경우 느린편이다.

 

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

기본적으로 지니 불순도를 사용하지만 엔트로피 불순도를 사용할 수도 있다.

엔트로피틑 분자의 무질서함을 측정하는 것으로 열역학의 개념이다. 분자가 안정해지면 엔트로피가 0에 가까워진다.

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

실제로는 지니를 쓰든 엔트로피를 쓰든 별 차이는 없다. 둘다 비슷한 트리를 만들어 낸다. 지니가 조금 빠르기는 하나 엔트로피는 좀더 균형잡힌 트리를 만들어 낸다.

 

6.7 규제 매개변수

결정트리는 제약사항이 거의 없다. 제한을 두지 않으면 과대적합이 되기 쉽다. 훈련되지전 파라미터수가 결정되지 않기에 이와 같은 모델을 비파라미터 모델(nonparametric model) 이라고 부른다. 

반대로 선형 모델과 같은 파라미터 모델 (parametric model) 은 미리 정의된 모델 파라미터수를 가지므로 자유도가 제한되고 오버피팅을 줄일 수 있다.

 

결정트리는 제한

max_depth : 최대 깊이

min_samples_split : 분항되기 위해 노드가 가져야할 최소 샘플 수

min_sample_leaf : 리프 노드가 가지고 있어야할 최소 샘플 수

min_weight_fraction_leaf : 가중피가 부여된 전체 샘플수에서의 비율

max_leaf_nodes : 리프노드위 최대 수

max_features : 각 노드에서 분할에 사용할 특성의 최대 수

 

제한없이 결정트리를 훈련시키고 불필요한 노드를 가지치기(pruning) 하는 알고리즘도 있음.

순도를 높이는것이 통계적으로 큰 효과가 없다면 리프노드 바로위 노드는 없어도 될수도 있음.

대표적으로 통계정 검정을 사용하여 우연히 향상된것인치 추정한다 -> 귀무가설

이 확률을 p-값 이라고 부르며 어떤 임계값보다 높으면 불필요한 노드로 간주되고 그 자식노드는 살제된다.

 

6.8 회귀

 

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

전 트리들과의 차이점은 각 노드가 어떤 클래스를 예측하는 것이 아닌 값을 예측한다는 점이다.

이걸 max_depth 를 3으로 눌려주면 다음과 같이 변한다.

CART 알고리즘은 훈련 세트의 분순도를 최소화 하는 방향으로 분할하는 대신 MSE(평균제곱오차) 를 최소화하도록 분할하는것을 제외하고는 비슷하게 작동한다.

회귀에서도 오버피팅이 되기 쉬운데 규제가 없으면 아래와 같이 될수도 있다.(오른쪽은 min_sample_leaf = 10)

 

6.9 불완전성

 

결정트리는 계단모양을 만든다. 그래서 후련세트의 회저에 민감하다. 즉 45도 돌아간 샘플을 생각해보면 구불구불 해지는 것을 볼수있다. 이럴때는 PCA 를 사용하면 좋다.

또 다른 문제는 훈련데이터의 작은 변화에도 매우 민감하다. 즉 같은 dataset 에도 매우다른 트리가 나올수 있다.