Catboost 기본부터 알아보기

Catboost

Boosting algorithm이란?

머신러닝 앙상블 기법중 하나로 약한 학습기 여러개를 순차적으로 여러개 결합하여 예측과 분류의 성능을 높이는 알고리즘

여러개의 알고리즘이 순차적으로 학습 예측 하면서 이전에 학습한 알고리즘의 예측이 틀린 데이터를 올바르게 예측할수 있도록 다음알고리즘에 가중치를 부여하여 학습과 예측을 진행하는 방식

앙상블 : 여러 단순한 모델을 결합하여 정확한 모델을 만드는 방법

의사 결정 트리(Decision Tree)

• 일련의 분류 규칙을 통해 데이터를 분류, 회귀하는 지도학습모델, 결과 모델이 Tree 구조이다. 특정 기준에 따라 데이터를 구분하게 되며 한번의 분기 마다 변수영역을 두개로 구분한다. 여기서 나온 질문이나 정답을 노드(Node)라고 한다.
• 의사 결정 트리의 기본 아이디어는 말단노드가 가장 섞이지 않은 상태에서 분류되는 복잡성(Entropy)가 가장 낮도록 만드는 것이 핵심이다.
• 불순도(impurity)
  • 의사 결정 트리에서 분기 기준을 선택하기 위해서는 불순도라는 개념을 사용한다. 이는 복잡성을 의미하며 범주 안에 서로 다른 데이터가 얼마나 섞여있는지를 의미한다. 다양한 범주의 개채가 섞여 있을수록 불순도가 높아진다.
  • 분기 기준을 정할때 현재 노드보다 자식 노드의 불순도가 더 낮도록 설정해야한다.
  • 그래서 자식노드가 부모 노드에 비해 불순도가 낮아진 정도를 정보 획득(Information Gain) 이라고 한다.
  • 불순도를 정량적으로 평가 할수 있는 함수는 대표적으로 2가지 종류가 있다.
• 지니 지수(Gini)

$$
I(A) = 1-\Sigma_{k=1}^m p_k^2 ; [range: 0 \sim 0.5]
$$

• 엔트로피 지수(Entropy)
• $$
  E = -\Sigma_{i=1}^{k} p_i\log_2(p_i) ; [range: 0 \sim 1]
  $$
• 정보 획득
  • 만일 불순도가 1인 상태에서 0.7로 바뀌게 되면 정보획득은 0.3이다
  • 의사 결정 트리의 구성단계
  • 1. Root노드의 불순도 계산
    2. 나머지 속성에 대해 자식노드의 불순도 계산
    3. 각 속성에 대한 정보획득 값이 최대가 되는 분기 조건을 찾아 분기
    4. 모든 leaf 노드의 불순도가 0이 될때까지 2~3 과정 수행
  • 모든 말단 노드의 불순도가 0이 되면 이러한 상황을 Full tree(최대 트리)를 형성하게 됨. 그런데 이런 최대트리 상황은 데이터의 과적합 문제(Overfitting)를 일으켜 일반화의 성능이 떨어지게 된다.
  • 따라서 형성된 결정트리에 대해 가지치기(Pruning)을 수행해 일반화 성능을 올림
• 의사결정 트리의 가지치기 비용함수
  • 비용함수는 가설이 얼마나 정확한지 판단하는 기준을 책정해주는 함수로 의사결정트리에서 일반화를 위한 가지치기를 통해 최대한 비용이 가장 작은 가지치기를 찾는것을 목적으로 한다. 그 정의는 다음과 같다.
  $$
  CC(T) = Err(T) + α × L(T)
  $$
  • CC(T) = 의사 결정 트리의 비용복잡도
  • ERR(T) = 검증 데이터에 대한 오분류율
  • Alpha = ERR과 L의 결합 가중치
  • L(T) = terminal node의 수(트리구조의 복잡도)
• 데이터 전처리와 수치형 변수 범주형 범주를 한꺼번에 다룰수 있다는 장점이 있다.
• 과적합으로 인해 알고리즘의 성능이 떨어징수도 있도 한번에 하나의 변수만 고려하기 때문에 변수의 상호작용을 파악하기 어렵다. 그리고 데이터의 변동에 민감하다.
• 이러한 의사 결정트리의 문제점을 보안한것이 "Random forest"이다.

랜덤 포레스트(Random forest)

