Decision Tree

- Decision Tree (의사결정나무)

Decision Tree (의사결정나무)는 분류(Classification)와 회귀(Regression) 모두 가능한 지도 학습 모델 중 하나입니다.

의사결정나무는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며,

그 모양이 나무와 같다고 해서 의사결정나무라 불립니다.

 

 

 - 트리 구조 형태의 모델
   · Nodes: 속성에 대한 결정을 표시 (income 조건)
   · Branches: 결정의 선택을 표시 (선택결과)
   · Leaf nodes: 결정 조합의 결과를 나타냄 (말단 node에서 결정)

 - 의사 결정 트리는 분할 및 정복 접근 방식을 사용하여 구축됩니다.

 

 

- Partitioning Up the Predictor Space

  - 분류 / 회귀 문제에서 예측을하는 한 가지 방법은 예측자 공간을 나누는 것입니다.

   (i.e. all the possible values for X1, X2, ..., Xp) into distinct regions, say R1, R2, ..., Rk

 - 그런 다음 특정 지역 (예 : Rj)에 해당하는 모든 X에 대해 동일한 예측을 합니다.
 

 - 지역 Rj의 경우 최상의 예측은 다음과 같습니다.
      · 해당 지역 내 훈련 데이터 중 가장 일반적인 카테고리 (in case of classification)
      · 지역 Rj에 해당하는 훈련 데이터의 모든 응답의 평균 (in case of regression)

 

 

- C5.0 algorithm

 - C5.0은 순도 측정을 위해 엔트로피를 사용합니다.

 - Entropy 란
   · '무질서한 정도', '규칙적이지 않은 정도', '불확실성'
   · 정보 이득이 높을수록 동질 그룹을 만드는 기능이 더 좋습니다.

     (information gain이 큰 feature로 나누면 비슷한 성질의 그룹으로 만들어짐)

 

 

- 모델 학습

 - 재귀적 분기 (recursive partitioning)

 - 가지치기 (pruning)
   · A large tree (i.e. one with many terminal nodes) may tend to overfit the training data

 - How do we know how far back to prune the tree? 
   · We use cross validation

     (cross validation: training 데이터를 여러개로 나누어 test를 반복하는 과정) to see which tree has the lowest error rate.

 

 

- Decision Tree Pros and Cons

 장점.

   - 고차원 데이터를 다루는데 문제가 많지 않다. (but. sample이 많아지면 효울적이지 않다.)
   - 변수 타입에 따라 영향을 받지 않는다.
   - 해석이 쉽다. (해석이 중요한 Domain에서 적용)

 단점.

   - 성능이 복잡한 데이터에 대해서는 다른 복잡한 model 보다 떨어지는 경우가 있다.

 

 

- Problem with a single best model

 - 의사 결정 트리는 높은 분산으로 어려움을 겪습니다.

   (variance: training 데이터를 조금 바꿨을 경우, 결과가 많이 바뀌는가 안바뀌는가)

 

 - 이러한 Decision tree의 문제를 풀기 위해 아래의 방식을 사용합니다.
   1. bagging (bootstrap aggregating)을 사용: 여러 번 뽑아 각 모델을 학습시켜 결과를 집계 (Aggregating) 하는 방법
   2. Ensemble methods: 여러개의 model을 종합적으로 판단하여 예측
   3. Bootstrapping: training 데이터를 resampling 하여 여러개의 데이터를 생성하는 것

 

 

- Bagging

Bagging은 Bootstrap Aggregation의 약자입니다. 배깅은 샘플을 여러 번 뽑아(Bootstrap) 각 모델을 학습시켜 결과물을 집계

(Aggregration)하는 방법입니다

 - Bagging (Bootstrap Aggregating) => 'Random Forest'
   · Bootstrap + voting (used for classification)
   · Bootstrap + Averaging (used for regression)

 - 정확도와 안정성이 상승

 - variance 및 overfitting을 줄일 수 있다.

   (sample의 평균을 내면 분산이 줄어드는 효과가 있어 variance가 줄어든다.)

 

 

- Random Forest (랜덤포레스트)

기계 학습에서의 Random Forest는 분류, 회귀 분석 등에 사용되는 앙상블 학습 방법의 일종으로,

훈련 과정에서 구성한 다수의 결정 트리로부터 부류(분류) 또는 평균 예측치(회귀 분석)를 출력함으로써 동작합니다. 

 

 - Ensemble methods: 약한 여러 학습자를 결합하여 더 강한 학습자를 만듭니다.

 - Random Forests
   · 같은 데이터로 부터 의사결정나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법 (Bagging)
   · 각 나무를 만들 때, m개의 feature들을 무작위로 선정하여 학습시킴

 

 

- Prediction for Random Forest

 - For prediction, there are two approaches:
   1. majority vote (투표 방식): 0 or 1로 각각 트리에서 비율이 다를 수 있음
   2. average the probabilities: 트리 내의 확률 자체를 평균

 - 일반적인 "Bagging"과 달리 "Random Forest"는 m개의 feature들만 선정하여 

   굉장히 영향을 많이 미치는 feature을 배재하고 뽑을 수 있기 때문에 "de-correlates" 하다.

 

 

 아주대학교 정보통신대학원 손경아 교수님의 기계학습 및 데이터 마이닝 강의를 바탕으로 작성하였습니다.

 학습 목적으로 포스팅 합니다.