5장_트리_알고리즘_송명섭.md

Decision Tree

• 분류와 회귀 모두 적용 가능한 지도 학습 알고리즘
• 많은 머신러닝 알고리즘들이 최적의 가중치를 찾는 과정이었지만,
  의사결정트리는 간단히 스무고개 놀이를 떠올리면 좋다.

Q. 그렇다면 사용자가 준비한 데이터 피처를 어떤 방식으로 분류하는가?

CART Algorithm

• Classification and Regression Tree의 약자로, 분류/회귀 모두에 적용 가능함.
• 분류는 불순도(gini/entrophy), 회귀는 MSE(평균제곱오차)가 낮아지는 방향으로 분기 지속

+) 참고

• 불순도(Impurity)는 해당 범주 내에 상이한 데이터가 섞여있는 정도로,
  다양한 개체가 섞여 있을수록 불순도가 높으며 종류로는 Gini, Entrophy가 있다.
• 정보 이득(Information Gain)은 분기 전후의 불순도 차이를 의미한다.
• 각 분할에서 정보 이득을 최대화 수 있도록
• 최종 결과는 동일하더라도 질문(분할)을 어떻게 하느냐에 따라 정보 이득이 다른데,
  이해하기 쉬운 예시로, 1~100 up&down을 할 때 답이 98인데 90을 부르면
  첫 질문에 90개를 거르는 상당한 효과를 보게 된다.(수식적 계산보다는 맥락 상의 예시랄까?)

추가로, 장단점을 알아보자.

• 직관적인 해석이 쉽다(정말로다가).
• 피처의 스케일링이 불필요하다.
• 하지만 과적합의 위험이 매우 높다. 이는 분류 기준(gini 또는 entrophy)이나
  max_depth, min_samples_split 등의 하이퍼파라미터를 어떻게 가져가느냐에 따라 완화할 수 있는데,
  이것이 '가지치기'이다.

+) 지니 불순도와 지니 인덱스로 두 개의 식이 있는 개념은 후에 정리해서 올리겠다.

교차 검증

어떤 알고리즘을 배운다면, 왜 필요한지를 먼저 생각해보자.
릿지/라쏘는 과적합 방지를 위한 규제 기법이었고, 로지스틱 회귀는 확률 기반의 분류 기법이었다.
교차 검증(Cross Validation) 이전에 Validation을 떠올려보자.
(검증이 후술할 하이퍼파라미터 튜닝과, 다양한 검증 기법과 왜 관련이 있을지도 고민해보자)
데이터셋을 Train, Validation, Test로 분류한 이유부터 생각해보자.

예제와 같이 환자 데이터가 있고, 새로운 환자가 다음과 같이 추가되었다고 하자.


이를 보고 심장병 유무를 파악하려면? 먼저, 어떤 ML 모델을 사용할지 결정해야 한다.(로지스틱 회귀 or KNN or SVM, etc...)
다양한 성능 지표를 비교하여 모델을 선택하면 될 것이다.
데이터를 train과 test로 나눈 것은 기계학습의 핵심인 '예측'을 위해서인데,
이 중 지도학습, 즉 학습을 한 후에 한 번도 보지 못 한 데이터를 제공했을 때 이를 예측하는 것이 ML의 목표이다.
이를 위한 Unseen data 역할을 test 데이터가 하는 것이다. 하지만 문제가 발생한다.

예를 들어, 정렬된 10000개의 데이터에 대해 두 데이터셋 1 ~ 5000(A), 5001 ~ 10000(B)로 분류한 후,
첫 번째 그룹인 1~5000 데이터에 대한 test 결과 정확도가 95%일 때, 이는 좋은 모델인가?
(물론 정확도만 보면 안 되긴 하지만)
그리고 A 모델을 B에 적용해도 좋은 결과를 얻을 수 있을까? 결론은...

테스트 데이터 일반화 능력도 중요하지만, 테스트 데이터에 대한 과적합도 문제이다.

그리고 Hyperparameter Tuning을 통해 최적화에 더 가까워질 기회를 놓친다. 다시 말해

Test만 있다면 모델 성능 결과를 도출할 순 있지만 더 좋은 성능의 모델 탐색(최적화)의 기회가 없어진다.

test는 모델 성능 평가가 전부일 뿐이다. 성능 개선에 관여하지 않는다.\

Q. 모델 1과 모델 2에 대해 test 데이터로 평가해서 비교해도 되지 않냐?
A. test 데이터는 예측을 위한 최종 수단이다. 건드리면 안 된다.
물론 테스트 데이터에 대한 성능 지표를 적용해서 확인할 수는 있겠지.
문제는 test 데이터가 유출되어 모델이 학습하게 된다.
test 데이터가 자주 쓰이면 data leakage 문제로 test에 맞게 변질될 수 있다.
아기가 내 휴대폰으로 뽀로로 영상만 죽어라 보면 유튜브 알고리즘이 잠식되어
내가 검색할 때 관련 영상에 막 뜨는 것처럼 말이다.(비유가 애매하긴 하지만)

요약하면,