의사 결정트리는 과적합 문제가 발생할 가능성이 크다. 그래서 의사 결정 트리에서는 Puruning을 통해 트리의 최대 높이를 제한해 과적합 문제를 피하려고 하지만 한계가 있다. 랜덤 포레스트는 좀더 일반화된 트리를 만드는 것에 목적이 있다.

• Bagging: 트리를 만들때 trainging Set의 부분집합을 활용하여 형성하는 것. 모든 트리는 서로 다른 데이터를 바탕으로 형성하지만 training set의 부분집합이다. 부분집합을 형성할때에는 중복을 허용한다.
• Bagging Feature: 데이터의 Feature 또한 부분 집합으로 활용한다. 일반적으로 M^{1/2}의 개수만큼 선택하며 트리가 만들어 질때까지 해당과정을 반복한다. 그래서 만들어진 트리중 information gain이 가장 높은 feature을 선택하여 데이터를 분류한다.
• classify: Bagging에서 형성된 여러개의 트리를 통해 임의의 데이터의 분류 결과 값 경향성을 확인하고 최종적으로 결과를 분류함.

AdaBoost(Adaptive Boost)

관측치들에 가중치를 더하면서 동작하는 모델. 분류하기 어려운 데이터에는 가중치를 더하고 잘 분류되어진 데이터에는 가중치를 덜하는 방식으로 부스팅을 수행한다. 약한 학습기(weak Learner)로서 의사 결정 트리(Decision Tree)를 사용한다. AdaBoost에서는 노드 2개짜리 tree model(stump)을 이용해 부스팅을 진행한다.

1. 전체 데이터 random sampling
2. 모든 sample 데이터 가중치 초기화
3. weak learner를 만들고 학습의 error를 계산해 데이터의 가중치와 모델 가중치를 확인한다.
4. error를 바탕으로한 데이터 가중치로 업데이트한다.
5. 데이터 가중치를 기반으로 모델 가중치를 계산한다.
6. 3~5 번 과정을 충분히 반복한다.
7. 모델 가중치를 Normalize 하고 최종모델을 도출한다.

$$
W_i=1/n, i=1,\ldots,n
$$$$
err_m=\Sigma_{i=1}^{n}W_i
$$$$
c_m=\frac{1}{2}\log((1-err_m)/err_m)
$$$$
w_i =w_i\cdot exp(-c_m\cdot y_i \cdot \hat f_m(x_i))
$$

Gradient Boosting(GBM)

• Residual fitting은 아주 간단한 모델 A를 통해 y를 예특하고 생긴 잔차(Residual)을 다시 B모델을 통해 예측하는것이다. 이를 통해 A+B모델을 통해 y을 예측하면 A보다 나은 B모델을 만들수 있고 점차 잔차가 줄어들며 trainig set을 잘 설명해주는 예측 모델을 만들수 있게 된다.
• 해당 모델을 통해 bias를 줄일수 있으나 과적합의 위험이 있기 때문에 smapling, penaliaing, regularization 같은 테크닉을 이용해 사용하는 것이 보편적이다.
• penaliaing: 목적성을 띄기 위해서 가중치를 주는 기술을 뜻한다.
• regularization: 일종의 패널티 조건으로서 복잡한 쪽 보다 단순한 쪽을 선택하게 함으로서 일반적으로 더 좋은 학습결과를 하게 만드는 테크닉이다.
• Residual fitting과 Gradient의 관계는 Residual(잔차)를 만약 loss funtion를 sqaured error라고 한다면 이를 순차적으로 다음 모델로 넘겼을때 다음 residual이 negative gradient가 된다고 한다.
• $$
  j(y_i,f(x_i))=\frac{1}{2}(y_i-f(x_i))^2
  $$
• $$
  \frac{\partial j(y_i,f(x_i))}{\partial f(x_i)}=\frac{\partial[\frac{1}{2}(y_i-f(x_i))^2]}{\partial f(x_i)}=f(x_i)-y_i=-(y_i-f(x_i))
  $$
