[Machine Learning] 의사결정나무 (지도학습 / 분류)
https://piscesue0317.tistory.com/27
[Data Science] 지도학습과 비지도학습이란 ?
데이터 마이닝이란 대량의 데이터를 탐색하고 분석하여 의미 있는 패턴과 규칙을 발견하는 것입니다. 또한, 예측이 주된 목적입니다. 이러한 데이터 마이닝에는 다양한 기법들이 존재합니다.
piscesue0317.tistory.com
지도학습이란 y = f(x) 에 대해
입력변수 (X) 와 출력변수 (Y)의 관계에 대하여 모델링하는 것입니다.
즉, Y에 대해 예측하거나 분류하는 문제를 다룹니다.
오른쪽 그림과 같이
변수들로 기준을 만들고 이것을 통하여
샘플을 분류하고, 분류된 집단의 성질을 통하여 주정하는 모형을
'의사결정나무'라고 합니다.
우리는 이 의사결정나무를
통해 데이터를 분류 혹은 예측합니다.
먼저, 의사결정나무의 구성요소에 대해
알아보겠습니다.
부모마디 : 자식마디의 상위마디
자식마디 : 하라의 마디로부터 분리되어 나간 2개 이상의 마디들
뿌리마디 : 나무구조가 시작되는 마디
끝마디 : 각 나무줄기의 끝에 위치하고 있는 마디
의사결정나무 종류에는
총 2가지가 있습니다.
이 때문에 의사결정나무를
CART (Classfication and Regression Tree) 라고
부르기도 합니다.
회귀나무 (Regression Tree) 는 목표변수가 수치형인 경우이며
분류나무 (Classification Tree) 는 목표변수가 범주형인 경우입니다.
의사결정 나무 장점
- 해석의 용이성 : 나무구조에 표현되기 때문에 모형을 쉽게 이해 가능
- 빠른 계산 속도
- 비모수적 추정 : 선형성, 정규성, 등분산성 등의 가정 불필요 → 따라서 다수의 샘플 필요
의사결정 나무 단점
- 설명변수와 목표변수 간의 어려운 관계파악 : 설명 변수가 일정량 증가할 때 목표변수에 미치는 영향을 정량화 불가
- 파악하기 어려운 교호작용 : 변수를 하나씩 살펴보고 가지를 분리하기 때문에 교호작용의 영향 반영 불가 ex ) y = f ( x ) 일 때, x가 1 증가하면 y도 x 만큼 증가
Classification Tree
STEP 1 . 목표변수를 잘 분리하는 독립변수 선택
독립변수가 범주형 변수의 경우,
분할될 수 있는 모든 가능한 범주를 탐색한 후,
불순도 값을 계산합니다.
만약 범주가 여러 개라면,
아래와 같은 방식으로 분할하여야 합니다.
ex ) 범주 : A, B, C
{A} and {B, C}
{B} and {A, C}
{C} and {A, B}
독립변수가 연속형 변수의 경우,
연속적 값 사이의 중심점을 찾습니다.
예를 들어 변숫값이 14.0, 14.8, 16.0 인 경우,
첫 분할 기준점은 14.4 (14.0과 14.8 사이의 가운데)
두 번째 분할 기준점은 15.4 (14.8과 16.0 사이의 가운데) 로 지정해 줍니다.
그 후, 레코드를 변수 > 14.4 와 변수 < 14.4 로 분할하여
불순도를 측정해 최적의 분리 기준을 정합니다.
STEP 2. 최적의 의사결정나무 분리지점 선택
의사결정나무를 분할할 때는 정량적 지표인
불순도를 이용합니다.
모든 가능한 분할에 대해
불순도 값을 계산하여 불순도가 가장 많이
감소하는 변수를 선택합니다.
이때, 불순도란 여러 가지의 클래스가
섞여 있는 정도를 말합니다.
반대로 순수도는 같은 클래스끼리
얼마나 많이 포함되어 있는지를 말합니다.
예를 들어,
49%,51%로 분할한 A와
95% 5%로 분류한 B가 있을 때,
B가 순수도가 더 높다라고 표현할 수 있습니다.
위의 개념에 대입하자면
B를 선택하는 것이 좋을 것 같습니다.
불순도 측정 1. 지니지수
위 식은 m개의 관측치를
포함하는 직사각형 A에 대한 지니지수입니다.
모든 관측치가 같은 클래스에 속할 때,
I (A) = 1 - 1 = 0 입니다.
각 클래스에 속한 관측치들의 비율이 같을 때,
I (A) = 1 - (0.5) = 0.5 입니다.
지니지수는 0과 0.5 사이에 존재하며
0에 가까울수록 좋습니다.
* Pk : 직사각형 A내에서 클래서 k에 속하는 관측치의 비율
위 예시로 지니지수를 계산해 보도록 하겠습니다.
위 식은 m개의 관측치를 포함하는 d개의 직사각형이
존재할 때의 지니지수입니다.
이렇게 분할하는 경우,
지니지수의 감소량이 얻어집니다.
예시를 통해 위 식을 계산해보도록 하겠습니다.
이렇게 분할을 통해 얻어지는 지니지수의 감소량은
0.49 - 0.36 = 0.13 입니다.
불순도 측정 2. 엔트로피 지수
위 식은 m개의 관측치를
포함하는 직사각형 A에 대한 엔트로피입니다.
모든 관측치가 같은 클래스에 속할 때,
Entropy (A) = 0 입니다.
혹은 각 클래스에 속한 관측치들의 비율이 같을 때
Entropy (A) = log2(m) 입니다.
엔트로피 값은 이처럼 0과 log2(m)
사이에 존재하며 0에 가까울수록 좋습니다.
* Pk : 직사각형 A내에서 클래서 k에 속하는 관측치의 비율
위 예시로 엔트로피지수를 계산해 보도록 하겠습니다.
위 식은 m개의 관측치를 포함하는 d개의 직사각형이
존재할 때의 엔트로피 지수입니다.
또한, 이렇게 분할하는 경우,
엔트로피의 감소량이 얻어집니다.
예시를 통해 위 식을 계산해보도록 하겠습니다.
이렇게 분할을 통해 얻어지는 엔트로피의 감소량은
0.98 - 0.78 = 0.2 입니다.
STEP 3. 의사결정나무 생성
그럼 언제까지 분리를 해나가야 하는 걸까요?
따라서 의사결정나무에는
정지규칙이라는 것이 존재합니다.
1. Relative reduction
위와 같은 정량적인 불순도 지표들을 분리기준으로 사용하는 경우엔,
분석자가 지정한 값보다 감소량이 큰 설명변수가
더 이상 없으면 정지합니다.
2. Minimum number of cases
마디에 포함되어 있는 관측수가
분석자가 미리 지정한 숫자보다 작으면 정지합니다.
3. Maximum Tree Depth
의사결정나무의 깊이
(뿌리마디로부터 시작하여 몇 단계까지 분리를 계속할 것인지) 를
바탕으로 정지합니다.
이렇게 의사결정나무의 성장을 정지시키는 원칙은
자식마디들의 순수도가 100프로일 때입니다.
하지만 이 원칙은 데이터를 과적합할 수 있으며
이는 새로운 데이터에 대한 예측 정확성을 떨어뜨립니다.
따라서 우리는 가지치기라는 것을
해야합니다.
STEP 4. 부적절한 나뭇가지 제거 (가지치기)
나무를 완전 성장시킨 후,
검증데이터에 대한 오분류율을 측정해 보면
어디서부터 과적합이 일어나는지를
알 수 있습니다.
위 그래프를 보자면
일정 지점을 지나면서 오분류율이 다시 증가하기 시작하는데,
그 지점부터가 과적합이라고 판단합니다.
따라서 해당 지점이 가장 최적의 분리 지점이며
그 후로는 가지치기를 진행합니다.
STEP 5. 최종 의사결정나무 선정
↓
STEP 6. 분류규칙 (Rule) 도출
의사결정나무가 완성되었을 때,
우리는 아래와 같은 분류규칙을 도출할 수 있습니다.
IF (Lot size < 19) AND IF (Income < 84.75) THEN Non-Owner
IF (Lot size < 19) AND IF (Income > 84.75) THEN owner
IF (Lot size > 19) AND IF (Income < 57.15) THEN non-own
IF (Lot size > 19) AND IF (Income > 57.15) THEN own
STEP 7. 분류 및 예측
분류나무에서는 예측값을
다수결 투표를 통해 결정합니다.
위 예시의 경우 물음표에 들어갈 색깔은
파란색이 되겠습니다.