Study/머신러닝
4. Decision Tree
우당탕탕코린이
2024. 2. 20. 15:28
의사결정 트리 분류기 (Decision Tree Classifier)
- 의사결정 트리 분류기는 트리 모양의 순차형 다이어그램을 통해 주어진 데이터를 분류.
- 트리의 루트부터 시작해서 모든 중간 노드들은 의사 결정 사항 (조건)
- 트리의 맨 끝에 있는 리프 노드는 의사 결정 사항에 따른 최종 결과
- 의사결정 트리 분류기의 동작은 의사결정 트리를 생성하는 학습 단계와 생성된 의사결정 트리에 따라 주어진 데이터를 분류하는 분류 단계로 나눠 볼 수 있다.
- 대표적인 트리 생성 알고리즘 : ID3, C4.5, CART, CHAID
- 예시
- 의사결정 트리는 데이터를 재귀적으로 파티셔닝하여 생성.
CART (Classification and Regression Tree)
- 학습데이터를 사용하여 각 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 분할해 가며 트리를 생성.
- 기본적으로는 클래스 별로 데이터를 잘 가를 수 있으면 좋은 분할.
- 하지만 하나의 피처와 해당 값으로 전체 데이터를 클래스 별로 완벽하게 가를 수는 없기 때문에, 단계적으로 분할 조건들을 탐색해 나가야 한다.
- CART는 각 노드에서 분할을 위한 피처와 해당 피처의 값의 조합을 탐욕적(Greedy) 방식으로 탐색
- Global Optima가 아니라 Local Optima를 우선 고려.
- 작동 과정
- 분할
- 각 노드에서 분할을 위한 피처와 해당 피처의 값의 조합을 탐욕적(Greedy) 방식으로 탐색
- Global Optima가 아니라 Local Optima를 우선 고려.
- 정지 : 분할 과정은 다음과 같은 조건들이 만족되면 중지
- 분할 후 만들어질 노드의 샘플 수가 일정 수준 이하일 때
- 트리의 깊이가 일정 수준 이상일 때 -> 오버피팅을 피하기 위한 조치
- 분할되지 않은 마지막 노드들에 클래스 레이블을 할당하는데, 각 노드에 있는 데이터의 클래스 중 가장 다수 클래스를 할당.
- 분할
- 이를 위해서는 어떤 피처와 해당 값을 선택했을 때 데이터를 클래스 별로 얼마나 잘 분할해 내는지 평가할 수 있는 값이 필요하다. -> 트리 분할 척도 (지니계수, 정보이득)
트리 분할 측정 척도
- 각 피처와 해당 값들이 가장 잘 조합된 결과를 선택하기 위해 분할이 얼마나 잘 이루어졌는지를 측정하는 척도
- 대표적인 트리 분할 츨정 척도
- 지니 계수 (Gini Impurity)
- 정보 이득 (Information Gain), Entropy
지니 계수 (Gini Impurity)
- 데이터가 클래스 별로 고르게 분포되어 있는지, 아니면 특정 클래스에 편중되어 분포되어 있는지 나타냄
- 편중될수록 지니 계수가 작고, 고를수록 크다.
- 두 개의 클래스가 존재할 때,
- 모든 데이터가 한 클래스에만 속한다면 지니계수는 1 - (1*1 + 0*0) = 0
- 두 클래스가 반반씩 속한다면 지니계수는 1 - (0.5 * 0.5 + 0.5 * 0.5) = 0.5
- 분할한 결과로 만들어진 자식 노드들 각각에 대해서 지니 계수를 구하고 가중평균하여 분할 결과를 측정.
- 지니 계수가 작을수록 클래스를 편중해서 잘 갈라냈음을 의미.
정보 이득
- 트리 분할 후 얼마나 순도가 더 좋아졌는지 평가한다.
- = 트리 분할을 통해 불확실성이 얼마나 줄어드는지를 축정한다.
- 불확실성이 높다는 것은 클래스 별로 고르게 분포되어 있다는 것.
- 모든 클래스에 똑같은 비율로 데이터가 존재할 때, 여기서 어떤 데이터를 임의로 뽑는다면 이 데이터가 어떤 클래스에 속할지 불확실하다.
- 반대로, 특정 클래스에 편중되어 있으면 데이터의 클래스에 대한 불확실성이 낮다.
- 정보 이득은 트리 분할 전 후의 엔트로피 값 차이로 계산된다.
- 2개의 클래스가 존재할 때,
- 모든 데이터 한 클래스에만 속한다면 엔트로피는 -( 1 * log2(1) + 0 ) = 0
- 두 클래스에 반반씩 속한다면 엔트로피는 -( 0.5 * log2(0.5) + 0.5 * log2(0.5) ) = 1
- 정보 이득은 트리 분할 전 (부모 노드) 엔트로피와 트리 분할 수 (자식 노드들) 엔트로피 값의 차이로 정의
- 자식 노드들의 엔트로피 값은 지니 계수와 같은 방식으로 가중 평균하여 계산.
