현재 머신러닝 모델들 중 우수한 성능을 보이는 모델은 전부 부스팅 계열이다.
그리고 이 부스팅 계열 모델들 (XGB, lightGBM) 은 의사결정나무라는 알고리즘으로부터 시작을 했는데
이번 포스팅에서는 의사 결정 나무 알고리즘의 분류, 회귀 알고리즘과
파라미터 추정, 해석에 대해 설명해보겠다.
index.
0. 의사 결정 나무와 부스팅 모델들
1. 의사결정나무의 컨셉
2. 의사결정나무의 회귀
1) 분할 방법
2) cost function
3) 분할 변수와 분할점
3. 의사결정나무의 분류
1) 분할 방법
2) cost function - gini index, Cross entropy
3) 분할 변수와 분할점
4) 실제 계산과정
5) 정보이득 information gain +) feature importance
4. 의사결정나무 모델의 종류 : ID3, C4.5, CART
1) ID3
2) C4.5
3) CART
0. 의사 결정 나무와 부스팅 모델들
기초가 되는 컨셉은 의사결정나무
의사 결정나무는 물음표 살인마, 스무고개 같이 여러개의 조건을 통해, 데이터를 분류 또는 수치 예측을 한다.
이 나무가 여러개 있을 때 (Bagging) 랜덤 포래스트
여러개의 나무에서 잘못된 오답에 가중치를 부여해 학습하는게 Gradient Boosting
Gradient Boosting 을 경량화 한게 XGB, Light GBM이다.
1. 의사결정나무의 컨셉
2. 의사결정나무의 회귀
1) 분할 방법
- 아래 우측의 그림처럼 독립 변수(x1, x2)를 기준으로 따라 조건을 설정 (t1 보다 작은지? yes or no)
- 이 과정을 반복하며 데이터를 그룹핑함 - 이렇게 생성된게 끝마디 R1, R2, R3, R4, R5
- 새로운 데이터가 입력되었을 때 조건에 따라서 끝마디까지 내려감, 분류된 범주 값의 평균으로 입력값 예측(yhat = 3)
2) cost function
"실제 y 값" 과 "평균을 통해 추측한 예측값 yhat" 사이의 오차를 최소화 하는게 cost function
3) 분할 변수와 분할점 - grid search 방식
grid search에 가까움, 분할 변수와 분할점 모두 입력, cost function 계산 -> 비용함수가 제일 작은 쪽으로 학습
3. 의사결정나무의 분류
1) 분할 방법
- 아래 우측의 그림처럼 독립 변수(x1, x2)를 기준으로 따라 조건을 설정 (yes or no)
- 이 과정을 반복하며 데이터를 그룹핑함
- 새로 입력된 데이터에 대해서 맵핑된 그룹에서 대다수가 차지하는 클래스의 값으로 예측
2) 불순도를 낮추는 cost function
* 불순도 (impurity)
세가지 모두 특징은 데이터를 분류할 때 분류되는 데이터들의 불순도를 측정하는 목적
클래스가 섞이지 않고 분류가 잘 되었을 수록, 불순도가 낮음
반면 클래스가 섞여 있고, 반반인 경우에는, 불순도가 높음
의사결정나무 모델은 이 불순도가 낮아지는 방향으로 학습을 함
A. Misclassification Rate : 매칭되지 않는 비용을 최소화 하는 것
B. Gini index
지니계수는 통계적 분산 정도를 정량화해서 표현한 값, 0과 1사이의 값을 가짐
지니계수가 높을 수록 잘 분류되지 못한 것
C. Cross entropy
엔트로피(entropy) 는 확률분포가 가지는 정보의 확신도 혹은 정보량을 수치로 표현한 것
- D: 주어진 데이터들의 집합
- k-class set in sample: D에서의 k클래스에 속하는 레코드의 수
- |sample|: 주어진 데이터들의 집합의 데이터 개수
엔트로피 값은 레코드 값 포함 비율에 로그를 적용하고 다시 가중치로 곱한 값을 모두 더한 것이다
엔트로피 값이 작을 수록 잘 분류 된 것이다.
3) 분할 변수와 분할점
- 모든 경우의 수를 다 해보고 어떨 때 Cost function의 값이 작아지는지 다 계산
- 낮아지는 방향으로 분기점 찾고 내려감
4) 실제 계산 과정
좌측 총 오분류율은 가중평균, 우측 j 는 클래스를 의미
지니계수, 엔트로피 둘 다 각 클래스 값 구한 뒤 summation, 둘 다 값이 적을 수록 잘 분류된 것
5) information gain : 특정 변수를 사용했을 때 엔트로피의 감소량
ex. 전체 데이터에서 특정 변수 A를 사용했을 때, 엔트로피를 얼마나 감소했는지
예시 )) 날씨에 따른 야외활동 여부 분류 - cost function : cross entropy
wind 에 대해 information gain을 구하자면
S (=전체 y label 개수) : Yes 9/ No 5
Sfalse (= wind가 false 일 때, ylabel의 개수) : Yes 6 / No 2
Strue (= wind가 true 일 때, ylabel의 개수) : Yes 3 / No 3
IG(S, wind) = 0.048, IG(S, humidity) = 0.151
이 둘을 비교했을 때, humidity가 전체 entropy 값을 더 많이 감소시킨다 → 해당 피쳐가 더 중요하다고 해석 가능.
+) scikit-learn 에서 feature importance 는 information gain 으로 구한다.
지니 계수로
총 샘플이 400개이고, Class가 두 종류, 즉 이항 분류하는 경우입니다.
이 때, 아래 세가지 노드 C1, C1left, C1rightC1, C1left, C1right의 지니 불순도를 계산하자면,
즉 c1 노드들 보다 그 아래 노드의 불순도가 적어지게 된다.
각 피쳐의 중요도를 파악하기 위해선 노드의 중요도 먼저 계산되어야한다.
여기서 말하는 노드의 중요도는 위에서 설명하는 imformation gain 이다.
## 노드 중요도 (imformation gain) 구하기 - cost function : Gini index
### 피쳐 중요도
설명 : i 라는 feature가 있다고 할때,
i 의 feature importance = i feature로 인해서 분기된 노드들의 중요도(information gain) 합 / 전체 노드들의 중요도 합
따라서 scikit-learn 에서 feature importance 는
해당 피쳐로 인해 분기된 노드들의 information gain합 / 전체 분기된 노드들의 information gain 합 이다.
4. 의사결정나무 모델의 종류 : ID3, C4.5, CART
1) ID3 ( Iterative Dichotomiser 3)
- 분류 알고리즘에서만 활용
- 분류에서 cost function은 cross entropy
- entropy를 기반으로 구한 information gain 을 최대화 하는 방향으로 분기
- 이 알고리즘은 독립변수가 모두 범주형일 때만 활용 가능****
2) C4.5 (ID3 알고리즘의 결점을 보완)
- Information gain ratio로 분기
- information gain 의 한계점 :
데이터를 잘게 분해할 수록 더 높은 수치가 나오게됨, 하지만 잘게 분해하는 것이 좋은 분류라고 말하기는 어려움
- 따라서 C4.5에서는 information gain을 수정한 information gain ratio 를 사용
- 위 공식을 통해 잘게 분기해서 information gain 이 높게 나오는 것을 방지함.
- 연속형 변수 활용 가능
- 결측치 포함된 데이터 활용 가능
- 과적합을 방지하기 위한 가지치기
상세 내용은 : https://tyami.github.io/machine%20learning/decision-tree-3-c4_5/
3) CART (Classification and Regression Tree)
- 분류에서는 cost function 을 gini index로 두고 계산 (= 불순도를 gini index로 계산)
- 회귀에서는 cost function을 RSS로 계산
- scikit learn DecisionTreeClassifier 는 CART 기반으로 구현
- 독립변수가 범주형, 연속형 모두 활용 가능함
- binary tree : 여러개의 자식 노드가 아니라 단 두개의 노드로 분기를 함
참고 link :
https://heeya-stupidbutstudying.tistory.com/m/41
https://tyami.github.io/machine%20learning/decision-tree-4-CART/
https://soohee410.github.io/iml_permutation_importance
https://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance.html
https://moondol-ai.tistory.com/401
https://www.youtube.com/watch?v=2Rd4AqmLjfU&list=PLpIPLT0Pf7IoTxTCi2MEQ94MZnHaxrP0j&index=17
댓글