6. 비선형분류모형1
의사결정나무
의사결정나무
: 널리 사용되는 분류기 : 복잡한 데이터에 대하여 좋은 성느을 보임
: 학습데이터로부터 '설명가능한' 분류기준을 결정
-> 이게 왜? : 많은 머신러닝 모델이 '블랙박스' (설명불가능함)
: 데이터를 '뿌리'로부터 말단의 '잎'까지 순차적 분류
의사결정나무 알고리즘
: Hunt's algorithm
: CART
: ID3, C4.5
: SLIQ, SPRINT
의사결정나무 분류
: Rule based 알고리즘
: 기준을 자동으로 만들어 주는 것
: 같은 데이터의 분류에 대하여 하나 이상의 서로 다른 트리 학습 가능!
: training데이터를 이용해 tree모델을 만들고, test데이터에 모델을 적합시킨다!
=> 그럼, 의사결정나무를 어떻게 만드냐!!
Hunt's Algorithm
Dt : node t에 있는 학습 데이터의 수
일반적인 절차
1) 만일, Dt에 속한 데이터가 모두 하나의 클래스 Yt에 속해있다면, t는 Yt클래스의 leaf node
2) 만일, Dt에 속한 데이터가 존재하지 않으면, t는 기본 클래스 Yd(default)의 leaf node
3) 만일, Dt에 속한 데이터가 둘 이상의 클래스일 경우, 더 작은 부분집합으로 분리
Tree Induction
Greedt strategy(탐욕적 전략)
- 하나의 입력변수를 이용해서 특정 최적 기준을 만족하는 분리조건을 탐색
어떻게 분리할 건지?
- 어떻게 분리기준 변수를 선택할 건지?
- 최적의 분리는 무엇인지?
- 언제까지 분리할 건지?
어떻게 분리할 것인가 ! (type과 분리수에 따라서!)
type : 명목형변수/ 순서형변수 /연속형변수
분리의수 : 2waysplit / multiway split
Nominal Atrributes(명목형 변수)
- Multi way - 서로 다른 값 모두 사용(각 카테고리의 개수만큼)
- Binary split - 값들을 두개의 부분집합 => 최적의 분리기준 탐색 필요 (대부분 계산상의 효율 때문에 이거 선택 많음! )
Ordinal Attributes (순서형 변수)
- Multi-way split : 서로 다른 값을 모두 사용하여 분리
- Binary split : 두개의 부분집합, 최적의 분리기준 탐색필요
- Wrond split : 순서가 섞이면 안됨!
Continous Attributes(연속형 변수)
- 이산화를 통해서 순서형 변수로 재구성
- Binary split > Multi-way split
최적분리기준 결정방법
Greedy approach : 균질(homogeneous)한 class분포가 선호됨
=> 측정기준: 얼마나 homogeneous 한가!
불순도(impurity)에 대한 측정이 필요합
- Gini index/ Entrophy / Misclassification error
Gini index
Gini index 개념
- Gini(t) = 1- 시그마[p(j|t)]^2
- p(j|t) = node t에서 클래스 j의 상대빈도
- 최대값 : 1-1/n (Gini index 높음)
: 데이터들이 모든 클래스에 균일하게 분포할 때! (non-homogenous / impurity 높음)
- 최소값 : 0 (Gini index 낮음)
: 모든 데이터가 하나의 클래스에 속해있을 때 (homogenous / impurity 낮음)
- 두개로 분리하는 경우,
: 가중치로 인하여 더 크고 (gain 이 클수록 좋은 분리)
: 순도가 높은 분리를 탐색 !
: 서로 다른 값마다, 각 클래스에 속하는 수를 탐색해 count matrix구성!
- multi way split경우,
: impurity 낮춤, 다만 오버피팅 가능성 높음
Gini index 분류
- 일반적으로 하나의 값을 이용해 2-waysplit
- 다양한 분리기준 값이 존재
- 각 분리기준에 해당하는 count matrix가 존재
- 최적의 분리 기준값 v를 선택하는 단순한 방법
: 각 v 마다 countmatrix계산 후 지니인덱스 => 많은 계산 시간!!
=> 현실적인 계산은 각 입력변수마다 v를 설정해보기, count matrix의 v값을 그렇게 정리
Entrophy
entrophy
- 얼마나 무질서하냐, entrophy가 크면클수록 서로다른 class가 많이 섞여 있다는 뜻
- entrophy(t) = -시그마 p(j|t)logp(j|t)
- 최대값 : lognc : eplxjemfdl ahems zmffotmdp rbsdlfgkrp qnsvhgkf Eo
- 최소값: 0 : 모든 데이터가 하나의 클래스에 속해이쓸때
=> GINI기반이랑 비슷
Information Gain
- 분리를 통한 엔트로피의 감소량 추정, Gain이 가장 높아지도록
(엔트로피 감소량이 많아지도록) 분리
- ID3, C4.5
- Disadvantage : 상대적으로 많은 분리를 하려는 경향 / 작고 순도가 높은 부분집합 추구
Gain Ratio : Gain/SplitINFO
- 상대적 GAIN을 이ㅛ하여 작고 많은 분리 제어 가능
- C4.5에 이용
Misclassification Error
MisClassification Error
- Error(t) = 1-maxP(i|t)
- 가장 많은 비율을 1에서 뺌
- node에서 오분류율 탐지
- 최대값: 1-1/n : 데이터들이 모든 클래스에 균일하게 분포할 때
- 최소값 : 0, 모든 데이터가 하나의 클래스에 속해있을 때
- 대신, GAIN이 없음
Tree Induction 의 중단
1) 한 노드안의 데이터가 모두 같은 클래스에 속할 경우 분리를 중단
2) 한 노드안의 데이터 입력 값이 모두 비슷한 경우 분리를 중단
3) 조기종료 (overfitting 방지) => b/c 일반화오류 떨어지는 것 방지위해!
의사결정나무 요약
1) 학습이 쉽고 빠름
2) 새로운 데이터에 대한 분류가 빠름
3) 작은 크기의 의사결정나무에 대해 설명 및 이해가 쉬움
4) 많은 데이터셋에서 우수한 성능을 보임
decision boundary
: 의사결정나무는 축에 평행한 decision boundary
overfitting
- 크고 복잡해질수록 overfitting
- Training error를 통해서 구성된 tree가 새로운 데이터에 잘 작동될지 모름
- error측정 기준 필요
1) Optimistic approach = e(t)
2) Pessimistic approach = 각 리프노드의 num를 곱해줌.
3) Reduced error pruning (REP)
: 트레이닝 일부를 가지고 Validation error(generalization error) 가 작아지도록 트리 만들기.
- occam's Razor
: 두 모델이 유사한 genralization을 가질 경우, 단순한 모델 선호
: 복잡한 모델의 경우 우ㅎ연히 현재 샘플된데이터의 에러에 의해 적합되었을 확률이 높음
: 모델 평가시, 모델의 복잡도도 반드시 고려!
over fitting 의 해결
Pre-Pruning
- 트리가 구성되기 전에 알고리즘 중단
- 한 노드가 같은 클래스, 입력값이 같을 때
- 추가 제한 조건
: 사전의 정의 된 일정 수 이하
: 데이터 클래스의 분포가 모든 입력변수에 독립
: 어떤 분리도 불순도 수치를 개선하지 못할때
Post-Pruning
- 다 만들고 가지치기
- 가지치기에 의해 generalization error개선시, 유지.
=> sub tree가 ㅣㄷㅁㄹnode로 대체됨.
- 새로운 leaf node의 클래스 라베른 가장 많은 수
