Powered by GitBook

cbu03_A_기계학습_트리

신경망/딥러닝/강화 학습은 별도 Chapter에서 정리

1. 결정 트리

ID3 : 시드니대학교 퀸란(Quinlan), 엔트로피+정보이득 개념 활요한 결정트리 알고리즘 중 하나

C4.5(사후가지치기 적용), C5.0, CART(정보이득 대신 지니지수 사용)로 발전
배깅, 부스팅등 보완적 방법 연동

결정트리 문제	분할 척도	특징
분류	정보이득
분류	정보이득비
분류	지니 지수
회귀	표준편차축소(SDR)

1.1 개요

트리 형태로 의사결정 지식을 표현한 것

내부 노드(internal node) : 비교 속성
간선(edge) : 속성 값
단말 노드(terminal node) : 부류(class), 대표값

1.2 알고리즘

분할속성 결정시 엔트로피 + 정보이득 이용

A. 엔트로피

E(y) = y에 대한 정보를 나타내기 위해 평균적으로 알아야할 bit의 갯수
불확실성을 계량화 하기 위한 수학적 도구 : 엔트로피가 낮을수록 확실성 증가
동질적인 정보 측정
- 섞인 정도가 클수록 큰 값
- 원래는 정보량 측정 목적의 척도
공식 :
- $\log_2$ : 0,1 bit로표현하기 때문에 2
- p(c) : 분류 c에 속하는 비율
- - : log함수는 1이하일때 음수 값이므로 이를 막기 위해 (-)를 앞에 붙임??

B. 정보이득

데이터 분류하는 데 해당 속성 A의 효율성을 계량화하기 위한 척도
속성 A를 앎으로써 얻는 엔트로피의 감소 정도
정보 이득이 클수록 확실성이 증가
- G(D,A) : 속성 A의 값을 앎으로써 발생하는 엔트로피의 감소 기대, 전체 E - 특정피쳐 선택시 E
- values(A) : 속성 A가 취할 수 있는 가능한 모든 값들의 집합
- $D_v$ : D의 부분집합으로 속석 A는 값 v를 갖는다. $D_v = \{d \in D | A(d)=v\}$

Step 1. 각 선택에 대한 엔트로피 계산

eg.

Pattern : 사각형(9개) vs. 삼각형(5개)

$p(사각형) = \frac{9}{14} , p(삼각형) = \frac{5}{14}$
엔트로피 $I= -\sum_c p(c) log_2 p(c) \rightarrow -\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$

Step 2. 정보 이득 계산

IG(pattern) = 0.246

Step 3. 각 분류 기준 별로 모두 수행

IG(pattern) = 0.246 IG(Outline) = 0.151 IG(Dot) = 0.048

Step 4. 분할 속성 선택

정보이득이 큰것 선택 : Pattern

1.3 단점 및 해결책

단점: 분할속성 척도로 정보이득(IG)사용시 속성값이 많은것 선호

속성값이 많으면 데이터집합을 많은 부분집합으로 분할, 작은 부분집합은 동질적인 경향

해결책 : 개선된 척도 사용

정보 이득비
지니 지수

A. 개선된 척도 : 정보 이득비

속성값이 많은 속성에 패널티줌 = I(A)로 나누어 줌

$GainRation(A) = \frac{IG(A)}{I(A)} = \frac{I-I_{res}(A)}{I(A)}$

패널 I(A) = $-\sum_v p(v)log_2(p(v))$

속성 A의 속성값을 부류로 간주 하여 계산된 엔트로피
속성값이 많을수록 커지는 경향

B. 지니 지수(Gini Index)

Step 1. 지니값 계산

두 확률의 곲의 총합으로 계산 : Gini = $\sum p(i)p(j)$

예시] Pattern : 사각형(9개) vs. 삼각형(5개) $p(사각형) = \frac{9}{14} , p(삼각형) = \frac{5}{14} \rightarrow Gini = \frac{9}{14} \times \frac{5}{14} = 0.230$

Step 2. 속성 A에 대한 지니 지수값 가중 평균

Gini(A) = $\sum_v p(v) \sum_{i \neq j}p(i|v)p(j|v)$

Step 3. 지니 지수 이득

GiniGaim(A) = Gini - Gini(A)

1.4 다양한 결정 트리 알고리즘

ID3 알고리즘

범주형(categorical) 속성값을 갖는 데이터에 대한 결정트리 학습
예. PlayTennis, 삼각형/사각형 문제

C4.5 알고리즘

범주형 속성값과 수치형 속성값을 갖는 데이터로 부터 결정트리 학습
ID3를 개선한 알고리즘

C5.0 알고리즘

C4.5를 개선한 알고리즘

CART 알고리즘

수치형 속성을 갖는 데이터에 대해 적용

1.5 결정트리를 이용한 회귀분석

차이점

단말 노드가 분류가 아닌 수치값

분할 척도 선택

표준편차 축소(Reduction of standard deviation,SDR)을 최대로 하는 속성 선택
SDR = SD-SD(A)
- SD = 표준편차
- SD(A) = 속성 A를 기준으로 분할 후의 부분 집합별 표준표차의 가중 평균

트리구조에서는 Overfitting방지를 위한 Regularization을 이용하지 못한다.

이러한 이유로 앙상블(ensemble)을 이용하여 overfitting을 방지 한다.

가지치기 기법을 통해 Overfitting을 방지 한다.

results matching ""

No results matching ""