의사결정나무 분류

소개

DT(의사결정 트리)는 분류 및 회귀에 사용되는 비모수적 지도 학습 방법입니다. 목표는 데이터 특징에서 유추되는 간단한 의사결정 규칙을 학습하여 대상 변수의 값을 예측하는 모델을 만드는 것입니다.

엔트로피

훈련의 목표는 가장 최적의 트리를 찾기 위해 노드에서 최상의 분할을 찾는 것입니다. 분할은 엔트로피와 같은 몇 가지 기준을 사용하여 수행됩니다.

엔트로피에는 다음과 같은 다양한 정의가 있습니다.

• 엔트로피는 정보 소스에 포함된 정보의 양에 해당합니다.

• 엔트로피는 무작위성 또는 집합의 놀라움 측정으로도 볼 수 있습니다.

• 엔트로피는 시스템의 예측 불가능성 또는 불순물을 측정하는 척도입니다.

의사결정 트리에서는 엔트로피를 노드 내부의 순도를 측정하는 기준으로 간주합니다. 의사결정 트리 모델의 목표는 각 분할에서 노드의 엔트로피를 줄이는 것입니다.

따라서 우리는 부모 노드의 엔트로피와 자식 노드의 엔트로피 간의 차이를 최대화하려고 합니다. 이 차이를 정보 이득이라고 합니다.

집합 $X$의 엔트로피 $H$는 수학적으로 다음과 같이 공식화됩니다.

정보 획득

Information Gain은 부모 노드의 엔트로피와 chlid 노드의 엔트로피의 가중 합 간의 차이이므로 다음과 같이 공식화할 수 있습니다.

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

어디:

• $H(.)$는 엔트로피입니다.

• $Y$는 분할 전의 모집단이며 상위 노드를 나타냅니다.

• $X$는 분할에 사용하려는 변수입니다.

• $x$는 X의 고유한 값입니다.

• $Y[X==x]$는 $x$ 값만 포함된 분할 목록입니다.

적절한 예를 들어보자:

X 값을 사용하여 상위 노드를 나눌 때 정보 이득을 계산하겠습니다.

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

\

먼저 부모 노드의 엔트로피를 계산합니다.

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

\

그런 다음 X의 고유 값을 사용하여 분할 후 각 하위 노드의 내부 확률을 계산합니다.

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

와 같은:

• $H(Y | X = Square)$ : 첫 번째 자식 노드의 엔트로피를 나타냅니다.

• $H(Y | X = Circle)$ : 두 번째 자식 노드의 엔트로피를 나타냅니다.

\

첫 번째 하위 노드부터 시작합니다.

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

\

그런 다음 두 번째 하위 노드는 다음과 같습니다.

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

\

마지막으로 정보 이득 공식의 엔트로피를 다음과 같이 대체합니다.

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

\

\

앞에서 설명한 것처럼 노드 분할의 목적은 정보 이득을 최대화하여 결과 하위 노드의 엔트로피를 최소화하는 것입니다. 이를 위해서는 서로 다른 입력 세트 $X_1, X_2, \ldots, Xn$로 노드를 분할해야 하며 정보 이득을 최대화하는 분할만 유지합니다.

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

분할을 중단해야 하는 경우

의사결정 트리의 노드 분할은 재귀적이므로 분할을 중지하기 위해 사용할 수 있는 기준이 있어야 합니다. 가장 많이 구현된 기준은 다음과 같습니다.

• 노드가 순수할 때: H(노드) = 0. 더 이상 노드를 분할하는 것은 의미가 없습니다.

• 최대 깊이 수: 모델이 도달할 수 있는 최대 깊이를 설정할 수 있습니다. 즉, 노드가 순수하지 않더라도 분할이 중지됩니다.

• 노드당 최소 샘플 수: 노드당 최소 샘플 수 $N$를 설정할 수도 있습니다. 노드당 샘플 수가 $N$과 같으면 노드가 순수하지 않더라도 분할을 중지합니다.

훈련이 끝날 때(분할) 결정 트리의 끝에 의존하는 각 노드는 하위 트리의 루트가 아니기 때문에 "리프"라고 합니다. 각 리프는 가장 많은 샘플을 보유한 클래스를 나타냅니다.

결론

의사결정 트리는 효율성, 직관적인 배경 및 간단한 구현으로 인해 가장 유명한 기계 학습 알고리즘 중 하나입니다. 이 알고리즘은 수치 독립 변수(Gaussian Decision Tree)와 함께 추가로 사용될 수 있으며 회귀 작업을 해결하기 위해 확장될 수도 있습니다.