그리디 탐색(Greedy Search

Ensemble

먼저, 앙상블을 왜 학습하는지 생각해보자.

Opinion 1

기계학습의 목적은 예측인데, 이를 잘 수행하기 위해 예측과 실제 간 차이를 Loss로 정의하였고,
이 Loss를 최소화하는, 다시 말해 Optimal Parameter를 찾아내는 것이 지금까지 본 알고리즘들의 공통점이다.
(ex. 로지스틱 회귀, 릿지/라쏘, 잔차제곱 등)

하지만, 앙상블은 오차의 최소화와는 거리가 있다. 앞에서 다룬, 앙상블의 기반이 되는 결정 트리는
손실을 줄인다는 느낌보다는, Information Gain과 Impurity를 고려하여 순차적인 결정 규칙을 통해
최적의 분할을 찾으며, 이때 각 분할마다 데이터가 분류/예측된다.

사전적 의미는 '조화' 또는 '통일'로, 여러 결정트리를 결합하여 보다 강력한 예측 모델을 생성한다.
Hyperparameter tuning이 주어진 알고리즘 내에서 최적의 파라미터를 찾기 위함이라면,
Ensenble은 예측의 조합으로 최종 예측을 결정하는, 알고리즘 간 조합을 통해 성능을 최대화하는 것이다.
주요 앙상블 기법에는 Bagging 방식의 Random Forest와, Boosting 방식의 Gradient Boosting이 있다.

Opinion 2

이상적인 모델은 4번째가 바람직하지만, 현실에서는 2번째 또는 3번째인 경우가 많다.
앙상블의 목적은 4번째, 다중 학습 모델을 기반으로 Bias/Variance 감소를 통해 Total Error를 줄이는 것이다.
앞에서도 언급했고, 그림을 통해서도 알 수 있듯이,
Bagging과 Boosting은 감소하고자 하는 목적에 따라 구분된다.

Bagging(Bootstrap Aggregating)

• 기존 학습 데이터(Original Data)로부터 랜덤하게 '복원추출'하여
  동일한 사이즈의 데이터셋을 여러개 만들어 앙상블을 구성하는 여러 모델을 학습시키는 방법
• 복원추출에 의해 생성된 새로운 데이터셋을 Bootstrap이라 함.
• 기존 데이터로만 학습 시 해당 epsilon에 종속적이나, 복원추출로 생성된 각 Bootstrap에 의해
  기존의 노이즈와 다른 분포의 변형된 노이즈가 이러한 위험을 방지
  -> 분산이 높다는 건 노이즈 변동에 의한 예측 결과가 크게 변한다는 것을 의미하는데,
  다양한 노이즈의 분포를 가진 Bootstrap들의 '개별 학습 + 결합'으로 노이즈의 영향을 줄임.(분산 감소)

Process of Bagging

• 데이터를 무작위 샘플링하여 여러 하위 집합 생성
• 각 집합별로 별도의 모델 훈련(개별 학습)
• 모델 예측 집계(Averaging for Regression, Voting for Classification)
• 집계된 결과을 바탕으로 최종 예측 수행

+ 참고)

Bootstrap에 포함되지 않은 데이터를 OOB(Out Of Bag) 데이터라 하는데,
각 Bootstrap을 OOB로 검증하여 일반화 성능 향상에 기여할 수 있다.

정리

• 훈련 접근법 : 모델은 다양한 하위 집합에 대해 독립적으로 훈련
• 모델 독립성 : 모델은 독립적이며 병렬 학습
• 오류 처리 : 예측을 평균화하여 분산을 줄임
• 예측 과정 : Averaging or Voting 통해 예측 결합
• 장점
  • 분산이 감소하고, 안정성이 향상된다.
  • 과적합 및 고차원 데이터를 잘 처리한다.
  • 병렬 훈련으로 시간이 절약된다.
• 단점
  • 여러 모델로 인해 해석 저하(해석 가능성이 주요 관심사가 아니면 사용하기 좋음)
  • 기본 모델이 충분히 다양하지 않다면 비효과적

Boosting

• 여러 Week learner를 결합하여 Strong learner를 생성함이 목표
• 배깅과 달리 순차적 학습, 각 후속 모델은 이전 모델에서 발생한 실수를 수정하는 데 중점을 둚.
• 잘못 분류된 인스턴스에 더 높은 가중치를 할당하여 후속 모델이 해당 인스턴스에 주의를 기울이도록 함.

정리

• 훈련 접근법 : 모델은 순차적으로 학습, 후속 모델은 이전 모델의 실수에 중점을 둚.
• 모델 독립성 : 모델은 상호 의존하며 순차 수행
• 오류 처리 : 반복적으로 예측 개선, 잘못 분류된 인스턴스를 중점적으로 함.
• 예측 과정 : 가중치 투표를 통해 예측 결정
• 장점
  • 약한 모델의 정확도를 크게 향상
  • 잘못 분류된 인스턴스에 더 높은 가중치를 할당하여 클래스 불균형 처리
  • 강력한 예측 모델 생성
• 단점
  • 훈련 데이터에 노이즈나 이상치 포함될 경우 Overfitting에 취약
  • 계산 비용과 시간 많이 소요

정확한 성능(Low Bias)은 부스팅, 안정성과 다양성(Low Variance)은 배깅

Q. 앙상블은 단일 결정트리의 Overfitting을 줄이고, 보다 Generalization된 예측을 수행할 수 있다. (Yes/No)
A. Yes