Decision Tree (결정 트리)

결정트리란?

이진 분류 및 회귀, 다중 분류 등 다양한 모형 구분에서 활용가능한 머신러닝 알고리즘으로, 강력한 머신러닝 모형으로 알려져 있는 Random Forest의 기본 구성 요소입니다.

• 루트 노드(Root Node) : 깊이가 0인 맨 꼭대기의 노드
• 리프 노드(Leaf Node) : 자식 노드를 가지지 않는 노드
• samples 속성: 얼마나 많은 훈련 샘플이 적용되었는지
• value 속성 : 노드에서 각 클래ㅐ스에 얼마나 많은 훈련 샘플이 있는지
• Gini 속성 : 불순도를 측정
  • 한 노드의 모든 샘플이 같은 클래스에 속해 있다면, 이 노드를 순수(gini=0)하다고 함

 

[ 장점 ]

• 데이터 전처리가 거의 필요하지 않습니다
• 특성 스케일이 불필요합니다.
• 모델 해성 능력이 높습니다
  • 화이트 박스 모델 : 직관적이고 결정 방식을 이해하기 쉽다 (ex) 결정트리)
  • 블랙 박스 모델 : 성능이 뛰어나고 예측을 만드는 연산 과정을 쉽게 확인할 수 있으나, 예측에 대한 설명이 어렵다 (ex) 랜덤포레스트, 신경망)

 

[ 확률 추정 ]

• 결정트리는 한 샘플이 특정 클래스 k에 속할 확률을 추정할 수도 있습니다.
  • 위에서 결정트리를 시각화한 사진을 예시로, 길이가 5cm 너비가 1.5cm인 꽃잎에 대해 이에 해당하는 리프노드는 깊이 2에서 왼쪽 노드(초록색 노드)입니다
  • 이때 각 클래스에 해당하는 확률은 setosa = 0/54 = 0% , versicolor = 49/54 = 90.7% , virginica = 5/54 = 9.3%

 

[ CART (Classification And Regression Tree) ]

CART는 분류도 하고 회귀도 할 수 있는 트리로 알고리즘은 다음과 같습니다.

• 먼저 훈련 세트를 하나의 특성 k의 임계값 t(k)를 사용해 두 개의 subset으로 나눈다
• 다음, 가장 순수한(gini가 0에 가까운) subset으로 나눌수있는 (k, t(k))짝을 찾는다
• 따라서 CART알고리즘이 최소화해야하는 비용함수는 아래와 같다
  • G는 서브셋의 불순도, m은 서브셋의 샘플 수

• CART알고리즘이 subset을 나누는 과정은 max_depth 매개 변수로 정의된 최대 깊이가 되면 중지하거나, 불순도를 줄이는 분할을 찾을 수 없을 때 멈춘다
  • max_depth 외에도 min_samples_split, min_samples_leaf, min_weight_fraction_leaf, max_leaf_nodes와 같은 하이퍼파라미터도 중지 조건에 관여함
• CART알고리즘은 탐욕적 알고리즘(greedy algorithm)이다
  • 탐욕적 알고리즘은 항상 최적의 솔루션을 보장하지는 않음
  • 또한 최적의 트리를 찾는 것은 NP-완전(NP-complete)문제로도 알려져 있기 떄문에, 납득할 만한 좋은 솔루션으로만 만족을 해야함

 

[ 계산복잡도 ]

결정 트리를 훈련하기 위해서는 약 O(n*log2(m))개의 노드를 거쳐야 한다(n :변수개수, m :데이터개수)

• 각 노드에서 모든 훈련 샘플은 모든(max_features가 지정이 되면 더 적은) 변수의 값을 확인하기 때문에, 훈련에 필요한 전체 복잡도는 변수의 개수(n)과 관련되어 O(n*log2(m))이다

예측시, 결정트리를 탐색하기 위해서는 약 O(log2(m))개의 노드를 거쳐야 한다

• 각 노드는 하나의 변수의 값만 확인하기 떄문에, 예측에 필요한 전체 복잡도는 변수 개수(n)과 무관하게 O(log2(m))이다
• 따라서, 큰 훈련 세트를 다룰 떄도 예측 속도가 빠르다

 

[ 지니불순도 & 엔트로피 ]

• 일반적으로 지니불순도와 엔트로피 모두 비슷한 트리를 생성해내기 때문에, 계산이 좀 더 빠른 지니불순도를 기본값으로 사용합니다.
• 그러나 가끔 다른 트리의 형태가 만들어 지는 경우, 지니불순도는 가장 빈도 높은 클래스를 한쪽 가지로 고립시키는 경향이 있으며 엔트로피는 조금 더 균형 잡힌 트리를 생성하는 특징이 있습니다

지니 불순도

엔트로피

• p(i,k)는 i번째 노드에 있는 훈련 샘플 중 클래스 k에 속한 샘플의 비율

 

[ 규제 매개변수 ]

max_로 시작하는 매개변수를 감소시키면 모델에 대한 규제가 커집니다.(과대적합 위험 감소)

• max_depth : 결정트리의 최대 깊이
• max_leaf_nodes : 리프 노드의 최대 개수
• max_features : 각 노드에서 분할에 사용할 특성의 최대 개수

min_으로 시작하는 매개변수를 증가시키면 모델에 대한 규제가 커집니다(과대적합 위험 감소)

• min_samples_split : 분할되기 위해 노드가 가져야하는 최소 샘플의 개수
• min_samples_leaf : 리프노드가 가지고 있어야할 최소 샘플의 개수
• min_weight_fraction_leaf : min_samples_leaf와 비슷하지만, 가중치가 부여된 전체 샘플 수 내에서의 비율

 

[ 불안정성 ] 

결정트리는 이해하고 해석하기가 쉽고, 사용하기 편하고, 성능도 뛰어나지만, 결정 경계가 계단 모양이라서 훈련세트의 회전에 민감하다.

• 회전에 민감한 데이터라면, 결정 트리 모델이 불필요하게 구불구불해지기 때문에 이러한 경우 잘 일반화 할 수 없다.
• 훈련 데이터를 더 좋은 방향으로 회전시키는 PCA(주성분 분석)기법을 사용하여 불안정성을 개선할 수 있다
  • 랜덤포레스트는 많은 트리에서 만든 예측을 평균내는 방법으로 불안정성을 극복함

 

 

# 코드 참고

GitHub - sonzwon/TIL_DL