분류 및 회귀 트리/CART
CART는 입력 확률 변수 X가 주어졌을 때 출력 확률 변수 Y의 조건부 확률 분포를 학습하는 방법입니다.
정의
CART는 의사결정 트리가 이진 트리이고, 내부 노드 특징의 값이 "예"와 "아니오"라고 가정합니다. 왼쪽 가지는 "예" 값을 갖는 가지이고, 오른쪽 가지는 "아니오" 값을 갖는 가지입니다. 이러한 의사결정 트리는 각 특징을 두 개로 재귀적으로 나누고, 입력 공간, 즉 특징 공간을 유한한 수의 단위로 나누고, 이러한 단위에 대한 예측 확률 분포, 즉 주어진 입력 조건에서 출력의 조건부 확률 분포를 결정하는 것과 같습니다.
CART 알고리즘은 다음 두 단계로 구성됩니다.
- 트리 생성: 훈련 데이터 세트를 기반으로 의사결정 트리를 생성합니다. 생성된 의사결정 트리는 가능한 한 커야 합니다.
- 트리 가지치기: 검증 데이터 세트를 사용하여 생성된 트리를 가지치고 최적의 서브트리를 선택합니다. 최소 손실 함수가 가지치기 기준으로 사용됩니다.
의사결정 트리의 생성은 이진 의사결정 트리를 재귀적으로 구성하는 과정입니다. 회귀 트리에는 제곱 오차 최소화 기준이 사용되고, 분류 트리에는 지니 지수 최소화 기준이 사용되어 특성 선택을 수행하고 이진 트리를 생성합니다.
회귀 트리 생성
X와 Y가 각각 입력 벡터와 출력 벡터이고, Y가 연속 변수라고 가정합니다. 학습 데이터 세트 가 주어졌을 때 회귀 트리를 생성하는 방법을 고려해 보세요.
회귀 트리는 입력 공간(즉, 특징 공간)의 분할과 해당 분할의 각 단위의 출력 값에 해당합니다. 입력 공간이 M개의 단위 $latex R_{1}, R_{2}, \ldots, R_{M}$로 나뉘었고 각 단위 $latex R_{m} $에 고정된 출력 값 $latex c_{m} $가 있다고 가정합니다. 그러면 회귀 트리 모델은 다음과 같이 표현할 수 있습니다. $latex f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right) $
입력 공간의 분할이 결정되면 제곱 오차를 사용할 수 있습니다.$latex \sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$
훈련 데이터에 대한 회귀 트리의 예측 오차를 나타내기 위해, 각 단위의 최적 출력 값은 최소 제곱 오차의 기준을 사용하여 풀립니다. 단위 $latex R_{m} $의 최적값 $latex c_{m} $는 모든 입력 인스턴스 $latex x_{i} $에 대한 출력 $latex y_{i} $의 평균인 것을 쉽게 알 수 있습니다. 즉,
문제는 입력 공간을 어떻게 분할하느냐이다. 여기서 우리는 첫 번째를 선택하기 위해 휴리스틱 방법을 사용합니다. 제이 변수 $latex x^{(j)}$와 그에 따른 값 에스 , 분할 변수 및 분할 지점으로 두 영역을 정의합니다.
그런 다음 최적의 분할 변수를 찾으세요. 제이 그리고 최적의 분할점 에스 . 구체적으로 해결하다
고정된 입력 변수의 경우 제이 최적의 분할점을 찾을 수 있습니다 에스
모든 입력 변수를 탐색하고 최적의 분할 변수를 찾습니다. 제이 , $latex (j, s) $ 쌍을 형성하여 입력 공간을 두 개의 영역으로 나눕니다. 그런 다음, 중지 조건이 충족될 때까지 위의 분할 과정이 각 영역에 대해 반복됩니다.
분류 트리 생성
분류 트리는 지니 지수를 사용하여 최적의 특징을 선택하고 특징의 최적 이진 절단점을 결정합니다.
지니계수
분류 과정에서 K개의 클래스가 있다고 가정할 때, 샘플 포인트가 k번째 클래스에 속할 확률은 $latex p_{k} $이고, 이 확률 분포의 지니 지수는 다음과 같이 정의됩니다.
2개 클래스 분류 문제의 경우, 샘플 포인트가 첫 번째 클래스에 속할 확률이 p인 경우, 확률 분포의 지니 지수는 다음과 같습니다.
주어진 샘플 집합 D에 대해 지니 지수는 다음과 같습니다.
그중 $latex C_{k} $는 D에 있는 k번째 클래스에 속하는 샘플들의 부분집합이고, K는 클래스의 개수이다.
샘플 집합 D가 특징 A가 특정 가능한 값 a를 취하는지 여부에 따라 $latex D_{1}$와 $latex D_{2}$의 두 부분으로 나뉜다면, 즉 다음과 같습니다.
그러면 특징 A의 조건 하에서 집합 D의 지니 지수는 다음과 같이 정의됩니다.
지니 지수 $latex {Gini}(D) $는 집합 D의 불확실성을 나타내고, 지니 지수 $latex {Gini}(D, A) $는 A=a로 분할한 후 집합 D의 불확실성을 나타냅니다. 지니 지수가 클수록 표본 집합의 불확실성이 커지는데, 이는 엔트로피와 유사합니다.
생성 알고리즘
입력: 훈련 데이터 세트 D, 계산 중지 조건
출력: CART 의사결정 트리
훈련 데이터 세트에 따르면 루트 노드에서 시작하여 각 노드에서 다음 작업을 재귀적으로 수행하여 이진 결정 트리를 구축합니다.
- 노드의 학습 데이터 집합을 D라고 가정하고, 데이터 집합에 대한 기존 특성의 지니 계수를 계산합니다. 이때 각 특징 A에 대하여 가능한 값 a, D는 샘플 포인트 A=a의 검정이 "예"인지 "아니오"인지에 따라 $latex D_{1} $와 $latex D_{2} $의 두 부분으로 나뉘며, A=a일 때의 지니계수를 계산한다.
- 가능한 모든 특징 A와 가능한 모든 분할점 a 중에서 가장 작은 지니 지수와 해당 분할점을 갖는 특징을 최적의 특징과 최적 분할점으로 선택합니다. 최적의 특징과 최적의 분할 지점을 기반으로 현재 노드에서 두 개의 자식 노드를 생성하고, 특징에 따라 두 자식 노드에 교육 데이터 세트를 분배합니다.
- 중지 조건이 충족될 때까지 두 자식 노드에 대해 (1)과 (2)를 재귀적으로 호출합니다.
- CART 의사결정 트리 생성