• 이렇듯 GB에서는 다음모델을 만들때 negative gradient를 이용해 만들기 때문에 gradient boosting이라고 한다.
• negative gradient는 직관적으로 어떤 데이터 포인트에서 loss fuction이 줄어들기 위해 f(x)로 가려는 방향이가. 이 방향에서 새로운 모델을 fitting해서 이전 모델과 결합하면 f(x)는 loss fuction이 줄어드는 방향으로 업데이트 되는 것이다. 그래서 어러한 아이디어를 Gradient Boosting이라고 부르는 것이다.
• 1. 최초값을 weight의 평균값으로 예측
  2. 예측값과 실제값 사이의 오차 구하기
  3. 계산된 오차를 다른 데이터셋 Feature를 가지고 Tree를 만들기
  4. 분류된 값들은 평균을 매김(트리완성)
  5. 완성된 트리에 새 데이터를 넣고 나온 wieght값이랑 이전에 평균 weight값이랑 더한다. 이때 과적합을 피하기 위해 learning rate를 곱해준 만큼 더해서 새로운 residaul을 만들어준다.
  6. 남은 데이터들도 5번과정을 수행하고 나온 residual 로 업데이트 해준다.
  7. 2~5본 과정을 반복하면서 점점 오차다 줄어들고 Hight Variance를 피하면서 천천히 학습을 해나간다.
• GB 또한 완전히 과적합 문제에서 자유롭지 못하며 수행시간이 느리다는 단점이 있다.

XGBoost(XGB)

• GB가 병렬 학습이 지원되도록 구현한 알고리즘으로 회귀 문제와 분류 문제를 모두 지원하고 효율이 좋다.
• 구현 라이브러리 설명 : https://wooono.tistory.com/97

Light GBM

• 파라미터 튜닝이 번거로운 XGB를 보안하기 위해 만들어진 알고리즘으로 성능을 유지한 채 학습시간을 상당히 단축시킨 모델이다.
• 기존의 GB는 균형트리방식(Level wise)을 사용해 학습을 진행했다. 이는 균형잡힌 트리를 생성하면서 깊이를 최소화 할수 있다는 장점이 있고 과적합에 더 강하지만 균형을 맞추는 과정에서 더 시간이 걸린다는 문제가 있다
• 그래서 LightGBM은 리프 중심 트리 분할(Leaf wise) 방식을 사용해 트리의 균형을 맞추지 않고 최대 손실값(max leaf loss)를 가지는 리프 노드를 계속 분할래서 깊고 비대칭적인 트리를 만든다. 이와 같은 방식을 통해 균형 트리 방식보다 예측 손실 오류를 최소화 할수 있다.
• 구현 라이르러리 설명 : https://kimdingko-world.tistory.com/184
• 깊이가 깊은 트리를 형성하기에 하이퍼 파라미터 설정시 최대 깊이 설정이 중요하다.
• 약간 그리디 알고리즘 느낌이다..

CatBoost

• CatBoost의 경우 GB와 같은 균형트리방식(Level wise)을 사용해 학습을 진행한다.
• Order Boosting: 데이터 셋의 일부를 뽑아 잔차를 계산하고 모델을 만든다. 그리고 해당 모델로 나머지 데이터의 잔차를 예측하고 예측한 값을 가용해 업데이트 한다.
• Random Permutaion: 데이터를 셔플링한 후 데이터를 뽑아내고 트리를 다각적으로 볼수 있도록한다.
• Orderd Target Encoding: 범주형 변수를 인코딩 할때 임의의 선정된 데이터 외에 선정되지 못한 데이터의 타겟값까지도 엔코딩 되는 현상인 Data leakage를 피하기 한다.그래서 이전 데이터들의 타겟값을 기억해 두었다가 이전에 사용된 데이터의 타겟값만 업데이트 하는 기법이다.
• Encoding 관련 자료 : https://dailyheumsi.tistory.com/120
• Categorical Feauture Combinations : 서로 다른 두개의 카테고리가 명확하게 서로다른 성질을 보이는 경우 두개의 카테고리를 하나로 합쳐 생각한다.
• One-hot Encoding : Target Encoding이 비효율 적인 범주형 변수를 처리할 때는 One-hot Encoding을 수행하는 기법
• One-hot Encoding: 범주형 변수의 출현빈도로 변환하는 엔코딩 방식을 말한다. (범주 -> 수)
• Optimized Parameter tuning : XDB, light GBM의 경우 파라미터 설정이 까다로우나 CatBoost는 내부 알고리즘을 이용해 이러한 까다로운 파라미터 설정을 안해도 결과에 영향을 주지 않는다.
• 대신 희소 행렬은 처리 하지 못하며 데이터가 대부분 수치형 변수 일경우 CatBoost보다 light GBM이 유리하다고 한다.