Decision Tree 알고리즘(CART, ID3, C4.5)
1. CART 알고리즘
1.1 CART (Classification and Regression Tree)알고리즘 이란?
지니계수를 이용해서 Tree알고리즘을 구현한 방식입니다.
CART 알고리즘의 특징
1. 자식 노드를 두개만 갖는다.
2. Regression을 구현 할 수 있다. (불순도를 사용하지 않고 오차를 사용)
1.2 지니계수란 ?
지니계수는 불순도를 나타내는 지표 중 하나.
각 확률 간 괴리가 커질 수록 지니계수가 낮아지는 추세를 보임.
예) 이산형 자료에서의 지니계수
Case 1) 가슴통증이 있을때(YES) 심장질환이 있다(YES)/없다(NO) 105/39
Case 2) 가슴통증이 없을때(NO) 심장질환이 있다(YES)/없다(NO) 39/125
이때 두 케이스 지니계수는 1에서 YES의 비율의 제곱과 NO의 비율의 제곱을 뺀것이 됩니다.
따라서,
Case 1 의 지니계수는 1 - (105/144)^2 - (39/144)^2 = 0.395
Case 2 의 지니계수는 1 - (39/164)^2 - (125/164)^2 = 0.336
2. ID3 알고리즘
2.1 ID3 알고리즘 이란?
Iterative Dichotomiser 3의 약자.
불순도를 "엔트로피"를 이용해서 구하는 알고리즘
1. Regression을 구현할수 없다
2. 자식노드를 2개이상 분기 할 수 있다.
2.2 엔트로피란?
엔트로피 = 확률변수의 놀라움을 측정한 값
분기를 결정하는 방식은
분기전 엔트로피(H(S)) - 분기후 엔트로피(H(S,A))로 나타낼 수 있고 이를 Information gain이라고 하며
분기 후 엔트로피는 양쪽 가지로 나눠지는 확률 곱하기 엔트로피의 합으로 구할 수 있습니다.
최적의 의사결정 나무를 만들기 위해선 분기전 엔트로피(H(S)) - 분기후 엔트로피(H(S,A))의 값이 "가장 큰" 변수로 분기합니다.
3. C4.5 알고리즘
3.1 C4.5 알고리즘 이란?
ID3 알고리즘을 개선한 알고리즘
1. 정교한 불순도 지표 (Information gain ratio) 활용 -> IV(Intrinsic value) 를 사용하여 개선
Information gain ratio = IG/IV
2. 범주형 변수 뿐 아니라 연속형 변수를 사용 가능
특정 Threshold를 분기점으로 사용
3. 결측치가 포함된 데이터도 사용 가능
결측치를 뺀 값들로만 엔트로피를 계산
information gain에 전체 데이터 중 결측치가 아닌 값의 비율을 곱하여 계산
Intricsic value는 결측치를 하나의 클래스로 보고 포함해서 계산
4. 과적합을 방지하기 위한 가지치기
분기가 된 이후 가지치기를 진행하는 방식
1) 데이터를 train/test => train/pruning/test 데이터로 나눔
2) training 데이터로 의사결정 나무 생성
3) pruning data와 test data로 가지치기를 수행
4) 분기된 가지의 에러가가 부모노드의 에러보다 클 경우 분기를 진행하지 않고 가지치기
4. 자료형 별 Decision Tree의 학습
4.1 Decision Tree의 학습과정 (이산형 자료)
1. 루트 노드가 될 피쳐를 선택한다.
피쳐를 통해서 분기된 두 자식노드의 지니계수의 가중평균이 가장 낮은 피쳐가 루트노드로 선택 됨
예) 가슴통증에 대한 지니계수의 가중평균은 (144/308)*0.395 + (164/308)*0.336 = 약 0.36
2. 자식 노드들을 이용해서 지니계수가 작아지는 방향으로 데이터를 분리해 나간다.
<과정>
1. 루트노드에서 분기해 나간 자식노드에서도 마찬가지로 지니계수가 가장 적은 피쳐를 이용해서 분기한다.
2. 이 과정을 반복해 나간다.
3. 만약 부모 노드가 자식노드 보다 지니계수가 적다면 분기하지 않는다.
4.2 Decision Tree의 학습과정 (연속형 자료)
1. 연속형 자료를 sort한다.
2. sort된 자료와 인접한 자료간의 평균을 구한다. 예) 0번 자료와 1번자료의 평균
3. 평균을 가지고 평균보다 작은 데이터들이 가지는 타겟값을 이용해서 가장 작은 지니계수를 구해나간다.
4.3 Decision Tree의 학습과정 (순위형 자료)
1. 순위보다 작거나 같은 것을 기준으로 지니계수를 구한다.
2. 가장 높은 순위는 모든 자료를 포함하기 때문에 계산하지 않는다.
4.4 Decision Tree의 학습과정 (범주형 자료)
1. 특정 범주를 골랐을때를 기준으로 지니계수를 구한다.
2. 이떄 범주 or 범주를 골랐을때도 계산한다.
3. 하지만 모든 범주를 골랐을경우는 모든 자료를 포함하기 때문에 계산하지 않는다
0 comments:
댓글 쓰기