[ML] Decision Tree

About this offer

공부 기록 기본 프로세스 의사결정나무 - 데이터를 뿌리부터 잎까지 순차적 으로 분기함 구성 성분(헷갈리는 것만 정리함) 끝 마디: 자식 마디가 없는 마디 중간 마디: 부모/자식 둘다 있는 마디 가지: 뿌리 마디에서 끝 마디까지 중 가능한 경로 중 하나 깊이: 가지 중 가장 많은 마디의 수 분류와 회귀 둘다 사용 가능 CART 알고리즘: 회귀 가능한 분할을 모두 탐색한다 가능한 분할 중 하나를 고정한다. (평균으로 구역 나눔) 고정된 분할에 대해 예측값을 계산한다. 오차가 더 작은 분할을 선택한다. ( = 분산 감소량이 많다) 분류 가능한 분할은 정해져 있다. 고정된 분할에 대해 예측값 계산한다. 오차가 더 작은 분할을 선택한다. 의사결정나무에서 결정해야 할 것 어떤 속성으로 분할할 것인가? 언제까지 분할할 것인가? (default: 분류 후 집합이 한 클래스로 몰리면 종료) 분할 속성 선택 ; 어떤 속성으로 분할할 것인가? Regression : 가장 분산 감소량이 많은 속성 선택 → 표준편차를 줄이는 방향으로 모든 피처에 대해서 $S(T, X)$ 구하고, 가장 분산 감소량이 많은 $X$를 선택함 $S(T, X) = \sum\limits_{c\in X}P(c)S(c)$ Classification : 가장 정보 이득이 큰 속성 선택 (*정보 이득 계산, 지니계수 계산 시험에 나옴 바오피셜) 정보 엔트로피 샘플 집합의 순도 측정 샘플 집합 D의 속성 값 중 k번째 클래스 샘플이 차지하는 비율 p_k 일 때 정보 엔트로피 $$ Ent(D)= -\sum\limits_{k=1}^{|Y|}p_klog_2p_k $$ Ent(D)의 값이 작을수록 D의 순도는 높아짐 → 작을수록 좋은 값 순도가 100%: 정보 엔트로피 = 0 순도가 50%: 정보 엔트로피 = 1 ⇒ 제일 헷갈리는 상태 정보 이득: Ent(D)가 줄어든 정도 $$ Gain(D,a) = Ent(D)-\sum\limits_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v) $$ Ent(D): 원래 엔트로피 → 안나뉘어져 있을 때 ⇒ 가장 정보 이득 큰 속성을 선택! (ID3의 분할 속성 선택 방법)* 정보 이득이 크다 == 불확실성이 크게 줄어든다 ID3 루트노드에서 시작해서 모든 속성(*feature)에 대해 정보이득 계산 가장 정보이득이 큰 속성을 기준으로 분할 각 자식 노드에서 과정 재귀적으로 반복함 정보 이득율 정보 이득 규칙은 취할 수 있는 값의 수가 비교적 많은 속성에 유리함. → 이렇게 되면 샘플 하나하나가 고유한 값 하나씩에 대응할 수 있음 ⇒ 정보 이득은 증가하지만 오버피팅 위험 $Gain\ ratio (D,a) = \frac {Gain(D, a)}{IV(a)}$ $IV = -\sum\limits_{v=1}^V \frac {|D^v|}{|D|}log_2\frac {|D^v|}{|D|}$ 속성 a가 취할 수 있는 값의 수가 많아질 수록 IV의 값이 커짐 → 패널티 효과 지니계수 (얼마나 불평등한가?) 집합 내 순도를 측정하는 다른 방법 지니값: 집합 D에서 임의의 두 샘플을 골랐을 때, (복원 추출 했을 때) 고른 두 샘플이 서로 다른 클래스일 확률. $$ Gini(D) =\sum\limits_{k=1}^{|Y|}\sum\limits_{k'\ne k}p_kp_{k'} = 1-\sum\limits_{k=1}^{|Y|}p_k^2 $$ 지니값이 작을수록 D의 순도가 높음 → 지니값은 작을수록 좋다. 지니계수 $$ Gini\ index(D) =\sum\limits_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v) $$ 가지치기 ; ‘멈춘다’ 는 의미 의사결정나무의 과적합 과도한 반복 → 가지 수 많이 만들어냄 → 훈련 셋 자체를 기억해버리면 안됨 사전 가지치기 분할 전 미리 예측하여 노드 분할이 트리의 일반화 성능을 향상시킬 수 있다면 분할, 아니면 분할 정지 *일반화 성능: 훈련 데이터셋이 아닌 검증 데이터셋으로 알 수 있음 장점 의사결정트리가 많은 가지를 뻗지 못하도록 함. 훈련 시간과 테스트 시간 크게 줄여줌 단점 일반화 성능을 잠시 낮추더라도 계속되는 분할을 통해 일반화 성능 향상시킬 가능성 사전에 차단 과소적합 위험 증가 사후 가지치기 훈련 셋 전체에 대해 트리를 만들고, 상향식으로 위 노드가 터미널 노드(덜 잘랐을 때의 노드)로 바뀌었을 때 일반화 성능이 향상된다면 하위 트리 삭제 과소 적합의 위험이 낮고, 일반화 성능 높음

Offer details

Provider

velog

Source

velog-rss

Score

54.37

Confidence

49%