어떤 기준으로 노드를 놓아야하며, 어떤 노드를 가장 위에 놓아야하는 가?
정보획득량
어떤 사건이 얼마만큼의 정보를 줄 수 있는지를 수치화한 값.
정보획득량을 계산하기 위해선 엔트로피를 이해해야함.
정보 함수
정보의 가치를 반환하는데 발생할 확률이 작은 사건일 수록 정보의 가치가 크고, 반대로 발생할 확률이 클 수록 정보의 가치가 작음.
엔트로피
무질서도를 정량화해서 표현한 값. 어떤 집합의 엔트로피가 높을 수록 그 집단의 특징을 찾는 것이 어렵다는 것을 의미.
따라서 Decision Tree의 node의 엔트로피가 최소가 되는 방향으로 분류해 나가는 것이 최적의 방법으로 분류한 것이라고 할 수 있음.
정보획득량은 전체 엔트로피에서 분류 후 엔트로피를 뺀 값을 의미. 분류 전 엔트로피가 1이었는데, 분류 후 엔트로피도 1이라면 정보획득은 전혀 일어난 것이 아님. 하지만 분류 전 엔트로피가 1이었는데, 분류 후 엔트로피가 0이 되었다면 모든 값들을 분류할 수 있게 되었다는 것을 의미하며 정보획득량은 1이라고 볼 수 있다.
지니계수(Gini Index)
엔트로피 이외에 불순도 지표로 많이 쓰이는 공식. 엔트로피보다 계산이 빠르기 때문에 주로 사용된다.
작동 원리
재귀적 분귀 (Recursive Partitioning)
정보획득량(분류 전 엔트로피 -분류 후 엔트로피)을 최소화하는 방향으로 계산을 반복한다. 이를 통해 가장 큰 정보획득량을 갖는 기준으로 첫 분류를 진행한다. 첫 분류를 진행한 뒤에는 분류된 대상을 같은 방법으로 또 분류해나간다. 이렇게 같은 방법을 다시 사용해나가면서 분류하는 과정을 재귀적 분귀(Recursive Partitioning)이라고 한다.
모든 잎의 엔트로피가 0이 될 때까지 반복한다. 하지만 모든 잎의 엔트로피가 0이 될때까지 분류를 반복하면, Overfitting 현상을 일으킬 수 있다. 따라서 일정 단계에서 중지시키거나 분기를 재조정 해줘야 한다.
일정단계에서 중지해주는 것은 정확히 언제인지 계산하기 어렵기 때문에 주로 분기를 재조정하는 방식을 사용한다. 분기를 재조정하는 방식을 가지치기(Pruning)이라고 한다.
가지치기 (Pruning)
Decision Tree의 Overfitting을 방지하는 방법.
모든 노드를 분리한 뒤 분기를 적절히 합치는 과정을 거쳐 일반화(generalization)를 해줄 필요가 있음.
가지치기의 정도를 결정하는 방법
- 에러감소 프루닝 (reduced error pruning)
모든 노드 아래부분을 자르거나 결합한 뒤의 오류와 결합 전의 오류를 비교하여 더 이상 오류가 줄어들기 전까지 반복하는 단순하고 직관적인 방법
2. 룰 포스트 프루닝 (rule post pruning)
룰은 루트 노드부터 잎 노드까지의 경로를 의미함. 트리를 모두 룰 형태로 변환한 뒤, 각 룰의 정확도를 구하고 정확도가 낮은 순서대로 제거하는 방법.
분류
- 새로운 데이터가 특정 terminal node(끝 노드)에 속한다는 정보를 확인함.
- 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류.
회귀
- 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환함.
- 이 때, 예측값은 종류는 terminal node의 개수와 일치함. 분류라고 생각하면 됨. (terminal node가 10개라면 10종류의 답만 출력함)
정리
Decision Tree 알고리즘은 계산복잡성 대비 높은 예측 성능을 가지고 있다. 또한 변수 단위로 설명력을 지닌다는 강점을 가지고 있다. 다만 결정경계(decision boundary)가 데이터 축에 수직이어서 비선형(non-linear) 데이터 분류엔 적합하지 않는다.
이같은 문제를 극복하기 위해 등장한 모델이 Random Forest이다.
이 글은 아래의 블로그를 기반으로 작성되었습니다.
https://gomguard.tistory.com/86, https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
